Code & Func
2017-10-05

打卡,第12天

今天刷的题目是Longest Substring with At Least K Repeating Characters:

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Input: s = “aaabb”, k = 3

Output: 3

The longest substring is “aaa”, as ‘a’ is repeated 3 times.

Input: s = “ababbc”, k = 2

Output: 5

The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

本来是以为像Longest Substring Without Repeating Characters一样用两个下标去遍历,然后动态规划的去做(问题来了?动态规划是什么。。。我竟然还没有去翻,拖延症又犯了),一开始发现我可能需要在遍历前先知道当前字符是否会出现k次啊,恩,那就先用一个unordered_map去遍历一遍字符串来记录出现的次数吧:

1
unordered_map<char,int> count;
2
for(auto c:s)
3
++count[c];

然后就开始思考什么时候i应该向前移动了,当s[j]出现的次数小于k时,i就应该变成j+1了,恩,这个时候我就应该计算s[i,j]的长度,显然不能直接是j-i来算长度啦,因为在以下情况时,它就失灵了:

Input: s = “ababacb” k = 3

如果直接j-i的话,就会得出5,但是显然在这个子串中,b只出现了两次,所以我们还要回去检查一遍,然后就开始想要怎么计算长度,大概需要一个下标ti一直往j移动,遍移动遍计算,那么问题来了,我怎么知道什么时候t应该往前走,什么时候应该计算,恩,干脆先遍历一遍计算一下出现次数,然后我才能知道什么计算。。。突然发现有点不对,我好像写的代码是重复的,恩,按照这个逻辑一直走下去,好像我会一直递归这个过程,想了想就写成递归的形式吧,看起来好像就莫名其妙的写出了一个用分治法的解法了:

  • 先遍历一遍计算整个串中出现的次数
  • 然后开始从头遍历,找出一个t使得count[ s[t] ] < k
  • 找到了,我们就分别计算s[i:t]和s[t+1:j]的最大长度即可
  • 没找到,那么说明整个串是符合的,我们直接返回串长度即可
  • 递归结束的条件就是当串长度比k小的时候啦。
1
string s; //为了减少递归传递而设置的全局变量
2
int t;
3
4
int longestSubstring(string ss, int tt) {
5
if (tt <= 1) return ss.size();
6
s = ss;
7
t = tt;
8
unordered_map<char,int> count;
9
for(auto c:s)
10
++count[c];
11
return longestSubString(0,s.size(),count);
12
}
13
14
int longestSubString(int beg,int end,unordered_map<char,int> &imap ){
15
if (end - beg < t) return 0;
12 collapsed lines
16
int j;
17
for(j = beg;j < end && imap[s[j]] >= t;j++)
18
/*do nothing*/;
19
if (j == end) return end - beg;
20
unordered_map<char,int> right;
21
for(int k = beg;k < j;k++){
22
--imap[ s[k] ];//重复利用imap,减少空间复杂度
23
++right[ s[k] ];
24
}
25
return max(longestSubString(beg,j,right),
26
longestSubString(j+1,end,imap));
27
}

有一点要注意的就是:如果是使用map而不是unordered_map的话,时间是会超限的。

然后是在dicuss中看到的解法:

下面这个的解法和我的类似,他的会比较简洁,不过应该没我的快,因为他每次都需要递归都是直接传递string的,而且调用s.substr其实挺耗费时间的,应该每次都是深拷贝。

1
int longestSubstring(string s, int k) {
2
if(s.size() == 0 || k > s.size()) return 0;
3
if(k == 0) return s.size();
4
unordered_map<char,int> Map;
5
for(int i = 0; i < s.size(); i++){
6
Map[s[i]]++;
7
}
8
int idx =0;
9
while(idx <s.size() && Map[s[idx]] >= k) idx++;
10
if(idx == s.size()) return s.size();
11
int left = longestSubstring(s.substr(0 , idx) , k);
12
int right = longestSubstring(s.substr(idx+1) , k);
13
return max(left, right);
14
}

第二个是用迭代的方法做的,比较快点,但是好像最坏情况是会出现O(n^2)的时间复杂度:

1
int longestSubstring(string s, int k) {
2
int max_len = 0;
3
for (int first = 0; first+k <= s.size();) {
4
int count[26] = {0};
5
int mask = 0;
6
int max_last = first;
7
for (int last = first; last < s.size(); ++last) {
8
int i = s[last] - 'a';
9
count[i]++;
10
if (count[i]<k) mask |= (1 << i);
11
else mask &= (~(1 << i));
12
13
if (mask == 0) {
14
max_len = max(max_len, last-first+1);
15
max_last = last;
6 collapsed lines
16
}
17
}
18
first = max_last + 1;
19
}
20
return max_len;
21
}
上一条动态