当前位置：首页 > ds >正文

【Leecode 随笔】

ds 2025/7/19 20:28:11

在这里插入图片描述

文章目录

- 题目一：盛最多水的容器
- - 题目描述：
  - 题目分析：
  - 解题思路：
  - 示例代码：
  - 深入剖析：
- 题目二：最长无重复字符的子串
- - 题目描述：
  - 题目分析：
  - 解题思路：
  - 示例代码：
  - 深入剖析：
- 题目三：合并区间
- - 题目描述：
  - 题目分析：
  - 解题思路：
  - 示例代码：
  - 深入剖析：

🌈你好呀！我是山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨

题目一：盛最多水的容器

题目描述：

给定 n 个非负整数 a1，a2，…，an，每个数代表一个坐标点 (i, ai) 。在坐标内画 n 条垂直线，使得 i 垂直线的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴构成的容器可以容纳最多的水。

题目分析：

这是一个典型的双指针问题。我们可以使用两个指针分别指向数组的首尾，然后计算当前两个指针所构成的容器的面积。接着，我们移动指向较短线段的指针（因为容器的高度由较短的线段决定，移动较长线段的指针无法增加容器的高度，而只会减少容器的宽度），直到两个指针相遇。

解题思路：

初始化两个指针，一个指向数组的开始，另一个指向数组的末尾。
计算当前两个指针所构成的容器的面积，并更新最大面积。
移动指向较短线段的指针。
重复步骤2和3，直到两个指针相遇。
返回最大面积。

示例代码：

#include <stdio.h>  // 函数声明  
int maxArea(int* height, int heightSize);  int main() {  int height[] = {1,8,6,2,5,4,8,3,7};  int heightSize = sizeof(height) / sizeof(height[0]);  int result = maxArea(height, heightSize);  printf("Maximum area: %d\n", result);  return 0;  
}  // 计算最大容器面积的函数实现  
int maxArea(int* height, int heightSize) {  int max_area = 0;  int left = 0;  int right = heightSize - 1;  while (left < right) {  // 计算当前容器的面积  int current_area = (right - left) * ((height[left] < height[right]) ? height[left] : height[right]);  // 更新最大面积  if (current_area > max_area) {  max_area = current_area;  }  // 移动指向较短线段的指针  if (height[left] < height[right]) {  left++;  } else {  right--;  }  }  return max_area;  
}

深入剖析：

该算法的时间复杂度为O(n)，因为我们只遍历了数组一次。空间复杂度为O(1)，因为我们只使用了常数级别的额外空间。这种双指针的技巧在处理类似问题时非常有用，特别是当问题涉及到数组或链表的两端时。

题目二：最长无重复字符的子串

题目描述：

给定一个字符串，找出其中没有重复字符的最长子串的长度。

题目分析：

这是一个滑动窗口问题。我们可以使用两个指针来定义一个窗口，窗口内的字符都是唯一的。当遇到重复字符时，我们移动左指针来缩小窗口，直到窗口内没有重复字符为止。同时，我们需要一个哈希表来记录每个字符在窗口中的位置，以便在O(1)时间内判断字符是否重复。

解题思路：

初始化两个指针（left和right）和一个哈希表（用于记录字符的位置）。
使用right指针扩展窗口，直到遇到重复字符。
当遇到重复字符时，移动left指针缩小窗口，直到窗口内没有重复字符。
在每次移动窗口后，更新最大长度。
重复步骤2-4，直到right指针到达字符串的末尾。
返回最大长度。

示例代码：

#include <stdio.h>  
#include <string.h>  // 函数声明  
int lengthOfLongestSubstring(char * s);  int main() {  char s[] = "abcabcbb";  int result = lengthOfLongestSubstring(s);  printf("Length of longest substring without repeating characters: %d\n", result);  return 0;  
}  // 计算最长无重复字符子串长度的函数实现  
int lengthOfLongestSubstring(char * s) {  int n = strlen(s);  if (n == 0) {  return 0;  }  int max_len = 0;  int left = 0;  int right = 0;  int char_map[256] = { -1 }; // 假设输入字符为ASCII码  while (right < n) {  if (char_map[s[right]] != -1) {  // 遇到重复字符，移动左指针  left = (char_map[s[right]] + 1 > left) ? char_map[s[right]] + 1 : left;  }  // 更新字符的位置  char_map[s[right]] = right;  // 更新最大长度  max_len = (right - left + 1 > max_len) ? right - left + 1 : max_len;  // 移动右指针  right++;  }  return max_len;  
}

深入剖析：

该算法的时间复杂度为O(n)，因为我们只遍历了字符串一次。空间复杂度为O(1)（如果考虑哈希表的大小为常数，因为ASCII码字符集是有限的），但实际上哈希表的大小取决于字符集的大小，对于Unicode字符集，空间复杂度会稍大一些。滑动窗口技巧在处理子串、子数组相关问题时非常有效。

题目三：合并区间

题目描述：

给出一个区间的集合，请合并所有重叠的部分。

题目分析：

这是一个排序和合并问题。首先，我们需要对区间按照起始位置进行排序。然后，我们遍历排序后的区间列表，使用一个变量来跟踪当前的合并区间。如果下一个区间的起始位置小于或等于当前合并区间的结束位置，则将它们合并；否则，将当前合并区间添加到结果列表中，并更新合并区间为下一个区间。

解题思路：

对区间按照起始位置进行排序。
初始化一个空的结果列表和一个变量来跟踪当前的合并区间。
遍历排序后的区间列表：
如果当前区间与合并区间重叠，则合并它们。
否则，将合并区间添加到结果列表中，并更新合并区间为当前区间。
将最后一个合并区间添加到结果列表中。
返回结果列表。

示例代码：

#include <stdio.h>  
#include <stdlib.h>  // 区间结构体定义  
typedef struct {  int start;  int end;  
} Interval;  // 比较函数，用于qsort排序  
int compare(const void *a, const void *b) {  Interval *intervalA = (Interval *)a;  Interval *intervalB = (Interval *)b;  return intervalA->start - intervalB->start;  
}  // 合并区间的函数声明  
Interval* merge(Interval* intervals, int intervalsSize, int* returnSize);  int main() {  Interval intervals[] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};  int intervalsSize = sizeof(intervals) / sizeof(intervals[0]);  int returnSize = 0;  Interval* result = merge(intervals, intervalsSize, &returnSize);  printf("Merged intervals:\n");  for (int i = 0; i < returnSize; i++) {  printf("[%d, %d] ", result[i].start, result[i].end);  }  printf("\n");  // 释放动态分配的内存  free(result);  return 0;  
}  // 合并区间的函数实现  
Interval* merge(Interval* intervals, int intervalsSize, int* returnSize) {  if (intervalsSize == 0) {  *returnSize = 0;  return NULL;  }  // 按照起始位置排序区间  qsort(intervals, intervalsSize, sizeof(Interval), compare);  // 动态分配结果数组的内存  Interval* merged = (Interval*)malloc(intervalsSize * sizeof(Interval));  *returnSize = 0;  // 初始化当前合并区间  Interval current = intervals[0];  for (int i = 1; i < intervalsSize; i++) {  if (intervals[i].start <= current.end) {  // 当前区间与合并区间重叠，合并它们  current.end = (intervals[i].end > current.end) ? intervals[i].end : current.end;  } else {  // 当前区间与合并区间不重叠，将合并区间添加到结果列表中，并更新合并区间  merged[*returnSize] = current;  (*returnSize)++;  current = intervals[i];  }  }  // 添加最后一个合并区间到结果列表中  merged[*returnSize] = current;  (*returnSize)++;  return merged;  
}