分享我的Lintcode题解，目前进度244/248

楼主厉害，自己现在也在刷题，多向你学习

Single Number III
题意：一个数组中，除了两个数出现一次，其他的都出现了两次。把这俩找出来。
解法：请直接看代码。我第一次遇到这题时，独立想了很久都没思路，看了这个解法之后感觉很神奇。反正我自己是没想出来。这回已经是第三次碰见这题了。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param A : An integer array
   
5.      * @return : Two integers
   
6.      */
   
7.     vector<int> singleNumberIII(vector<int> &A) {
   
8.         int lb;
   
9.         int n = A.size();
   
10.         int i;
    
11.         int n1, n2;
    
12.         
    
13.         lb = n1 = n2 = 0;
    
14.         for (i = 0; i < n; ++i) {
    
15.             lb ^= A[i];
    
16.         }
    
17.         lb = lb & -lb;
    
18.         for (i = 0; i < n; ++i) {
    
19.             if (A[i] & lb) {
    
20.                 n1 ^= A[i];
    
21.             } else {
    
22.                 n2 ^= A[i];
    
23.             }
    
24.         }
    
25.         vector<int> ans;
    
26.         ans.push_back(n1);
    
27.         ans.push_back(n2);
    
28.         return ans;
    
29.     }
    
30. };

复制代码

复杂度：时间O(N)，空间O(1)。

Insert Node in a Binary Search Tree
题意：给定一棵BST，插入一个新节点。
解法：各种情况都考虑到。这题没有算法难度，但面试官很喜欢出这种简单题，一旦你出bug，马上thank you立即执行。不像那些难题，即使想不出来还可能给个缓刑。
代码：

1. /**
   
2. * Definition of TreeNode:
   
3. * class TreeNode {
   
4. * public:
   
5. *     int val;
   
6. *     TreeNode *left, *right;
   
7. *     TreeNode(int val) {
   
8. *         this->val = val;
   
9. *         this->left = this->right = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. class Solution {
    
14. public:
    
15.     /**
    
16.      * @param root: The root of the binary search tree.
    
17.      * @param node: insert this node into the binary search tree
    
18.      * @return: The root of the new binary search tree.
    
19.      */
    
20.     TreeNode* insertNode(TreeNode* root, TreeNode* node) {
    
21.         if (root == NULL) {
    
22.             return node;
    
23.         }
    
24.         TreeNode *ptr = root;
    
25.         while (true) {
    
26.             if (node->val < ptr->val) {
    
27.                 if (ptr->left == NULL) {
    
28.                     ptr->left = node;
    
29.                     break;
    
30.                 } else {
    
31.                     ptr = ptr->left;
    
32.                 }
    
33.             } else if (node->val > ptr->val) {
    
34.                 if (ptr->right == NULL) {
    
35.                     ptr->right = node;
    
36.                     break;
    
37.                 } else {
    
38.                     ptr = ptr->right;
    
39.                 }
    
40.             } else {
    
41.                 break;
    
42.             }
    
43.         }
    
44.         return root;
    
45.     }
    
46. };

复制代码

复杂度：时间O(H)，空间O(1)。

Binary Search Tree Iterator
题意：hard难度。给定一个BST，请实现一个迭代器，使得能够按中序遍历的顺序逐个访问其中的元素。
解法1：既然是中序遍历，肯定可以把中序遍历跑一遍，然后用hashing记录下后继节点。这样访问的时候就可以实现O(1)时间了。
代码1：

1. // O(1) with hashing, which requires O(n) time for preprocessing
   
2. #include <unordered_map>
   
3. #include <vector>
   
4. using namespace std;
   
5. /**
   
6. * Definition of TreeNode:
   
7. * class TreeNode {
   
8. * public:
   
9. *     int val;
   
10. *     TreeNode *left, *right;
    
11. *     TreeNode(int val) {
    
12. *         this->val = val;
    
13. *         this->left = this->right = NULL;
    
14. *     }
    
15. * }
    
16. * Example of iterate a tree:
    
17. * Solution iterator = Solution(root);
    
18. * while (iterator.hasNext()) {
    
19. *    TreeNode * node = iterator.next();
    
20. *    do something for node
    
21. */
    
