LeetCode-Hot100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : vector<int > twoSum (vector<int >& nums, int target) { unordered_map<int , int > res; for (int i = 0 ; i < nums.size (); i ++ ) { auto it = res.find (target - nums[i]); if (it != res.end ()) { return {it -> second, i}; } res[nums[i]] = i; } return {}; } };
主要还是对哈希表不熟悉，可参考c++中unordered_map的用法的详述（包含unordered_map和map的区别）_unorder map-CSDN博客
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : void moveZeroes (vector<int >& nums) for (int i = 0 , j = 0 ; i < nums.size ();) { if (nums[i] != 0 ) { swap (nums[i], nums[j]); j ++ ; } i ++ ; } } };
一开始以为是在头尾各设置两个指针，结果发现数组内的非零元素顺序变了。应该是开头设置两个指针，然后让其分别指向零和非零元素，这样的双指针算法是可行的。或者可以让非零元素不断向左覆盖，再在最后补零。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : vector<vector<string>> groupAnagrams (vector<string>& strs) { unordered_map<string, vector<string>> res1; for (int i = 0 ; i < strs.size (); i ++ ) { string str_s = strs[i]; sort (strs[i].begin (), strs[i].end ()); res1[strs[i]].push_back (str_s); } vector<vector<string>> res2; for (auto it = res1. begin (); it != res1. end (); it ++ ) { res2. push_back (it -> second); } return res2; } };
一开始想的是用unordered_set()，后来发现有ab、aab这样的情况就会出错；经观察可以发现，异位词排序后的词刚好可以作为哈希表的键，所以用哈希表做了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : int longestConsecutive (vector<int >& nums) unordered_set<int > num_set; for (int &n : nums) { num_set.insert (n); } int length = 0 ; for (const int & n : num_set) { int cur = 0 ; int num = n; if (num_set.count (num - 1 ) == 0 ) { while (num_set.count (num)) { cur ++ ; num = num + 1 ; } length = max (length, cur); } } return length; } };
这题的题目没太搞懂，官方题解是直接去重的，也就是说不考虑重复元素，比如1 2 3 3 3 4 5就应该返回5，而不是7；另外这题的居然用排序比哈希表还快；哈希的核心就是可以用O(1)的时间复杂度来查找哈希集合中的元素，然后根据本题的逻辑进一步优化——即每次只让集合中没有x - 1的x进入循环
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public: vector<vector<int >> threeSum(vector<int >& nums) { sort(nums.begin(), nums.end()); vector<vector<int >> res; for (int i = 0 ; i < nums.size(); i ++ ) { if (i == 0 || nums[i] != nums[i - 1 ]) { int target = -nums[i]; int l = i + 1 , r = nums.size() - 1 ; while (l < r) { int sum = nums[l] + nums[r]; if (sum == target) { res.push_back({nums[i], nums[l], nums[r]}); l ++; r -- ; while (l < r && nums[l] == nums[l - 1 ]) l ++; while (l < r && nums[r] == nums[r + 1 ]) r --; } else if (sum < target) { l ++; } else { r --; } } } } return res; } };
一眼能看出来的方法就是三重循环再加个哈希表去重，但这样的时间和空间复杂度都很高；然后题目提示的方法是排序 + 双指针，双指针算法有快慢指针、对撞指针这两种。根据本题的性质，比较适合对撞指针。经过排序后再进行三重循环，可以避免重复；然后在每重循环中，相邻的两个元素不能相同，可以避免重复。然后发现，二三重循环其实是可以并列的。
当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从O(N^2)减少至O(N)。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int maxArea (vector<int >& height) int vol = 0 ; for (int i = 0 , j = height.size () - 1 ; i < j;) { int v = (j -i) * min (height[i], height[j]); vol = max (vol, v); if (height[i] <= height[j]) i ++ ; else j -- ; } return vol; } };
暴力的做法就是双重for循环，然后依次求面积。然后这题明显的可以看出来用两个快慢指针，分别从头尾开始移动；最大的难点在于什么时候该移动哪个指针。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : bool searchMatrix (vector<vector<int >>& matrix, int target) if (matrix.empty () || matrix[0 ].empty ()) { return false ; } int m = matrix.size (); int n = matrix[0 ].size (); int i = 0 ; int j = n - 1 ; while (i < m && j >= 0 ) { if (target == matrix[i][j]) return true ; else if (target < matrix[i][j]) j --; else i ++ ; } return false ; } };
暴力解法直接遍历；
对每一行进行二分查找；
Z字形查找，从右上角开始遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution {public : ListNode* reverseList (ListNode* head) { ListNode *curr = new ListNode (); ListNode *prev = new ListNode (); ListNode *tmp = new ListNode (); if (head != nullptr ) { curr = head -> next; prev = head; prev -> next = nullptr ; } else { return nullptr ; } while (curr != nullptr ) { tmp = curr -> next; curr -> next = prev; prev = curr; curr = tmp; } return prev; } };
利用两个指针从前往后依次逆置相邻的两个结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution {public : bool isPalindrome (ListNode* head) stack<int > s; ListNode *p = new ListNode (); p = head; while (p != nullptr ) { s.push (p -> val); p = p -> next; } p = head; while (p != nullptr ) { if (p -> val != s.top ()) { return false ; } s.pop (); p = p -> next; } return true ; } };
利用栈结构，先将元素入栈，再依次出栈并且判断链表中的节点元素是否相等；
快慢指针？（ 可以将空间复杂度降到O(1) ）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : bool hasCycle (ListNode *head) unordered_set<ListNode*> res; while (head != nullptr ) { if (res.count (head)) { return true ; } res.insert (head); head = head -> next; } return false ; } };
哈希表；
快慢指针，慢指针每次移动一个节点，快指针每次移动两个结点；若存在环，则快慢指针一定会相遇；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution {public : ListNode *getIntersectionNode (ListNode *headA, ListNode *headB) { if (headA == nullptr || headB == nullptr ) { return nullptr ; } ListNode *pA = headA; ListNode *pB= headB; while (pA != pB) { if (pA == nullptr ) { pA = headB; } else { pA = pA -> next; } if (pB == nullptr ) { pB = headA; } else { pB = pB -> next; } } return pA; } };
先利用哈希集合存储A中的每个节点，然后遍历B中的节点，若有在哈希集合中出现的则为相交节点；时间复杂度为O(m + n)，空间复杂度为O(m)；
双指针，设立两个指针分别各自遍历一遍A和B，无论是否相交，最后一定会相遇；时间复杂度为O(m + n)，空间复杂度为O(1)；
