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

Word Ladder
题意：给定一个词典，其中所有的单词都等长。给你两个同样长的单词作为起点和终点，要求在每次只改变一个字母的情况下，从起点变到终点。还要求每次变化的单词都必须在词典中。求起点到终点的最短距离。
解法：既然每次允许变一个字母，那么就等同于”相邻单词的距离都为1“，于是求最短距离自然要用BFS了。这题我写过好几版代码，都是同一思路。这个是写的比较简洁的一个。
代码：

1. // Solution using BFS
   
2. #include <algorithm>
   
3. #include <queue>
   
4. #include <unordered_map>
   
5. using namespace std;
   
6. 
   
7. typedef unordered_set<string> uss;
   
8. class Solution {
   
9. public:
   
10.     /**
    
11.       * @param start, a string
    
12.       * @param end, a string
    
13.       * @param dict, a set of string
    
14.       * @return an integer
    
15.       */
    
16.     int ladderLength(string start, string end, uss &dict) {
    
17.         if (start == end) {
    
18.             return 0;
    
19.         }
    
20.         
    
21.         dict.insert(start);
    
22.         dict.insert(end);
    
23.         
    
24.         queue<string> q;
    
25.         unordered_map<string, int> um;
    
26.         
    
27.         string p;
    
28.         char ch;
    
29.         int i, j, len = start.length();
    
30.         int cc;
    
31.         
    
32.         um[start] = 1;
    
33.         q.push(start);
    
34.         while (um.find(end) == um.end() && !q.empty()) {
    
35.             p = q.front();
    
36.             cc = um[p];
    
37.             q.pop();
    
38.             for (i = 0; i < len; ++i) {
    
39.                 ch = p[i];
    
40.                 for (j = 0; j < 26; ++j) {
    
41.                     if (ch == 'a' + j) {
    
42.                         continue;
    
43.                     }
    
44.                     p[i] = 'a' + j;
    
45.                     if (dict.find(p) == dict.end()) {
    
46.                         // Not in dict
    
47.                         continue;
    
48.                     }
    
49.                     if (um.find(p) != um.end()) {
    
50.                         // Already visited
    
51.                         continue;
    
52.                     }
    
53.                     um[p] = cc + 1;
    
54.                     q.push(p);
    
55.                 }
    
56.                 p[i] = ch;
    
57.             }
    
58.         }
    
59.         return um[end];
    
60.     }
    
61. };

复制代码

复杂度：时间是O(26 ^ LD)，其中LD是起点和终点的最短编辑距离。空间是O(DS)，DS是词典中的单词数。

又被审核吞掉一题：Word Ladder。
可恶~我说什么值得审核的了？有本事来审我全家~

你们机器审核用的是不是用敏感词表+正则匹配？把模式改改吧，被误杀很不爽的有木有！

Word Ladder II
题意：hard难度。跟Word Ladder一样，不过这次要求出所有长度最短的路径。
解法：因为要求的是具体的路径，于是题目复杂多了。按照BFS一对多的形式，我们要求出路径，只能记录每个单词在路径中的前一个单词，也就是前驱节点。这样可以逐个向前回溯出一条路径来。首先要做的还是BFS，不过为了保存路径，我们还需要利用backtrace数组保存每个搜到单词的前一个单词。搜索过程中需要不断地从字典中删掉单词，这个是保证算法效率的关键。
代码：

1. #include <algorithm>
   
2. #include <unordered_map>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /**
   
8.       * @param start, a string
   
9.       * @param end, a string
   
10.       * @param dict, a set of string
    
11.       * @return a list of lists of string
    
12.       */
    
13.     vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
    
14.         ans.clear();
    
15.         bt.clear();
    
16.         
    
17.         dict.insert(start);
    
18.         dict.insert(end);
    
19.         
    
20.         vector<vector<string> > a(2);
    
21.         string s1, s2;
    
22.         int f, nf;
    
