Leetcode周赛165
2024-08-28 23:10:35
找出井字棋的获胜者
思路
模拟。
代码
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];
}
};
最新文章
- Java 设计模式 —— 单例模式
- ipad上自定义view的旋转适配
- c++ STL 学习记录 草稿。
- String、Stringbuffer、StringBuilder的区别（转载）
- HDU 3487 Play with Chain（Splay）
- update多表陷阱
- C#常用的命名规范
- vb安装过程中 ntvdm.exe[9696]中发生未处理的win32异常
- /调整button的title的位置
- ToString()使用方法
- GCC 命令行具体解释
- QT在构造函数中退出程序
- 获取 metadata 的完整例子 - 每天5分钟玩转 OpenStack（166）
- NPOI给单元格加范围边框
- Django与Ajax
- js 取整 取余
- T-SQL删除存储过程
- ThinkPHP 文件上传到阿里云OSS上（干货）
- [转]【Angular4】基础（一）：脚手架 Angular CLI
- [HTML/CSS]有一种节点叫做文本节点