LeetCode Week 6:第 51 ~ 55 题

时间:2020-9-17 作者:admin

专栏——LeetCode

文章目录

51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
LeetCode Week 6:第 51 ~ 55 题
上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

输入:4
输出:[
[“.Q…”, // 解法 1
“…Q”,
“Q…”,
“…Q.”],
[“…Q.”, // 解法 2
“Q…”,
“…Q”,
“.Q…”]
]
解释: 4 皇后问题存在两个不同的解法。

提示:

皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。

题解:
(暴力搜索) O(n!)
暴力搜索所有方案。
为了优化时间效率,定义 vectorrow, col, diag, anti_diag;,用来记录每一行、每一列、每条对角线上是否有皇后存在。
搜索时需要记录4个状态:x,y,s,nx,y,s,n,分别表示横纵坐标、已摆放的皇后个数、棋盘大小。
对于每步搜索,有两种选择:
当前格子不放皇后,则转移到 dfs(x, y + 1, s, n);
如果 (x,y)(x,y) 所在的行、列、对角线不存在皇后,则当前格子可以摆放皇后,更新row, col, diag,anti_diag后
转移到 dfs(x, y + 1, s + 1, n);,回溯时不要忘记恢复row, col, diag, anti_diag等状态。

c++版

class Solution {
public:
    vector<string> path;
    vector<vector<string>> ans;
    vector<bool> row, col, d, fd;
    vector<vector<string>> solveNQueens(int n) {
        path = vector<string> (n, string(n, '.'));
        row = col = vector<bool> (n, false); 
        d = fd = vector<bool> (2*n, false);
        dfs(0, 0, 0, n);
        return ans;
    }
    void dfs(int x, int y, int s, int n){
        if(y == n)x++, y = 0;
        if(x == n){
            if(s == n)
                ans.push_back(path);
            return ;
        }
        dfs(x, y + 1, s, n);
        if(!row[x] && !col[y] && !d[x + y] && !fd[n - 1 - x + y]){
            row[x] = col[y] = d[x + y] = fd[n - 1 - x + y] = true;
            path[x][y] = 'Q';
            dfs(x, y + 1, s + 1, n);
            path[x][y] = '.';
            row[x] = col[y] = d[x + y] = fd[n - 1 - x + y] = false;
        }
    }
};

python版

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        row = [False] * n
        col = [False] * n
        d = [False] * 2 * n
        fd = [False] * 2 * n
        ans = []
        path = []
        path = [['.' for _ in range(n)] for _ in range(n)]

        def dfs(x, y, s, n):
            if y == n:
                x += 1
                y = 0
            if x == n:
                if(s == n):
                    l = []
                    for i in path:
                        l.append(''.join(i))
                    ans.append(l)
                return 
            dfs(x, y + 1, s, n)
            if not row[x] and not col[y] and not d[x + y] and not fd[n - 1 - x + y]:
                row[x] = True
                col[y] = True
                d[x + y] = True
                fd[n - 1 - x + y] = True
                path[x][y] = 'Q'
                dfs(x, y + 1, s + 1, n)
                row[x] = False
                col[y] = False
                d[x + y] = False
                fd[n - 1 - x + y] = False
                path[x][y] = '.'
        dfs(0, 0, 0, n)
        return ans

52. N皇后 II

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

LeetCode Week 6:第 51 ~ 55 题
上图为 8 皇后问题的一种解法。

给定一个整数 n,返回 n 皇后不同的解决方案的数量。

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[“.Q…”, // 解法 1
“…Q”,
“Q…”,
“…Q.”],
[“…Q.”, // 解法 2
“Q…”,
“…Q”,
“.Q…”]
]

提示:

皇后,是国际象棋中的棋子,意味着国王的妻子。皇后只做一件事,那就是“吃子”。当她遇见可以吃的棋子时,就迅速冲上去吃掉棋子。当然,她横、竖、斜都可走一或 N-1 步,可进可退。(引用自 百度百科 – 皇后 )

题解:
此题解法和上一题 完全相同。只是将记录方案,改成记录方案数。

c++版

