Longest Substring Without Repeating Characters

       int lengthOfLongestSubstring(string s) {
        int n=s.length();
        int i=0,j=0,maxLen=0;
        bool exist[256]={false};
        while(j<n){
            if(exist[s[j]]){
                maxLen=max(maxLen,j-i);
                while(s[i]!=s[j]){
                    exist[s[i]]=false;
                    i++;
                }
                i++;
                j++;
            }
            else{
                exist[s[j]]=true;
                j++;
            }
        }
        return max(maxLen,n-i);
    }
 //same idea, more concise
 int lengthOfLongestSubstring(string s) {
           bool exist[256]={false};
        int res = 0;
        int start = 0, end = 0, N = s.size();
        while (end < N && start + res < N)
        {
            if (!exist[s[end]])
                exist[s[end++]] = true;
            else
                exist[s[start++]] = false;
            res = max(end - start, res);
        }
        return res;    
    }

Maximum Subarray

     int maxSubArray(int A[], int n) {
        vector<int > dp(n,0);
        dp[0]=A[0];
        int amax=A[0];
        for(int i=1;i<n;i++){
            dp[i]=A[i]+(dp[i-1]>0?dp[i-1]:0);
            amax=max(dp[i],amax);
        }
        return amax;
    }
 //less space
    int maxSubArray(int A[], int n) {
        int mx,pre;
        mx=pre=A[0];
        for(int i=1;i<n;i++){
            if(pre>0)
                {pre+=A[i];}
            else
                pre=A[i];
            if(pre>mx) mx=pre;   
        }
        return mx;       
    }

Word Break II

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        if (!wordBreakPossible(s, dict)) return res;
        wordBreakRe(s, dict, 0, "", res);
        return res;
    }
   
    void wordBreakRe(const string &s, const unordered_set<string> &dict,
                     int start, string sentence, vector<string> &res) {
        if (start == s.size()) {
            res.push_back(sentence);
            return;
        }
        if (start != 0) sentence.push_back(' ');
        for (int i = start; i < s.size(); ++i) {
            string word = s.substr(start, i-start+1);
            if (dict.find(word) == dict.end())
                continue;
            wordBreakRe(s, dict, i+1, sentence + word, res);
        }
    }
   
    bool wordBreakPossible(const string &s, const unordered_set<string> &dict) {
        int N = s.size();
        bool canBreak[N+1];
        memset(canBreak, false, sizeof(canBreak));
        canBreak[0] = true;
        for (int i = 1; i <= N; ++i) {
            for (int j = i-1; j >= 0; --j) {
                if (canBreak[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[N];
    }
};

//another flavor
class Solution {
public:
//From right to left, compute the start index such that the substring[start ,current] is in the dictionary. Then backtrace from the beginning.
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<list<int>> mark(s.length(),list<int>());
        for(int stop=s.length();stop>=0;stop--){
            if(stop<s.length()&&mark[stop].empty()) continue;
            for(int start=stop-1;start>=0;start--){
                if(dict.count(s.substr(start,stop-start)))
                    mark[start].push_back(stop);
            }
           
        }
           
        vector<string> result;
        collect(mark,0,s,"",result);
        return result;
   
    }
    void collect(vector<list<int>>& mark, int ind, const string& s,
                string path, vector<string>& result){
        for(auto& stop:mark[ind]){
            string sub =s.substr(ind,stop-ind);
            string newpath=path+(ind==0?sub:" "+sub);
            if(stop==s.length()) result.push_back(newpath);
            else collect(mark,stop,s,newpath,result);
        }           
   
    }
};

Word Break

    wordB[i] means whether the substring [0, i] is true.

bool wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> wordB(s.length() + 1, false);
        wordB[0] = true;
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (wordB[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    wordB[i] = true;
                    break;
                }
            }
        }
        return wordB[s.length()];
    }

Lowest Common Ancestor of a Binary Tree

geeksforgeeks

leetcode

Lowest Common Ancestor of  binary search tree


Lowest Common Ancestor of a Binary Tree with parent pointer:

way 1, use a hashmap to record a path to root until find a node that is already inserted in the map.
way 2, get the height of the two nodes, compute the difference.

Sqrt(x)

二分法。基本思路是跟二分查找类似，要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，直到左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。代码如下：

    int sqrt(int x) {
        if(x<0) return -1;
        if(x==0) return 0;
        int l=1,r=x/2+1;
        while(l<=r){
            int m=l+(r-l)/2;
            if(m<=x/m&&x/(m+1)<(m+1))
                return m;
            if(m<x/m)
                l=m+1;
            else r=m-1;   
        }
        return 0;
    }

//another flavor
    int sqrt(int x) {
      if(x<=1) return x;
   
      int left=0, right=x, mid;
   
      while( (right-left)>1 )
      {
        mid=left+(right-left)/2;
   
        if(mid==x/mid)
          return mid;
        else if(x/mid < mid)
          right=mid;
        else
          left=mid;
      }
   
      return left;

    }

Generate Parentheses

dfs backtracking  经验： 如果dfs函数的参数是pass by reference, 那么在递归调用后，要做恢复现场的工作，如下面函数中对com 和lcnt的操作。 如果dfs函数的参数是pass by value, 那么在递归调用后，就可以不用再作处理了，如flavor 3 中的参数。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        int lcnt=0;
        string com="";
        help(n,ret,com,lcnt);
        return ret;
    }
    void help(int n, vector<string>&ret, string&com, int &lcnt){
        if(lcnt<com.length()-lcnt||lcnt>n){
            return;
        }
        if(com.length()==2*n){
            ret.push_back(com);return;
        }
        com.push_back('(');
        lcnt++;
        help(n,ret,com,lcnt);
        com.pop_back();
        lcnt--;
        com.push_back(')');
        help(n,ret,com,lcnt);
        com.pop_back();//don't forget this!
    }
};

// flavor 2
class Solution {
public:
    vector<string> generateParenthesis(int n) {
       
        vector<string> ret;
        string com="";
        generateParenthesisRe(0,0,n,com,ret);
        return ret;
       
    }
   
    void generateParenthesisRe(int left, int right, int n,string& com,vector<string>&ret){
        if(left==n&&right==n){
            ret.push_back(com);
            return;
        }
        if(left>n||right>n)
            return;
        if(left>right){
            com.push_back('(');
            generateParenthesisRe(left+1,right,n,com,ret);
            com.pop_back();
            com.push_back(')');
            generateParenthesisRe(left,right+1,n,com,ret);
            com.pop_back();           
        }
        else if(left==right){
            com.push_back('(');
            generateParenthesisRe(left+1,right,n,com,ret);
            com.pop_back();
        }
           
    }
};

//flavor 3
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        generator(ret,"",0,0,n);
        return ret;
    } 
    void generator(vector<string> & ans, string s, int l, int r, int n){
   
        if(l>n||r>n)
            return;
        if(l==n&&r==n)
            ans.push_back(s);
        generator(ans,s+"(",l+1,r,n);
        if(l>r)
            generator(ans,s+")",l,r+1,n);
    }

};