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

stellari 发表于 2015-7-18 22:05
quickSelect可以简单地写成迭代形式的啊。那样空间复杂度就是O(1)了。

哦，对了！谢谢提醒，我居然一直没注意这就是尾递归。。
待我马上改一份出来~

zhuli19901106 发表于 2015-7-18 22:06
因为题目要求不准用加法，用++i或者foreach之类的实质上都要用到加法，所以我特意按照verilog的风格写了3 ...

哦，对。不过，具体到你这个代码来说，也可以不使用有++的循环。因为addBit函数中所有用到 i 的地方都是 (1 << i)，所以，你完全可以干脆就传 1 << i 这个数进来，还省得每次用的时候再移位了。这样，循环就可以写成
for (unsigned int mask  = 1; mask != 0 ; mask <<= 1) {
    addBit(a, b, s, mask, c);
}
之类的。

刚看lz二十几天刷完了感觉每天十二道题才可以。顿时觉得很厉害。后来看到lz已经做了很多很多道题之后也就了然了。

stellari 发表于 2015-7-18 22:16
哦，对。不过，具体到你这个代码来说，也可以不使用有++的循环。因为addBit函数中所有用到 i 的地方都是  ...

也对啊，看来当时复制粘贴还是偷懒了。真要面试时写32个，估计面试官也要鄙视我了~~看来还是懒了，再多想一步就得出这个循环了。

354886 发表于 2015-7-18 22:18
刚看lz二十几天刷完了感觉每天十二道题才可以。顿时觉得很厉害。后来看到lz已经做了很多很多道题之后也就了 ...

是这样的，我大部分时间都花在hard难度上，其他题刷起来还比较流畅。
easy共70题左右，花了两天做完。
medium题目需要一定的思考，我差不多一天十几~二十几题。
hard难度就到了能力的瓶颈了，有很久都想不出来的，也有很久才想出来的。
感觉这里面最有思考价值的，就是hard题目，以及medium中可以进行多种优化的题目。

感觉如果大家能在代码中进行挑错和对比，对改进自己的代码应该有好处的。所以欢迎讨论哈~~

zhuli19901106 发表于 2015-7-18 15:50
A + B Problem
题意：求32位整数之和A + B
解法1：直接相加就不提了。此处可以考虑用全加器的原理，纯位 ...

这题其实还有更简单的解法。原理是：先完全不带Carry Flag每位加一遍，得到一个临时的sum；再单独把每位的Carry Flag都找出来（还要左移一位）。然后再把sum和carry相加。然后又得到新的sum和carry……不停把sum和carry相加，直到carry全为0为止。最差时间复杂度同样是O(logN)，不过，如果这两个数字相加的进位很少的话，实际的循环次数也会很少：

1. 
   
2. int aplusb(int a, int b) {
   
3.         while (b) {
   
4.             int sum = a ^ b;    // Adding without carry flag
   
5.             int carry = (a & b) << 1; // Get only the carry flag
   
6.             a = sum;            // Then in the next step, add
   
7.             b = carry;          // sum(without CF) and CF only
   
8.         }                       // Until one of them (usualy CF) becomes 0.
   
9.         return a;      // Now at least one of a and b must be 0
   
10.     }
    

复制代码

Interleaving String
题意：给定字符串sa，sb，sc。判断sc是否可由sa和sb交叉构成。比如“ab”和“cd”可以交叉构成“acbd”。类似于扑克牌的切牌操作。
解法1：使用动态规划，用dp{i}{j}表示长度i和j的sa、sb前缀是否能交叉构成长度为长度为为 + j的sc前缀。
代码1：

1. class Solution {
   
2. public:
   
3.     /**
   
4.      * Determine whether s3 is formed by interleaving of s1 and s2.
   
5.      * @param s1, s2, s3: As description.
   
6.      * @return: true of false.
   
7.      */
   
8.     bool isInterleave(string s1, string s2, string s3) {
   
9.         int n1 = s1.size();
   
10.         int n2 = s2.size();
    
11.         int n3 = s3.size();
    
12.         if (n1 + n2 != n3) {
    
13.             return false;
    
14.         }
    
15.         if (n1 == 0) {
    
16.             return s2 == s3;
    
17.         }
    
18.         if (n2 == 0) {
    
19.             return s1 == s3;
    
20.         }
    
21.         vector<vector<bool> > dp;
    
22.         int i, j;
    
23.         dp.resize(n1 + 1, vector<bool>(n2 + 1, false));
    
24.         
    
25.         dp[0][0] = true;
    
26.         for (i = 1; i <= n2; ++i) {
    
27.             if (dp[0][i - 1] && s2[i - 1] == s3[i - 1]) {
    
28.                 dp[0][i] = true;
    
29.             }
    
30.         }
    
31.         for (i = 1; i <= n1; ++i) {
    
32.             if (dp[i - 1][0] && s1[i - 1] == s3[i - 1]) {
    
33.                 dp[i][0] = true;
    
34.             }
    
35.         }
    
36.         for (i = 1; i <= n1; ++i) {
    
37.             for (j = 1; j <= n2; ++j) {
    
38.                 if (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) {
    
39.                     dp[i][j] = true;
    
40.                 }
    
41.                 if (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]) {
    
42.                     dp[i][j] = true;
    
43.                 }
    
44.             }
    
45.         }
    
46.         return dp[n1][n2];
    
47.     }
    
