leetcode 1 ~ 100

1. 两数之和（用哈希表减少查找的时间复杂度）

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> dict; // val : indexfor (int i = 0; i < nums.size(); i++){if (dict.count(target - nums[i]))return {dict[target - nums[i]], i};elsedict[nums[i]] = i;}return {};}
};

（注：本题也可以用双指针算法。）

2. 两数相加（高精度加法）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* dummy = new ListNode(-1);ListNode* p = dummy;int t = 0;while (l1 || l2 || t){if (l1) {t += l1->val;l1 = l1->next;}if (l2) {t += l2->val;l2 = l2->next;}p->next = new ListNode(t % 10);p = p->next;t /= 10;}return dummy->next;}
};

3.无重复字符的最长子串：（模板：经典的滑动窗口算法）

class Solution {
public:int lengthOfLongestSubstring(string s) {int res = 0;unordered_map<char, int> ht; // ht: hashtablefor (int l = 0, r = 0; r < s.size(); r++){ht[s[r]]++;while (ht[s[r]] > 1){ht[s[l]]--;l++;}res = max(res, r - l + 1);}return res;}
};

5. 最长回文子串（枚举）

class Solution {
public:string longestPalindrome(string s) {string res = "";for (int i = 0; i < s.size(); i++) {// 看回文串的长度是否是奇数int l = i - 1, r = i + 1;while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;if (res.size() < r - (l + 1)) res = s.substr(l + 1, r - (l + 1));// 看回文串的长度是否是偶数l = i, r = i + 1;while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;if (res.size() < r - (l + 1)) res = s.substr(l + 1, r - (l + 1));}return res;}
};

6. Z 自形变换（找规律）

class Solution {
public:string convert(string s, int numRows) {if (numRows == 1) return s; // numRows = 1会导致base为0，需要特判string res = "";int base = 2 * numRows - 2;for (int k = 0; k < numRows; k++)for (int i = 0; i < s.size(); i++)if ((i - k) % base == 0 || (i + k) % base == 0)res += s[i];return res;}
};// 每一趟会有 numRows + (nuRows - 2) = 2 * numRows - 2 = base 个数
// 故最终第0行应该是满足 (i + 0) % base == 0的数
// 第1行是 (i + 1) % base == 0的数
// 第 k 行是 (i + k) % base == 0的数
// k的范围是从 0 到 numRows - 1

7.整数反转

class Solution {
public:int reverse(int x) {int res = 0;bool is_minus = (x < 0);while (x){if (is_minus && res < (INT_MIN - x % 10) / 10) return 0;if (!is_minus && res > (INT_MAX - x % 10) / 10) return 0;res = res * 10 + x % 10;x /= 10;}return res;}
};

8. 字符串转换整数（atoi）

class Solution {
public:int myAtoi(string s) {int res = 0;bool is_minus = false;for (int i = 0; i < s.size(); i++){if (s[i] == ' ') continue;else if (s[i] == '+' || s[i] == '-'){is_minus = (s[i] == '-');if (i + 1 < s.size() && !isdigit(s[i + 1])) return res;else continue;}else if (isdigit(s[i])){while (i < s.size() && isdigit(s[i])){int t = s[i] - '0';if (is_minus && res > (INT_MAX - t) / 10) return INT_MIN;if (!is_minus && res > (INT_MAX - t) / 10) return INT_MAX;res = res * 10 + t;i++;}if (is_minus) return -res;else return res;}else return res;}return res;}
};

9. 回文数

class Solution {
public:bool isPalindrome(int x) {if (x < 0) return false;if (!x) return true;long long res = 0; // 翻转后有可能会溢出int tmp = x;while (tmp){res = res * 10 + tmp % 10;tmp /= 10;}return res == x;}
};

11.盛水最多的容器（贪心（基于双指针来实现））

class Solution {
public:int maxArea(vector<int>& height) {int res = 0;int i = 0, j = height.size() - 1;while (i < j){res = max(res, min(height[i], height[j]) * (j - i));if (height[i] < height[j]) i++;else j--;}return res;}
};

12. 整数转罗马数字

class Solution {
public:string intToRoman(int num) {unordered_map<int, string> dict{{1, "I"}, {4, "IV"}, {5, "V"}, {9, "IX"}, {10, "X"}, {40, "XL"}, {50, "L"}, {90, "XC"}, {100, "C"}, {400, "CD"}, {500, "D"}, {900, "CM"}, {1000, "M"}};vector<int> base{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};string res = "";for (auto b : base){if (!num) break;int cnt = num / b;num %= b;if (cnt){for (int i = 0; i < cnt; i++)res += dict[b];}}return res;}
};

13. 罗马数字转整数

class Solution {
public:int romanToInt(string s) {// 从右往左遍历，定义一个哈希表表示大小关系，正常情况下右边小于等于左边；// 如果右边大于左边，说明出现了特殊规则// unordered_map<char, int> pri{{'I', 1}, {'V', 2}, {'X', 3}, {'L', 4}, \// {'C', 5}, {'D', 6}, {'M', 7}}; /* 后记：val表的功能可以替代pri，故可以不用专门定义pri */unordered_map<char, int> val{{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, \{'C', 100}, {'D', 500}, {'M', 1000}};int res = 0;for (int i = s.size() - 1; i >= 0;){if (i && val[s[i]] > val[s[i - 1]]) // e.g. IV{res += val[s[i]] - val[s[i - 1]];i -= 2;}else{res += val[s[i]];i--;}}return res;}
};

14. 最长公共前缀

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string cp = strs[0];for (auto& s : strs)for (int i = 0; i < cp.size(); i++)if (cp[i] != s[i]) {cp.erase(cp.begin() + i, cp.end());break;   }return cp;}
};

15. 三数之和（双指针 + 去重）

本题双指针算法的判定依据：

对于每一个固定的 i，当 j 增大时，k 必减小。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end()); // sort是双指针算法和去重的前提vector<vector<int>> res;for (int i = 0; i < nums.size() - 2; i++){if (i && nums[i] == nums[i - 1]) continue; // 对i去重for (int j = i + 1, k = nums.size() - 1; j < nums.size() - 1; j++){if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 对j去重while (j < k && nums[i] + nums[j] + nums[k] > 0) k--;if (j == k) break; // 注意：两指针不能重合！if (nums[i] + nums[j] + nums[k] == 0)res.push_back({nums[i], nums[j], nums[k]});}}return res;}
};

16. 最接近的三数之和（双指针算法）

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(), nums.end());pair<int, int> res(INT_MAX, INT_MAX);for (int i = 0; i < nums.size() - 2; i++){if (i && nums[i] == nums[i - 1]) continue;for (int j = i + 1, k = nums.size() - 1; j < k; j++){if (j > i + 1 && nums[j] == nums[j - 1]) continue;while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) k--;int sum = nums[i] + nums[j] + nums[k];res = min(res, make_pair(abs(sum - target), sum));if (j < k - 1){sum = nums[i] + nums[j] + nums[k - 1];res = min(res, make_pair(target - sum, sum));}}}return res.second;}
};

