[Leetcode] Find Median from Data Stream, Solution

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: 

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

For example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

[Thoughts]
这里保持两个堆，一个最大堆，一个最小堆，把输入数字一分为二，保持两个一半一半。当输入数组为偶数个数字的时候，从最大堆和最小堆取堆顶的数字，求平均。当输入数组为奇数个数字的时候，取最小堆的堆顶。


[Code]

1:  class MedianFinder {  
2:  public:  
3:    priority_queue<int> min_h;  
4:    priority_queue<int, std::vector<int>, std::greater<int>> max_h;  
5:    /** initialize your data structure here. */  
6:    MedianFinder() {  
7:        
8:    }  
9:      
10:    void addNum(int num) {  
11:      min_h.push(num);  
12:      max_h.push(min_h.top());  
13:      min_h.pop();  
14:      if(min_h.size() < max_h.size()) {  
15:        min_h.push(max_h.top());  
16:        max_h.pop();  
17:      }  
18:    }  
19:      
20:    double findMedian() {  
21:      if(min_h.size() > max_h.size()) return min_h.top();  
22:      return (double)(min_h.top() + max_h.top())/2;  
23:    }  
24:  };  
25:    
26:  /**  
27:   * Your MedianFinder object will be instantiated and called as such:  
28:   * MedianFinder obj = new MedianFinder();  
29:   * obj.addNum(num);  
30:   * double param_2 = obj.findMedian();  
31:   */  

[Leetcode] Maximum Length of Pair Chain, Solution

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:

1. The number of given pairs will be in the range [1, 1000].

[Thoughts]
按照数组的结束数字排序，然后从左到右扫描。如果满足b<c的条件，则count+1.


[Code]

1:    int findLongestChain(vector<vector<int>>& pairs) {  
2:      if(pairs.size() == 0) return 0;  
3:        
4:      std::sort(pairs.begin(), pairs.end(), comp);  
5:        
6:      int count = 1;  
7:      vector<int>& pair = pairs[0];  
8:      for(int i =1; i<pairs.size(); i++) {  
9:        if(pairs[i][0] > pair[1]) {  
10:          count ++;  
11:          pair = pairs[i];  
12:        }  
13:      }  
14:        
15:      return count;  
16:    }  
17:      
18:    static bool comp(vector<int>& a, vector<int>& b) {  
19:      return a[1] < b[1];  
20:    }  

[Leetcode] Palindromic Substrings, Solution

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

1. The input string length won't exceed 1000.

[Thoughts]
从左到右遍历字符串，以每一个字符为中心，向左右两边扩展扫描，统计palindromic string。

另外，这题也可以用DP，类似于 http://fisherlei.blogspot.com/2012/12/leetcode-longest-palindromic-substring.html 。

[Code]

1:    int countSubstrings(string s) {  
2:      if(s == "") return 0;  
3:        
4:      int count = 1;   
5:      for(int i =1; i< s.size(); i++) {  
6:        // palindrom length is odd and i in the middle  
7:        count += countPalindrom(s, i, i);  
8:          
9:        // palindrom length is even and (i-1, i) in themiddle  
10:        count += countPalindrom(s, i-1, i);  
11:      }  
12:      return count;  
13:    }  
14:      
15:    int countPalindrom(string& s, int start, int end) {  
16:      int count = 0;  
17:      for(int i =0; start >=0 && end <s.size(); i++)  
18:      {  
19:        if(s[start] != s[end]) break;  
20:          
21:        count++;  
22:        start--;  
23:        end++;  
24:      }  
25:        
26:      return count;  
27:    }  

[Leetcode] Decode String, Solution

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

[Thoughts]
凡是这种decode的题，基本上都是用栈。当遇到左括号的时候，保留住当前的栈状态，当遇到右括号的时候，弹出当前栈状态，做一番处理。具体看code



[Code]

