特色的南昌网站制作,怎样免费做游戏代理,wordpress 不检查更新,网站的页脚什么做1. 题目
给定一个布尔表达式和一个期望的布尔结果 result#xff0c;布尔表达式由 0 (false)、1 (true)、 (AND)、 | (OR) 和 ^ (XOR) 符号组成。 实现一个函数#xff0c;算出有几种可使该表达式得出 result 值的括号方法。
示例 1:
输入: s 1^0|0|1, r…1. 题目
给定一个布尔表达式和一个期望的布尔结果 result布尔表达式由 0 (false)、1 (true)、 (AND)、 | (OR) 和 ^ (XOR) 符号组成。 实现一个函数算出有几种可使该表达式得出 result 值的括号方法。
示例 1:
输入: s 1^0|0|1, result 0
输出: 2
解释: 两种可能的括号方法是
1^(0|(0|1))
1^((0|0)|1)示例 2:
输入: s 0001^1|0, result 1
输出: 10提示
运算符的数量不超过 19 个来源力扣LeetCode 链接https://leetcode-cn.com/problems/boolean-evaluation-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 区间DP解题
dp[i][j] 表示 区间[i,j]内运算值为 0 or 1 的方案数初始化每个数字处dp?[i][i]1, if s[i]?然后按长度len递增求解dp[i][ilen]dp[i][ilen]的求解可以根据其内部左右两侧的方案乘积得出所以分成两部分dp[i,j],dp[j2][ilen],遍历所有的jj1处为运算符然后根据运算符的三种可能讨论0,1的结果累加即可
class Solution {
public:int countEval(string s, int result) {if(s)return 0;int i, j, n s.size(), len;vectorvectorint dp0(n,vectorint(n,0));vectorvectorint dp1(n,vectorint(n,0));//dp[i][j] 表示 区间[i,j]内运算值为 的方案数for(i 0; i n; i2){if(s[i]1)dp1[i][i] 1;elsedp0[i][i] 1;}for(len 2; len n-1; len 2){ //按长度递增for(i 0; i n-len; i 2){ //左端点ifor(j i; j ilen-2; j2){ //中间端点jif(s[j1]){dp1[i][ilen] dp1[i][j]*dp1[j2][ilen];dp0[i][ilen] dp0[i][j]*dp0[j2][ilen]dp1[i][j]*dp0[j2][ilen]dp0[i][j]*dp1[j2][ilen];}else if(s[j1]|){dp1[i][ilen] dp1[i][j]*dp1[j2][ilen]dp1[i][j]*dp0[j2][ilen]dp0[i][j]*dp1[j2][ilen];dp0[i][ilen] dp0[i][j]*dp0[j2][ilen];}else//^{dp1[i][ilen] dp1[i][j]*dp0[j2][ilen]dp0[i][j]*dp1[j2][ilen];dp0[i][ilen] dp0[i][j]*dp0[j2][ilen]dp1[i][j]*dp1[j2][ilen];}}}}if(result)return dp1[0][n-1];return dp0[0][n-1];}
};8 ms 7 MB