17. 电话号码的字母组合（标准 DFS）

class Solution {
public:string s;unordered_map<char, string> dict{{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};vector<string> res;vector<string> letterCombinations(string digits) {if (digits.empty()) return {};dfs(digits, 0);return res;}void dfs(string digits, int idx){if (idx == digits.size()){res.push_back(s);return;}for (char c : dict[digits[idx]]){s += c;dfs(digits, idx + 1);s.pop_back();}}
};

18. 四数之和（双指针算法）

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;if (nums.size() < 4) return res;sort(nums.begin(), nums.end());for (int i = 0; i < nums.size() - 3; i++){if (i && nums[i] == nums[i - 1]) continue;for (int j = i + 1; j < nums.size() - 2; j++){if (j > i + 1 && nums[j] == nums[j - 1]) continue;for (int k = j + 1, m = nums.size() - 1; k < m; k++){if (k > j + 1 && nums[k] == nums[k - 1]) continue;while (k < m - 1 && (long)nums[i] + nums[j] + nums[k] + nums[m - 1] >= target) m--; // 注意：不加long会有数据溢出问题，下同if ((long)nums[i] + nums[j] + nums[k] + nums[m] == target)res.push_back({nums[i], nums[j], nums[k], nums[m]});}}}return res;}
};

19. 删除链表的倒数第 N 个结点（前后双指针寻找结点 + dummy 避免特判）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(-1, head);ListNode* left = dummy;ListNode* right = head;for (int i = 0; i < n; i++)right = right->next;while (right != nullptr){left = left->next;right = right->next;}left->next = left->next->next;ListNode* res = dummy->next;delete dummy; // 删除哑节点，释放内存return res;}
};

20. 有效的括号（栈的简单应用）

class Solution {
public:bool isValid(string s) {stack<char> stk;for (auto c : s){if (c == '(' || c == '{' || c == '[')stk.push(c);else{// if (stk.empty() || (c == ')' && stk.top() != '(') || (c == '}' && stk.top() != '{') || (c == ']' && stk.top() != '['))if (stk.empty() || abs(stk.top() - c) > 2) // (){}[] = 40 41 123 125 91 93return false;else stk.pop();}}return stk.empty();}
};

21. 合并两个有序链表（模拟归并排序中的二路归并操作）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummy = new ListNode(-1);ListNode* p = dummy;ListNode* p1 = list1;ListNode* p2 = list2;while (p1 && p2){if (p1->val <= p2->val){p->next = p1;p1 = p1->next;}else{p->next = p2;p2 = p2->next;}p = p->next;}if (p1) p->next = p1;if (p2) p->next = p2;return dummy->next;}
};

22. 括号生成（DFS）

class Solution {
public:string s;vector<string> res;vector<string> generateParenthesis(int n) {// 左括号用了i个，右括号用了j个，当i == j == n时，即可dfs(n, 0, 0);return res;}void dfs(int n, int left, int right){if (left == n && right == n){res.push_back(s);return;}// 左分支的条件如果满足，就转向左分支if (left < n){s += '(';dfs(n, left + 1, right); // 在左分支里继续进行递归s.pop_back(); // 和回溯}//如果右分支的条件满足，就转向右分支if (right < left){s += ')';dfs(n, left, right + 1); // 在右分支里继续进行递归s.pop_back(); // 和回溯}}
};

24. 两两交换链表中的节点（链表结点交换算法）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummy = new ListNode(-1, head);ListNode* p = dummy;while (p->next && p->next->next){ListNode* left = p->next; // 必须要先用两个临时结点把p->nextListNode* right = p->next->next; // 和p->next->next保存起来p->next = right;left->next = right->next;right->next = left;p = left; // <=> p = p->next->next;}return dummy->next;}
};

26. 删除有序数组中的重复项（经典双指针算法）

class Solution {
public:int removeDuplicates(vector<int>& nums) {int k = 0;for (int i = 0; i < nums.size(); i++){if (!i || nums[i] != nums[i - 1])nums[k++] = nums[i];}return k;}
};

27. 移除元素（简单的双指针算法）

第一种实现方式：两个指针都从左往右走

class Solution {
public:int removeElement(vector<int>& nums, int val) {int k = 0; // k是新数组的长度，初始时为0for (int i = 0; i < nums.size(); i++)if (nums[i] != val)nums[k++] = nums[i];return k;}
};

第二种实现方式：两个指针从两头出发往中间走

class Solution {
public:int removeElement(vector<int>& nums, int val) {int n = nums.size();int i = -1, j = n;while (i < j){do i++; while (i < j && nums[i] != val);do j--; while (i < j && nums[j] == val);if (i < j) swap(nums[i], nums[j]);}return i;}
};
// 注：这种实现方式可以应对以下两种边界情况：
// （1）nums为空；
// （2）nums仅含1个元素

31. 下一个排列：

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();// 从后往前找到第一对升序的元素int i = n - 1;while (i >= 1 && nums[i - 1] >= nums[i]) i--;if (i == 0) // 如果不存在升序元素对，reverse(nums.begin(), nums.end()); // 直接将降序翻转为升序else // 如果存在升序元素对，{int j = i; i--; // 此时nums[i - 1], nums[i]即为从后往前第一对升序元素// 再次从后往前，寻找第一个大于nums[i]的元素int k = n - 1;while (k > i && nums[i] >= nums[k]) k--;// 找到后将nums[i]和nums[k]交换swap(nums[i], nums[k]);// 此时[j, end)必降序，将其翻转为升序即可reverse(nums.begin() + j, nums.end());}}
};

32. 最长有效括号

class Solution {
public:int longestValidParentheses(string s) {int res = 0;stack<int> stk;for (int i = 0, start = -1; i < s.size(); i++){if (s[i] == '(') stk.push(i);else // 来右括号{if (!stk.empty()) // 来右括号且栈不空，说明栈顶有左括号{stk.pop(); // 将左括号弹出，if (!stk.empty()) // 如果弹出后栈顶仍有左括号，res = max(res, i - stk.top()); // 则左括号的下一个位置到i的长度即为当前i对应的最大有效括号长度else res = max(res, i - start); // 如果将栈顶左括号弹出后栈空，则从start + 1到i皆为有效长度}else // 来右括号且栈空{start = i;}}}return res;}
};

33.搜索旋转排序数组：

class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while (l <= r){int mid = l + r >> 1;if (nums[mid] == target) return mid;// 我们要做的就是确定每次的mid到底是在左半段还是右半段中if (nums[l] <= nums[mid]) // 说明mid在左半段，则左半段可以二分{if (nums[l] <= target && target < nums[mid])r = mid - 1;elsel = mid + 1;}else // 说明mid在右半段，则右半段可以二分{if (nums[mid] < target && target <= nums[r])l = mid + 1;elser = mid - 1;}}return -1;}
};

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

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> res;if (nums.empty()) return {-1, -1};int l = 0, r = nums.size() - 1;while (l < r){int mid = l + r >> 1;if (nums[mid] >= target) r = mid;else l = mid + 1;}if (nums[l] != target) return {-1, -1};else{res.push_back(l);int l = 0, r = nums.size() - 1;while (l < r){int mid = l + r + 1 >> 1;if (nums[mid] <= target) l = mid;else r = mid - 1;}res.push_back(l);}return res;}
};

35.搜索插入位置：

// 找到从前往后第一个大于等于target的位置
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int l = 0, r = nums.size(); // 注意：此处不再是nums.size() - 1while (l < r){int mid = l + r >> 1;if (nums[mid] >= target) r = mid;else l = mid + 1;}return l;}
};

36.有效的数独：

class Solution {
public:bool row[9][9], col[9][9], block[3][3][9];bool isValidSudoku(vector<vector<char>>& board) {memset(row, 0, sizeof row);memset(col, 0, sizeof col);memset(block, 0, sizeof block);for (int i = 0; i < 9; i++)for (int j = 0; j < 9; j++)if (board[i][j] != '.'){int t = board[i][j] - '1';if (row[i][t] || col[j][t] || block[i / 3][j / 3][t])return false;elserow[i][t] = col[j][t] = block[i / 3][j / 3][t] = true;}return true;}
};

37.解数独：

class Solution {
public:bool row[9][9], col[9][9], block[3][3][9];void solveSudoku(vector<vector<char>>& board) {memset(row, 0, sizeof row);memset(col, 0, sizeof col);memset(block, 0, sizeof block);int n = board.size(), m = board[0].size();for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)if (board[i][j] != '.'){int t = board[i][j] - '1';row[i][t] = col[j][t] = block[i / 3][j / 3][t] = true;}dfs(board, 0, 0);}bool dfs(vector<vector<char>>& board, int x, int y){int n = board.size(), m = board[0].size();if (y == m) { y = 0; x++; }if (x == n) return true;if (board[x][y] != '.') return dfs(board, x, y + 1);for (int num = 0; num < 9; num++){if (!row[x][num] && !col[y][num] && !block[x / 3][y / 3][num]){board[x][y] = num + '1';row[x][num] = col[y][num] = block[x / 3][y / 3][num] = true;if (dfs(board, x, y + 1)) return true;board[x][y] = '.';row[x][num] = col[y][num] = block[x / 3][y / 3][num] = false;}}return false;}
};

38.外观数列：

class Solution {
public:string countAndSay(int n) {string s = "1";for (int i = 0; i < n - 1; i++){string tmp = "";for (int j = 0; j < s.size();){int k = j + 1;while (k < s.size() && s[j] == s[k]) k++;tmp += to_string(k - j) + s[j];j = k;}s = tmp;}return s;}
};

39.组合总和：

• 第一种 DFS：逐数字枚举

class Solution {
public:vector<int> path;vector<vector<int>> res;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(candidates, 0, target);return res;    }void dfs(vector<int>& candidates, int u, int target){if (target == 0){res.push_back(path);return;} // 注意：此if与后面if的顺序不能颠倒！if (u == candidates.size()) return;// skip current positiondfs(candidates, u + 1, target);// choose current positionif (target - candidates[u] >= 0){path.push_back(candidates[u]);dfs(candidates, u, target - candidates[u]);path.pop_back();}}
};

• 第二种 DFS：按第 i 个数选多少个来搜索

class Solution {
public:vector<int> path;vector<vector<int>> res;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(candidates, 0, target);return res;    }void dfs(vector<int>& candidates, int u, int target){if (target == 0){res.push_back(path);return;} // 注意：此if与后面if的顺序不能颠倒！if (u == candidates.size()) return;for (int i = 0; i * candidates[u] <= target; i++){dfs(candidates, u + 1, target - i * candidates[u]);path.push_back(candidates[u]);}for (int i = 0; i * candidates[u] <= target; i++)path.pop_back();}
};

40.组合总和：

class Solution {
public:vector<int> path;vector<vector<int>> res;vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());dfs(candidates, 0, target);return res;    }void dfs(vector<int>& candidates, int idx, int target){if (target == 0){res.push_back(path);return;}if (idx == candidates.size()) return;int prev = -1;for (int i = idx; i < candidates.size(); i++){if (prev != candidates[i] && candidates[i] <= target){prev = candidates[i];path.push_back(candidates[i]);dfs(candidates, i + 1, target - candidates[i]);path.pop_back();}}}
};

