Posts

LeetCode 动态规划 题目 3. 数组相关 300 最长上升子序列 在无序数组中找到最长上升子序列的长度。 用一个数组 dp[i] 表示到第 i 个数字为止的最长上升子序列，每次遍历 i 之前的每个数字 j，如果 nums[i] > nums[j]，那么 j 和 i 可以形成一个上升子序列，让 dp[i] = max(dp[i], dp[j] + 1) 就能得到最长的上升子序列了。 class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(), res = 2; if (n <= 1) return n; vector<int> dp(n, 1); for (int i = 1; i < n; ++i) for (int j = 0; j < i; ++j) if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); res = max(res, dp[i]); } return res; } }; 53 最大子序和 找一个数组中具有最大和的连续子数组的和。 ...

LeetCode 动态规划 题目 1. 数字相关 263 丑数 判断一个数 num 是否是丑数。 通用的方法是自底向上求出大于等于 num 的第一个数来判断 num 是否是丑数。但这道题已经给出了数 num，直接通过模运算就能得到结果了。 class Solution { public: bool isUgly(int num) { if (num < 1) return false; while (num % 2 == 0) num /= 2; while (num % 3 == 0) num /= 3; while (num % 5 == 0) num /= 5; return num == 1; } }; 264 丑数 II 求第 n 个丑数。 用一个数组 ugly 来保存前 m 个丑数，用三个质因数 2，3，5 乘以其当前系数对应的丑数，得到新的丑数，最小的一个就是第 m + 1 个丑数。时间复杂度是 O(m * n)，其中 m 是质因数的个数，n 是要找的第 n 个丑数。 class Solution { public: int nthUglyNumber(int n) { vector<int> ugly(n, 1); int base_2 = 0, base_3 = 0, base_5 = 0; int m = INT_MAX; for (int i = 1; i < n; ++i) { ugly[i] = min({2 * ugly[base_2], 3 * ugly[base_3], 5 * ugly[base_5]}); if (2 * ugly[base_2] == ugly[i]) ++base_2; if (3 * ugly[base_3] == ugly[i]) ++base_3; if (5 * ugly[base_5] == ugly[i]) ++base_5; cout << ugly[i] << endl; } return ugly[n - 1]; } }; 313 超级丑数 给定质因数数组 primes，求第 n 个丑数。 ...

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的最大子矩阵。 ...