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

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

image.png

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

展开讨论
共 11 个讨论

第一题:

枚举随便搞搞都行

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
  • 找出井字棋的获胜者
    首先模拟走的情况,得到最终的棋盘局面,然后模拟判断谁赢或者draw以及pending就可以了。时间复杂度 O(n2)O(n^2),当然 n=3n=3
class Solution(object):
    def tictactoe(self, moves):
        """
        :type moves: List[List[int]]
        :rtype: str
        """
        def check_win(grid):
            for i in range(3):
                if grid[i][0] == grid[i][1] and grid[i][0] == grid[i][2]:
                    if grid[i][0] != 0:
                        return grid[i][0]
                    
            for i in range(3):
                if grid[0][i] == grid[1][i] and grid[0][i] == grid[2][i]:
                    if grid[0][i] != 0:
                        return grid[0][i]
            
            if grid[0][0] == grid[1][1] and grid[0][0] == grid[2][2]:
                if grid[0][0] != 0:
                    return grid[0][0]
                
            if grid[2][0] == grid[1][1] and grid[2][0] == grid[0][2]:
                if grid[2][0] != 0:
                    return grid[2][0]
            return None
        import numpy as np
        grid = np.zeros((3,3),dtype=np.int)
        cnt = 1
        for x,y in moves:
            grid[x,y] = cnt
            cnt = 3 - cnt
        res = check_win(grid)
        if not res is None:
            return chr(ord('A')+res-1)
        if len(moves) == 9: return 'Draw'
        return 'Pending'
  • 不浪费原料的汉堡制作方案
    这道题有两种思路,第一种思路是贪心,我们先假设全部做小汉堡,这样会导致两种情况:

    1. 番茄不够:无解
    2. 番茄剩余:由于大汉堡只比小汉堡多2个番茄,所以我们可以对每个小汉堡加上两个番茄变成大汉堡。

    对于第二种情况,还需要判断番茄奇偶数量以及是不是全做大汉堡都有多余等无解情况。

    而第二种思路更简单,我们可以直接列一个二元一次方程组,直接求解数量,然后判断数量是不是正整数来判断无解就可以了。

class Solution(object):
    def numOfBurgers(self, tomatoSlices, cheeseSlices):
        """
        :type tomatoSlices: int
        :type cheeseSlices: int
        :rtype: List[int]
        """
        if tomatoSlices == 0 and cheeseSlices == 0:
            return [0,0]
        if tomatoSlices == 0 or cheeseSlices == 0:
            return []
        tomatoSlices -= cheeseSlices * 2
        if tomatoSlices < 0 or tomatoSlices % 2 != 0:
            return []
        
        if tomatoSlices > cheeseSlices * 2:
            return []
        return [tomatoSlices/2, cheeseSlices-tomatoSlices/2]
  • 统计全为 1 的正方形子矩阵

  • 首先预处理出每行每列从第0个格子到第i个格子的和,这样我们可以在 O(1)O(1) 的时间内判断该行或者列某一部分是否全为1,这是非常常见的预处理技巧。

    然后我们暴力正方形起点和边长判断就可以了。如果我们已知(i,i)到(i+k,j+k)为全1正方形,那么我们要判断(i,i)到(i+k+1,i+k+1)的时候,只需要判断(i+k+1,i..i+k+1)以及(i..i+k+1,i+k+1)是否全为1就可以了,可以用上述的预处理结果快速计算出来。时间复杂度 O(n3)O(n^3)

