当前位置：首页 > news >正文

LeetCode刷题 day25

news 2026/6/30 13:26:05

1.为运算表达式设计优先级

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以按任意顺序返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 104 。

示例 1：
输入：expression = “2-1-1”
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2

示例 2：
输入：expression = “23-45”
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10

思路
这题可以采用动态规划的思想，不过与平常的动态规划不同，此题的思路是按长度动态规划，先计算所有包含一个运算符的表达式结果，再计算包含两个表达式的结果，依此类推，直到包含所有表达式的结果都计算出来。
以2 ∗ 3 − 4 ∗ 5 ∗ 6 + 7 − 8 2*3-4*5*6+7-82∗3−4∗5∗6+7−8为例：
2 ∗ 3 − 4 2*3-42∗3−4与5 ∗ 6 + 7 − 8 5*6+7-85∗6+7−8这两个子表达式结果相乘的可能性，需要先计算出2 ∗ 3 − 4 2*3-42∗3−4的情况，5 ∗ 6 + 7 − 8 5*6+7-85∗6+7−8的情况，再相乘，即为所有的情况。
因此转移方程为:
d p [ l ] [ r ] = ∑ d p [ l ] [ k ] ∗ d p [ k + 2 ] [ r ] k = l , l + 2 , l + 4 , . . . dp[l][r] = ∑{dp[l][k]*dp[k+2][r]} \space k=l,l+2,l+4,...dp[l][r]=∑dp[l][k]∗dp[k+2][r]k=l,l+2,l+4,...

classSolution{staticintADD=-1;staticintSUB=-2;staticintMUL=-3;publicList<Integer>diffWaysToCompute(Stringexpression){//以某个运算符作为最后的运算符进行计算List<Integer>ops=newArrayList<>();intn=expression.length();for(inti=0;i<n;){if(!Character.isDigit(expression.charAt(i))){charc=expression.charAt(i);if(c=='+'){ops.add(ADD);}elseif(c=='-'){ops.add(SUB);}else{ops.add(MUL);}i++;}else{intnum=0;while(i<n&&Character.isDigit(expression.charAt(i))){num=num*10+expression.charAt(i)-'0';i++;}ops.add(num);}}List<Integer>[][]dp=newList[n][n];for(inti=0;i<ops.size();i++){for(intj=0;j<ops.size();j++){dp[i][j]=newArrayList<Integer>();}}for(inti=0;i<ops.size();i+=2){dp[i][i].add(ops.get(i));}//i表示表达式长度//j表示表达式起始位置//求解时，依次统计长度为3,5,7,9,...的所有表达式计算结果//dp[l][r]表示起始l，终止r长度的表达式有多少种结果for(inti=3;i<=ops.size();i+=2){for(intj=0;j+i<=ops.size();j+=2){//确定l，rintl=j;intr=j+i-1;//k从l移动到rfor(intk=l+1;k<r;k+=2){List<Integer>left=dp[l][k-1];List<Integer>right=dp[k+1][r];for(intnum1:left){for(intnum2:right){if(ops.get(k)==ADD){dp[l][r].add(num1+num2);}elseif(ops.get(k)==SUB){dp[l][r].add(num1-num2);}else{dp[l][r].add(num1*num2);}}}}}}returndp[0][ops.size()-1];}}

时间复杂度：O ( 2 n ) O(2^n)O(2n)
空间复杂度：O ( 2 n ) O(2^n)O(2n)

2.作为子字符串出现在单词中的字符串数目

给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。

子字符串是字符串中的一个连续字符序列。

示例 1：
输入：patterns = [“a”,“abc”,“bc”,“d”], word = “abc”
输出：3
解释：

“a” 是 “abc” 的子字符串。
“abc” 是 “abc” 的子字符串。
“bc” 是 “abc” 的子字符串。
“d” 不是 “abc” 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。

示例 2：
输入：patterns = [“a”,“b”,“c”], word = “aaaaabbbbb”
输出：2
解释：

“a” 是 “aaaaabbbbb” 的子字符串。
“b” 是 “aaaaabbbbb” 的子字符串。
“c” 不是 “aaaaabbbbb” 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。

示例 3：
输入：patterns = [“a”,“a”,“a”], word = “ab”
输出：3
解释：patterns 中的每个字符串都作为子字符串出现在 word “ab” 中。

思路
只要一次判断每个patterns中的字符串是否是word的子串即可，采用KMP算法进行判断，不使用自带函数

classSolution{publicintnumOfStrings(String[]patterns,Stringword){intcount=0;for(inti=0;i<patterns.length;i++){if(kmp(word,patterns[i])!=-1){count++;}}returncount;}privateintkmp(Strings,Stringp){intn=s.length(),m=p.length();//生成模式串的next数组int[]next=newint[m];next[0]=-1;inti=next[0];intj=0;//生成next数组while(j<m-1){//前缀串匹配上时，一次就能搞定if(i<0||p.charAt(i)==p.charAt(j)){i++;j++;if(p.charAt(i)!=p.charAt(j)){next[j]=i;}else{next[j]=next[i];}//未匹配上时，循环判断}else{i=next[i];}}//匹配i=0;j=0;//匹配s和pwhile(i<n&&j<m){if(j<0||s.charAt(i)==p.charAt(j)){i++;j++;}else{j=next[j];}}returnj==m?i-j:-1;}}