Code Ganker: Reverse Integer -- LeetCode

Code Ganker: Reverse Integer -- LeetCode: 原题链接: http://oj.leetcode.com/problems/reverse-integer/ 这道题思路非常简单，就是按照数字位反转过来就可以，基本数字操作。但是这种题的考察重点并不在于问题本身，越是简单的题目越要注意细节，一般来说整数的处理问题要注意的有两点...

4Sum

    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > ret;
        if(num.size()<4)
            return ret;
        sort(num.begin(),num.end());
        for(int i=0;i<num.size()-3;i++){
            if(i>0&&num[i]==num[i-1]) continue;
            for(int j=i+1;j<num.size()-2;j++){
                if(j>i+1&&num[j]==num[j-1]) continue;
                int l=j+1,r=num.size()-1;
                while(l<r){
                    int sum=num[i]+num[j]+num[l]+num[r];
                    if(sum>target)
                        r--;
                    else if(sum<target)
                        l++;
                    else{
                        vector<int> tmp;
                        tmp.push_back(num[i]);tmp.push_back(num[j]);tmp.push_back(num[l]);tmp.push_back(num[r]);
                        ret.push_back(tmp);
                        do{l++;}while(l<r&&num[l]==num[l-1]);
                        do{r--;}while(l<r&&num[r]==num[r+1]);
                    }                       
                }

            }
        }
        return ret;
    }

3Sum Closest

// similar to threeSum   
int threeSumClosest(vector<int> &num, int target) {
   
        if(num.size()<3)
            return 0;
        sort(num.begin(),num.end());
        int ret=num[0]+num[1]+num[2];
        for (int i=0;i<num.size()-2;i++)
        {
            // remove duplicates 
            if(i>0&&num[i]==num[i-1])
                continue;
            int start=i+1;
            int end=num.size()-1;
            while(start<end)
            {
                int sum=num[i]+num[start]+num[end];
                if(abs(sum-target)<abs(ret-target))
                {
                    ret=sum;
                }
                if(sum>target)
                {
                    end--;
                }
                else if(sum<target)
                {
                    start++;
                }
                else
                {
                    return target;
                }
   
            }
        }
        return ret; 
    }

3Sum

//O(n^2)
vector<vector<int> > threeSum(vector<int> &num) {
    vector<vector<int> > ret;
    if(num.size()<3)
        return ret;
    sort(num.begin(),num.end());
    for (int i=0;i<num.size()-2&&num[i]<=0;i++)
    {
        // remove duplicates 
        if(i>0&&num[i]==num[i-1])
            continue;
        int start=i+1;
        int end=num.size()-1;
        while(start<end)
        {
            int sum=num[i]+num[start]+num[end];
            if(sum<0)
            {
                start++;
            }
            else if(sum>0)
            {
                end--;
            }
            else
            {
                vector<int> temp;
                temp.push_back(num[i]);temp.push_back(num[start]);temp.push_back(num[end]);
                ret.push_back(temp);
                // move the left pointer to right and skip duplicates; 
                do{start++;}while(start<end&&num[start]==num[start-1]);
                do{end--;}while(start<end&&num[end]==num[end+1]);
            }

        }
    }
    return ret;
}

Anagrams

vector<string> anagrams(vector<string> &strs) {
    vector<string> ret;
    map<string, vector<string>> dict;
    vector<string>::iterator st;
    for(st=strs.begin();st!=strs.end();st++)
    {
        string key=*st;
        sort(key.begin(),key.end());
        dict[key].push_back(*st);
    }
    map<string, vector<string>> ::iterator it;
    for (it=dict.begin();it!=dict.end();it++)
    {
        if (it->second.size()>1)
        {
            for (st=it->second.begin();st!=it->second.end();st++)
            {
                ret.push_back(*st);
            }
        }
    }
    return ret;
}

