1. 单链表如何做到O（1）的删除复杂度。
简单的跟他下一个元素交换，然后删除下一个元素。如果是最后一个元素怎么办，我也不知道。
2. lru, lfu的写法还不是很熟悉，有时间再写一下。
3. 有一个n*m的矩阵，矩阵上有一个数字代表颜色，当连续的5个元素是相同的时候，就认为是可消除的。连续包括上下，左右或者斜着，就是八连通的。
判断：1.这个矩阵是不可消除的。 2. 存在一个交换，使得他跟上下左右，某一个元素交换以后（注意，这里的交换元素是四连通的），是可消除的。
分析：简单的暴力即可。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 int a[maxn][maxn]; 8 int n, m; 9 int dx[] = {-1, 1, -1, 1, -1, 1, 0, 0}; 10 int dy[] = {-1, 1, 0, 0, 1, -1, -1, 1}; 11 bool in(int x, int y) { 12 if(x >= 0 && x < n && y >= 0 && y < m) return 1; 13 return 0; 14 } 15 bool check(int x, int y) { 16 for (int i = 0; i < 8; i += 2) { 17 int c = 1; 18 int cur = a[x][y]; 19 int cx = x + dx[i], cy = y + dx[i]; 20 while(check(cx, cy) && a[cx][cy] == cur && c < 5) { 21 c++; 22 cx = cx + dx[i], cy = cy + dx[i]; 23 } 24 if(c >= 5) return 1; 25 cx = x + dx[i + 1], cy = y + dy[i]; 26 while(check(cx, cy) && a[cx][cy] == cur && c < 5) { 27 c++; 28 cx = cx + dx[i + 1], cy = cy + dy[i + 1]; 29 } 30 if(c >= 5) return 1; 31 } 32 return 0; 33 } 34 int ax[] = {1, -1, 0, 0}; 35 int ay[] = {0, 0, 1, -1}; 36 bool solve() { 37 cin >> n >> m; 38 for (int i = 0; i < n; i++) 39 for (int j = 0; j < m; j++) 40 cin >> a[i][j]; 41 for (int i = 0; i < n; i++) { 42 for (int j = 0; j < m; j++) { 43 if(check(i, j)) return 0; 44 } 45 } 46 for (int i = 0; i < n; i++) { 47 for (int j = 0; j < m; j++) { 48 for (int k = 0; k < 4; k++) { 49 int cx = i + ax[k], cy = j + ay[k]; 50 if(in(cx, cy)) { 51 swap(a[i][j], a[cx][cy]); 52 if(check(i, j)) 53 return 1; 54 swap(a[i][j], a[cx][cy]); 55 } 56 } 57 } 58 } 59 return 0; 60 } 61 62 int main() { 63 freopen("test.in", "r", stdin); 64 //freopen("test.out", "w", stdout); 65 ios::sync_with_stdio(0); 66 cin.tie(0); cout.tie(0); 67 solve(); 68 return 0; 69 }
4. 单链表的反转。二叉树通过额外的指针使得每一层串起来。双链表的复制，但是，每个节点有一个额外的random指针，指向链表中的某一个元素，编写这个链表的复制方法。
5. to_string, sprintf, 函数的使用。
6. 今日头条4.18笔试后2道题目：
官方题解：http://discuss.acmcoder.com/topic/58f60f8fa846074f746580d7
第三道题目：
先用一个矩阵保存最后的结果，处理完毕以后打印结果。
好多边界条件，确实没有考虑到，小数的处理，比如1.0， 1.10, 1.11， 末尾的0，是不需要打印的。这点很重要。
程序的逻辑，以及代码复用，减少编程复杂度。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 bool res[10][100]; 8 int tot; 9 int a, b; 10 char ch[10]; 11 int work(char x) { 12 //cout << x <<endl; 13 if(x == '1') { 14 for (int i = 0; i < 5; i++) 15 res[i][tot + 1] = 1; 16 tot += 3; 17 } else if(x == '0') { 18 res[0][tot + 1] = 1, res[0][tot + 2] =1, res[0][tot + 3] = 1; 19 res[1][tot + 1] = 1, res[1][tot + 2] =0, res[1][tot + 3] = 1; 20 res[2][tot + 1] = 1, res[2][tot + 2] =0, res[2][tot + 3] = 1; 21 res[3][tot + 1] = 1, res[3][tot + 2] =0, res[3][tot + 3] = 1; 22 res[4][tot + 1] = 1, res[4][tot + 2] =1, res[4][tot + 3] = 1; 23 tot += 5; 24 } else if(x == '2') { 25 res[0][tot + 1] = 1, res[0][tot + 2] =1, res[0][tot + 3] = 1; 26 res[1][tot + 1] = 0, res[1][tot + 2] =0, res[1][tot + 3] = 1; 27 res[2][tot + 1] = 1, res[2][tot + 2] =1, res[2][tot + 3] = 1; 28 res[3][tot + 1] = 1, res[3][tot + 2] =0, res[3][tot + 3] = 0; 29 res[4][tot + 1] = 1, res[4][tot + 2] =1, res[4][tot + 3] = 1; 30 tot += 5; 31 } else if(x == '3') { 32 res[0][tot + 1] = 1, res[0][tot + 2] =1, res[0][tot + 3] = 1; 33 res[1][tot + 1] = 0, res[1][tot + 2] =0, res[1][tot + 3] = 1; 34 res[2][tot + 1] = 1, res[2][tot + 2] =1, res[2][tot + 3] = 1; 35 res[3][tot + 1] = 0, res[3][tot + 2] =0, res[3][tot + 3] = 1; 36 res[4][tot + 1] = 1, res[4][tot + 2] =1, res[4][tot + 3] = 1; 37 tot += 5; 38 } else if(x == '4') { 39 res[0][tot + 1] = 1, res[0][tot + 2] =0, res[0][tot + 3] = 1; 40 res[1][tot + 1] = 1, res[1][tot + 2] =0, res[1][tot + 3] = 1; 41 res[2][tot + 1] = 1, res[2][tot + 2] =1, res[2][tot + 3] = 1; 42 res[3][tot + 1] = 0, res[3][tot + 2] =0, res[3][tot + 3] = 1; 43 res[4][tot + 1] = 0, res[4][tot + 2] =0, res[4][tot + 3] = 1; 44 tot += 5; 45 } else if(x == '5') { 46 res[0][tot + 1] = 1, res[0][tot + 2] =1, res[0][tot + 3] = 1; 47 res[1][tot + 1] = 1, res[1][tot + 2] =0, res[1][tot + 3] = 0; 48 res[2][tot + 1] = 1, res[2][tot + 2] =1, res[2][tot + 3] = 1; 49 res[3][tot + 1] = 0, res[3][tot + 2] =0, res[3][tot + 3] = 1; 50 res[4][tot + 1] = 1, res[4][tot + 2] =1, res[4][tot + 3] = 1; 51 tot += 5; 52 } else if(x == '6') { 53 res[0][tot + 1] = 1, res[0][tot + 2] =1, res[0][tot + 3] = 1; 54 res[1][tot + 1] = 1, res[1][tot + 2] =0, res[1][tot + 3] = 0; 55 res[2][tot + 1] = 1, res[2][tot + 2] =1, res[2][tot + 3] = 1; 56 res[3][tot + 1] = 1, res[3][tot + 2] =0, res[3][tot + 3] = 1; 57 res[4][tot + 1] = 1, res[4][tot + 2] =1, res[4][tot + 3] = 1; 58 tot += 5; 59 } else if(x == '7') { 60 res[0][tot + 1] = 1, res[0][tot + 2] =1, res[0][tot + 3] = 1; 61 res[1][tot + 1] = 0, res[1][tot + 2] =0, res[1][tot + 3] = 1; 62 res[2][tot + 1] = 0, res[2][tot + 2] =0, res[2][tot + 3] = 1; 63 res[3][tot + 1] = 0, res[3][tot + 2] =0, res[3][tot + 3] = 1; 64 res[4][tot + 1] = 0, res[4][tot + 2] =0, res[4][tot + 3] = 1; 65 tot += 5; 66 } else if(x == '8') { 67 res[0][tot + 1] = 1, res[0][tot + 2] =1, res[0][tot + 3] = 1; 68 res[1][tot + 1] = 1, res[1][tot + 2] =0, res[1][tot + 3] = 1; 69 res[2][tot + 1] = 1, res[2][tot + 2] =1, res[2][tot + 3] = 1; 70 res[3][tot + 1] = 1, res[3][tot + 2] =0, res[3][tot + 3] = 1; 71 res[4][tot + 1] = 1, res[4][tot + 2] =1, res[4][tot + 3] = 1; 72 tot += 5; 73 } else if(x == '9') { 74 res[0][tot + 1] = 1, res[0][tot + 2] =1, res[0][tot + 3] = 1; 75 res[1][tot + 1] = 1, res[1][tot + 2] =0, res[1][tot + 3] = 1; 76 res[2][tot + 1] = 1, res[2][tot + 2] =1, res[2][tot + 3] = 1; 77 res[3][tot + 1] = 0, res[3][tot + 2] =0, res[3][tot + 3] = 1; 78 res[4][tot + 1] = 1, res[4][tot + 2] =1, res[4][tot + 3] = 1; 79 tot += 5; 80 } else if(x == '+') { 81 res[0][tot + 1] = 0, res[0][tot + 2] =0, res[0][tot + 3] = 0; 82 res[1][tot + 1] = 0, res[1][tot + 2] =1, res[1][tot + 3] = 0; 83 res[2][tot + 1] = 1, res[2][tot + 2] =1, res[2][tot + 3] = 1; 84 res[3][tot + 1] = 0, res[3][tot + 2] =1, res[3][tot + 3] = 0; 85 res[4][tot + 1] = 0, res[4][tot + 2] =0, res[4][tot + 3] = 0; 86 tot += 5; 87 } else if(x == '-') { 88 res[0][tot + 1] = 0, res[0][tot + 2] =0, res[0][tot + 3] = 0; 89 res[1][tot + 1] = 0, res[1][tot + 2] =0, res[1][tot + 3] = 0; 90 res[2][tot + 1] = 1, res[2][tot + 2] =1, res[2][tot + 3] = 1; 91 res[3][tot + 1] = 0, res[3][tot + 2] =0, res[3][tot + 3] = 0; 92 res[4][tot + 1] = 0, res[4][tot + 2] =0, res[4][tot + 3] = 0; 93 tot += 5; 94 } else if(x == '*') { 95 res[0][tot + 1] = 0, res[0][tot + 2] =0, res[0][tot + 3] = 0; 96 res[1][tot + 1] = 1, res[1][tot + 2] =0, res[1][tot + 3] = 1; 97 res[2][tot + 1] = 0, res[2][tot + 2] =1, res[2][tot + 3] = 0; 98 res[3][tot + 1] = 1, res[3][tot + 2] =0, res[3][tot + 3] = 1; 99 res[4][tot + 1] = 0, res[4][tot + 2] =0, res[4][tot + 3] = 0; 100 tot += 5; 101 } else if(x == '/') { 102 res[0][tot + 1] = 0, res[0][tot + 2] =0, res[0][tot + 3] = 0; 103 res[1][tot + 1] = 0, res[1][tot + 2] =0, res[1][tot + 3] = 1; 104 res[2][tot + 1] = 0, res[2][tot + 2] =1, res[2][tot + 3] = 0; 105 res[3][tot + 1] = 1, res[3][tot + 2] =0, res[3][tot + 3] = 0; 106 res[4][tot + 1] = 0, res[4][tot + 2] =0, res[4][tot + 3] = 0; 107 tot += 5; 108 } else if(x == '=') { 109 res[0][tot + 1] = 0, res[0][tot + 2] =0, res[0][tot + 3] = 0;res[0][tot + 4] = 0; 110 res[1][tot + 1] = 1, res[1][tot + 2] =1, res[1][tot + 3] = 1;res[1][tot + 4] = 1; 111 res[2][tot + 1] = 0, res[2][tot + 2] =0, res[2][tot + 3] = 0;res[2][tot + 4] = 0; 112 res[3][tot + 1] = 1, res[3][tot + 2] =1, res[3][tot + 3] = 1;res[3][tot + 4] = 1; 113 res[4][tot + 1] = 0, res[4][tot + 2] =0, res[4][tot + 3] = 0;res[4][tot + 4] = 0; 114 tot += 6; 115 } else if(x == '.') { 116 res[0][tot + 1] = 0, res[0][tot + 2] =0; 117 res[1][tot + 1] = 0, res[1][tot + 2] =0; 118 res[2][tot + 1] = 0, res[2][tot + 2] =0; 119 res[3][tot + 1] = 1, res[3][tot + 2] =1; 120 res[4][tot + 1] = 1, res[4][tot + 2] =1; 121 tot += 4; 122 } 123 } 124 void do1(double x) { 125 char t[20]; 126 if(x - int(x) == 0) { 127 sprintf(t, "%.0f", x); 128 } else if(x * 10 - (int)(x * 10) <= 1e-8) { 129 sprintf(t, "%.1f", x); 130 } else { 131 sprintf(t, "%.2f", x); 132 } 133 int n = strlen(t); 134 for (int i = 0; i < n; i++) 135 work(t[i]); 136 } 137 void solve() { 138 //double t = 0.4; 139 //cout << (t * 10 - int(t * 10) <= 1e-9) << endl; 140 //return; 141 cin >> a >> ch >> b; 142 do1(a); 143 work(ch[0]); 144 do1(b); 145 work('='); 146 double r = 0; 147 if(ch[0] == '+') { 148 r = a + b; 149 } else if(ch[0] =='-') { 150 r = a - b; 151 } else if(ch[0] == '*') { 152 r = a * b; 153 } else if(ch[0] == '/') { 154 r = 1.0 * a / b; 155 } 156 do1(r); 157 for (int i = 0; i < 5; i++) { 158 for (int j = 0; j < tot; j++) 159 cout << (res[i][j] ? '*' : ' '); 160 cout << endl; 161 } 162 } 163 164 int main() { 165 freopen("test.in", "r", stdin); 166 //freopen("test.out", "w", stdout); 167 ios::sync_with_stdio(0); 168 cin.tie(0); cout.tie(0); 169 solve(); 170 return 0; 171 }
第四道：
根本没有想法，看的题解。
动态规划，如何dp， 肯定是dp[i][j][k]的形式，对于每个位置，算出挑选k个元素的最大值。关键问题是：怎么考虑转移方程。
我理解的不是很明白，还是看上面的官方题解吧。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e2 + 10; 7 int n, k; 8 int a[maxn][maxn]; 9 int s[maxn][maxn]; 10 int dp[maxn][maxn][5100]; 11 void solve() { 12 cin >> n >> k; 13 for (int i = 1; i <= n; i++) { 14 for (int j = 1; j <= i; j++) 15 cin >> a[i][j]; 16 } 17 for (int i = 1; i <= n; i++) { 18 for (int j = 1; j <= i; j++) { 19 s[i][j] = s[i][j - 1] + a[n - j + 1][n - i + 1]; 20 cout << i << " " << j << " " << s[i][j] << endl; 21 } 22 } 23 memset(dp, -1, sizeof dp); 24 for (int i = 0; i <= n; i++) 25 dp[i][0][0] = 0; 26 for (int i = 1; i <= n; i++) { 27 for (int j = i; j >= 0; j--) { 28 for (int x = j; x <= k; x++) { 29 dp[i][j][x] = max(dp[i][j + 1][x], s[i][j] + dp[i - 1][max(0,j - 1)][x - j] ); 30 } 31 } 32 } 33 cout << dp[n][0][k] << endl; 34 35 } 36 37 int main() { 38 freopen("test.in", "r", stdin); 39 //freopen("test.out", "w", stdout); 40 ios::sync_with_stdio(0); 41 cin.tie(0); cout.tie(0); 42 solve(); 43 return 0; 44 }