22. class Solution {
    
23. public:
    
24.     //@param root: The root of binary tree.
    
25.     Solution(TreeNode *root) {
    
26.         if (root == NULL) {
    
27.             cur = NULL;
    
28.             return;
    
29.         }
    
30.         
    
31.         vector<TreeNode *> v;
    
32.         
    
33.         inorder(root, v);
    
34.         int n = v.size();
    
35.         int i;
    
36.         for (i = 1; i < n; ++i) {
    
37.             nextNode[v[i - 1]] = v[i];
    
38.         }
    
39.         nextNode[v[n - 1]] = NULL;
    
40.         cur = v[0];
    
41.     }
    
42. 
    
43.     //@return: True if there has next node, or false
    
44.     bool hasNext() {
    
45.         // write your code here
    
46.         return cur != NULL;
    
47.     }
    
48.    
    
49.     //@return: return next node
    
50.     TreeNode* next() {
    
51.         TreeNode *ptr = cur;
    
52.         cur = nextNode[cur];
    
53.         return ptr;
    
54.     }
    
55.    
    
56.     ~Solution() {
    
57.         nextNode.clear();
    
58.     }
    
59. private:
    
60.     unordered_map<TreeNode *, TreeNode *> nextNode;
    
61.     TreeNode *cur;
    
62.    
    
63.     void inorder(TreeNode *root, vector<TreeNode *> &v) {
    
64.         if (root == NULL) {
    
65.             return;
    
66.         }
    
67.         inorder(root->left, v);
    
68.         v.push_back(root);
    
69.         inorder(root->right, v);
    
70.     }
    
71. };

复制代码

复杂度1：O(N)预处理，O(1)访问时间。空间O(N)。

解法2：起初我还没想通这题为什么定为hard难度，其实是没考虑到这题的空间可以优化到O(1)。请看下面的解法。当然，要求空间O(1)，时间就不可能O(1)了。
代码2：

1. // O(h) time and O(1) space
   
2. /**
   
3. * Definition of TreeNode:
   
4. * class TreeNode {
   
5. * public:
   
6. *     int val;
   
7. *     TreeNode *left, *right;
   
8. *     TreeNode(int val) {
   
9. *         this->val = val;
   
10. *         this->left = this->right = NULL;
    
11. *     }
    
12. * }
    
13. * Example of iterate a tree:
    
14. * Solution iterator = Solution(root);
    
15. * while (iterator.hasNext()) {
    
16. *    TreeNode * node = iterator.next();
    
17. *    do something for node
    
18. */
    
19. class Solution {
    
20. public:
    
21.     //@param root: The root of binary tree.
    
22.     Solution(TreeNode *root) {
    
23.         this->root = root;
    
24.         if (root == NULL) {
    
25.             cur = NULL;
    
26.             return;
    
27.         }
    
28.         cur = root;
    
29.         while (cur->left != NULL) {
    
30.             cur = cur->left;
    
31.         }
    
32.     }
    
33. 
    
34.     //@return: True if there has next node, or false
    
35.     bool hasNext() {
    
36.         return cur != NULL;
    
37.     }
    
38.    
    
39.     //@return: return next node
    
40.     TreeNode* next() {
    
41.         TreeNode *ans = cur;
    
42.         if (cur->right != NULL) {
    
43.             cur = cur->right;
    
44.             while (cur->left != NULL) {
    
45.                 cur = cur->left;
    
46.             }
    
47.             return ans;
    
48.         }
    
49.         
    
50.         TreeNode *p1 = root;
    
51.         TreeNode *p2 = NULL;
    
52.         while (p1->val != cur->val) {
    
53.             if (cur->val < p1->val) {
    
54.                 p2 = p1;
    
55.                 p1 = p1->left;
    
56.             } else {
    
57.                 p1 = p1->right;
    
58.             }
    
59.         }
    
60.         cur = p2;
    
61.         return ans;
    
62.     }
    
63. private:
    
64.     TreeNode *root, *cur;
    
65. };

复制代码

复杂度2：时间O(H)，空间O(1)。

OK，今天到此为止。

Remove Node in Binary Search Tree
题意：hard难度。给定一个BST，删除其中等于特定值的一个节点。
解法：之所以定为hard难度，是因为要考虑的情况有点多，不仔细的话很容易出bug。
代码：

1. // The BST can be in reversed order
   
2. /**
   
3. * Definition of TreeNode:
   
4. * class TreeNode {
   
5. * public:
   
6. *     int val;
   
7. *     TreeNode *left, *right;
   
8. *     TreeNode(int val) {
   
9. *         this->val = val;
   
10. *         this->left = this->right = NULL;
    
11. *     }
    
12. * }
    
13. */
    