two sum

			Solution:1. hashmap, O(n).	2. sort first. O(nlog n)
		vector<int> twoSum(vector<int> &numbers, int target) {     map<int,int> myMap;     vector<int> ret;     for (int i=0;i<numbers.size();i++)     {         if(myMap.count(numbers[i])==0)             myMap[numbers[i]]= i;         if(myMap.count(target-numbers[i]))         {             int l=myMap[target-numbers[i]];             if(l<i)             {                 ret.push_back(l+1);                 ret.push_back(i+1);                 return ret;             }         }     } } //sort method, by anniekim bool compare(pair<int, int> a, pair<int, int> b) {     return a.first < b.first; } vector<int> twoSum(vector<int> &numbers, int target) {     vector<pair<int, int>> nums(numbers.size());     for (int i = 0; i < numbers.size(); ++i)         nums[i] = make_pair(numbers[i], i+1);     sort(nums.begin(), nums.end(), compare);     int l = 0, r = nums.size() - 1;     while (l < r)     {         int sum = nums[l].first + nums[r].first;         if (sum == target) break;         else if (sum < target) l++;         else r--;     }     vector<int> res;     res.push_back(min(nums[l].second, nums[r].second));     res.push_back(max(nums[l].second, nums[r].second));     return res; }

Word Ladder II

 http://www.cnblogs.com/shawnhue/archive/2013/06/05/leetcode_126.html
niaokedaoren的方案中使用了一个前驱单词表，即记录每一个单词的前驱单词是哪些。这样在遍历完毕后，我们从end出发递归就能把所有路径生成出来。但是由于前驱单词表不能记录当前的层次信息，似乎我们没法完成去重的工作。这个方案的巧妙之处就在于它没有使用我们通常的队列保存待处理的单词，一个单词一个单词先进先出处理的方法，而是使用两个vector来模拟队列的操作。我们从vector 1中遍历单词进行转换尝试，发现能转换的单词后将其放入vector 2中。当vector 1中的单词处理完毕后即为一层处理完毕，它里面的单词就可以从字典里删去了。接着我们对vector 2进行同样处理，如此反复直到当前处理的vector中不再有单词。我们发现vector 1和vector 2在不断地交换正处理容器和待处理容器的身份，因此可以通过将其放入一个数组中，每次循环对数组下标值取反实现身份的交替.


class Solution {
    public:
    std::vector<std::vector<std::string> > findLadders(std::string start, std::string end, std::unordered_set<std::string> &dict)
    {
       
        result_.clear();
        dict.insert(start);
        dict.insert(end);
        std::unordered_map<std::string, std::vector<std::string>> prevMap;
       
        for(auto iter = dict.begin(); iter != dict.end(); ++iter)
        {
            prevMap[*iter] = std::vector<std::string>();
        }
       
        std::vector<std::unordered_set<std::string>> candidates(2);

// 为什么要用set 来存储，有讲究吗？
//我是这么考虑的，因为当前一层的某些节点可以从前一层的多个节点到达.

//用set,这样bfs的时候，多次加入这些节点，就没有事情了。

       
        int current = 0;
        int previous = 1;
       
        candidates[current].insert(start);
       
        while(true)
        {
            current = !current;
            previous = !previous;
           
            for (auto iter = candidates[previous].begin(); iter != candidates[previous].end(); ++iter)
            {
                dict.erase(*iter);
            }
           
            candidates[current].clear();
           
            for(auto iter = candidates[previous].begin(); iter != candidates[previous].end(); ++iter)
            {
                std::string word = *iter;
                for(size_t pos = 0; pos < iter->size(); ++pos)
                {
                    char before=word[pos];
                    for(char i = 'a'; i <= 'z'; ++i)
                    {
                        if(before == i)
                        {
                            continue;
                        }
                       
                        word[pos] = i;
                       
                        if(dict.count(word) > 0)
                        {
                            prevMap[word].push_back(*iter);
                            candidates[current].insert(word);
                        }
                    }
                    word[pos]=before;
                }
            }
           
            if (candidates[current].size() == 0)
            {
                return result_;
            }
            if (candidates[current].count(end))
            {
                break;
            }
        }
       
       
        std::vector<std::string> path;
        GeneratePath(prevMap, path, end);
       
        return result_;
    }
   
private:
    void GeneratePath(std::unordered_map<std::string, std::vector<std::string>> &prevMap, std::vector<std::string>& path,
                      const std::string& word)
    {
        if (prevMap[word].size() == 0)
        {
            path.push_back(word);
            std::vector<std::string> curPath = path;
            reverse(curPath.begin(), curPath.end());
            result_.push_back(curPath);
            path.pop_back();
            return;
        }
       
        path.push_back(word);
        for (auto iter = prevMap[word].begin(); iter != prevMap[word].end(); ++iter)
        {
            GeneratePath(prevMap, path, *iter);
        }
        path.pop_back();
    }
   
    std::vector<std::vector<std::string>> result_;
};


 //by anniekim, almost the same as the above code

