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

zhuli19901106 发表于 2015-7-23 21:29
好吧，如果是程序计算文本相似度来过滤垃圾信息的话，那也没办法了。。
我也不能每题换种语言去写@_@

楼主加油，支持你！

Wildcard Matching
题意：hard难度。实现通配符的功能。
解法：个人觉得这题和正则匹配是这里面最难的题之一。为了处理*，依然是要处理匹配失败时的回溯问题。不过这题的回溯方法比正则要简单，只用保存最后一个*的位置。
代码：

1. #include <cstring>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param s: A string
   
8.      * @param p: A string includes "?" and "*"
   
9.      * @return: A boolean
   
10.      */
    
11.     bool isMatch(const char *s, const char *p) {
    
12.         if (s == NULL || p == NULL) {
    
13.             return false;
    
14.         }
    
15.         int ls = strlen(s);
    
16.         int lp = strlen(p);
    
17.         if (lp == 0) {
    
18.             return ls == 0;
    
19.         }
    
20.         
    
21.         int i, j;
    
22.         int star_s, star_p;
    
23.         
    
24.         i = j = 0;
    
25.         star_s = star_p = -1;
    
26.         while (i < ls) {
    
27.             if (p[j] == '?' || s[i] == p[j]) {
    
28.                 ++i;
    
29.                 ++j;
    
30.             } else if (p[j] == '*') {
    
31.                 star_p = j++;
    
32.                 star_s = i;
    
33.             } else if (star_p != -1) {
    
34.                 i = ++star_s;
    
35.                 j = star_p + 1;
    
36.             } else {
    
37.                 return false;
    
38.             }
    
39.         }
    
40.         while (j < lp && p[j] == '*') {
    
41.             ++j;
    
42.         }
    
43.         return j == lp;
    
44.     }
    
45. };

复制代码

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

sun403 发表于 2015-7-23 22:46
Lintcode上 space replacement  程序中return的是int数据， 题目要求是输出最后的string，楼主怎么写的这部 ...

这题可以从头到尾扫一遍，看有多少个空格。
然后从尾到头扫一遍，碰见空格就写“%20”，碰见其他字符就直接写。
因为第一遍已经确定了空格的个数，所以第二遍每个字符该放哪儿都是可以确定的。这题在后面，我还得有几天才能写到。

Segment Tree Build
题意：线段树的构造。对于搞竞赛的人，线段树肯定是贴身宝贝。对于我们这些没搞过的，就很陌生了。所以要学一下。
解法：依题意来。纯线段树当然是很耗空间的。此处顺便提一下：“mm = (ll + rr) / 2;”这种写法是错误的，学数值分析时第一堂课老师就讲这个。
代码：

1. /**
   
2. * Definition of SegmentTreeNode:
   
3. * class SegmentTreeNode {
   
4. * public:
   
5. *     int start, end;
   
6. *     SegmentTreeNode *left, *right;
   
7. *     SegmentTreeNode(int start, int end) {
   
8. *         this->start = start, this->end = end;
   
9. *         this->left = this->right = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. typedef SegmentTreeNode STN;
    
14. class Solution {
    
15. public:
    
16.     /**
    
17.      *@param start, end: Denote an segment / interval
    
18.      *@return: The root of Segment Tree
    
19.      */
    
20.     STN *build(int start, int end) {
    
21.         if (start > end) {
    
22.             return NULL;
    
23.         }
    
24.         STN *root = new STN(start, end);
    
25.         if (start == end) {
    
26.             return root;
    
27.         }
    
28.         int mid = start + (end - start) / 2;
    
29.         root->left = build(start, mid);
    
30.         root->right = build(mid + 1, end);
    
31.         return root;
    
32.     }
    
33. };

复制代码

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

说到线段树，想起了POJ上一道线段树入门题我还没做，于是跑去写。
http://poj.org/problem?id=2528
没想到leetcode做久了，已经忘了POJ坑爹的风格：常数优化。
从一开始以为很快就能AC，到后来越写bug越多，各种调优。中途POJ服务器还挂了好几次。到AC的时候，已经半夜三点了(T_T)

1. // 2528        Accepted        10872K        94MS        G++        3383B        2015-07-24 02:49:48
   
2. #include <algorithm>
   
3. #include <cstdio>
   
4. #include <cstring>
   
5. using namespace std;
   
6. 
   
7. const int N = 100005;
   
8. int s[N];
   
9. int e[N];
   
10. 
    
11. int d1[2 * N];
    