14. class Solution {
    
15. public:
    
16.     /**
    
17.      * @param root: The root of the binary search tree.
    
18.      * @param value: Remove the node with given value.
    
19.      * @return: The root of the binary search tree after removal.
    
20.      */
    
21.     TreeNode *removeNode(TreeNode *root, int value) {
    
22.         if (root == NULL) {
    
23.             return NULL;
    
24.         }
    
25.         
    
26.         TreeNode *par, *cur;
    
27.         bool invert = false;
    
28.         if (root->left != NULL && root->val < root->left->val) {
    
29.             invert = true;
    
30.         }
    
31.         if (root->right != NULL && root->val > root->right->val) {
    
32.             invert = true;
    
33.         }
    
34.         
    
35.         par = NULL;
    
36.         cur = root;
    
37.         while (cur != NULL && cur->val != value) {
    
38.             par = cur;
    
39.             if (value < cur->val && !invert) {
    
40.                 cur = cur->left;
    
41.             } else {
    
42.                 cur = cur->right;
    
43.             }
    
44.         }
    
45.         if (cur == NULL) {
    
46.             // Value not found
    
47.             return root;
    
48.         }
    
49.         if (cur->left == NULL && cur->right == NULL) {
    
50.             // Removing a leaf node
    
51.             if (cur == root) {
    
52.                 // The tree is empty now
    
53.                 delete root;
    
54.                 return NULL;
    
55.             }
    
56.             if (par->left == cur) {
    
57.                 delete par->left;
    
58.                 par->left = NULL;
    
59.             } else {
    
60.                 delete par->right;
    
61.                 par->right = NULL;
    
62.             }
    
63.             return root;
    
64.         }
    
65.         
    
66.         TreeNode *ptr;
    
67.         int newVal;
    
68.         if (cur->left != NULL) {
    
69.             ptr = cur->left;
    
70.             while (ptr->right != NULL) {
    
71.                 ptr = ptr->right;
    
72.             }
    
73.         } else {
    
74.             ptr = cur->right;
    
75.             while (ptr->left != NULL) {
    
76.                 ptr = ptr->left;
    
77.             }
    
78.         }
    
79.         newVal = ptr->val;
    
80.         removeNode(cur, newVal);
    
81.         cur->val = newVal;
    
82.         return root;
    
83.     }
    
84. };

复制代码

复杂度：时间O(H)，空间O(H)。

Lowest Common Ancestor
题意：给定一棵二叉树，求其中两个节点的最近公共父节点。
解法：这题面试里很常考，然而基本都不允许用parent指针。所以可以用LCA倍增法或者Tarjan离线算法。这题既然是每次算一个query，我就选LCA倍增法了。感觉这题的出题方式比较坑爹，不论用什么算法都显得没效率。问题出在题目本身。
代码：

1. #include <algorithm>
   
2. #include <unordered_map>
   
3. #include <vector>
   
4. using namespace std;
   
5. /**
   
6. * Definition of TreeNode:
   
7. * class TreeNode {
   
8. * public:
   
9. *     int val;
   
10. *     TreeNode *left, *right;
    
11. *     TreeNode(int val) {
    
12. *         this->val = val;
    
13. *         this->left = this->right = NULL;
    
14. *     }
    
15. * }
    
16. */
    
17. class Solution {
    
18. public:
    
19.     /**
    
20.      * @param root: The root of the binary search tree.
    
21.      * @param A and B: two nodes in a Binary.
    
22.      * @return: Return the least common ancestor(LCA) of the two nodes.
    
23.      */
    
24.     TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
    
25.         um.clear();
    
26.         dep.clear();
    
27.         v.clear();
    
28.         p.clear();
    
29.         
    
30.         if (root == NULL || A == NULL || B == NULL) {
    
31.             return NULL;
    
32.         }
    
33.         if (A == B) {
    
34.             return A;
    
35.         }
    
36.         
    
37.         maxd = n = 0;
    
38.         preorder(root, 1);
    
39.         p.resize(n, vector<int>(MAXDEP));
    
40.         getParents(root);
    
41.         
    
42.         int i, j;
    
43.         for (i = 1; i < MAXDEP; ++i) {
    
44.             for (j = 0; j < n; ++j) {
    
45.                 p[j][i] = p[p[j][i - 1]][i - 1];
    
46.             }
    
47.         }
    
48.         
    
49.         return v[LCA(um[A], um[B])];
    
50.     }
    
