1. 有一个n*m的网格，刚开始都是海洋，然后不断加入岛屿（x,y），岛屿上下左右的岛屿会连接到一起形成一个新的岛屿，求每次这样的操作以后岛屿的数目。
给出复杂度说明。
答：采用并查集，复杂度O（1）。
就是这道题 https://hihocoder.com/problemset/problem/1487
2. 也是n*m的网格，给出从左上角到右下角的一条随机路径，每次可以往上下左右四个方向行进。
while的判断条件没有写好。
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl 10 typedef long long ll; 11 using namespace std; 12 typedef pair<int, int> pii; 13 const int maxn = 1e3 + 10; 14 int n, m; 15 int a[maxn][maxn]; 16 vector<pii> p; 17 int dx[] = {-1, 0, 1, 0}; 18 int dy[] = {0, 1, 0, -1}; 19 bool check(int x, int y) { 20 if(x < 0 || x >= n || y < 0 || y >= m) return 0; 21 return 1; 22 } 23 int work(int x, int y) { 24 int r = 0; 25 for (int i = 0; i < 4; i++) { 26 int cx = x + dx[i], cy = y + dy[i]; 27 if(check(cx, cy) && a[cx][cy] == 0) { 28 r++; 29 } 30 } 31 return r; 32 } 33 void solve() { 34 cin >> n >> m; 35 int x, y; 36 x = y = 0; 37 p.pb({x, y}); 38 a[x][y] = 1; 39 srand(time(0)); 40 while(x != n - 1 || y != m - 1) { 41 42 int c = work(x, y); 43 if(c == 0) { 44 a[x][y] = 0; 45 x = p.back().first, y = p.back().second; 46 p.pop_back(); 47 } else { 48 int t = rand() % c; 49 for (int i = 0, j = 0; i < 4; i++) { 50 int cx = x + dx[i], cy = y + dy[i]; 51 if(check(cx, cy) && a[cx][cy] == 0) { 52 if(j == t) { 53 p.pb({cx, cy}); 54 a[cx][cy] = 1; 55 x = cx, y = cy; 56 break; 57 } else j++; 58 } 59 } 60 } 61 //cout << x << " asd " << y << endl; 62 } 63 //cout << x << " a " << y << endl; 64 for (pii t : p) 65 cout << t.first << " " << t.second << endl; 66 } 67 int main() { 68 freopen("test.in", "r", stdin); 69 //freopen("test.out", "w", stdout); 70 ios::sync_with_stdio(0); 71 cin.tie(0); cout.tie(0); 72 solve(); 73 return 0; 74 }
3. 判断2个链表是否相交。
经典的办法，得到2个链表长度，长的往后移动2个链表长度的差值，然后举个判断是否相等。
这些巧妙的办法需要多看书，多看discuss的解决办法。
4. 美团笔试的要求2个二叉树节点的最近公共祖先，要求空间复杂度是O（1）的。
那就是递归调用，好像剑指offer上面有讲。
5. 完美世界的笔试题目，比较简单，一个是排序合并，一个是用stack模拟，判断是否合法。
6. 腾讯，碎掉的玻璃球，好像不知道怎么解。给定数，判断有多少质数对的和，等于这个数。
总结：剑指offer，编程之美的书，需要好好看一看了。