const knapsack = (W, N, wt, val) =>{ let dp = newArray(); for (let i = 0; i < N + 1; i++){ dp[i] = newArray(); for (let j = 0; j < W + 1; j++){ dp[i][j] = 0; } }//先定义二维数组，并均初始化为0 for (i = 1; i <= N; i++){ for (w = 1; w <= W; W++){ if (w - wt[i - 1] < 0){ //当前背包容量放不下时，只能选择不装入背包 dp[i][w] = dp[i - 1][w]; } else { //装入或不装入背包的择优 dp[i][w] = max(dp[i - 1][w - wt[i - 1]] + val[i - 1], dp[i - 1][w]); } } } return dp[N][W]; } //使用动态规划遍历时，同时择优并用DP表来存储已经计算完的数据。
动态规划之子集背包分割
怎么将⼆维动态规划压缩成⼀维动态规划吗？这就是状态压缩，很容易的，
题目：给定一个只包含正整数的非空数组，是否可以将该数组分割成两个子集，使两个子集的元素和相等：
对于这个问题，看起来和背包没有任何关系，为什么说它是背包问题呢？ ⾸先回忆⼀下背包问题⼤致的描述是什么： 给你⼀个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两 个属性。其中第 i 个物品的重量为 wt[i] ，价值为 val[i] ，现在让你⽤ 这个背包装物品，最多能装的价值是多少？
那么对于这个问题，我们可以先对集合求和，得出 sum ，把问题转化为背 包问题：给⼀个可装载重量为sum / 2的背包和N个物品，每个物品的重量为nums[i]。现在让你装物品，是否存在⼀种装法，能够恰好将背包装满？
const lengthOfLIS = (nums) => { let dp = newArray(); for (let i = 0; i < nums.length; i++){ dp[i] = 1; } for (i = 0; i < nums.length; i++){ for (let j = 0; j < i; j++){ if (nums[i] > nums[j]){ dp[i] = max.(dp[i], dp[j] + 1); } } } let res = 0; //将每个以nums[i]结尾的LIS长度存到dp之后，遍历一遍找出最大的那个 for (i = 0; i < dp.length; i++){ res = max.(res, dp[i]); } return res; }
let arrayObj = [{}];//定义对象数组 let m = str1.length, n = str2.length; let dp = newArray(); for (let i = 0; i < m; i++){ dp[i] = newArray(); for (let j = 0; j < n; j++){ dp[i][j] = { 'val' : 0, 'choice' : 0, //val为其原本dp数组值，choice为操作，0代表什么也不做，1代表插入，2代表删除，3代表替换 }; } } //最终结果为dp[m][n]，后续则一步步反推，插入=>左移、替换=>左移并上移、删除=>上移,形成一条路径；这样一步步走回来了。
第⼀题就解决了，但是这样处理 base case 很⿇烦，⽽且注意⼀下状态转移 ⽅程，新状态只和相邻的⼀个状态有关，其实不⽤整个 dp 数组，只需要⼀ 个变量储存相邻的那个状态就⾜够了，这样可以把空间复杂度降到 O(1):
k= +infinity
k为正无穷，则可以把k、k-1看作一样，同样可以改写框架，数组中k已经不会改变，则不需要记录k。
1 2 3 4 5 6 7 8 9 10
intmaxProfit_k_inf(int[] prices){ int n = prices.length; int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { int temp = dp_i_0; dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]); dp_i_1 = Math.max(dp_i_1, temp - prices[i]); } return dp_i_0; }
k = infinity + coldDown
每次 sell 之后要等⼀天才能继续交易。只要把这个特点融⼊上⼀题的状态转 移⽅程即可：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) ; dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]); //解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，⽽不是 i-1 。 intmaxProfit_with_cool(int[] prices){ int n = prices.length; int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE; int dp_pre_0 = 0; // 代表 dp[i-2][0] for (int i = 0; i < n; i++) { int temp = dp_i_0; dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]); dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]); dp_pre_0 = temp; } return dp_i_0; }
k = +infinity with fee
每次交易要⽀付⼿续费，只要把⼿续费从利润中减去即可。
1 2 3 4 5 6 7 8 9 10 11 12 13
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) ; dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee); //解释：相当于买⼊股票的价格升⾼了。 在第⼀个式⼦⾥减也是⼀样的，相当于卖出股票的价格减⼩了。 intmaxProfit_with_fee(int[] prices, int fee){ int n = prices.length; int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { int temp = dp_i_0; dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]); dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee); } return dp_i_0; }
k = 2
k = 2 和前⾯题⽬的情况稍微不同，因为上⾯的情况都和 k 的关系不太⼤。 要么 k 是正⽆穷，状态转移和 k 没关系了；要么 k = 1，跟 k = 0 这个 base case 挨得近，最后也没有存在感。 这道题 k = 2 和后⾯要讲的 k 是任意正整数的情况中，对 k 的处理就凸显出 来了。
这道题由于没有消掉 k 的影响，所以必须要对 k 进⾏穷举：
1 2 3 4 5 6 7 8 9 10 11 12
int max_k = 2; int[][][] dp = newint[n][max_k + 1][2]; for (int i = 0; i < n; i++) { for (int k = max_k; k >= 1; k--) { if (i - 1 == -1) { /*处理 base case */ } dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]); dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]); } }// 穷举了 n × max_k × 2 个状态，正确。 return dp[n - 1][max_k][0];
k = any integer
有了上⼀题 k = 2 的铺垫，这题应该和上⼀题的第⼀个解法没啥区别。但是 出现了⼀个超内存的错误，原来是传⼊的 k 值会⾮常⼤，dp 数组太⼤了。 现在想想，交易次数 k 最多有多⼤呢？ ⼀次交易由买⼊和卖出构成，⾄少需要两天。所以说有效的限制 k 应该不超 过 n/2，如果超过，就没有约束作⽤了，相当于 k = +infinity。这种情况是之 前解决过的。 直接把之前的代码重⽤：
1 2 3 4 5 6 7 8 9 10 11 12
intmaxProfit_k_any(int max_k, int[] prices){ int n = prices.length; if (max_k > n / 2) return maxProfit_k_inf(prices); int[][][] dp = newint[n][max_k + 1][2]; for (int i = 0; i < n; i++) for (int k = max_k; k >= 1; k--) { if (i - 1 == -1) { /* 处理 base case */ } dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i0]); dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices;
classSolution { public: vector<int> twoSum(vector<int>& numbers, int target){ vector<int> v; for (int i = 0; i < numbers.size(); i++){ int t = target - numbers[i], l = i + 1, r = numbers.size() - 1; while (l <= r){ int mid = (l + r) / 2; if (numbers[mid] == t){ v.push_back(i + 1); v.push_back(mid + 1); return v; } if (numbers[mid] < t){ l = mid + 1; } else { r = mid - 1; } } } return v; } };
7、整数反转
给出一个32位的整数，需要将这个整数中每位上的数字进行反转。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: intreverse(int x){ longlong ans = 0; while (x) { ans = ans * 10 + x % 10; x /= 10; } if (ans < INT_MIN || ans > INT_MAX){ return0; } return (int)ans; } }; //小的类型会越界，则添加一个大的类型将其存储，并在后面添加判断语句。
9、判断回文数
判断一个整数是否是回文数；即从右往左和从左往右一样；其实就是将该数反转调过来。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution { public: boolisPalindrome(int x){ longlong y = 0, z = x; if (z < 0){ returnfalse; } while (z){ y = y * 10 + z % 10; z /= 10; } return y == x; } };
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode}l1 * @param {ListNode}l2 * @return {ListNode} */ var mergeTwoLists = function(l1, l2) { var ans = new ListNode(); var root = ans; while (l1 != null || l2 != null){ if (l1=== null){ root.next = l2; break; } if (l2 === null){ root.next = l1; break } if (l1.val < l2.val){ root.next = l1; l1 = l1.next; } else{ root.next = l2; l2 = l2.next; } root = root.next; } return ans.next; };
26、删除排序数组重复项
双指针法
1 2 3 4 5 6 7 8 9 10 11 12 13 14
/** * @param {number[]}nums * @return {number} */ var removeDuplicates = function(nums) { let left = 0, right = 1; while(right < nums.length){ if(nums[left] !== nums[right]){ nums[++left] = nums[right]; } right++; } return left + 1; };
27、移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
1 2 3 4 5 6 7 8 9
var removeElement = function(nums, val) { let ind = 0; for (let i = 0; i < nums.length; i++){ if (nums[i] != val){ nums[ind++] = nums[i]; } } return ind; };
//fill语句，将数组用...数据填充满，从第几位开始填充，且本身是不修改原数组长度的 //includes判断数组中是否包含一个指定的值 let arr = ["a","b","c","d","e"]; arr.includes("c",2); //后面参数代表从第几位开始检索
字符串新增方法
1 2 3 4 5 6 7 8 9 10 11 12 13
let str = "开课吧和面为课堂"； str.startsWith("开课吧");//返回一个bool值 str.endsWith("面为课堂")； str.repeat(30); //模板字符串，如何快速地构造出想要的字符串 //${}插值表达式，可以用值，也可以用函数，适合该值有复杂的逻辑处理 let p = document.querySelector("p"); let name = "小明"; let age = 18; let school = "大学"; p.innerHTML = `今年<strong>${name}</strong>就要<strong>${age}</strong>岁了，终于升入<strong>${school}</strong>了`； //先用``反引号将整个值包起来，在用插值表达式来一个个插入值 //模板字符串可以换行
let a = 0; let b = 1; let name = "小明"; let obj = { a, b, c(){ console.log("a"); }, [name]: 111; }; //可以直接在obj里面起属性名表达式，可通过变量来给属性名赋值。 //对象合并,其实可以使用之前的对象展开来进行合并 let obj = { a: 1, b :2 }; let obj2 = { c : 3, d :4 }; Object.assign(obj2 ，obj);//第一个参数为合并传入的对象