41.缺失的第一个正数：

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for (int i = 0; i < n; i++){while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])swap(nums[nums[i] - 1], nums[i]);}for (int i = 0; i < n; i++){if (nums[i] != i + 1)return i + 1;}return n + 1;}
};

42.接雨水：

class Solution {
public:int trap(vector<int>& height) {int ans = 0;int l = 0, r = height.size() - 1;int lmax = 0, rmax = 0;while (l < r){lmax = max(lmax, height[l]);rmax = max(rmax, height[r]);if (lmax <= rmax){ans += lmax - height[l];l++;}else{ans += rmax - height[r];r--;}}return ans;}
};

43.字符串相乘：

class Solution {
public:string multiply(string num1, string num2) {int n = num1.size(), m = num2.size();vector<int> A, B;for (int i = n - 1; i >= 0; i--) A.push_back(num1[i] - '0');for (int i = m - 1; i >= 0; i--) B.push_back(num2[i] - '0');vector<int> C(n + m);for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)C[i + j] += A[i] * B[j];// 集中处理进位int t = 0;for (int i = 0; i < C.size(); i++){t += C[i];C[i] = t % 10;t /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();string res;for (int i = C.size() - 1; i >= 0; i--) res += C[i] + '0';return res;}
};

44.通配符匹配：

