215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array/

Solution:
Just for the purpose of practice, will use min heap data structure to solve this problem. Then the Kth largest element will be the root of a min heap with size of K.

Need to build a min Heap structure, and the key step is a shift function that will be used in both building and maintaining the heap. See below:

Code:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int l = nums.size();
        buildMinHeap(nums, k);
        for(int i=k; i<l; ++i){
            if(nums[i] > nums[0]){
                swap(nums[i], nums[0]);
                shiftHeap(nums, 0, k-1);
            }
        }
        return nums[0];
    }
private:
    void buildMinHeap(vector<int> &n, int l){
        for(int i=1; i<l; ++i){
            n.insert(n.begin(), n[i]);
            n.erase(n.begin()+i+1);
            shiftHeap(n, 0, i);  //maintain an ordered range 0-i;
        }
    }
    void shiftHeap(vector<int> &v, int m, int n){
        if(2*m+1 == n && v[m] > v[n]) swap(v[m], v[n]);//if 2*m + 1 > n, continue;
        if(2*m+2<=n && v[m] > min(v[2*m+1], v[2*m+2])){
            if(v[2*m+1] > v[2*m+2]){
                swap(v[m], v[2*m+2]);
                shiftHeap(v, 2*m+2, n);
            }
            else{
                swap(v[m], v[2*m+1]);
                shiftHeap(v, 2*m+1, n);
            }
        }
    }
};

211. Add and Search Word - Data structure design

https://leetcode.com/problems/add-and-search-word-data-structure-design/

Solution:
May use the prefix trie data structure. Then need DSF for the word searching. As long as there is one path is right, return true; otherwise, return false.

Code:

class WordDictionary {
public:
    struct TrieNode{
        bool end;
        vector<TrieNode*> children;
        TrieNode(): end(false), children(26, NULL) {}
    };
    
    WordDictionary(){//constructor;
        root = new TrieNode();
    }
    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode *t = root;
        for(auto a:word){
            if(!t->children[a-'a']) t->children[a-'a'] = new TrieNode();
            t = t->children[a-'a'];
        }
        t->end = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return swDSF(word, root, 0);
    }
    
    bool swDSF(string w, TrieNode* r, int i){
        if(i == w.size()) return r->end;
        if(w[i] == '.'){
             for(auto a:r->children){
                if(a && swDSF(w, a, i+1)) return true;
            }
            return false;
        }
        return r->children[w[i]-'a'] && swDSF(w, r->children[w[i]-'a'], i+1);
    }
    
private:
    TrieNode *root;
};
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

210. Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

Solution:
Need to build up the directed graph first. Then apply BSF strategy. Start with the zero-indegree (means no prerequisite is needed) elements, and gradually decease the indegrees of the elements that can now be partially accessed. Once the indegree becomes zero, it means it can be fully accessed. If all the elements can be accessed, the total number of them should be the total number of the courses. Or there should be cycle existed. And it is impossible to finish all the courses. Then return empty vector.
(update: the visit vector is not necessary, since inD has enough constrain to avoid duplicates.)

Code:

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> res, inD(numCourses, 0);
        vector<vector<int>> graph(numCourses, vector<int>(0));
        for(auto a:prerequisites){//build graph and indegrees;
            graph[a.second].push_back(a.first);
            ++inD[a.first];
        }
        vector<bool> visit(numCourses, true);
        queue<int> q;
        for(int i=0; i<numCourses; ++i){
            if(!inD[i]){
                q.push(i);
                res.push_back(i);
            } 
        }
        while(q.size()){
            int t = q.front();
            q.pop();
            for(auto a:graph[t]){
                if(visit[a] && inD[a] == 1){
                    res.push_back(a);
                    visit[a] = false;
                }
                --inD[a];
                if(!inD[a]) q.push(a);
            }
        }
        if(res.size()!=numCourses) res.clear();
        return res;
    }
}; 

http://dongxicheng.org/structure/trietree/

201. Bitwise AND of Numbers Range

https://leetcode.com/problems/bitwise-and-of-numbers-range/

Solution:

We need to find a way to reduce the time complexity. As indicated by the title, bitwise operation may be a choice. One way is to check the 1s and 0s at each bit (31 bits in total). For each bit, once 0 is found, then the final results at that bit will be 0 (bitwise AND).

