新姿势暴力过LeetCode 395. Longest Substring with At Least K Repeating Characters
这道题最优解法应该是O(n)的，一开始没想到，就这么暴力也AC了，看网上博客O(n^2)是过不了的，我优化的好？
class Solution {
public:
int longestSubstring(string s, int k) {
if (s.size() == 0 || k > s.size()){
return 0;
}
if (k == 1 || k == 0){
return s.size();
}
int curLen = 0, maxLen = 0;
int ch[26];
for (int i = 0; i < s.size(); ++i){
memset(ch, 0, sizeof(ch));
for (int j = i; j < s.size(); ++j){
ch[s[j] - 'a']++;
if (isTrue(ch, k)){
maxLen = max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
bool isTrue(int ch[26], int k){
for (int i = 0; i < 26; ++i){
if (ch[i] == 0) continue;
if (ch[i] < k) return false;
}
return true;
}
};
0 个回复