力扣爆刷第100天之hot100五连刷86-90

2024-03-20 12:36

本文主要是介绍力扣爆刷第100天之hot100五连刷86-90,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣爆刷第100天之hot100五连刷86-90

文章目录

      • 力扣爆刷第100天之hot100五连刷86-90
      • 一、139. 单词拆分
      • 二、300. 最长递增子序列
      • 三、152. 乘积最大子数组
      • 四、416. 分割等和子集
      • 五、32. 最长有效括号

一、139. 单词拆分

题目链接:https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-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, List<String> 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/?envType=study-plan-v2&envId=top-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/?envType=study-plan-v2&envId=top-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/?envType=study-plan-v2&envId=top-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[sum+1];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/?envType=study-plan-v2&envId=top-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-j+1;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;}
}

这篇关于力扣爆刷第100天之hot100五连刷86-90的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/829468

相关文章

90、k8s之secret+configMap

一、secret配置管理 配置管理: 加密配置:保存密码,token,其他敏感信息的k8s资源 应用配置:我们需要定制化的给应用进行配置,我们需要把定制好的配置文件同步到pod当中容器 1.1、加密配置: secret: [root@master01 ~]# kubectl get secrets ##查看加密配置[root@master01 ~]# kubectl get se

Android 10.0 mtk平板camera2横屏预览旋转90度横屏拍照图片旋转90度功能实现

1.前言 在10.0的系统rom定制化开发中,在进行一些平板等默认横屏的设备开发的过程中,需要在进入camera2的 时候,默认预览图像也是需要横屏显示的,在上一篇已经实现了横屏预览功能,然后发现横屏预览后,拍照保存的图片 依然是竖屏的,所以说同样需要将图片也保存为横屏图标了,所以就需要看下mtk的camera2的相关横屏保存图片功能, 如何实现实现横屏保存图片功能 如图所示: 2.mtk

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目,分别是:【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height