这是一个创建于 845 天前的主题，其中的信息可能已经有所发展或是发生改变。
迫于...遂在此记录苦逼刷题生活
 |
1
god 2022-07-29 21:53:27 +08:00 via iPad  2
Knuth 也要刷题了^-^
—-讲个冷笑话 |
 |
2
Knuth OP Day 1
3. 无重复字符的最长子串：哈希表、滑动窗口 |
|
3
Knuth OP Day2
239. 滑动窗口最大值 优先队列 /单调队列 |
|
4
Knuth OP Day3
76. 最小覆盖子串 滑动窗口，收缩左边界 一个小技巧，对于哈希表 key 为 char 类型，value 为 int 类型，可以直接使用数组，int[128]。 通过这三道题对滑动窗口的题有了一定的理解 以后一周更新两次，题目坚持每天刷 |
|
5
Knuth OP 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.子集 |
|
7
Knuth OP 工作不顺心，刷题继续
146. LRU 缓存 这题用两个 unordered_map+list 也能实现 O(1)，明天在学习双向链表 |
|
9
Knuth OP 2022/8/7
做点简单的 1. 两数之和 哈希表一次遍历 167. 两数之和 II - 输入有序数组 双指针 |
|
10
Knuth OP 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 标记奇 /偶 |
|
11
Knuth OP 300. 最长递增子序列
1. dp O(n^2) 2. DP+贪心+二分下界 一个坑，二分算法边界理解又有问题了，https://www.acwing.com/solution/content/107848/ |
|
12
Knuth OP 2022/8/9
今天好累，回顾一道题 5. 最长回文子串 法一：dp 法二：中心扩展法 分奇偶 |
|
13
Knuth OP 2022/8/10
1143. 最长公共子序列 dp 遗留问题:输出最长公共子序列 |
|
14
Knuth OP |
|
15
Knuth OP 今日新词
head count × head cut √ |
|
16
Knuth OP 2022/8/20
今日学习单调栈 42.接雨水 496.下一个更大元素 I 503.下一个更大元素 II 739.每日温度 |
 |
17
2830446056 2022-10-27 00:59:44 +08:00 via Android
怎么不做了呀
|
|
18
Knuth OP 又得重启流浪力扣计划了！
|
Select Language