On the shoulders of giants.

weekly-contest-165

找出井字棋的获胜者

A 和 B 在一个 3 x 3 的网格上玩井字棋。

井字棋游戏的规则如下:

  • 玩家轮流将棋子放在空方格 (” “) 上。
  • 第一个玩家 A 总是用 “X” 作为棋子,而第二个玩家 B 总是用 “O” 作为棋子。
  • “X” 和 “O” 只能放在空方格中,而不能放在已经被占用的方格上。
  • 只要有 3 个相同的(非空)棋子排成一条直线(行、列、对角线)时,游戏结束。
  • 如果所有方块都放满棋子(不为空),游戏也会结束。
  • 游戏结束后,棋子无法再进行任何移动。

给你一个数组 moves,其中每个元素是大小为 2 的另一个数组(元素分别对应网格的行和列),它按照 AB 的行动顺序(先 AB)记录了两人各自的棋子位置。

如果游戏存在获胜者(AB),就返回该游戏的获胜者;如果游戏以平局结束,则返回 “Draw”;如果仍会有行动(游戏未结束),则返回 “Pending”。

你可以假设 moves 都 有效(遵循井字棋规则),网格最初是空的,A 将先行动。

示例 1:

输入:moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
输出:"A"
解释:"A" 获胜,他总是先走。
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

示例 2:

输入:moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
输出:"B"
解释:"B" 获胜。
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

示例 3:

输入:moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
输出:"Draw"
输出:由于没有办法再行动,游戏以平局结束。
"XXO"
"OOX"
"XOX"

示例 4:

输入:moves = [[0,0],[1,1]]
输出:"Pending"
解释:游戏还没有结束。
"X  "
" O "
"   "

提示:

  • 1 <= moves.length <= 9
  • moves[i].length == 2
  • 0 <= moves[i][j] <= 2
  • moves 里没有重复的元素。
  • moves 遵循井字棋的规则。
题解

给 \(x,o\) 分别记录行、列、对角线上的棋子个数,如果存在 3 个,那么该棋手胜。

时间复杂度:\(O(n)\)

class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        int row[2][3], col[2][3], count[2][2];
        
        memset(row, 0, sizeof(row));
        memset(col, 0, sizeof(col));
        memset(count, 0, sizeof(count));
        
        for(int i = 0; i < moves.size(); i++) {
            int o = i % 2, x = moves[i][0], y = moves[i][1];
            row[o][x]++;
            col[o][y]++;
            if(x - y == 0) count[o][0]++;
            if(x + y == 2) count[o][1]++;
            if(row[o][x] == 3 || col[o][y] == 3 || count[o][0] == 3 || count[o][1] == 3) {
                return o == 0 ? "A" : "B";
            }
        }
        
        if(moves.size() == 9) return "Draw";
        else return "Pending";
    }
};

不浪费原料的汉堡制作方案

圣诞活动预热开始啦,汉堡店推出了全新的汉堡套餐。为了避免浪费原料,请你帮他们制定合适的制作计划。

给你两个整数 tomatoSlices 和 cheeseSlices,分别表示番茄片和奶酪片的数目。不同汉堡的原料搭配如下:

  • 巨无霸汉堡:4 片番茄和 1 片奶酪
  • 小皇堡:2 片番茄和 1 片奶酪

请你以 [total_jumbo, total_small]([巨无霸汉堡总数,小皇堡总数])的格式返回恰当的制作方案,使得剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量都是 0

如果无法使剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量为 0,就请返回 []

示例 1:

输入:tomatoSlices = 16, cheeseSlices = 7
输出:[1,6]
解释:制作 1 个巨无霸汉堡和 6 个小皇堡需要 4*1 + 2*6 = 16 片番茄和 1 + 6 = 7 片奶酪。不会剩下原料。

示例 2:

输入:tomatoSlices = 17, cheeseSlices = 4
输出:[]
解释:只制作小皇堡和巨无霸汉堡无法用光全部原料。

示例 3:

输入:tomatoSlices = 4, cheeseSlices = 17
输出:[]
解释:制作 1 个巨无霸汉堡会剩下 16 片奶酪,制作 2 个小皇堡会剩下 15 片奶酪。

示例 4:

输入:tomatoSlices = 0, cheeseSlices = 0
输出:[0,0]

示例 5:

输入:tomatoSlices = 2, cheeseSlices = 1
输出:[0,1]

提示:

  • 0 <= tomatoSlices <= 10^7
  • 0 <= cheeseSlices <= 10^7
