LeetCode Weekly Contest 165

LeetCode Weekly Contest 165.

问题 1

题目链接

判断每行、每列、两条对角线的字符是否相同，棋盘状态始终有效，不需要考虑 corner case。

问题 2

题目链接

鸡兔同笼问题，数学题。

问题 3

题目链接

这道题比赛的时候没做出来，结束后发现想复杂了，进阶题是求所有元素是 1 的子矩阵(不要求方阵)。

解法：DP，根据左、上、左上三者最小值更新当前值，参考 LC 221。

复杂度：时间复杂度 O(n^2)，空间复杂度 O(n^2)，可优化为 O(n)。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def countSquares(self, A: List[List[int]]) -> int:
        m, n = len(A), len(A[0])

        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

        res = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if A[i-1][j-1] == 1:
                   dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + A[i-1][j-1]
                   res += dp[i][j]

        return res

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();

        vector<vector <int>> dp(m+1, vector<int>(n+1, 0));
        int res = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    dp[i+1][j+1] = min(dp[i][j+1], min(dp[i+1][j], dp[i][j])) + 1;
                    res += dp[i+1][j+1];
                }
            }
        }

        return res;
    }
};

问题 4

题目链接
解法：DP。
复杂度：时间复杂度 O(kn^2)，空间复杂度 O(kn)。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        memo = {}

        def cost(s, i, j):
            r = 0
            while i < j:
                if s[i] != s[j]:
                    r += 1
                i += 1
                j -= 1
            return r

        def dfs(i, k):
            if (i, k) in memo: 
                return memo[(i, k)]
            if n - i == k:
                return 0
            if k == 1:
                return cost(s, i, n - 1)
            res = float('inf')
            for j in range(i + 1, n - k + 2):
                res = min(res, cost(s, i, j - 1) + dfs(j, k - 1))
            memo[(i, k)] = res
            return res

        return dfs(0 , k)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int palindromePartition(string s, int k) {
        int n = s.size();
        vector<vector <int>> memo(n+1, vector<int>(k+1, -1));

        return dfs(s, n, 0, k, memo); 
    }

    int cost(string& s, int i, int j) {
        int res = 0;
        while (i < j) {
            if (s[i] != s[j]) {
                res++;
            }
            i++;
            j--;
        }
        return res;
    }


    int dfs(string& s, int n, int i, int k, vector<vector <int>>& dp) {
        if (dp[i][k] != -1) return dp[i][k];

        if (n - i == k) return 0;

        if (k == 1) return cost(s, i, n - 1);

        int res = INT_MAX;
        for (int j = i + 1; j < n-k+2; j++) {
            res = min(res, cost(s, i, j - 1) + dfs(s, n, j, k - 1, dp));
        }

        dp[i][k] = res;
        return res;
    }
};

留言

2019-12-01
▲