But this still is not enough. Actually once the number on the higher edge has one bit that is 1 on the higher bits more than that of the lower edge, then all the bits will become 0 from AND. So we just need to find the locations of the highest bit that is 1 for both m and n. If the location of n is higher than that of m, the result will be 0. (we can also work on the lower side to figure out the highest location for the non-zero bits for both numbers, then the iteration can start from that bit to higher once. But for simplicity, I just set the out-layer loop starting from 0.)

One detail, when n is the INT_MAX, we cannot use it as the end condition for the for-loop (since it will trigger INT_MAX + 1). However, the good new is that INT_MAX itself has no constrain on AND at all. So once n is the maximum, we just need to set it to be INT_MAX - 1.

Code:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        if(n==INT_MAX) n = n-1;
        int res = 0;
        int l1 = 30, l2 = l1;// l1 is the highest "1" bit location for m; 
        while(l1>=0){
            if((1<<l1)&m) break;
            --l1;
        }
        while(l2>=0){// similar for l2 to n;
        if((1<<l2)&n) break;
            --l2;
        }
        if(l2>l1) return 0;
        for(int i=0; i<=l1; ++i){
            int t = (1<<i);
            for(int j=m; j<=n; ++j){
                t = t & j;
                if(!t) break;
            }
            res |= t;
        }
        return res;
    }
};  

187. Repeated DNA Sequences

https://leetcode.com/problems/repeated-dna-sequences/

Solution:

It is straightforward to use the "brute force" hash map method plus a sliding window with size of 10-letter. But something else can be applied to reduce the space complexity since it is too expensive when using string as the hash key.

We just need to distinguish four letters, so bitwise operation may be used and two bits are enough for four, i.e. 'A' can be 00, 'C' for 01, 'G' for 10, and 'T' for 11.

Two details need to consider:

1) : a mask may need to set all the bits beyond the first 20 from the left to be 0. (since we only need to consider the "10-letter" sub-sequences and each letter need 2 bits). 0xFFFFF represents the first 20 bits from the left are 1s, and all the rest are 0s. (F in hexadecimal is equivalent to 1111 in binary);

2): need to remove the possible duplicates. Can use set, but actually can also use hash map, see below.

Code:

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        unordered_map<char, int> m1{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        unordered_map<int, int> m2;
        int i = 0, t = 0, mask = 0xfffff;  // the lower 20 bits are 1s;
        while(i<9) t = (t<<2) + m1[s[i++]];
        while(i<s.size()){
            t = ((t<<2) & mask) | m1[s[i++]];
            if(m2.find(t) == m2.end()) m2[t] = 1;
            else{ 
                if(m2[t] == 1){
                    res.push_back(s.substr(i-10, 10));
                    m2[t] = 0;
                }
            }
        }
        return res;
    }
};

173. Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/

Solution:
Take a while to figure out what this question is for... (Originally thought it is for the "second" smallest element in the Tree...) OK, here it is. It will always find the next smallest element in the BST if it exists. So if it is called from the beginning until the end, the sequence output will be the elements sorted from mid-order traversal (left -> root -> right) of BST.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        TreeNode *r = root;
        while(r){
            s.push(r);
            r = r->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    int next() {
        TreeNode *t = s.top();
        int res = t->val;
        s.pop();
        if(t->right){
            t = t->right;
            while(t){
                s.push(t);
                t = t->left;
            }
        }
        return res;
    }
private:
    stack<TreeNode*> s;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */

http://www.cnblogs.com/grandyang/p/4231455.html

164. Maximum Gap

https://leetcode.com/problems/maximum-gap/

Solution:
Do not have any clue with O(n) for this problem until searching online... (the reference is listed at bottom).
Will use Bucket Sort (https://en.wikipedia.org/wiki/Bucket_sort). Here are the some key points:
1: the bucket size is equivalent to the average distance between elements; then the maximum gap must be between the adjacent non-empty buckets;
2: the first bucket and the last bucket must not be empty.

Code:

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int l = nums.size();
        if(l<2) return 0;
        int mx = INT_MIN, mn = INT_MAX;
        for(auto i:nums){
            mx = max(mx, i);
            mn = min(mn, i);
        }
        int bucket_size = (mx-mn)/l + 1;// average distance between elements.
        int bucket_num = (mx-mn)/bucket_size + 1;
        vector<int> bucket_mins(bucket_num, INT_MAX);
        vector<int> bucket_maxs(bucket_num, INT_MIN);
        for(auto i:nums){
            int index = (i-mn)/bucket_size;
            bucket_mins[index] = min(bucket_mins[index], i);
            bucket_maxs[index] = max(bucket_maxs[index], i);
        }
        int res = 0, ind_min = 1, ind_max = 0;//first bucket is not empty;
        while(ind_min<bucket_num){
            while(bucket_mins[ind_min] == INT_MAX ) ++ind_min; //last bucket is not empty;
            res = max(res, bucket_mins[ind_min]-bucket_maxs[ind_max]);
            ind_max = ind_min++;
        }
        return res;
    }
};

