2023.5.28LeetCode第347场周赛
A. 移除字符串中的尾随零
思路
从最后一位开始遍历,为0则跳过
代码
class Solution {
public:
string removeTrailingZeros(string num) {
int i = num.size() - 1;
while (i >= 0 && num[i] == '0') i -- ;
return num.substr(0, i + 1);
}
};
B. 对角线上不同值的数量差
思路
暴力模拟
代码
class Solution {
public:
vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& g) {
int n = g.size(), m = g[0].size();
vector<vector<int>> ans, tl, br;
ans.resize(n, vector<int>(m));
tl.resize(n, vector<int>(m));
br.resize(n, vector<int>(m));
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ ) {
//tl
int x = i - 1, y = j - 1;
unordered_set<int> se;
while (x >= 0 && y >= 0) {
se.insert(g[x][y]);
x -- , y -- ;
}
tl[i][j] = se.size();
//br
se.clear();
x = i + 1, y = j + 1;
while (x < n && y < m) {
se.insert(g[x][y]);
x ++ , y ++ ;
}
br[i][j] = se.size();
}
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
ans[i][j] = abs(tl[i][j] - br[i][j]);
return ans;
}
};
C. 使所有字符相等的最小成本
思路
对于每个s[i] != s[i - 1]
,要使其相等
有两种选择,翻转前i
个,或者翻转后n - i
个,选择代价最小的方案文章来源:https://www.toymoban.com/news/detail-463181.html
代码
class Solution {
public:
long long minimumCost(string s) {
long long ans = 0;
int n = s.size();
for (int i = 1; i < n; i ++ ) {
if (s[i] != s[i - 1])
ans += min(i, n - i);
}
return ans;
}
};
D. 矩阵中严格递增的单元格数
思路
动态规划
从小到大枚举所有值,每个值一定是从更小的数转移而来
定义动态规划数组f,f[i][j]
表示到(i,j)经过的最多数量
维护每行每列最大的f值f[i][j] = max(row[i], col[j]) + 1
计算后更新row和col数组文章来源地址https://www.toymoban.com/news/detail-463181.html
代码
class Solution {
public:
typedef pair<int, int> PII;
int maxIncreasingCells(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
vector<int> row(n), col(m); // 存放每一行列最大的f值
map<int, vector<PII>> mp; // 从小到大记录每个值的位置
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
mp[mat[i][j]].push_back({i, j});
int ans = 0;
for (auto [k, v] : mp) {
vector<int> p;
for (auto i : v) {
int x = i.first, y = i.second;
p.push_back(max(row[x], col[y]) + 1);
}
for (int i = 0; i < v.size(); i ++ ) {
ans = max(ans, p[i]);
int x = v[i].first, y = v[i].second;
row[x] = max(row[x], p[i]);
col[y] = max(col[y], p[i]);
}
}
return ans;
}
};
到了这里,关于LeetCode第347场周赛的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!