网上购物网站开发的背景,金峰辉网站建设,招聘网络推广专员,网站移动端是什么力扣爆刷第100天之hot100五连刷86-90 文章目录 力扣爆刷第100天之hot100五连刷86-90一、139. 单词拆分二、300. 最长递增子序列三、152. 乘积最大子数组四、416. 分割等和子集五、32. 最长有效括号 一、139. 单词拆分
题目链接#xff1a;https://leetcode.cn/problems/word-…力扣爆刷第100天之hot100五连刷86-90 文章目录 力扣爆刷第100天之hot100五连刷86-90一、139. 单词拆分二、300. 最长递增子序列三、152. 乘积最大子数组四、416. 分割等和子集五、32. 最长有效括号 一、139. 单词拆分
题目链接https://leetcode.cn/problems/word-break/description/?envTypestudy-plan-v2envIdtop-100-liked 思路定义dp[i]表示字符串s[0, i]可以被拼接出那么如果要推导出当前s[0,i]可以被拼出只需要s[0, i-word.length]可以被拼出且s[i-word.length] w即可推出此即为递推公式。
class Solution {public boolean wordBreak(String s, ListString wordDict) {boolean[] dp new boolean[s.length() 1];dp[0] true;for(int i 1; i dp.length; i) {for(String word : wordDict) {if(i word.length() || dp[i] || !dp[i-word.length()]) continue;dp[i] isTrue(s, word, i);}}return dp[s.length()];}boolean isTrue(String s, String word, int index) {int i index - word.length(), j 0;while(i index) {if(s.charAt(i) ! word.charAt(j)) return false;i;j;}return true;}
}
二、300. 最长递增子序列
题目链接https://leetcode.cn/problems/longest-increasing-subsequence/description/?envTypestudy-plan-v2envIdtop-100-liked 思路定义dp[i]表示区间[0, i]以nums[i]为结尾的最长递增子序列的长度那么如果nums[i] nums[j]故 dp[i] Math.max(dp[i], dp[j]1);
class Solution {public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length];Arrays.fill(dp, 1);int max 1;for(int i 1; i nums.length; i) {for(int j 0; j i; j) {if(nums[i] nums[j]) {dp[i] Math.max(dp[i], dp[j]1);}}max Math.max(max, dp[i]);}return max;}
}
三、152. 乘积最大子数组
题目链接https://leetcode.cn/problems/maximum-product-subarray/description/?envTypestudy-plan-v2envIdtop-100-liked 思路求最长乘积子数组由于元素有负数存在我们求每一个位置的最大值该最大值的并不一定依赖的是前一个位置的最大值也可能是前一个位置的最小值所以要用两个数组记录分表记录最大和最小值在求最大值的时候dp[i] max(前一个位置的最大值 * 当前元素 当前元素 前一个位置的最小值 * 当前元素)。每一个dp[i]由三种装填推出。
class Solution {public int maxProduct(int[] nums) {int[] dpMax new int[nums.length];int[] dpMin new int[nums.length];dpMax[0] nums[0];dpMin[0] nums[0];int max nums[0];for(int i 1; i nums.length; i) {dpMax[i] Math.max(dpMax[i-1] * nums[i], Math.max(nums[i], dpMin[i-1] * nums[i]));dpMin[i] Math.min(dpMin[i-1] * nums[i], Math.min(nums[i], dpMax[i-1] * nums[i])); }for(int i 1; i nums.length; i) {max Math.max(max, dpMax[i]);}return max;}
}
四、416. 分割等和子集
题目链接https://leetcode.cn/problems/partition-equal-subset-sum/description/?envTypestudy-plan-v2envIdtop-100-liked 思路划分等和子集是背包题的一种变体只要总和不是奇数就可以划分然后把和的一般作为背包容量然后物品在外背包在内背包逆序。
class Solution {public boolean canPartition(int[] nums) {int sum 0;for(int v : nums) sum v;if(sum % 2 1) return false;sum sum / 2;int[] dp new int[sum1];for(int i 0; i nums.length; i) {for(int j sum; j nums[i]; j--) {dp[j] Math.max(dp[j], dp[j-nums[i]] nums[i]);}}return dp[sum] sum;}
}五、32. 最长有效括号
题目链接https://leetcode.cn/problems/longest-valid-parentheses/description/?envTypestudy-plan-v2envIdtop-100-liked 思路使用动态规划做时间超了可以使用栈做。
class Solution {public int longestValidParentheses(String s) {if(s.length() 0) return 0;int[] dp new int[s.length()];int max 0;for(int i 1; i s.length(); i) {for(int j 0; j i; j) {if(isTrue(s, j, i)) {dp[i] i-j1;break;}}max Math.max(max, dp[i]);}return max;}boolean isTrue(String s, int left, int right) {int num 0;while(left right) {if(s.charAt(left) () {num;}else{num--;}if(num 0) return false;}return num 0;}
}使用栈
class Solution {public int longestValidParentheses(String s) {int maxans 0;int[] dp new int[s.length()];for (int i 1; i s.length(); i) {if (s.charAt(i) )) {if (s.charAt(i - 1) () {dp[i] (i 2 ? dp[i - 2] : 0) 2;} else if (i - dp[i - 1] 0 s.charAt(i - dp[i - 1] - 1) () {dp[i] dp[i - 1] ((i - dp[i - 1]) 2 ? dp[i - dp[i - 1] - 2] : 0) 2;}maxans Math.max(maxans, dp[i]);}}return maxans;}
}
