Posts

LeetCode 二分查找 二分查找可以在有序数组中以较高的效率查找符合条件的值，时间复杂度是O(logN)，空间复杂度是O(1)。 易错点 计算中间值的方法 k = i + (j - i) / 2 k = (i + j) / 2 第二种方法一般都会造成整型数据溢出，所以只用第一种方法。 循环条件 如果要找唯一的值，且下限i和上限j都会在更新时在中间值k的基础上+1或-1，那么循环条件是 i <= j，j能被取到，j = nums.size() - 1，计算中间值用 k = i + (j - i + 1) / 2 如果要找大于等于或小于等于某条件的值，且下限i和上限j其中之一不会在k的基础上+1或-1，那么循环条件是 i < j，j不能被取到，j = nums.size()，计算中间值用 k = i + (j - i) / 2 两种方法有各自的应用场景，没用对的话会出现边界值的问题，或是死循环导致TLE。 题目 1. 查找数 704 二分查找 在有序数组中搜索目标值，如果存在则返回下标，否则返回 -1。 最标准的二分查找。因为下限i和上限j都会在更新时+1和-1，所以让j = nums.size() - 1，循环条件是 i <= j。 ...

LeetCode 位运算 位运算包括： 与 & 或 | 异或 ^ 取反 ~ 左移 « 右移 » 技巧 移位运算 x « 1：算数左移 数字的二进制表示的所有位向左移动一位，相当于乘以 2 在右边补 0 x » 1：算数右移 数字的二进制表示的所有位向右移动一位，相当于除以 2 在左边补符号位，即正数补 0，负数（在补码的基础上）补 1 负数移位 负数是以补码的形式存储的，负数进行右移运算时需要将其取反转换成反码，加一转换成补码，再将其向右移动一位得到新的补码，再将其减一得到新的反码，再取反转换成原码才能得到结果。例如 -7 的二进制表示是 10000111（因为 32 位太长所以这里用 8 位 int 型表示），其反码是 11111000，补码是11111001，向右移动一位是 11111100，减一得到新的反码 11111011，原码是10000100，也就是 -4；补码向左移一位是 11110010，减一得到新的反码 11110001，原码是 10001110，也就是 -14 比较简单的理解方式是左移乘以 2，右移除以 2。例如 -7 » 1 = -7 / 2 = -4，-7 « 1 = -14 题目 1. 单个数字 693 交替位二进制数 检查一个二进制数相邻的两个位数是否均不相等。 ...

Kick Start 2019 Round C Wiggle Walk (6pts, 12pts) 在一个R * C的矩阵里面移动，遇到已经走过的格子直接跳过。数据保证移动时不会超出给定的矩阵。 Solution: Simulation 用一个visited数组记录已经走过的格子，遇到走过的格子则直接跳过往后遍历。讲道理这个方法时间复杂度是过不了Hidden Test Set的，但是我也不知道为什么就过了。 时间复杂度：O(n^2) 空间复杂度：O(n^2) // C++ #include <iostream> #include <cmath> #include <cstdio> #include <math.h> #include <limits> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; vector<vector<bool>> visited(50001, vector<bool>(50001, false)); void Forward(char &p, int &r, int &c) { if (p == 'E') { while (visited[r][c + 1]) ++c; visited[r][++c] = true; } else if (p == 'W') { while (visited[r][c - 1]) --c; visited[r][--c] = true; } else if (p == 'N') { while (visited[r - 1][c]) --r; visited[--r][c] = true; } else if (p == 'S') { while (visited[r + 1][c]) ++r; visited[++r][c] = true; } } void solve(const int &t) { int n, R, C, r, c; string str; scanf("%d %d %d %d %d", &n, &R, &C, &r, &c); cin >> str; visited = vector<vector<bool>>(50001, vector<bool>(50001, false)); visited[r][c] = true; for (int i = 0; i < n; ++i) Forward(str[i], r, c); printf("Case #%d: %d %d\n", t, r, c); } int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; ++t) solve(t); return 0; } Circuit Board (14pts, 20pts) 在矩阵里找到每一行最大值与最小值不超过K的最大子矩阵。 ...

Object Detection Object detection deals with detecting instances of objects of a certain class, such as humans, animals, etc, in digital images and videos. Object detection has applications in many areas of computer vision, including image retrieval, face detection, video surveillance, and self-driving, etc. Current detection systems repurpose classifiers to perform detection. To detect an object, these systems take a classifier for that object and evaluate it at various locations and scales in a test image. ...

Code Jam 2019 Round 1C Robot Programming Strategy (10pts, 18pts) 已知所有人石头剪刀布的出招顺序，每一轮同时和所有人比赛，找到必胜的策略。 Solution: Eliminiating 每一轮遍历当前轮次所有人的出招，如果同时有三种情况（R, P, S）则没有必胜策略，直接输出IMPOSSIBLE；否则返回胜利或打平的策略。 对于已经打败过的对手没有必要再考虑其之后的出招，所以用一个defeated数组保存已经打败过的对手以便直接跳过。因为当前轮次有可能超过对手的出招顺序长度，所以要用i % size获取对手当前的出招。 时间复杂度：O(A ^ 2) 空间复杂度：O(A) #include <iostream> #include <cmath> #include <cstdio> #include <math.h> #include <limits> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; char Decide(const char &R, const char &P, const char &S) { if (R && P && S) return 'X'; if (R && P) return 'P'; if (R && S) return 'R'; if (P && S) return 'S'; if (R) return 'P'; if (P) return 'S'; return 'R'; } bool Defeate(const char &current, const char &opponent) { return (current == 'R' && opponent == 'S') || (current == 'S' && opponent == 'P') || (current == 'P' && opponent == 'R'); } void solve(const int &t) { int A; scanf("%d", &A); int i = 0; vector<string> opponent(A); vector<bool> defeated(A, false); bool R, P, S; string res; for (int a = 0; a < A; ++a) cin >> opponent[a]; while (true) { int current_opponent = 0; R = false, P = false, S = false; for (int a = 0; a < A; ++a) { if (!defeated[a]) { ++current_opponent; if (opponent[a][i % opponent[a].size()] == 'R') R = true; else if (opponent[a][i % opponent[a].size()] == 'P') P = true; else S = true; } } if (current_opponent == 0) break; char result = Decide(R, P, S); if (result == 'X') { res = "IMPOSSIBLE"; break; } res += result; for (int a = 0; a < A; ++a) { if (!defeated[a] && Defeate(result, opponent[a][i % opponent[a].size()])) defeated[a] = true; } ++i; } printf("Case #%d: %s\n", t, res.c_str()); } int main() { int T; scanf("%d", &T); for (int t = 1; t <= T; ++t) solve(t); return 0; } Power Arrangers (11pts, 21pts) // TODO ...