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

Topological Sorting
题意：求拓扑排序。
解法1：逐个找出入度为0的节点。两层循环，效率不高。
代码1：

1. // O(n ^ 2) solution
   
2. #include <unordered_map>
   
3. using namespace std;
   
4. /**
   
5. * Definition for Directed graph.
   
6. * struct DirectedGraphNode {
   
7. *     int label;
   
8. *     vector<DirectedGraphNode *> neighbors;
   
9. *     DirectedGraphNode(int x) : label(x) {};
   
10. * };
    
11. */
    
12. typedef DirectedGraphNode DGN;
    
13. class Solution {
    
14. public:
    
15.     /**
    
16.      * @param graph: A list of Directed graph node
    
17.      * @return: Any topological order for the given graph.
    
18.      */
    
19.     vector<DGN *> topSort(vector<DGN *> graph) {
    
20.         unordered_map<DGN *, int> ind;
    
21.         vector<DGN *> ans;
    
22.         int n, m;
    
23.         int i, j;
    
24.         
    
25.         n = graph.size();
    
26.         for (i = 0; i < n; ++i) {
    
27.             m = graph[i]->neighbors.size();
    
28.             for (j = 0; j < m; ++j) {
    
29.                 ++ind[graph[i]->neighbors[j]];
    
30.             }
    
31.         }
    
32.         int cc;
    
33.         vector<bool> v(n, false);
    
34.         while (true) {
    
35.             cc = 0;
    
36.             for (i = 0; i < n; ++i) {
    
37.                 if (v[i] || ind[graph[i]] != 0) {
    
38.                     continue;
    
39.                 }
    
40.                 ++cc;
    
41.                 v[i] = true;
    
42.                 ans.push_back(graph[i]);
    
43.                 m = graph[i]->neighbors.size();
    
44.                 for (j = 0; j < m; ++j) {
    
45.                     --ind[graph[i]->neighbors[j]];
    
46.                 }
    
47.             }
    
48.             if (cc == 0) {
    
49.                 break;
    
50.             }
    
51.         }
    
52.         return ans;
    
53.     }
    
54. };

复制代码

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

解法2：改成BFS。
代码2：

1. // Solution using BFS
   
2. #include <queue>
   
3. #include <unordered_set>
   
4. #include <unordered_map>
   
5. using namespace std;
   
6. /**
   
7. * Definition for Directed graph.
   
8. * struct DirectedGraphNode {
   
9. *     int label;
   
10. *     vector<DirectedGraphNode *> neighbors;
    
11. *     DirectedGraphNode(int x) : label(x) {};
    
12. * };
    
13. */
    
14. typedef DirectedGraphNode DGN;
    
15. class Solution {
    
16. public:
    
17.     /**
    
18.      * @param graph: A list of Directed graph node
    
19.      * @return: Any topological order for the given graph.
    
20.      */
    
21.     vector<DGN *> topSort(vector<DGN *> graph) {
    
22.         unordered_map<DGN *, int> ind;
    
23.         vector<DGN *> ans;
    
24.         int n, m;
    
25.         int i, j;
    
26.         
    
27.         n = graph.size();
    
28.         for (i = 0; i < n; ++i) {
    
29.             m = graph[i]->neighbors.size();
    
30.             for (j = 0; j < m; ++j) {
    
31.                 ++ind[graph[i]->neighbors[j]];
    
32.             }
    
33.         }
    
34.         int cc;
    
35.         queue<DGN *> q;
    
36.         unordered_set<DGN *> us;
    
37.         
    
38.         for (i = 0; i < n; ++i) {
    
39.             if (ind[graph[i]] == 0) {
    
40.                 q.push(graph[i]);
    
41.             }
    
42.         }
    
43.         
    
44.         DGN *p;
    
45.         while (!q.empty()) {
    
46.             p = q.front();
    
47.             q.pop();
    
48.             if (us.find(p) != us.end()) {
    
49.                 // Already visited
    
50.                 continue;
    
51.             }
    
52.             if (ind[p] > 0) {
    
53.                 // In-degree is not zero
    
54.                 q.push(p);
    
55.                 continue;
    
56.             }
    
57.             
    
58.             ans.push_back(p);
    
59.             us.insert(p);
    
60.             m = p->neighbors.size();
    
61.             for (i = 0; i < m; ++i) {
    
62.                 --ind[p->neighbors[i]];
    
63.                 q.push(p->neighbors[i]);
    
64.             }
    
65.         }
    
66.         return ans;
    
67.     }
    
68. };