class Solution(object):
    def countSquares(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        import numpy as np
        row_sum = np.cumsum(matrix,axis=0)
        col_sum = np.cumsum(matrix,axis=1)
        n = len(matrix)
        m = len(matrix[0])
        def get_row_sum(i, ti, tj):
            if i == 0:
                return row_sum[ti,tj]
            else:
                return row_sum[ti,tj] - row_sum[i-1,tj]
        def get_col_sum(j, tj, ti):
            if j == 0:
                return col_sum[ti,tj]
            else:
                return col_sum[ti,tj] - col_sum[ti,j-1]
        def get_ans(i,j):
                
            ans = 0
            ti = i; tj = j
            if matrix[ti][tj] == 1: ans += 1
            else: return ans
            
            ti += 1
            tj += 1
            while ti < n and tj < m:
                if not get_row_sum(i, ti, tj) == ti - i + 1:
                    break
                if not get_col_sum(j, tj, ti) == tj - j + 1:
                    break
                ans += 1
                ti += 1; tj += 1
            return ans
        ans = 0
        for i in range(n):
            for j in range(m):
                ans += get_ans(i,j)
        return ans

  • 分割回文串 III

  • DP,首先暴力计算把 [i..j][i..j] 变成回文串的最小代价,计算方式也很简单,直接看第一个和最后一个,第二个和倒数第二个...是否一样,不一样则代价加1。

    有了预处理数组 cost 以后,令状态为 dp[i][j]dp[i][j] 表示把前 ii 个字符变为 jj 个回文串的最小代价,那么 dp[i][j]=min(dp[x][j1]+cost[x+1,i]),x[0..i1]dp[i][j] = min(dp[x][j-1] + cost[x+1,i]), x∈[0..i-1]

    最后结果为 dp[n1][k]dp[n-1][k] 即把前n个字符变为k段的最小代价。时间复杂度为 O(n3)O(n^3)

class Solution(object):
    def palindromePartition(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        import numpy as np
        def get_cost(s):
            n = len(s)
            cost = 0
            for i in range(n//2):
                if s[i] != s[n-i-1]:
                    cost += 1
            return cost
        n = len(s)
        cost = np.ones((n,n),dtype=np.int)*1000
        for i in range(n):
            for j in range(i,n):
                cost[i,j] = get_cost(s[i:j+1])
        #print(cost)
        dp = np.ones((n, k+3),dtype=np.int)*1000
        dp[0][1] = 0
        for i in range(1,n):
            dp[i][1] = cost[0,i]
            for mk in range(2,min(k+1,i+2)):
                for j in range(i):
                    dp[i][mk] = min(dp[i][mk], dp[j][mk-1] + cost[j+1,i])
        #print(dp)
        return dp[n-1][k]
9

IMG_20191201_105726.jpg

官方制裁(手动滑稽)

提交第二题然后直接被弹出网站,然后登录无效,卡了十分钟才能登账号。。。
这可能就是打着打着人没了吧

3

哇毕业了竟然有一天还可以见到鸡兔同笼,老夫的青春啊!

2

话不多说,干就完事了!

1

前三题都简单的,第四题我写了个O(n^4)的暴力dp以为肯定超时,结果过了。。?

1

出题人绝对玩过小学奥数。。。
第二题和第三题,让我回想起了被鸡兔同笼和数正方形支配的恐惧。。。
复杂度分别为O(1), O(N)

class Solution:
    # 第二题:
    def numOfBurgers(self, tomato: int, cheese: int) -> List[int]:
        # 4x+2y=tomato
        # x+y=cheese
        x = (tomato-2*cheese)/2
        y = (4*cheese-tomato)/2
        if x%1 or y%1 or x<0 or y<0:
            return []
        else:
            return [int(x),int(y)]

    # 第三题:
    def countSquares(self, matrix: List[List[int]]) -> int:
        dp = {(r,c) for r,row in enumerate(matrix) for c,pt in enumerate(row) if pt}
        ans = 0
        while(dp):
            ans+= len(dp)
            dp = {(r,c) for (r,c) in dp if (r,c+1) in dp and (r+1,c+1) in dp and (r+1,c) in dp}
        return ans

第四题还是dp,不过要分成两次:先统计子串,再对前缀串dp。复杂度O(N**3)
top-down邪教:

from functools import lru_cache
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        @lru_cache(None)
        def diff(i,j):
            if i>=j:
                return 0
            return diff(i+1,j-1)+(s[i]!=s[j])

        @lru_cache(None)
        def split(j,k):
            if k==1:return diff(0,j)
            return min(split(i,k-1)+diff(i+1,j) for i in range(k-2,j))
        return split(len(s)-1, k)
1

看很多解答里,创建数组在最大长度上+5;请问这个5有什么说法吗?

分享下第三题的暴力解法和参考的预处理解法
暴力求解:

class Solution {
public:
 
    bool isLegalBox(vector<vector<int>>& matrix,int tx,int ty,int bx,int by){
        for(int i = bx;i>=tx;i--){
            for(int j = by;j>=ty;j--){
                if(matrix[i][j] == 0){
                    return false;    
                }
            }
        }
        return true;
    }
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int w = min(m,n);
        int result = 0;
        for(int i = m-1;i>=0;i--){
            for(int j = n-1;j>=0;j--){
               for(int a = 0;a<w;a++){
                   if(i-a >=0 && j-a >=0){
                       if(isLegalBox(matrix,i-a,j-a,i,j)){
                           result++;
                       }else{
                            //跳过边长更大的矩形
                            break;  
                       }   
                    }
               }
            }    
        }
        return result;
    }
};

预处理求解:

class Solution {
public:
    int sum[305][305];
    int getSum(int x1,int x2,int y1,int y2){
        return sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1];
    }
    int countSquares(vector<vector<int>>& matrix) {
        
        int m = matrix.size();
        int n = matrix[0].size();
        //sum -> 0,0 ~ i,j 矩阵求和
        memset(sum,0,sizeof(sum));
        
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
            }
        }
        int w = min(n,m);
        int result = 0;
        
        for(int i = 0;i<=m;i++){
            for(int j = 0;j<=n;j++){
                for(int a = 1;a<=w;a++){
                    if(i+a <=m && j+a <=n){
                        if(getSum(i,i+a,j,j+a) == a*a){   
                            result++;
                        }else{
                            break;
                        }
                    }
                }
            }
        }
        return result;
    }
};
1
  • 找出井字棋的获胜者
  • 暴力过,先按照顺序模拟下棋,然后判断结果即可:
class Solution {
    public String tictactoe(int[][] moves) {
        char[][] board = new char[3][3];
        
        for(int i = 0; i < 3; i++){
            Arrays.fill(board[i],'-');
        }
        int x = 0;
        //模拟比赛
        for(int[] mo : moves){
            if(x == 0) board[mo[0]][mo[1]] = 'A';
            if(x == 1) board[mo[0]][mo[1]] = 'B';
            x = 1 - x;
        }
        //判断行
        for(int i = 0; i < 3; i++){
            if(board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] != '-'){
                return board[i][0] == 'A' ? "A" : "B";
            }
        }
        //判断列
        for(int j = 0; j < 3; j++){
            if(board[0][j] == board[1][j] && board[0][j] == board[2][j] && board[2][j] != '-'){
                return board[0][j] == 'A' ? "A" : "B";
            }
        }
        //判断对角线
        if(board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] != '-'){
            return board[0][0] == 'A' ? "A" : "B";
        }
        if(board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] != '-'){
            return board[0][2] == 'A' ? "A" : "B";
        }
        if(moves.length < 9)
            return "Pending";
        return "Draw";
        
    }
}
  • 不浪费原料的汉堡制作方案
  • 简单的数学题:
  • 设x = tomatoSlices;y = cheeseSlices;做汉堡需要番茄为m,奶酪为n
  • 做a个巨无霸:a*(4m+n) ; 做个b小黄堡:b*(2m + n);
  • 一共:a*(4m+n) + b*(2m + n) = xm + yn;
  • 整理一下:(4a+2b)m + (a+b)n = xm + yn;
  • 解之:a = (x - 2 * y) / 2 ; b = y - a;
class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        List<Integer> res = new ArrayList<>();
        int x = tomatoSlices;
        int y = cheeseSlices;
        if((x - 2 * y) % 2 != 0) return res;
        int a = (x - 2 * y) / 2;
        int b = y - a;
        if(a < 0 || b < 0) return res;
        res.add(a);
        res.add(b);
        return res;
    }
}
  • 统计全为 1 的正方形子矩阵
  • 动态规划:
class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        if(m < 1) return 0;
        int n = matrix[0].length;
        //用于累计结果
        int res = 0;
        //dp[i][j],以坐标i,j为右下角的正方形的最大边长,注意是边长
        int[][] dp = new int[m][n];
        if(matrix[0][0] == 1){
            dp[0][0] = 1;
            res ++;
        }

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

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 1){
                    //注意这里min,画图分析即可搞懂
                    dp[i][j] = Math.min(dp[i - 1][j - 1],Math.min(dp[i - 1][j],dp[i][j - 1])) + 1;
                    //累计结果
                    res += dp[i][j];
                }
            }
        }
        return res;
    }
}
  • 分割回文串 III
  • 动态规划
  • 参考题目813. 最大平均值和的分组