class Solution {
public:bool isMatch(string s, string p) {int n = s.size(), m = p.size();s = ' ' + s, p = ' ' + p;vector<vector<bool>> f(n + 1, vector<bool>(m + 1));f[0][0] = true;for (int i = 0; i <= n; i++) // i必须从0开始，因为f[0][j]是有意义的for (int j = 1; j <= m; j++) // j可以从1开始，因为f[i][0]必为falseif (p[j] == '*')f[i][j] = f[i][j - 1] || (i && f[i - 1][j]);elsef[i][j] = (s[i] == p[j] || p[j] == '?') && (i && f[i - 1][j - 1]);return f[n][m];}
};

45.跳跃游戏 II：

class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();vector<int> f(n);for (int i = 1, j = 0; i < n; i++){while (j + nums[j] < i) j++;f[i] = f[j] + 1;}return f[n - 1];}
};

46.全排列：

class Solution {
public:vector<int> path;vector<vector<int>> res;bool st[10];vector<vector<int>> permute(vector<int>& nums) {dfs(nums, 0);return res;}void dfs(vector<int>& nums, int u){if (u == nums.size()){res.push_back(path);return;}for (int i = 0; i < nums.size(); i++){if (!st[i]){path.push_back(nums[i]);st[i] = true;dfs(nums, u + 1);path.pop_back();st[i] = false;}}}
};

