Amazon 社招新OA

贡献一个sliding window 的答案

1.    public List<String> Solution(String s, int N){
   
2.         List<String> res = new ArrayList<>();
   
3.         if(s == null || N <=0 || s.length() < N) return res;
   
4.         Map<Character, Integer> map = new HashMap<>();
   
5.         int left = 0, dupCount = 0, len = 0;
   
6.         for(int right = 0; right < s.length(); right++){
   
7.             len++;
   
8.             if(!map.containsKey(s.charAt(right))){
   
9.                 map.put(s.charAt(right), 1);
   
10.             }else{
    
11.                 map.put(s.charAt(right), map.get(s.charAt(right))+1);
    
12.                 dupCount++;
    
13.             }
    
14. 
    
15.             while(len == N){
    
16.                 if(dupCount == 1){
    
17.                     String subString = s.substring(left, left + N);
    
18.                     res.add(subString);
    
19.                 }
    
20.                 if(map.get(s.charAt(left)) == 2){
    
21.                     dupCount--;
    
22.                 }
    
23.                 map.put(s.charAt(left), map.get(s.charAt(left)) - 1);
    
24.                 len--;
    
25.                 ++left;
    
26.             }
    
27.         }
    
28. 
    
29.         return res;
    
30.     }

复制代码

我知道你哪里错了，result里面要排除掉重复的string。应该问题就出在这里。

lixin832500 发表于 2017-12-30 07:32
贡献一个sliding window 的答案

这个代码里也没有去重吧

xxtxdy 发表于 2018-1-16 05:27
这个代码里也没有去重吧

去重可以最后直接用set

Sliding Window: 用hash map记录char frequency, 用hash set存满足条件的substring

1. vector<string> distingK1Substrings(string s, int k) {
   
2.     unordered_set<string> unique; // distinct substrings
   
3.     unordered_map<char, int> fre; // substring char frequency
   
4.     for (int i = 0; i < s.size(); ++i) {
   
5.         ++fre[s[i]];
   
6.         if (i >= k && --fre[s[i-k]] == 0) fre.erase(s[i-k]);
   
7.         if (fre.size() == k-1) unique.insert(s.substr(i-k+1,k));
   
8.     }
   
9.     return vector<string>(unique.begin(), unique.end());
   
10. }

复制代码

zzgzzm 发表于 2018-2-4 01:17
Sliding Window: 用hash map记录char frequency, 用hash set存满足条件的substring

楼上的Code跑出来有问题也～

tanyeun 发表于 2018-2-9 02:34
楼上的Code跑出来有问题也～

什么问题？是因为输出没有按原string中的顺序吗？若是有这个要求的话就加一个vector<string>,每找到一个先在unique中看是否存在，若不存在就加入vector<string>。

unorder_set中的顺序是随机的。

啊，我看错了，原来这个是解k-1 distinct, 有一个重复的．我以为是解k distinct

lixin832500 发表于 2017-12-30 07:32
贡献一个sliding window 的答案

dupCount --的判断条件应该是 >= 2，不是== 2吧？比如这个用例"aaabbcccc", 4

zzgzzm 发表于 2018-2-4 01:17
Sliding Window: 用hash map记录char frequency, 用hash set存满足条件的substring

有没有什么好方法去掉重复的string ?