LeetCode刷题笔记
目录
一.2496.数组中字符串的最大值
思路：
遍历输入数组中的字符串，判断字符串每一个字符是否都是数字。如果字符串只包含数字，那么转换该字符串为十进制下的所表示的数字，否则值为字符串的长度。最后返回字符串数组里的最大值。
代码：
class Solution {
public:
int maximumValue(vector<string>& strs) {
int cnt=0;
for(auto& str:strs){
bool flage=true;
for(char& s:str){
if(!isdigit(s)){
flage=false;
break;
}
}
cnt=max(cnt,flage?stoi(str):(int)str.size());
}
return cnt;
}
};注意事项：
isdigit()是检测字符是否是数字的字符。
stoi()将数字字符串，转化为数字。
string.size()返回值是unsigned类型，需要强制转换。
二.面试题 16.19.水域大小
思路：
- 从网格图的 0 出发，DFS 访问八方向的 0，并把这些 0 标记成「访问过」。代码实现时可以直接把 0 修改成 1。
- DFS 过程中，统计每个方向访问到的格子个数，累加个数得到池塘大小 cnt。
- 每次从一个新的 0 出发（起点），就意味着找到了一个新的池塘，把 DFS 得到的池塘大小加入答案。
- 利用sort函数，把答案排序后返回。
代码：
class Solution {
public:
int fang[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
int dfs(vector<vector<int>> &land, int x, int y) {
if (x < 0 || x >= land.size() || y < 0 || y >= land[x].size() || land[x][y])
return 0;
land[x][y] = 1;
// 标记 (x,y) 被访问，避免重复访问
int cnt = 1;
// 访问八方向的
for(int i=0;i<8;i++)
cnt+= dfs(land,x+fang[i][0],y+fang[i][1]);
return cnt;
}
vector<int> pondSizes(vector<vector<int>>& land) {
int hang=land.size();
int lie=land[0].size();
vector<int> s;
for(int i=0;i<hang;i++){
for(int j=0;j<lie;j++){
if(land[i][j]==0){
int p=dfs(land,i,j);
s.push_back(p);
}
}
}
sort(s.begin(),s.end());
return s;
}
};三.LCP 41 .黑白翻转棋
思路：
我们注意到，题目中棋盘的大小最大为 8×8，因此，我们可以尝试枚举所有的空余位置作为下一步放置黑棋的位置，然后使用广度优先搜索的方法计算在该位置下可以翻转的白棋的数量，找出最大值即可。我们定义一个函数 bfs(i,j)，表示在棋盘上放置黑棋在 (i,j) 位置后，可以翻转的白棋的数量。在函数中，我们使用队列来进行广度优先搜索，初始时将 (i,j) 放入队列中，然后不断取出队首位置，遍历棋盘的八个方向，如果该方向上是一段连续的白棋，且在末尾是黑棋，则将该黑棋之前的所有白棋都可以翻转，将这些白棋的位置放入队列中，继续进行广度优先搜索。最后，我们返回可以翻转的白棋的数量。
代码：
class Solution {
public:
const int dirs[8][2] = {
{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
};
bool judge(const vector<string>& chessboard, int x, int y, int dx, int dy) {
x += dx;
y += dy;
while (0 <= x && x < chessboard.size() && 0 <= y && y < chessboard[0].size()) {
if (chessboard[x][y] == 'X') {
return true;
} else if (chessboard[x][y] == '.') {
return false;
}
x += dx;
y += dy;
}
return false;
}
int bfs(vector<string> chessboard, int px, int py) {
int cnt = 0;
queue<pair<int, int>> q;
q.emplace(px, py);
chessboard[px][py] = 'X';
while (!q.empty()) {
pair<int, int> t = q.front();
q.pop();
for (int i = 0; i < 8; ++i) {
if (judge(chessboard, t.first, t.second, dirs[i][0], dirs[i][1])) {
int x = t.first + dirs[i][0], y = t.second + dirs[i][1];
while (chessboard[x][y] != 'X') {
q.emplace(x, y);
chessboard[x][y] = 'X';
x += dirs[i][0];
y += dirs[i][1];
++cnt;
}
}
}
}
return cnt;
}
int flipChess(vector<string>& chessboard) {
int res = 0;
for (int i = 0; i < chessboard.size(); ++i) {
for (int j = 0; j < chessboard[0].size(); ++j) {
if (chessboard[i][j] == '.') {
res = max(res, bfs(chessboard, i, j));
}
}
}
return res;
}
};
1595.连接两组点的最小成本
思路：
枚举第一组物品，对于这 n 个物品,每一个物品都有 2^m 种连线状态 (一个物品可以连多个另一组的物品)也就有 2^m 种连线发方式。枚举 n 个物品，对于第 i 个物品的每个状态集合，计算他和前 i-1 个物品的总状态集合的最小代价这里如果是暴力直接枚举，则时间复杂度是 O(n2^m2^m)
因为一共 n 个物品，前 i-1 个物品状态集合大小是 2^m，当前第 i 个物品状态集合大小是 2^m
当前物品 i 的状态集合是前 i 个物品状态集合的子集时分两种情况:
1:物品 i 的状态集合与前 i-1 个物品的状态集合无交集时，两集合并可能会使并集代价更小
2:物品 i 的状态集合与前 i-1 个物品的状态集合有交集时，物品 i 只有对第 2 组连一条线时才可能更新状态，这是因为有交集的那部分前 i-1 个物品中肯定有物品连过了，那对于前 i 个物品的这个二进制状态，当前物品再连肯定是浪费的，但是只连无交集的部分情况1已经包含了，所以为了防止当前的第 i 个物品一条线都不连，则再枚举一下只连一条线防止当前物品落下的情况
代码：
class Solution {
public:
int connectTwoGroups(vector<vector<int>> &cost) {
int m = cost[0].size(), f[1 << m];
f[0] = 0;
for (int j = 0; j < m; j++) {
int mn = INT_MAX;
for (auto &c: cost)
mn = min(mn, c[j]);
int bit = 1 << j;
for (int mask = 0; mask < bit; mask++)
f[bit | mask] = f[mask] + mn;
}
for (auto &row: cost) {
for (int j = (1 << m) - 1; j >= 0; j--) {
int res = INT_MAX;
for (int k = 0; k < m; k++)
res = min(res, f[j & ~(1 << k)] + row[k]);
f[j] = res;
}
}
return f[(1 << m) - 1];
}
};
- 点赞
- 收藏
- 关注作者
评论（0）