Weekly Contest 165

Posted on | In , | |
Words count in article: 625 | Reading time ≈ 3

1275. Find Winner on a Tic Tac Toe Game

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
class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        int count = 0;
        int map[3][3] = {0};
        // A : 1 , B : -1
        int cur = 1;
        for(auto& m : moves){
            if(count == 9){
                return "Draw";
            }
            map[m[0]][m[1]] = cur;
            if(map[0][0]==cur && map[0][1]==cur && map[0][2]==cur) return cur == 1 ? "A" : "B";
            if(map[1][0]==cur && map[1][1]==cur && map[1][2]==cur) return cur == 1 ? "A" : "B";
            if(map[2][0]==cur && map[2][1]==cur && map[2][2]==cur) return cur == 1 ? "A" : "B";
            if(map[0][0]==cur && map[1][0]==cur && map[2][0]==cur) return cur == 1 ? "A" : "B";
            if(map[0][1]==cur && map[1][1]==cur && map[2][1]==cur) return cur == 1 ? "A" : "B";
            if(map[0][2]==cur && map[1][2]==cur && map[2][2]==cur) return cur == 1 ? "A" : "B";
            if(map[0][0]==cur && map[1][1]==cur && map[2][2]==cur) return cur == 1 ? "A" : "B";
            if(map[2][0]==cur && map[1][1]==cur && map[0][2]==cur) return cur == 1 ? "A" : "B";
            cur *= -1;
            count++;
        }
        if(count == 9) return "Draw";
        else return "Pending";
    }
};

1276. Number of Burgers with No Waste of Ingredients

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> numOfBurgers(int tt, int cc) {
        // Jumbo Burger: 4 tomato slices and 1 cheese slice.
        // Small Burger: 2 Tomato slices and 1 cheese slice.
        vector<int> ret;
        int flag = 0;
        int i = 0;
        while(true){
            if(4 * i + (cc-i) * 2 == tt){
                ret.push_back(i);
                ret.push_back(cc-i);
                break;
            }
            if(i > cc) break;
            i++;
        }
        return ret;
    }
};

1277. Count Square Submatrices with All Ones

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
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int ret = 0;
        for(int i=0; i<matrix.size(); i++){
            for(int j=0; j<matrix[0].size(); j++){
                if(matrix[i][j] == 0) continue;
                ret++;
                int d = 1;
                while(true){
                    int ff = 1;
                    if(i + d >= matrix.size() || j + d >= matrix[0].size()) break;
                    for(int ii = i; ii <= i + d; ii++){
                        for(int jj = j; jj <= j + d; jj++){
                            if(matrix[ii][jj] != 1){
                                ff = 0;
                                break;
                            }
                        }
                    }
                    if(ff == 1) ret++;
                    else break;
                    d++;
                }
            }
        }
        return ret;
    }
};

1278. Palindrome Partitioning III

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
class Solution 
{
    public:
    int moves(string s) //number of steps to make palindrome
    {
        int c=0;
        int p1=0;
        int p2=(int)s.length()-1;
        while(p1<p2)
        {
            if(s[p1]!=s[p2]) c++;
            p1++;
            p2--;
        }
        return c;
    }
    int dp(vector<vector<int>>& m,string& s,int l,int k) //l is the length of the string starting from 0, k is the number of partitions
    {
        if(m[l][k]!=2147483647) return m[l][k];
        if(k==1) m[l][k]=moves(s.substr(0,l));
        else for(int i=k-1;i<l;i++) m[l][k]=min(m[l][k],dp(m,s,i,k-1)+moves(s.substr(i,l-i)));
        return m[l][k];
    }
    int palindromePartition(string s, int k) 
    {
        int n=s.length();
        vector<vector<int>> m(n+1,vector<int>(k+1,2147483647));
        return dp(m,s,n,k);
    }
};
Donate? comment?