9.14-9.20

1.binary-tree-zigzag-level-order-traversal(二叉树的锯齿遍历)

地址：http://www.lintcode.com/zh-cn/problem/binary-tree-zigzag-level-order-traversal/

分析：设置个flag，根据flag来决定是否reverse每行的元素

代码：

 1 class Solution {
 2     /**
 3      * @param root: The root of binary tree.
 4      * @return: A list of lists of integer include
 5      *          the zigzag level order traversal of its nodes' values
 6      */
 7 public:
 8     vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
 9         // write your code here
10         int flag = 0;
11         vector<vector<int>> ans;
12         vector<int> add;
13         if (root == NULL) return ans;
14         queue<TreeNode*> qu, tmp;
15         qu.push(root);
16         while (!qu.empty())
17         {
18             TreeNode *tn = qu.front();
19             add.push_back(tn->val);
20             qu.pop();
21             if (tn->left) tmp.push(tn->left);
22             if (tn->right) tmp.push(tn->right);
23             if (qu.empty())
24             {
25                 if (flag) reverse(add.begin(), add.end());
26                 ans.push_back(add); add.clear();
27                 flag = !flag;
28             }
29             if (qu.empty() && (!tmp.empty()))
30             {
31                 qu = tmp;
32                 while (!tmp.empty()) tmp.pop();
33             }
34         }
35         return ans;
36     }
37 };

View Code

2.combination-sum-ii(数字合并)

地址：http://www.lintcode.com/zh-cn/problem/combination-sum-ii/#

分析：dfs+双指针，注意剪枝

代码：

 1 class Solution {
 2 public:
 3     /**
 4      * @param num: Given the candidate numbers
 5      * @param target: Given the target number
 6      * @return: All the combinations that sum to target
 7      */
 8     void work(int sum, int target, int cnt, int idx, vector<vector<int>> &ans, vector<int>& add, vector<int>& num)
 9     {
10         if (sum > target) return ;
11         if (cnt < 2) return ;
12         if (cnt == 2)
13         {
14             int i = idx, j = num.size()-1;
15             while (i < j)
16             {
17                 if (num[i]+num[j]+sum == target)
18                 {
19                     add.push_back(num[i]); add.push_back(num[j]);
20                     ans.push_back(add);
21                     add.pop_back(); add.pop_back();
22                     i++;
23                 }
24                 else if (num[i]+num[j]+sum > target) j--;
25                 else i++;
26             }
27             return ;
28         }
29         for (int i = idx; i < num.size(); ++i)
30         {
31             if (sum+num[i] > target) break;
32             add.push_back(num[i]);
33             work(sum+num[i], target, cnt-1, i+1, ans, add, num);
34             add.pop_back();
35         }
36     }
37     vector<vector<int> > combinationSum2(vector<int> &num, int target) {
38         // write your code here
39         sort(num.begin(), num.end());
40         vector<vector<int>> ans;
41         vector<int> add;
42         for (int i = 0; i < num.size(); ++i)
43         {
44             if (num[i] == target) 
45             {
46                 add.push_back(target);
47                 ans.push_back(add);
48                 add.clear();
49             }
50         }
51         for (int i = 2; i <= num.size(); ++i)
52             work(0, target, i, 0, ans, add, num);
53         if (ans.size() == 0) return ans;
54         vector<vector<int>> ret;
55         sort(ans.begin(), ans.end());
56         ret.push_back(ans[0]);
57         for (int i = 1; i < ans.size(); ++i)
58             if (ans[i] != ret.back()) ret.push_back(ans[i]);
59         return ret;
60     }
61 };

View Code

3.最大值查询

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5443

分析：直接用线段树搞，简单题目。写的好丑==好久没写了。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <string>
 5 #include <cstring>
 6 #include <set>
 7 #include <utility>
 8 #include <map>
 9 #include <cstdlib>