23.         a[0].push_back(start);
    
24.         f = 1;
    
25.         nf = !f;
    
26.         
    
27.         int i, j, k, n, len;
    
28.         char ch;
    
29.         while (true) {
    
30.             a[f].clear();
    
31.             n = a[nf].size();
    
32.             for (i = 0; i < n; ++i) {
    
33.                 dict.erase(a[nf][i]);
    
34.             }
    
35.             for (i = 0; i < n; ++i) {
    
36.                 s1 = s2 = a[nf][i];
    
37.                 len = s1.length();
    
38.                 for (j = 0; j < len; ++j) {
    
39.                     ch = s1[j];
    
40.                     for (k = 0; k < 26; ++k) {
    
41.                         if (ch == 'a' + k) {
    
42.                             continue;
    
43.                         }
    
44.                         s1[j] = 'a' + k;
    
45.                         if (dict.find(s1) == dict.end()) {
    
46.                             continue;
    
47.                         }
    
48.                         a[f].push_back(s1);
    
49.                         bt[s1].insert(s2);
    
50.                     }
    
51.                     s1[j] = ch;
    
52.                 }
    
53.             }
    
54.             if (a[f].empty() || bt.find(end) != bt.end()) {
    
55.                 break;
    
56.             }
    
57.             f = !f;
    
58.             nf = !f;
    
59.         }
    
60.         if (bt.find(end) == bt.end()) {
    
61.             return ans;
    
62.         }
    
63.         res.clear();
    
64.         backTrace(end);
    
65.         return ans;
    
66.     }
    
67. private:
    
68.     vector<vector<string> > ans;
    
69.     unordered_map<string, unordered_set<string> > bt;
    
70.     vector<string> res;
    
71.    
    
72.     void backTrace(string s) {
    
73.         if (bt.find(s) == bt.end()) {
    
74.             // End of back trac
    
75.             vector<string> r(res);
    
76.             r.push_back(s);
    
77.             reverse(r.begin(), r.end());
    
78.             ans.push_back(r);
    
79.             return;
    
80.         }
    
81.         unordered_set<string> &v = bt[s];
    
82.         res.push_back(s);
    
83.         for (auto it = v.begin(); it != v.end(); ++it) {
    
84.             backTrace(*it);
    
85.         }
    
86.         res.pop_back();
    
87.     }
    
88. };

复制代码

复杂度：跟Word Ladder一样。

敏感词测试开始
周永康
令计划
闷声发大财
作大死
陈光诚
送温暖
查水表
修炼
圆满
审核si全家
大法好
Big Brother is watching you.
网络审查
审你妹审个锤子
审个毛线
screw you
防民之口甚于防川
falungong
法轮功
敏感词测试结束

这你都不审，跑去审我的题解，你几个意思？
你敏感词表里存的是运算符跟C语言关键字吧？发个代码你倒要审核了，审核系统怎么做的？
吐槽完毕

Largest Rectangle in Histogram
题意：hard难度。给定一个直方图，如果每一条的宽度是1，求直方图覆盖的区域中，能画出的和坐标轴对齐的最大矩形的面积。
解法：对于每个位置，比如第i位的高度为A{i}，我们关心的是向左向右能找到多少个连续的位置，这些位置的高度都不低于A{i}。剩下的请参见下面代码。这种算法的思路，其实和并查集的路径压缩有点像，效率自然也很高。这题还有使用栈的一种解法，时间空间都是相同数量级的，而且感觉比较难懂，所以我就没去深究了。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param height: A list of integer
   
8.      * @return: The area of largest rectangle in the histogram
   
9.      */
   
