找出井字棋的获胜者
思路
模拟。
代码
class Solution {
public:
char mp[4][4];
bool check(int x, int y, char ch) {
int flag = 1;
for(int i = 0; i < 3; ++i) {
if(mp[x][i] != ch) flag = 0;
}
if(flag) return true;
flag = 1;
for(int i = 0; i < 3; ++i) {
if(mp[i][y] != ch) flag = 0;
}
if(flag) return true;
int cnt = 0;
for(int i = -2; i < 3; ++i) {
if(x + i >= 0 && x + i < 3 && y + i >= 0 && y + i < 3 && mp[x+i][y+i] == ch) ++cnt;
}
if(cnt == 3) return true;
cnt = 0;
for(int i = -2; i < 3; ++i) {
if(x - i >= 0 && x - i < 3 && y + i >= 0 && y + i < 3 && mp[x-i][y+i] == ch) ++cnt;
}
return cnt == 3;
}
string tictactoe(vector<vector<int>>& moves) {
int n = moves.size();
for(int i = 0; i < 3; ++i) {
for(int j = 0; j < 3; ++j) mp[i][j] = ' ';
}
for(int i = 0; i < n; ++i) {
if(i & 1) mp[moves[i][0]][moves[i][1]] = 'O';
else mp[moves[i][0]][moves[i][1]] = 'X';
}
int flag = 0;
for(int i = 0; i < 3; ++i) {
for(int j = 0; j < 3; ++j) {
if(mp[i][j] != ' ' && check(i, j, mp[i][j])) {
if(mp[i][j] == 'X') return "A";
else if(mp[i][j] == 'O') return "B";
}
if(mp[i][j] == ' ') flag = 1;
}
}
if(flag) return "Pending";
else return "Draw";
}
};不浪费原料的汉堡制作方案
思路
一开始看到数据范围只有\(10^7\)然后直接枚举\(T\)了(可能是写搓了？)，然后写了个二分。
二分有多少个小皇堡然后比较\(tomatoSlices\)使用数量。
代码
class Solution {
public:
vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
std::vector<int> v;
int ub = cheeseSlices, lb = 0, mid, ans = -1;
while(ub >= lb) {
mid = (ub + lb) >> 1;
if(mid * 2 + (cheeseSlices - mid) * 4 >= tomatoSlices) {
lb = mid + 1;
ans = mid;
} else ub = mid - 1;
}
if(ans != -1 && ans * 2 + (cheeseSlices - ans) * 4 == tomatoSlices) {
v.resize(2);
v[0] = cheeseSlices - ans, v[1] = ans;
}
return v;
}
};统计全为 1 的正方形子矩阵
思路
二维前缀和然后枚举上下边界的左边界，看这个正方形内的\(1\)的个数。
代码
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
int sum[305][305];
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= m; ++j) sum[i][j] = 0;
}
int ans = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + matrix[i][j];
}
}
for(int l = 1; l <= n; ++l) {
for(int r = l; r <= n; ++r) {
int len = r - l + 1;
for(int j = 1; j + len - 1 <= m; ++j) {
if(sum[r][j+len-1] - sum[l-1][j+len-1] - sum[r][j-1] + sum[l-1][j-1] == len * len) ++ans;
}
}
}
return ans;
}
};分割回文串 III
思路
先预处理出以\(i\)为左端点，\(j\)为右端点的字符串变成回文串需要修改多少个位置。
然后进行\(dp\)，\(dp[i][j]\)表示前\(i\)个字母构成\(j\)个回文串所需要修改的最少位置。
转移方程为\(dp[i][j]=min(dp[i][j],dp[lst-1][j-1]+change[lst][i])\)。
代码
class Solution {
public:
const int inf = 0x3f3f3f3f;
int palindromePartition(string s, int k) {
int dp[105][105];
memset(dp, inf, sizeof(dp));
int n = s.length();
for(int i = 0; i <= k; ++i) dp[0][i] = 0;
int change[105][105];
memset(change, 0, sizeof(change));
for(int i = 0; i < n; ++i) {
for(int j = i; j < n; ++j) {
for(int st = i, ed = j; st <= ed; ++st, --ed) {
change[i][j] += (s[st] != s[ed]);
}
}
}
for(int i = 0; i < n; ++i) {
for(int j = 1; j <= min(i+1, k); ++j) {
for(int lst = 1; lst <= i + 1; ++lst) {
dp[i+1][j] = min(dp[i+1][j], dp[lst-1][j-1] + change[lst-1][i]);
}
}
}
return dp[n][k];
}
};