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

Count of Smaller Number before itself
题意：hard难度。给定一个整数数组，元素都介于0-10000之间。对于每个元素A{i}，求它前面有多少个比它小的。
解法：这题又用到了树状数组，注意0-10000这个条件的作用。如果我们直接开个长度为10001的数组B，对于每个A{i}，都把B的对应位置B{A{i}}加上1，那么A{i}前面比它小的元素的个数，就等于B{0} + B{1} + ... + B{A{i} - 1}。于是，能够快速求和的树状数组就派上用场了。
这题如果数据较大的话，比如两亿，那么就得通过离散化的思路映射成小数据。
代码：

1. class Solution {
   
2. public:
   
3.    /**
   
4.      * @param A: An integer array
   
5.      * @return: Count the number of element before this element 'ai' is
   
6.      *          smaller than it and return count number array
   
7.      */
   
8.     vector<int> countOfSmallerNumberII(vector<int> &A) {
   
9.         vector<int> s(N + 1, 0);
   
10.         vector<int> ans;
    
11.         int n = A.size();
    
12.         int i;
    
13.         for (i = 0; i < n; ++i) {
    
14.             // Offset by 1
    
15.             ans.push_back(sum(s, A[i]));
    
16.             add(s, A[i] + 1, 1);
    
17.         }
    
18.         return ans;
    
19.     }
    
20. private:
    
21.     static const int N = 10001;
    
22.    
    
23.     int lowbit(int x) {
    
24.         return x & -x;
    
25.     }
    
26.    
    
27.     int sum(vector<int> &a, int i) {
    
28.         int sum = 0;
    
29.         while (i > 0) {
    
30.             sum += a[i];
    
31.             i -= lowbit(i);
    
32.         }
    
33.         return sum;
    
34.     }
    
35.    
    
36.     void add(vector<int> &a, int i, int val) {
    
37.         if (i == 0) {
    
38.             return;
    
39.         }
    
40.         while (i <= N) {
    
41.             a[i] += val;
    
42.             i += lowbit(i);
    
43.         }
    
44.     }
    
45. };

复制代码

复杂度：时间O(N * log(M))，其中M表示数组元素的范围，此处是10000。空间是O(M)。

Longest Substring with At Most K Distinct Characters
题意：给定一个字符串，求至多包含K种不同字符的最长字串。
解法：依然是用首尾两个指针，边移动边统计字符个数，字符种类的方法。扫描过程中随时更新结果。
代码：

1. #include <cstring>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param s : A string
   
8.      * @return : The length of the longest substring
   
9.      *           that contains at most k distinct characters.
   
10.      */
    
11.     int lengthOfLongestSubstringKDistinct(string s, int k) {
    
12.         int c[256];
    
13.         int n = s.length();
    
14.         
    
15.         if (n == 0 || k == 0) {
    
16.             return 0;
    
17.         }
    
18.         
    
19.         int ans = 0;
    
20.         memset(c, 0, sizeof(c));
    
21.         int cc = 0;
    
22.         int i, j;
    
23.         i = j = 0;
    
24.         while (j < n) {
    
25.             if (c[s[j]] == 0) {
    
26.                 ++cc;
    
27.             }
    
28.             ++c[s[j]];
    
29.             if (cc <= k) {
    
30.                 ans = max(ans, j - i + 1);
    
31.                 ++j;
    
32.                 continue;
    
33.             }
    
34.             while (cc > k) {
    
35.                 --c[s[i]];
    
36.                 if (c[s[i]] == 0) {
    
37.                     --cc;
    
38.                 }
    
39.                 ++i;
    
40.             }
    
41.             ++j;
    
42.         }
    
43.         return ans;
    
44.     }
    
45. };

复制代码

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

The Smallest Difference
题意：给定两个数组A和B，任选i和j，求A{i}和B{j}的最小差值。
解法1：排好序，一个遍历，一个二分。
代码1：

1. // O(n * log(n)) solution with O(1) space
   
2. #include <algorithm>
   
3. #include <climits>
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     /**
   
9.      * @param A, B: Two integer arrays.
   
10.      * @return: Their smallest difference.
    
11.      */
    
12.     int smallestDifference(vector<int> &A, vector<int> &B) {
    
13.         if (A.size() > B.size()) {
    
14.             return smallestDifference(B, A);
    
15.         }
    
16.         
    
17.         sort(A.begin(), A.end());
    
18.         sort(B.begin(), B.end());
    
19.         
    
20.         int i, j;
    
21.         int ans = INT_MAX;
    
22.         int na = A.size();
    
23.         int nb = B.size();
    
24.         
    
25.         for (i = 0; i < na; ++i) {
    
26.             j = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
    
27.             if (j < nb) {
    
28.                 ans = min(ans, B[j] - A[i]);
    
29.             }
    
30.             if (j > 0) {
    
31.                 ans = min(ans, A[i] - B[j - 1]);
    
32.             }
    
33.         }
    
34.         return ans;
    
35.     }
    