10.     int largestRectangleArea(vector<int> &height) {
    
11.         vector<int> &a = height;
    
12.         int n = a.size();
    
13.         if (n == 0) {
    
14.             return 0;
    
15.         }
    
16.         vector<int> dl(n), dr(n);
    
17.         int i;
    
18.         dl[0] = 0;
    
19.         for (i = 1; i <= n - 1; ++i) {
    
20.             dl[i] = i;
    
21.             while (dl[i] - 1 >= 0 && a[dl[i] - 1] >= a[i]) {
    
22.                 dl[i] = dl[dl[i] - 1];
    
23.             }
    
24.         }
    
25.         dr[n - 1] = n - 1;
    
26.         for (i = n - 2; i >= 0; --i) {
    
27.             dr[i] = i;
    
28.             while (dr[i] + 1 <= n - 1 && a[dr[i] + 1] >= a[i]) {
    
29.                 dr[i] = dr[dr[i] + 1];
    
30.             }
    
31.         }
    
32.         int ans = 0;
    
33.         for (i = 0; i < n; ++i) {
    
34.             ans = max(ans, a[i] * (dr[i] - dl[i] + 1));
    
35.         }
    
36.         return ans;
    
37.     }
    
38. };

复制代码

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

Word Search
题意：给定一个字符矩阵A，和一个单词W。允许你从矩阵任意位置出发，上下左右移动。看能不能找到轨迹为W的路径。
解法：快使用DFS。
代码：

1. class Solution {
   
2. public:
   
3.     Solution() {
   
4.         d.resize(4, vector<int>(2));
   
5.         d[0][0] = -1;
   
6.         d[0][1] = 0;
   
7.         d[1][0] = +1;
   
8.         d[1][1] = 0;
   
9.         d[2][0] = 0;
   
10.         d[2][1] = -1;
    
11.         d[3][0] = 0;
    
12.         d[3][1] = +1;
    
13.     }
    
14.     /**
    
15.      * @param board: A list of lists of character
    
16.      * @param word: A string
    
17.      * @return: A boolean
    
18.      */
    
19.     bool exist(vector<vector<char> > &board, string word) {
    
20.         n = board.size();
    
21.         if (n == 0) {
    
22.             return false;
    
23.         }
    
24.         m = board[0].size();
    
25.         if (m == 0) {
    
26.             return false;
    
27.         }
    
28.         target = word;
    
29.         if (target == "") {
    
30.             return true;
    
31.         }
    
32.         b.clear();
    
33.         b.resize(n, vector<int>(m, false));
    
34.         ans = false;
    
35.         
    
36.         int i, j;
    
37.         for (i = 0; !ans && i < n; ++i) {
    
38.             for (j = 0; !ans && j < m; ++j) {
    
39.                 if (board[i][j] != target[0]) {
    
40.                     continue;
    
41.                 }
    
42.                 b[i][j] = true;
    
43.                 DFS(i, j, board, 1);
    
44.                 b[i][j] = false;
    
45.             }
    
46.         }
    
47.         return ans;
    
48.     }
    
49. private:
    
50.     int n, m;
    
51.     string target;
    
52.     vector<vector<int> > b;
    
53.     vector<vector<int> > d;
    
54.     bool ans;
    
55.    
    
56.     bool inbound(int x, int y) {
    
57.         return x >= 0 && x <= n - 1 && y >= 0 && y <= m - 1;
    
58.     }
    
59.    
    
60.     void DFS(int x, int y, vector<vector<char> > &board, int len) {
    
61.         if (ans) {
    
62.             return;
    
63.         }
    
64.         if (len == target.length()) {
    
65.             ans = true;
    
66.             return;
    
67.         }
    
68.         int i;
    
69.         int xx, yy;
    
70.         for (i = 0; i < 4; ++i) {
    
71.             xx = x + d[i][0];
    
72.             yy = y + d[i][1];
    
73.             if (!inbound(xx, yy)) {
    
74.                 continue;
    
75.             }
    
76.             if (b[xx][yy]) {
    
77.                 continue;
    
78.             }
    
79.             if (board[xx][yy] != target[len]) {
    
80.                 continue;
    
81.             }
    
82.             b[xx][yy] = true;
    
83.             DFS(xx, yy, board, len + 1);
    
84.             b[xx][yy] = false;
    
85.         }
    
86.     }
    
87. };

