讨论/题目交流/ 🏆 第 165 场力扣周赛/
🏆 第 165 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 找出井字棋的获胜者
4 分 - 不浪费原料的汉堡制作方案
5 分 - 统计全为 1 的正方形子矩阵
6 分 - 分割回文串 III

展开讨论

第一题:

枚举随便搞搞都行

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        allpath = [
            [[0,0],[0,1],[0,2]],
            [[1,0],[1,1],[1,2]],
            [[2,0],[2,1],[2,2]],
            [[0,0],[1,0],[2,0]],
            [[0,1],[1,1],[2,1]],
            [[0,2],[1,2],[2,2]],
            [[0,0],[1,1],[2,2]],
            [[2,0],[1,1],[0,2]]
        ]
        def test(a):
            for line in allpath:
                if len(list(filter(lambda path: path in a, line))) == 3:
                    return True
            return False

        if test(moves[0::2]):
            return "A"
        elif test(moves[1::2]):
            return "B"
        elif len(moves) == 9:
            return "Draw"
        else:
            return "Pending"

第二题:

做x个巨无霸汉堡,y个小皇堡,则有方程组

4x+2y=tomato4x+2y=tomato
x+y=cheesex+y=cheese

整理一下就变成了了

x=tomato2cheese2x=\frac{tomato - 2 * cheese}{2}

求出x和y之后,判断一下x和y是否为整数,是否为负数即可

class Solution:
    def numOfBurgers(self, tomatoSlices: int, cheeseSlices: int) -> List[int]:
        if (tomatoSlices - 2 * cheeseSlices) % 2 != 0:
            return []
        x = (tomatoSlices - 2 * cheeseSlices) // 2
        y = cheeseSlices - x
        if x >= 0 and y >= 0:
            return [x, y]
        else:
            return []

第三题:

只需要枚举所有的正方形即可,问题就转变成如何判断以(i,j)为左上角,长度为k的正方形是否全为1,再转变一下,就是求这个正方形里面的元素和是否等于kkk*k

于是我们可以用前缀和来解决这个问题

prefix[i][j] = matrix[i][j] + prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1]

sum(i, j, k) = prefix[i + k][j + k] - prefix[i + k][j - 1] - prefix[i - 1][j + k] + prefix[i - 1][j - 1]

复杂度是o(n3)o(n^3)

另外,狗哥@jiangyanerpang,提醒了,可以用o(n2)o(n^2)来解决这个问题

用dp[i][j]表示以(i,j)为右下角,全为1的最大的正方形长度,可以用o(1)来解决转移问题

代码请狗哥来补充

o(n3)o(n^3)的版本

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        prefix = [[0] * (m + 1) for _ in range(0, n + 1)]
        for i in range(0, n):
            for j in range(0, m):
                prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + matrix[i][j]
        ret = 0
        for i in range(0, n):
            for j in range(0, m):
                k = 1
                while i + k < n + 1 and j + k < m + 1:
                    if prefix[i + k][j + k] - prefix[i + k][j] - prefix[i][j + k] + prefix[i][j] == k * k:
                        ret += 1
                        k += 1
                    else:
                        break
        return ret

o(n2)o(n^2)的版本

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        dp = [[0] * m for _ in range(0, n)]
        ret = 0
        for i in range(0, n):
            for j in range(0, m):
                if matrix[i][j] == 0:
                    continue
                dp[i][j] = 1
                if i == 0 or j == 0:
                    ret += dp[i][j]
                    continue
                sub = min(dp[i - 1][j], dp[i][j - 1])
                if sub != 0:
                    if matrix[i - sub][j - sub] == 1:
                        dp[i][j] = sub + 1
                    else:
                        dp[i][j] = sub
                ret += dp[i][j]
        return ret

第四题:

令dp[i][j]表示字符串s[0:j](就是字符串s的前j+1个字符),切割i次的最小代价(最小修改的字符数)

如果最后一个切割出来的字符串,切割在第k个位置,也就是s[k,j]

那么s[k,j]的最小代价我们是可以求出来的是吧?只需要根据回文的定义,判断左半边跟右半边有多少个字符不相等

剩下的字符串s[0,k-1]需要切割成i-1个字符串,最小代价是dp[i-1][k]

于是切割在第k个位置时,最小代价是dp[i-1][k]+change(s[k,j])

我们可以得到转移方程dp[i][j]=min(dp[i1][k]+change(s[k+1:j])),k[0,j1]dp[i][j]=min(dp[i-1][k] + change(s[k+1:j])),k\in [0,j-1]

由于change(s[k+1:j])跟i无关,我们可以调整一下dp的顺序,先枚举j,再枚举k,这样枚举i的过程中change(s[k+1:j])只需要算一次

复杂度是o(n3)o(n^3),如果没有调整dp的顺序,复杂度是o(n4)o(n^4)

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def change(left, right):
            ret = 0
            while left < right:
                if s[left] != s[right]:
                    ret += 1
                left += 1
                right -= 1
            return ret
        
        dp = [[-1] * (len(s) + 1) for _ in range(0, k + 1)]
        dp[0][0] = 0
        for j in range(1, len(s) + 1):
            p = j - 1
            while p >= 0:
                a = change(p, j - 1)
                for i in range(1, k + 1):
                    if dp[i - 1][p] == -1:
                        continue
                    sub = dp[i - 1][p] + a
                    if dp[i][j] == -1:
                        dp[i][j] = sub
                    else:
                        dp[i][j] = min(dp[i][j], sub)
                p -= 1
                        
        return dp[k][len(s)]

应大家的要求,放个c++版本。。。

class Solution {
public:
    int change(string &s, int left, int right) {
        int ret = 0;
        while (left < right) {
            if (s[left++] != s[right--]) {
                ret++;
            }
        }
        return ret;
    }
    int palindromePartition(string s, int k) {
        vector<vector<int>> dp = vector<vector<int>>(k + 1, vector<int>(s.size() + 1, -1));
        dp[0][0] = 0;
        for (int j = 1;j <= s.size();j++) {
            for (int p = 0;p < j;p++) {
                int cache = change(s, p, j - 1);
                for (int i = 1;i <= k;i++) {
                    if (dp[i - 1][p] == -1) {
                        continue;
                    }
                    int sub = dp[i - 1][p] + cache;
                    if (dp[i][j] == -1) {
                        dp[i][j] = sub;
                    } else {
                        dp[i][j] = min(dp[i][j], sub);
                    }
                }
            }
        }
        return dp[k][s.size()];
    }
};
16
展开全部 11 讨论