发一道碰到的数组题

用heap 可以优化到O(nlogk）
基本思路就是如果对于一个全为S开头的子串 "S......S"， 必然是先把从最左边（或最右边）开始把若干个S（<=3) 变为 . 有些位置可以把转化3个S， 有些位置只能转化1或2个S， 我们总共就只能做K 次操作。 所以就选top k 个位置。 太懒了，就先贴一个nlogn 的代码吧， 如果限制heap的size为K, 那么负责度就是 nlogk.

1. 
   
2. #include <iostream>
   
3. #include <queue>
   
4. #include <string>
   
5. 
   
6. int solve(string s, int k) {
   
7.     priority_queue<int> q;
   
8.     int idx = 0;
   
9.     int ret = 0;
   
10.     while(idx < s.size()) {
    
11.         if(s[idx] == '.') {
    
12.             ret++;
    
13.             idx++;
    
14.         }
    
15.         else {
    
16.             int len = 0;
    
17.             while(idx + len < s.size() && s[idx + len] == 'S' && len <= 2)
    
18.                 len++;
    
19.             q.push(len);
    
20.             idx += len;
    
21.         }
    
22.     }
    
23.     while(k != 0 && !q.empty()) {
    
24.         ret += q.top();
    
25.         q.pop();
    
26.         k--;
    
27.     }
    
28.     return ret;
    
29. };
    
30. 
    
31. string t = "SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.";
    
32. int main() {
    
33.     cout << solve(t, 23) << endl;
    
34.     return 0;
    
35. }
    

复制代码

337845818 发表于 2019-6-18 00:41
https://leetcode.com/problems/max-consecutive-ones-iii/

补充内容 (2019-6-18 00:45):

哥们你这是我一开始的想法，不过很遗憾应该是错的。
比如
6 2
S.SSSS
按照你的做法答案是5，正确答案是6。

Gary.W 发表于 2019-6-18 04:35
用heap 可以优化到O(nlogk）
基本思路就是如果对于一个全为S开头的子串 "S......S"， 必然是先把从最左边 ...

哥们你试试这个？
6 2
S.SSSS
6
我这边测的是输出的是5

来贴代码了，昨天睡觉的时候优化到了O(n)，其实证明链表里每次断裂后不会产生新的连续3个S(或者1，2个s，如果当前在检查相应的长度)即可，每遍都从前往后扫一遍就可以啦。

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. #include <iterator>
   
5. #include <algorithm>
   
6. #include <list>
   
7. using namespace std;
   
8. 
   
9. int solve(string s,int n,int k)
   
10. {
    
11.     list<int> l;
    
12.     int res = 0;
    
13.     for(auto i:s){
    
14.         if(i=='.') // . converts to 1 and S converts to 0
    
15.         {
    
16.             res++;
    
17.             l.push_back(0);
    
18.         }else
    
19.             l.push_back(1);
    
20.     }
    
21.     for(int curCheck = 3; curCheck>=1 && k>0; curCheck--)
    
22.     {
    
23.         if(l.size()<3)
    
24.             break;
    
25.         auto i=l.begin(), j=i;
    
26.         int windowSum = *(i++);
    
27.         windowSum += *(i++);
    
28.         while(i!=l.end())
    
29.         {
    
30.             windowSum += *(i++);
    
31.             if(windowSum == curCheck)
    
32.             {
    
33.                 res += curCheck;
    
34.                 k--;
    
35.                 if(k == 0)
    
36.                     break;
    
37.                 l.erase(j++);
    
38.                 l.erase(j++);
    
39.                 l.erase(j++);
    
40.                 windowSum =0;
    
41.                 if(i == l.end())
    
42.                     break;
    
43.                 windowSum += *(i++);
    
44.                 if(i == l.end())
    
45.                     break;
    
46.                 windowSum += *(i++);
    
47.                 continue;
    
48.             }
    
49.             windowSum -= *(j++);
    
50.         }
    
51.     }
    
52.    
    
53.     return res;
    
54. }
    
55. 
    
56. int main(int argc, const char * argv[]) {
    
57.     cout<<solve("SS.S...S....SS..S..S.S.S...SS...SSS..SS.SS.SSSSS...S.S.S...S......S",67,4)<<endl;
    
58.     cout<<solve(".S.....SSSSS.SSSS...SS.SSS.SS",29,2)<<endl;
    
59.     cout<<solve(".S...SSS.SSS..SSSS.SSSSS.SS.S.SS.SS.SSSSSSS.SS...SS.S.SSS.SS.S.SS..S..S.SSS.SS.",79,6)<<endl;
    
60.     cout<<solve("SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.",276,23)<<endl;
    
61.     return 0;
    
62. }

复制代码

Neroldy 发表于 2019/06/18 09:39:52


哥们你试试这个？
6 2
S.SSSS
6
我这边测的是输出的是5

这个case 不应该是5吗

Gary.W 发表于 2019/06/18 10:39:46


这个case 不应该是5吗

噗， 溜了溜了

@seeker丶 的代码是没问题的，但是证明应该不对啊，比如
6 2
S.SSSS
其实正确的原因是删除链表节点后，后续节点自动向前补充，从而使得最初的选择是“可移动的”，但是在证明中没体现这一点。

hyn 发表于 2019/06/28 22:55:05
@seeker丶 的代码是没问题的，但是证明应该不对啊，比如
6 2
S.SSSS
其实正确的原因是删除链表节点后，后续节点自动向前补充，从而使得最初的选择是“可移动的”，但是在证明中没体现这一...

这个我觉得是用链表的基本原理了，我觉得读者应该能想明白之所以用链表就是这样的思想，但是仅有这一点不能保证贪心就最优啊，所以正确性的重点还要考虑重叠情况。

换句话说，我不用考虑相对别人的方法为什么“正确”，而要考虑相对链表方法中可能存在的错误为什么“正确”而进行证明