题解

为了推到方便,假设 \(n=tomatoSlices,m=cheeseSlices\) 。

设有 \(x\) 个巨型汉堡, \(y\) 个小型汉堡。

那么有,\(4x+2y=n,x+y=m\) ,即 \(x=\frac{n-2m}{2}\) 。

所以当 \(n-2m\) 被 \(2\) 整除时有解,\(y=m-x\) 且 \(0\leqslant x,y\) 。

时间复杂度:\(O(1)\)

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

统计全为 1 的正方形子矩阵

给你一个 m * n 的矩阵,矩阵中的元素不是 0 就是 1,请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1:

输入:matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出:15
解释: 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2:

输入:matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出:7
解释:
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

提示:

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1
题解

先统计二维前缀和,然后枚举子正方形边长 \(r\) ,并遍历所有子正方形,判断子正方形内的权值和是否为 \(r^2\) 。

时间复杂度:\(O(n^3)\)

class Solution {
public:
    vector<vector<int>> sum;
    
    int cal(int x1, int y1, int r) {
        int x2 = x1 + r - 1, y2 = y1 + r - 1, num = 0;
        num = sum[x2][y2];
        if(x1) num -= sum[x1 - 1][y2];
        if(y1) num -= sum[x2][y1 - 1];
        if(x1 && y1) num += sum[x1 - 1][y1 - 1];
        return num;
    }
    
    int countSquares(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size(), count = 0;
        
        sum.resize(n);
        for(int i = 0; i < n; i++) sum[i].resize(m);
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                sum[i][j] = matrix[i][j];
                if(i) sum[i][j] += sum[i - 1][j];
                if(j) sum[i][j] += sum[i][j - 1];
                if(i && j) sum[i][j] -= sum[i - 1][j - 1];
            }
        }
        
        for(int r = 1; r <= min(n, m); r++) {
            for(int i = 0; i + r - 1 < n; i++) {
                for(int j = 0; j + r - 1 < m; j++) {
                    if(cal(i, j, r) == r * r) count++;
                }
            }
        }
        
        return count;
    }
};

分割回文串 III

给你一个由小写字母组成的字符串 s,和一个整数 k

请你按下面的要求分割字符串:

  • 首先,你可以将 s 中的部分字符修改为其他的小写英文字母。
  • 接着,你需要把 s 分割成 k 个非空且不相交的子串,并且每个子串都是回文串。

请返回以这种方式分割字符串所需修改的最少字符数。

示例 1:

输入:s = "abc", k = 2
输出:1
解释:你可以把字符串分割成 "ab" 和 "c",并修改 "ab" 中的 1 个字符,将它变成回文串。

示例 2:

输入:s = "aabbc", k = 3
输出:0
解释:你可以把字符串分割成 "aa"、"bb" 和 "c",它们都是回文串。

示例 3:

输入:s = "leetcode", k = 8
输出:0

提示:

  • 1 <= k <= s.length <= 100
  • s 中只含有小写英文字母。
题解

动态规划:设 \(dp_{i,k}\) 为字符子串 \(s_{0,i}\) 划为 \(k\) 个子串的最小代价,状态转移为:

当 \(j<i\) , \(dp_{i,k}=\min (dp[j,k-1] + cost[j+1][i])\) 。

其中 \(cost_{x,y}\) 为字符子串 \(s_{x,y}\) 变为回文串的最小代价,可以预处理出 \(cost_{x,y}\) 。

时间复杂度:\(O(n^3)\)

class Solution {
public:
    int cal(string s) {
        int n = s.length() - 1, count = 0;
        int x = n / 2, y = (n % 2 ? x + 1 : x);
        
        for(int i = 0; i <= n / 2; i++) {
            count += (s[x - i] != s[y + i]);
        }
        
        return count;
    }
    
    int palindromePartition(string s, int k) {
        int n = s.length();
        int cost[n][n], dp[n][k + 1];
        
        memset(cost, 0, sizeof(cost));
        memset(dp, 0x3f, sizeof(dp));
        
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                cost[i][j] = cal(s.substr(i, j - i + 1));
            }
        }
        
        for(int i = 0; i < n; i++) dp[i][1] = cost[0][i];
        
        for(int ki = 2; ki <= k; ki++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < i; j++) {
                    dp[i][ki] = min(dp[i][ki], dp[j][ki - 1] + cost[j + 1][i]);
                }
            }
        }
        
        return dp[n - 1][k];
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注