LeetCode刷题(十一)——顺序刷题51至55

51.N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

分析：既然要保持每行，每列，两条斜线仅仅只能存在一个皇后，可以创建多个标识bool数组，我们可以每行每行地放皇后所以我们只需要创建每列和斜线的标识数组，对于列标识数组还是很简单的，而斜线的标识数组要如何标识呢？看下图:

代码：

class Solution {
    
public:
    vector<vector<string>>res;
    vector<bool>col,dg,udg;
    vector<string>path;
    int nt;
    vector<vector<string>> solveNQueens(int n) {
    
        nt = n;
        path = vector<string>(n,string(n,'.'));
        col = dg = udg =vector<bool>( n * 2);//有x+y所以最大也不会超过2*n
        dfs(0);//第0行开始搜索
        return res;
    }

    void dfs(int u)
    {
    
        if(u == nt)
        {
    
            res.push_back(path);
            return;
        }

        //枚举每一列
        for(int i = 0; i < nt; i++)
        {
    
            if(!col[i] && !dg[u - i + nt] && !udg[u + i])
            {
    
                col[i] = dg[u - i + nt] = udg[u + i]=true;
                path[u][i]='Q';
                dfs(u + 1);
                //恢复现场
                col[i] = dg[u - i + nt] = udg[u + i] = false;
                path[u][i]='.';
            }
        }
        return;
    }
};

---

52.N皇后 II

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

分析：这题的思路是一样的只是要求的东西是方案数量，可以用上题代码返回size就可以，也可以用下面的代码实现。
代码：

class Solution {
    
public:
    int nt;
    vector<string>path;
    vector<bool>st,udg,dg;
    int totalNQueens(int n) {
    
        nt = n;
        path = vector<string> (nt,string( n , '.' ));
        st = vector<bool> (n);
        udg = dg = vector<bool>(n*2);
        return dfs(0);
    }

    int dfs(int u)
    {
    
        if(u == nt) return 1;
        int res = 0;
        for(int i = 0; i < nt; i++)
        {
    
            if(!st[i] && !udg[u - i + nt] && !dg[u + i])
            {
       
                st[i] = udg[u - i + nt] = dg[u + i] = true;
                res += dfs(u + 1);
                //恢复现场
                st[i] = udg[u - i + nt] = dg[u + i] = false;

            }
        }
        return res;
    }

};

---

53.最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

分析：这一题可以使用动态规划来做可以做到时间复杂度为O(n)、空间复杂度为O(1)，分析思路如下图:

代码：

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;
    }
};

---

54.螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

分析:当进行顺时针移动时会对当前的(x,y)进行移动，我们可以按照这个来设置两个偏移数组来进行移动，在移动时判断是否越界或者是元素已经遍历过，如下图：
代码：

class Solution {
    
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
    
        int n = matrix.size();
        int m = matrix[0].size();
        vector<int>res;
        if(!matrix.size())return res;
        vector<vector<bool>>st(n , vector<bool>(m));//是否已经遍历过状态数组
        //偏移数组dx,dy
        int dx[] = {
    0 , 1 , 0 , -1};
        int dy[] = {
    1 , 0 , -1 , 0};
        int a , b;
        for(int i = 0 , x = 0 , y = 0, d = 0; i < n * m; i++)
        {
    
            res.push_back(matrix[x][y]);
            st[x][y] = true;
            a = dx[d] + x ,b = dy[d] + y;
            if(a>=n||a<0||b>=m||b<0||st[a][b])
            {
    
                d = (d+1)%4;
                a = dx[d] + x ,b = dy[d] + y;
            }
            x = a , y = b;
        }
        return res;
    }
};

---

55.跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
示例1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

分析：通过分析，假如我们可以跳跃到第k个点那么就一定可以跳跃到k-1这个点，以此类推，可以发现如果可以跳到i这个点，那么就可以跳到0—k-1，同样的如果连0—k-1都到不了那么一定到不了第k个点。

代码：

class Solution {
    
public:
    bool canJump(vector<int>& nums) {
    
        for(int i = 0, j = 0; i < nums.size(); i++)
        {
    
            if (j < i) return false;//说明到不了第i个点
            j = max(j , i + nums[i]);//将j与i+nums[i]进行比较
        }
        return true;//到达最后那个点，说明成功到达
    }
};