48. };

复制代码

复杂度1：时间空间均为O(N* M)

解法2：这种dp递推很常见，特点是当前状态只依赖于相邻的状态。即dp{i}{j}只和dp{i}{j - 1}，dp{i - 1}{j}，dp{i - 1}{j - 1}有关。所以空间可以优化为O(M)。
代码2：

1. // O(n ^ 2) solution with space optimization
   
2. class Solution {
   
3. public:
   
4.     /**
   
5.      * Determine whether s3 is formed by interleaving of s1 and s2.
   
6.      * @param s1, s2, s3: As description.
   
7.      * @return: true of false.
   
8.      */
   
9.     bool isInterleave(string s1, string s2, string s3) {
   
10.         int n1 = s1.size();
    
11.         int n2 = s2.size();
    
12.         int n3 = s3.size();
    
13.         if (n1 + n2 != n3) {
    
14.             return false;
    
15.         }
    
16.         if (n1 == 0) {
    
17.             return s2 == s3;
    
18.         }
    
19.         if (n2 == 0) {
    
20.             return s1 == s3;
    
21.         }
    
22.         vector<vector<bool> > dp;
    
23.         int i, j;
    
24.         dp.resize(2, vector<bool>(n2 + 1, false));
    
25.         int f, nf;
    
26.         
    
27.         dp[0][0] = true;
    
28.         for (i = 1; i <= n2; ++i) {
    
29.             if (dp[0][i - 1] && s2[i - 1] == s3[i - 1]) {
    
30.                 dp[0][i] = true;
    
31.             }
    
32.         }
    
33.         
    
34.         f = 1;
    
35.         nf = !f;
    
36.         for (i = 1; i <= n1; ++i) {
    
37.             for (j = 0; j <= n2; ++j) {
    
38.                 dp[f][j] = false;
    
39.             }
    
40.             if (dp[nf][0] && s1[i - 1] == s3[i - 1]) {
    
41.                 dp[f][0] = true;
    
42.             }
    
43.             for (j = 1; j <= n2; ++j) {
    
44.                 if (dp[nf][j] && s1[i - 1] == s3[i + j - 1]) {
    
45.                     dp[f][j] = true;
    
46.                 }
    
47.                 if (dp[f][j - 1] && s2[j - 1] == s3[i + j - 1]) {
    
48.                     dp[f][j] = true;
    
49.                 }
    
50.             }
    
51.             f = !f;
    
52.             nf = !f;
    
53.         }
    
54.         f = !f;
    
55.         return dp[f][n2];
    
56.     }
    
57. };

复制代码

复杂度2：时间为O(N* M)，空间可优化到O(M)。

stellari 发表于 2015-7-18 22:53
这题其实还有更简单的解法。原理是：先完全不带Carry Flag每位加一遍，得到一个临时的sum；再单独把每位 ...

这思路神奇，完全没想到。果然脑子快了代码都能写出花样来啊，哈哈~~

Insert Interval
题意：给定一组已经排好序的区间，互不相交。请你插入一个新区间进去，保证插入完成后依然是互不相交。
解法：问题就是如何处理区间合并了。这题如果想复杂，就会做复杂。所以往简单了想，想想区间的左端和右端分别怎么处理就行了。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. /**
   
4. * Definition of Interval:
   
5. * classs Interval {
   
6. *     int start, end;
   
7. *     Interval(int start, int end) {
   
8. *         this->start = start;
   
9. *         this->end = end;
   
10. *     }
    
11. */
    
12. class Solution {
    
13. public:
    
14.     /**
    
15.      * Insert newInterval into intervals.
    
16.      * @param intervals: Sorted interval list.
    
17.      * @param newInterval: new interval.
    
18.      * @return: A new interval list.
    
19.      */
    
20.     vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
    
21.         vector<Interval> &a = intervals;
    
22.         Interval b = newInterval;
    
23.         int i, n = a.size();
    
24.         
    
25.         vector<Interval> ans;
    
26.         i = 0;
    
27.         while (i < n && a[i].end < b.start) {
    
28.             ans.push_back(a[i++]);
    
29.         }
    
30.         while (i < n && b.end >= a[i].start) {
    
31.             b.start = min(b.start, a[i].start);
    
32.             b.end = max(b.end, a[i].end);
    
33.             ++i;
    
34.         }
    
35.         ans.push_back(b);
    
36.         while (i < n) {
    
37.             ans.push_back(a[i++]);
    
38.         }
    
39.         return ans;
    
40.     }
    
41. };

复制代码

复杂度：时间是O(N)，空间O(1)。如果用二分可以做到更优，我偷懒了没写。不过worst case时间肯定是O(N)的。

zhuli19901106 发表于 2015-7-18 22:24
是这样的，我大部分时间都花在hard难度上，其他题刷起来还比较流畅。
easy共70题左右，花了两天做完。
...

medium我一天最多十道已经是极限了。佩服