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

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

image.png

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

展开讨论
  • 找出井字棋的获胜者
  • 暴力过,先按照顺序模拟下棋,然后判断结果即可:
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];
        
    }
}
展开全部 11 讨论