个人网站空间多大合适,网站空间面板,免费的网络推广渠道,成都网站建设成功案例单招网给你一个 二进制 字符串 s 和一个整数 k。
如果一个 二进制字符串 满足以下任一条件#xff0c;则认为该字符串满足 k 约束#xff1a;
字符串中 0 的数量最多为 k。字符串中 1 的数量最多为 k。
返回一个整数#xff0c;表示 s 的所有满足 k 约束 的子字符串的数量。
如…给你一个 二进制 字符串 s 和一个整数 k。
如果一个 二进制字符串 满足以下任一条件则认为该字符串满足 k 约束
字符串中 0 的数量最多为 k。字符串中 1 的数量最多为 k。
返回一个整数表示 s 的所有满足 k 约束 的子字符串的数量。
如果数据范围大的话这题目还真有点难度。但是它的数据太小了直接暴力就行只能算简单中的简单了。思路没啥可说的就按题目要求的做找到所有的子串然后检查是否满足0和1的数量最多为k
class Solution {
public:vectorstring enumerate(string s){vectorstring ret;int d1, lens.length();while (dlen){for (int i0; ilen-d; i){ret.push_back(s.substr(i, d));cout s.substr(i, d) endl;}d;}return ret;}bool k_strain(string s, int k){int num00, num10;for (char i:s){if (i1) num1;else num0;}return num0k || num1k;}int countKConstraintSubstrings(string s, int k) {vectorstring vec enumerate(s);printf(%d\n, vec.size());int ans 0;for (auto i:vec){if (k_strain(i, k)) ans;}return ans;}
};
时间复杂度应该算O(n^3),n表示字符串的长度空间复杂度应该是O(n*n)