12. int dc1;
    
13. 
    
14. int d[3 * N];
    
15. int dc;
    
16. 
    
17. int n;
    
18. int b[N];
    
19. int ans;
    
20. 
    
21. typedef struct SegmentTreeNode {
    
22.     int start, end;
    
23.     int tag;
    
24.     SegmentTreeNode *left, *right;
    
25.    
    
26.     SegmentTreeNode(int _start = 0, int _end = 0) {
    
27.         start = _start;
    
28.         end = _end;
    
29.         tag = -1;
    
30.         left = right = NULL;
    
31.     }
    
32. } STN;
    
33. const int MAX_NODE = 500000;
    
34. STN nodes[MAX_NODE];
    
35. int nc;
    
36. 
    
37. int mymin(int x, int y)
    
38. {
    
39.     return x < y ? x : y;
    
40. }
    
41. 
    
42. int mymax(int x, int y)
    
43. {
    
44.     return x > y ? x : y;
    
45. }
    
46. 
    
47. STN *buildTree(int start, int end)
    
48. {
    
49.     if (start > end) {
    
50.         return NULL;
    
51.     }
    
52.     STN *root = &(nodes[nc++]);
    
53.     root->start = start;
    
54.     root->end = end;
    
55.     if (start == end) {
    
56.         return root;
    
57.     }
    
58.     int mid = start + (end - start >> 1);
    
59.     if (mid < end) {
    
60.         root->left = buildTree(start, mid);
    
61.     }
    
62.     if (mid + 1 > start) {
    
63.         root->right = buildTree(mid + 1, end);
    
64.     }
    
65.     return root;
    
66. }
    
67. 
    
68. void addPoster(STN *root, int start, int end, int tag)
    
69. {
    
70.     if (start > end) {
    
71.         return;
    
72.     }
    
73.     if (start == root->start && end == root->end) {
    
74.         root->tag = tag;
    
75.         return;
    
76.     }
    
77.     int mid = root->start + (root->end - root->start >> 1);
    
78.     int oldtag = root->tag;
    
79.     root->tag = -1;
    
80.     if (oldtag >= 0) {
    
81.         addPoster(root, root->start, start - 1, oldtag);
    
82.         addPoster(root, end + 1, root->end, oldtag);
    
83.     }
    
84.    
    
85.     addPoster(root->left, start, mymin(mid, end), tag);
    
86.     addPoster(root->right, mymax(mid + 1, start), end, tag);
    
87. }
    
88. 
    
89. void countPoster(STN *root)
    
90. {
    
91.     if (root == NULL) {
    
92.         return;
    
93.     }
    
94.     if (root->tag >= 0) {
    
95.         if (!b[root->tag]) {
    
96.             b[root->tag] = 1;
    
97.             ++ans;
    
98.         }
    
99.         return;
    
100.     }
     
101.     countPoster(root->left);
     
102.     countPoster(root->right);
     
103. }
     
104. 
     
105. void discretization()
     
106. {
     
107.     dc = 0;
     
108.     d[dc++] = d1[0];
     
109.     int i;
     
110.     for (i = 1; i < dc1; ++i) {
     
111.         if (d1[i] - d1[i - 1] > 1) {
     
112.             d[dc++] = d1[i - 1] + (d1[i] - d1[i - 1] >> 1);
     
113.         }
     
114.         d[dc++] = d1[i];
     
115.     }
     
116. }
     
117. 
     
118. void clearTree(STN *root)
     
119. {
     
120.     if (root == NULL) {
     
121.         return;
     
122.     }
     
123.     clearTree(root->left);
     
124.     clearTree(root->right);
     
125. 
     
126.     root->left = NULL;
     
127.     root->right = NULL;
     
128.     root->tag = -1;
     
129.     --nc;
     
130. }
     
131. 
     
132. int removeDuplicate(int a[], int n)
     
133. {
     
134.     int i, j;
     
135.     int n1 = 0;
     
136. 
     
137.     i = 0;
     
138.     while (i < n) {
     
139.         j = i + 1;
     
140.         while (j < n && a[i] == a[j]) {
     
141.             ++j;
     
142.         }
     
143.         a[n1++] = a[i];
     
144.         i = j;
     
145.     }
     
146.     return n1;
     
147. }
     
148. 
     
149. int bs(int x)
     