复制代码

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

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

Longest Consecutive Sequence
题意：给定一个无序数组，求其中能够组成的最长连续序列。比如[100, 4, 200, 1, 3, 2]的最长连续序列是[1, 2, 3, 4]，返回最大长度。
解法：又是哈希表的妙用。我们可以把各个元素看成一个个独立的段。只要是连续的，就可以进行合并。合并完了之后就变成了[100->1, 1->4, 200->1]，所以最大长度就是4了。
代码：

1. // O(n) time and space
   
2. #include <algorithm>
   
3. #include <unordered_map>
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     /**
   
9.      * @param nums: A list of integers
   
10.      * @return an integer
    
11.      */
    
12.     int longestConsecutive(vector<int> &num) {
    
13.         vector<int> &a = num;
    
14.         unordered_map<int, int> um;
    
15.         int n = a.size();
    
16.         int i;
    
17.         for (i = 0; i < n; ++i) {
    
18.             um[a[i]] = 1;
    
19.         }
    
20.         unordered_map<int, int>::iterator it1, it2;
    
21.         it1 = um.begin();
    
22.         while (it1 != um.end()) {
    
23.             while (true) {
    
24.                 i = it1->first + it1->second;
    
25.                 it2 = um.find(i);
    
26.                 if (it2 == um.end()) {
    
27.                     break;
    
28.                 }
    
29.                 it1->second += it2->second;
    
30.                 um.erase(it2);
    
31.             }
    
32.             ++it1;
    
33.         }
    
34.         int ans = 0;
    
35.         for (it1 = um.begin(); it1 != um.end(); ++it1) {
    
36.             ans = max(ans, it1->second);
    
37.         }
    
38.         return ans;
    
39.     }
    
40. };

复制代码

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

Backpack II
题意：典型的背包问题，给定N件物品和M容量，求可获得的最大价值。
解法：DP。
代码：

1. // O(n * m) time, O(m) space
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     /**
   
8.      * @param m: An integer m denotes the size of a backpack
   
9.      * @param A & V: Given n items with size A[i] and value V[i]
   
10.      * @return: The maximum value
    
11.      */
    
12.     int backPackII(int m, vector<int> A, vector<int> V) {
    
13.         vector<int> dp;
    
14.         int n = A.size();
    
15.         int i, j;
    
16.         
    
17.         dp.resize(m + 1, -1);
    
18.         dp[0] = 0;
    
19.         for (i = 0; i < n; ++i) {
    
20.             for (j = m; j >= A[i]; --j) {
    
21.                 if (dp[j - A[i]] < 0) {
    
22.                     continue;
    
23.                 }
    
24.                 dp[j] = max(dp[j], dp[j - A[i]] + V[i]);
    
25.             }
    
26.         }
    
27.         int ans = 0;
    
28.         for (i = m; i >= 0; --i) {
    
29.             ans = max(ans, dp[i]);
    
30.         }
    
31.         return ans;
    
32.     }
    
33. };

复制代码

实现：时间O(N * M)，空间O(M)。

Max Tree
题意：Cartesian tree
解法1：首先，构造笛卡尔树的关键是找到最大点。那么就在“找到最大”上面想办法。于是想到了RMQ问题的稀疏表解法，因为数组的内容是不会变的。
代码1：

1. // O(log ^ 2(n)) solution, using RMQ
   
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 A: Given an integer array with no duplicates.
    
18.      * @return: The root of max tree.
    
19.      */
    
20.     TreeNode* maxTree(vector<int> A) {
    
21.         int n = A.size();
    
22.         if (n == 0) {
    
23.             return NULL;
    
24.         }
    
25.         
    
26.         st.clear();
    
27.         calcSparseTable(A);
    
28.         
    
29.         return maxTreeRecur(A, 0, A.size() - 1);
    
30.     }
    