复制代码

复杂度2：时间O(N + E)，空间O(N + E)

又被吞掉一题：Topological Sorting。

Hash Function
题意：照题目要求，实现一个哈希函数。
解法：照题目要求。
代码：

1. typedef long long int LL;
   
2. 
   
3. class Solution {
   
4. public:
   
5.     /**
   
6.      * @param key: A String you should hash
   
7.      * @param HASH_SIZE: An integer
   
8.      * @return an integer
   
9.      */
   
10.     int hashCode(string key,int HASH_SIZE) {
    
11.         int n = key.size();
    
12.         LL ans = 0;
    
13.         int i;
    
14.         for (i = 0; i < n; ++i) {
    
15.             ans = (ans * 33 + key[i]) % HASH_SIZE;
    
16.         }
    
17.         return ans;
    
18.     }
    
19. };

复制代码

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

Rehashing
题意：当哈希表的load factor超过阈值之后，性能会显著下降。于是此时需要扩大容量。请完成rehash操作。
解法：算好位置，插入。
代码：

1. // This problem is a bit unreasonable.
   
2. // Why must the nodes be appended to the end of the list?
   
3. /**
   
4. * Definition of ListNode
   
5. * class ListNode {
   
6. * public:
   
7. *     int val;
   
8. *     ListNode *next;
   
9. *     ListNode(int val) {
   
10. *         this->val = val;
    
11. *         this->next = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16. public:
    
17.     /**
    
18.      * @param hashTable: A list of The first node of linked list
    
19.      * @return: A list of The first node of linked list which have twice size
    
20.      */   
    
21.     vector<ListNode*> rehashing(vector<ListNode*> hashTable) {
    
22.         int n1 = hashTable.size();
    
23.         int n2 = n1 * 2;
    
24.         vector<ListNode *> ans(n2, NULL);
    
25.         vector<ListNode *> tail(n2, NULL);
    
26.         
    
27.         int i, j;
    
28.         ListNode *p, *q;
    
29.         for (i = 0; i < n1; ++i) {
    
30.             p = hashTable[i];
    
31.             while (p != NULL) {
    
32.                 q = p->next;
    
33.                 j = addr(p->val, n2);
    
34.                
    
35.                 if (ans[j] == NULL) {
    
36.                     ans[j] = tail[j] = p;
    
37.                 } else {
    
38.                     tail[j]->next = p;
    
39.                     tail[j] = p;
    
40.                 }
    
41.                 tail[j]->next = NULL;
    
42.                
    
43.                 p = q;
    
44.             }
    
45.             hashTable[i] = NULL;
    
46.         }
    
47.         return ans;
    
48.     }
    
49. private:
    
50.     int addr(int val, int cap) {
    
51.         return val >= 0 ? val % cap : (val % cap + cap) % cap;
    
52.     }
    
53. };

复制代码

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

又被吞掉一题：Rehashing。

Heapify
题意：建堆。
解法：自底向上逐步筛选、交换。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param A: Given an integer array
   
8.      * @return: void
   
9.      */
   
10.     void heapify(vector<int> &A) {
    
11.         int n = A.size();
    
12.         if (n < 2) {
    
13.             return;
    
14.         }
    
15.         int i, j, k;
    
16.         int minVal;
    
17.         
    
18.         for (i = (n - 1) / 2; i >= 0; --i) {
    
19.             j = i;
    
20.             while (j * 2 + 1 <= n - 1) {
    
21.                 k = j;
    
22.                 minVal = A[j];
    
23.                 if (A[j * 2 + 1] < minVal) {
    
24.                     k = j * 2 + 1;
    
25.                     minVal = A[k];
    
26.                 }
    
27.                 if (j * 2 + 2 <= n - 1 && A[j * 2 + 2] < minVal) {
    
28.                     k = j * 2 + 2;
    
29.                     minVal = A[k];
    
30.                 }
    
31.                 if (k == j) {
    
32.                     break;
    
33.                 }
    
34.                 swap(A[j], A[k]);
    
35.                 j = k;
    
36.             }
    
37.         }
    
38.     }
    