47.全排列 II：

class Solution {
public:vector<int> path;vector<vector<int>> res;bool st[10];vector<vector<int>> permuteUnique(vector<int>& nums) {vector<int> tmp = nums;sort(tmp.begin(), tmp.end());dfs(tmp, 0);return res;}void dfs(vector<int>& nums, int u){if (u == nums.size()){res.push_back(path);return;}int prev = -11;for (int i = 0; i < nums.size(); i++){if (prev != nums[i] && !st[i]){prev = nums[i];path.push_back(nums[i]);st[i] = true;dfs(nums, u + 1);path.pop_back();st[i] = false;}}}
};

48.旋转图像：

class Solution {
public:void rotate(vector<vector<int>>& matrix) {/* 两次对称即可：先沿反对角线对称，再沿中轴左右对称*/int n = matrix.size();for (int i = 0; i < n; i++)for (int j = 0; j < i; j++)swap(matrix[i][j], matrix[j][i]);for (int i = 0; i < n; i++)for (int j = 0; j < n / 2; j++)swap(matrix[i][j], matrix[i][n - 1 - j]);}
};

49.字母异位词分组：

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> map;for (auto& str : strs){string tmp = str;sort(tmp.begin(), tmp.end());map[tmp].push_back(str);}vector<vector<string>> res;for (auto& item : map) res.push_back(item.second);return res;}
};