31. private:
    
32.     // Needed for RMQ
    
33.     vector<vector<int> > st;
    
34.    
    
35.     TreeNode *maxTreeRecur(vector<int> &a, int ll, int rr) {
    
36.         if (ll > rr) {
    
37.             return NULL;
    
38.         }
    
39.         int i, mi;
    
40.         
    
41.         mi = RMQ(a, ll, rr);
    
42.         TreeNode *root = new TreeNode(a[mi]);
    
43.         root->left = maxTreeRecur(a, ll, mi - 1);
    
44.         root->right = maxTreeRecur(a, mi + 1, rr);
    
45.         return root;
    
46.     }
    
47.    
    
48.     void calcSparseTable(vector<int> &a) {
    
49.         int n = a.size();
    
50.         int b = 1;
    
51.         int m = 1;
    
52.         while (b << 1 <= n) {
    
53.             b <<= 1;
    
54.             ++m;
    
55.         }
    
56.         st.resize(m, vector<int>(n));
    
57.         int i;
    
58.         for (i = 0; i < n; ++i) {
    
59.             st[0][i] = i;
    
60.         }
    
61.         b = 1;
    
62.         int j;
    
63.         for (i = 1; i < m; ++i) {
    
64.             for (j = 0; j + (b << 1) <= n; ++j) {
    
65.                 if (a[st[i - 1][j]] > a[st[i - 1][j + b]]) {
    
66.                     st[i][j] = st[i - 1][j];
    
67.                 } else {
    
68.                     st[i][j] = st[i - 1][j + b];
    
69.                 }
    
70.             }
    
71.             b <<= 1;
    
72.         }
    
73.     }
    
74.    
    
75.     int RMQ(vector<int> &a, int ll, int rr) {
    
76.         int b = 1;
    
77.         int i = 0;
    
78.         while (b << 1 <= rr - ll + 1) {
    
79.             b <<= 1;
    
80.             ++i;
    
81.         }
    
82.         if (a[st[i][ll]] > a[st[i][rr - b + 1]]) {
    
83.             return st[i][ll];
    
84.         } else {
    
85.             return st[i][rr - b + 1];
    
86.         }
    
87.     }
    
88. };

复制代码

复杂度1：平均时间O(log^2(N))，最坏时间O(N * log(N))。空间O(N * log(N))。

解法2：这种解法我没独立想出来，参考了github其他人上的代码。思路一两句话说不清楚，利用了单调栈。感觉得多看几遍代码才能理解，很巧妙。
代码2：

1. // Cartesian Tree, make it O(n)
   
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 A: Given an integer array with no duplicates.
    
18.      * @return: The root of max tree.
    
19.      */
    
20.     TreeNode* maxTree(vector<int> A) {
    
21.         int n = A.size();
    
22.         if (n == 0) {
    
23.             return NULL;
    
24.         }
    
25.         stack<TreeNode *> st;
    
26.         TreeNode *p, *p1, *p2;
    
27.         int i;
    
28.         for (i = 0; i < n; ++i) {
    
29.             p = new TreeNode(A[i]);
    
30.             if (!st.empty() && A[i] > st.top()->val) {
    
31.                 p1 = st.top();
    
32.                 st.pop();
    
33.                 while (!st.empty() && A[i] > st.top()->val) {
    
34.                     p2 = st.top();
    
35.                     st.pop();
    
36.                     p2->right = p1;
    
37.                     p1 = p2;
    
38.                 }
    
39.                 p->left = p1;
    
40.             }
    
41.             st.push(p);
    
42.         }
    
43.         
    
44.         TreeNode *r = st.top();
    
45.         st.pop();
    
46.         while (!st.empty()) {
    
47.             st.top()->right = r;
    
48.             r = st.top();
    
49.             st.pop();
    
50.         }
    
51.         return r;
    
52.     }
    
53. };

复制代码

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