39. };

复制代码

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

Word Search II
题意：hard难度。给定一个字符矩阵，和一个词典。允许你上下左右走，从矩阵的一点走到另一点。请问总共有多少种走法，使得轨迹恰好构成词典里的单词。把那些单词找出来。
解法：和Word Search类似，不过这次有了许多单词，而且要求都找出来，那么首先要考虑的就是DFS的效率问题。于是，为了优化效率，我们引入字典树。代码虽然复杂了，但思路还是比较简单的，就是DFS。
代码：

1. typedef struct TrieNode {
   
2.     static const int N = 26;
   
3.    
   
4.     bool isWord;
   
5.     vector<TrieNode *> child;
   
6.    
   
7.     TrieNode() {
   
8.         isWord = false;
   
9.         child.resize(N, NULL);
   
10.     }
    
11. } TrieNode;
    
12. 
    
13. class Solution {
    
14. public:
    
15.     Solution() {
    
16.         d.resize(4, vector<int>(2));
    
17.         d[0][0] = +1;
    
18.         d[0][1] = 0;
    
19.         
    
20.         d[1][0] = -1;
    
21.         d[1][1] = 0;
    
22.         
    
23.         d[2][0] = 0;
    
24.         d[2][1] = +1;
    
25.         
    
26.         d[3][0] = 0;
    
27.         d[3][1] = -1;
    
28.     }
    
29.     /**
    
30.      * @param board: A list of lists of character
    
31.      * @param words: A list of string
    
32.      * @return: A list of string
    
33.      */
    
34.     vector<string> wordSearchII(vector<vector<char> > &board, vector<string> &words) {
    
35.         v.clear();
    
36.         us.clear();
    
37.         ans.clear();
    
38.         
    
39.         vector<vector<char> > &b = board;
    
40.         n = b.size();
    
41.         m = n ? b[0].size() : 0;
    
42.         if (!(n || m)) {
    
43.             return ans;
    
44.         }
    
45.         
    
46.         TrieNode *root = new TrieNode();
    
47.         for (auto it = words.begin(); it != words.end(); ++it) {
    
48.             insertWord(root, *it);
    
49.         }
    
50.         
    
51.         string s = "";
    
52.         v.resize(n, vector<bool>(m, false));
    
53.         int i, j;
    
54.         for (i = 0; i < n; ++i) {
    
55.             for (j = 0; j < m; ++j) {
    
56.                 v[i][j] = true;
    
57.                 s.push_back(b[i][j]);
    
58.                 DFS(i, j, s, root->child[b[i][j] - 'a'], b);
    
59.                 s.pop_back();
    
60.                 v[i][j] = false;
    
61.             }
    
62.         }
    
63.         
    
64.         for (auto it = us.begin(); it != us.end(); ++it) {
    
65.             ans.push_back(*it);
    
66.         }
    
67.         clearTrie(root);
    
68.         return ans;
    
69.     }
    
70. private:
    
71.     int n, m;
    
72.     vector<vector<bool> > v;
    
73.     unordered_set<string> us;
    
74.     vector<string> ans;
    
75.     vector<vector<int> > d;
    
76.    
    
77.     bool inbound(int x, int y) {
    
78.         return x >= 0 && x <= n - 1 && y >= 0 && y <= m - 1;
    
79.     }
    
80.    
    
81.     void DFS(int x, int y, string &s, TrieNode *r, vector<vector<char> > &b) {
    
82.         if (r == NULL) {
    
83.             return;
    
84.         }
    
85.         if (r->isWord) {
    
86.             // A word is found
    
87.             us.insert(s);
    
88.         }
    
89.         int x1, y1;
    
90.         int i;
    
91.         for (i = 0; i < 4; ++i) {
    
92.             x1 = x + d[i][0];
    
93.             y1 = y + d[i][1];
    
94.             if (!inbound(x1, y1) || v[x1][y1]) {
    
95.                 continue;
    
96.             }
    
97.             v[x1][y1] = true;
    
98.             s.push_back(b[x1][y1]);
    
99.             DFS(x1, y1, s, r->child[b[x1][y1] - 'a'], b);
    
100.             s.pop_back();
     
101.             v[x1][y1] = false;
     
102.         }
     
103.     }
     
104.    
     
105.     void insertWord(TrieNode *root, string s) {
     
106.         int n = s.length();
     
107.         if (n == 0) {
     
108.             return;
     
109.         }
     
110.         int i;
     
111.         TrieNode *p = root;
     
112.         for (i = 0; i < n; ++i) {
     
113.             if (p->child[s[i] - 'a'] == NULL) {
     
114.                 p->child[s[i] - 'a'] = new TrieNode();
     
115.             }
     
116.             p = p->child[s[i] - 'a'];
     
117.         }
     
118.         p->isWord = true;
     
119.     }
     
120.    
     
121.     void clearTrie(TrieNode *&root) {
     
122.         if (root == NULL) {
     
123.             return;
     
124.         }
     
125.         int i;
     
126.         for (i = 0; i < TrieNode::N; ++i) {
     
127.             clearTrie(root->child[i]);
     
128.         }
     
129.         root->child.clear();
     
130.         delete root;
     
131.         root = NULL;
     
132.     }
     
133. };