class Solution {
    public:
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        map<string, vector<string>> traces; // If A->C and B->C, then traces[C] contains A and B.
        // This is used for recovering the paths.
        vector<unordered_set<string>> level(2);
        int cur = 0;
        int prev = 1;
        level[cur].insert(start);
        dict.insert(end);
        while (true)
        {
            prev = !prev;
            cur = !cur;
            level[cur].clear();
            // remove visited words. IMPORTANT!
            for (unordered_set<string>::iterator it = level[prev].begin(); it != level[prev].end(); ++it)
                dict.erase(*it);
            for (unordered_set<string>::iterator it = level[prev].begin(); it != level[prev].end(); ++it)
            {
                string word = *it;
                for (size_t i = 0; i < word.size(); i++) {
                    char before = word[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == before)
                            continue;
                        word[i] = c;
                        if (dict.find(word) != dict.end()) {
                            traces[word].push_back(*it);
                            level[cur].insert(word);
                        }
                    }
                    word[i] = before;
                }
            }
            if (level[cur].empty() || level[cur].count(end) > 0)
                break;
        }
        vector<vector<string>> res;
        vector<string> onePath;
        if (!traces.empty())
            buildResult(traces, res, onePath, end);
        return res;
    }
    void buildResult(map<string, vector<string>> &traces, vector<vector<string>> &res, vector<string> &onePath, string word)
    {
        if (traces.count(word) == 0)
        {
            vector<string> copy(onePath);
            copy.push_back(word);
            reverse(copy.begin(), copy.end());
            res.push_back(copy);
            return;
        }
        const vector<string> &s = traces[word];
        onePath.push_back(word);
        for (vector<string>::const_iterator it = s.begin(); it != s.end(); ++it)
            buildResult(traces, res, onePath, *it);
        onePath.pop_back();
    }

};

Palindrome Partitioning II -interesting

 //there is a related problem: longest palindrome substring
Note that in the following solution, to accommodate the dp computation of palin, we define dp[i] to be the mincut for the substring from i to the end.
     int minCut(string str) {
        int leng = str.size();

        int dp[leng+1];
        bool palin[leng][leng];

      for(int i = 0; i <= leng; i++)
        dp[i] = leng-i-1;
      for(int i = 0; i < leng; i++)
          for(int j = 0; j < leng; j++)
                palin[i][j] = false;

      for(int i = leng-1; i >= 0; i--){
        for(int j = i; j < leng; j++){
          if(str[i] == str[j] && (j-i<2 || palin[i+1][j-1])){
            palin[i][j] = true;
            dp[i] = min(dp[i],dp[j+1]+1);
          }
        }
      }
      return dp[0];
    }

 //one dimension dp, by anniekim
   int minCut(string s) {
        int N = s.size();
        bool isP[N];
        int dp[N];
        dp[0] = 0;
        for (int i = 1; i < N; ++i)
        {
            isP[i] = true;
            dp[i] = dp[i-1] + 1;
            for (int j = 0; j < i; ++j)
            {
                isP[j] = (s[i] == s[j]) ? isP[j+1] : false; // isP[j] == true -> [j...i] is a palindrome
                                                            // isP[j+1] == true -> [j+1...i-1] is a palindrome
                if (isP[j])
                    dp[i] = (j == 0) ? 0 : min(dp[i], dp[j-1] + 1); // dp[i] -> minCount for [0...i]
            }
        }
        return dp[N-1];
    }

Palindrome Partitioning

//dfs, backtraking

    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> part;
        partitionRe(s, 0, part,res);
        return res;
    }
    void partitionRe(const string &s, int start, vector<string> &part,vector<vector<string>> &res) {
        if (start == s.size())
        {
            res.push_back(part);
            return;
        }
        string palindrom;
        for (int i = start; i < s.size(); ++i) {
            palindrom.push_back(s[i]);
            if (!isPalindrome(palindrom)) continue;
            part.push_back(palindrom);
            partitionRe(s, i + 1, part,res);
            part.pop_back();
        }
    }
    bool isPalindrome(const string &s) {
        int i = 0, j = s.size()-1;
        while (i < j) {
        if (s[i] != s[j]) return false;
        i++; j--;
        }
        return true;
    }

Maximal Rectangle -interesting

three methods are provided.