class Solution {
    public int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] num = new int[n][n];
        //先统计变成各个子串变成回文串需要改变的字符数量
        for(int i = 0; i < n; i++){
            int left = i - 1;
            int right = i + 1;
            while(left >= 0 && right  < n){
                if(s.charAt(left) != s.charAt(right)){
                    num[left][right] = num[left + 1][right - 1] + 1;
                }else{
                    num[left][right] = num[left + 1][right - 1];
                }
                left --;
                right ++;
            }
        }
        for(int i = 0; i < n - 1; i++){
            int left = i - 1;
            int right = i + 1 + 1;
            if(s.charAt(i) != s.charAt(i + 1)){
                num[i][i + 1] = 1;
            }
            while(left >= 0 && right  < n){
                if(s.charAt(left) != s.charAt(right)){
                    num[left][right] = num[left + 1][right - 1] + 1;
                }else{
                    num[left][right] = num[left + 1][right - 1];
                }
                left --;
                right ++;
            }
        }
        //开始dp
        int[][] dp = new int[n + 1][k + 1];
        //dp[i][l]代表前i个字符分成l份需要改变的最小字符数量,
        //则对于 0<j< i dp[i][l] = min(dp[i][l],dp[j][l - 1] + num[j][i - 1]);
        for(int i = 1; i <= n; i++){
            dp[i][1] = num[0][i - 1];
        }
        for(int i = 1; i <= n; i++){
            for(int l = 2; l <= k; l++){
                dp[i][l] = Integer.MAX_VALUE;
                for(int j = 0; j < i; j++){
                    dp[i][l] = Math.min(dp[i][l],dp[j][l - 1] + num[j][i - 1]);
                }
            }
        }
        return dp[n][k];
        
    }
}

只能完成两道题,觉得自己还是比较菜的...

第一道题 5275. 找出井字棋的获胜者
模拟下棋步骤就做出来了

class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        //棋盘
        int pan[3][3] = {{0,0,0},{0,0,0},{0,0,0}};
        //下棋
        for(int i = 0; i < moves.size(); i++){
            pan[moves[i][0]][moves[i][1]] = (i % 2 == 0?1:-1);
        }
        //下满了吗
        bool isFulled = moves.size() == 9?true:false;
        //横纵统计,前三位A,后三位B
        int x[6] = {0,0,0,0,0,0};
        int y[6] = {0,0,0,0,0,0};
        //两条对角线统计,前A后B
        int cl[2] = {0,0};
        int cr[2] = {0,0};
        //开始统计
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(pan[i][j] == 1){
                    x[i]++;
                    y[j]++;
                    //左对角线
                    if(i + j == 0 || i + j == 4){
                        cl[0]++;
                    }//右对角线
                    else if(i + j == 2){
                        //中间补充
                        if(i == j)  cl[0]++;
                        cr[0]++;
                    }
                }else if(pan[i][j] == -1){
                    x[i+3]++;
                    y[j+3]++;
                    //左对角线
                    if(i + j == 0 || i + j == 4){
                        cl[1]++;
                    }//右对角线
                    else if(i + j == 2){
                        //中间补充
                        if(i == j)  cl[1]++;
                        cr[1]++;
                    }
                }
            }
        }
        //直线判断
        for(int i = 0; i < 6; i++){
            if(x[i] == 3 || y[i] == 3){
                return i < 3?"A":"B";
            }
        }
        //对角线判断
        if(cl[0] == 3 || cr[0] == 3){
            return "A";
        }else if(cl[1] == 3 || cr[1] == 3){
            return "B";
        }
        //终局判断
        if(isFulled)    return "Draw";
        return "Pending";
    }
};

第二道题 5276. 不浪费原料的汉堡制作方案
看完题目以后瞬间就脑补到鸡兔同笼(二元一次方程组),把番茄看做腿,芝士看成头...
然后只需要针对一些特殊情况处理一下就通过了

class Solution {
public:
    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        if(cheeseSlices == tomatoSlices && tomatoSlices == 0)   return {0,0};
        if(tomatoSlices % 2 != 0 || cheeseSlices == 0)   return {};
        int x = (tomatoSlices - 2 * cheeseSlices) / 2;
        int y = cheeseSlices - x;
        if(x < 0 || y < 0) return {};
        return {x,y};
    }
};

第三道题 5277. 统计全为 1 的正方形子矩阵
做的时候脑子里是卷积运算的想法,但能力不足...用C++写的时候各种出问题,时间来不及了...
以下是我做的思路:
第一层和第二层循环分别作为卷积核的偏移,
第三层和第四层循环就对每个核内的数字进行累加,
总数等于边长²的就累加一个正方形。