http://www.cnblogs.com/grandyang/p/4234970.html

143. Reorder List

https://leetcode.com/problems/reorder-list/

Solution:
May use two pointers, one is fast that move two nodes per time and the other is slow that move one per time. Then when the fast one reaches the end, the slow one reaches the middle. The next step is to divide the list into two lists: the first half and the second half. Reverse the second half, then merge them. (Seems not hard to understand, I think this question is designed for checking the details for implementation.)

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;
        ListNode *fast = head, *slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = reverseL(slow->next);
        slow->next = NULL; //must have!
        slow = head;
        while(slow && fast){
            ListNode *t = fast;
            fast = t->next;
            t->next = slow->next;
            slow->next = t;
            slow = t->next;
        }
    }
private:
    ListNode* reverseL(ListNode* h){
        if(!h || !h->next) return h;
        ListNode *dummy = new ListNode(-1);
        dummy->next = h;
        while(h && h->next){
            ListNode* p = h->next;
            h->next = p->next;
            p->next = dummy->next;
            dummy->next = p;
        }
        return dummy->next;
    }
}; 

139. Word Break

https://leetcode.com/problems/word-break/

Solution:
1) Brute force DSF Recursion. But will cause TLE (not surprisingly);
2) DP. Suppose dp[i] represents the true status (can be separated into words) of substring from 0 to i, then dp[i+1] will be true if both dp[j] and wordDict.find(s.substr(j, i+1-j)) are true for 0<= j <i. Similar dp argument can also applied from right to left, and actually this one can be used to reduce the time complexity for the next question (II) (the details for the implementation will be a little bit different, see below. And also dp[i] now means the substring from i to n can be segmented).

Code:
DSF Recursion:

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if(s.empty()) return false;
        if(wordDict.find(s) != wordDict.end()) return true;
        for(int i=0; i<s.size(); ++i){
            string t = s.substr(0, i+1);
            if(wordDict.find(t)) != wordDict.end() && wordBreak(s.substr(i+1), wordDict)) return true;
        }
        return false;
    }
};

