Leetcode question brushing (XI) -- sequential questions brushing 51 to 55

51.N Queen

According to the rules of chess , The queen can attack the pieces on the same row, column or diagonal line .
n queens problem It's about how to make n A queen is placed in n×n On the chessboard , And keep the Queens from attacking each other .
Give you an integer n , Go back to all the different n queens problem Solutions for .
Each solution contains a different n queens problem The chess piece placement scheme of , The scenario ‘Q’ and ‘.’ They represent the queen and the vacant seat .
Example 1：

 Input ：n = 4
 Output ：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 explain ： As shown in the figure above ,4  There are two different solutions to the queen problem .

analysis ： Since you want to keep every line , Each column , Only one queen can exist in two slashes , You can create multiple identities bool Array , We can put queens in every row, so we Just create an identification array for each column and slash , For the column identification array, it is still very simple , And how to identify the slash identification array ？ Look at the picture below :

Code ：

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);// Yes x+y So the maximum will not exceed 2*n
        dfs(0);// The first 0 Line start search 
        return res;
    }

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

        // Enumerate each column 
        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);
                // Restore the scene 
                col[i] = dg[u - i + nt] = udg[u + i] = false;
                path[u][i]='.';
            }
        }
        return;
    }
};

---

52.N Queen II

n queens problem It's about how to make n A queen is placed in n × n On the chessboard , And keep the Queens from attacking each other . Give you an integer n , return n queens problem Number of different solutions .
Example 1：

 Input ：n = 4
 Output ：2
 explain ： As shown in the figure above ,4  There are two different solutions to the queen problem .

analysis ： The idea of this question is the same, but the required thing is the number of schemes , You can use the code above to return size Can , You can also use the following code .
Code ：

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);
                // Restore the scene 
                st[i] = udg[u - i + nt] = dg[u + i] = false;

            }
        }
        return res;
    }

};

---

53. Maximum subarray and

Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and . Subarray Is a continuous part of the array .
Example 1：

 Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
 Output ：6
 explain ： Continuous subarray  [4,-1,2,1]  And the biggest , by  6 .

analysis ： This problem can be solved by dynamic programming, and the time complexity can be O(n)、 The space complexity is O(1), The analysis idea is shown in the figure below :

Code ：

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. Spiral matrix

To give you one m That's ok n Columns of the matrix matrix , Please follow Clockwise spiral sequence , Returns all elements in the matrix .
Example 1：

 Input ：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 Output ：[1,2,3,6,9,8,7,4,5]

analysis : When moving clockwise, the current (x,y) For mobile , We can set two offset arrays according to this to move , When moving, judge whether it is out of bounds or whether the element has been traversed , Here's the picture ：
Code ：

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));// Whether the status array has been traversed 
        // Offset array 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. Jumping game

Given an array of nonnegative integers nums , You're in the beginning of the array The first subscript . Each element in the array represents the maximum length you can jump at that location . Judge whether you can reach the last subscript .
Example 1：

 Input ：nums = [2,3,1,1,4]
 Output ：true
 explain ： You can jump first  1  Step , From the subscript  0  Reach subscript  1,  And then from the subscript  1  jump  3  Step to the last subscript .

analysis ： Through analysis , If we can jump to the k Then you can jump to k-1 This point , And so on , You can find that if you can jump to i This point , Then you can jump to 0—k-1, Similarly, if even 0—k-1 If you can't get there, you must not get there k A little bit .

Code ：

class Solution {
    
public:
    bool canJump(vector<int>& nums) {
    
        for(int i = 0, j = 0; i < nums.size(); i++)
        {
    
            if (j < i) return false;// Explain that you can't reach the i A little bit 
            j = max(j , i + nums[i]);// take j And i+nums[i] Compare 
        }
        return true;// Reach the last point , Description successful arrival 
    }
};