【JavaScript】LeetCode：96-100
96 单词拆分
- 动态规划
- 完全背包：背包-字符串s，物品-wordDict中的单词，可使用多次。
- 问题转换：s能否被wordDict中的单词组成。
- dp[i]：长度为i的字符串s[0, i]能否被wordDict组成，dp[i] = true / false。
- 两层for循环遍历顺序：先背包后物品。
- i为字符串长度，j从0开始，一直遍历到i - 1，若s[j, i]在wordDict中，且s[0, i - j]能被wordDict组成，则s[0, i]能被wordDict组成。
- 初始化：dp[0] = true，其他为false。
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function(s, wordDict) {
let dp = Array(s.length + 1).fill(0);
dp[0] = 1;
for(let i = 1; i <= s.length; i++){
for(let j = 0; j < i; j++){
if(wordDict.includes(s.slice(j, i)) && dp[j] == 1){
dp[i] = 1;
}
}
}
return dp[s.length]? true: false;
};
97 最长递增子序列
- 动态规划
- dp[i]：以nums[i]为结尾的最长递增子序列的长度。
- 第一层for循环遍历每个数字i，第二层for循环遍历从0到i - 1的每个数字j。
- 若nums[i] > nums[j]，则以nums[i]为结尾的最长递增子序列的长度 = max(以nums[j]为结尾的最长递增子序列的长度 + 1, dp[i])。
- 初始化：因为每个数字的最长递增子序列的长度最小为1，所以dp[i] = 1。
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
let dp = Array(nums.length).fill(1);
let res = 1;
for(let i = 1; i < nums.length; i++){
for(let j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
};
98 乘积最大子数组
- 动态规划
- 由于在数组中有负数，因此这里设置两个dp数组。
- dp_max[i]：以nums[i]为结尾的子数组的最大乘积，dp_min[i]：以nums[i]为结尾的子数组的最小乘积。
- dp_max[i] = max(nums[i] * 以nums[i - 1]为结尾的子数组的最大乘积, nums[i] * 以nums[i - 1]为结尾的子数组的最小乘积, nums[i])。
- dp_min[i] = min(nums[i] * 以nums[i - 1]为结尾的子数组的最大乘积, nums[i] * 以nums[i - 1]为结尾的子数组的最小乘积, nums[i])。
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function(nums) {
let dp_max = Array(nums.length).fill(0);
let dp_min = Array(nums.length).fill(0);
let res = nums[0];
dp_max[0] = nums[0], dp_min[0] = nums[0];
for(let i = 1; i < nums.length; i++){
dp_max[i] = Math.max(Math.max(nums[i] * dp_max[i - 1], nums[i] * dp_min[i - 1]), nums[i]);
dp_min[i] = Math.min(Math.min(nums[i] * dp_max[i - 1], nums[i] * dp_min[i - 1]), nums[i]);
res = Math.max(res, dp_max[i]);
}
return res;
};
99 分割等和子集
- 动态规划
- 0 / 1背包
- dp[j]：容量为j的背包最大价值为dp[j]。
- target为nums的总和，若使用nums中的物品(数字 = 价值)能把容量为target / 2的背包装满，价值为target / 2，则能够分割等和子集。
- 根据题意，若target为奇数，则不能够分割等和子集。
- 第一层for循环遍历物品，第二层for循环遍历背包容量。
- dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])。
/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function(nums) {
let target = nums.reduce((sums, item) => sums + item, 0);
if(target % 2 == 1){
return false;
}else{
target = Math.floor(target / 2);
}
let dp = Array(target + 1).fill(0);
for(let i = 0; i < nums.length; i++){
for(let j = target; j >= nums[i]; j--){
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[target] == target? true: false;
};
100 最长有效括号
- 动态规划
- dp[i]：以s[i]为结尾的最长有效子串的长度。
- 初始化：dp[i] = 0。
- (1) 若s[i] = “(”：dp[i] = 0。
- (2) 若s[i] = “)”：
① s[i - 1] = “(”：例如…( )，s[i - 1]和s[i]为有效括号，因此dp[i] = dp[i - 2] + 2。
② s[i - 1] = “)”：例如…( (…) )，此时判断s[i - dp[i - 1] - 1]的括号方向，若为"("，则与s[i]为有效括号，因此dp[i] = dp[i - 1] + 2 + 以s[i - dp[i - 1] - 2]为结尾的有效字串的长度。 - … ) ( ( … ) )
- i - dp[i - 1] - 2 i - dp[i - 1] - 1 i - dp[i - 1] … i - 1 i
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let dp = Array(s.length).fill(0);
let res = 0;
for(let i = 1; i < s.length; i++){
if(s[i] == "("){
dp[i] = 0;
}else if(s[i] == ")"){
if(s[i - 1] == "("){
if(i - 2 >= 0){
dp[i] = dp[i - 2] + 2;
}else{
dp[i] = 2;
}
}else if(s[i - 1] == ")" && s[i - dp[i - 1] - 1] == "("){
if(i - dp[i - 1] - 2 >= 0){
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
}else{
dp[i] = dp[i - 1] + 2;
}
}
}
res = Math.max(res, dp[i]);
}
return res;
};
原文地址：https://blog.csdn.net/weixin_45980065/article/details/143747413
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！