10 #include <queue>
11 #include <vector>
12 #include <numeric>
13 #include <list>
14 #include <bitset>
15 #include <exception>
16 #include <istream>
17 #include <ostream>
18 #include <stdexcept>
19 #include <functional>
20 #include <typeinfo>
21 
22 #define LL long long int
23 using namespace std;
24 
25 const int maxn = 1010;
26 typedef struct node
27 {
28     int left, right, val;
29 }node;
30 
31 node stree[maxn<<2];
32 int a[maxn];
33 int t, n, q;
34 
35 void build(int root, int l, int r)
36 {
37     if (l == r) stree[root].val = a[l], stree[root].left = l, stree[root].right = r;
38     else
39     {
40         build(2*root, l, (l+r)/2);
41         build(2*root+1, (l+r)/2+1, r);
42         stree[root].left = l, stree[root].right = r;
43         stree[root].val = max(stree[2*root].val, stree[2*root+1].val);
44     }
45 }
46 
47 int query(int root, int l, int r)
48 {
49     if (l > stree[root].right || r < stree[root].left) return INT_MIN;
50     if (stree[root].left >= l && stree[root].right <= r) return stree[root].val;
51     return max(query(root*2, l, r), query(root*2+1, l, r));
52 }
53 
54 int main()
55 {
56     int l, r;
57     scanf("%d", &t);
58     while (t--)
59     {
60         scanf("%d", &n);
61         for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
62         build(1, 0, n-1);
63         scanf("%d", &q);
64         for (int i = 0; i < q; ++i)
65         {
66             scanf("%d%d", &l, &r);
67             printf("%d
", query(1, l-1, r-1));
68         }
69     }
70 
71     return 0;
72 }

View Code

4.最长公共子序列

地址：http://www.lintcode.com/zh-cn/problem/longest-common-subsequence/

分析：DP

代码：

 1 class Solution {
 2 public:
 3     /**
 4      * @param A, B: Two strings.
 5      * @return: The length of longest common subsequence of A and B.
 6      */
 7     int longestCommonSubsequence(string A, string B) {
 8         // write your code here
 9         int dp[1010][1010];
10         memset(dp, 0, sizeof(dp));
11         for (int i = 0; i < A.length(); ++i)
12         {
13             for (int j = 0; j < B.length(); ++j)
14             {
15                 if (A[i] == B[j])
16                 {
17                     if (i == 0 || j == 0) dp[i][j] = 1;
18                     else dp[i][j] = max(dp[i-1][j-1]+1, max(dp[i][j-1], dp[i-1][j]));
19                 }
20                 else
21                 {
22                     if (i == 0 || j ==  0)
23                     {
24                         if (i == 0 && j == 0) dp[i][j] = 0;
25                         else if (i == 0) dp[i][j] = dp[i][j-1];
26                         else dp[i][j] = dp[i-1][j];
27                     }
28                     else dp[i][j] = max(max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
29                 }
30             }
31         }
32         return dp[A.length()-1][B.length()-1];
33     }
34 };

View Code

5.longest-consecutive-sequence(最长连续序列)

地址：http://www.lintcode.com/zh-cn/problem/longest-consecutive-sequence/

分析：Hash

代码：

 1 class Solution {
 2 public:
 3     /**
 4      * @param nums: A list of integers
 5      * @return an integer
 6      */
 7     int longestConsecutive(vector<int> &num) {
 8         // write you code here
 9         unordered_set<int> st;
10         for (int i = 0; i < num.size(); ++i)
11             st.insert(num[i]);
12         int ans = 0;
13         for (int i = 0; i < num.size(); ++i)
14         {
15             int left, right, val = num[i];
16             do
17             {
18                 unordered_set<int>::iterator it = st.find(val);
19                 if (it == st.end()) break;
20                 val--; st.erase(it);
21             }while (true);
22             left = num[i]-val;
23             val = num[i]+1;
24             do
25             {
26                 unordered_set<int>::iterator it = st.find(val);
27                 if (it == st.end()) break;
28                 val++; st.erase(it);
29             }while(true);
30             right = val-num[i]-1;
31             if (left+right > ans) ans = left+right;
32         }
33         return ans;
34     }
35 };

View Code

6.最长上升子序列

地址：http://www.lintcode.com/zh-cn/problem/longest-increasing-subsequence/

分析：简单DP

代码：

 1 class Solution {
 2 public:
 3     /**
 4      * @param nums: The integer array
 5      * @return: The length of LIS (longest increasing subsequence)
 6      */
 7     int longestIncreasingSubsequence(vector<int> nums) {
 8         // write your code here
 9         int dp[1000];
10         for (int i = 0; i < nums.size(); ++i)
11         {
12             dp[i] = 1;
13             for (int j = 0; j < i; ++j)
14                 if (nums[i] >= nums[j]) dp[i] = max(dp[i], dp[j]+1);
15         }
16         int ans = 0;
17         for (int i = 0; i < nums.size(); ++i)
18             if (dp[i] > ans) ans = dp[i];
19         return ans;
20     }
21 };

View Code

7.triangle-count

地址：http://www.lintcode.com/zh-cn/problem/triangle-count/

分析：暴力的。。。竟然没吃T，不知道为啥，回头再看看。。。

代码：

 1 class Solution {
 2 public:
 3     /**
 4      * @param S: A list of integers
 5      * @return: An integer
 6      */
 7     int triangleCount(vector<int> &S) {
 8         // write your code here
 9         int ans = 0;
10         sort(S.begin(), S.end());
11         for (int i = 0; i < S.size()-2; ++i)
12             for (int k = S.size()-1; k >i+1; --k)
13                 for (int j = i+1; j < k; ++j)
14                     if (S[k]-S[j] < S[i]) { ans += k-j; break; }
15         return ans;
16     }
17 };

View Code

8.最近公共祖先(lowest-common-ancestor)

题目：http://www.lintcode.com/zh-cn/problem/lowest-common-ancestor/

分析:dfs即可=。=

代码：

 1 class Solution {
 2 public:
 3     /**
 4      * @param root: The root of the binary search tree.
 5      * @param A and B: two nodes in a Binary.
 6      * @return: Return the least common ancestor(LCA) of the two nodes.
 7      */
 8     int work(TreeNode *root, TreeNode *a, TreeNode *b, TreeNode *&ans)
 9     {
10         int cnt = 0;
11         if (root == NULL) return cnt;
12         if (root == a || root == b) cnt += 1;
13         int val1 = 0, val2 = 0;
14         val1 = work(root->left, a, b, ans);
15         val2 = work(root->right, a, b, ans);
16         if (cnt + val1 + val2 == 2)
17         {
18             if (ans == NULL) ans = root;
19         }
20         return cnt + val1 + val2;
21     }
22     TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
23         // write your code here
24         TreeNode *ans = NULL;
25         work(root, A, B, ans);
26         if (ans == NULL) return root;
27         return ans;
28     }
29 };

View Code

9. 链表翻转

地址：http://www.lintcode.com/zh-cn/problem/reverse-linked-list-ii/

分析：指针类题目，瞎搞。。。

代码：

 1 /**
 2  * Definition of singly-linked-list:
 3  * 
 4  * class ListNode {
 5  * public:
 6  *     int val;
 7  *     ListNode *next;
 8  *     ListNode(int val) {
 9  *        this->val = val;
10  *        this->next = NULL;
11  *     }
12  * }
13  */
14 class Solution {
15 public:
16     /**
17      * @param head: The head of linked list.
18      * @param m: The start position need to reverse.
19      * @param n: The end position need to reverse.
20      * @return: The new head of partial reversed linked list.
21      */
22     ListNode *reverseBetween(ListNode *head, int m, int n) {
23         // write your code here
24         int cnt = 1;
25         ListNode *tmp = head, *first, *pre, *temp, *g;
26         if (m == n) return head;
27         if (m == 1) first = head;
28         
29         while (cnt < m)
30         {
31             if (cnt+1 == m) pre = tmp;
32             tmp = tmp->next;
33             first = tmp;
34             cnt++;
35         }
36         g = tmp->next;
37         temp = tmp->next->next;
38         while (cnt < n)
39         {
40             g->next = tmp;
41             tmp = g; g = temp; 
42             if (g != NULL) temp = g->next;
43             cnt++;
44         }
45         if (m != 1) pre->next = tmp;
46         first->next = g;
47         if (m == 1) return tmp;
48         return head;
49     }
50 };

View Code

10.The Unique MST

地址：http://poj.org/problem?id=1679

分析：利用Prim算法比较最小生成树与次小生成树，加边成环，然后减边，看代价是否改变。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <string>
 5 #include <cstring>
 6 #include <set>
 7 #include <utility>
 8 #include <map>
 9 #include <cstdlib>
10 #include <queue>
11 #include <vector>
12 #include <numeric>
13 #include <list>
14 #include <bitset>
15 #include <exception>
16 #include <istream>
17 #include <ostream>
18 #include <stdexcept>
19 #include <functional>
20 #include <typeinfo>
21 
22 #define LL long long int
23 using namespace std;
24 
25 const int maxn = 110;
26 int g[maxn][maxn], mcost[maxn][maxn];
27 int cost[maxn], pre[maxn];
28 int m, n, sum;
29 bool vis[maxn];
30 vector<int> vec;
31 
32 void prim()
33 {
34     memset(vis, false, sizeof(vis));
35     vis[1] = true;
36     sum = 0;
37     for (int i = 1; i <= m; ++i)
38         pre[i] = 1, cost[i] = g[1][i];
39     vec.push_back(1);
40 
41     for (int i = 1; i <= m; ++i)
42     {
43         int temp = INT_MAX, k;
44         for (int j = 1; j <= m; ++j)
45             if (!vis[j] && temp > cost[j])
46                 temp = cost[k = j];
47         if (temp == INT_MAX) break;
48         vis[k] = true;
49         sum += temp;
50         for (int j = 0; j < vec.size(); ++j)
51             mcost[vec[j]][k] = mcost[k][vec[j]] = max(mcost[vec[j]][pre[k]], temp);
52         vec.push_back(k);
53 
54         for (int j = 1; j <= m; ++j)
55             if (!vis[j] && cost[j] > g[k][j])
56                 cost[j] = g[k][j],pre[j] = k;
57     }
58 }
59 
60 int main()
61 {
62     int t;
63     scanf("%d", &t);
64     while (t--)
65     {
66         scanf("%d%d", &m, &n);
67         for (int i = 0; i <= m; ++i)
68             for (int j = 0; j <= m; ++j)
69                 g[i][j] = i == j ? 0 : INT_MAX, mcost[i][j] = 0;
70         int x, y, w;
71         for (int i = 0; i < n; ++i)
72         {
73             scanf("%d%d%d", &x, &y, &w);
74             g[x][y] = g[y][x] = w;
75         }
76 
77         prim();
78 
79         int minn = INT_MAX;
80         for (int i = 1; i <= m; ++i)
81             for (int j = 1; j <= m; ++j)
82                 if (i != j && i != pre[j] && j != pre[i])
83                     minn = min(minn, g[i][j]-mcost[i][j]);
84         if (minn != 0) printf("%d
", sum);
85         else puts("Not Unique!");
86     }
87 
88     return 0;
89 }

View Code

11.Big Christmas Tree

地址：http://poj.org/problem?id=3013

分析：dijkstra+堆优化(邻接表，若用vector则TLE=、=)

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <string>
  5 #include <cstring>
  6 #include <set>
  7 #include <utility>
  8 #include <map>
  9 #include <cstdlib>
 10 #include <queue>
 11 #include <vector>
 12 #include <numeric>
 13 #include <list>
 14 #include <bitset>
 15 #include <exception>
 16 #include <istream>
 17 #include <ostream>
 18 #include <stdexcept>
 19 #include <functional>
 20 #include <typeinfo>
 21 
 22 #define LL long long int
 23 using namespace std;
 24 
 25 const long long INF = 10000000000;
 26 const int M = 50005;
 27 int n, m, edgeNum;
 28 long long dis[M];
 29 int head[M];
 30 int visit[M];
 31 int weight[M];
 32 
 33 struct Edge
 34 {
 35     int w;
 36     int to;
 37     int next;
 38 }edge[M*2];
 39 
 40 struct Node
 41 {
 42     int u;
 43     int dis;
 44     bool operator < (const Node &a) const
 45     {
 46         return dis>a.dis;
 47     }
 48 };
 49 
 50 void init()
 51 {
 52     int i;
 53     edgeNum = 0;
 54     for(i = 0; i < M; i++)
 55     {
 56         visit[i] = 0;
 57         head[i] = -1;
 58         dis[i] = INF;
 59     }
 60 }
 61 void addEdge(int a, int b, int c)
 62 {
 63     edge[edgeNum].w = c;
 64     edge[edgeNum].to = b;
 65     edge[edgeNum].next = head[a];
 66     head[a] = edgeNum++;
 67 }
 68 void Dij(int u)
 69 {
 70     int i, v;
 71     Node temp, now;
 72     priority_queue<Node> q;
 73     temp.dis = 0;
 74     temp.u = u;
 75     dis[u] = 0;
 76     q.push(temp);
 77     while (!q.empty())
 78     {
 79         temp = q.top();
 80         q.pop();
 81         if (visit[temp.u]) continue;
 82         visit[temp.u] = 1;
 83         for (i = head[temp.u]; i != -1; i = edge[i].next)
 84         {
 85             v = edge[i].to;
 86             if (!visit[v] && dis[v]>dis[temp.u]+edge[i].w)
 87             {
 88                 dis[v] = dis[temp.u]+edge[i].w;
 89                 now.dis = dis[v];
 90                 now.u = v;
 91                 q.push(now);
 92             }
 93         }
 94     }
 95     return ;
 96 }
 97 int main()
 98 {
 99     int T, a, b, c, i;
100     scanf("%d", &T);
101     while (T--)
102     {
103 
104         scanf("%d%d", &n, &m);
105         init();
106         for(i = 0; i < n; i++)
107             scanf("%d", &weight[i]);
108         for(i = 0; i < m; i++)
109         {
110             scanf("%d%d%d", &a, &b, &c);
111             a--; b--;
112             addEdge(a, b, c);
113             addEdge(b, a, c);
114         }
115         Dij(0);
116         long long res=0;
117         for(i = 0; i < n; i++)
118         {
119             if(dis[i] == INF) break;
120             res += dis[i]*weight[i];
121         }
122         if(i == n) printf("%lld
", res);
123         else puts("No Answer");
124     }
125     return 0;
126 }

View Code

12.linked-list-cycle-ii(带环链表)

地址：http://www.lintcode.com/zh-cn/problem/linked-list-cycle-ii/#

分析：快慢指针

代码：

 1 class Solution {
 2 public:
 3     /**
 4      * @param head: The first node of linked list.
 5      * @return: The node where the cycle begins. 
 6      *           if there is no cycle, return null
 7      */
 8     ListNode *detectCycle(ListNode *head) {
 9         // write your code here
10         ListNode *t1 = head, *t2 = head;
11         while (t1 && t2 && t2->next)
12         {
13             t1 = t1->next;
14             t2 = t2->next->next;
15             if (t1 == t2)
16             {
17                 t1 = head;
18                 while (true)
19                 {
20                     t1 = t1->next;
21                     t2 = t2->next;
22                     if (t1 == t2) return t1;
23                 }
24             }
25         }
26         return NULL;
27     }
28 };

View Code

13.Balanced Lineup

地址：http://poj.org/problem?id=3264

分析：线段树，注意N的范文，题目写的1-50,000，结果测试数据却是1-200,000 ！！！MADAN...

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <string>
 5 #include <cstring>
 6 #include <set>
 7 #include <utility>
 8 #include <map>
 9 #include <cstdlib>
10 #include <queue>
11 #include <vector>
12 #include <numeric>
13 #include <list>
14 #include <bitset>
15 #include <exception>
16 #include <istream>
17 #include <ostream>
18 #include <stdexcept>
19 #include <functional>
20 #include <typeinfo>
21 
22 #define LL long long int
23 using namespace std;
24 
25 const int maxn = 200005;
26 
27 typedef struct node
28 {
29     int min_val, max_val, left, right;
30 }node;
31 
32 node stree[maxn<<2];
33 int n, q;
34 int val[maxn];
35 
36 void build(int root, int left, int right)
37 {
38     if (left == right)
39     {
40         stree[root].max_val = stree[root].min_val = val[left];
41         stree[root].left = left, stree[root].right = right;
42         return ;
43     }
44     build(root*2, left, (left+right)/2);
45     build(root*2+1, (left+right)/2+1, right);
46     stree[root].left = left, stree[root].right = right;
47     stree[root].min_val = min(stree[root*2].min_val, stree[root*2+1].min_val);
48     stree[root].max_val = max(stree[root*2].max_val, stree[root*2+1].max_val);
49 }
50 
51 void query(int root, int left, int right, int& max_num, int& min_num)
52 {
53     if (stree[root].max_val <= max_num && stree[root].min_val >= min_num) return ;
54     if (stree[root].left > right || stree[root].right < left) return ;
55     if (left <= stree[root].left && right >= stree[root].right)
56     {
57         max_num = max(max_num, stree[root].max_val);
58         min_num = min(min_num, stree[root].min_val);
59     }
60     int mid = (stree[root].left + stree[root].right)/2;
61     if (right <= mid) query(root*2, left, right, max_num, min_num);
62     else if (left > mid)query(root*2+1, left, right, max_num, min_num);
63     else
64     {
65         query(root*2, left, right, max_num, min_num);
66         query(root*2+1, left, right, max_num, min_num);
67     }
68 }
69 
70 int main()
71 {
72     scanf("%d%d", &n, &q);
73     for (int i = 1; i <= n; ++i)
74         scanf("%d", &val[i]);
75     build(1, 1, n);
76 
77     int left, right, max_num, min_num;
78     for (int i = 0; i < q; ++i)
79     {
80         max_num = -1, min_num = 2e9;
81         scanf("%d%d", &left, &right);
82         query(1, left, right, max_num, min_num);
83         printf("%d
", max_num-min_num);
84     }
85     return 0;
86 }

View Code

14.Add Digits

地址：https://leetcode.com/problems/add-digits/

分析：谁都会做的水题。

代码：

 1 public class Solution {
 2     public int addDigits(int num) {
 3         int ans = 0;
 4         while (num > 9)
 5         {
 6             while (num != 0)
 7             {
 8                 ans += num%10;
 9                 num /= 10;
10             }
11             num = ans;
12             ans = 0;
13         }
14         return num;
15     }
16 }

View Code

15.Majority Element

地址：https://leetcode.com/problems/majority-element/

分析：计数原理

代码：

 1 public class Solution {
 2     public int majorityElement(int[] nums) {
 3         int val = nums[0];
 4         int cnt = 1;
 5         for (int i = 1; i < nums.length; ++i)
 6         {
 7             if (nums[i] == val) cnt++;
 8             else cnt--;
 9             if (cnt == 0) { val = nums[i]; cnt = 1; }
10         }
11         return val;
12     }
13 }

View Code

16.Binary Tree Paths

地址：https://leetcode.com/problems/binary-tree-paths/

分析：简单题，dfs

代码：

 1 class Solution {
 2 public:
 3     string int2str(int val)
 4     {
 5         int flag = 0;
 6         if (val == 0) return "0";
 7         if (val < 0) flag = 1, val = -val;
 8         string ret = "";
 9         while (val)
10         {
11             ret += (char)(val%10+'0');
12             val /= 10;
13         }
14         if (flag) ret += "-";
15         reverse(ret.begin(), ret.end());
16         return ret;
17     }
18     void work(TreeNode* root, vector<int>& add, vector<vector<int>>& vec)
19     {
20         if (root == NULL) return ;
21         if (!root->left && !root->right)
22         {
23             add.push_back(root->val);
24             vec.push_back(add);
25             add.pop_back();
26             return ;
27         }
28         add.push_back(root->val);
29         work(root->left, add, vec);
30         work(root->right, add, vec);
31         add.pop_back();
32     }
33     vector<string> binaryTreePaths(TreeNode* root) {
34         vector<vector<int>> vec;
35         vector<int> add;
36         work(root, add, vec);
37         vector<string> ans;
38         for (int i = 0; i < vec.size(); ++i)
39         {
40             string str = "";
41             if (vec[i].size() != 0)
42             {
43                 str += int2str(vec[i][0]);
44                 for (int j = 1; j < vec[i].size(); ++j)
45                    str = str + "->" + int2str(vec[i][j]); 
46                 ans.push_back(str);
47             }
48         }
49         return ans;
50     }
51 };

View Code

17.Ugly Number

地址：https://leetcode.com/problems/ugly-number/

分析：水题。

代码：

 1 class Solution {
 2 public:
 3     bool isUgly(int num) {
 4         if (num <= 0) return false;
 5         while (num%2 == 0) num /= 2;
 6         while (num%3 == 0) num /= 3;
 7         while (num%5 == 0) num /= 5;
 8         if (num == 1) return true;
 9         return false;
10     }
11 };

View Code

18.First Bad Version

地址：https://leetcode.com/problems/first-bad-version/

分析：二分

代码：

 1 bool isBadVersion(int version);
 2 
 3 class Solution {
 4 public:
 5     int firstBadVersion(int n) {
 6         long long int l = 1, r = n;
 7         while (l < r)
 8         {
 9             long long int m = (l+r)>>1;
10             if (isBadVersion(m) == false) l = m+1;
11             else r = m;
12         }
13         return l;
14     }
15 };

View Code

19.Generate Parentheses

地址：https://leetcode.com/problems/generate-parentheses/

分析：DFS一下，判断几种情况。

代码：

 1 class Solution {
 2 public:
 3     void work(vector<string>& ans, string add, int val1, int val2, int n)
 4     {
 5         if (val1 == val2 && val1 == n)
 6         {
 7             ans.push_back(add);
 8             return ;
 9         }
10         if (val1 == val2)
11             work(ans, add+"(", val1+1, val2, n);
12         else if (val1 == n)
13         {
14             string s(n-val2, ')');
15             work(ans, add+s, val1, n, n);
16         }
17         else
18         {
19             work(ans, add+"(", val1+1, val2, n);
20             work(ans, add+")", val1, val2+1, n);
21         }
22     }
23     vector<string> generateParenthesis(int n) {
24         string add = "";
25         vector<string> ans;
26         work(ans, add, 0, 0, n);
27         return ans;
28     }
29 };

View Code

20.Surprising Strings

地址：http://poj.org/problem?id=3096

分析：水题，用STL//poj不支持c++ 11

代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <cstring>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <stack>
11 #include <queue>
12 #include <unordered_map>
13 #include <unordered_set>
14 
15 using namespace std;
16 
17 int main()
18 {
19     string str;
20     while (cin>>str && str != "*")
21     {
22         bool flag = true;
23         set<string> st;
24         for (int i = 1; i < str.length() && flag; ++i)
25         {
26             st.clear();
27             for (int j = 0; j < str.length()-i && flag; ++j)
28             {
29                 string temp = "";
30                 temp = temp + str[j] + str[i+j];
31                 if (st.count(temp))
32                     flag = false;
33                 else
34                     st.insert(temp);
35             }
36         }
37         cout << str;
38         if (flag) printf(" is surprising.
");
39         else printf(" is NOT surprising.
");
40     }
41 
42     return 0;
43 }

View Code

21.Ugly Number

地址：http://www.lintcode.com/zh-cn/problem/ugly-number/

分析：利用队列，3个队列，分别保存*3, *5，*7的数字，每次选择最小的一个push进vector，然后将其*3, *5,*7push到queue，直到vector的大小到k+1

代码：

 1 class Solution {
 2 public:
 3     /*
 4      * @param k: The number k.
 5      * @return: The kth prime number as description.
 6      */
 7     long long kthPrimeNumber(int k) {
 8         // write your code here
 9         queue<long long int> q1, q2, q3;
10         vector<long long int> v;
11         long long int t1, t2, t3, tmp;
12         v.push_back(1);
13         int cnt = 0;
14         while (cnt < k)
15         {
16             q1.push(v.back()*3);
17             q2.push(v.back()*5);
18             q3.push(v.back()*7);
19             tmp = min(min(q1.front(), q2.front()), q3.front());
20             v.push_back(tmp);
21             if (tmp == q1.front()) q1.pop();
22             if (tmp == q2.front()) q2.pop();
23             if (tmp == q3.front()) q3.pop();
24             cnt++;
25         }
26         return tmp;
27     }
28 };

View Code

22.Missing Number

地址：https://leetcode.com/problems/missing-number/

分析：O(n)，利用nums的数据大小为0……n来做。

代码：

 1 class Solution {
 2 public:
 3     int missingNumber(vector<int>& nums) {
 4         for (int i = 0; i < nums.size(); ++i)
 5         {
 6             while (nums[i] != i)
 7             {
 8                 if (nums[i] == nums.size()) break;
 9                 swap(nums[i], nums[nums[i]]);
10             }
11         }
12         for (int i = 0; i < nums.size(); ++i)
13             if (i != nums[i]) return i;
14         return nums.size();
15     }
16 };

View Code

23.Number of Islands

地址：https://leetcode.com/problems/number-of-islands/

分析：BFS即可

代码：

 1 class Solution {
 2 public:
 3     int numIslands(vector<vector<char>>& grid) {
 4         if (grid.size() == 0) return 0;
 5         int ans = 0;
 6         int m = grid.size(), n = grid[0].size();
 7         for (int i = 0; i < m; ++i)
 8         {
 9             for (int j = 0; j < n; ++j)
10             {
11                 queue<pair<int, int>> qu;
12                 while (!qu.empty()) qu.pop();
13                 if (grid[i][j] == '1')
14                 {
15                     grid[i][j] = '0';
16                     ans++;
17                     qu.push(make_pair(i, j));
18                     while (!qu.empty())
19                     {
20                         int x = qu.front().first;
21                         int y = qu.front().second;
22                         qu.pop();
23                         if (x-1 >= 0 && grid[x-1][y] == '1') qu.push(make_pair(x-1, y)), grid[x-1][y] = '0';
24                         if (x+1 < m && grid[x+1][y] == '1') qu.push(make_pair(x+1, y)), grid[x+1][y] = '0';
25                         if (y+1 < n && grid[x][y+1] == '1') qu.push(make_pair(x, y+1)), grid[x][y+1] = '0';
26                         if (y-1 >= 0 && grid[x][y-1] == '1') qu.push(make_pair(x, y-1)), grid[x][y-1] = '0';
27                     }
28                 }
29             }
30         }
31         return ans;
32     }
33 };

View Code

24.H-Index

地址：https://leetcode.com/problems/h-index/

 1 //分析：排序一下，然后n从大到小开始验证，如果OK，就return。
 2 class Solution {
 3 public:
 4     int hIndex(vector<int>& citations) {
 5         sort(citations.begin(), citations.end());
 6         int size = citations.size();
 7         for (int n = size; n >= 1; --n)
 8         {
 9             if (citations[size-n] >= n) return n;
10         }
11         return 0;
12     }
13 };

View Code

25.H-Index II

地址：https://leetcode.com/problems/h-index-ii/

 1 //分析：类似于上题，不过已经排序了，题目要求O(lgn)，用binary search即可。
 2 class Solution {
 3 public:
 4     int hIndex(vector<int>& citations) {
 5         if (citations.size() == 0) return 0;
 6         int size = citations.size();
 7         int l = 1, r = size, m = (l+r)>>1;
 8         while (l < r)
 9         {
10             m = (l + r) >> 1;
11             if (citations[size-m] >= m) l = m+1;
12             else r = m-1;
13         }
14         if (citations[size-l] >= l) return l;
15         return l-1;
16     }
17 };

View Code

26.Rotate List

地址：https://leetcode.com/problems/rotate-list/

 1 //分析：链表题。
 2 class Solution {
 3 public:
 4     ListNode* rotateRight(ListNode* head, int k) {
 5         if (head == NULL) return head;
 6         int len = 0;
 7         ListNode *t1 = head, *t2 = head;
 8         while (t1) t1 = t1->next, len++;
 9         k %= len;
10         len = 0;
11         t1 = head; 
12         if (k == 0) return head;
13         while (t2 && len < k)
14         {
15             t2 = t2->next;
16             len++;
17         }
18         if (t2 == NULL) return head;
19         while (t2->next)
20         {
21             t1 = t1->next;
22             t2 = t2->next;
23         }
24         ListNode *ret = t1->next;
25         t1->next = NULL;
26         t2->next = head;
27         return ret;
28     }
29 };

View Code

27.Ugly Number II

地址：https://leetcode.com/problems/ugly-number-ii/

 1 //分析：上面貌似有个几乎一样的题，差距就在1是否为ugly number
 2 class Solution {
 3 public:
 4     int nthUglyNumber(int n) {
 5         vector<long long int> v;
 6         queue<long long int> q2, q3, q5;
 7         v.push_back(1);
 8         int cnt = 1;
 9         while (cnt < n)
10         {
11             q2.push(2*v.back());
12             q3.push(3*v.back());
13             q5.push(5*v.back());
14             long long int tmp = min(min(q2.front(), q3.front()), q5.front());
15             v.push_back(tmp);
16             if (tmp == q2.front()) q2.pop();
17             if (tmp == q3.front()) q3.pop();
18             if (tmp == q5.front()) q5.pop();
19             cnt++;
20         }
21         return v.back();
22     }
23 };

View Code

28.Binary Tree Right Side View

 1 //BFS即可
 2 class Solution {
 3 public:
 4     vector<int> rightSideView(TreeNode* root) {
 5         vector<int> ans;
 6         if (root == NULL) return ans;
 7         queue<TreeNode *> q1, q2;
 8         q1.push(root);
 9         while (!q1.empty())
10         {
11             if (q1.size() == 1) ans.push_back(q1.front()->val);
12             if (q1.front()->left != NULL) q2.push(q1.front()->left);
13             if (q1.front()->right != NULL) q2.push(q1.front()->right);
14             q1.pop();
15             if (q1.empty() && !q2.empty())
16             {
17                 q1 = q2;
18                 while (!q2.empty()) q2.pop();
19             }
20         }
21         return ans;
22     }
23 };

View Code

29.Combination Sum III

 1 //简单DFS
 2 class Solution {
 3 public:
 4     void work(int idx, int sum, int cnt, vector<vector<int>>& ans, vector<int>& add, int k, int n)
 5     {
 6         if (cnt > k || sum > n) return ;
 7         if (sum == n && cnt == k)
 8         {
 9             ans.push_back(add);
10             return ;
11         }
12         if (cnt == k && sum != n) return ;
13         for (int i = idx; i <= 9 && sum+i <= n; ++i)
14         {
15             add.push_back(i);
16             work(i+1, sum+i, cnt+1, ans, add, k, n);
17             add.pop_back();
18         }
19     }
20     vector<vector<int>> combinationSum3(int k, int n) {
21         vector<vector<int>> ans;
22         vector<int> add;
23         work(1, 0, 0, ans, add, k, n);
24         return ans;
25     }
26 };

View Code

30.Binary Search Tree Iterator

 1 //一开始想错了，其实has_next，next,其实就是获取当前最小值，然后删除了这个最小值
 2 //那么用栈就很容易解决了
 3 /**
 4  * Definition for binary tree
 5  * struct TreeNode {
 6  *     int val;
 7  *     TreeNode *left;
 8  *     TreeNode *right;
 9  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10  * };
11  */
12 class BSTIterator {
13 public:
14     stack<TreeNode *> st;
15     int next_num;
16     BSTIterator(TreeNode *root) {
17         while (root)
18         {
19             st.push(root);
20             root = root->left;
21         }
22     }
23 
24     /** @return whether we have a next smallest number */
25     bool hasNext() {
26         if (!st.empty())
27         {
28             TreeNode *t = st.top();
29             st.pop();
30             next_num = t->val;
31             TreeNode *tmp = t->right;
32             if (tmp)
33             {
34                 while (tmp)
35                 {
36                     st.push(tmp);
37                     tmp = tmp->left;
38                 }
39             }
40             return true;
41         }
42         return false;
43     }
44 
45     /** @return the next smallest number */
46     int next() {
47         return next_num;
48     }
49 };
50 
51 /**
52  * Your BSTIterator will be called like this:
53  * BSTIterator i = BSTIterator(root);
54  * while (i.hasNext()) cout << i.next();
55  */

View Code

31.Unique Binary Search Trees II

 1 //递归的思想,瞎搞
 2 class Solution {
 3 public:
 4     vector<TreeNode*> work(int left, int right)
 5     {
 6         vector<TreeNode*> ret;
 7         if (left > right)
 8         {
 9             ret.push_back(NULL);
10             return ret;
11         }
12         if (left == right)
13         {
14             TreeNode* tmp = new TreeNode(left);
15             ret.push_back(tmp);
16             return ret;
17         }
18         for (int i = left; i <= right; ++i)
19         {
20             vector<TreeNode*> t1 = work(left, i-1);
21             vector<TreeNode*> t2 = work(i+1, right);
22             
23             for (int x = 0; x < t1.size(); ++x)
24             {
25                 for (int y = 0; y < t2.size(); ++y)
26                 {
27                     TreeNode* tmp = new TreeNode(i);
28                     tmp->left = t1[x];
29                     tmp->right = t2[y];
30                     ret.push_back(tmp);
31                 }
32             }
33         }
34         return ret;
35     }
36     vector<TreeNode*> generateTrees(int n) {
37         return work(1, n);
38     }
39 };

View Code

32.Partition List

 1 //链表类题目，还是瞎搞就行
 2 class Solution {
 3 public:
 4     bool find(ListNode *head, int x)
 5     {
 6         ListNode *tmp = head;
 7         while (tmp)
 8         {
 9             if (tmp->val < x) return true;
10             tmp = tmp->next;
11         }
12         return false;
13     }
14     ListNode* partition(ListNode* head, int x) {
15         ListNode *tmp = head, *pre = NULL, *root = NULL;
16         while (tmp)
17         {
18             while (tmp && tmp->val < x) pre = tmp, tmp = tmp->next;
19             if (tmp == NULL) break;
20             if (find(tmp, x))
21             {
22                 ListNode *t = tmp;
23                 while (t->next->val >= x) t = t->next;
24                 ListNode* tt = t->next;
25                 t->next = t->next->next;
26                 if (pre == NULL) 
27                 {
28                     root = tt;
29                     tt->next = tmp;
30                     pre = root;
31                 }
32                 else
33                 {
34                     pre->next = tt;
35                     tt->next = tmp;
36                     pre = tt;
37                 }
38             }
39             else break;
40         }
41         if (root != NULL) return root;
42         return head;
43     }
44 };

View Code

33.Construct Binary Tree from Preorder and Inorder Traversal

 1 //Talk is cheap. Show me code.
 2 class Solution {
 3 public:
 4     TreeNode* build(vector<int>& preorder, vector<int>& inorder, int left1, int right1, int left2, int right2)
 5     {
 6         if (left1 > right1) return NULL;
 7         TreeNode *tmp = new TreeNode(preorder[left1]);
 8         if (left1 == right1) return tmp;
 9         int i, j;
10         for (i = left2; i <= right2; ++i)
11             if (inorder[i] == preorder[left1]) break;
12         for (j = left1+1; j <= right1; j++)
13             if (j-(left1+1) == i-left2) break;
14         tmp->left = build(preorder, inorder, left1+1, j-1, left2, i-1);
15         tmp->right = build(preorder, inorder, j, right1, i+1, right2);
16         return tmp;
17     }
18     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
19         return build(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
20     }
21 };

View Code

34.Group Anagrams

 1 //用Map做比较简单，map<string, vector<string>>; 然后排下序
 2 class Solution {
 3 public:
 4     vector<vector<string>> groupAnagrams(vector<string>& strs) {
 5         map<string, vector<string>> mp;
 6         for (int i = 0; i < strs.size(); ++i)
 7         {
 8             string str = strs[i];
 9             sort(str.begin(), str.end());
10             if (mp.count(str))
11                 mp[str].push_back(strs[i]);
12             else
13             {
14                 vector<string> v;
15                 v.push_back(strs[i]);
16                 mp.insert(make_pair(str, v));
17             }
18         }
19         vector<vector<string>> ans;
20         for (map<string, vector<string>>::iterator it = mp.begin(); it != mp.end(); ++it)
21         {
22             sort((it->second).begin(), (it->second).end());
23             ans.push_back(it->second);
24         }
25         return ans;
26     }
27 };

View Code

35.Reverse Nodes in k-Group

 1 //逆置链表
 2 class Solution {
 3 public:
 4     ListNode* reverseKGroup(ListNode* head, int k) {
 5         if (head == NULL) return head;
 6         int len = 0;
 7         ListNode *tt = head;
 8         while (tt) { tt=tt->next; len++; }
 9         if (k > len) return head;
10         if (k < 2) return head;
11         int cnt = 1;
12         ListNode *t1 = head, *t2 = head->next, *pre = NULL;
13         while (cnt < k)
14         {
15             pre = t2->next;
16             t2->next = t1;
17             t1 = t2;
18             t2 = pre;
19             cnt++;
20         }
21         head->next = reverseKGroup(t2, k);
22         return t1;
23     }
24 };

View Code

36.Move Zeroes

 1 //two points
 2 class Solution {
 3 public:
 4     void moveZeroes(vector<int>& nums) {
 5         int i= 0, j = 0, size = nums.size();
 6         while (true)
 7         {
 8             while (i < size && nums[i] != 0) ++i;
 9             j = i;
10             while (j < size && nums[j] == 0) ++j;
11             if (i == size || j == size) break;
12             swap(nums[i], nums[j]);
13         }
14     }
15 };

View Code

37.Search in Rotated Sorted Array II

 1 //二分
 2 class Solution {
 3 public:
 4     bool search(vector<int>& nums, int target) {
 5         if (nums.size() == 0) return false;
 6         int l = 0, r = nums.size()-1;
 7         while (l <= r)
 8         {
 9             int m = (l+r) >> 1;
10             if (nums[m] == target) return true;
11             if (nums[l] == nums[r] && nums[m] == nums[r]) l++, r--;
12             else if (nums[l] <= nums[m])
13             {
14                 if (nums[l] <= target && target < nums[m]) r = m-1;
15                 else l = m+1;
16             }
17             else
18             {
19                 if (nums[r] >= target && nums[m] < target) l = m+1;
20                 else r = m-1;
21             }
22         }
23         return false;
24     }
25 };

View Code

38.Find Minimum in Rotated Sorted Array II

 1 //二分
 2 class Solution {
 3 public:
 4     int findMin(vector<int>& nums) {
 5         int l = 0, r = nums.size()-1;
 6         while (l <= r)
 7         {
 8             if (l == r) return nums[l];
 9             if (l+1 == r) return min(nums[l], nums[r]);
10             int m = (l+r) >> 1;
11             if (nums[l] == nums[r] && nums[r] == nums[m]) { l++, r--; continue; }
12             if (nums[l] >= nums[m] && nums[m] <= nums[r]) r = m;
13             else if (nums[l] >= nums[m] && nums[m] > nums[r]) l = m;
14             else if (nums[l] < nums[m] && nums[l] >= nums[r]) l = m;
15             else if (nums[l] < nums[m] && nums[l] < nums[r]) r = m; 
16         }
17         return nums[l];
18     }
19 };

View Code

39.Perfect Squares

 1 //BFS && DP
 2 class Solution {
 3 public:
 4     int numSquares(int n) {
 5         vector<int> vis(n+1, 0);
 6         queue<pair<int, int>> qu;
 7         if ((int)sqrt(n)*sqrt(n) == n) return 1;
 8         qu.push(make_pair(n, 1));
 9         while (!qu.empty())
10         {
11             int val = qu.front().first;
12             int dep = qu.front().second;
13             if ((int)sqrt(val)*sqrt(val) == val) return dep;
14             for (int i = sqrt(val); i*i > 0; --i)
15             {
16                 if (vis[val-i*i]) continue;
17                 vis[val-i*i] = 1;
18                 qu.push(make_pair(val-i*i, dep+1));
19             }
20             qu.pop();
21         }
22     }
23 };

View Code

40.Single Number III

 1 //将2*n+2问题转化为2*n+1问题，所有数异或，得到最后结果，然后找最后一个非零位////置。根据这个位置做分类，所有这个位置为零的为一组，所有这个位置为一的为一组。 
 2 class Solution {
 3 public:
 4     vector<int> singleNumber(vector<int>& nums) 
 5     {
 6         int len = nums.size();
 7         int AxorB = 0;
 8         for(int i=0; i<len; i++)
 9             AxorB ^= nums[i];
10         int mask = AxorB & (~(AxorB-1));
11         int A = 0;
12         int B = 0;
13         for(int i=0; i<len; i++)
14         {
15             if((mask&nums[i])==0)
16                 A ^= nums[i];
17             else
18                 B ^= nums[i];
19         }
20         return vector<int>({A, B});
21     }
22 };

View Code