50.Pow(x, n)：

class Solution {
public:double myPow(double x, int n) {typedef long long LL;bool is_minus = n < 0;double res = 1;for (LL k = abs(LL(n)); k; k >>= 1){if (k & 1) res *= x;x *= x;}if (is_minus) res = 1 / res;return res;}
};

51. N 皇后（DFS）

class Solution {
public:bool col[10], dg[20], udg[20];vector<vector<string>> res;vector<vector<string>> solveNQueens(int n) {// 初始化棋盘vector<string> g;for (int i = 0; i < n; i++)g.push_back(string(n, '.'));dfs(0, n, g);return res;}void dfs(int u, int n, vector<string>& g){if (u == n){res.push_back(g);return;}for (int i = 0; i < n; i++){if (!col[i] && !dg[u - i + n] && !udg[u + i]){g[u][i] = 'Q';col[i] = dg[u - i + n] = udg[u + i] = true;dfs(u + 1, n, g);g[u][i] = '.';col[i] = dg[u - i + n] = udg[u + i] = false;}}}
};

52. N 皇后 II（DFS，和 51 题完全一样，只是不需要记录方案是什么）

class Solution {
public:bool col[10], dg[20], udg[20];int res = 0;int totalNQueens(int n) {dfs(0, n);return res;}void dfs(int u, int n){if (u == n){res++;return;}for (int i = 0; i < n; i++){if (!col[i] && !dg[u - i + n] && !udg[u + i]){col[i] = dg[u - i + n] = udg[u + i] = true;dfs(u + 1, n);col[i] = dg[u - i + n] = udg[u + i] = false;}}}
};

53. 最大子数组和（动态规划）

从动态规划的角度去理解：（更推荐）

class Solution {
public:int maxSubArray(vector<int>& nums) {int res = INT_MIN;for (int i = 0, last = 0; i < nums.size(); i++){last = nums[i] + max(last, 0);res = max(res, last);}return res;}
};// 动态规划：
// f[i] 表示所有以nums[i]结尾的连续子数组的最大和
// f[i] = max(nums[i], f[i - 1] + nums[i]) = nums[i] + max(f[i - 1], 0);
// 由于只用到了两个状态，因此可以用一个变量保存f[i - 1]，这样空间复杂度可以优化至O(1)

从贪心的角度去理解：

class Solution {
public:int maxSubArray(vector<int>& nums) {int res = -1e5, sum = 0;for (int i = 0; i < nums.size(); i++){sum += nums[i];if (sum < nums[i]) sum = nums[i];res = max(res, sum);}return res;}
};
// 贪心：
// 从左到右扫描，

54. 螺旋矩阵

方法一：（迭代）利用方向数组（推荐）

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> res;int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};int m = matrix.size(), n = matrix[0].size();vector<vector<bool>> st(m, vector<bool>(n));for (int i = 0, x = 0, y = 0, d = 0; i < m * n; i++){// 先判断上一步有没有走对，如果没有走对，就纠正上一步并让其走对if (x < 0 || x >= m || y < 0 || y >= n || st[x][y]){x -= dx[d], y -= dy[d];d = (d + 1) % 4;x += dx[d], y += dy[d];}// 如果走对的话就记录res.push_back(matrix[x][y]);st[x][y] = true;x += dx[d], y += dy[d]; // 并继续往前走}return res;}
};

