Leetcode 刷题记录

Knuth 也要刷题了^-^

-讲个冷笑话

Day 1
3. 无重复字符的最长子串：哈希表、滑动窗口

Day2
239. 滑动窗口最大值
优先队列 /单调队列

Day3
76. 最小覆盖子串
滑动窗口，收缩左边界
一个小技巧，对于哈希表 key 为 char 类型，value 为 int 类型，可以直接使用数组，int[128]。

通过这三道题对滑动窗口的题有了一定的理解

以后一周更新两次，题目坚持每天刷

2020/8/4：
最近做了链表、回溯
链表
21. 合并两个有序链表
25. K 个一组翻转链表
92.反转链表 II
206.反转链表
链表题 dummy 节点可以节省好多工作
回溯
注意有重复元素时，先排序，在回溯过程中注意树层剪枝即 nums[i] == nums[i-1]&&used[i-1]=false 时跳过，此时代表 i-1 已经被选过了
46/47.全排列
78/90.子集

@Knuth #5 排列问题通过 used 数组标识已使用元素，子集通过 start 参数来过滤已使用元素

工作不顺心，刷题继续

146. LRU 缓存
这题用两个 unordered_map+list 也能实现 O(1)，明天在学习双向链表

@Knuth 补一个快速选择算法
215. 数组中的第 K 个最大元素-看 CLRS9.2 证明

2022/8/7
做点简单的
1. 两数之和 哈希表一次遍历
167. 两数之和 II - 输入有序数组 双指针

2020/8/7
快速排序
关于边界条件 https://www.acwing.com/solution/content/16777/
这篇题解讲的很不错，个人喜欢用 j 做边界，所以 pivot=nums[l],对于用 i 做边界，则需要同 j 的情况取反。对于数据增强的情况下 pivot 取 nums[(l+r)/2]或随机化加快速度
``` cpp
void quick_sort(vector<int>& nums, int l, int r) {
if(l >= r) {
return ;
}
// int pivot = (r + l) / 2;
int pivot = l + rand() % (r - l + 1);
// 注意基准元素应当取出来比较
int x = nums[pivot];
int i = l - 1;
int j = r + 1;
while(i < j) {
// x 不能用 nums[pivot]代替，因为 swap 会破坏 nums[pivot]
while(nums[++i] < x);
while(nums[--j] > x);
if(i < j) {
swap(nums[i], nums[j]);
}
}
quick_sort(nums, l, j);
quick_sort(nums, j+1, r);
}
```
归并排序
堆排序
（改天在学
快速选择算法
思路：直接 k-1 寻找排序后第 k-1 个元素的位置，因为每次只递归一边，所以期望复杂度时 O(n)，具体证明算导(看不懂 x

``` cpp
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return quick_select(nums, 0, nums.size() - 1, k - 1);
}

int quick_select(vector<int>& nums, int l, int r, int k) {
if(l >= r) {
return nums[l];
}
int i = l - 1;
int j = r + 1;
// int pivot = l + rand() % (r - l + 1);
int pivot = (l + r) / 2;
// int pivot = l;
int x = nums[pivot];
while(i < j) {
while(nums[++i] > x);
while(nums[--j] < x);
if(i < j) {
swap(nums[i], nums[j]);
}
}
//
// int sl = j - l + 1;
if(k <= j) {
return quick_select(nums, l, j, k);
}
return quick_select(nums, j + 1, r, k);

}
};
```

15. 三数之和
首先排序
对于 nums[i] > 0,可以直接 break ，后面不会有符合题意的三元组
注意 i 去重，jk 在取到目标三元组也需要去重，
103. 二叉树的锯齿形层序遍历
flag 标记奇 /偶

300. 最长递增子序列
1. dp O(n^2)
2. DP+贪心+二分下界
一个坑，二分算法边界理解又有问题了，https://www.acwing.com/solution/content/107848/

2022/8/9
今天好累，回顾一道题
5. 最长回文子串
法一：dp
法二：中心扩展法 分奇偶

2022/8/10
1143. 最长公共子序列
dp
遗留问题:输出最长公共子序列

236. 二叉树的最近公共祖先
后续遍历
if(root == NULL || root == p || root == q) {
return root;
}
@Knuth @god

今日新词
head count × head cut √

2022/8/20
今日学习单调栈
42.接雨水
496.下一个更大元素 I
503.下一个更大元素 II
739.每日温度

怎么不做了呀

又得重启流浪力扣计划了！