150. {
     
151.     int ll = 0;
     
152.     int rr = dc - 1;
     
153.     int mm;
     
154.     while (ll <= rr) {
     
155.         mm = ll + (rr - ll >> 1);
     
156.         if (x < d[mm]) {
     
157.             rr = mm - 1;
     
158.         } else if (x > d[mm]) {
     
159.             ll = mm + 1;
     
160.         } else {
     
161.             return mm;
     
162.         }
     
163.     }
     
164.     return -1;
     
165. }
     
166. 
     
167. void solve()
     
168. {
     
169.     scanf("%d", &n);
     
170.    
     
171.     int i;
     
172.     dc1 = 0;
     
173.     for (i = 0; i < n; ++i) {
     
174.         scanf("%d%d", &s[i], &e[i]);
     
175.         d1[dc1++] = s[i];
     
176.         d1[dc1++] = e[i];
     
177.     }
     
178.     sort(d1, d1 + dc1);
     
179.     dc1 = removeDuplicate(d1, dc1);
     
180.    
     
181.     discretization();
     
182.    
     
183.     STN *root = buildTree(0, dc - 1);
     
184.     for (i = 0; i < n; ++i) {
     
185.         addPoster(root, bs(s[i]), bs(e[i]), i);
     
186.     }
     
187.    
     
188.     ans = 0;
     
189.     memset(b, 0, sizeof(b));
     
190.     countPoster(root);
     
191.     printf("%d\n", ans);
     
192.    
     
193.     clearTree(root);
     
194. }
     
195. 
     
196. int main()
     
197. {
     
198.     int t, ti;
     
199.    
     
200.     scanf("%d", &t);
     
201.     for (ti = 0; ti < t; ++ti) {
     
202.         solve();
     
203.     }
     
204.    
     
205.     return 0;
     
206. }

复制代码

思维有多乱，代码就有多烂。我自己都晕了。

也借这题说说C/C++常系数优化的事吧：
1. set和map很好用，但是手写二分比它们要快。
2. sort函数效率很高，自己手写快排没它快。
3. vector的效率和数组差了好几倍。
4. memset比fill要快
5. new东西很慢，用全局数组比逐个动态分配会快很多。
6. 递归效率不一定低，写法是关键。
7. cin比scanf慢10倍。但如果用了ios::sync_with_stdio(false);则不再需要和C的缓冲区保持同步，于是速度几乎一样了。
8. 位运算可以代替2相关的乘除法，速度差别很大。
9. emplace_back比push_back快点，因为少了一次复制。
把上面的优化技巧都用到了，这题就能在100ms内AC，都不用的话就严重超时。然而，这些都跟复杂度没半毛钱关系。复杂度始终是一样的。
这就是《编程珠玑》里提到的“程序调优”。

Segment Tree Query
题意：RMQ问题。只要求实现query函数。
解法：分情况讨论的话，代码会很复杂。应该尽量搞简单点。
代码：

1. #include <algorithm>
   
2. #include <climits>
   
3. using namespace std;
   
4. /**
   
5. * Definition of SegmentTreeNode:
   
6. * class SegmentTreeNode {
   
7. * public:
   
8. *     int start, end, max;
   
9. *     SegmentTreeNode *left, *right;
   
10. *     SegmentTreeNode(int start, int end, int max) {
    
11. *         this->start = start;
    
12. *         this->end = end;
    
13. *         this->max = max;
    
14. *         this->left = this->right = NULL;
    
15. *     }
    
16. * }
    
17. */
    
18. typedef SegmentTreeNode STN;
    
19. class Solution {
    
20. public:
    
21.     /**
    
22.      *@param root, start, end: The root of segment tree and
    
23.      *                         an segment / interval
    
24.      *@return: The maximum number in the interval [start, end]
    
25.      */
    
26.     int query(STN *root, int start, int end) {
    
27.         if (start > end) {
    
28.             return INT_MIN;
    
29.         }
    
30.         if (start == root->start && end == root->end) {
    
31.             return root->max;
    
32.         }
    
33.         int mid = root->start + (root->end - root->start >> 1);
    
34.         int ans = INT_MIN;
    
35.         ans = max(ans, query(root->left, start, min(end, mid)));
    
36.         ans = max(ans, query(root->right, max(start, mid + 1), end));
    
37.         return ans;
    
38.     }
    
39. };

复制代码

复杂度：时间O(log(N))，空间O(log(N))。整棵树的空间不算在query的复杂度里。

Segment Tree Modify
题意：RMQ问题。这回要实现修改单个元素的功能。
解法：逐步向下搜索，然后反过来向上更新最大值。
代码：

