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

Find Minimum in Rotated Sorted Array
题意：给定一个旋转过的有序数组，不含重复元素。求最小元素。
解法：二分搜索。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param num: the rotated sorted array
   
5.      * @return: the minimum number in the array
   
6.      */
   
7.     int findMin(vector<int> &num) {
   
8.         int n = num.size();
   
9.         if (n == 1) {
   
10.             return num[0];
    
11.         }
    
12.         int ll, mm, rr;
    
13.         ll = 0;
    
14.         rr = n - 1;
    
15.         if (num[ll] < num[rr]) {
    
16.             return num[ll];
    
17.         }
    
18.         while (rr - ll > 1) {
    
19.             mm = ll + (rr - ll) / 2;
    
20.             if (num[mm] > num[rr]) {
    
21.                 ll = mm;
    
22.             } else {
    
23.                 rr = mm;
    
24.             }
    
25.         }
    
26.         return num[rr];
    
27.     }
    
28. };

复制代码

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

Find Minimum in Rotated Sorted Array II
题意：给定一个旋转过的有序数组，可以包含重复元素。求最小元素。
解法：依然是二分，不过对重复元素要加上处理。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param num: the rotated sorted array
   
8.      * @return: the minimum number in the array
   
9.      */
   
10.     int findMin(vector<int> &num) {
    
11.         int n = num.size();
    
12.         if (n == 1) {
    
13.             return num[0];
    
14.         }
    
15.         int ll, mm, rr;
    
16.         ll = 0;
    
17.         rr = n - 1;
    
18.         while (rr - ll > 1) {
    
19.             if (num[ll] < num[rr]) {
    
20.                 return num[ll];
    
21.             }
    
22.             if (num[ll] == num[rr]) {
    
23.                 ++ll;
    
24.                 continue;
    
25.             }
    
26.             mm = ll + (rr - ll) / 2;
    
27.             if (num[mm] > num[rr]) {
    
28.                 ll = mm;
    
29.             } else {
    
30.                 rr = mm;
    
31.             }
    
32.         }
    
33.         return min(num[ll], num[rr]);
    
34.     }
    
35. };

复制代码

复杂度：时间O(log(N))，空间O(1)。时间最坏可以到O(N)。

Rotate Image
题意：给定一个NxN的矩阵，就地顺时针旋转90度。
解法：分成上下左右四个子矩阵，找出它们每个元素的对应关系。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param matrix: A list of lists of integers
   
5.      * @return: Void
   
6.      */
   
7.     void rotate(vector<vector<int> > &matrix) {
   
8.         vector<vector<int> > &a = matrix;
   
9.         int n = a.size();
   
10.         if (n == 0) {
    
11.             return;
    
12.         }
    
13.         
    
14.         int tmp;
    
15.         int i, j;
    
16.         for (i = 0; i < n / 2; ++i) {
    
17.             for (j = 0; j < (n + 1) / 2; ++j) {
    
18.                 tmp = a[i][j];
    
19.                 a[i][j] = a[n - 1 - j][i];
    
20.                 a[n - 1 - j][i] = a[n - 1 - i][n - 1 - j];
    
21.                 a[n - 1 - i][n - 1 - j] = a[j][n - 1 - i];               
    
22.                 a[j][n - 1 - i] = tmp;
    
23.             }
    
24.         }
    
25.     }
    
26. };

复制代码

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

Set Matrix Zeroes
题意：给定一个NxM的矩阵，如果某个元素是0，则把对应的整行整列全都设成0。要求就地完成。
解法：可以把第一行，第一列作为标记数组，额外再用两个变量即可。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param matrix: A list of lists of integers
   
5.      * @return: Void
   
6.      */
   
7.     void setZeroes(vector<vector<int> > &matrix) {
   
8.         vector<vector<int> > &a = matrix;
   
9.         int n, m;
   
10.         n = a.size();
    
11.         if (n == 0) {
    
12.             return;
    
13.         }
    
14.         m = a[0].size();
    
15.         if (m == 0) {
    
16.             return;
    
17.         }
    
18.         
    
19.         int i, j;
    
20.         int r0 = 1, c0 = 1;
    
21.         for (i = 0; i < n; ++i) {
    
22.             if (a[i][0] == 0) {
    
23.                 c0 = 0;
    
24.                 break;
    
25.             }
    
26.         }
    
27.         for (i = 0; i < m; ++i) {
    
28.             if (a[0][i] == 0) {
    
29.                 r0 = 0;
    
30.                 break;
    
31.             }
    
32.         }
    
33.         for (i = 1; i < n; ++i) {
    
34.             for (j = 1; j < m; ++j) {
    
35.                 if (a[i][j] == 0) {
    
36.                     a[i][0] = 0;
    
37.                     a[0][j] = 0;
    
38.                 }
    
39.             }
    
40.         }
    
41.         for (i = 1; i < n; ++i) {
    
42.             for (j = 1; j < m; ++j) {
    
43.                 if (a[i][0] && a[0][j]) {
    
44.                     continue;
    
45.                 }
    
46.                 a[i][j] = 0;
    
47.             }
    
48.         }
    
49.         if (r0 == 0) {
    
50.             for (i = 0; i < m; ++i) {
    
51.                 a[0][i] = 0;
    
52.             }
    
53.         }
    
54.         if (c0 == 0) {
    
55.             for (i = 0; i < n; ++i) {
    
56.                 a[i][0] = 0;
    
57.             }
    
58.         }
    
59.     }
    
60. };

复制代码

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