36. };

复制代码

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

解法2：排好序，归并成一个数组，不过要标记每个元素是来自A还是来自B。然后求最小差值。这做法虽然在理论复杂度上没优势，不过后面的归并过程是线性时间，所以还是会快些的。
代码2：

1. // O(n * log(n)) solution with O(n) space
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. int abs(int x)
   
6. {
   
7.     return x >= 0 ? x : -x;
   
8. }
   
9. 
   
10. class Solution {
    
11. public:
    
12.     /**
    
13.      * @param A, B: Two integer arrays.
    
14.      * @return: Their smallest difference.
    
15.      */
    
16.     int smallestDifference(vector<int> &A, vector<int> &B) {
    
17.         sort(A.begin(), A.end());
    
18.         sort(B.begin(), B.end());
    
19.         
    
20.         vector<int> tag;
    
21.         vector<int> C;
    
22.         
    
23.         int na = A.size();
    
24.         int nb = B.size();
    
25.         int i, j;
    
26.         i = j = 0;
    
27.         while (i < na && j < nb) {
    
28.             if (A[i] < B[j]) {
    
29.                 C.push_back(A[i++]);
    
30.                 tag.push_back(0);
    
31.             } else {
    
32.                 C.push_back(B[j++]);
    
33.                 tag.push_back(1);
    
34.             }
    
35.         }
    
36.         if (i < na) {
    
37.             C.push_back(A[i++]);
    
38.             tag.push_back(0);
    
39.         } else {
    
40.             C.push_back(B[j++]);
    
41.             tag.push_back(1);
    
42.         }
    
43.         
    
44.         int n = C.size();
    
45.         int ans = INT_MAX;
    
46.         for (i = 0; i < n - 1; ++i) {
    
47.             if (tag[i] ^ tag[i + 1]) {
    
48.                 ans = min(ans, abs(C[i] - C[i + 1]));
    
49.             }
    
50.         }
    
51.         
    
52.         return ans;
    
53.     }
    
54. };

复制代码

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

Number of Airplanes in the Sky
题意：给定很多飞机的起降时间，请求出同一时刻天上最多有几架飞机。如果存在起降重合的，按照先降后起处理。
解法：这题起初没思路，往线段树那想了，结果没想出来。后来看了别人的解法，才发现可以和括号匹配问题联系起来想。细节参见下列代码。
代码：

1. #include <algorithm>
   
2. #include <utility>
   
3. using namespace std;
   
4. /**
   
5. * Definition of Interval:
   
6. * classs Interval {
   
7. *     int start, end;
   
8. *     Interval(int start, int end) {
   
9. *         this->start = start;
   
10. *         this->end = end;
    
11. *     }
    
12. */
    
13. bool comp(const pair<int, int> &p1, const pair<int, int> &p2)
    
14. {
    
15.     if (p1.first != p2.first) {
    
16.         return p1.first < p2.first;
    
17.     } else {
    
18.         return p1.second > p2.second;
    
19.     }
    
20. }
    
21. 
    
22. class Solution {
    
23. public:
    
24.     /**
    
25.      * @param intervals: An interval array
    
26.      * @return: Count of airplanes are in the sky.
    
27.      */
    
28.     int countOfAirplanes(vector<Interval> &airplanes) {
    
29.         vector<pair<int, int> > v;
    
30.         pair<int, int> p;
    
31.         int n = airplanes.size();
    
32.         int i;
    
33.         for (i = 0; i < n; ++i) {
    
34.             p.first = airplanes[i].start;
    
35.             p.second = 0;
    
36.             v.push_back(p);
    
37.             p.first = airplanes[i].end;
    
38.             p.second = 1;
    
39.             v.push_back(p);
    
40.         }
    
41.         sort(v.begin(), v.end(), comp);
    
42.         int ans = 0;
    
43.         int cnt = 0;
    
44.         n = v.size();
    
45.         for (i = 0; i < n; ++i) {
    
46.             if (v[i].second == 0) {
    
47.                 ++cnt;
    
48.                 ans = max(ans, cnt);
    
49.             } else {
    
50.                 --cnt;
    
51.             }
    
52.         }
    
53.         return ans;
    
54.     }
    
55. };

复制代码

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

Longest Substring Without Repeating Characters
题意：给定一个字符串，求出不含重复字符的最长字串。
解法：依然是两个指针向前走，随时统计字符个数，随时更新结果。
代码：