复制代码

复杂度：时间O((N * M)!)，空间一样。

补充内容 (2015-7-23 15:11):
更正：复杂度：时间O(4 ^ (N * M))，空间一样。只是理论复杂度很高，实际当然没这么高。

LRU Cache
题意：hard难度。实现一个LRU Cache。
解法：哈希表配合双向链表，所有操作都可以O(1)时间完成。此题很容易一堆bug，因为双链表比单链表还乱。
代码：

1. // Hashmap and doubly linked list.
   
2. #include <unordered_map>
   
3. using namespace std;
   
4. 
   
5. typedef struct DoublyListNode {
   
6.     int key;
   
7.     int val;
   
8.     struct DoublyListNode *left;
   
9.     struct DoublyListNode *right;
   
10.     DoublyListNode(int key = 0, int val = 0): key(key), val(val) {
    
11.         left = right = NULL;
    
12.     }
    
13. } DLN;
    
14. 
    
15. class LRUCache{
    
16. public:
    
17.     // @param capacity, an integer
    
18.     LRUCache(int capacity) {
    
19.         cap = capacity;
    
20.         size = 0;
    
21.         head = tail = NULL;
    
22.     }
    
23.    
    
24.     // @return an integer
    
25.     int get(int key) {
    
26.         if (um.find(key) == um.end()) {
    
27.             return DEFAULT_VALUE;
    
28.         }
    
29.         moveToFront(key);
    
30.         return um[key]->val;
    
31.     }
    
32. 
    
33.     // @param key, an integer
    
34.     // @param value, an integer
    
35.     // @return nothing
    
36.     void set(int key, int value) {
    
37.         DLN *p;
    
38.         if (um.find(key) == um.end()) {
    
39.             if (size == cap) {
    
40.                 p = tail;
    
41.                 um.erase(tail->key);
    
42.                 tail->key = key;
    
43.                 tail->val = value;
    
44.             } else {
    
45.                 p = new DLN(key, value);
    
46.                 if (head == NULL) {
    
47.                     head = tail = p;
    
48.                 } else {
    
49.                     p->right = head;
    
50.                     head->left = p;
    
51.                     head = p;
    
52.                 }
    
53.                 ++size;
    
54.             }
    
55.             um[key] = p;
    
56.         } else {
    
57.             p = um[key];
    
58.             p->val = value;
    
59.         }
    
60.         moveToFront(key);
    
61.     }
    
62. private:
    
63.     static const int DEFAULT_VALUE = -1;
    
64.     unordered_map<int, DLN *> um;
    
65.     int cap;
    
66.     int size;
    
67.     DLN *head, *tail;
    
68.    
    
69.     void moveToFront(int key) {
    
70.         if (um.find(key) == um.end()) {
    
71.             return;
    
72.         }
    
73.         DLN *p = um[key];
    
74.         if (p == head) {
    
75.             return;
    
76.         }
    
77.         
    
78.         if (p == tail) {
    
79.             tail = tail->left;
    
80.             tail->right = NULL;
    
81.         } else {
    
82.             p->left->right = p->right;
    
83.             p->right->left = p->left;
    
84.         }
    
85.         p->left = NULL;
    
86.         p->right = head;
    
87.         head->left = p;
    
88.         head = p;
    
89.     }
    
90. };

复制代码

