力扣第130场双周赛

本文主要是介绍力扣第130场双周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

判断矩阵是否满足条件

给定二维矩阵，判断所有格子是否满足如下条件：

1. 如果它下面的格子存在，那么它需要等于它下面的格子
2. 如果它右边的格子存在，那么它需要不等于它右边的格子

遍历二维矩阵，简单模拟即可。

class Solution {
public:bool satisfiesConditions(vector<vector<int>>& grid) {auto m = grid.size(), n = grid[0].size();for(int i = 0; i < m; i ++){for(int j = 0; j < n; j ++){// 若不是最后一行，判断和下面的格子是否相等if(i != m - 1 && grid[i][j] != grid[i + 1][j])  return false;// 若不是最后一列，判断和右边的格子是否不等if(j != n - 1 && grid[i][j] == grid[i][j + 1])  return false;}}return true;}
};

正方形中的最多点数

给定若干个点和每个点对应的标签，若一个正方形中心在原点，所有边平行于坐标轴，且正方形内不存在标签相同的两个点，则称之为合法正方形。求合法正方形中可以包含的最多点数。

在半边长为$a$合法正方形边界上的点$(x,y)$都满足如下条件：$max(|x|,|y|)=a$​。

条件：这个点的标签之前没有出现过。

从每个半边长不同的正方形从小到大枚举，如果这个半边长的正方形上的所有点都满足条件，则继续判断下一个正方形。

如果这个半边长的正方形上有某个点不满足条件，则退出循环。

class Solution {
public:int maxPointsInsideSquare(vector<vector<int>>& points, string s) {auto n = s.size();// 使用数据结构存储每个正方形上的点和标签map<int, vector<char>> mp;for(int i = 0; i < n; i ++){int x = points[i][0], y = points[i][1];int d = max(fabs(x), fabs(y));char c = s[i];// 将标签放入每个正方形对应的数组中mp[d].push_back(c);}// 存储数量int num = 0;// 存储每个标签出现次数vector<int> m(26);for(auto p : mp){auto y = p.second;bool flag = true;// 遍历当前正方形上所有点的标签，若有已经出现过的，则标记不合法for(auto x : y){if(m[int(x - 'a')] != 0)    flag = false;m[int(x - 'a')] ++;}// 如果合法则加上，不合法则退出循环if(flag)    num += y.size();else    break;}return num;}
};

分割字符频率相等的最少字符串

平衡字符串是指字符串中所有字符串出现的次数都相同。求字符串s最少能分割为多少个平衡字符串。

显然，我们可以用$f(j)$来表示前$j$个字符最少能分割为多少个平衡字符串

那么有$f(i)=minf(j)+1$，并且要满足$s[j+1:i]$是一个平衡字符串。

如何快速判断一个字符串是否为平衡字符串：记字符串长度为$l$，字符串中出现过的字符种类为$x$，字符串中出现最多的字符数量为$y$，若$xy=l$，那么这个字符串就是平衡字符串。

class Solution {
public:int minimumSubstringsInPartition(string s) {int n = s.size();s = " " + s;// f[i]表示前i个字符能被划分为多少个平衡字符串vector<int> f(n + 10, 1010);f[0] = 0, f[1] = 1;for(int i = 2; i <= n; i ++){// m存储s[j:i]内字符出现次数vector<int> m(26);int num = 0, maxx = 0;// 从s[i:i]迭代到s[1:i]for(int j = i; j >= 1; j --){// 若s[j]之前未出现过, 字符种类++if(m[int(s[j] - 'a')] == 0) num ++;m[int(s[j] - 'a')] ++;// 判断一下加完后，最大出现次数是否改变maxx = max(maxx, m[int(s[j] - 'a')]);// 若为s[j:i]平衡字符串，那么字符串可切分为s[1:j-1]和s[j:i]if(num * maxx == i - j + 1) f[i] = min(f[i], f[j - 1] + 1);}// 如果s[1:i]本身就是平衡字符串，答案为1if(num * maxx == i) f[i] = min(f[i], 1);}return f[n];}
};

这篇关于力扣第130场双周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---