打卡记录

344. 反转字符串 链接：344. 反转字符串 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 双指针法 看完题解后的想法 —— 实现中遇到的困难 —— 代码 class Solution { public: void reverseString(vector<char>& s) { int n = s.size(); int left = 0, right = n - 1; while (left < right) { char tmp = s[left]; s[left] = s[right]; s[right] = tmp; left++; right--; } } }; 541. 反转字符串II 链接：541. 反转字符串II 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 反转字符串写成可传位置的函数，然后一段段翻转，最后处理尾巴； 看完题解后的想法 用 for 循环每次跳 2k 更简洁； 实现中遇到的困难 —— 代码 class Solution { public: string reverseStr(string s, int k) { int n = s.size(); int time = n / (2* k); int tail = n % (2* k); int index = 0; while (time > 0) { swapStr(s, index, index+k-1); index = index + 2 * k ; time--; } if (tail > 0 && tail < k) { swapStr(s, index, index+tail-1); } else { swapStr(s, index, index+k-1); } return s; } void swapStr(string& s, int l, int r) { int left = l, right = r; while (left < right) { char tmp = s[left]; s[left] = s[right]; s[right] = tmp; left++; right--; } } }; KamaCoder 54. 替换数字 链接：KamaCoder 54. 替换数字 文章：代码随想录 视频：无 状态：⚠️ 第一想法 刚开始在纠结如何原地扩展； ...

454. 四数相加II 链接：力扣454 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 two sum的变形，把数组两两分组之后变成two sum； 看完题解后的想法 —— 实现中遇到的困难 这里最开始看到分组都要两层循环，时间复杂度达到 $O(n^2)$ ，就觉得在查询逻辑里可以不用哈希直接遍历，因为也是两层循环； 但是这个是要考虑数组大小的，原来的数组大小是 $n$ ，分组求和之后就是 $n^2$ ，如果再两层遍历循环这个 $n^2$ 的数组复杂度就是 $O(n^4)$ ； 代码 class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> hash; int cnt = 0; for (int i = 0; i < nums1.size(); i++) { for (int j = 0; j < nums2.size(); j++) { hash[nums1[i] + nums2[j]]++; } } for (int i = 0; i < nums3.size(); i++) { for (int j = 0; j < nums4.size(); j++) { int sum = nums3[i] + nums4[j]; if (hash.count(-sum) != 0) { cnt += hash[-sum]; } } } return cnt; } }; 383. 赎金信 链接：力扣383 文章：代码随想录 状态：✅ 第一想法 类似于异构词，但是只用部分一致； ...

242. 有效的字母异位词 链接：力扣242 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 这道题要判断两个字符串包含的字符是否完全一致，第一想法就是哈希表； 仔细思考就会发现因为只有26个字符，所以不需要使用完整的哈希表，只需要使用一个定长数组模拟哈希就行了； 看完题解后的想法 —— 实现中遇到的困难 最开始的时候将 s 的写入和判断的 t 的减少分开在了两个循环中，其实一次循环就能做； 代码 class Solution { public: bool isAnagram(string s, string t) { if (s.size() != t.size()) { return false; } int cnt[26] = {}; for (int i = 0; i < s.size(); i++) { cnt[s[i] - 'a']++; cnt[t[i] - 'a']--; } for (int c : cnt) { if (c != 0) { return false; } } return true; } }; 349. 两个数组的交集 链接：力扣349 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 使用集合去重+记录出现元素,之后再用集合去重; ...

24. 两两交换链表中的节点 链接：力扣24 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 两两交换，头节点也要进入交换，要把这种特殊情况转变为一般情况，所以需要引入dummyHead； 让之后的交换都是某个节点的next和next->next；变成了一般性问题； 还有就是三指针的交换顺序，这里采用标记了最后需要指向的节点降低心智负担； 看完题解后的想法 —— 实现中遇到的困难 dummy.next忘记指向head了； 代码 class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next = head; ListNode* cur = &dummy; while (cur->next != nullptr && cur->next->next != nullptr) { ListNode* finalFoward = cur->next->next->next; ListNode* firstMove = cur->next->next; ListNode* secondMove = cur->next; cur->next = firstMove; firstMove->next = secondMove; secondMove->next = finalFoward; cur = cur->next->next; } return dummy.next; } }; 19. 删除链表的倒数第N个节点 链接：力扣19 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 第一想法是反转链表，然后从头找过去，然后删除节点再返回来； ...

203. 移除链表元素 链接：力扣203 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 因为要删除节点，可能头节点本身也是要删除的，因此引入dummy_head，这样之后的所有节点都是next节点也不用区分是不是头节点； 看完题解后的想法 实现中遇到的困难 实现的时候忽略了next的next仍然可能是要删除的值； 代码 class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode dummy(INT_MAX); dummy.next = head; ListNode* cur = &dummy; while (cur->next != nullptr) { if (cur->next->val == val) { cur->next = cur->next->next; // 只是删掉了后继的第一个节点，可能有连续需要删除的 } else { cur = cur->next; // 只有cur->next不是目标才能走 } } return dummy.next; } }; 707. 设计链表 链接：力扣707 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 考察的是类的基本书写，需要注意各种代码规范； 因为有频繁的插入和删除，所以需要维护一个dummyHead来保证不用单独处理Head的情况； ...

209. 长度最小的子数组 链接：力扣209 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 看到这道题的第一想法是做一个前缀和，但是引入前缀和之后需要去减去之后恰好小于target的另一个前缀和，遍历的话复杂度就会变成 $O(n^2)$ ，然后想到了可以二分查找； 但是仔细思考一下就会发现，可以维护一个队列，不断把数据push进去，一旦找到大于target的就开始把前面的数据踢出去，直到再次小于target；这样就不需要复杂的查找了； 看完题解后的想法 队列在这里其实就是一个双指针维护的滑动窗口； 实现中遇到的困难 result需要判断当前窗口大小和历史result谁更小，使用双指针滑动窗口不会有问题，但是如果是用队列来维护滑动窗口，需要使用queue.size(),返回的类型是size_t，需要强制转换成int； 一开始还给result直接赋值0，但是这样在min里会锁死最小值； 代码 class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int sum = 0; int result = INT_MAX; int left = 0; for (int right = 0; right < nums.size(); right++) { sum += nums[right]; while (sum >= target) { result = min(result, right-left+1); sum = sum - nums[left]; left++; } } return result == INT_MAX ? 0 : result;; } }; 59. 螺旋矩阵II 链接：力扣59 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 看完题目的第一想法就是如何移动坐标去填充数据，然后就被边界条件卡住了； ...

704. 二分查找 链接：力扣704 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 二分查找母题； 有闭区间和开区间两种解法： 闭区间：right 初始化为 nums.size()-1 ,是实右边界；在进入 while 循环时就要注意需要判断 left == right；同时每次移动边界都要从已经找到的地方往右或往左移动一步； 开区间：right 初始化为 nums.size() ,是虚右边界；在进入 while 循环时就要注意写 left < right；移动时左边界是 mid+1， 而右边界是 mid； 看完题解后的想法 —— 实现中遇到的困难 采用实变界进入循环的判断忘记了需要判断left == right； 代码 class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size()-1; while (left <= right) { int mid = left + (right-left)/2; if (nums[mid] == target) { return mid; } else if (nums[mid] > target) { right = mid-1; } else { left = mid+1; } } return -1; } }; 27. 移除元素 链接：力扣27 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 第一想法就是维护两个指针，left 找到 val 位置，而 right 从右边找不为val的值，当左右相遇说明找完了； ...