学做网站用谁的书,英文网站建设 飞沐,wordpress哪个主题,360优化大师下载文章目录 1. 两数之和#xff08;用哈希表减少查找的时间复杂度#xff09;2. 两数相加#xff08;高精度加法#xff09;3.无重复字符的最长子串#xff1a;#xff08;模板#xff1a;经典的滑动窗口算法#xff09;5. 最长回文子串#xff08;枚举#xff09;6. Z… 文章目录 1. 两数之和用哈希表减少查找的时间复杂度2. 两数相加高精度加法3.无重复字符的最长子串模板经典的滑动窗口算法5. 最长回文子串枚举6. Z 自形变换找规律7.整数反转8. 字符串转换整数atoi9. 回文数11.盛水最多的容器贪心基于双指针来实现12. 整数转罗马数字13. 罗马数字转整数14. 最长公共前缀15. 三数之和双指针 去重16. 最接近的三数之和双指针算法17. 电话号码的字母组合标准 DFS18. 四数之和双指针算法19. 删除链表的倒数第 N 个结点前后双指针寻找结点 dummy 避免特判20. 有效的括号栈的简单应用21. 合并两个有序链表模拟归并排序中的二路归并操作22. 括号生成DFS24. 两两交换链表中的节点链表结点交换算法26. 删除有序数组中的重复项经典双指针算法27. 移除元素简单的双指针算法31. 下一个排列32. 最长有效括号33.搜索旋转排序数组34.在排序数组中查找元素的第一个和最后一个位置35.搜索插入位置36.有效的数独37.解数独38.外观数列39.组合总和40.组合总和41.缺失的第一个正数42.接雨水43.字符串相乘44.通配符匹配45.跳跃游戏 II46.全排列47.全排列 II48.旋转图像49.字母异位词分组50.Pow(x, n)51. N 皇后DFS52. N 皇后 IIDFS和 51 题完全一样只是不需要记录方案是什么53. 最大子数组和动态规划54. 螺旋矩阵55.跳跃游戏56. 区间合并模板区间合并57. 插入区间58. 最后一个单词的长度模拟题59. 螺旋矩阵 II方向数组的简单应用 1. 两数之和用哈希表减少查找的时间复杂度
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, 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_mapchar, 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(vectorint 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_mapint, 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}};vectorint 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_mapchar, int pri{{I, 1}, {V, 2}, {X, 3}, {L, 4}, \// {C, 5}, {D, 6}, {M, 7}}; /* 后记val表的功能可以替代pri故可以不用专门定义pri */unordered_mapchar, 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(vectorstring 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:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(), nums.end()); // sort是双指针算法和去重的前提vectorvectorint 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(vectorint nums, int target) {sort(nums.begin(), nums.end());pairint, 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_mapchar, string dict{{2, abc},{3, def},{4, ghi},{5, jkl},{6, mno},{7, pqrs},{8, tuv},{9, wxyz}};vectorstring res;vectorstring 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:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint 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) {stackchar 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;vectorstring res;vectorstring 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(vectorint 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(vectorint 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(vectorint 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;}
};
// 注这种实现方式可以应对以下两种边界情况
// 1nums为空
// 2nums仅含1个元素31. 下一个排列
class Solution {
public:void nextPermutation(vectorint 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;stackint 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(vectorint 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:vectorint searchRange(vectorint nums, int target) {vectorint 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(vectorint 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(vectorvectorchar 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(vectorvectorchar 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(vectorvectorchar 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:vectorint path;vectorvectorint res;vectorvectorint combinationSum(vectorint candidates, int target) {dfs(candidates, 0, target);return res; }void dfs(vectorint 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:vectorint path;vectorvectorint res;vectorvectorint combinationSum(vectorint candidates, int target) {dfs(candidates, 0, target);return res; }void dfs(vectorint 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:vectorint path;vectorvectorint res;vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());dfs(candidates, 0, target);return res; }void dfs(vectorint 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(vectorint 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(vectorint 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();vectorint 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);vectorint 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;vectorvectorbool f(n 1, vectorbool(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(vectorint nums) {int n nums.size();vectorint 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:vectorint path;vectorvectorint res;bool st[10];vectorvectorint permute(vectorint nums) {dfs(nums, 0);return res;}void dfs(vectorint 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:vectorint path;vectorvectorint res;bool st[10];vectorvectorint permuteUnique(vectorint nums) {vectorint tmp nums;sort(tmp.begin(), tmp.end());dfs(tmp, 0);return res;}void dfs(vectorint 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(vectorvectorint 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:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring map;for (auto str : strs){string tmp str;sort(tmp.begin(), tmp.end());map[tmp].push_back(str);}vectorvectorstring 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];vectorvectorstring res;vectorvectorstring solveNQueens(int n) {// 初始化棋盘vectorstring 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, vectorstring 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 皇后 IIDFS和 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(vectorint 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(vectorint 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:vectorint spiralOrder(vectorvectorint matrix) {vectorint res;int dx[] {0, 1, 0, -1}, dy[] {1, 0, -1, 0};int m matrix.size(), n matrix[0].size();vectorvectorbool st(m, vectorbool(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:vectorint res;vectorint spiralOrder(vectorvectorint 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(vectorvectorint 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(vectorint 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:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint 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:vectorvectorint insert(vectorvectorint intervals, vectorint 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;vectorvectorint 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:vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) {vectorvectorint 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:vectorvectorint generateMatrix(int n) {vectorvectorint res(n, vectorint(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;}
};
