知识点模拟思路模拟加法的进位过程，翻转两个字符串，从前往后进行加法，同时维护一个进位carry。每一次把当前位记录到结果字符串中。最后反转结果字符串即可。时间复杂度 AC Code (c++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a string字符串 * @param b string字符串 * @return string字符串 */ string addBinary(str...

知识点动态规划思路因为要求刚好匹配 所以不满足则不可以, 所以 定义f[i][j]  表示t的前i个字符 是否满足能 s前i个字符和x的前i-j个字符匹配由于 所以状态数最多20000个每次状态转移, 讨论当前t中的字符和哪一个字符串的字符相匹配, 单次转移的时间复杂度为总的时间复杂度 AC Code (c++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param x string...

知识点背包问题 DP思路首先先对所有的数求和，如果是奇数则不可拆分。之后需要凑出sum/2的总和，问题转化成有n个数可以选一次或者不选，求出是否能凑出sum/2，则可以用01背包解决。实现上可以 一维空间优化。时间复杂度 AC Code（C++） #include <numeric> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param weights int整型vector * @return bool布尔型 ...

知识点动态规划思路定义f[i]为到达下标为i位置所需要的最小的代价, 答案为f[n]每一次可以从前面3个位置进行转移时间复杂度 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param height int整型vector * @return int整型 */ const int INF = 1e9; int minEnergyJump(vector<int>&am...

知识点二分思路两次二分分别找到比所求段小的第一个位置和当前数字的第一个位置即可。重要的在于二分边界条件的书写。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param weights int整型vector * @param target int整型 * @return int整型vector */ int n; vector<int> sea...

知识点前后缀分解 前缀和思路不能使用除法，我们可以预处理每个位置的前后缀的乘积，然后遍历每个位置用前后缀的乘积来计算得到答案。时间复杂度预处理前后缀和 遍历整个数组 整体时间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param milk_amount int整型vector * @return int整型vector */ vector<int> product...

知识点二分思路在一个有序序列中寻找第一个大于等于x的值，可以使用二分法进行，实现上可以直接调用lower_bound函数时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param labels int整型vector * @param target int整型 * @return int整型 */ int searchInsert(vector<int>...

知识点记忆化搜索思路定义状态 f[i]为总和为i的最优分解, 由于可以全分解为1, 所以任何数都是存在合法分解的我们可以根据当前选取什么数t , 将该问题转化为一个子问题递归终点为x为0时 返回空数组状态数为n, 每一次转移需要枚举次, 总的时间复杂度为 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型vector */ con...

知识点模拟 归并思路从后往前，归并两个数组，如果一个数组全用完了，就把剩下的接在后面就好了。时间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param time1 int整型vector * @param time2 int整型vector * @param m int整型 * @param n int整型 * @return int整型 */ ...

知识点DP思路状态表示 f[i][j]表示到达位置(i, j)的合法方案数由于可以从上方来, 也可以从左边来, 按照这两个来源进行更新即可时间复杂度 AC Code (c++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型vector<vector<>> * @return int整型 */ int uniquePathsWithObstacles(vec...

知识点最短路 Dijkstra思路这道题要求可以上下左右四个方向移动，那么需要用Dijkstra算法，如果只允许向下或者向右移动，那么可以用DP解决。DP在当前的题面中是错误的。hack数据：[[1,1,1,9],[9,9,1,9],[9,1,1,9],[9,1,9,9],[9,1,1,1]]这个数据长这样, 明显存在一条为1的最短路，DP无法得到这个解1 1 1 99 9 1 99 1 1 99 1 9 99 1 1 1我认为正解是dijkstra，每一次可以向周围的四个格子移动。n为点数, m是边数, 由于只能向周围四个方向移动, m = 4n, 所以时间复杂度为AC Code (C++...

知识点哈希表思路从左到右遍历，用哈希表记录下每个数出现的最左端的位置。每次找target-当前数的数是否存在，存在则更新答案。时间复杂度 AC Code（C++） #include <unordered_map> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param info int整型vector * @param target_weight int整型 * @return int整型vector ...

知识点状态机DP思路状态表示: f[i][j] 表示前i个位置且第i个位置 取/不取的状态为j的最大值状态转移: f[i][0] = max(f[i-1][0], f[i-1][1]) f[i][1] = f[i-1][0] + nums[i-1](下标从0开始)时间复杂度 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 ...

知识点分类讨论 DP思路环形排列，我们可以分类讨论是否取第一个房子和最后一个房子来进行分类讨论其余的部分和上一道题完全一致。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int eatGrass(vector<int>& nums) { int f[100...