算法积累三（数组和字符串）Algorithms-Array and String

1. Common Problems

   1. Get the length of the longest consecutive elements sequence in an array. For example, given [31, 6, 32, 1, 3, 2], the longest consecutive elements sequence is [1,2,3]. Return its length: 3.

      Solution: How to determine if i is in the sequence. If i-1 is in the sequence, then i could add into the seq end. If i+1 is in the sequence, then i could add into the seq front. In this problem, key is num, but what the value of the hashtable? We need to find the max len of the seq, so we want to keep the min and max value of seq, so we can get the len easily. So the value of hashtable should be the min, max pair.

      class Bound{
          int high_;
        	int low_;
        	Bound(int high, int low):high_(high), low_(low) {};
      };
      
      int LengthOfLongestConsecutiveSeq(vector<int>& nums){
          unordered_map<int, Bound> hash_map;
        	int local;
        	int max_len = 0;
        	for(auto& item : nums){
              if(hash_map.count(item)){ // handle for duplicate
                  continue;
              }
            	local = item;
            	int low = local, high = local;
            	if(hash_map.count(local-1)){
                  low = hash_map[local-1].low;
              }
            	if(hash_map.count(local+1)){
                  high = hash_map[local+1].high;
              }
            	// Update low's high, high's low
            	hash_map[low].high = hash_map[local].high = high;
            	hash_map[high].low = hash_map[local].low = low;
            
            	if(high - low + 1 > max_len) max_len = high - low + 1;
            	
          }
        	return max_len;
      }

      Time complexity: only iterative all numbers of nums once, so O(n)

   2. Given input “I have 36 books, 40 pens2.” output should be : “I evah 36 skoob, 40 2snep.” (only two punctuations, period or comma)

      Solution: reverse every word except valid number.

      Need to do two things: one: determine if it needs to reverse, two: reverse the current word.

      string ReverseWord(string& sentences){
        	string res;
          istringstream is(sentences);
        	string temp;
        	while(is >> temp){
            	char punc='';
              if(temp.back() == ',' || temp.back() == '.'){
                	punc = temp.back();
                	temp = temp.substr(0, temp.size()-1);
              }
            	bool flag = true;
            	for(auto& ch : temp){
      			if(ch < '0' && ch > '9'){
                      flag = false;
                    	break;
                  }
              }
            	if(flag){
                  res += temp + punc + ' ';
              }
            	else{
                  reverse(temp.begin(), temp.end());
                	res += temp + punc + ' ';
              }
          }
        	res = res.substr(res.begin(), res.size()-1);
        	return res;
      }

2. Related Templates

   1. Vector:

      1. How to delete element in a vector loop?

         // Wrong one
         for(auto it = v.begin(); it != v.end(); it++){
             if(condition){
                 v.erase(it);
             }
         }

         This is wrong, because when erase the element, the whole vector will change.

         // Correct but not so elegent
         for (auto it = v.begin(); it != v.end(); ){
             if(condition){
                 it = v.erase(it);
             }
           	else{
                 it ++;
             }
         }

         This is correct, because when vector delete one element, the following one will forward one.

         // erase-remove idiom
         v.erase(remove_if(v.begin(), v.end(), [](int i){condition;}, v.end()))

         Actually, I have mentioned this in previous blog. Remove_if function will push all elements that not satisfy the condition to the front, the rest for the back. So erase the return value to the end.

   2. String

      String match:

      1. Brute-Force: O(MN)

      2. Rabin-Karp: amortized O(M+N)

         1. Main idea is :caculate the rolling hash, if the hash is equal to the pattern, then compare the the substring with pattern piece by piece.

         2. For example, pattern = “abc” string = “abdeabc”, selected prime=3, define a=1, b=2, c=3, d=4 ……

            hash(abc) = 1 + 2 * 3 + 3*3^2
            hash(abd) = 1 + 2 * 3 + 4 * 3^2
            hash(bde) = (hash(abd) - hash(a))/3 + 5 * 3^2

            ​

      3. KMP: O(N)

      # Rabin-Karp
      const int base = 256;
      const int prime = 101;
      
      void RabinKarp(string txt, string pattern){
        int update_base = 1;
        
        int t_len = txt.size();
        int p_len = pattern.size();
        // Calculate the hash for pattern
        int p_hash = 0;
        int t_hash = 0;
        for(int i=0; i<p_len; i++){
          // Use for rolling hash update
          update_base = (update_base * base) % prime;
          p_hash = (p_hash * base + pattern[i]) % prime;
          t_hash = (t_hash * base + txt[i]) % prime;
        }
        
        for(int j=0; j<t_len - p_len; j++){
          if(p_hash == t_hash){
            int k=0;
            for(k=0; k<p_len; k++){
              if(txt[j+k] != pattern[k]){
                break;
              }
            }
            if(k == p_len){
              cout << "matched from " << j;
            }
          }
          // Update hash
          // Cannot else if, because equal not mean find completely
          if(j < t_len - p_len){
            t_hash = (base * (t_hash - update_hash * txt[j]) + txt[j + p_len]) % prime;
            // t_hash might be neg
            if(t_hash < 0){
              t_hash = t_hash + prime;
            }
          }
        }
        
      }

      ​