2024秋招算法

参考资料

代码随想录 https://programmercarl.com/
LeetCode https://leetcode.cn/
卡码网KamaCoder https://kamacoder.com/
大炮算法 https://blog.csdn.net/qq_44843488/article/details/140665597

刷题感悟

• 可根据输入的规模大概判断解法的时间复杂度

输入数据规模	时间复杂度
10^8	O(n)
10^5	O(nlogn)
10^4	O(n^2)

• 对于输入为数组，并且解题复杂度大于等于O(nlogn)的题目，可考虑先对数组进行排序
• 快慢指针是一种判断链表是否成环的经典方法，但快慢指针的用法不仅于此，我猜想对于大部分判断遍历是否会出现死循环的题，快慢指针都是一种可行的解法。（环形链表，环形链表II，快乐数）
• 对于需要操作链表节点的题目，为链表添加虚拟头节点可一定程度简化操作

一 数组

1.1 二分查找

• 前提
  有序数组，元素唯一（有重复元素，使用二分查找法返回的元素下标可能不是唯一）
• 思想
  • 定义 target 是在一个在左闭右闭的区间里，也就是[left, right]
  • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
  • 若要通过二分查找确定插入位置，则最后需判断nums[mid] > target，若是则mid为结果，若不是则mid + 1为结果
• 代码

  // https://leetcode.cn/problems/binary-search/description/
  class Solution {public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left)/2;if (nums[mid] == target) {return mid;} if (nums[mid] < target) {left = mid + 1;}if (nums[mid] > target) {right = mid - 1;}}return -1;}
  };
  

1.2 移除元素

• 前提
  O(1)空间，不要求保留原顺序
• 思想
  将要删除的元素用数组最后面的元素进行替换
• 代码

  // https://leetcode.cn/problems/remove-element/description/
  class Solution {public:int removeElement(vector<int>& nums, int val) {int left = 0, right = nums.size() - 1;while (left <= right) {if (nums[left] == val) {nums[left] = nums[right];right --;} else {left ++;}}// [0, right]为需要保留的元素，长度位right + 1return right + 1;}
  };
  

1.3 长度最小的子数组

• 前提
  O(1)空间，子数组连续
• 思想
  定义区间[left, right)，当区间和sum < target时移动right，相反则记录当前区间长度right - left并移动left，直到right > 数组总长度时结束循环
• 代码

  // https://leetcode.cn/problems/minimum-size-subarray-sum/description/
  class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0, right = 0; // [left, right)int sum = 0, ans = 0;while (right <= nums.size()) {if (sum < target) {// 此时right指针已达到末尾，且子数组和小于target// 结束循环if (right ==  nums.size()) {break;}sum += nums[right];right ++;} else {int len = right - left;if (ans == 0) {ans = len;} else {ans = ans > len ? len : ans;}sum -= nums[left];left ++;}}return ans;}
  };
  

1.4 螺旋矩阵

• 思想
  关键在于方向的转换，并且需要记录行和列上还有多少是没有遍历过的，每次方向转换都需要减少一个待遍历的行或列