zhuli19901106 发表于 2015-7-22 03:03
Word Search
题意：给定一个字符矩阵A，和一个单词W。允许你从矩阵任意位置出发，上下左右移动。看能不能 ...

143楼的word search这个题目的时间复杂度为啥是O((N * M)!)呢？另外是不是可以考虑把主函数双循环内的标记和取消标记这组回溯操作一起放到递归函数中呢？另外，在网上学到了一招这个题，可以把空间复杂度降到O(1), 即不使用标记数组，而是对访问过的cell先暂存其字符，然后用一个其他非字母字符代替，回溯的时候再把暂存的拿回来放进去，不过也还是有局限性，得假设不会出现这个字母字符。

太可怕了，这是专业选手么。。。。我Leetcode断断续续半年了才刷完190

水逼一枚 发表于 2015-7-23 07:01
143楼的word search这个题目的时间复杂度为啥是O((N * M)!)呢？另外是不是可以考虑把主函数双循环内的标 ...

嗯，我见过这种做法，也这么干过，以前做POJ时就有这种题，当时还觉得能把空间降到O(1)肯定更好，后来工作了才发现算法题中既有大智慧，也有小聪明。区别就在于是否有利于实际工作。好多做算法题的特殊技巧，放在工作中用都是会被揍的。
所以现在我还是倾向于一般性的做法。实际开发中还是要注意规范的，习惯性地改变原数组并不好。
另外，对于标记“已访问”数组放在DFS内部还是外部比较好，我的结论是：完全一样。只要逻辑正确，两者没什么区别。都是DFS+回溯。两种写法我都经常会用。
这种一个数组当成两个用的，在lintcode里就有好几题，比如这题
http://www.lintcode.com/en/problem/sort-colors-ii/
题目所要求的O(1)空间解法，就可以通过在原数组上动歪脑子实现的。

话说那也不叫O(1)。。。应该是省了一个数组。空间复杂度还要算递归中的参数开销。

liyimeng 发表于 2015-7-23 07:14
太可怕了，这是专业选手么。。。。我Leetcode断断续续半年了才刷完190

不敢。。我并没搞过竞赛。但是把刷题当作爱好，几年下来也刷过一两千题，所以只是打字比较快。

水逼一枚 发表于 2015-7-23 07:01
143楼的word search这个题目的时间复杂度为啥是O((N * M)!)呢？另外是不是可以考虑把主函数双循环内的标 ...

对了，忘记回答时间复杂度问题了。貌似应该是指数级，不是阶乘，当时没细想。

递归算法的时间复杂度我都没太仔细推导，要细推的话，式子会复杂很多，这编辑器不支持LaTeX，写起来会很麻烦。这儿有两百多题，要在草稿纸上证明复杂度，怕是比我做完一题的时间还要多，耗不起。

DFS的理论复杂度通常都暴高，实际运行效率则取决于剪枝的好坏、数据的好坏。这种题目，完全可以给出那种变态的bad case（让你的程序很难剪枝，要么递归到爆栈，要么超时），让人几乎无法AC，但那样对于学习编程的人意义就不大了。只是出题人不这么干罢了，为了让我们做出来。

可以这么说：你剪枝剪得必须非常好，才能应付绝大多数bad case。换言之，你剪枝剪得稍微不好，就能轻易找到bad case，让你的代码变得出奇的慢。

此处可以举个例子：
我在POJ上做过一道解数独的题，复杂度很高，对吧。我正向DFS，结果超时。改成反向DFS，于是AC了。
leetcode上也有相同的解数独的题，照理说完全一样。于是我反向DFS，超时了。改回正向，于是AC了。
（当然，要是能写出dancing-links就得另当别论）
OJ对于这些DFS题通常是很宽容的，因为如果真的逼近了理论复杂度，那运行时间是很恐怖的。所以给的test case大多不会太烂，保证你的DFS不会走的太深，或者搜到解的位置不会太靠后。要不就超时了。

如果把POJ和leetcode上的test case结合起来，估计只有dancing links能够AC。

按照算法导论上的解释，复杂度分析要以worst-case为主，只有worst case几乎不会出现时，才关注average case。

Unique Binary Search Trees
题意：中序遍历结果为1-N的BST可以有多少种不同的形态？
解法1：Catalan数。直接递推来算。
代码1：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @paramn n: An integer
   
5.      * @return: An integer
   
6.      */
   
7.     int numTrees(int n) {
   
8.         vector<int> v;
   
9.         v.push_back(1);
   
10.         v.push_back(1);
    
11.         int i, j;
    
12.         for (i = 2; i <= n; ++i) {
    
13.             v.push_back(0);
    
14.             for (j = 0; j < i; ++j) {
    
15.                 v[i] += v[j] * v[i - 1 - j];
    
16.             }
    
17.         }
    
18.         return v[n];
    
19.     }
    
20. };

复制代码

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

解法2：直接用组合公式。
代码2：

1. typedef long long int LL;
   
2. class Solution {
   
3. public:
   
4.     /**
   
5.      * @paramn n: An integer
   
6.      * @return: An integer
   
7.      */
   
8.     int numTrees(int n) {
   
9.         return C(2 * n, n) / (n + 1);
   
10.     }
    
11. private:
    
12.     LL C(int n, int k) {
    
13.         LL sum = 1;
    
14.         int i;
    
15.         LL q = 1;
    
16.         for (i = 1; i <= k; ++i) {
    
17.             sum *= n + 1 - i;
    
18.             q *= i;
    
19.             if (sum % q == 0) {
    
20.                 sum /= q;
    
21.                 q = 1;
    
22.             }
    
23.         }
    
24.         return sum;
    
25.     }
    
26. };

复制代码

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