DP: from left to right

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int l = s.size();
        if(!l) return false;
        vector<bool> dp(l+1, false);
        dp[0] = true;
        for(int i=1; i<=s.size(); ++i){
            for(int j=0; j<i; ++j){
                if(wordDict.find(s.substr(j, i-j)) != wordDict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[l];
    }
};

DP: from right to left

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int l = s.size();
        if(!l) return false;
        vector<bool> dp(l+1, false);
        dp[l] = true;
        for(int i=l-1; i>=0; --i){
            for(int j=l; j>i; --j){
                if(wordDict.find(s.substr(i, j-i)) != wordDict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
};

140. Word Break II

https://leetcode.com/problems/word-break-ii/

Solution:
May use DSF. In order to reduce the time complexity, we can pre-build a one dimensional array dp[i] to represents that the sub-string from i to n can be segmented into words.

Code:

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> res;
        int l = s.size(); 
        if(!l) return res;
        vector<bool> dp(l+1, false);
        dp[l] = true;
        for(int i=l-1; i>=0; --i){
            for(int j=l; j>i; --j){
                if(wordDict.find(s.substr(i, j-i)) != wordDict.end() && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        wBDSF(s, wordDict, dp, 0, "", res);
        return res;
    }
private:
    void wBDSF(string s, unordered_set<string> &w, vector<bool> &dp, int ind, string t, vector<string> &r){
        if(ind == s.size()) r.push_back(t);
        else{
            for(int i=ind; i<s.size(); ++i){
                string t1 = s.substr(ind, i-ind+1);
                if(w.find(t1) != w.end() && dp[i+1]){
                    wBDSF(s, w, dp, i+1, t.empty()?t+t1:t+" "+t1, r);
                }
            }
        }
    }
}; 

131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

Solution:
Consider to use DSF. The "end condition" or "basic case" is when the search reaches the end of the string. Also need to determine whether all the possible substrings are palindrome or not.

Code:

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        if(!s.size()) return res;
        vector<string> temp;
        vector<vector<bool>> isP(s.size(), vector<bool>(s.size(), false));
        for(int i=s.size()-1; i>=0; --i){//DP for judging palindrome;
            for(int j=i; j<s.size(); ++j){
                if(s[i]==s[j] && (j-i<=2 || isP[i+1][j-1])) isP[i][j] = true;
            }
        }
        pDSF(s, 0, temp, isP, res);
        return res;
    }
private:
    void pDSF(string s, int ind, vector<string> &t, vector<vector<bool>> &isP, vector<vector<string>> &r){
        if(ind == s.size()) r.push_back(t);
        else{
            for(int i=ind; i<s.size(); ++i){
                if(isP[ind][i]){
                    t.push_back(s.substr(ind, i+1-ind));
                    pDSF(s, i+1, t, isP, r);
                    t.pop_back();
                }
            }
        }
    }
};

130. Surrounded Regions

https://leetcode.com/problems/surrounded-regions/

Solution:
May use the breadth first search strategy. And the search will be easier if it starts from the edges towards the inside. A visit matrix will be used to track the position visited (an alternative way is to set value of the board[i][j] that can not be surrounded from 'O' to be some other value rather than 'O' or 'X').

Code:

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if(!m) return;
        int n = board.front().size();
        if(!n) return;
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j] == 'O' && !visit[i][j] && (i == 0 || i == m-1 || j == 0 || j == n-1))
                    sBSF(board, i, j, visit);
            }
        }
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(!visit[i][j] && board[i][j] == 'O') board[i][j] = 'X'; 
            }
        }
    }
private:
    void sBSF(vector<vector<char>> &b, int x, int y, vector<vector<bool>> &v){
        v[x][y] = true;
        queue<pair<int, int>> q; //for BSF;
        q.push(make_pair(x, y));
        while(q.size()){
            int x1 = q.front().first; //need to updated for each loop;
            int y1 = q.front().second; //same here;
            q.pop(); 
            if(x1-1>=0 && b[x1-1][y1] == 'O' && !v[x1-1][y1]){//left;
                v[x1-1][y1] = true;
                q.push(make_pair(x1-1, y1));
            }
            if(x1+1<b.size() && b[x1+1][y1] == 'O' && !v[x1+1][y1]){//right;
                v[x1+1][y1] = true;
                q.push(make_pair(x1+1, y1));
            } 
            if(y1-1>=0 && b[x1][y1-1] == 'O' && !v[x1][y1-1]){//up;
                v[x1][y1-1] = true;
                q.push(make_pair(x1, y1-1));
            } 
            if(y1+1<b.front().size() && b[x1][y1+1] == 'O' && !v[x1][y1+1]){//down;
                v[x1][y1+1] = true;
                q.push(make_pair(x1, y1+1));
            }
        }
    }
};

128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/

Solution:
My first response is to sort the array first, but this question requests time complexity of O(n). So we may need some help from data structures, like hash table, set, ... Will use hash table, first to built up hash table; then scan the array again, for each element, will check the existence its neighbor in value with the help of hash table built.  Then find the longest one to return.

Code:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_map<int, bool> m;
        for(auto i:nums) m[i] = true;//built up hash table (or map);
        for(auto i:nums){
            if(m[i]){
                int len = 1;
                int j = 1;
                while(m[i+j]){//search larger direction in value;
                    ++len;
                    m[i+j] = false;
                    ++j;
                }
                j = 1;
                while(m[i-j]){//search smaller direction in value;
                    ++len;
                    m[i-j] = false;
                    ++j;
                }
                m[i] = false;
                res = max(res, len);
            }
        }
        return res;
    }
}; 

