51. N 皇后
![
对于n 皇后问题,对于n的遍历即为行遍历,所以需要另外对于列,两个对角线进行考虑
class Solution {
public:
vector<bool> col, dg, udg;
vector<vector<string>> ans;
vector<string> path;
vector<vector<string>> solveNQueens(int n) {
path = vector<string> (n,string(n,'.'));
col = vector<bool> (n);
dg = udg = vector<bool> (n * 2);
dfs(0,n);
return ans;
}
// 其中 k 表示第几行,x
void dfs(int k,int n){
if(k == n){
ans.push_back(path);
return;
}
// 对于一行检验其中某个位置是否合格,y
for(int i = 0 ; i < n; i++){
if(!col[i] && !dg[k - i + n] && !udg[k + i]){
col[i] = dg[k -i + n] = udg[k + i] = true;
path[i][k] = 'Q';
dfs(k + 1, n);
path[i][k] = '.';
col[i] = dg[k -i + n] = udg[k + i] = false;
}
}
}
};
52. N皇后 II
class Solution {
public:
vector<bool> col, dg, udg;
int totalNQueens(int n) {
col = vector<bool> (n);
dg = udg = vector<bool> (n * 2);
return dfs(0,n);
}
// 其中 k 表示第几行
int dfs(int k,int n){
int ans = 0;
if(k == n) return 1;
// 对于一行检验其中某个位置是否合格
for(int i = 0 ; i < n; i++){
if(!col[i] && !dg[k - i + n] && !udg[k + i]){
col[i] = dg[k -i + n] = udg[k + i] = true;
// 这里不需要进行记录 . 改为 Q,因为是记录个数
ans += dfs(k + 1, n);
col[i] = dg[k -i + n] = udg[k + i] = false;
}
}
return ans;
}
};
53. 最大子数组和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 这里的s是以前一个数结尾的字串的最大值
// 定义为INT_MIN是因为可能所有元素都是负数,输出最大的一个负数
int res = INT_MIN,s = 0;
for(auto num : nums){
// 如果之前的字串最大和为正数,那此时当然要加上
if(s > 0) s += num;
// 前面的都是负数,加上只会更小,直接舍弃,重置s=num
else s = num;
// 之前的最大值和现在的最大值取一个最大值
res = max(res,s);
}
return res;
}
};
54. 螺旋矩阵
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
int n = matrix.size();
if(!n) return ans;
int m = matrix[0].size();
vector<vector<bool>> st(n,vector<bool>(m));
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
for(int i = 0,d = 0,x = 0,y = 0 ; i < n * m; i ++ ){
ans.push_back(matrix[x][y]);
st[x][y] = true;
int a = x + dx[d],b = y + dy[d];
if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
d = (d + 1) % 4;
a = x + dx[d],b = y + dy[d];
}
x = a,y = b;
}
return ans;
}
};
类似走迷宫
55. 跳跃游戏
class Solution {
public:
bool canJump(vector<int>& nums) {
// j 表示从从上一个位置可以跳到的最后一个位置,如果最后小于nums.size(),必定跳不到,可以自己试试例子
for (int i = 0, j = 0; i < nums.size(); i ++ ) {
if (j < i) return false;
j = max(j, i + nums[i]);
}
return true;
}
};