所有總結(jié)題目 http://www.reibang.com/p/55b90cfcb406

這里總結(jié)了頻率4的題目：

2.Add Two Numbers

描述
You are given two linked lists representing two non-negative numbers. The digits
are stored in reverse order and each of their nodes contain a single digit. Add the
two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

分析
跟 Add Binary 很類似
代碼
// Add Two Numbers
// 跟Add Binary 很類似
// 時間復(fù)雜度O(m+n)抽诉，空間復(fù)雜度O(1)

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode dummy(-1); // 頭節(jié)點(diǎn)
        int carry = 0;
        ListNode *prev = &dummy;
        for (ListNode *pa = l1, *pb = l2;
            pa != nullptr || pb != nullptr;
            pa = pa == nullptr ? nullptr : pa->next,
            pb = pb == nullptr ? nullptr : pb->next,
            prev = prev->next) {

            const int ai = pa == nullptr ? 0 : pa->val;
            const int bi = pb == nullptr ? 0 : pb->val;
            const int value = (ai + bi + carry) % 10;
            carry = (ai + bi + carry) / 10;
            prev->next = new ListNode(value); // 尾插法
        } 
        if (carry > 0)
            prev->next = new ListNode(carry);
        return dummy.next;
    }
};

12.Integer to Roman

描述
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

代碼
// Integer to Roman
// 時間復(fù)雜度O(num)疏叨，空間復(fù)雜度O(1)

class Solution {
public:
    string intToRoman(int num) {
        const int radix[] = {1000, 900, 500, 400, 100, 90,
        50, 40, 10, 9, 5, 4, 1};
        const string symbol[] = {"M", "CM", "D", "CD", "C", "XC",
        "L", "XL", "X", "IX", "V", "IV", "I"};  
        string roman;
        for (size_t i = 0; num > 0; ++i) {
            int count = num / radix[i];
            num %= radix[i];
            for (; count > 0; --count) roman += symbol[i];
        } 
        return roman;
    }
};

13. Roman to Integer

描述
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

分析
從前往后掃描谒撼，用一個臨時變量記錄分段數(shù)字哪审。
如果當(dāng)前比前一個大和敬，說明這一段的值應(yīng)該是當(dāng)前這個值減去上一個值。比如 IV = 5 – 1 ；否則，將當(dāng)前值加入到結(jié)果中睛琳，然后開始下一段記錄。比如 VI = 5 +1, II=1+1
代碼

// Roman to Integer
// 時間復(fù)雜度O(n)踏烙，空間復(fù)雜度O(1)

class Solution {
public:
    inline int map(const char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    } 

    int romanToInt(const string& s) {
        int result = 0;
        for (size_t i = 0; i < s.size(); i++) {
            if (i > 0 && map(s[i]) > map(s[i - 1])) {
                result += (map(s[i]) - 2 * map(s[i - 1]));
            } else {
                result += map(s[i]);
            }
        } 
        return result;
    }
};

22. Generate Parentheses

描述
Given n pairs of parentheses, write a function to generate all combinations of
well-formed parentheses.
For example, given n = 3 , a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

分析
小括號串是一個遞歸結(jié)構(gòu)师骗，跟單鏈表、二叉樹等遞歸結(jié)構(gòu)一樣讨惩，首先想到用遞歸辟癌。
一步步構(gòu)造字符串。當(dāng)左括號出現(xiàn)次數(shù) <n 時荐捻，就可以放置新的左括號黍少。當(dāng)右括號
出現(xiàn)次數(shù)小于左括號出現(xiàn)次數(shù)時，就可以放置新的右括號处面。
代碼1
// Generate Parentheses
// 時間復(fù)雜度O(TODO)厂置，空間復(fù)雜度O(n)

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string path;
        if (n > 0) generate(n, path, result, 0, 0);
        return result;
    } 
// l 表示 ( 出現(xiàn)的次數(shù), r 表示 ) 出現(xiàn)的次數(shù)

void generate(int n, string& path, vector<string> &result, int l) {
    if (l == n) {
    string s(path);
    result.push_back(s.append(n - r, ')'));
        return;
        } 
        path.push_back('(');
        generate(n, path, result, l + 1, r);
        path.pop_back();

        if (l > r) {
            path.push_back(')');
            generate(n, path, result, l, r + 1);
            path.pop_back();
        }
    }
};