//first, using largestRectangleArea

    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int N=matrix.size();
        int M=matrix[0].size();
        int ret=0;
        vector<int> height(M+1,0);
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++)
                height[j]=matrix[i][j]=='0'?0:height[j]+1;
            ret=max(ret,largestRectangleArea(height));   
        }
        return ret;   
    }
    int largestRectangleArea(const vector<int>& height){
        int N=height.size();
        int i=0;
        int ret=0;
        stack<int> stk;
        while(i<N){
            if(stk.empty()||height[stk.top()]<=height[i])
                stk.push(i++);
            else{
                int index=stk.top();stk.pop();
                int width=stk.empty()?i:i-(stk.top()+1);
                ret=max(ret,width*height[index]);
            }   
        }
        return ret;
    }

//second
    int maximalRectangle(vector<vector<char> > &matrix) {
        int num_i=matrix.size();
        if (num_i==0) return 0;
        int num_j=matrix[0].size();
        if (num_j==0) return 0;
        vector<vector<int>> max_x(num_i,vector<int>(num_j,0));  //number of consecutive 1s to the left of matrix[i][j], including itself

        int area=0;
        for (int i=0;i<num_i;i++){
            for (int j=0;j<num_j;j++){
                if (matrix[i][j]=='1'){
                    if (j==0) max_x[i][j]=1;
                    else max_x[i][j]=max_x[i][j-1]+1;
                    int y=1;
                    int x=num_j;
                    while((i-y+1>=0)&&(matrix[i-y+1][j]=='1')){
                        x=min(x, max_x[i-y+1][j]);
                        area=max(area,x*y);
                        y++;
                    }
                }
            }
        }

        return area;
    }

//third, most efficient, but a little hard to understand

http://hi.baidu.com/mzry1992/item/030f9740e0475ef7dc0f6cba

Case 1 -- matrix(i, j) = 1
H(i, j) = H(i-1, j) + 1
L(i, j) = max( L(i-1, j), the position of the left  nearest 0 in this row )
R(i, j) = min( R(i-1, j), the position of the right nearest 0 in this row )

Case 2 -- matrix(i, j) = 0
H(i, j) = 0
L(i, j) = 0
R(i, j) = n

 //
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty()) {
            return 0;
        }

        int n = matrix[0].size();
        vector<int> H(n);
        vector<int> L(n);
        vector<int> R(n, n);

        int ret = 0;
        for (int i = 0; i < matrix.size(); ++i) {
            int left = 0, right = n;
            // calculate L(i, j) from left to right
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    ++H[j];
                    L[j] = max(L[j], left);
                }
                else {
                    left = j+1;
                    H[j] = 0; L[j] = 0; R[j] = n;
                }
            }
            // calculate R(i, j) from right to right
            for (int j = n-1; j >= 0; --j) {
                if (matrix[i][j] == '1') {
                    R[j] = min(R[j], right);
                    ret = max(ret, H[j]*(R[j]-L[j]));
                }
                else {
                    right = j;
                }
            }
        }

        return ret;
    }

Largest Rectangle in Histogram

//by anniekim
// Keep a non-descending stack. O(n).
to help understanding, a picture in http://fisherlei.blogspot.com/2012/12/leetcode-largest-rectangle-in-histogram.html?spref=bl

    int largestRectangleArea(vector<int> &height) {
        height.push_back(0);
        stack<int> aStack;
        int res=0, i=0, N=height.size();
        while(i<N){
            if(aStack.empty()||height[aStack.top()]<=height[i])
                aStack.push(i++);
            else{//compute the area of  rectangle that column index can cover
                int index=aStack.top();aStack.pop();
                int width=aStack.empty()?i:i-aStack.top()-1;
                res=max(res,width*height[index]);
            }   
        }
        return res;
    }

Add Two Numbers

 //by anniekim

    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode dummy(0), *cur = &dummy;
        int carry = 0;
        while (l1 || l2 || carry){
            int sum = carry;
            if (l1) {
            sum += l1->val;
            l1 = l1->next;
            }
            if (l2) {
            sum += l2->val;
            l2 = l2->next;
            }
            carry = sum >= 10 ? 1 : 0;
            sum %= 10;
            ListNode *newNode = new ListNode(sum);
            cur->next = newNode;
            cur = newNode;
        }
        return dummy.next;
    }

Add Binary

    string addBinary(string a, string b) {
        int N = a.size(), M = b.size(), K = max(N, M);
        string res(K, ' ');
        int carry = 0;
        int i = N-1, j = M-1, k = K-1;
        while (i >= 0 || j >= 0)
        {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            carry = sum / 2;
            res[k--] = sum % 2 + '0';
        }
        if (carry == 1)
        res.insert(res.begin(), '1');
        return res;   
    }

