无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
思路：滑动窗口
暴力解法：两次遍历，记录以每一个字符开头的最长无重复字符子串，返回最大值，时间复杂度O(n^2^)
肯定会超时
观察可以发现一个规律：假设 Si-j 是以第 i 个字符开头的无重复字符最长子串，那么当以第 i+1 个字符开头时，i+1到 j 一定也是无重复字符子串，右指针不用回退，也就是说可以维护一个滑动窗口。时间复杂度O(n)。
反转链表 https://leetcode.cn/problems/reverse-linked-list/
思路：mock_head = nullptr ，p指针指向head，q指针指向mock_head，也就是说p指针在右，q指针在左，当p非空时，循环执行：先记录p的下一个节点到tmp，把p->next指向q，然后把q放到p的位置，最后把p放到tmp。
数组中第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
思路：维护一个大小为K的最小堆，堆中的元素是数组中最大的K个，堆顶的元素就是答案
1 priority_queue<int , vector<int >, greater<int >> min_heap;
三数之和 https://leetcode.cn/problems/3sum/
暴力解法：三重循环，时间复杂度O(n^3^)。
三指针解法：先把数组排序，定义三个指针，i，j = i + 1，k = nums.size() - 1
i 由外层 for 循环控制，去重机制：if(i > 0 && nums[i] == nums[i - 1]) continue;
内层由一个 while 语句控制 j 和 k ，while (j < k)
计算当前的三数之和：
（1）如果为0，那么保存结果，更新 j 和 k 的值，注意 ：更新时 j 和 k 都要考虑去重：
1 2 3 4 while (j < k && nums[j] == nums[j + 1 ]) ++j;while (j < k && nums[k] == nums[k - 1 ]) --k;++j; --k;
（2）如果和大于0，–k
（3）否则，++j
最大子数组和 https://leetcode.cn/problems/maximum-subarray/
思路：考虑以第 i 个位置结束的子数组，nums[i] 有两种选择：要么和前面构成数组，要么自己单独成一个数组
所以这道题可以考虑动态规划，dp[i]记录以 nums[i] 结尾的最大连续子数组，dp[i + 1] = max(dp[i] + nums[i + 1]， nums[i + 1])
1 2 3 4 5 6 7 8 9 int m = nums.size ();vector<int > dp (m, 0 ) ;dp[0 ] = nums[0 ]; int res = dp[0 ];for (int i = 1 ; i < m; ++i) { dp[i] = max (dp[i - 1 ] + nums[i], nums[i]); res = max (res, dp[i]); } return res;
最长回文子串 https://leetcode.cn/problems/longest-palindromic-substring/
思路：遍历字符串中的每一个字符，计算以该字符为中心的最长回文子串，这时分两种情况：奇数扩散和偶数扩散，取两者最大值，遍历过程中记录最大回文子串的长度和该子串的中心位置dex，计算出子串的左端点，最后使用：
合并两个有序链表 https://leetcode.cn/problems/merge-two-sorted-lists/description/
思路：使用三个指针，p、q 和 cur ，前俩分别指向这两个链表的头节点，new一个mock_head节点，cur指向它，最后返回mock_head->next
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 ListNode* p = list1; ListNode* q = list2; ListNode* mock_head = new ListNode (0 ); ListNode* cur - mock_head; while (p != nullptr || q != nullptr ) { if (p == nullptr ) { cur->next = q; break ; } if (q == nullptr ) { cur->next = p; break ; } if (p->val < q->val) { cur->next = p; cur = p; p = p->next; } else { cur->next = q; cur = q; q = q->next; } } return mock_head->next;
二叉树地层序遍历 https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
思路：使用一个队列保存节点，队列的大小为每层节点的数量
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 : vector<vector<int >> levelOrder (TreeNode* root) { if (root == nullptr ) return {}; queue<TreeNode*> que; vector<vector<int >> res; que.push (root); while (!que.empty ()) { int m = que.size (); vector<int > tmp; for (int i = 0 ; i < m; ++i) { TreeNode* p = que.front (); que.pop (); tmp.push_back (p->val); if (p->left != nullptr ) que.push (p->left); if (p->right != nullptr ) que.push (p->right); } res.push_back (tmp); } return res; } };
岛屿数量 https://leetcode.cn/problems/number-of-islands/
思路：使用dfs，将1改为0，dfs的调用次数就是岛屿的数量
注意：不能改为-1，-1不是一个合法的char
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 class Solution {public : void dfs (vector<vector<char >>& grid, int i, int j, int m, int n) grid[i][j] = '0' ; if (j + 1 < n && grid[i][j + 1 ] == '1' ) dfs (grid, i, j + 1 , m, n); if (i + 1 < m && grid[i + 1 ][j] == '1' ) dfs (grid, i + 1 , j, m, n); if (j - 1 >= 0 && grid[i][j - 1 ] == '1' ) dfs (grid, i, j - 1 , m, n); if (i - 1 >= 0 && grid[i - 1 ][j] == '1' ) dfs (grid, i - 1 , j, m, n); } int numIslands (vector<vector<char >>& grid) int m = grid.size (); int n = grid[0 ].size (); int res = 0 ; for (int i = 0 ; i < m; ++i) { for (int j = 0 ; j < n; ++j) { if (grid[i][j] == '1' ) { dfs (grid, i, j, m, n); ++res; } } } return res; } };
两数之和 https://leetcode.cn/problems/two-sum/description/
思路：使用一个unordered_map记录nums[i] 和 i
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : vector<int > twoSum (vector<int >& nums, int target) { int m = nums.size (); unordered_map<int , int > mp; mp[nums[0 ]] = 0 ; for (int i = 1 ; i < m; ++i) { int n = target - nums[i]; if (mp.count (n) != 0 ) { return {mp[n], i}; } mp[nums[i]] = i; } return {}; } };
全排列 https://leetcode.cn/problems/permutations/description/https://leetcode.cn/problems/permutations/description/
思路：使用递归和回溯，关键的两个数据结构：vector used(nums.size(), false)和vector paths
注意：vector的构造参数是（元素个数，值）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : void backtrace (vector<int >& nums, vector<vector<int >>& res, vector<bool >& used, vector<int >& paths) if (paths.size () == nums.size ()) { res.push_back (paths); return ; } for (int i = 0 ; i < nums.size (); ++i) { if (used[i] == true ) continue ; paths.push_back (nums[i]); used[i] = true ; backtrace (nums, res, used, paths); used[i] = false ; paths.pop_back (); } } vector<vector<int >> permute (vector<int >& nums) { vector<int > paths; vector<bool > used (nums.size(), false ) ; vector<vector<int >> res; backtrace (nums, res, used, paths); return res; } };
有效的括号 https://leetcode.cn/problems/valid-parentheses/description/
思路：使用一个栈，遇到左括号入栈，遇到右括号分两种情况：如果此时栈为空，直接返回false，否则取栈顶元素，判断左右括号是否匹配，如果不匹配，直接返回false，否则移除栈顶元素，接着往下遍历。最后，如果栈为空，返回true，否则返回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 class Solution {public : bool is_left (const char & ch) if (ch == '(' || ch == '{' || ch == '[' ) return true ; return false ; } bool match (char ch1, char ch2) if (ch1 == '(' && ch2 == ')' ) return true ; if (ch1 == '[' && ch2 == ']' ) return true ; if (ch1 == '{' && ch2 == '}' ) return true ; return false ; } bool isValid (string s) int m = s.size (); stack<char > st; for (int i = 0 ; i < m; ++i) { if (is_left (s[i])) { st.push (s[i]); } else { if (st.empty ()) return false ; char left = st.top (); if (!match (left, s[i])) return false ; else { st.pop (); } } } if (st.empty ()) return true ; return false ; } };
合并两个有序数组 https://leetcode.cn/problems/merge-sorted-array/description/
思路：双指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : void merge (vector<int >& nums1, int m, vector<int >& nums2, int n) vector<int > tmp; int p = 0 , q = 0 ; while (p < m || q < n) { if (p == m) { tmp.push_back (nums2[q++]); } else if (q == n) { tmp.push_back (nums1[p++]); } else { if (nums1[p] < nums2[q]) { tmp.push_back (nums1[p++]); } else { tmp.push_back (nums2[q++]); } } } for (int i = 0 ; i < m + n; ++i) { nums1[i] = tmp[i]; } } };
买卖股票的最佳时机 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
思路：遍历每一天，把它当成卖出日，看看用之前最低价买入能赚多少，同时更新最低买入价。所以只需要一次遍历，维护最低买入价和当前最大利润
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int maxProfit (vector<int >& prices) int m = prices.size (); int min_mairu = prices[0 ]; int max_profit = 0 ; for (int i = 1 ; i < m; ++i) { max_profit = max (max_profit, prices[i] - min_mairu); min_mairu = min (prices[i], min_mairu); } return max_profit; } };
反转链表II https://leetcode.cn/problems/reverse-linked-list-ii/description/
思路：使用mock_head和两个指针，pre指向left端点的前一个节点，cur指向left所在节点，执行right-left次操作，没次操作都干同一件事情，把cur->next节点摘下来，插到pre的后面（也叫头插法）。
注意：整个过程中，pre和cur指针的位置不用动
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : ListNode* reverseBetween (ListNode* head, int left, int right) { ListNode* mock_head = new ListNode (0 ); mock_head->next = head; ListNode* pre = mock_head; ListNode* cur = pre->next; for (int i = 1 ; i < left; ++i) { pre = cur; cur = cur->next; } for (int i = 0 ; i < right - left; ++i) { ListNode* next = cur->next; cur->next = next->next; pre->next = next; next->next = pre->next; } return mock_head->next; };
