class Solution {
public:
int countEval(string s, int result) {
}
};
面试题 08.14. 布尔运算
给定一个布尔表达式和一个期望的布尔结果 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 = "0&0&0&1^1|0", result = 1 输出: 10
提示：
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-30 21:31:00
func countEval(s string, result int) int {
var dp [40][40][2]int
l := len(s)
for i := 0; i < l; i +=2{
dp[i][i][int(s[i]-'0')] = 1
}
// printDP(&dp)
// 区间宽度
for i := 2; i < l + 1; i += 1{
//区间起点
for j := 0; j < l-i + 1; j += 1{
// 区间运算符号的位置
for k := j+1; k < i + j; k +=1 {
getAns(s, j, k, i+j, &dp)
}
}
}
return dp[0][len(s)-1][result]
}
func getAns(s string, i, mid, j int, dp *[40][40][2]int){
switch s[mid]{
case '&':
dp[i][j][0] += dp[i][mid-1][0] * dp[mid+1][j][0]
dp[i][j][0] += dp[i][mid-1][1] * dp[mid+1][j][0]
dp[i][j][0] += dp[i][mid-1][0] * dp[mid+1][j][1]
dp[i][j][1] += dp[i][mid-1][1] * dp[mid+1][j][1]
case '^':
// 0
dp[i][j][0] += dp[i][mid-1][0] * dp[mid+1][j][0]
dp[i][j][0] += dp[i][mid-1][1] * dp[mid+1][j][1]
// 1
dp[i][j][1] += dp[i][mid-1][1] * dp[mid+1][j][0]
dp[i][j][1] += dp[i][mid-1][0] * dp[mid+1][j][1]
case '|':
dp[i][j][1] += dp[i][mid-1][1] * dp[mid+1][j][0]
dp[i][j][1] += dp[i][mid-1][0] * dp[mid+1][j][1]
dp[i][j][1] += dp[i][mid-1][1] * dp[mid+1][j][1]
dp[i][j][0] += dp[i][mid-1][0] * dp[mid+1][j][0]
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2022-11-30 21:30:45
//dp[i][j][0/1]，表示s[i:j+1]结果为0/1的括号方法种数
func countEval(s string, result int) int {
dp := make([][][2]int, len(s))
for i := 0; i < len(dp); i++ {
dp[i] = make([][2]int, len(s))
}
//dp[0][len-1][result]即为答案，i需要倒序遍历，j正序遍历
for i := len(s) - 1; i >= 0; i -= 2 {
for j := i; j < len(s); j += 2 {
if i == j {
if s[i] == '0' {
dp[i][j][0]++
} else {
dp[i][j][1]++
}
continue
}
/*
操作符s[k]将s[i:j+1]分为s[i:k]和s[k+1:j+1]分为前后两块
遍历各自dp[i][k-1][0/1]和dp[k+1][j][0/1]共四种情况，累计dp[i][j][0/1]的值
*/
for k := i + 1; k < j; k += 2 {
for arg1 := 0; arg1 <= 1; arg1++ {
for arg2 := 0; arg2 <= 1; arg2++ {
if doBoolOp(arg1, arg2, s[k]) == 0 {
dp[i][j][0] += dp[i][k-1][arg1] * dp[k+1][j][arg2]
} else {
dp[i][j][1] += dp[i][k-1][arg1] * dp[k+1][j][arg2]
}
}
}
}
}
}
return dp[0][len(s)-1][result]
}
func doBoolOp(arg1, arg2 int, operator byte) int {
if operator == '&' {
return arg1 & arg2
} else if operator == '|' {
return arg1 | arg2
} else {
return arg1 ^ arg2
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 7.8 MB, 提交时间: 2022-11-30 21:29:28
class Solution {
public:
unordered_map<string, pair<int, int > > dp;
int countEval(string s, int result) {
pair<int, int > ans = helper(s);
//pair<int, int > 中第一个数表示结果中0的出现次数，第二个数表示1的出现次数
if (result == 0)
return ans.first;
else
return ans.second;
}
pair<int, int > helper(string s) {
if (dp.count(s) != 0)
return dp[s];
int ans[2] = { 0 };
int len = s.size();
if (len == 1)
if (s == "1")
ans[1]++;
else
ans[0]++;
else {
for (int i = 1; i < len; i += 2) {
//不断的找分割点，类似求卡特兰数的思想
//递归的获得 分割点前后字符串可以生成多少个括号位置不同的0或者1
pair<int, int > t1 = helper(s.substr(0, i));
pair<int, int > t2 = helper(s.substr(i+1));
switch (s[i]) {
case '&': //分割点为 & ，获得0 有 0&0 ，1&0 ， 0&1 三种情况，交叉相乘后累加这三种情况
ans[0] += t1.first * t2.first + t1.second *t2.first + t2.second*t1.first;
ans[1] += t1.second * t2.second; // 要想获得 1 只有 1&1 这一种情况
break;
case '|':// 同理
ans[0] += t1.first * t2.first;
ans[1] += t1.second * t2.second + t1.first * t2.second + t2.first * t1.second;;
break;
case '^':// 同理
ans[0] += t1.first * t2.first + t1.second * t2.second;
ans[1] += t1.first * t2.second + t2.first * t1.second;
break;
}
}
}
dp[s] = make_pair(ans[0], ans[1]);
return { ans[0] ,ans[1] };
}
};
python3 解法, 执行用时: 84 ms, 内存消耗: 15.7 MB, 提交时间: 2022-11-30 21:27:48
class Solution:
def countEval(self, s: str, result: int) -> int:
operations = {
"&":{
True:[(True,True)],
False:[(True,False),(False,False),(False,True)]
},
"|":{
True:[(True,True),(True,False),(False,True)],
False:[(False,False)]
},
"^":{
True:[(True,False),(False,True)],
False:[(False,False),(True,True)]
}
}
@lru_cache(maxsize=1000000000)
def dfs(s, target):
if len(s)==1:
lp = int(s)
return int(lp == target)
cnt = 0
for i,c in enumerate(s):
if c in operations:
for lta,rta in operations[c][target]:
cnt+=dfs(s[:i], lta) * dfs(s[i+1:], rta)
return cnt
return dfs(s, int(result))
javascript 解法, 执行用时: 68 ms, 内存消耗: 45.2 MB, 提交时间: 2022-11-30 21:26:48
/**
* @param {string} s
* @param {number} result
* @return {number}
*/
/**
* @param {string} s
* @param {number} result
* @return {number}
*/
var countEval = function (s, result) {
let row = s.length;
// 创建一个三维数组，第三维长度为2（第三维可以这样理解，一个区间的result 状态情况，要么为0，要么为1），并初始化为0.
// 比如 row=2 => [ [ [ 0, 0 ], [ 0, 0 ] ], [ [ 0, 0 ], [ 0, 0 ] ] ]
// dp的含义 dp[i][j][result] : i,j 区间的字符串得到状态 result 的方案数目
let dp = Array.from(Array(row), () => { return Array.from(Array(row), () => Array(2).fill(0)) })
for (let i = 0; i < row; i++) { //初始化
if (s[i] == '0') {
dp[i][i][0] = 1 //只有一个字符，得到0的方案数为1 （得到1的方案数为0，前面构建数组的时候，已经填充过了）
} else if (s[i] == '1') {
dp[i][i][1] = 1 //只有一个字符，得到1的方案数为1
}
}
for (let len = 2; len < s.length; len++) { //长度为2 ，开始从左往右扫描（len的长度不断增加，是因为：大区间的结果依赖于小区间的结果，必须从小区间开始计算）
for (let i = 0; i + len < s.length; i += 2) {
let j = i + len; // i，j 区间内判断，j是终点
for (let k = i + 1; k < j; k += 2) { // k 为 i，j 区间的 符号 ，以k为分割点，左边字符区间： [i][k-1] 右边[k+1][j]
if (s[k] == '&') {
//在 分割点是 & 的情况下， 计算状态 。 比如 dp[i][j][0] 只有左右字符状态为： 0 0 和 0 1 和 1 0 这三种情况。 求方法数，用乘法（比如 左边字符串 有2 种方案得状态0，右边有2种方案得到状态1. 那么总字符串得到0的方案是：2*2=4
dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1] + dp[i][k - 1][1] * dp[k + 1][j][0]
dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][1]
} else if (s[k] == '|') {
dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0]
dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][1] + dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1]
} else if (s[k] == '^') {
dp[i][j][0] += dp[i][k - 1][0] * dp[k + 1][j][0] + dp[i][k - 1][1] * dp[k + 1][j][1]
dp[i][j][1] += dp[i][k - 1][1] * dp[k + 1][j][0] + dp[i][k - 1][0] * dp[k + 1][j][1]
}
}
}
}
return dp[0][row - 1][result] // 求整个区间的方案数
};