127. Word Ladder

https://leetcode.com/problems/word-ladder/

Solution:
This question can be viewed as the most fundamental "breadth search first" (Breadth-first search - Wikipedia). The popular way to implement is using queue data structure to maintain each "level", as the search expands. For this question, a hash map can be used to store the "level" information.

Code: 

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        unordered_map<string, int> m;
        m[beginWord] = 1;
        queue<string> q;
        q.push(beginWord);
        while(!q.empty()){
            string s = q.front();
            q.pop();
            for(int i=0; i<s.size(); ++i){
                string s1 = s;
                for(int cr='a'; cr<='z'; ++cr){
                    s1[i] = cr;
                    if(s1 == endWord) return m[s] + 1;
                    if(wordList.find(s1) != wordList.end() && m.find(s1) == m.end()){
                        m[s1] = m[s] +1;
                        q.push(s1);
                    }
                }
            }
        }
        return 0;
    }
};

473. Matchsticks to Square

https://leetcode.com/contest/leetcode-weekly-contest-13/problems/matchsticks-to-square/

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you can save this little girl or not.

Note:

    The length sum of the given matchsticks is in the range of 0 to 10^9.
    The length of the given matchstick array will not exceed 15.

Solution:
some condition needs to be true if the final result is true:
1: the total number of the elements in the array needs to be at least 4;
2: the average needs to be divided by 4 exactly;
3: the largest elements in the array cannot be larger than the average;
4: the most difficult part: those elements has to be packaged exactly and fully into 4 containers with the same size of the average, and each elements can only be used once;

Code:

class Solution {
public:
    bool makesquare(vector<int>& nums) {
        if(nums.size()<4) return false;
        int ave = 0, left = 0, len = 0;
        for(int i=0; i<nums.size(); ++i){
            ave +=nums[i]/4;
            left +=nums[i]%4;
        }
        if(left%4) return false;
        else len = ave + left/4;
        for(auto i:nums){
              if(i>len) return false;
        }
        vector<int> side(4, 0);
        return fitDSF(nums, 0, len, side);
    }
private:
    bool fitDSF(vector<int> &n, int ind, int l, vector<int> &s){
        if(ind == n.size()) return true;
        for(int i=0; i<4; ++i){
            if(i>0&&s[i] == s[i-1]) continue;//if not included, will cause TLE...
            if(s[i] + n[ind] <= l){
                s[i] += n[ind];
                if(fitDSF(n, ind+1, l, s)) return true;
                s[i] -= n[ind];
            }
        }
        return false;
    }
};

477. Total Hamming Distance

https://leetcode.com/contest/leetcode-weekly-contest-13/problems/total-hamming-distance/

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Solution:
May use the bitwise operation to reduce the time complexity. All the numbers can be viewed as 32 bits with 0s and 1s. So for each bit, we just need to count the total number of 1s, then the total number of 0s will be (total numbers - the numbers of 1s). And the contribution to the Hamming distance will be count of 1s times the count of 0s. Similar argument can be applied to all the rest bits.

Code:

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<32; ++i){
            int one = 0;
            for(int j=0; j<nums.size(); ++j){
                if((1<<i) & nums[j]) ++one;//one is the numbers of 1s;
            }
            res += one*(nums.size()-one);// nums of 1s x nums of 0s
        }
        return res;
    }
};

115. Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/

Solution:

Need dynamic programming (dp). The key is to find the transition equation. Let suppose dp[i][j] represents the number of distinct subsquences in the first i elements of s for the first j elements of t. When t[j] != s[i], then s[i] cannot be used, and dp[i+1][j+1] = dp[i][j+1]; if t[j] == s[i], then s[i] can be either used nor not used, and dp[i+1][j+1] = dp[i][j] + dp[i][j+1]; so,

                          

         dp[i+1][j+1] = dp[i][j+1];                 if(s[i] ! = t[j])
                      = dp[i][j] + dp[i][j+1];      else

And the space can be further optimized to O(n).