代碼2 （遞歸）

class Solution {
public:
    vector<string> generateParenthesis (int n) {
        if (n == 0) return vector<string> (1, "");
        if (n == 1) return vector<string> (1, "()");
        
        vector<string> result;
        for (int i = 0; i < n; ++i)
            for (auto inner : generateParenthesis (i))
                for (auto outer : generateParenthesis (n - 1 - i))
                    result.push_back ("(" + inner + ")" + outer);
        return result;
    }
};

23. Merge k Sorted Lists

描述
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its
complexity.

代碼
// Merge k Sorted Lists
// 時間復(fù)雜度O(n1+n2+...)，空間復(fù)雜度O(1)
class Solution {
public:
     ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty()) {
            return NULL;
        }
        int n = lists.size();
        while(n > 1) {
            int k = (n + 1) / 2;
            for(int i = 0; i < n / 2; i++) {
                //合并i和i + k的鏈表魂角，并放到i位置
                lists[i] = merge2List(lists[i], lists[i + k]);
            }
            //下個循環(huán)只需要處理前k個鏈表了
            n = k;
        }
        return lists[0];
    }
    ListNode* merge2List(ListNode* n1, ListNode* n2) {
        ListNode dummy(0);
        ListNode* p = &dummy;
        while(n1 && n2) {
            if(n1->val < n2->val) {
                p->next = n1;
                n1 = n1->next;
            } else {
                p->next = n2;
                n2 = n2->next;
            }
            p = p->next;
        }
        if(n1) {
            p->next = n1;
        } else if(n2) {
            p->next = n2;
        }
        return dummy.next;
    }
}; ?

24. Swap Nodes in Pairs

描述
Given a linked list, swap every two adjacent nodes and return its head.
For example, Given 1->2->3->4, you should return the list as 2->1->4->3 .
Your algorithm should use only constant space. You may not modify the values in
the list, only nodes itself can be changed.

代碼
// Swap Nodes in Pairs
// 時間復(fù)雜度O(n)昵济，空間復(fù)雜度O(1)

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if (head == NULl || head->next == NULL)
            return head;
        else if (head->next->next == NULL) {
            ListNode* pNext = head->next;
            pNext->next = head;
            head->next = NULL;
            return pNext;
        } else {
            ListNode* pNext = head->next;
            ListNode* newHead = pNext->next;
            pNext->next = head;
            head->next = swapPairs(newHead);
            return pNext;
        }
    }
};

27. Remove Element

描述
Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn't matter what you leave beyond the new length.

代碼
// Remove Element
// Time Complexity: O(n), Space Complexity: O(1)

class Solution {
public:
    int removeElement(vector<int>& nums, int target) {
        int index = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != target) {
                nums[index++] = nums[i];
            }
        } 
        return index;
    }
};

46. Permutations（全排列）

描述
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3]have the following permutations:
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], and [3,2,1].

class Solution {
public:
    bool next_perm(vector<int>& num) {
        int i = num.size()-1, j = num.size()-1;
        while(i-1 >= 0 && num[i] < num[i-1])i--;
        if(i == 0)
            return false;
        i--;
        while(num[j] < num[i])
            j--;
        std::swap(num[i], num[j]);
        reverse(num.begin()+i+1, num.end());
        return true;
    }
    vector<vector<int> > permute(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> > ans;
        do {
            ans.push_back(num);
        } while(next_perm(num));
        return ans;
    }
};

49. Anagrams

描述
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.

代碼
class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        int i;
        map<string,int> book;
        vector<string> d,t;
        for(i=0;i<strs.size();t.push_back(strs[i]),i++);
        for(i=0;i<t.size();i++)
        {
            sort(t[i].begin(),t[i].end());
            if(book.count(t[i])==0) book[t[i]]=0;
            book[t[i]]++;
        }
        for(i=0;i<strs.size();i++)
            if(book[t[i]]>=2) d.push_back(strs[i]);
        return d;
    }
};

67. Add Binary

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

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

分析: 我認(rèn)為這道題所要注意的地方涵蓋以下幾個方面:
對字符串的操作.
對于加法，我們應(yīng)該建立一個進(jìn)位單位，保存進(jìn)位數(shù)值.
我們還要考慮兩個字符串如果不同長度會怎樣.
int 類型和char類型的相互轉(zhuǎn)換.