51. private:
    
52.     static const int MAXDEP = 16;
    
53.     unordered_map<TreeNode *, int> um;
    
54.     vector<int> dep;
    
55.     vector<TreeNode *> v;
    
56.     vector<vector<int> > p;
    
57.     int n;
    
58.     int maxd;
    
59.    
    
60.     void preorder(TreeNode *root, int d) {
    
61.         maxd = max(maxd, d);
    
62.         
    
63.         um[root] = n++;
    
64.         v.push_back(root);
    
65.         dep.push_back(d);
    
66.         if (root->left != NULL) {
    
67.             preorder(root->left, d + 1);
    
68.         }
    
69.         if (root->right != NULL) {
    
70.             preorder(root->right, d + 1);
    
71.         }
    
72.     }
    
73.    
    
74.     void getParents(TreeNode *root) {
    
75.         if (root->left != NULL) {
    
76.             p[um[root->left]][0] = um[root];
    
77.             getParents(root->left);
    
78.         }
    
79.         if (root->right != NULL) {
    
80.             p[um[root->right]][0] = um[root];
    
81.             getParents(root->right);
    
82.         }
    
83.     }
    
84.    
    
85.     int LCA(int x, int y) {
    
86.         if (dep[x] < dep[y]) {
    
87.             return LCA(y, x);
    
88.         }
    
89.         
    
90.         int i;
    
91.         for (i = MAXDEP - 1; i >= 0; --i) {
    
92.             if (dep[p[x][i]] >= dep[y]) {
    
93.                 x = p[x][i];
    
94.             }
    
95.             if (dep[x] == dep[y]) {
    
96.                 break;
    
97.             }
    
98.         }
    
99.         if (x == y) {
    
100.             return x;
     
101.         }
     
102.         
     
103.         for (i = MAXDEP - 1; i >= 0; --i) {
     
104.             if (p[x][i] != p[y][i]) {
     
105.                 x = p[x][i];
     
106.                 y = p[y][i];
     
107.             }
     
108.         }
     
109.         return p[x][0];
     
110.     }
     
111. };

复制代码

复杂度：预处理时间O(N * log(N))，空间O(N * log(N))。每次query时间O(log(N))，空间O(1)。

k Sum
题意：hard难度。给定一个不含重复元素的正整数数组，从中选出K个数加起来等于target，求总共有多少个这种组合。
解法：这题定为hard难度，是因为题目的复杂度很高，需要有效率的算法才能通过。首先，看这题有没有想到背包问题？给你N件物品，从中选出K件能够有多少种组合，加起来于target？我就是用这种思路AC的。但是，按照思路应该用三维数组DP{i}{j}{k}，表示从前j个元素中选取i个，加起来等于k的组合共有多少种。不过数据量显然大得惊人，所以第一维用滚动数组优化掉(N变成了2)，第三维改用哈希表(只保存非零的值，节省空间)，这样空间就够用了。
代码：

1. #include <algorithm>
   
2. #include <unordered_map>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /**
   
8.      * @param A: an integer array.
   
9.      * @param k: a positive integer (k <= length(A))
   
10.      * @param target: a integer
    
11.      * @return an integer
    
12.      */
    
