阅读量:0
文章目录
参考资料
代码随想录 https://programmercarl.com/
LeetCode https://leetcode.cn/
大炮算法 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 + 1 return 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); // 要删除的节点为尾节点，需要修改tail if (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] = target auto 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时结束递归返回true if (n == 1) { return true; } // 当n出现过时，说明n不可能变为1，返回false if (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; } // 找到最低位的1 int 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; } };