1. /**
   
2. * Definition of SegmentTreeNode:
   
3. * class SegmentTreeNode {
   
4. * public:
   
5. *     int start, end, max;
   
6. *     SegmentTreeNode *left, *right;
   
7. *     SegmentTreeNode(int start, int end, int max) {
   
8. *         this->start = start;
   
9. *         this->end = end;
   
10. *         this->max = max;
    
11. *         this->left = this->right = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16. public:
    
17.     /**
    
18.      *@param root, index, value: The root of segment tree and
    
19.      *@ change the node's value with [index, index] to the new given value
    
20.      *@return: void
    
21.      */
    
22.     void modify(SegmentTreeNode *root, int index, int value) {
    
23.         if (root->start == root->end) {
    
24.             root->max = value;
    
25.             return;
    
26.         }
    
27.         int mid = root->start + (root->end - root->start) / 2;
    
28.         if (index <= mid) {
    
29.             modify(root->left, index, value);
    
30.         } else {
    
31.             modify(root->right, index, value);
    
32.         }
    
33.         root->max = max(root->left->max, root->right->max);
    
34.     }
    
35. };

复制代码

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

Singleton
题意：实现单体模式。
解法：C++的写法中有个语法问题，看最后一行代码。另外，如果要对多线程适用的话，就得加锁。
代码：

1. class Solution {
   
2. public:
   
3.     static Solution *getInstance() {
   
4.         if (instance == NULL) {
   
5.             instance = new Solution();
   
6.         }
   
7.                 return instance;
   
8.     }
   
9. private:
   
10.     Solution();
    
11.     static Solution *instance;
    
12. };
    
13. Solution *Solution::instance = NULL;

复制代码

复杂度：非算法题。

Interval Minimum Number
题意：RMQ问题。
解法：使用ST算法。这题对搞竞赛的人有好几种解法，我只选最好写的ST算法。其他解法还包括线段树、笛卡尔树，肯定没这个好写就是了。
代码：

1. // Solution using sparse table
   
2. #include <algorithm>
   
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. class Solution {
    
14. public:
    
15.     /**
    
16.      *@param A, queries: Given an integer array and an query list
    
17.      *@return: The result list
    
18.      */
    
19.     vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {
    
20.         // Sparse table
    
21.         vector<vector<int> > st;
    
22.         int base = 1;
    
23.         int n = A.size();
    
24.         int m = 1;
    
25.         while (base << 1 <= n) {
    
26.             base <<= 1;
    
27.             ++m;
    
28.         }
    
29.         base = 1;
    
30.         st.resize(m);
    
31.         
    
32.         int i;
    
33.         for (i = 0; i < m; ++i) {
    
34.             st[i].resize(n - base + 1);
    
35.             base <<= 1;
    
36.         }
    
37.         
    
38.         for (i = 0; i < n; ++i) {
    
39.             st[0][i] = A[i];
    
40.         }
    
41.         
    
42.         int j;
    
43.         base = 1;
    
44.         for (i = 1; i < m; ++i) {
    
45.             base <<= 1;
    
46.             for (j = 0; j + base <= n; ++j) {
    
47.                 st[i][j] = min(st[i - 1][j], st[i - 1][j + (base >> 1)]);
    
48.             }
    
49.         }
    
50.         
    
51.         m = queries.size();
    
52.         int x, y;
    
53.         vector<int> ans;
    
54.         for (i = 0; i < m; ++i) {
    
55.             x = queries[i].start;
    
56.             y = queries[i].end;
    
57.             base = 1;
    
58.             j = 0;
    
59.             while (base << 1 <= y - x + 1) {
    
60.                 base <<= 1;
    
61.                 ++j;
    
62.             }
    
63.             ans.push_back(min(st[j][x], st[j][y + 1 - base]));
    
64.         }
    
65.         return ans;
    
66.     }
    
67. };

复制代码

复杂度：预处理时间O(N * log(N))，每次query时间O(log(N))，空间O(N * log(N))。

zhuli19901106 发表于 2015-7-22 03:11
Longest Consecutive Sequence
题意：给定一个无序数组，求其中能够组成的最长连续序列。比如[100, 4, 200 ...

我想问一下，像这个题还有类似的题目出现过的吗？就是利用HashMap左右延展来解题这类似的题目？这题想了好一会儿都没想到要往Hash结构上靠。。智商太捉急了。。感觉各种hard题目都是出在array上，有啥心得吗？还有就是这个题能用DP吗？如果不能用DP是为啥不能呢？谢谢！