9.21-9.27

 1 //dfs、前序遍历一下即可
 2 class Solution {
 3 public:
 4     void dfs(TreeNode* root, TreeNode* &pre)
 5     {
 6         if (root == NULL) return ;
 7         pre->left = root;
 8         pre = pre->left;
 9         if (root->left) dfs(root->left, pre);
10         if (root->right) dfs(root->right, pre);
11     }
12     void work(TreeNode *root)
13     {
14         if (root == NULL) return;
15         if (root->left) work(root->left);
16         root->left = NULL;
17     }
18     void flatten(TreeNode* root) {
19         if (root == NULL) return ;
20         TreeNode* tmp = new TreeNode(-1);
21         dfs(root, tmp);
22         TreeNode *t = root;
23         while (t)
24         {
25             t->right = t->left;
26             t = t->left;
27         }
28         t = root;
29         work(t);
30     }
31 };

View Code

2.Convert Sorted List to Binary Search Tree

 1 //递归，根据postorder来做，postorder最后一个值肯定是root，根据这个来做即可。
 2 class Solution {
 3 public:
 4     TreeNode* build(vector<int>& inorder, vector<int>& postorder, int left1, int right1, int left2, int right2)
 5     {
 6         if (left1 > right1) return NULL;
 7         TreeNode *tmp = new TreeNode(postorder[right2]);
 8         if (left1 == right1)
 9             return tmp;
10         int i, j;
11         for (i = right1; i >= left1; --i)
12             if (inorder[i] == postorder[right2]) break;
13         tmp->right = build(inorder, postorder, i+1, right1, right2-1-(right1-i-1), right2-1);
14         tmp->left = build(inorder, postorder, left1, i-1, left2, right2-1-(right1-i-1)-1); 
15     }
16     
17     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
18         return build(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
19     }
20 };

View Code

3. 三个随机输入的数组，输出同时在3个数组中都存在的数字(qunar笔试)

 1 //排序
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <string>
 7 #include <cstring>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <stack>
12 #include <queue>
13 
14 using namespace std;
15 
16 int main()
17 {
18     int n[3];
19     vector<int> v[3];
20 
21     for (int i = 0; i < 3; ++i)
22     {
23         int val;
24         scanf("%d", &n[i]);
25         for (int j = 0; j < n[i]; ++j)
26         {
27             scanf("%d", &val);
28             v[i].push_back(val);
29         }
30         sort(v[i].begin(), v[i].end());
31     }
32 
33     int l0 = 0, l1 = 0, l2 = 0, flag = 0;
34     int r0 = v[0].size(), r1 = v[1].size(), r2 = v[2].size();
35     while (true)
36     {
37         if (v[0][l0] == v[1][l1] && v[2][l2] == v[1][l1])
38         {
39             if (flag) printf(" ");
40             printf("%d", v[0][l0]);
41             flag = 1;
42             l0++, l1++, l2++;
43             continue;
44         }
45         int val = min(min(v[0][l0], v[1][l1]), v[2][l2]);
46         if (val == v[0][l0]) l0++;
47         if (val == v[1][l1]) l1++;
48         if (val == v[2][l2]) l2++;
49         if (l0 == r0 || l1 == r1 || l2 == r2) break;
50     }
51 
52     return 0;
53 }

View Code

4. Submatrix Sum

 1 //n^3复杂度，利用map解决
 2 class Solution 
 3 {
 4 public:
 5     /**
 6      * @param matrix an integer matrix
 7      * @return the coordinate of the left-up and right-down number
 8      */
 9     vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) 
10     {
11         vector<vector<int>> ans;
12         int m = matrix.size();
13         if (m == 0) return ans;
14         int n = matrix[0].size();
15         if (m == 0) return ans;
16 
17         vector<int> t(n+1, 0);
18         vector<vector<int>> dp(m+1, t);
19 
20         for (int i = 0; i < m; ++i)
21             for (int j = 0; j < n; ++j)
22                 dp[i+1][j+1] = matrix[i][j] + dp[i+1][j] + dp[i][j+1] - dp[i][j];
23         
24         for (int l = 0; l < m; ++l)
25         {
26             for (int h = l+1; h <= m; ++h)
27             {
28                 map<int, int> mp;
29                 for (int j = 0; j <= n; ++j)
30                 {
31                     int diff = dp[h][j] - dp[l][j];
32                     if (mp.count(diff))
33                     {
34                         int k = mp[diff];
35                         vector<int> add;
36                         add.push_back(l), add.push_back(k);
37                         ans.push_back(add); add.clear();
38                         add.push_back(h-1), add.push_back(j-1);
39                         ans.push_back(add);
40                         return ans;
41                     }
42                     else mp.insert(make_pair(diff, j));
43                 }
44             }
45         }
46         return ans;
47      }
48 };

