Top100题
散列
struct MyListNode {
int val;
int pos;
struct MyListNode *next;
};
// 散列表
typedef struct {
struct MyListNode *data;
} MyHashMap;
const int hashSize = 1543;
MyHashMap *createHashMap() {
MyHashMap *hashMap = (MyHashMap *) malloc(sizeof(MyHashMap));
hashMap->data = (struct MyListNode *) malloc(sizeof(struct MyListNode) * hashSize);
for (int i = 0; i < hashSize; ++i) {
hashMap->data[i].val = 0x80000000;
hashMap->data[i].pos = -1;
hashMap->data[i].next = NULL;
}
return hashMap;
}
int hash(int key) {
return (key+1000000000) % hashSize;
}
struct MyListNode *getList(MyHashMap *hashMap, int key) {
return &(hashMap->data[hash(key)]);
}
int containsKey(MyHashMap *hashMap, int key) {
struct MyListNode *head = getList(hashMap, key);
while (head != NULL) {
if (head->val == key) return head->pos;
head = head->next;
}
return -1;
}
void insert(MyHashMap *hashMap, int key, int pos) {
if (containsKey(hashMap, key) != -1)return;
struct MyListNode *head = getList(hashMap, key);
struct MyListNode *node = (struct MyListNode *) malloc(sizeof(struct MyListNode));
node->val = key;
node->pos = pos;
node->next = head->next;
head->next = node;
}
int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 0;
MyHashMap *hashMap = (MyHashMap *) malloc(sizeof(MyHashMap));
hashMap = createHashMap();
for (int i = 0; i < numsSize; ++i) {
int t = containsKey(hashMap, target - nums[i]);
if (t != -1) {
res[0] = i;
res[1] = t;
*returnSize = 2;
return res;
} else {
insert(hashMap, nums[i], i);
}
}
return res;
}
// todo
int cmp(const void *a, const void *b) {
return (*(int *) a) - (*(int *) b);
}
// 时间复杂度O（nlogn）
int longestConsecutive(int *nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int maxLen = 0, tempLen = 0;
for (int i = 0; i < numsSize; ++i) {
if (i == 0) {
tempLen++;
maxLen = 1;
} else {
if (nums[i] - nums[i - 1] == 0) continue;
if (nums[i] - nums[i - 1] == 1) {
tempLen++;
if (tempLen > maxLen) maxLen = tempLen;
} else {
// 当前值不是前一个值加1，则这个值是一个新序列的开头
tempLen = 1;
}
}
}
return maxLen;
}
class Solution {
// 时间复杂度O（n）
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
// 加入集合，对数组去重
for (int num : nums) set.add(num);
int maxLen = 0;
for (Integer num : set) {
// 先检查上个元素是否出现在set中，如果有就不用重复统计tempLen了
if (!set.contains(num - 1)) {
// 如果上个元素不在set中，则这个元素就是这个序列的首个元素
int tempLen = 1;
int curNum = num + 1;
// 依次判断后续一个元素是否在set中
while (set.contains(curNum)) {
tempLen++;
curNum++;
}
maxLen = Math.max(tempLen, maxLen);
}
}
return maxLen;
}
}
双指针
void moveZeroes(int *nums, int numsSize) {
// slow指向当前应该存放非零元素的位置
int slow = 0;
// fast遇到非零元素时，就把元素移到nums[slow]中
int fast = 0;
while (fast < numsSize) {
if (nums[fast] != 0) {
nums[slow++] = nums[fast];
}
fast++;
}
// slow及其后面的都是0
while (slow < numsSize) {
nums[slow++] = 0;
}
}
int min(int a, int b) {
return a < b ? a : b;
}
int max(int a, int b) {
return a > b ? a : b;
}
// 暴力枚举
int maxArea(int *height, int heightSize) {
int res = 0;
for (int i = 0; i < heightSize; ++i) {
for (int j = i + 1; j < heightSize; ++j) {
int temp = (j - i) * min(height[i], height[j]);
res = max(res, temp);
}
}
return res;
}
int min(int a, int b) {
return a < b ? a : b;
}
int max(int a, int b) {
return a > b ? a : b;
}
int maxArea(int *height, int heightSize) {
int left = 0, right = heightSize - 1;
int res = 0;
while (left < right) {
int temp = (right - left) * min(height[left], height[right]);
res = max(res, temp);
// 每次把短板往里移动，短板可能变长，总面积才可能变大
// 如果移动长板，底一定变小，高度不会超过之前的那个短板，高只会原来越低，面积只会变小
if (height[left] < height[right])
left++;
else
right--;
}
return res;
}
int cmp(const void *a, const void *b) {
return (*(int *) a) - (*(int *) b);
}
// 三元组最大个数
const int SIZE = 20000;
int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
if (nums == NULL || numsSize < 3) return NULL;
int **res = (int **) malloc(sizeof(int *) * SIZE);
int index = 0;
*returnColumnSizes = (int *) malloc(sizeof(int) * SIZE);
*returnSize = 0;
// 排序
qsort(nums, numsSize, sizeof(int), cmp);
// 排序后最后一个数小于0时，不符合题意
if (nums[numsSize - 1] < 0) return NULL;
for (int i = 0; i < numsSize - 2; ++i) {
// 当前值都大于0了，后面就没必要找了
if (nums[i] > 0) break;
if (i > 0) {
// 上一个固定i的情况已经讨论完了，包括nums[left]，nums[right]也等于nums[i]的情况
// i必须更新到下一个值不同的地方
while ((i < numsSize - 2) && nums[i] == nums[i - 1]) i++;
}
int left = i + 1, right = numsSize - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res[index] = (int *) malloc(sizeof(int) * 3);
res[index][0] = nums[i];
res[index][1] = nums[left];
res[index][2] = nums[right];
index++;
// 当前的left，right，i是符合要求的三元组
// 固定i，同时变动left，right使nums[left]，nums[right]都变成新的值
// 若只变动left，right中的一个，那这三个数一定不符合题意，因为原来的三个刚好符合题意
// 把left移到与当前值相同的最后一个位置
while (left < right && nums[left] == nums[left + 1]) left++;
// 把left移动到和当前值不同的第一个位置
left++;
while (left < right && nums[right] == nums[right - 1]) right--;
right--;
// left，right找完了，跳出循环，修改i
if (left >= right) break;
} else if (sum > 0) {
// right移到比当前值小的下一个元素
while (left < right && nums[right] == nums[right - 1]) right--;
right--;
} else {
// left移到比当前值大的下一个元素
while (left < right && nums[left] == nums[left + 1]) left++;
left++;
}
}
}
*returnSize = index;
*returnColumnSizes = (int *) malloc(sizeof(int) * index);
for (int i = 0; i < index; ++i) {
(*returnColumnSizes)[i] = 3;
}
return res;
}
// 按行累积，每次累加当前行上能接多少水（超时）
int trap(int *height, int heightSize) {
int res = 0;
int lever = 1;
// 找最大高度
int maxHeight = 0;
for (int i = 0; i < heightSize; ++i)
if (height[i] > maxHeight) maxHeight = height[i];
// 每次找一层，一格一格的加
while (lever <= maxHeight) {
int i = 0;
// 找到第一个不低于当前lever的作为左边界
while (i < heightSize && height[i] < lever) i++;
if (i >= heightSize) continue;
int temp = 0;
while (i < heightSize) {
if (height[i] < lever) {
// 已有左边界，并且比当前层低，说明这个格子(i, lever)可以放水
temp++;
} else if (height[i] >= lever) {
// 找到大于或等于当前层的右边界，就把之前累积的水加到结果中，并清空temp
// 当前的右边界变成下一个左边界，在继续寻找下一个右边界
res += temp;
temp = 0;
}
i++;
}
lever++;
}
return res;
}
int findMax(int *height, int start, int end) {
int max = height[start];
while (start <= end) {
if (height[start] > max) max = height[start];
start++;
}
return max;
}
// 按列累积，每次累加当前列上能接多少水
int trap(int *height, int heightSize) {
int res = 0;
// 记录当前元素左边的最大值
int tempLeftMax = height[0];
int leftMaxArr[heightSize];
for (int i = 1; i <= heightSize - 2; ++i) {
leftMaxArr[i] = tempLeftMax;
if (height[i] > tempLeftMax) tempLeftMax = height[i];
}
// 记录当前元素右边的最大值
int tempRightMax = height[heightSize - 1];
int rightMaxArr[heightSize];
for (int i = heightSize - 2; i >= 1; i--) {
rightMaxArr[i] = tempRightMax;
if (height[i] > tempRightMax) tempRightMax = height[i];
}
for (int i = 1; i < heightSize - 1; ++i) {
// 找左右两边最高的列
// 1.大量重复寻找会超时
// int leftMax = findMax(height, 0, i - 1);
// int rightMax = findMax(height, i + 1, heightSize - 1);
// 2.两边遍历保存结果
int leftMax = leftMaxArr[i];
int rightMax = rightMaxArr[i];
int min = leftMax < rightMax ? leftMax : rightMax;
// 只有左边最高的和右边最高的，二者中的较小者比当年的列高，当前列才能接得住水
// 较小者小于等于当前列，接不住水
if (min > height[i]) res += min - height[i];
}
return res;
}
// 用leftMax优化掉leftMaxArr数组
// 由于i是从左往右，所以rightMaxArr没法用这个办法优化掉
int trap(int *height, int heightSize) {
int res = 0;
// 记录当前元素右边的最大值
int tempRightMax = height[heightSize - 1];
int rightMaxArr[heightSize];
for (int i = heightSize - 2; i >= 1; i--) {
rightMaxArr[i] = tempRightMax;
if (height[i] > tempRightMax) tempRightMax = height[i];
}
// *记录当前元素左边的最大值
int leftMax = height[0], rightMax;
for (int i = 1; i < heightSize - 1; ++i) {
// 找左右两边最高的列
rightMax = rightMaxArr[i];
int min = leftMax < rightMax ? leftMax : rightMax;
// 只有左边最高的和右边最高的，二者中的较小者比当年的列高，当前列才能接得住水
// 较小者小于等于当前列，接不住水
if (min > height[i]) res += min - height[i];
// *更新leftMax
if (height[i] > leftMax) leftMax = height[i];
}
return res;
}
// 双指针优化掉leftMaxArr、rightMaxArr
int trap(int *height, int heightSize) {
int res = 0;
// 柱子能接到的水 = min{左右两边最高的柱子} - 当前柱子的高度
// L、R是两根柱子，本应该有L的两个变量leftMaxOfL、rightMaxOfL和R的两个变量leftMaxOfR、rightMaxOfR
// 由于L < R，所以leftMaxOfL <= leftMaxOfR，rightMaxOfR <= rightMaxOfL
// 从而如果leftMaxOfL > rightMaxOfR，则一定有leftMaxOfR >= rightMaxOfR，即在R处，左边最高的柱子大于右边最高的柱子，此时可以计算在R处能接到的水
// 如果leftMaxOfL < rightMaxOfR，则一定有rightMaxOfL >= leftMaxOfL，即在L处，右边最高的柱子大于左边最高的柱子，此时可以计算在L处能接到的水
// 实际上只用到了leftMaxOfL和rightMaxOfR这两个变量
// 记录当前元素左边的最大值
int leftMaxOfL = height[0], rightMaxOfR = height[heightSize - 1];
// 双指针，L、R代替原来的i
int L = 1, R = heightSize - 2;
for (int i = 1; i < heightSize - 1; ++i) {
// leftMaxOfL = leftMaxArr[L] = max(leftMaxArr[L-1], height[L-1])
// 即当前位置的左侧最大元素，是上个元素的左侧最大元素和上个元素两者中的较大者，height[L-1]是可能成为leftMax的变量
// 同理，当前位置的右侧最大元素，是后个元素的右侧最大元素和后个元素两者中的较大者，height[R+1]是可能成为rightMax的变量
if (height[L - 1] < height[R + 1]) {
// 从左往右更新
// 当height[L-1] < height[R+1]时，一定有leftMaxOfL < rightMaxOfR todo ???
// [1,5,3,4,2,6]
// 此时min=leftMaxOfL
int min = leftMaxOfL;
if (min > height[L]) res += min - height[L];
// 更新leftMax
if (height[L] > leftMaxOfL) leftMaxOfL = height[L];
L++;
} else {
// 从右往左更新
int min = rightMaxOfR;
if (min > height[R]) res += min - height[R];
// 更新rightMax
if (height[R] > rightMaxOfR) rightMaxOfR = height[R];
R--;
}
}
return res;
}
// todo 栈
int trap(int *height, int heightSize) {
int res = 0;
int stack[heightSize];
int top = 0;
int current = 0;
while (current < heightSize) {
// 当前高度大于栈顶高度，说明之前的地方能接水，持续出栈到栈顶高度大于等于当前高度或者直到栈空为止
while (top > 0 && height[current] > height[stack[top - 1]]) {
// 栈顶出栈
int h = height[stack[top - 1]];
top--;
if (top == 0) break;
// 两个柱子间的距离
int distance = current - stack[top - 1] - 1;
// 新的栈顶高度和当前高度的较小者
int min = height[stack[top - 1]] < height[current] ? height[stack[top - 1]] : height[current];
res += distance * (min - h);
}
stack[top++] = current;
current++;
}
return res;
}
滑动窗口
int lengthOfLongestSubstring(char *s) {
int len = strlen(s);
if (len < 2) return len;
// 记录当前在滑动窗口中的字符
int *hashSet = (int *) calloc(128, sizeof(int));
int left = 0, right = 0;
hashSet[s[right]] = 1;
int res = 1;
while (right + 1 < len) {
// 待进入窗口的下个字符
char nextChar = s[right + 1];
if (hashSet[nextChar] == 0) {
// 未出现过就加入到窗口中
hashSet[nextChar] = 1;
right++;
// 更新最大长度
if ((right - left + 1) > res) res = right - left + 1;
} else {
// 已经出现在窗口中，就移动left
while (left <= right && s[left] != nextChar) {
// 去掉left之前的字符
hashSet[s[left]] = 0;
left++;
}
// 此时s[left]和nextChar相等
// 窗口整体右移一格
left++;
right++;
}
}
return res;
}
// todo
子串
// 暴力枚举(超时)
int subarraySum(int *nums, int numsSize, int k) {
int res = 0;
for (int i = 0; i < numsSize; ++i) {
int tempSum = 0;
for (int j = i; j < numsSize; ++j) {
tempSum += nums[j];
if (tempSum == k) res++;
}
}
return res;
}
// 记录前缀和(超时)
int subarraySum(int *nums, int numsSize, int k) {
int *prefixSum = (int *) calloc(numsSize + 1, sizeof(int));
for (int i = 1; i <= numsSize; ++i) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
int res = 0;
for (int i = 0; i < numsSize; ++i) {
for (int j = i; j < numsSize; ++j) {
if (prefixSum[j + 1] - prefixSum[i] == k) res++;
}
}
return res;
}
// todo
// 只关心有多少个prefixSum[j]满足prefixSum[j]等于prefixSum[i] - k，不关心j的具体位置
int subarraySum(int *nums, int numsSize, int k) {
int res = 0;
const int size = 20000 * 1000;
// 最多20000个数，和的范围是[-20000000, 20000000]，右移20000000，使其下标从0开始，[0, 40000000]
int *hashMap = (int *) calloc(size * 2, sizeof(int));
// 记录前缀和(prefixSum[i]不包括i处的元素)
// j < i, prefixSum[i] - prefixSum[j] = k时，说明[j, i-1]就是一个和为k的子数组
// 转化为累加prefixSum[j]等于prefixSum[i] - k的个数
int *prefixSum = (int *) calloc(numsSize + 1, sizeof(int));
// 第一个元素的前缀和是0，单独记录下这个0出现过一次（不然就修改定义，prefixSum[i]改成包括i处的元素）
hashMap[0 + size]++;
for (int i = 1; i <= numsSize; ++i) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
res += hashMap[prefixSum[i] - k + size];
// 累加前缀和为prefixSum[i]出现的次数
hashMap[prefixSum[i] + size]++;
}
return res;
}
普通数组
矩阵
链表
二叉树