目录1.为运算表达式设计优先级2.作为子字符串出现在单词中的字符串数目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*67-82∗3−4∗5∗67−8为例2 ∗ 3 − 4 2*3-42∗3−4与5 ∗ 6 7 − 8 5*67-85∗67−8这两个子表达式结果相乘的可能性需要先计算出2 ∗ 3 − 4 2*3-42∗3−4的情况5 ∗ 6 7 − 8 5*67-85∗67−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[k2][r]} \space kl,l2,l4,...dp[l][r]∑dp[l][k]∗dp[k2][r]kl,l2,l4,...classSolution{staticintADD-1;staticintSUB-2;staticintMUL-3;publicListIntegerdiffWaysToCompute(Stringexpression){//以某个运算符作为最后的运算符进行计算ListIntegeropsnewArrayList();intnexpression.length();for(inti0;in;){if(!Character.isDigit(expression.charAt(i))){charcexpression.charAt(i);if(c){ops.add(ADD);}elseif(c-){ops.add(SUB);}else{ops.add(MUL);}i;}else{intnum0;while(inCharacter.isDigit(expression.charAt(i))){numnum*10expression.charAt(i)-0;i;}ops.add(num);}}ListInteger[][]dpnewList[n][n];for(inti0;iops.size();i){for(intj0;jops.size();j){dp[i][j]newArrayListInteger();}}for(inti0;iops.size();i2){dp[i][i].add(ops.get(i));}//i表示表达式长度//j表示表达式起始位置//求解时依次统计长度为3,5,7,9,...的所有表达式计算结果//dp[l][r]表示起始l终止r长度的表达式有多少种结果for(inti3;iops.size();i2){for(intj0;jiops.size();j2){//确定lrintlj;intrji-1;//k从l移动到rfor(intkl1;kr;k2){ListIntegerleftdp[l][k-1];ListIntegerrightdp[k1][r];for(intnum1:left){for(intnum2:right){if(ops.get(k)ADD){dp[l][r].add(num1num2);}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){intcount0;for(inti0;ipatterns.length;i){if(kmp(word,patterns[i])!-1){count;}}returncount;}privateintkmp(Strings,Stringp){intns.length(),mp.length();//生成模式串的next数组int[]nextnewint[m];next[0]-1;intinext[0];intj0;//生成next数组while(jm-1){//前缀串匹配上时一次就能搞定if(i0||p.charAt(i)p.charAt(j)){i;j;if(p.charAt(i)!p.charAt(j)){next[j]i;}else{next[j]next[i];}//未匹配上时循环判断}else{inext[i];}}//匹配i0;j0;//匹配s和pwhile(injm){if(j0||s.charAt(i)p.charAt(j)){i;j;}else{jnext[j];}}returnjm?i-j:-1;}}时间复杂度O ( n ∗ m ) O(n*m)O(n∗m)n是数组长度m是partterns中最长字符串长度空间复杂度O ( m ) O(m)O(m)