時間復(fù)雜度:其實(shí)這就是針對兩個字符串加起來跑一遍砸紊，O(n) n代表長的那串字符串長度.
class Solution {
public:
    string addBinary(string a, string b) {
        int len1 = a.size();
        int len2 = b.size();
        if(len1 == 0)
            return b;
        if(len2 == 0)
            return a;

        string ret;
        int carry = 0;
        int index1 = len1-1;
        int index2 = len2-1;

        while(index1 >=0 && index2 >= 0)
        {
            int num = (a[index1]-'0')+(b[index2]-'0')+carry;
            carry = num/2;
            num = num%2;
            index1--;
            index2--;
            ret.insert(ret.begin(),num+'0');
        }

        if(index1 < 0 && index2 < 0)
        {
            if(carry == 1)
            {
                ret.insert(ret.begin(),carry+'0');
                return ret;
            }
        }

        while(index1 >= 0)
        {
            int num = (a[index1]-'0')+carry;
            carry = num/2;
            num = num%2;
            index1--;
            ret.insert(ret.begin(),num+'0');
        }
        while(index2 >= 0)
        {
            int num = (b[index2]-'0')+carry;
            carry = num/2;
            num = num%2;
            index2--;
            ret.insert(ret.begin(),num+'0');
        }
        if(carry == 1)
            ret.insert(ret.begin(),carry+'0');
        return ret;
    }
};

69. Sqrt(x)

描述
Implement int sqrt(int x) .
Compute and return the square root of x .

分析
二分查找
代碼
// LeetCode, Sqrt(x)
// 二分查找
// 時間復(fù)雜度O(logn)传于，空間復(fù)雜度O(1)

class Solution {
public:
    int mySqrt(int x) {
        int left = 1, right = x / 2;
        int last_mid; // 記錄最近一次mid
        if (x < 2) return x;
        
        while(left <= right) {
            const int mid = left + (right - left) / 2;
            if(x / mid > mid) { // 不要用 x > mid * mid，會溢出
                left = mid + 1;
                last_mid = mid;
            } else if (x / mid < mid) {
                right = mid - 1;
            } else {
                return mid;
            }
        } 
        return last_mid;
    }
};

77. Combinations

描述
Given two integers n and k, return all possible combinations of k numbers
out of 1 ... n.
For example, If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

遞歸
// Combinations
// 深搜醉顽，遞歸
// 時間復(fù)雜度O(n!)沼溜，空間復(fù)雜度O(n)

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > result;
        vector<int> path;
        dfs(n, k, 1, 0, path, result);
        return result;
    }

private:
    // start，開始的數(shù), cur游添，已經(jīng)選擇的數(shù)目
    static void dfs(int n, int k, int start, int cur,
        vector<int> &path, vector<vector<int> > &result) {
        if (cur == k) {
            result.push_back(path);
        }
        for (int i = start; i <= n; ++i) {
            path.push_back(i);
            dfs(n, k, i + 1, cur + 1, path, result);
            path.pop_back();
        }
    }
};

78. Subsets

描述
Given a set of distinct integers, S , return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example, If S = [1,2,3] , a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

遞歸
增量構(gòu)造法
每個元素系草，都有兩種選擇，選或者不選唆涝。

代碼
// Subsets
// 增量構(gòu)造法找都，深搜，時間復(fù)雜度O(2^n)廊酣，空間復(fù)雜度O(n)
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end()); // 輸出要求有序
        vector<vector<int> > result;
        vector<int> path;
        subsets(S, path, 0, result);
        return result;
    }
private:
    static void subsets(const vector<int> &S, vector<int> &path, int step,
        vector<vector<int> > &result) {
        if (step == S.size()) {
            result.push_back(path);
            return;
        } 
        // 不選S[step]
        subsets(S, path, step + 1, result);
        // 選S[step]
        path.push_back(S[step]);
        subsets(S, path, step + 1, result);
        path.pop_back();
    }
};

79. Word Search

描述
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where
"adjacent" cells are those horizontally or vertically neighbouring. The same
letter cell may not be used more than once.
For example, Given board =
[
["ABCE"],
["SFCS"],
["ADEE"]
]
word = "ABCCED", -> returns true ,
word = "SEE", -> returns true ,
word = "ABCB", -> returns false .