1:    string decodeString(string s) {  
2:      stack<int> repeat_counts;  
3:      stack<string> pre_fix;  
4:        
5:      int num = 0;  
6:      string decoded = "";  
7:      string cur = "";  
8:        
9:      s = "1[" + s +"]"; // wrap the input into a bracket to simplify the logic  
10:      for(int i = 0; i< s.size(); i++) {  
11:        if(isdigit(s[i])) {  
12:          num = num*10 + s[i] -'0';  
13:          continue;  
14:        }  
15:          
16:        if(s[i] == '[') {  
17:          repeat_counts.push(num);  
18:          num = 0;  
19:          pre_fix.push(cur);  
20:          cur = "";  
21:          continue;  
22:        }  
23:          
24:        if(s[i] == ']') {  
25:          int repeat = repeat_counts.top();  
26:          repeat_counts.pop();  
27:          string prefix = pre_fix.top();  
28:          pre_fix.pop();  
29:            
30:          cur = prefix + repeatString(cur, repeat);  
31:          continue;  
32:        }  
33:          
34:        cur += s[i];  
35:      }  
36:        
37:      return cur;  
38:    }  
39:      
40:    string repeatString(string& organic, int repeats) {  
41:      string result = "";  
42:      for(int i =0; i< repeats; i++) {  
43:        result += organic;  
44:      }  
45:        
46:      return result;  
47:    }  

[Leetcode] Remove K Digits, Solution

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

[Thoughts]

首先分析一下什么样的数是最小的数。数总是有0~9的数字组成，高位的数字越小，这个数就越小。

所以，在对一个数做删除数字处理的时候，首先要从高位上把大的数字干掉，尽可能保留小的。

举个例子 num = "143219", k = 4

这个数字可以按照递增和递减分成三段 “1”， “4321”， “9”。递减子段上除了最后一个数字，其他的都可以被删除。

如果递减子段都处理完了，还没有删满k个，那就从最右边删（因为剩下的都是递增区间段了。）

[Code]

1:    string removeKdigits(string num, int k) {  
2:      string res = "";  
3:        
4:      for(int i =0; i<num.size(); i++) {  
5:        while(res.size()>0 && res.back() > num[i]&& k>0) {  
6:          res.pop_back();  
7:          k--;  
8:        }  
9:        res.push_back(num[i]);  
10:      }  
11:        
12:      // if k != 0, remove the digit from right  
13:      res.erase(res.size() - k, k);  
14:        
15:      // trim the zero  
16:      int i =0;  
17:      while(res[i] == '0' && i<res.size()-1) i++;  
18:        
19:      res.erase(0, i);  
20:        
21:      return res.size() == 0? "0": res;  
22:    }  

[LeetCode] Anagrams 解题报告

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

» Solve this problem

[解题思路]
对每一个字符串取水印，然后水印相同的即为anagrams。但是实现上倒是有个问题，最开始取水印的方式如代码中红字所示。但是对于超大字符串，也导致了超时。改为去一个整数hash，但是这种实现的风险是，hash值相同的不见得是anagrams。

目前想不出来好的实现。

[Code]

1:    vector<string> anagrams(vector<string> &strs) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<string> result;  
5:      if(strs.size() ==0) return result;  
6:      map<long, vector<string> > smap;  
7:      for(int i =0; i< strs.size(); i++)  
8:      {  
9:        smap[footprint(strs[i])].push_back(strs[i]);  
10:      }      
11:      for(map<long, vector<string> >::iterator it = smap.begin();  
12:      it!=smap.end(); ++it)  
13:      {  
14:        if(it->second.size() <=1)  
15:          continue;  
16:        result.insert(result.begin(), it->second.begin(), it->second.end());  
17:      }  
18:      return result;  
19:    }  
20:    long footprint(string str)  
21:    {  
22:      int index[26];  
23:      memset(index, 0, 26*sizeof(int));  
24:      for(int i = 0; i < str.size(); i++)   
25:      {   
26:        index[str[i]-'a']++;        
27:      }  
28:      /*string footp;  
29:      for(int i =0; i<26; i++)  
30:      {  
31:        footp.append(1,i+'a');  
32:        stringstream ss;   
33:        ss << index[i];  
34:        footp.append(ss.str());  
35:      }*/  
36:      long footp=0;  
37:      int feed =7;  
38:      for(int i =0; i< 26; i++)  
39:      {  
40:        footp= footp*feed +index[i];  
41:      }  
42:      return footp;   
43:    }   

[LeetCode] Add Binary 解题报告

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

» Solve this problem

[解题思路]
典型的实现题。没什么可说的。


[Code]
很少用c++，不查api库，不知道还有reverse这个方法。