plus one

    vector<int> plusOne(vector<int> &digits) {
        int i=digits.size()-1;
        int carry=1;
        while(i>=0&&carry){
            int sum=digits[i]+carry;
            carry=sum/10;
            digits[i]=sum%10;
            i--;
        }
        if(carry)
            digits.insert(digits.begin(),1);
        return digits;   
    }

Longest Palindromic Substring

first method: dp

    string longestPalindrome(string s) {
        if(s.length()==0)
            return "";
        bool palin[1000][1000] = {false};
        int maxLen = 0;
        int maxstart=0;
        for(int i=s.length()-1;i>=0;i--)
        {
            for(int j=i;j<s.length();j++)
            {
                if(s[i]==s[j] && (j-i<=2 || palin[i+1][j-1]))
                {
                    palin[i][j] = true;
                    if(maxLen<j-i+1)
                    {
                        maxLen=j-i+1;
                        maxstart=i;
                    }
                }
            }
        }
        return s.substr(maxstart,maxLen); 
    }

second method: Time O(n), Space O(n) (Manacher's Algorithm)
 the code is generally adopted from leetcode, but i have changed a little to satisfy my understanding.  There is another flavor written by anniekim.

string preProcess(const string &s) {
  int n = s.length();

  string ret;
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);

  ret += "#";
  return ret;
}

string longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  int *P = new int[n];
  int C = 0, R = 0;
  for (int i = 0; i < n; i++) {
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)
   
    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
   
    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])//actually need to check if the index is in the range.
      P[i]++;

    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }

  // Find the maximum element in P.
  int maxLen = 0;
  int centerIndex = 0;
  for (int i = 0; i < n; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  delete[] P;
 
  return s.substr((centerIndex  - maxLen)/2, maxLen);
}

Multiply Strings

two flavors of code are provided.

//first one
    string multiply(string num1, string num2) {
    int lenA = num1.length();
    int lenB = num2.length();
    string ret;

    int i, j;


    int* c = new int[lenA + lenB];
    memset(c, 0, sizeof(int) * (lenA+lenB));

    for (i = lenA - 1; i >= 0; i--)
        for (j = lenB - 1; j >= 0; j--)                   
            c[i + j + 1] += (num2[j] - '0') * (num1[i] - '0');

    for (i = lenA + lenB - 1; i >= 0; i--)
    {
        if (c[i] >= 10)
        {
            c[i - 1] += c[i] / 10;
            c[i] %= 10;
        }
    }
       
    i = 0;
    while ((i < lenA + lenB)&&c[i] == 0)
        i++;
   
    if(i==(lenA+lenB))
        ret="0";
   
    while (i < lenA + lenB)
    {
        ret.push_back(c[i] + '0');
        i++;
    }


    delete[] c; 
    return ret;
    }

//second one, by anniekim

string multiply(string num1, string num2) {     int N = num1.size(), M = num2.size();     string res(N+M, '0');     for (int i = N - 1; i >= 0; --i)     {         int carry = 0;         for (int j = M - 1; j >= 0; --j)         {             int sum = carry + (res[i+j+1] - '0') +                 (num1[i] - '0') * (num2[j] - '0');             res[i+j+1] = sum % 10 + '0';             carry = sum / 10;         }         res[i] += carry;     }     while (res.size() > 1 && res[0] == '0')         res.erase(res.begin());     return res; }

Maximum Product Subarray

dp, three flavors of code are provided:

    //f[k] means maximum product that can be achieved ending with k
    //g[k] means minimum product that can be achieved ending with k

