程序员必备的算法（程序员面试金典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
提示：运算符的数量不超过 19 个
解题思路分析1、动态规划；时间复杂度O(n^3)，空间复杂度O(n^2)
func countEval(s string, result int) int {
n := len(s)
// dp[i][j][0/1] => s[i:j 1]结果为0/1的方法数
dp := make([][][2]int, n)
for i := 0; i < n; i {
dp[i] = make([][2]int, n)
}
for i := n - 1; i >= 0; i = i - 2 {
for j := i; j < n; j = j 2 {
if i == j {
if s[i] == 0 {
dp[i][j][0]
} else {
dp[i][j][1]
}
continue
}
for k := i 1; k < j; k = k 2 { // 枚举操作符
for a := 0; a <= 1; a {
for b := 0; b <= 1; b {
if getValue(a, b, s[k]) == 0 {
dp[i][j][0] = dp[i][j][0]
dp[i][k-1][a]*dp[k 1][j][b]
} else {
dp[i][j][1] = dp[i][j][01]
dp[i][k-1][a]*dp[k 1][j][b]
}
}
}
}
}
}
return dp[0][n-1][result]
}
func getValue(a, b int, op byte) int {
if op == & {
return a & b
} else if op == | {
return a | b
}
return a ^ b
}
2、动态规划；时间复杂度O(n^3)，空间复杂度O(n^2)
func countEval(s string, result int) int {
n := len(s)
// dp[i][j][0/1] => s[i:j 1]结果为0/1的方法数
dp := make([][][2]int, n)
for i := 0; i < n; i {
dp[i] = make([][2]int, n)
}
for i := n - 1; i >= 0; i = i - 2 {
for j := i; j < n; j = j 2 {
if i == j {
dp[i][j][s[i]-0]
continue
}
for k := i 1; k < j; k = k 2 { // 枚举操作符
for a := 0; a <= 1; a {
for b := 0; b <= 1; b {
temp := getValue(a, b, s[k])
dp[i][j][temp] = dp[i][j][temp]
dp[i][k-1][a]*dp[k 1][j][b]
}
}
}
}
}
return dp[0][n-1][result]
}
func getValue(a, b int, op byte) int {
if op == & {
return a & b
} else if op == | {
return a | b
}
return a ^ b
}
3、动态规划；时间复杂度O(n^3)，空间复杂度O(n^2)
func countEval(s string, result int) int {
n := len(s)
// dp[i][j][0/1] => s[i:j 1]结果为0/1的方法数
dp := make([][][2]int, n)
for i := 0; i < n; i {
dp[i] = make([][2]int, n)
if i%2 == 0 {
dp[i][i][int(s[i]-0)]
}
}
for length := 2; length <= n; length = length 2 { // 枚举长度
for i := 0; i <= n-length; i = i 2 { // 枚举起点
j := i length // 确定终点
for k := i 1; k < j; k = k 2 { // 枚举操作符
for a := 0; a <= 1; a {
for b := 0; b <= 1; b {
temp := getValue(a, b, s[k])
dp[i][j][temp] = dp[i][j][temp]
dp[i][k-1][a]*dp[k 1][j][b]
}
}
}
}
}
return dp[0][n-1][result]
}
func getValue(a, b int, op byte) int {
if op == & {
return a & b
} else if op == | {
return a | b
}
return a ^ b
}
Medium题目，采用动态规划
,免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。