• 代码

  // https://leetcode.cn/problems/spiral-matrix-ii/description/
  class Solution {
  public:vector<vector<int>> generateMatrix(int n) {// direction = 0 => 从左到右，direction = 1 => 从上到下// direction = 2 => 从右到左，direction = 3 => 从下到上int direction = 0;int row_count = n, col_count = n;int i_index = 0, j_index = 0; int num = 1;// 初始化结果vector<vector<int>> res;for (int i = 0; i < n; i ++) {vector<int> r(n);res.push_back(r);}while (num <= n * n) {// printf("direction = %d\n", direction);switch(direction) {case 0:// printf("case0, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < col_count; i ++) {res[i_index][j_index] = num;j_index ++;num ++;}i_index ++;j_index --;row_count --;break;case 1:// printf("case1, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < row_count; i ++) {res[i_index][j_index] = num;i_index ++;num ++;}i_index --;j_index --;col_count --;break;case 2:// printf("case2, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < col_count; i ++) {res[i_index][j_index] = num;j_index --;num ++;}j_index ++;i_index --;row_count --;break;case 3:// printf("case3, i = %d, j = %d\n", i_index, j_index);for (int i = 0; i < row_count; i ++) {res[i_index][j_index] = num;i_index --;num ++;}i_index ++;j_index ++;col_count --;break;}direction ++;direction = direction % 4;// for (int i = 0; i < n; i ++) {//     for (int j = 0; j < n; j ++) {//         cout << res[i][j];//     }//     cout << endl;// }}return res;}
  };
  

1.5 在排序数组中查找元素的第一个和最后一个位置

• 代码

  // https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
  class Solution {
  public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> ret(2, -1);// 有效区间[left, right]int left = 0, right = nums.size() - 1, mid;bool tag = false;while (left <= right) {mid = left + (right - left)/2;if (nums[mid] == target) {tag = true;break;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}if (!tag) return ret;// cout << left << " " <<  mid << " " << right  << endl;// [left, mid - 1] 中寻找小于target的元素int l = left, r = mid - 1, from = left;while (l <= r) {int m = l + (r - l)/2;if (nums[m] < target) {from = m;break;} else {r = m - 1;}}// 向右找到第一个等于target的元素while (nums[from] != target) from ++;// [mid + 1, right] 中寻找大于target的元素l = mid + 1;r = right;int to = right;while (l <= r) {int m = l + (r - l)/2;if (nums[m] > target) {to = m;break;} else {l = m + 1;}}// 向左找到第一个等于target的元素while (nums[to] != target) to --;ret[0] = from;ret[1] = to;return ret;}
  };
  

二 链表

2.1 移除链表元素

• 思想
  移除链表中指定元素的关键在于找到被移除元素的上一个节点
• 代码

  // https://leetcode.cn/problems/remove-element/description/
  class Solution {
  public:ListNode* removeElements(ListNode* head, int val) {// 定义虚拟头节点，不需要对第一个节点进行特殊判断ListNode *dummy_head = new ListNode(-1, head);// 定义pre和cur，方便删除元素ListNode *pre = dummy_head;ListNode *cur = dummy_head->next;while (cur != NULL) {if (cur->val == val) {pre->next = cur->next;cur = pre->next;} else {pre = pre->next;cur = cur->next;}}return dummy_head->next;}
  };
  

2.2 设计链表

• 思想
  • 设计虚拟头节点可以简化对于第一个节点的操作
  • 由题可知，大部分操作都需要找到下标的为index的节点的上一个节点，因此设计了getPre(int index)函数
  • 设计尾节点可以降低addAtTail的时间复杂度，但是在链表变化时需要对其进行维护
• 代码

  // https://leetcode.cn/problems/design-linked-list/
  class MyListNode {    
  public:int val;MyListNode *next;MyListNode(int val, MyListNode *next) {this->val = val;this->next = next;}
  };class MyLinkedList {
  private:MyListNode *dummy_head;MyListNode *tail;int size;// 找到下标为index的上一个节点MyListNode *getPre(int index) {MyListNode *node = dummy_head;while (index > 0) {node = node->next;index --;}return node;}
  public:MyLinkedList() {dummy_head = new MyListNode(-1, NULL);tail = NULL;size = 0;}int get(int index) {if (index >= size) {return -1;}MyListNode *node = getPre(index);return node->next->val;}void addAtHead(int val) {MyListNode *node = new MyListNode(val, NULL);node->next = dummy_head->next;dummy_head->next = node;if (tail == NULL) {tail = node;}size ++;}void addAtTail(int val) {if (tail == NULL) {addAtHead(val);   } else {tail->next = new MyListNode(val, NULL);tail = tail->next;size ++;}}void addAtIndex(int index, int val) {// 如果 index 比长度更大，该节点将 不会插入 到链表中if (index > size) {return ;}// 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾if (index == size) {addAtTail(val);} else {MyListNode *node = new MyListNode(val, NULL);MyListNode *p = getPre(index);node->next = p->next;p->next = node;size ++;}}void deleteAtIndex(int index) {if (index >= size) {return ;}MyListNode *p = getPre(index);// 要删除的节点为尾节点，需要修改tailif (p->next == tail) {p->next = NULL;tail = p;} else {p->next = p->next->next;                }size --;}
  };
  

2.3 反转链表

• 思想
  • 为原链表添加虚拟头节点，删除节点时不需要维护头节点，简化操作（新链表的虚拟头节点同理）
  • 反转链表主要分为节点断开和节点接入，分为两部分实现，可避免思路不清晰，导致链表成环（q->next = NULL可删除）
• 代码

  // https://leetcode.cn/problems/reverse-linked-list/
  class Solution {
  public:ListNode* reverseList(ListNode* head) {// 为原链表添加虚拟头节点，方便节点的删除ListNode *dummy_head = new ListNode(-1, head);ListNode *p = dummy_head;// 为新链表添加虚拟头节点ListNode *new_head = new ListNode(-1);while (p->next != NULL) {// 把节点从原链表断开ListNode *q = p->next;p->next = q->next;q->next = NULL;// 把节点接入到新链表的头部q->next = new_head->next;new_head->next = q;}return new_head->next;}
  };
  

2.4 两两交换链表中的节点

• 思想
  • 多定义变量可一定程度上简化操作（变量不用🪙）
• 代码

  // https://leetcode.cn/problems/swap-nodes-in-pairs/description/
  class Solution {
  public:ListNode* swapPairs(ListNode* head) {ListNode *dummy_head = new ListNode(-1, head);ListNode *p = dummy_head;while (p->next != NULL && p->next->next != NULL) {// a和b为要进行交换的节点，c为后面的节点ListNode *a = p->next;ListNode *b = a->next;ListNode *c = b->next;// 将a和b从原链表中断开（为了方便理解，可省略）p->next = NULL;a->next = NULL;b->next = NULL;// 重新拼接p->next = b;b->next = a;a->next = c;p = a;}   return dummy_head->next;}
  };
  

2.5 删除链表的倒数第N个节点

• 思想
  先让fast跑n步，然后slow和fast再一起跑，fast到达末尾时，slow刚好为倒数第n+1个节点
• 代码

  // https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
  class Solution {
  public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *dummy_head = new ListNode(-1, head);ListNode *fast = dummy_head;ListNode *slow = dummy_head;while (n > 0) {fast = fast->next;n --;}while (fast->next != NULL) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummy_head->next;   }
  };
  

2.6 链表相交

• 代码

  // https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
  class Solution {
  public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 计算链表A和B的节点数int a_count = 0;int b_count = 0;ListNode *p = headA;while (p != NULL) {a_count ++;p = p->next;}p = headB;while (p != NULL) {b_count ++;p = p->next;}// 若两个链表相差sub个节点，则让长的链表先跑sub步while (a_count > b_count) {headA  = headA->next;a_count --;}while (b_count > a_count) {headB = headB->next;b_count --;}// 两个链表同时往前，此时遇到的第一个相同节点即为结果while (headA != headB) {headA = headA->next;headB = headB->next;}return headA;}
  };
  

2.7 环形链表II

• 思想
  • 通过快慢指针法确定链表是否存在环，并找到环中的任意一个节点
  • 遍历环，直至将环中的所有节点添加到set集合中
  • 从head开始遍历，当节点存在与set集合中时，即为环的入口节点
• 代码

  // https://leetcode.cn/problems/linked-list-cycle-ii/
  class Solution {
  public:ListNode *detectCycle(ListNode *head) {// 通过快慢指针法确定链表是否存在环，并找到环中的任意一个节点ListNode *fast = head;ListNode *slow = head;bool tag = false;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) {tag = true;break;}}if (tag) {// 此时fast和slow都是环中的节点，遍历环，直至将环中的所有节点添加到`set`集合中set<ListNode*> st;while (st.find(fast) == st.end()) {st.insert(fast);fast = fast->next;}// 从`head`开始遍历，当节点存在与`set`集合中时，即为环的入口节点while (st.find(head) == st.end()) {head = head->next;}return head;} else {return NULL;}}
  };
  

• 最优解法

  // https://leetcode.cn/problems/linked-list-cycle-ii/solutions/12616/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
  class Solution {
  public:ListNode *detectCycle(ListNode *head) {ListNode *fast = head;ListNode *slow = head;bool tag = false;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) {tag = true;break;}}if (!tag) return NULL;fast = head;while (fast != slow) {fast = fast->next;slow = slow->next;}return fast;}
  };
  

三 哈希表

3.1 有效的字母异位词

• 思想
  • 两个字符串长度不同，直接返回false
  • 遍历字符串s，使用map统计第一个字符串s中每各字符出现的次数
  • 遍历字符串t，若字符不存在于map中，则返回false；存在则进行减操作，当字符次数减为0时，从map移除
  • map为空则表示两个字符串是字母异位词
  • （进阶）由于题目中说明字符串都由小写字母组成，那么我们可以将所有字符映射到长度为26的数组，简化操作
• 代码（基础解法）

  // https://leetcode.cn/problems/valid-anagram/description/
  class Solution {
  public:bool isAnagram(string s, string t) {if (s.length() != t.length()) {return false;}map<char, int> mp;for (int i = 0; i < s.length(); i ++) {char key = s[i];auto it = mp.find(key);if (it != mp.end()) {it->second += 1;} else {mp.insert(pair<char, int>(key, 1));}}for (int i = 0; i < t.length(); i ++) {char key = t[i];auto it = mp.find(key);if (it == mp.end()) {return false;} else {if (it->second == 0) {return false;} else if (it->second == 1) {mp.erase(it);} else {it->second -= 1;}}}return mp.empty();}
  };
  

• 最优解法

  // https://leetcode.cn/problems/valid-anagram/description/
  class Solution {
  public:bool isAnagram(string s, string t) {if (s.length() != t.length()) {return false;}vector<int> mp(26, 0);for (char c : s) {mp[c - 'a'] ++;}for (char c : t) {mp[c - 'a'] --;}for (int c : mp) {if (c != 0) return false;}return true;}
  };
  

3.2 两个数组的交集

• 代码

  // https://leetcode.cn/problems/intersection-of-two-arrays/
  class Solution {
  public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;set<int> st;// 将nums1的所有元素添加到set中，会自动去重for (int num : nums1) {st.insert(num);}// 遍历nums2，判断元素是否存在st中，存在则是两个数组的交集，添加到结果数组ret中// 为防止元素重复添加，需要将其从st中移除for (int num : nums2) {if (st.find(num) != st.end()) {ret.push_back(num);st.erase(num);}}return ret;}
  };
  

3.3 两数之和

• 思想
  遍历数组nums，对于每个元素nums[i]，判断是否存在遍历过的元素nums[j]，使得nums[i] + nums[j] = target，若存在，则返回结果；若不存在，则将其添加到map中，使得每次获取y的时间代价为O(1)，整个算法时间复杂度为O(n)。
• 哈希表解法

  // https://leetcode.cn/problems/two-sum/
  class Solution {
  public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ret(2, -1);unordered_map<int, int> mp;for (int i = 0; i < nums.size(); i ++) {// 求出另一个元素的值int key = target - nums[i];// 查询前面是否存在nums[j] 使得nums[i] + nums[j] = targetauto it = mp.find(key);if (it != mp.end()) {ret[0] = it->second;ret[1] = i;break;} else {// 使用map，可使获取nums[j]的时间复杂度降为O(1)mp.insert(pair<int, int>(nums[i], i));   }}return ret;}
  };
  

3.4 三数之和

• 思想
  在两数之和的基础上再套一层循环，并加上一些条件，避免添加重复的三元组
• 注
  这种解法的时间复杂度是O(n^2)，与官方解法的时间复杂度一样，但是在提交时，最后几个测试用例会超时
• 哈希表解法（LeetCode最后几个测试用例会超时）

  // https://leetcode.cn/problems/3sum/
  class Solution {
  public:string getHash(int a, int b) {return to_string(a) + to_string(b);}vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;// 用于存储第二层遍历，前面遍历过的元素unordered_set<int> st;unordered_set<string> cache;// 先进行排序，可提前跳出不满足条件的循环sort(nums.begin(), nums.end());// 第一层遍历，确定三元组的第一个元素（由于数组有序，这个元素是三元组中最大的）// 从第三个元素开始遍历，是因为另外两个元素要往前找for (int i = 2; i < nums.size(); i ++) {// 在确认第一个元素nums[i]的情况下// nums[i] + nums[i - 1] + nums[i - 2]是最大的三元组，若其小于0，则其他三元组也不满足条件if (nums[i] + nums[i - 1] + nums[i - 2] < 0) {continue ;}// 计算三元组中另外两个元素的和int target = -nums[i];// 这一部分的主要思想跟"两数之和"类似for (int j = 0; j < i; j ++) {// 避免添加重复的三元组（在确定其中两个元素时，满足条件的三元组唯一）string hash_key = getHash(nums[i], nums[j]); if (cache.find(hash_key) != cache.end()) {st.insert(nums[j]);continue;} int key = target - nums[j];auto it = st.find(key);if (it != st.end()) {  vector<int> vec;vec.push_back(*it);vec.push_back(nums[j]);vec.push_back(nums[i]);ret.push_back(vec);cache.insert(hash_key);} else {st.insert(nums[j]);}}st.clear();}return ret;}
  };
  

• 双指针解法（可通过LeetCode所有测试用例）

  class Solution {
  public:// 参考解法https://leetcode.cn/problems/3sum/solutions/11525/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;sort(nums.begin(), nums.end());for (int i = 0; i < nums.size() - 2; i ++) {if (i > 0 && nums[i] == nums[i - 1]) {continue ;}int left = i + 1, right = nums.size() - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {vector<int> v = {nums[i], nums[left], nums[right]};ret.push_back(v);while(left < right && nums[left] == nums[++left]);while(left < right && nums[right] == nums[--right]); }if (sum > 0) right --;if (sum < 0) left ++;}}return ret;}
  };
  

3.5 四数之和

• 思想
  在三数之和的基础上再套一层循环
• 哈希表解法(超时)

  // https://leetcode.cn/problems/4sum/
  class Solution {
  public:string get_hash(int a, int b, int c) {return to_string(a) + "_" + to_string(b) + "_" + to_string(c);}vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;unordered_set<string> cache;sort(nums.begin(), nums.end());for (int i = 3; i < nums.size(); i ++) {for (int j = i - 1; j > 1; j --) {     unordered_set<int> st;for (int k = 0; k < j; k ++) {string hash_key = get_hash(nums[i], nums[j], nums[k]);if (cache.find(hash_key) != cache.end()) {continue ;}int key = target - nums[i] - nums[j] - nums[k];auto it = st.find(key);if (it != st.end()) {vector<int> v = {nums[i], nums[j], nums[k], key};ret.push_back(v);cache.insert(hash_key);} else {st.insert(nums[k]);}}}}return ret;}
  };
  

• 双指针解法

  class Solution {
  public:string get_hash(int a, int b, int c) {return to_string(a) + "_" + to_string(b) + "_" + to_string(c);}vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;unordered_set<string> cache;sort(nums.begin(), nums.end());for (int i = 3; i < nums.size(); i ++) {for (int j = i - 1; j > 1; j --) {   long new_target = (long)target - nums[i] - nums[j];int left = 0, right = j - 1;while (left < right) {if (nums[left] + nums[right] == new_target) {// 避免添加重复的三元组string hash_key = get_hash(nums[i], nums[j], nums[right]);if (cache.find(hash_key) == cache.end()) {cache.insert(hash_key);vector<int> v = {nums[i], nums[j], nums[right], nums[left]};ret.push_back(v);}while (left < right && nums[left] == nums[++left]);while (left < right && nums[right] == nums[--right]);} else if (nums[left] + nums[right] < new_target) {while (left < right && nums[left] == nums[++left]);} else if (nums[left] + nums[right] > new_target) {while (left < right && nums[right] == nums[--right]);}}}}return ret;}
  };
  

3.6 四数相加II

• 思想

  • [暴力解法(超时)] 比较暴力的解法是先使用map统计nums4每个元素出现的次数，然后三层循环分别遍历nums1，nums2，nums3，计算三数之和的相反数target = -nums1[i] - nums2[j] - nums3[k]，最后从map查找target，将其在nums4中出现的次数累加到结果变量ans。然而，这种解法存在三层循环，其时间复杂度是O(n^3)，会发生超时。
  • [优化解法] 在暴力解法的基础上进行改进，最开始使用map统计nums3和nums4加和结果及其出现次数，然后两个循环分别遍历nums和nums2，计算两数之和的相反数target = -nums1[i] - nums2[j]，最后从map查找target，将其出现的次数累加到结果变量ans。这种解法可以将时间复杂度降低到O(n^2)。

• 暴力解法(超时)

  // https://leetcode.cn/problems/4sum-ii/
  class Solution {
  public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {int ans = 0;int n = nums1.size();unordered_map<int, int> mp;for (int i = 0; i < n; i ++) {auto it = mp.find(nums4[i]);if (it != mp.end()) {it->second ++;} else {mp.insert(pair<int, int>(nums4[i], 1));}} for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++ ) {for (int k = 0; k < n; k ++) {int target = -nums1[i] - nums2[j] - nums3[k];auto it = mp.find(target);if (it != mp.end()) {ans += it->second;}}}}return ans;}
  };
  

• 优化解法

  // https://leetcode.cn/problems/4sum-ii/
  class Solution {
  public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {int ans = 0;int n = nums1.size();// 统计nums3和nums4各取一个元素，进行加和的结果，并记录每个结果出现的次数unordered_map<int, int> mp;for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++ ) {int sum = nums3[i] + nums4[j];auto it = mp.find(sum);if (it != mp.end()) {it->second ++;} else {mp.insert(pair<int, int>(sum, 1));}}}// 两层遍历nums1和nums2，计算加和，从map中查询是否存在其相反数，存在则将其相反数出现的次数累加到结果变量for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++ ) {int target = -nums1[i] - nums2[j];auto it = mp.find(target);if (it != mp.end()) {ans += it->second;}}}return ans;}
  };
  

3.7 快乐数

• 哈希表解法

  // https://leetcode.cn/problems/happy-number/
  class Solution {
  public:bool isHappy(int n) {// 用set记录n是否出现过unordered_set<int> cache;return happy(n, cache);}bool happy(int n, unordered_set<int> &cache) {// 当n变为1时结束递归返回trueif (n == 1) {return true;}// 当n出现过时，说明n不可能变为1，返回falseif (cache.find(n) != cache.end()) {return false;}cache.insert(n);int sum = 0;while (n > 0) {int num = n % 10;sum += num * num;n /= 10;}return happy(sum, cache);}
  };
  

• 快慢指针解法
  • 思想
    fast每次走两步，slow每次走一步，要么fast = 1返回true，要么fast和slow相等，出现死循环，返回false

  // https://leetcode.cn/problems/happy-number/
  class Solution {
  public:bool isHappy(int n) {int slow = n;int fast = n;do {fast = happy(fast);fast = happy(fast);if (fast == 1) return true;slow = happy(slow);} while (slow != fast);return false;}int happy(int n) {int sum = 0;while (n > 0) {int num = n % 10;sum += num * num;n /= 10;}return sum;}
  };
  

四 位运算

4.1 只出现一次的数字

• 思想
  • [基础解法] 题目中说明，只有一个数字出现一次，其他都出现两次，并且输入的数据类型位int型，在大部分语言中的为4字节32位，先统计每个位上出现1的次数，若某个位置1出现次数不可被2整除，那么说明目标数字在该位的值为1，否则为0
  • [异或运算解法] 根据位运算的两个性质，两个相同的数异或的结果为0，任何数与0异或的结果为自身，题目中说明，只有一个数字出现一次，其他都出现两次，那么遍历数组进行异或运算，得到的结果即为只出现一次的数字
• 基础解法

  class Solution {
  public:// https://leetcode.cn/problems/single-number/int singleNumber(vector<int>& nums) {vector<int> bits(32, 0);int ans = 0;for (int num : nums) {for (int i = 0; i < 32; i ++) {bits[i] += (num >> i) & 1;}}for (int i = 0; i < 32; i ++) {if (bits[i] % 2 != 0) {ans |= (1 << i);}}return ans;}
  };
  

• 异或运算解法

  // https://leetcode.cn/problems/single-number/
  class Solution {
  public:int singleNumber(vector<int>& nums) {int ans = 0;for (int num : nums) {ans ^= num;}return ans;}
  };
  

4.2 只出现一次的数字II

• 思想
  • 题目中说明，只有一个数字出现一次，其他都出现三次，并且输入的数据类型位int型，在大部分语言中的为4字节32位，先统计每个位上出现1的次数，若某个位置1出现次数不可被3整除，那么说明目标数字在该位的值为1，否则为0
  • 这道题的解法其实与只出现一次的数字的基础解法思想相同，这种思想可以扩展到只有一个数字出现n次，其他都出现m次（n%m != 0）
• 代码

  // https://leetcode.cn/problems/single-number-ii/
  class Solution {
  public:int singleNumber(vector<int>& nums) {vector<int> bits(32, 0);for (int num : nums) {for (int i = 0; i < 32; i ++) {bits[i] += (num >> i) & 1;}}int ans = 0;for (int i = 0; i < 32; i ++) {if (bits[i] % 3 != 0) {ans |= (1 << i);}}return ans;}
  };
  

4.3 只出现一次的数字III

• 思想
  有两个数字出现一次，其余都出现两个，遍历数组进行异或运算的结果，即为两个出现一次的数字的异或结果，我们从二进制的角度看，若第i位的值为1，则说明这两个数在第i位的二进制表示不同，那么我们可以根据第i位的值，将数组分为两组，问题就转换为两个“有一个数字出现一次，其余都出现两个”的问题
• 代码

  class Solution {
  public:vector<int> singleNumber(vector<int>& nums) {int ans = 0;for (int num : nums) {ans ^= num;}// 找到最低位的1int i = 0;while (((ans >> i) & 1) == 0) i++;// 根据第i位是否位1将数组分为两组// 分别求“有一个数字出现一次，其余都出现两个”int ans1 = 0, ans2 = 0;for (int num : nums) {if (((num >> i) & 1) == 1) {ans1 ^= num;} else {ans2 ^= num;}}vector<int> ret = {ans1, ans2};return ret;}
  };
  

五 字符串

5.1 反转字符串

• 思想
  双指针法，定义头指针和尾指针，当两者不相等时，交换其所指字符后两个指针向内侧移动，直至指针相遇，结束循环
• 代码

  // https://leetcode.cn/problems/reverse-string
  class Solution {
  public:void reverseString(vector<char>& s) {int left = 0, right = s.size() - 1;while (left < right) {char c = s[left];s[left] = s[right];s[right] = c;left ++;right --;}}
  };
  

5.2 反转字符串II

• 思想
  题意是每2k个字符，将前k个字符进行反转。那么我们以每2k个字符为一次循环，也就是for (int i = 0; i < s.size(); i += 2*k)，然后在循环内进行前k个字符的反转，当然，这里需要考虑到最后一部分字符串小于k的情况，因此，定义反转字符的尾指针应该保证小于字符串的总长度
• 代码

  // https://leetcode.cn/problems/reverse-string-ii
  class Solution {
  public:string reverseStr(string s, int k) {// 0 -> (k-1)// 2k -> 3k - 1// 4k -> 5k - 1for (int i = 0; i < s.size(); i += 2*k) {int left = i;int right = i + k - 1;// 尾指针应该保证小于字符串的总长度if (right > s.size() - 1) {right = s.size() - 1;}while (left < right) {char c = s[left];s[left] = s[right];s[right] = c;left ++;right --;}}return s;}
  };
  

5.3 替换数字

• 思想
  定义结果字符串ans，遍历输入字符串s，每个遍历的字符定义为char c，当c >= '0' && c <= '9'，将字符串"number"拼接到ans，否则，将字符c拼接到ans
• 代码

// https://kamacoder.com/problempage.php?pid=1064
#include<iostream>
using namespace std;int main() {string s;cin >> s;string ans;for (char c : s) {if (c >= '0' && c <= '9') {ans += "number";} else {ans.append(1, c);}}cout << ans << endl;return 0;
}