方法二：（DFS）模拟

class Solution {
public:vector<int> res;vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();dfs(matrix, 0, 0, m - 1, n - 1); // 传入的是左上角和右下角的坐标(x1, y1)和(x2, y2)return res;}void dfs(vector<vector<int>>& matrix, int x1, int y1, int x2, int y2){if (x1 > x2 || y1 > y2) return;int i = x1, j = y1;while (j <= y2){res.push_back(matrix[i][j]);j++;}j--,i++;while (i <= x2){res.push_back(matrix[i][j]);i++;}i--, j--;while (i > x1 && j >= y1) // i > x1的目的是防止出现回退，如第2个测试用例{res.push_back(matrix[i][j]);j--;}j++, i--;while (j < y2 && i > x1) // j < y2的目的也是防止出现回退，例如[[7], [9], [6]]{res.push_back(matrix[i][j]);i--;}dfs(matrix, x1 + 1, y1 + 1, x2 - 1, y2 - 1);}
};

55.跳跃游戏：

class Solution {
public:bool canJump(vector<int>& nums) {for (int i = 0, j = 0; i < nums.size(); i++){if (j < i) return false;j = max(j, i + nums[i]);}return true;}
};

56. 区间合并（模板：区间合并）

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;sort(intervals.begin(), intervals.end());int st = -1, ed = -1;for (auto seg : intervals){if (ed < seg[0]){if (st != -1) res.push_back({st, ed});st = seg[0], ed = seg[1];}else ed = max(ed, seg[1]);}if (st != -1) res.push_back({st, ed});return res;}
};

57. 插入区间

方法一：先用二分查找找到插入位置，将新区间插入，再调用标准的区间合并算法

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {// 先二分找到插入位置int l = 0, r = intervals.size();while (l < r){int mid = l + r >> 1;if (intervals[mid][0] >= newInterval[0]) r = mid;else l = mid + 1;}intervals.insert(intervals.begin() + l, newInterval);// 调用区间合并模板int st = -1, ed = -1;vector<vector<int>> res;for (int i = 0; i < intervals.size(); i++){if (ed < intervals[i][0]){if (st != -1) res.push_back({st, ed});st = intervals[i][0], ed = intervals[i][1];}else ed = max(ed, intervals[i][1]);}if (st != -1) res.push_back({st, ed});return res;}
};

方法二：（Y总做法）模拟

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>> res;// 首先寻找左侧没有交叠的区间int k = 0;while (k < intervals.size() && intervals[k][1] < newInterval[0]){res.push_back(intervals[k]);k++;}// 对中间有交叠的区间进行合并if (k < intervals.size()) // 这一条件可以处理intervals为空的情况{newInterval[0] = min(intervals[k][0], newInterval[0]);while (k < intervals.size() && intervals[k][0] <= newInterval[1]){newInterval[1] = max(intervals[k][1], newInterval[1]);k++;}}res.push_back(newInterval);// 右侧没有交叠的区间也照抄while (k < intervals.size()){res.push_back(intervals[k]);k++;}return res;}
};

58. 最后一个单词的长度（模拟题）

class Solution {
public:int lengthOfLastWord(string s) {int k = s.size() - 1;while (s[k] == ' ') k--;int j = k;while (j >= 0 && s[j] != ' ') j--;return k - j;}
};

59. 螺旋矩阵 II（方向数组的简单应用）

class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int>(n));int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};for (int i = 1, x = 0, y = 0, d = 0; i <= n * n; i++){if (x < 0 || x >= n || y < 0 || y >= n || res[x][y] != 0){x -= dx[d], y -= dy[d];d = (d + 1) % 4;x += dx[d], y += dy[d];}res[x][y] = i;x += dx[d], y += dy[d];}return res;}
};