1. #include <cstring>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param s: a string
   
8.      * @return: an integer
   
9.      */
   
10.     int lengthOfLongestSubstring(string s) {
    
11.         int c[256];
    
12.         int n = s.length();
    
13.         int i, j;
    
14.         int ans = 0;
    
15.         
    
16.         memset(c, 0, sizeof(c));
    
17.         i = j = 0;
    
18.         while (j < n) {
    
19.             if (c[s[j]]) {
    
20.                 while (c[s[j]]) {
    
21.                     --c[s[i++]];
    
22.                 }
    
23.                 c[s[j]] = 1;
    
24.             } else {
    
25.                 c[s[j]] = 1;
    
26.                 ans = max(ans, j - i + 1);
    
27.             }
    
28.             ++j;
    
29.         }
    
30.         return ans;
    
31.     }
    
32. };

复制代码

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

zhuli19901106 发表于 2015-7-18 21:51
Subsets II
题意：给定一个multiset，求其所有子集。
解法：因为可以包含重复元素，所以此时子集的个数不 ...

26楼的SubsetsII这个题目，如果不用sort有什么方法可以解决吗？我在一个群里看到有人再问，也来随便问下。目前想的是可以用hash。楼主有啥想法没呢？

水逼一枚 发表于 2015-7-25 08:04
26楼的SubsetsII这个题目，如果不用sort有什么方法可以解决吗？我在一个群里看到有人再问，也来随便问下 ...

这题的复杂度是指数的，所以用排序对性能的影响可以忽略不计。另外，题目要求不重复、而且每个子集内部必须有序，所以不排序貌似没什好处啊。何乐而不为？
另外，哈希表是无序的，不能保证送进去的元素能够以有序的形式拿出来。如何保证结果中的每个子集有序呢？
私以为题目中经常提示你“能否在不用XXX的情况下完成题目”，是为了鼓励你多想不同思路。但不要刻意为了不用XXX而绞尽脑汁。比如不让你用map，你可以改用数组+排序+二分查找。这种思路不同，但是殊途同归的做法是值得鼓励的。
再来个反例，能否在不用sort的情况下给数组排序？可以，自己手写快排、堆排或者归并。这种“不用”其实没什么意义。
最坏情况，如果你不用一样东西，就没法以同样的效率解出题来，那还是用吧。

zhuli19901106 发表于 2015-7-24 22:44
不是，是研究生刚要开学~

楼主是学习的榜样啊，我也是要上ms，准备转cs，刷到90多题，就感觉好多没思路了。。。

Container With Most Water
题意：给定从位置0~N-1的N个位置，告诉你每个位置的柱子高度。如果允许你选取两个位置作为两堵墙，那么这两堵墙加上地板能够存多少水？
解法：这题的解法很简单，思路却很巧妙，请先看代码然后想想为什么。我第一次碰见时想了很久都没想到这思路，后来，回过头来想其实这种解法可以按照动态规划的思路简化得来。
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param heights: a vector of integers
   
5.      * @return: an integer
   
6.      */
   
7.     int maxArea(vector<int> &heights) {
   
8.         int i, j;
   
9.         int ans = 0;
   
10.         int n = heights.size();
    
11.         
    
12.         i = 0;
    
13.         j = n - 1;
    
14.         while (i < j) {
    
15.             ans = max(ans, (j - i) * min(heights[j], heights[i]));
    
16.             if (heights[i] < heights[j]) {
    
17.                 ++i;
    
18.             } else {
    
19.                 --j;
    
20.             }
    
21.         }
    
22.         return ans;
    
23.     }
    
24. };

复制代码

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

Print Numbers by Recursion
题意：一道无聊的题，为了考而考。
解法：”茴“字有四种写法，你知道吗？
代码：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * @param n: An integer.
   
5.      * return : An array storing 1 to the largest number with n digits.
   
6.      */
   
7.     vector<int> numbersByRecursion(int n) {
   
8.         ans.clear();
   
9.         DFS(0, 0, n);
   
10.         return ans;
    
11.     }
    
12. private:
    
13.     vector<int> ans;
    
14.    
    
15.     void DFS(int num, int idx, int n) {
    
16.         if (idx == n) {
    
17.             if (num > 0) {
    
18.                 ans.push_back(num);
    
19.             }
    
20.             return;
    
21.         }
    
22.         
    
23.         int i;
    
24.         for (i = 0; i < 10; ++i) {
    
25.             DFS(num * 10 + i, idx + 1, n);
    
26.         }
    
27.     }
    
28. };

复制代码

复杂度：懒得算。