LeetCode2019年第165场周赛

发表于 更新于 分类于 阅读次数： Disqus：

1275. 找出井字棋的获胜者

题目描述

A 和 B 在一个 3 x 3 的网格上玩井字棋。 井字棋游戏的规则如下： 玩家轮流将棋子放在空方格 (“ “) 上。 第一个玩家 A 总是用 “X” 作为棋子，而第二个玩家 B 总是用 “O” 作为棋子。 “X” 和 “O” 只能放在空方格中，而不能放在已经被占用的方格上。 只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。 如果所有方块都放满棋子（不为空），游戏也会结束。 游戏结束后，棋子无法再进行任何移动。 给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。 如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 “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 遵循井字棋的规则。

题解1

模拟即可，判断横，竖，及对角线只否有连线成功，有则返回对应的胜利者，没有的话，就看还有没有空位可以继续行动，有的话，表示仍可以行动，没有的话，就是平局。

代码1

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
int deal(int arr[3][3]){
    for(int i = 0; i < 3; ++i){
        if(arr[i][0] == 0 && arr[i][1] == 0 && arr[i][2] == 0){//行  - A
            return 0;
        }
        if(arr[i][0] == 1 && arr[i][1] == 1 && arr[i][2] == 1){//行 - B
            return 1;
        }
        if(arr[0][i] == 0 && arr[1][i] == 0 && arr[2][i] == 0){// 列 - A
            return 0;
        }
        if(arr[0][i] == 1 && arr[1][i] == 1 && arr[2][i] == 1){// 列 － B
            return 1;
        }
    }
    if(arr[0][0] == 0 && arr[1][1] == 0 && arr[2][2] == 0){//主 对角线 - A
        return 0;
    }
    if(arr[0][0] == 1 && arr[1][1] == 1 && arr[2][2] == 1){//主对角线 - B 
        return 1;
    }
    if(arr[0][2] == 0 && arr[1][1] == 0 && arr[2][0] == 0){//副对角线 - A
        return 0;
    }
    if(arr[0][2] == 1 && arr[1][1] == 1 && arr[2][0] == 1){//副对角线 - B
        return 1;
    }
    return -1;
}
class Solution {
public:

    string tictactoe(vector<vector<int>>& moves) {
        int arr[3][3];
        for(int i = 0; i < 3; ++i){
            for(int  j = 0;j < 3; ++j){
                arr[i][j] = -1;
            }
        }
        for(int i = 0; i < moves.size(); ++i){
            if(i & 1 == 1){
                arr[moves[i][0]][moves[i][1]] = 1;
            }
            else{
                arr[moves[i][0]][moves[i][1]] = 0;
            }
        }
        int res = deal(arr);
        cout << res << endl;
        for(int i = 0; i < 3; ++i){
            for(int  j = 0;j < 3; ++j){
                cout << arr[i][i] << " ";
            }
            cout << endl;
        }
        if(res == -1){
            bool flag = false;
            for(int i = 0; i < 3; ++i){
                for(int j = 0; j < 3; ++j){
                    if(arr[i][j] == -1){//有空格
                        flag = true;
                        break;
                    }
                }
            }
            if(flag){
                return "Pending";
            }
            else{
                return "Draw";
            }
        }
        else{
            return deal(arr) == 0?"A":"B";
        }
    }
};

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

题目描述

圣诞活动预热开始啦，汉堡店推出了全新的汉堡套餐。为了避免浪费原料，请你帮他们制定合适的制作计划。 给你两个整数 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]

题解1

解二元一次方程组即可，注意两个变量的解均为非负值。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> numOfBurgers(int tom, int che) {
        vector<int>res;
        int tmp = tom - 2 * che;
        if(tmp < 0  tmp & 1 == 1){
            return res;
        }
        res.push_back(tmp >> 1);
        res.push_back(che - (tmp >> 1));
        if(res[0] < 0  res[1] < 0){
            res.clear();
        }
        return res;
    }
};

1277. 统计全为 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

题解1

模拟，固定正方形的左上角，改变它的边长，直接求解的时间复杂度为$o(n^4)$，可以用$o(n^2)$的空间来存储行和与列和，只需要判断序列和是否与边长相等即可。具体实现见代码。

代码1

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
39
40
41
42
43
44
45
46
47
48
49
50
51
int rowSum[305][305];
int colSum[305][305];
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        memset(rowSum, 0, sizeof(rowSum));
        memset(rowSum, 0, sizeof(rowSum));
        int len1 = matrix.size();
        int len2 = matrix[0].size();
        for(int i = 0; i < len1; ++i){//行和
            for(int j = 0; j < len2; ++j){
                rowSum[i][j] = matrix[i][j] + (j == 0?0:rowSum[i][j - 1]);
            }
        }
        for(int i = 0; i < len1; ++i){//列和
            for(int j = 0; j < len2; ++j){
                colSum[i][j] = matrix[i][j] + (i == 0?0:colSum[i - 1][j]);
            }
        }
        long long int res = 0, num = 0;
        for(int i = 0; i < len1; ++i){
            for(int j = 0; j < len2; ++j){
                if(matrix[i][j] == 1){
                    ++num;
                    int tmp1, tmp2;
                    for(int m = i, n = j;m < len1, n < len2; m = m+1, n = n+1){//固定左上角顶，扩大边长
                        if(j - 1 < 0){
                            tmp1 = 0;
                        }
                        else{
                            tmp1 = rowSum[m][j - 1];
                        }
                        if(i - 1 < 0){
                            tmp2 = 0;
                        }
                        else{
                            tmp2 = colSum[i - 1][n];
                        }
                        if((rowSum[m][n] - tmp1 == n - j + 1) && (colSum[m][n] - tmp2 == m - i + 1)){
                            ++res;
                        }
                        else{
                            break;
                        }
                    }
                }
            }
        }
        return res;
    }
};

1278. 分割回文串 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 中只含有小写英文字母。

题解1

动态规划 dp[i][j]表示长度为j的字符串，划成i个回文串所需最少替换次数。 其中dp[i][j]的状态转换方程为 $dp[i][j] = min(dp[i][j], dp[i - 1][k] + deal(k, j - 1))\space k=i-1, \dots, j - 1$

代码1

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
39
40
41
42
#define MAX (1 << 30)
int cal(string s, int beg, int end){//计算变成回文串的步数
    int len = end - beg + 1, res = 0;
    if(len <= 0){
        return 0;
    }
    else{
        for(int i = beg, j = end; i < beg + (end - beg + 1) / 2; ++i, --j){
            if(s[i] != s[j]){
                ++res;
            }
        }
        return res;
    }
}


class Solution {
public:
    int palindromePartition(string s, int k) {
        int dp[105][105];//dp[i][j]表示将长为j的字符串分成i段
        int len =  s.size();
        for(int i = 0; i <= 100; ++i){//初始化
            for(int j = 0; j <= 100; ++j){
                if(i  >=  j){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = MAX;
                }
            }
        }
        for(int i = 1; i <= k; ++i){//分段
            for(int j = i; j <= len; ++j){//j的长度
                for(int k = i - 1; k <= j; ++k){
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + cal(s, k, j - 1));
                }
            }
        }
        return dp[k][len];
    }
};