f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )
g(k) = min( f(k-1) * A[k], A[k], g(k-1) * A[k] )

     int maxProduct3(int  A[],int n) {
        if (n<1)  return 0;
   
        vector<int> f(n,0),g(n,0);
        f[0] = A[0];
        g[0] = A[0];
        int res = A[0];
        for (int i = 1; i < n; i++) {
            f[i] = max(max(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
            g[i] = min(min(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
            res = max(res, f[i]);
        }
        return res;
    }

//convert the above one to use less space
    int maxProduct(int A[], int n) {
         if (n<1)  return 0;

        int f= A[0];
        int g= A[0];
        int res = A[0];
        for (int i = 1; i < n; i++) {
            int tmp=f;
            f = max(max(f * A[i], g* A[i]), A[i]);
            g = min(min(tmp * A[i], g* A[i]), A[i]);
            res = max(res, f);
        }
        return res;      
    }

//other flavors
    int maxProduct11(int A[], int n) {
        if (n < 1) return 0;
        int r = A[0];
        int max_p = A[0];
        // max_p is the maximum product that could be achieved
        // from the subarrays ending at the current position.
        int min_p = A[0];
        // The minimum product that could be achieved from
        // the subarrays ending at the current position.
        for(int i=1; i<n; i++){
            // The maximum or minimum product of the subarrays
            // ending at the current position could be achieved from the next three values.
            int a = max_p*A[i];
            // the max product of subarray ending at the previous position multiply the current value
            int b = min_p*A[i];
            // the minimum product of subarray ending at the previous position multiply the current value
            int c = A[i];
            // the current value
            max_p = max(max(a,  b),  c);
            min_p = min(min(a,  b),  c);
            if (max_p > r) r = max_p;
        }
        return r; 
    }
    //same idea way 2
    int maxProduct(int A[], int n) {
    if(n==1) return A[0];
    int pMax=0, nMax=0, m = 0;
    for(int i=0; i<n; i++){
        if(A[i]<0) swap(pMax, nMax);
        pMax = max(pMax*A[i], A[i]);
        nMax = min(nMax*A[i], A[i]);
        m = max(m, pMax);
    }
    return m;
    }

Code Ganker: ZigZag Conversion -- LeetCode

Code Ganker: ZigZag Conversion -- LeetCode: 原题链接: http://oj.leetcode.com/problems/zigzag-conversion/ 这道题是cc150里面的题目了，其实比较简单，只要看出来他其实每个zigzag是2*m-2个字符就可以，这里m是结果的行的数量。接下来就是对于每一行先把往下走的那...

Code Ganker: Word Ladder -- LeetCode

Code Ganker: Word Ladder -- LeetCode: 原题链接: http://oj.leetcode.com/problems/word-ladder/ 这道题看似一个关于字符串操作的题目，其实要解决这个问题得用图的方法。我们先给题目进行图的映射，顶点则是每个字符串，然后两个字符串如果相差一个字符则我们进行连边。接下来看看这个...

Code Ganker: Unique Paths II -- LeetCode

Code Ganker: Unique Paths II -- LeetCode: 原题链接: http://oj.leetcode.com/problems/unique-paths-ii/ 这道题跟 Unique Paths 非常类似，只是这道题给机器人加了障碍，不是每次都有两个选择（向右，向下）了。因为有了这个条件，所以 Unique Paths 中最...

Code Ganker: Unique Paths -- LeetCode

Code Ganker: Unique Paths -- LeetCode: 原题链接: http://oj.leetcode.com/problems/unique-paths/ 这道题是比较典型的动态规划的题目。模型简单，但是可以考核动态规划的思想。 我们先说说brute force的解法，比较容易想到用递归，到达某一格的路径数量等于它的上面和左...

Trapping Rain Water

 基本思路是这样的，用两个指针从两端往中间扫，在当前窗口下，如果哪一侧的高度是小的，那么从这里开始继续扫，如果比它还小的，肯定装水的瓶颈就是它了， 可以把装水量加入结果，如果遇到比它大的，立即停止，重新判断左右窗口的大小情况，重复上面的步骤。这里能作为停下来判断的窗口，说明肯定比前面的大了， 所以目前肯定装不了水（不然前面会直接扫过去）。这样当左右窗口相遇时，就可以结束了，因为每个元素的装水量都已经记录过了。代码如下：
int trap(int A[], int n) {
    int i = 0, j = n-1;
    int volume = 0;       
    int k = 0;
    while (i < j) {
        if (A[i] <= A[j]) {
            k = i+1;
            while (A[i] > A[k]) {
                volume += (A[i]-A[k]);
                k++;
            }
            i = k;
        }
        else {
            k = j-1;
            while (A[j] > A[k]) {
                volume += (A[j]-A[k]);
                k--;
            }
            j = k;
        }
    }  
    return volume;       
}


//method 2, by anniekim.
DP solution: Find left bound and right bound for each element. O(n).

int trap(int A[], int n) {
    if (n == 0) return 0;
    vector<int> maxLeft(n,0);
    vector<int> maxRight(n,0);
    maxLeft[0] = A[0];
    maxRight[n - 1] = A[n - 1];
    for (int i = 1; i < n; ++i) {
        maxLeft[i] = max(maxLeft[i - 1], A[i]);
        maxRight[n - 1 - i] = max(maxRight[n - i], A[n - 1 - i]);
    }
    int res = 0;
    for (int i = 1; i < n; ++i) {
        res += min(maxLeft[i], maxRight[i]) - A[i];
    }
    return res;
}

Code Ganker: Binary Tree Zigzag Level Order Traversal -- LeetCo...

Code Ganker: Binary Tree Zigzag Level Order Traversal -- LeetCo...: 原题链接: http://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ 这道题其实还是树的层序遍历 Binary Tree Level Order Traversal ，如果不熟悉的朋友可...

Best Time to Buy and Sell Stock III

 [Thoughts]
One dimensional dynamic planning.
Given an i, split the whole array into two parts:
[0,i] and [i+1, n], it generates two max value based on i, Max(0,i) and Max(i+1,n)
So, we can define the transformation function as:
Maxprofix = max(Max(0,i) + Max(i+1, n))  0<=i<n
------------------------------------------------------------
先从前往后找出每个i（i>0)之前（包括此位置）交易所有可能最大profit值，记录为 max_left[i].
在从后往前找出每个位置之后交易所有可能最大profit值，记录为 max_right[i].
接下来就简单了。一个for loop 解决问题。

 Solution: dp. max profit = max { l2r[0...i] + r2l[i+1...N-1] }.
0 <= i <= N-1


    int maxProfit(vector<int> &prices) {
        int N = prices.size();
        if (N <= 1) return 0;
        
        int l2r[N], r2l[N];
        l2r[0] = 0;
        r2l[N-1] = 0;
        
        int minn = prices[0];
        for (int i = 1; i < N; ++i)
        {
            minn = min(minn, prices[i]);
            l2r[i] = max(l2r[i-1], prices[i] - minn);
        }
        
        int maxx = prices[N-1];
        for (int i = N-2; i >= 0; --i)
        {
            maxx = max(maxx, prices[i]);
            r2l[i] = max(r2l[i+1], maxx - prices[i]);
        }
        
        int res = l2r[N-1];
        for (int i = 0; i < N-1; ++i)
            res = max(res, l2r[i] + r2l[i+1]);
        return res;
    }

类比： 此题可以candy的次优解法对看：http://codeganker.blogspot.com/2014/03/candy-leetcode.html 

Code Ganker: Candy -- LeetCode

Code Ganker: Candy -- LeetCode: 原题链接: http://oj.leetcode.com/problems/candy/ 这道题用到的思路和 Trapping Rain Water 是一样的，用动态规划。基本思路就是进行两次扫描，一次从左往右，一次从右往左。第一次扫描的时候维护对于每一个小孩左边所需要最少的...

Candy

最优解法：
/*
方案 ：O(n)时间，O(1)空间。
不需要记录每个孩子得到的糖果数目，只需要记录前一个孩子得到的糖果candy和
当前孩子之前rating取极大值的孩子位置maxIndex，以及该位置上孩子的糖果数maxValue。
通过这个，就可以判断需不要补糖果，以及补几颗。
*/
    int candy(vector<int> &ratings) {
        int N = ratings.size();
        if (N == 0) return 0;
        int candy = 1, res = 1;
        int maxValue = 1, maxIndex = 0;
        for (int i = 1; i < N; ++i)
        {
            if (ratings[i] >= ratings[i-1])
            {
                candy = ratings[i] == ratings[i-1] ? 1 : candy + 1;
                maxValue = candy;
                maxIndex = i;
            }
            else
            {
                if (candy == 1) {
                    if (maxValue <= i - maxIndex) {
                        res += i - maxIndex;
                        maxValue++;
                    } else {
                        res += i - maxIndex - 1;
                    }
                }
                candy = 1;
            }
            res += candy;
        }
        return res;
    }

//another one


int candy_2(vector<int> &ratings) {
    int N = ratings.size();
    if (N == 0) return 0;
    int candy[N];
    for (int i = 0; i < N; ++i)
        candy[i] = 1;
    for (int i = 1; i < N; ++i)
        if (ratings[i] > ratings[i-1])
            candy[i] = candy[i-1] + 1;
    for (int i = N-2; i >= 0; --i)
        if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1])
            candy[i] = candy[i+1] + 1;
    int res = 0;
    for (int i = 0; i < N; ++i)
        res += candy[i];
    return res;
}

另外一种次优的解法：
http://codeganker.blogspot.com/2014/03/candy-leetcode.html

Code Ganker: Container With Most Water -- LeetCode

Code Ganker: Container With Most Water -- LeetCode: 原题链接: http://oj.leetcode.com/problems/container-with-most-water/ 首先一般我们都会想到brute force的方法，思路很简单，就是对每一对pair都计算一次容积，然后去最大的那个，总共有n*(n-1)/2对pa...

Median of Two Sorted Arrays

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = m + n;
        if (total & 0x1)
            return findKthSortedArrays(A, m, B, n, total / 2 + 1);
        else
            return (findKthSortedArrays(A, m, B, n, total / 2) + findKthSortedArrays(A, m, B, n, total / 2 + 1)) / 2;
    }

    double findKthSortedArrays(int A[], int m, int B[], int n, int k) {
        if(m>n)
            return findKthSortedArrays(B,n,A,m,k);
        if(m==0) return B[k-1];
        if(k==1) return min(A[0],B[0]);
        int i=min(k/2,m);
        int j=k-i;
        if(A[i-1]==B[j-1])
            return A[i-1];
        else if(A[i-1]>B[j-1])  
            return findKthSortedArrays(A,i,B+j,n-j,k-j);
        else
            return findKthSortedArrays(A+i,m-i,B,j,k-i);
    }