13.     int kSum(vector<int> A, int k, int target) {
    
14.         vector<int> &a = A;
    
15.         sort(a.begin(), a.end());
    
16.         while (!a.empty() && a.back() > target) {
    
17.             a.pop_back();
    
18.         }
    
19.         
    
20.         int n = a.size();
    
21.         if (n == 0) {
    
22.             return 0;
    
23.         }
    
24.         int i;
    
25.         int sum = 0;
    
26.         for (i = 0; i < n; ++i) {
    
27.             sum += a[i];
    
28.         }
    
29.         if (sum < target) {
    
30.             return 0;
    
31.         }
    
32.         
    
33.         int j;
    
34.         vector<vector<unordered_map<int, int> > > dp(2);
    
35.         dp[0].resize(n);
    
36.         dp[1].resize(n);
    
37.         
    
38.         for (i = 0; i < n; ++i) {
    
39.             dp[0][i][0] = 1;
    
40.         }
    
41.         int f = 1;
    
42.         int nf = !f;
    
43.         auto it = dp[0][0].begin();
    
44.         sum = 0;
    
45.         for (i = 1; i <= k; ++i) {
    
46.             for (j = 0; j < n; ++j) {
    
47.                 dp[f][j].clear();
    
48.             }
    
49.             sum += a[i - 1];
    
50.             if (sum <= target) {
    
51.                 ++dp[f][i - 1][sum];
    
52.             }
    
53.             for (j = i; j < n; ++j) {
    
54.                 dp[f][j] = dp[f][j - 1];
    
55.                 for (it = dp[nf][j - 1].begin(); it != dp[nf][j - 1].end(); ++it) {
    
56.                     if (it->first + a[j] > target) {
    
57.                         continue;
    
58.                     }
    
59.                     dp[f][j][it->first + a[j]] += it->second;
    
60.                 }
    
61.             }
    
62.             f = !f;
    
63.             nf = !f;
    
64.         }
    
65.         
    
66.         return dp[nf][n - 1][target];
    
67.     }
    
68. };

复制代码

复杂度：时间O(K * N * SUM)，其中SUM是数组所有元素之和。空间O(N * SUM)。这题存在很多bad case，可以让程序变得出奇的慢。
比如下面这个{1, 2, 4, 8, ..., 536870912, 1073741824}，由这种数组构成的k-Sum毫无疑问是令人发指的，不但爆内存、还会超时。

k Sum II
题意：给定一个不含重复元素的数组，选取K个元素加起来等于target，求所有这样的组合。
解法：这题因为是要求具体的组合，所以需要递归解决。这题的数据比k Sum宽容多了，所以难度不算太高。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param A: an integer array.
   
8.      * @param k: a positive integer (k <= length(A))
   
9.      * @param target: a integer
   
10.      * @return a list of lists of integer
    
11.      */
    
12.     vector<vector<int> > kSumII(vector<int> A, int k, int target) {
    
13.         ans.clear();
    
14.         v.clear();
    
15.         sort(A.begin(), A.end());
    
16.         v.resize(k);
    
17.         this->n = A.size();
    
18.         this->k = k;
    
19.         this->target = target;
    
20.         if (k == 1) {
    
21.             solveOne(A, target);
    
22.             return ans;
    
23.         }
    
24.         DFS(A, 0, 0, 0);
    
25.         return ans;
    
26.     }
    
27. private:
    
28.     vector<vector<int> > ans;
    
29.     vector<int> v;
    
30.     int n;
    
31.     int k;
    
32.     int target;
    
33.    
    
34.     void solveOne(vector<int> &A, int target) {
    
35.         int i;
    
36.         for (i = 0; i < n; ++i) {
    
37.             if (A[i] == target) {
    
38.                 v[0] = target;
    
39.                 ans.push_back(v);
    
40.             }
    
41.         }
    
42.     }
    
43.    
    
44.     void DFS(vector<int> &A, int idx, int sum, int cc) {
    
45.         if (sum + A[idx] * (k - cc) > target) {
    
46.             return;
    
47.         }
    
48.         if (sum + A[n - 1] * (k - cc) < target) {
    
49.             return;
    
50.         }
    
51.         
    
52.         if (cc == k - 2) {
    
53.             int ll = idx;
    
54.             int rr = n - 1;
    
55.             while (ll < rr) {
    
56.                 if (A[ll] + A[rr] < target - sum) {
    
57.                     ++ll;
    
58.                 } else if (A[ll] + A[rr] > target - sum) {
    
59.                     --rr;
    
60.                 } else {
    
61.                     v[k - 2] = A[ll];
    
62.                     v[k - 1] = A[rr];
    
63.                     ans.push_back(v);
    
64.                     ++ll;
    
65.                 }
    
66.             }
    
67.             return;
    
68.         }
    
69.         
    
70.         int i;
    
71.         for (i = idx; i <= n - (k - cc); ++i) {
    
72.             v[cc] = A[i];
    
73.             DFS(A, i + 1, sum + A[i], cc + 1);
    
74.         }
    
75.     }
    
76. };

复制代码

复杂度：时间O(C(N, K))，空间一样。

EroicaCMCS 发表于 2015-7-19 03:42
其实是有公式的。。

LeetCode上一道类似的题目 #233-Number-of-Digit-One (https://leetcode.com/prob ...

diao bao le