View Code

5.Raising Bacteria

 1 //统计数字的二进制里有多少个1即可
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string>
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <queue>
 8 #include <list>
 9 #include <vector>
10 #include <map>
11 #include <set>
12 
13 using namespace std;
14 
15 int main()
16 {
17     int n, ans = 0;
18     scanf("%d", &n);
19     for (int i = 0; i < 32; ++i)
20     {
21         ans += n&1;
22         n >>= 1;
23     }
24     printf("%d
", ans);
25 
26     return 0;
27 }

View Code

6.Pet

 1 //BFS
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string>
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <queue>
 8 #include <list>
 9 #include <vector>
10 #include <map>
11 #include <set>
12 
13 using namespace std;
14 
15 const int maxn = 100010;
16 int vis[maxn];
17 int t, n, d;
18 vector<int> v[maxn];
19 
20 int main()
21 {
22     int x, y;
23 
24     scanf("%d", &t);
25     while (t--)
26     {
27         for (int i = 0; i < maxn; ++i)
28             vis[i] = 0, v[i].clear();
29         scanf("%d%d", &n, &d);
30         for (int i = 1; i < n; ++i)
31         {
32             scanf("%d%d", &x, &y);
33             v[x].push_back(y);
34         }
35         queue<pair<int, int>> qu;
36         qu.push(make_pair(0, 0));
37         while (!qu.empty())
38         {
39             int val = qu.front().first;
40             int dep = qu.front().second;
41             qu.pop();
42             if (dep > d) break;
43             vis[val] = 1;
44             for (int i = 0; i < v[val].size(); ++i)
45             {
46                 if (vis[v[val][i]]) continue;
47                 qu.push(make_pair(v[val][i], dep+1));
48             }
49         }
50         int ans = 0;
51         for (int i = 0; i < n; ++i)
52             ans += vis[i] ? 0 : 1;
53         printf("%d
", ans);
54     }
55 
56     return 0;
57 }

View Code

7.Finding Team Member

 1 //sort pair
 2 #include <iostream>
 3 #include <string>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <cstring>
 7 #include <vector>
 8 #include <map>
 9 #include <set>
10 #include <algorithm>
11 
12 using namespace std;
13 
14 const int maxn = 810;
15 int n;
16 int vis[maxn];
17 
18 int main()
19 {
20     int tmp;
21     scanf("%d", &n);
22     vector<pair<int, pair<int, int> > > v;
23     for (int i = 2; i <= 2*n; ++i)
24     {
25         for (int j = 1; j < i; ++j)
26         {
27             cin >> tmp;
28             v.push_back({tmp, {i, j}});
29         }
30     }
31     memset(vis, 0, sizeof(vis));
32     sort(v.begin(), v.end());
33     reverse(v.begin(), v.end());
34     for (int i = 0; i < v.size(); ++i)
35     {
36         if (!vis[v[i].second.first] && !vis[v[i].second.second])
37         {
38             vis[v[i].second.first] = v[i].second.second;
39             vis[v[i].second.second] = v[i].second.first;
40         }
41     }
42     for (int i = 1; i <= 2*n; ++i)
43     {
44         if (i != 1) printf(" ");
45         printf("%d", vis[i]);
46     }
47     puts("");
48 
49     return 0;
50 }

View Code

8.Corn Fields

 1 //状态压缩基础题
 2 #include <iostream>
 3 #include <string>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <queue>
10 #include <map>
11 #include <set>
12 
13 using namespace std;
14 
15 const int mod = 100000000;
16 int m, n;
17 int a[13];
18 int dp[15][(1<<12)+10];
19 
20 bool check(int x, int y)
21 {
22     if ((a[x]&y) != y) return false;
23     if ((y&(y<<1)) != 0 || (y&(y>>1)) != 0) return false;
24     return true;
25 }
26 
27 void work()
28 {
29     int mnum;
30     memset(dp, 0, sizeof(dp));
31     dp[0][0] = 1;
32     mnum = 1<<n;
33     for (int i = 1; i <= m; ++i)
34     {
35         for (int j = 0; j < mnum; ++j)
36         {
37             if (!check(i, j)) continue;
38             for (int k = 0; k < mnum; ++k)
39             {
40                 if ((j&k) != 0) continue;
41                 dp[i][j] += dp[i-1][k];
42                 dp[i][j] %= mod;
43             }
44         }
45     }
46     int ans = 0;
47     for (int i = 0; i < mnum; ++i)
48     {
49         ans += dp[m][i];
50         ans %= mod;
51     }
52     printf("%d
", ans);
53 }
54 
55 int main()
56 {
57     int val;
58     while (~scanf("%d%d", &m, &n))
59     {
60         for (int i = 1; i <= m; ++i)
61         {
62             a[i] = 0;
63             for (int j = 1; j <= n; ++j)
64             {
65                 scanf("%d", &val);
66                 a[i] = (a[i]<<1)+val;
67             }
68         }
69         work();
70     }
71 
72     return 0;
73 }

View Code

9.炮兵阵地

  1 //经典状态DP题, 开一个数组保存状态
  2 //【状态表示】dp[i][j][k] 表示第i行状态为k，第i-1状态为j时的最大炮兵个数。 
  3 //【状态转移方程】dp[i][k][t] =max(dp[i][k][t],dp[i-1][j][k]+num[t]); num[t]为t状态中1的个数 
  4 //【DP边界条件】dp[1][0][i] =num[i] 状态i能够满足第一行的硬件条件（注意：这里的i指的是第i个状态，不是一个二进制数，开一个数组保存二进制状态） 
  5 #include <iostream>
  6 #include <string>
  7 #include <cstdlib>
  8 #include <cstdio>
  9 #include <cstring>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <map>
 14 #include <set>
 15 
 16 using namespace std;
 17 
 18 int dp[105][100][100];
 19 int g[105];
 20 int v[100];
 21 int num[105];
 22 int n, m, top;
 23 
 24 bool check(int x)
 25 {
 26     if ((x&(x>>1)) != 0) return 0;
 27     if ((x&(x>>2)) != 0) return 0;
 28     if ((x&(x<<1)) != 0) return 0;
 29     if ((x&(x<<2)) != 0) return 0;
 30     return 1;
 31 }
 32 
 33 void init()
 34 {
 35     memset(dp, -1, sizeof(dp));
 36     top = 0;
 37     int total = 1<<m;
 38     for (int i = 0 ; i < total; ++i)
 39         if (check(i)) v[top++] = i;
 40 }
 41 
 42 bool fit(int x, int y)
 43 {
 44     if ((g[y]&x) != x) return false;
 45     return true;
 46 }
 47 
 48 int get1(int val)
 49 {
 50     int ans = 0;
 51     while (val)
 52     {
 53         ans += (val&1);
 54         val >>=  1;
 55     }
 56     return ans;
 57 }
 58 
 59 void work()
 60 {
 61     for (int i = 0; i < top; ++i)
 62     {
 63         num[i] = get1(v[i]);
 64         if (fit(v[i], 1)) dp[1][0][i] = num[i];
 65     }
 66 
 67     for (int i = 2; i <= n; ++i)
 68     {
 69         for (int t = 0; t < top; ++t)
 70         {
 71             if (!fit(v[t], i)) continue;
 72             for (int j = 0; j < top; ++j)
 73             {
 74                 if (v[t]&v[j]) continue;
 75                 for (int k = 0; k < top; ++k)
 76                 {
 77                     if (v[k]&v[t]) continue;
 78                     if (dp[i-1][j][k] == -1) continue;
 79                     dp[i][k][t] = max(dp[i][k][t], dp[i-1][j][k]+num[t]);
 80                 }
 81             }
 82         }
 83     }
 84 
 85     int ans = 0;
 86     for (int i = 1; i <= n; ++i)
 87         for (int j = 0; j < top; ++j)
 88             for (int k = 0; k < top; ++k)
 89                 ans = max(ans, dp[i][j][k]);
 90     printf("%d
", ans);
 91 }
 92 
 93 int main()
 94 {
 95     char c;
 96     while (~scanf("%d%d", &n, &m) && (m+n))
 97     {
 98         getchar();
 99         for (int i = 1; i <= n; ++i)
100         {
101             g[i] = 0;
102             for (int j = 1; j <= m; ++j)
103             {
104                scanf("%c", &c);
105                if (c == 'P') g[i] = (g[i]<<1)+1;
106                else g[i] = (g[i]<<1)+0;
107             }
108             getchar();
109         }
110         init();
111         work();
112     }
113 
114 
115     return 0;
116 }

View Code

10.Count Complete Tree Nodes

 1 //这题算啥，直接暴力不行，反正是瞎搞的
 2 class Solution {
 3 public:
 4     int height(TreeNode *root)
 5     {
 6         if (root == NULL) return 0;
 7         return 1+height(root->left);
 8     }
 9     
10     int work(TreeNode *root, int val)
11     {
12         if (root == NULL) return val;
13         if (height(root->left) == height(root->right))
14         {
15             if (root->right == NULL) return val;
16             return (val/2)+work(root->right, val/2);
17         }
18         if (root->left == NULL) return val;
19         else return work(root->left, val/2);
20     }
21     
22     int countNodes(TreeNode* root) {
23         if (root == NULL) return 0;
24         int depth = height(root);
25         int val = pow(2, depth-1);
26         int ans = pow(2, depth-1)-1;
27         return work(root, val)+ans;
28     }
29 };

View Code

11.Hie with the Pie

 1 //状态转移方程 dp[s][i] =min{dp[s][i],dp[s'][j]+dis[j][i]} dp[s][i]表示到达状态s时位于i位置的最小耗费，dis[j][i]表示两点之间的最短路.在DP之前要用floyd预处理一下求//出每两个点之间的最短距离。
 2 #include <iostream>
 3 #include <string>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <queue>
10 #include <map>
11 #include <set>
12 
13 #define INT_MAX 2147483647
14 using namespace std;
15 
16 const int maxn = 11;
17 
18 int g[maxn][maxn];
19 int dp[1<<10+10][maxn];
20 int n;
21 
22 void floyd()
23 {
24     for (int i = 0; i <= n; ++i)
25         for (int j = 0; j <= n; ++j)
26             for (int k = 0; k <= n; ++k)
27                 if (g[i][j] > g[i][k]+g[k][j])
28                     g[i][j] = g[i][k]+g[k][j];
29 }
30 
31 void work()
32 {
33     int m = (1<<n);
34 
35     for (int s = 0; s < m; ++s)
36     {
37         for (int i = 1; i <= n; ++i)
38         {
39             if (s&(1<<(i-1)))
40             {
41                 if (s == (1<<(i-1)))
42                     dp[s][i] = g[0][i];
43                 else
44                 {
45                     dp[s][i] = INT_MAX;
46                     for (int j = 1; j <= n; ++j)
47                     {
48                         if (s&(1<<(j-1)) && j != i)
49                             dp[s][i] = min(dp[s][i], dp[s^(1<<(i-1))][j]+g[j][i]);
50                     }
51                 }
52             }
53         }
54     }
55     int ans = dp[m-1][1]+g[1][0];
56     for (int i = 2; i <= n; ++i)
57         ans = min(ans, dp[m-1][i]+g[i][0]);
58     printf("%d
", ans);
59 }
60 
61 int main()
62 {
63     while (~scanf("%d", &n) && n)
64     {
65 
66         for (int i = 0; i <= n; ++i)
67             for (int j = 0; j <= n; ++j)
68                 scanf("%d", &g[i][j]);
69         floyd();
70         work();
71     }
72 
73     return 0;
74 }

View Code

12.Different Ways to Add Parenthese

 1 //分治
 2 class Solution {
 3 public:
 4     vector<int> work(vector<pair<int, int>>& vec, int left, int right)
 5     {
 6         vector<int> v1, v2, v3;
 7         if (left == right)
 8         {
 9             v3.push_back(vec[left].first);
10             return v3;
11         }
12         for (int i = left; i <= right; ++i)
13         {
14             if (vec[i].second)
15             {
16                 int flag = vec[i].first;
17                 v1 = work(vec, left, i-1);
18                 v2 = work(vec, i+1, right);
19                 for (int j = 0; j < v1.size(); ++j)
20                 {
21                     for (int k = 0; k < v2.size(); ++k)
22                     {
23                         int t1 = v1[j], t2 = v2[k];
24                         if (flag == 1) v3.push_back(t1+t2);
25                         else if (flag == 2) v3.push_back(t1-t2);
26                         else if (flag == 3) v3.push_back(t1*t2);
27                     }
28                 }
29             }
30         }
31         return v3;
32     }
33     
34     vector<int> diffWaysToCompute(string input) {
35         vector<pair<int, int>> vec;
36         int tmp = 0;
37         for (int i = 0; i < input.length(); ++i)
38         {
39             if (input[i] == '+')
40             {
41                 vec.push_back({tmp, 0});
42                 tmp = 0;
43                 vec.push_back({1, 1});
44             }
45             else if (input[i] == '-')
46             {
47                 vec.push_back({tmp, 0});
48                 tmp = 0;
49                 vec.push_back({2, 1});
50             }
51             else if (input[i] == '*')
52             {
53                 vec.push_back({tmp, 0});
54                 tmp = 0;
55                 vec.push_back({3, 1});
56             }
57             else tmp = tmp*10 + input[i]-'0';
58             if (i == input.length()-1) vec.push_back({tmp, 0});
59         }
60         vector<int> ans;
61         ans= work(vec, 0, vec.size()-1);
62         sort(ans.begin(), ans.end());
63         return ans;
64     }
65 };

View Code

13.Expression Add Operators

 1 //DFS， 注意'0'
 2 class Solution {
 3 public:
 4     vector<string> addOperators(string num, int target) {
 5         vector<string> res;
 6         addOperatorsDFS(num, target, 0, 0, "", res);
 7         return res;
 8     }
 9     void addOperatorsDFS(string num, int target, long long diff, long long curNum, string out, vector<string> &res) {
10         if (num.size() == 0 && curNum == target) {
11             res.push_back(out);
12         }
13         for (int i = 1; i <= num.size(); ++i) {
14             string cur = num.substr(0, i);
15             if (cur.size() > 1 && cur[0] == '0') return;
16             string next = num.substr(i);
17             if (out.size() > 0) {
18                 addOperatorsDFS(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res);
19                 addOperatorsDFS(next, target, -stoll(cur), curNum - stoll(cur), out + "-" + cur, res);
20                 addOperatorsDFS(next, target, diff * stoll(cur), (curNum - diff) + diff * stoll(cur), out + "*" + cur, res);
21             } else {
22                 addOperatorsDFS(next, target, stoll(cur), stoll(cur), cur, res);
23             }
24         }
25     }
26 };

View Code

14.Kth Largest Element in an Array

 1 //priority queue
 2 class Solution {
 3 public:
 4     int findKthLargest(vector<int>& nums, int k) {
 5         priority_queue<int> qu;
 6         for (int i = 0; i < nums.size(); ++i)
 7             qu.push(nums[i]);
 8         for (int i = 0; i < k-1; ++i)
 9             qu.pop();
10         return qu.top();
11     }
12 };

View Code

15. 滴滴打车笔试题

(超水的题目，替别人做的)给出多个数字输入，寻找最长的连续和为0的序列，并输出。

例如：input 1 -1 1 -1 2 -2 3 1 -1 -2 2

output : 1 -1 1 -1 2 -2

复杂度O(n)，扫描一遍即可

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <map>
10 #include <set>
11 #include <priority_queue>
12 #include <unordered_map>
13 #include <unordered_set>
14 
15 #define INT_MAX 2147483647
16 using namespace std;
17 
18 int main()
19 {
20     vector<int> v1, v2;
21     unordered_map<int, int> mp;
22     int val;
23     int left, right;
24     
25     while (~scanf("%d", &val)) v1.push_back(val), v2.push_back(val);
26     
27     val = 0;
28     for (int i = 1; i < v1.size(); ++i)
29     {
30         v1[i] += v1[i-1];
31         if (v1[i] == 0 && (i+1) > val) val = i+1, left = 0, right = i;
32         if (mp.count(v1[i]) == 0) mp.insert({v1[i], i});
33         else
34         {
35             if (i-mp[v1[i]] > val) val = i-mp[v1[i]], left = mp[v1[i]]+1, right = i;
36         }
37     }
38     
39     for (int i = left; i <= right; ++i)
40     {
41         if (i != left) printf(" ");
42         printf("%d", v2[i]);
43     }
44     puts("");
45     
46     return 0;
47 }

View Code

总结：这周主要做了一下DP类的题目，状态压缩DP，但是感觉DP类的题目还是不咋会做。看了几篇论文，也算是有点收获。中秋节，好好过节~~~~~~~~

下周：网络流类题目至少做10道。论文至少3篇。以后每周做一个类型的就可以，没啥事刷刷leetcode lintcode，如果乱做题，感觉收获不大。加油~

//计划不如变化快，尽量按照计划来！