亚麻：2017-11 (not fresh grad ) find all substring with N size and only one duplicate character.-白红宇

亚麻：2017-11 (not fresh grad ) find all substring with N size and only one duplicate character.

阅读量：5140 次

发布时间：2019-06-13

本文共 2529 字，大约阅读时间需要 8 分钟。

可能是2018 亚麻的OA题。

1.给字符串，找出里面长度为N的，并且里面字符只有一次重复的字串。

例子：s: asdfaghjkjqoiiii;N=5. 返回asdfa ghjkj hjkjq jkjqo jqoii.

1 #include 
     
           // std::cout 2 #include 
      
           // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap 3 #include 
       
               // std::vector 4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 11 //main point : ( refer to key data structure and the trick )12 13 // use the two unordered set: dup and match14 // dup : for check if the finded substring is already in result set , that means it has been found early.15 // match: check if the substring has only one duplicated char.16 17 //use list to store the results.18 19 // iterate the string with N size window from first char to the end of the string.20 21 22 using namespace std;23 24 25 list
              
                findNSubstring (string& s, int N){26 //check the input27 if ( s.empty()|| s.size() < N ) return list
               
                ();28 29 int sp =0;30 int steps = N-1;31 cout << " the steps is " << steps << endl;32 unordered_set
                
                  dup; //make sure no duplicated substring in result set.33 unordered_set 
                 
                   match; // check the substring has only one duplicated char.34 list
                  
                    res; //store the output.35 36 // Check the substrings one by one with N size window.37 while ((sp+steps) < s.size()){38 match.clear();39 40 // check if the substring have only one duplicated character.41 for (int j =0; j < N ; j++){42 match.insert(s[sp+j]);43 }44 45 if (match.size() == N-1){ // if yes, check if that substring has been in result set.46 cout<< "find one " << s.substr( sp, N) << " at "<< sp << endl;47 if ( dup.find( s.substr( sp, steps)) == dup.end()){48 res.push_back(s.substr( sp, N));49 dup.insert (s.substr( sp, N));50 }51 }52 sp++;53 }54 return res;55 }56 57 int main () {58 59 // cout << " test a substring length : " << string ("").size() << endl;60 61 //get the start time.62 struct timeval tv;63 gettimeofday(&tv,NULL);64 long ts = tv.tv_sec * 1000 + tv.tv_usec / 1000;65 66 //*** call the function .67 68 string in = "iiiiiiiiiiiiiiiiiii";//asdfaghjkjqoiiii";69 70 int q = 100 ;71 72 auto out = findNSubstring(in, q) ;73 74 for (auto e : out)75 cout<< e << endl;76 //*** end of the call77 78 //get the time of end.79 gettimeofday(&tv,NULL);80 long te = tv.tv_sec * 1000 + tv.tv_usec / 1000;81 82 //output the time of the running.83 cout<
                   
                    << endl<< "running tmie is : " << te - ts << endl;84 return 0;85 }