文章目录
- 题目一：盛最多水的容器
- 题目描述：
- 题目分析：
- 解题思路：
- 示例代码：
- 深入剖析：
- 题目二：最长无重复字符的子串
- 题目描述：
- 题目分析：
- 解题思路：
- 示例代码：
- 深入剖析：
- 题目三：合并区间
- 题目描述：
- 题目分析：
- 解题思路：
- 示例代码：
- 深入剖析：
🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨
题目一：盛最多水的容器
题目描述：
给定 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;
}
深入剖析：
该算法的时间复杂度为O(n log n)，其中n是区间的数量，因为我们需要对区间进行排序。空间复杂度为O(n)，因为我们需要动态分配一个与区间数量相等大小的结果数组。合并区间的技巧在处理类似问题时非常有用，特别是当问题涉及到重叠区间的合并、求并集等操作时。
✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊
🏠 我在CSDN等你哦！我的主页😍
_笔记)
)