下面是同样的意思：http://codeganker.blogspot.com/2014/02/median-of-two-sorted-arrays-leetcode.html

这道题比较直接的想法就是用Merge Sorted Array这个题的方法把两个有序数组合并，当合并到第(m+n)/2个元素的时候返回那个数即可，而且不用把结果数组存起来。算法时间复杂度是O(m+n)，空间复杂度是O(1)。因为代码比较简单，就不写出来了，跟Merge Sorted Array比较类似，大家可以参照这个题目的解法。
接下来我们考虑有没有优化的算法。优化的思想来源于order statistics，在算法导论10.3节中提到。问题等价于求两个array的第k=(m+n)/2（假设m和n分别是两个数组的元素个数）大的数是多少。基本思路是每次通过查看两个数组的第k/2大的数(假设是A[k/2],B[k/2])，如果两个A[k/2]=B[k/2]，说明当前这个数即为两个数组剩余元素的第k大的数，如果A[k/2]>B[k/2], 那么说明B的前k/2个元素都不是我们要的第k大的数，反之则排除A的前k/2个，如此每次可以排除k/2个元素，最终k=1时即为结果。总的时间复杂度为O(logk),空间复杂度也是O(logk)，即为递归栈大小。在这个题目中因为k=(m+n)/2,所以复杂度是O(log(m+n))。比起第一种解法有明显的提高，代码如下：