class Solution {
public:
    int ans = 0;
    vector<bool> row, col, d, fd;
    int totalNQueens(int n) {
        row = col = vector<bool> (n, false); 
        d = fd = vector<bool> (2*n, false);
        dfs(0, 0, 0, n);
        return ans;
    }
    void dfs(int x, int y, int s, int n){
        if(y == n)x++, y = 0;
        if(x == n){
            if(s == n)
                ans ++;
            return ;
        }
        dfs(x, y + 1, s, n);
        if(!row[x] && !col[y] && !d[x + y] && !fd[n - 1 - x + y]){
            row[x] = col[y] = d[x + y] = fd[n - 1 - x + y] = true;
            dfs(x, y + 1, s + 1, n);
            row[x] = col[y] = d[x + y] = fd[n - 1 - x + y] = false;
        }
    }
};

python版

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.ans = 0
        row = [False] * n
        col = [False] * n
        d = [False] * 2 * n
        fd = [False] * 2 * n
        def dfs(x, y, s, n):
            if y == n:
                x += 1
                y = 0
            if x == n:
                if(s == n):
                    self.ans += 1
                return 
            dfs(x, y + 1, s, n)
            if not row[x] and not col[y] and not d[x + y] and not fd[n - 1 - x + y]:
                row[x] = True
                col[y] = True
                d[x + y] = True
                fd[n - 1 - x + y] = True
                dfs(x, y + 1, s + 1, n)
                row[x] = False
                col[y] = False
                d[x + y] = False
                fd[n - 1 - x + y] = False
        dfs(0, 0, 0, n)
        return self.ans

53. 最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

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

题解:
动态规划 O(n)
1.设 f(i) 表示以第 i 个数字为结尾的最大连续子序列的 总和 是多少。
2.初始化 f(0)=nums[0]。
3.转移方程 f(i)=max(f(i−1)+nums[i],nums[i])。可以理解为当前有两种决策,一种是将第 i 个数字和前边的数字拼接起来;
另一种是第 i 个数字单独作为一个新的子序列的开始。
4.最终答案为 ans=max(f(k)),0≤k<n。

c++版

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int n = nums.size();
        vector<int> f(n);
        f[0] = nums[0];
        for(int i = 1; i < n; i++){
            f[i] = max(f[i - 1] + nums[i], nums[i]);
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

python版

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        f = [0 for _ in range(n)]
        ans = nums[0]
        f[0] = nums[0]
        for i in range(1, n):
            f[i] = max(f[i - 1] + nums[i], nums[i])
            ans = max(ans, f[i])
        return ans

54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

题解:
(模拟) O(nm)
定义四个方向的常数方向数组 dir,不妨假设 0 表示方向为向右,1 为向下,2 为向左,3 为向上。
定义二维数组 vis,代表该位置是否被访问过。
从坐标 (0, 0) 开始,初始方向为 0。
每次遍历后枚举下一个可行的方向是哪个,可行是指下一个位置没有被访问过。如果四个方向都不可行,则遍历结束。

c++版

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();
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};
        vector<vector<bool>> vis(n, vector<bool>(m));
        for(int i = 0, x = 0, y = 0, d = 0; i < m * n; i++){
            ans.push_back(matrix[x][y]);
            vis[x][y] = true;
            int a = x + dx[d];
            int b = y + dy[d];
            if(a < 0 || a >= n || b < 0 || b >= m || vis[a][b]){        
                d++;
                d %= 4;
                a = x + dx[d];
                b = y + dy[d];
            }
            x = a;
            y = b;
        }
        return ans;
    }
};

python版

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ans = []
        n = len(matrix)
        if not n:
            return ans
        m = len(matrix[0])
        vis = [[False for _ in range(m)] for _ in range(n)]
        x = 0
        y = 0
        d = 0
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        for i in range(n*m):
            ans.append(matrix[x][y])
            vis[x][y] = True
            a = x + dx[d]
            b = y + dy[d]
            if a < 0 or a >= n or b < 0 or b >= m or vis[a][b]:
                d += 1
                d %= 4
                a = x + dx[d]
                b = y + dy[d]
            x = a
            y = b
        return ans

55. 跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

c++版

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int last = 0;
        for(int i = 1; i < n; i++){
            while(last < i && i > last + nums[last])
                last++;
            if(last == i) return false;
        }
        return true;
    }
};

python版

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        last = 0
        for i in range(1, n):
            while last < i and i > last + nums[last]:
                last += 1
            if last == i:
                return False
        return True
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。