Code:

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(),  n = t.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=0; i<=m; ++i) dp[i][0] = 1;  //empty string is always a valid sub-sequence.
        for(int i=1; i<=n; ++i) dp[0][i] = 0;   //Non-empty string is always non-valid .. for an empty str.
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(s[i] == t[j]) dp[i+1][j+1] = dp[i][j] + dp[i][j+1];
                else dp[i+1][j+1] = dp[i][j+1];
            }
        }
        return dp[m][n];
    }
};

474. Ones and Zeroes

https://leetcode.com/problems/ones-and-zeroes/

solution:
这是个2维01背包问题 (two-D 0-1 Knapsack Problem). 所以不再啰嗦了， 如果第一次见到此类问题，就google "Knapsack Problem".

代码：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        //two-dimentional 0-1 knapsack problem.
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(auto s:strs){
            int count1 = 0, count2 = 0; // count1 for '0' and count2 for '1';
            for(auto c:s){
                if(c=='0') ++count1;
                else ++count2;
            }
            for(int i=m; i>count1-1; --i){
                for(int j=n; j>count2-1; --j){
                    dp[i][j] = max(dp[i][j], dp[i-count1][j-count2] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

solution:

这个题目想一口气写好不容易。 需要考虑的细节很多。算法倒是很好理解。既然是sorted array, 那么必须用好排好的序。所以要追求 O(ln n).

代码：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double res;
        int l1=nums1.size();
        int l2=nums2.size();
        int total = l1 + l2;
        if(total & 0x1){ // total is odd;
            res = findKth(nums1, 0, l1, nums2, 0, l2, total/2 + 1)*1.0;
        }
        else {
            res = (findKth(nums1, 0, l1, nums2, 0, l2, total/2)  
                  + findKth(nums1, 0, l1, nums2, 0, l2, total/2 + 1))/2.0;
        }
        return res;
    }
private:    
    int findKth(vector<int>& v1, int a1, int b1, vector<int>& v2, int a2, int b2, int k){
        int x1=b1-a1;
        int x2=b2-a2;
        if(x1>x2) return findKth(v2, a2, b2, v1, a1, b1, k);
        if(x1==0) return v2[a2+k-1];
        if(k==1) return min(v1[a1], v2[a2]);
        int m=min(x1, k/2); 
        int n=k-m;
        if(v1[a1+m-1]<v2[a2+n-1]){
            return findKth(v1, a1+m, b1, v2, a2, b2, k-m);
        }
        else if(v1[a1+m-1]>v2[a2+n-1]){
            return findKth(v1, a1, b1, v2, a2+n, b2, k-n);
        }
        else {
            return v1[a1+m-1];
        }
    }    
};

3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

solution:
可以使用double pointers. 需要更新最左边和最右边。题目不难， 这时就是看代码怎么写的简洁。

代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        int left = 0;
        vector<int> m(256, 0);
        for (int i=0; i<s.size(); ++i){
            left = max(left, m[s[i]]);
            m[s[i]] = i+1;
            res = max(res, i-left+1);
        }
        return res;
    } 
};

2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

solution:
需要考虑进位的问题。 然后就是linked list细节了： 生成新节点等等。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(-1);
        ListNode* p = &dummy;
        int carrier = 0;
        while(l1||l2){
            if(l1) {
                carrier += l1->val;
                l1 = l1->next;
            }
            if(l2) {
                carrier += l2->val;
                l2 = l2->next;
            }
            p->next = new ListNode(carrier%10);
            p = p->next;
            carrier /= 10;
        }
        if(carrier){
            p->next = new ListNode(carrier);
            p = p->next;
        }
        return dummy.next;
   };

1: Two Sum

https://leetcode.com/problems/two-sum/

solution:
不用hash table的话，需要double pointers. 这样的就 O(n2) 了。
使用hash table的话， 就很直观的 O(n) 了。 然后需要注意一些细节， 比如不要重复计入了， 还有就是可以扫一遍就行了 （hash的同时就可以判断了）。

代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int, int> map;
        for(int i=0; i<nums.size(); ++i){
            if(map.find(target-nums[i])!=map.end()&&i>map[target-nums[i]]){
                res.push_back(map[target-nums[i]]);
                res.push_back(i);
                return res;
            }
            else map[nums[i]]=i;
        }
        return res;
    }
};