布尔运算
难度:
标签:
题目描述
Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^ (XOR), and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.
Example 1:
Input: s = "1^0|0|1", result = 0 Output: 2 Explanation: Two possible parenthesizing ways are: 1^(0|(0|1)) 1^((0|0)|1)
Example 2:
Input: s = "0&0&0&1^1|0", result = 1 Output: 10
Note:
- There are no more than 19 operators in
s.
代码结果
运行时间: 34 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 使用递归结合Java Stream来解决这个问题。
* 2. 对每个操作符，将表达式分成两部分，递归地计算两部分的不同括号方法数。
* 3. 根据操作符，合并左右部分的结果。
*/
import java.util.stream.IntStream;
public class BooleanExpressionStream {
public int countEval(String s, int result) {
if (s.length() == 1) {
return s.charAt(0) - '0' == result ? 1 : 0;
}
return IntStream.range(0, s.length())
.filter(i -> s.charAt(i) == '&' || s.charAt(i) == '|' || s.charAt(i) == '^')
.mapToObj(i -> new int[]{i, s.charAt(i)})
.flatMapToInt(opInfo -> {
int i = opInfo[0];
char op = (char) opInfo[1];
return IntStream.of(0, 1).flatMap(leftResult ->
IntStream.of(0, 1).map(rightResult -> {
int totalWays = countEval(s.substring(0, i), leftResult) * countEval(s.substring(i + 1), rightResult);
if (op == '&') {
return (leftResult & rightResult) == result ? totalWays : 0;
} else if (op == '|') {
return (leftResult | rightResult) == result ? totalWays : 0;
} else { // op == '^'
return (leftResult ^ rightResult) == result ? totalWays : 0;
}
})
);
})
.sum();
}
public static void main(String[] args) {
BooleanExpressionStream solution = new BooleanExpressionStream();
System.out.println(solution.countEval("1^0|0|1", 0)); // 输出: 2
System.out.println(solution.countEval("0&0&0&1^1|0", 1)); // 输出: 10
}
}
解释
方法:
此题解采用动态规划的方式来解决问题。定义dp[i][j][0]和dp[i][j][1]为布尔表达式从索引i到j计算结果为False和True的方法数。初始化时，如果字符是'0'或'1'，则相应的dp[i][i][0]或dp[i][i][1]设为1。对于表达式中的每个可能的子段，使用变量k遍历所有可能的操作符位置，根据操作符的类型（AND、OR、XOR），更新dp数组。例如，对于AND操作，当两边都为True时结果才为True；对于OR操作，任意一边为True结果即为True；对于XOR操作，两边不同结果才为True。这样从最小的子表达式逐步扩大范围，直至得出整个表达式的结果。
时间复杂度:
O(n^3)
空间复杂度:
O(n^2)
代码细节讲解
🦆
如何确保动态规划数组dp[i][j][0]和dp[i][j][1]正确初始化，特别是对于非'0'和'1'的字符？
▷🦆
在动态规划解法中，变量k表示的操作符位置如何选择以确保所有可能的子表达式都被考虑到？
▷🦆
题解中对于操作符'&'、'|'和'^'的处理逻辑是否考虑了所有可能的操作数组合，如果有遗漏，请指出？
▷