复杂度：时间各种O(1)，空间各种O(1)。全局空间开销O(N)。

Combination Sum
题意：给定一个数组A和整数target。数组中每个元素可以取无数次，求所有加起来等于target的组合。
解法：DFS，注意剪剪枝。
代码：

1. #include <algorithm>
   
2. #include <unordered_set>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /**
   
8.      * @param candidates: A list of integers
   
9.      * @param target:An integer
   
10.      * @return: A list of lists of integers
    
11.      */
    
12.     vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
    
13.         v.clear();
    
14.         us.clear();
    
15.         a.clear();
    
16.         ans.clear();
    
17.         
    
18.         n = candidates.size();
    
19.         int i;
    
20.         for (i = 0; i < n; ++i) {
    
21.             us.insert(candidates[i]);
    
22.         }
    
23.         for (auto it = us.begin(); it != us.end(); ++it) {
    
24.             a.push_back(*it);
    
25.         }
    
26.         n = a.size();
    
27.         sort(a.begin(), a.end());
    
28.         t = target;
    
29.         DFS(0, 0);
    
30.         return ans;
    
31.     }
    
32. private:
    
33.     vector<int> v;
    
34.     unordered_set<int> us;
    
35.     vector<int> a;
    
36.     vector<vector<int> > ans;
    
37.     int n;
    
38.     int t;
    
39.    
    
40.     void DFS(int idx, int sum) {
    
41.         if (sum == t) {
    
42.             ans.push_back(v);
    
43.             return;
    
44.         }
    
45.         if (idx == n) {
    
46.             return;
    
47.         }
    
48.         if (sum + a[idx] > t) {
    
49.             return;
    
50.         }
    
51.         int i = 0;
    
52.         int j;
    
53.         while (sum + i * a[idx] <= t) {
    
54.             for (j = 0; j < i; ++j) {
    
55.                 v.push_back(a[idx]);
    
56.             }
    
57.             DFS(idx + 1, sum + i * a[idx]);
    
58.             for (j = 0; j < i; ++j) {
    
59.                 v.pop_back();
    
60.             }
    
61.             ++i;
    
62.         }
    
63.     }
    
64. };

复制代码

复杂度：式子比较长，不好写。

Palindrome Partitioning
题意：给定一个字符串，可以把它分割成回文子串之和。请求出所有不同的分割方法。
解法：首先用O(N ^ 2)时间和空间求出所有字串是否是回文串，然后进行DFS。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param s: A string
   
5.      * @return: A list of lists of string
   
6.      */
   
7.     vector<vector<string> > partition(string s) {
   
8.         pal.clear();
   
9.         ans.clear();
   
10.         n = s.length();
    
11.         if (n == 0) {
    
12.             return ans;
    
13.         }
    
14.         
    
15.         pal.resize(n, vector<bool>(n, false));
    
16.         int i, j;
    
17.         for (i = 0; i < n; ++i) {
    
18.             pal[i][i] = true;
    
19.         }
    
20.         for (i = 0; i < n - 1; ++i) {
    
21.             pal[i][i + 1] = (s[i] == s[i + 1]);
    
22.         }
    
23.         for (i = 2; i < n; ++i) {
    
24.             for (j = 0; j + i < n; ++j) {
    
25.                 pal[j][j + i] = (s[j] == s[j + i]) && pal[j + 1][j + i - 1];
    
26.             }
    
27.         }
    
28.         vector<string> par;
    
29.         DFS(s, par, 0);
    
30.         
    
31.         return ans;
    
32.     }
    
33. private:
    
34.     int n;
    
35.     vector<vector<bool> > pal;
    
36.     vector<vector<string> > ans;
    
37.    
    
38.     void DFS(string &s, vector<string> &par, int idx) {
    
39.         if (idx == n) {
    
40.             ans.push_back(par);
    
41.             return;
    
42.         }
    
43.         int i;
    
44.         for (i = n - 1; i >= idx; --i) {
    
45.             if (!pal[idx][i]) {
    
46.                 continue;
    
47.             }
    
48.             par.push_back(s.substr(idx, i - idx + 1));
    
49.             DFS(s, par, i + 1);
    
50.             par.pop_back();
    
51.         }
    
52.     }
    
53. };

复制代码

复杂度：O(N!)，空间一样。