代碼
//C++ DFS backtracking 的算法
class Solution {
public:
    bool isOut(int r, int c, int rows, int cols){
        return c<0 || c>=cols || r<0 || r>=rows;
    }
    bool DFS(vector<vector<char>> &board, int r, int c, string &word, int start){
        if(start>=word.size())
            return true;
        if(isOut(r, c, board.size(), board[0].size())||word[start]!=board[r][c])
            return false;
         
        int dx[]={0, 0, 1, -1}, dy[]={1, -1, 0, 0};
        char tmp=board[r][c];
        board[r][c]='.';
        for(int i=0; i<4; ++i){
            if(DFS(board, r+dx[i], c+dy[i], word, start+1))
               return true;
        }
        board[r][c]=tmp;
        return false;
    }
    bool exist(vector<vector<char> > &board, string word) {
        int rows=board.size(), cols=board[0].size();
        for(int r=0; r<rows; ++r)
            for(int c=0; c<cols; ++c){
                if(board[r][c]==word[0])
                    if(DFS(board, r, c, word, 0))
                        return true;
            }
        return false;
    }
};

102. Binary Tree Level Order Traversal能耻、

描述
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree{3,9,20,#,#,15,7},
3
/
9 20
/
15 7

return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/
2 3
/
4

5
The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

代碼
// Binary Tree Level Order Traversal
// 遞歸版，時間復(fù)雜度O(n)亡驰，空間復(fù)雜度O(n)

class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int>> result;
        traverse(root, 1, result);
        return result;
    } 
    
    void traverse(TreeNode *root, size_t level, vector<vector<int>> &result) {
        if (!root) return;
        if (level > result.size())
            result.push_back(vector<int>());

        result[level-1].push_back(root->val);
        traverse(root->left, level+1, result);
        traverse(root->right, level+1, result);
    }
};?

129. Sum Root to Leaf Numbers

描述
Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path1->2->3which represents the number123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/
2 3

The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.
Return the sum = 12 + 13 =25.

代碼
// Sum root to leaf numbers
// 時間復(fù)雜度O(n)晓猛，空間復(fù)雜度O(logn)

class Solution {
public:
    int sumNumbers(TreeNode *root) {
        return dfs(root, 0);
}
private:
    int dfs(TreeNode *root, int sum) {
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr)
            return sum * 10 + root->val;
        return dfs(root->left, sum * 10 + root->val) +
        dfs(root->right, sum * 10 + root->val);
    }
};

131. Palindrome Partitioning

描述
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s ="aab",
Return
[
["aa","b"],
["a","a","b"]
]

動態(tài)規(guī)劃+遞歸實(shí)現(xiàn)
class Solution {
public:
    //返回以s[i]開始的子串的所有拆分情況
    vector<vector<string> > dfs(size_t start, vector<vector<bool> >& flag, string s) {
        vector<vector<string> > res;
        //到達(dá)末尾
        if (start == s.length()) {
            vector<string> tmp;
            res.push_back(tmp);
        }
        else {
            //分兩部分
            for (size_t i = start; i < s.length(); i++) {
                //前半部分為回文
                if (flag[start][i] == true) {
                    //遞歸計算后半部分
                    vector<vector<string> > tmp = dfs(i + 1, flag, s);
                    //將返回的結(jié)果插入前半部分，放入res中
                    for (size_t k = 0; k < tmp.size(); k++) {
                        tmp[k].insert(tmp[k].begin(), s.substr(start, i - start + 1));
                        res.push_back(tmp[k]);
                    }
                }
            }
        }
        return res;
}

    vector<vector<string>> partition(string s) {
        vector<bool> tmp(s.size(), false);
        vector<vector<bool> > flag(s.size(), tmp);
        vector<vector<string> > res;
        //flag[i][j]為s[i..j]是否為回文串的標(biāo)志凡辱，用動態(tài)規(guī)劃
        //flag[i][j] = true  (當(dāng)s[i]==s[j]  且 flag[i+1][j-1]為true)
        for (int i = s.size() - 1; i >= 0; i--) {
            for (size_t j = i; j < s.size(); j++) {
                if (i == j) {
                    flag[i][j] = true;
                }
                else {
                    if (s[i] == s[j]) {
                        if (i + 1 == j || flag[i + 1][j - 1] == true)
                            flag[i][j] = true;
                    }
                }
            }
        }
        //遞歸找出拆分方法
        res = dfs(0, flag, s);
        return res;
    }
};