1:    string addBinary(string a, string b) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      string result;  
5:      int maxL = a.size() > b.size()? a.size():b.size();  
6:      std::reverse(a.begin(), a.end());  
7:      std::reverse(b.begin(), b.end());  
8:      int carry=0;  
9:      for(int i =0; i<maxL;i++)  
10:      {  
11:        int ai = i<a.size()? a[i]-'0':0;  
12:        int bi = i<b.size()?b[i]-'0':0;  
13:        int val = (ai+bi+carry)%2;  
14:        carry = (ai+bi+carry)/2;  
15:        result.insert(result.begin(), val+'0');  
16:      }  
17:      if(carry ==1)  
18:      {  
19:        result.insert(result.begin(), '1');  
20:      }  
21:      return result;  
22:    }  

[Note]
在facebook见过一个扩展题就是，如果不是二进制而是16进制，如何扩展。在上面的code中很容易更改，将Line13及Line14 中的2改成16就可以了。

Update 3/1/2014
上一个version写的太复杂，string的reverse根本没必要。直接用两个index一起往前跑就好了。更新之。

1:    string addBinary(string a, string b) {  
2:      int carry =0;  
3:      string result;  
4:      for(int i = a.size()-1, j = b.size()-1; i >=0 || j>=0; --i,--j)  
5:      {  
6:        int ai = i>=0? a[i]-'0':0;  
7:        int bj = j>=0? b[j]-'0':0;  
8:        int val = (ai+bj+carry)%2;  
9:        carry = (ai+bj+carry) /2;  
10:        result.insert(result.begin(), val+'0');  
11:      }  
12:      if(carry ==1)  
13:      {  
14:        result.insert(result.begin(), '1');  
15:      }  
16:      return result;  
17:    }  

[LeetCode] ZigZag Conversion 解题报告

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

» Solve this problem

[解题思路]
数学题。巨无聊的一道题，真正面试过程中，不大可能出这种问题。
n=4
P              I              N
A         L  S         I   G
Y   A       H    R
P              I

N=5
P               H
A          S  I
Y      I       R
P   L          I      G
A              N

所以，对于每一层主元素(红色元素)的坐标 (i,j)= (j+1 )*n +i
对于每两个主元素之间的插入元素（绿色元素），(j+1)*n -i

[Code]

1:    string convert(string s, int nRows) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function    
4:      if(nRows <= 1) return s;  
5:      string result;  
6:      if(s.size() ==0) return result;  
7:      for(int i =0; i< nRows; i++)  
8:      {  
9:        for(int j =0, index =i; index < s.size();   
10:            j++, index = (2*nRows-2)*j +i)  
11:        {  
12:          result.append(1, s[index]);  //red element
13:          if(i ==0 || i == nRows-1)   //green element
14:          {            
15:            continue;  
16:          }  
17:          if(index+(nRows- i-1)*2 < s.size())  
18:          {  
19:            result.append(1, s[index+(nRows- i-1)*2]);  
20:          }  
21:        }  
22:      }  
23:      return result;  
24:    }  

[LeetCode] Wildcard Matching, Solution

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

» Solve this problem

[解题思路]
主要是*的匹配问题。p每遇到一个*，就保留住当前*的坐标和s的坐标，然后s从前往后扫描，如果不成功，则s++,重新扫描。

[Code]

1:    bool isMatch(const char *s, const char *p) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      bool star = false;  
5:      const char *str, *ptr;  
6:      for(str = s, ptr =p; *str!='\0'; str++, ptr++)  
7:      {  
8:        switch(*ptr)  
9:        {  
10:          case '?':  
11:            break;  
12:          case '*':  
13:            star =true;  
14:            s=str, p =ptr;  
15:            while(*p=='*')  
16:              p++;  
17:            if(*p == '\0') // 如果'*'之后，pat是空的，直接返回true  
18:              return true;  
19:            str = s-1;  
20:            ptr = p-1;  
21:            break;  
22:          default:  
23:          {  
24:            if(*str != *ptr)  
25:            {  
26:              // 如果前面没有'*'，则匹配不成功  
27:              if(!star)  
28:                return false;  
29:              s++;  
30:              str = s-1;  
31:              ptr = p-1;  
32:            }  
33:          }  
34:        }  
35:      }  
36:      while(*ptr== '*')  
37:        ptr++;  
38:      return (*ptr == '\0');  
39:    }  

[LeetCode] Valid Sudoku 解题报告

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

» Solve this problem

[解题思路]
实现题。先检查行列，再检查小9格。