public double findMedianSortedArrays(int A[], int B[]) {
    if((A.length+B.length)%2==1)
        return helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1);
    else
        return (helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2) 
               +helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1))/2.0;
}
private int helper(int A[], int B[], int i, int i2, int j, int j2, int k)
{
    int m = i2-i+1;
    int n = j2-j+1;
    if(m>n)
        return helper(B,A,j,j2,i,i2,k);
    if(m==0)
        return B[j+k-1];
    if(k==1)
        return Math.min(A[i],B[j]);
    int posA = Math.min(k/2,m);
    int posB = k-posA;
    if(A[i+posA-1]==B[j+posB-1])
        return A[i+posA-1];
    else if(A[i+posA-1]<B[j+posB-1])
        return helper(A,B,i+posA,i2,j,j+posB-1,k-posA);
    else
        return helper(A,B,i,i+posA-1,j+posB,j2,k-posB);
}

实现中还是有些细节要注意的，比如有时候剩下的数不足k/2个，那么就得剩下的，而另一个数组则需要多取一些数。但是由于这种情况发生的时候，不是把一个数组全部读完，就是可以切除k/2个数，所以不会影响算法的复杂度。
这道题的优化算法主要是由order statistics派生而来，原型应该是求topK的算法，这个问题是非常经典的问题，一般有两种解法，一种是用quick select(快速排序的subroutine),另一种是用heap。 复杂度是差不多的，有兴趣可以搜一下，网上资料很多，topK问题在海量数据处理中也是一个非常经典的问题，所以还是要重视。