成都网站专业制作,辽宁省建设厅网站升级何时结束,自助发外链网站,网站优点介绍【单词拆分】
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以重复使用。
思路#xff1a;
首先#xff0c;我…【单词拆分】
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
思路
首先我们依次考虑s的前i个字母能否被分割直到in
对一个确定的i我们尝试在前i个字母中进行分割枚举每一个分割点如果分割点前面的部分能分割肯定已经被计算过直接查表即可且分割点后的部分存在于 wordDict中那么当前子串就是可分割的记录到表中
最后检查dp[n]即可。
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {int n s.size();// dpvectorbool dp(n 1, false);dp[0] true;//递推for (int i 1; i n; i) {for (int j 0; j i; j) {//bool flagfalse;// s[0]到s[j-1]能分割s[j]到s[i-1]if (dp[j] (find(wordDict.begin(),wordDict.end(),s.substr(j, i - j)) ! wordDict.end())) {dp[i] true;break;}}}return dp[n];}
};
【最长递增子序列】
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
思路
依次考虑前i个元素计算以第i个元素结尾的递增子序列长度
对第i个元素我们检查它前面的所有元素并试着把它接在该元素结尾的子序列后面如果还能满足递增则记录接上后的子序列长度
随时记录当前找到的最大长度。
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();vectorint dp(n, 1);for (int i 0; i n; i) {int curMax 1;for (int j 0; j i; j) {if (nums[j] nums[i])curMax max(curMax, dp[j] 1);}dp[i]curMax;}return *max_element(dp.begin(),dp.end());}
};
【乘积最大子数组】
给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
思路
本题重点在于会出现负数想让一个包含负数的数组乘积最大要么让这个负数乘绝对值最大的负数前缀乘积实际值最小要么什么也不干如果前缀只有正数乘正数要么不变要么变小直接不考虑
再考虑正数情况想让一个包含该数的数组乘积最大要么让它乘上最大的正的前缀乘积要么什么也不干前缀积只有负数时越乘越小
如果遇到0包含它的子数组乘积必为零我们可以留到最后去判断
以上逻辑看起来很复杂要判断当前元素和0的关系最大的前缀积最小的前缀积和零的关系特殊值0的处理等等但实际上不管怎么样我们需要的其实就是到当前元素为止的最大和最小乘积而我们做的计算也只有当前元素x最大前缀积当前元素x最小前缀积当前元素不变三种情况所以只要计算这三种结果并取其中的最大值和最小值就可。
class Solution {
public:int maxProduct(vectorint nums) {int ans INT_MIN;int n nums.size();int dpMax 1;int dpMin 1;for (int i 0; i n; i) {int tempdpMax;dpMax max(max(nums[i], nums[i] * dpMax), nums[i] * dpMin);dpMin min(min(nums[i], nums[i] * temp), nums[i] * dpMin);ans max(ans, dpMax);}return ans;}
};
【分割等和自己】
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
思路
把题目翻译一下其实就是能不能找出一个子数组它的和是原数组总和的一半这样就变成0-1背包了
首先算一下原数组总和如果是奇数肯定不行如果是偶数那么它的一半就是我们要找的子数组的和aka背包的容量而我们要记录的是考虑前i个物品时能否恰好把容量为j的背包装满
依次增加当前考虑的物品数量i倒序遍历背包容量j首先判断当前物品i如果它的重量正好等于当前容量j那么可以装满如果前i-1个物品已经能把j容量装满那么增加一个物品没有影响肯定也可以装满否则考虑前i-1个物品能否装满容量j-当前重量的背包如果能的话加上当前物品就正好是前i个物品装满j容量的背包
最后考虑到每一轮循环我们需要的信息其实都只有第i-1行进行空间优化用一维数组来滚动即可。
class Solution {
public:bool canPartition(vectorint nums) {int n nums.size();sort(nums.begin(), nums.end());int sum0;for(int i0; in; i){sum nums[i];}if(sum%2 || sumnums[n-1]) return false;int target sum/2;vectorbool dp(target1);dp[0]true;for(int i0; in; i){for(int jtarget; jnums[i]; j--){dp[j] dp[j] || dp[j-nums[i]];}}return dp[target];}
};
【最长有效括号】
给你一个只包含 ( 和 ) 的字符串找出最长有效格式正确且连续括号子串的长度。
思路
一开始疯狂条件判断把自己都判晕了后来才意识到本题的核心逻辑非常简单归纳真有意思。
遍历串中的每个字符我们记录以该字符结尾的最长有效子串长度
当我们拿到一个新的字符i有两种情况左括号结尾的必无效填0直接continue右括号结尾时我们要做的是看看这个右括号能不能找到对应的左括号把以字符i-1结尾的有效串包在里面如果找到了那么这个有效串的长度就增加了2还没完我们找到了最左边的括号以后还要看看它的前一个字符能提供多长的有效串拼接起来此时才真正拿到了以字符i结尾的最长的有效串
对当前字符是右括号且前一个字母是左括号的情况我们还可以进行代码优化直接用这两个字符组成的合法括号对拼接上前面的有效串即可本质是用dp[i - 1]为0的信息简化了表达式。
class Solution {
public:int longestValidParentheses(string s) {int n s.size();if (n 0)return 0;vectorint dp(n 1, 0);//dp[0] dp[1] 0;for (int i 2; i n; i) {//左结尾必不合法if (s[i - 1] ()continue;//右结尾时分情况讨论else {//正好是个左凑一对if (s[i - 2] ()dp[i] dp[i - 2] 2;//是个右要去当前元素左边的整个合法串的左边找找有没有配对的配上的话还要再往前接龙else {//配上了if ((i - 2 - dp[i - 1] 0) (s[i - 2 - dp[i - 1]] ())dp[i] dp[i - 1] 2 dp[i - 2 - dp[i - 1]];}}}return *max_element(dp.begin(), dp.end());}
};