[Code]

1:    bool isValidSudoku(vector<vector<char> > &board) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(board.size() == 0) return false;  
5:      int row[9], col[9];      
6:      for(int i =0; i<9; i++)  
7:      {  
8:        memset(row, 0, 9*sizeof(int));  
9:        memset(col, 0, 9*sizeof(int));  
10:        for(int j =0; j<9; j++)  
11:        {  
12:          if(board[i][j] != '.')  
13:          {   
14:            if(row[board[i][j]-49] ==1)  
15:              return false;  
16:            row[board[i][j]-49]++;  
17:          }  
18:          if(board[j][i] != '.')  
19:          {    
20:            if(col[board[j][i]-49] ==1)  
21:              return false;  
22:            col[board[j][i]-49]++;  
23:          }  
24:        }  
25:      }      
26:      for(int i =0; i< 9; i+=3)  
27:      {  
28:        for(int j =0; j<9; j+=3)  
29:        {  
30:          memset(row, 0, 9*sizeof(int));  
31:          for(int m=0; m<3; m++)  
32:          {  
33:            for(int n =0; n<3; n++)  
34:            {  
35:              if(board[m+i][n+j] == '.')  
36:                continue;  
37:              if(row[board[m+i][n+j]-49] ==1)  
38:                return false;  
39:              row[board[m+i][n+j]-49]++;  
40:            }  
41:          }  
42:        }  
43:      }  
44:      return true;  
45:    }  

[LeetCode] Valid Parentheses 解题报告

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

» Solve this problem

[解题思路]
经典的栈匹配。一个栈，左符号入栈，右符号出栈。最后检查栈是否为空。

[Code]

1:    bool isValid(string s) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<char> sta;  
5:      if(s.size() ==0) return false;  
6:      sta.push_back(s[0]);  
7:      for(int i =1; i< s.size(); i++)  
8:      {  
9:        if(s[i] == '(' || s[i] == '[' || s[i] == '{')  
10:        {  
11:          sta.push_back(s[i]);  
12:          continue;  
13:        }  
14:        char current = sta.back();  
15:        if(s[i] == ')' && current != '(')  
16:          return false;  
17:        if(s[i] == ']' && current != '[')  
18:          return false;  
19:        if(s[i] == '}' && current != '{')  
20:          return false;  
21:        sta.pop_back();  
22:      }  
23:      if(sta.size() !=0) return false;  
24:      return true;  
25:    }  

[LeetCode] Text Justification 解题报告

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Corner Cases:

• A line other than the last line might contain only one word. What should you do in this case?
  In this case, that line should be left-justified.

» Solve this problem

[解题思路]
实现题，非算法题。但是写出来还真挺麻烦。这道题草稿只花了不到20分钟，但是让它能正确运行通过测试数据，我花了一个小时。

[Code]

1:       vector<string> fullJustify(vector<string> &words, int L) {   
2:            vector<string> result;   
3:            if(0 == words.size()) return result;     
4:            int i =0;   
5:            while(i< words.size())   
6:            {   
7:                 int start = i;   
8:                 int sum = 0;   
9:                 while(i<words.size() && sum + words[i].size()<=L)   
10:                 {   
11:                      sum+=words[i].size() +1;   
12:                      i++;   
13:                 }   
14:                 int end = i-1;    
15:                 int intervalCount = end - start;   
16:                 int avgSp = 0, leftSp = 0;   
17:                 if(intervalCount >0)   
18:                 {   
19:                      avgSp = (L-sum + intervalCount+1)/intervalCount;   
20:                      leftSp = (L-sum + intervalCount+1)%intervalCount;   
21:                 }      
22:                 string line;      
23:                 for(int j = start; j<end; j++)   
24:                 {   
25:                      line+=words[j];   
26:                      if(i == words.size()) // the last line  
27:                      line.append(1, ' ');   
28:                      else   
29:                      {   
30:                           line.append(avgSp, ' '); //average space  
31:                           if(leftSp>0) // the extra space  
32:                           {   
33:                                line.append(1, ' ');   
34:                                leftSp--;   
35:                           }   
36:                      }   
37:                 }   
38:                 line+=words[end];   
39:                 if(line.size()<L)   
40:                      line.append(L-line.size(), ' ');   
41:                 result.push_back(line);      
42:            }   
43:            return result;   
44:       }