Posts

LeetCode 动态规划 题目 6. 字符串相关 712 两个字符串的最小ASCII删除和 给定两个字符串，计算使两个字符串相同所需要删除的字符的ASCII值的和的最小值。 对于两个字符串中的字符 s1[i] 和 s2[j]，如果s1[i] == s2[j]，那么这两个字符都不需要被删除，所以 dp[i][j] = dp[i - 1][j - 1]，否则至少有一个应该被删除，取两个中的最小值，状态转移方程是dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j])。时间复杂度是 O(m * n)，空间复杂度是 O(m * n)。 class Solution { public: int minimumDeleteSum(string s1, string s2) { int n1 = s1.size(), n2 = s2.size(); vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0)); for (int i = 1; i <= n1; ++i) dp[i][0] = dp[i - 1][0] + s1[i - 1]; for (int j = 1; j <= n2; ++j) dp[0][j] = dp[0][j - 1] + s2[j - 1]; for (int i = 0; i < n1; ++i) for (int j = 0; j < n2; ++j) if (s1[i] == s2[j]) dp[i + 1][j + 1] = dp[i][j]; else dp[i + 1][j + 1] = min(dp[i][j] + s1[i] + s2[j], min(dp[i][j + 1] + s1[i], dp[i + 1][j] + s2[j])); return dp[n1][n2]; } }; 5 最长回文子串 找到一个字符串中的最长回文子串。...

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 个丑数。...

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 交替位二进制数 检查一个二进制数相邻的两个位数是否均不相等。...