《LeetCode 顺序刷题》51 - 60

51、[困难] N 皇后位运算哈希表class Solution { private: bool checkCol[10], checkDig1[20], checkDig2[20]; vectorvectorstring ret; vectorstring path; int num; void dfs(int row) { if (row num) { ret.push_back(path); return; } for (int col 0; col num; col) { // 剪枝 if (!checkCol[col] !checkDig1[row - col num] !checkDig2[row col]) { path[row][col] Q; checkCol[col] checkDig1[row - col num] checkDig2[row col] true; dfs(row 1); path[row][col] .; checkCol[col] checkDig1[row - col num] checkDig2[row col] false; } } } public: vectorvectorstring solveNQueens(int n) { num n; path.resize(num); for (int i 0; i num; i) { path[i].append(num, .); } dfs(0); return ret; } };class Solution { private: bool isValid(vectorpairint, int solution, int row, int col) { // 保证和每个皇后的位置都不冲突 for (pairint, int position : solution) { // 不在同一列, 以及不在同一斜线 if (position.second col || (position.first position.second row col) || (position.first - position.second row - col)) { return false; } } return true; } void dfs(vectorvectorpairint, int solutions, vectorpairint, int solution, int row, int n) { // 当每一行的位置都确定之后, 保存方案 if (row n) { solutions.push_back(solution); return; } // 遍历每一列可能的位置 for (int i 0; i n; i) { if (isValid(solution, row, i)) { // 保存当前的皇后位置 solution.push_back(make_pair(row, i)); // 确认下一行皇后的位置 dfs(solutions, solution, row 1, n); // 回溯 solution.pop_back(); } } } vectorvectorstring trans(vectorvectorpairint, int solutions, int n) { vectorvectorstring ret; // 转换每一个方案 for (vectorpairint, int solution : solutions) { vectorstring str(n, string(n, .)); for (pairint, int pos : solution) { // 皇后的位置赋值为 Q str[pos.first][pos.second] Q; } // 转换好一种方案 ret.push_back(str); } return ret; } public: vectorvectorstring solveNQueens(int n) { // 所有的解决方案 vectorvectorpairint, int solutions; // 一种解决方案 vectorpairint, int solution; dfs(solutions, solution, 0, n); return trans(solutions, n); } };52、[困难] N 皇后 Ⅱ位运算哈希表class Solution { public: int totalNQueens(int n) { vectorbool checkCol(10, false), checkDig1(20, false), checkDig2(20, false); int ret 0; dfs(checkCol, checkDig1, checkDig2, ret, n, 0); return ret; } void dfs(vectorbool checkCol, vectorbool checkDig1, vectorbool checkDig2, int ret, int n, int row) { if (n row) { ret; return; } for (int col 0; col n; col) { // 剪枝 if (!checkCol[col] !checkDig1[row - col n] !checkDig2[row col]) { checkCol[col] checkDig1[row - col n] checkDig2[row col] true; dfs(checkCol, checkDig1, checkDig2, ret, n, row 1); checkCol[col] checkDig1[row - col n] checkDig2[row col] false; } } } };class Solution { private: bool isValid(vectorpairint, int solution, int row, int col) { // 保证和每个皇后的位置都不冲突 for (pairint, int position : solution) { // 不在同一列, 以及不在同一斜线 if (position.second col || (position.first position.second row col) || (position.first - position.second row - col)) { return false; } } return true; } void dfs(int ret, vectorpairint, int solution, int row, int n) { // 当每一行的位置都确定之后, 保存方案 if (row n) { ret; return; } // 遍历每一列可能的位置 for (int i 0; i n; i) { if (isValid(solution, row, i)) { // 保存当前的皇后的位置 solution.push_back(make_pair(row, i)); // 确认下一行皇后的位置 dfs(ret, solution, row 1, n); // 回溯 solution.pop_back(); } } } public: int totalNQueens(int n) { int ret 0; vectorpairint, int solution; dfs(ret, solution, 0, n); return ret; } };53、[中等] 最大子数组和线段树动态规划class Solution { public: int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n 1); int ret INT_MIN; for (int i 1; i n; i) { dp[i] max(nums[i - 1], dp[i - 1] nums[i - 1]); ret max(ret, dp[i]); } return ret; } };class Solution { public: int maxSubArray(vectorint nums) { int ret INT_MIN, curSum 0; for (const auto num : nums) { curSum curSum 0 ? curSum num : num; ret max(ret, curSum); } return ret; } };54、[中等] 螺旋矩阵数组class Solution { public: vectorint spiralOrder(vectorvectorint matrix) { vectorint ret; if (matrix.empty()) { return ret; } int upper 0, down matrix.size() - 1; int left 0, right matrix[0].size() - 1; while (true) { for (int i left; i right; i) // 向右移动直到最右 { ret.push_back(matrix[upper][i]); } if (upper down) // 重新设定上边界若上边界大于下边界则遍历遍历完成下同 { break; } for (int i upper; i down; i) // 向下 { ret.push_back(matrix[i][right]); } if (--right left) { break; } for (int i right; i left; i--) // 向右 { ret.push_back(matrix[down][i]); } if (--down upper) { break; } for (int i down; i upper; i--) // 向上 { ret.push_back(matrix[i][left]); } if (left right) { break; } } return ret; } };55、[中等] 跳跃游戏贪心class Solution { public: bool canJump(vectorint nums) { int maxpos 0; int n nums.size() - 1; for (int i 0; i n; i) { // 判断是否可以到达当前位置 if (maxpos i) { maxpos max(maxpos, i nums[i]); // 判断最远的位置是否包含最后一个位置 if (maxpos n) { return true; } } else { return false; } } return false; } };56、[中等] 合并区间排序数组class Solution { public: vectorvectorint merge(vectorvectorint intervals) { int m intervals.size(); if (m 0) return {}; sort(intervals.begin(), intervals.end()); vectorvectorint ret; for (int i 0; i m; i) { int left intervals[i][0], right intervals[i][1]; if (!ret.size() || ret.back()[1] left) { ret.push_back({left, right}); } else { ret.back()[1] max(ret.back()[1], right); } } return ret; } };57、[中等] 插入区间数组class Solution { public: vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) { int left newInterval[0]; int right newInterval[1]; bool placed false; vectorvectorint ret; for (const auto interval : intervals) { if (interval[0] right) { // 在插入区间的右侧且无交集 if (!placed) { ret.push_back({left, right}); placed true; } ret.push_back(interval); } else if (interval[1] left) { // 在插入区间的左侧且无交集 ret.push_back(interval); } else { // 与插入区间有交集计算它们的并集 left min(left, interval[0]); right max(right, interval[1]); } } if (!placed) { ret.push_back({left, right}); } return ret; } };58、[简单] 最后一个单词的长度字符串class Solution { public: int lengthOfLastWord(string s) { int index s.size() - 1; while (s[index] ) { index--; } int wordLength 0; while (index 0 s[index] ! ) { wordLength; index--; } return wordLength; } };59、[中等] 螺旋矩阵 Ⅱ数组class Solution { public: vectorvectorint generateMatrix(int n) { vectorvectorint ret(n, vectorint(n)); int left 0, right n - 1; int upper 0, down n - 1; int index 1; while (true) { // 向右 for (int i left; i right; i) { ret[upper][i] index; } if (upper down) { break; } // 向下 for (int i upper; i down; i) { ret[i][right] index; } if (--right left) { break; } // 向左 for (int i right; i left; i--) { ret[down][i] index; } if (--down upper) { break; } // 向上 for (int i down; i upper; i--) { ret[i][left] index; } if (left right) { break; } } return ret; } };