題目 給定一個布爾表達式和一個期望的布爾結果 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, 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 i { dp[i] = make([][2]int, n) } for i := n - 1; i i = i - 2 { for j := i; j j = j 2 { if i == j { if s[i] == { dp[i][j][0] } else { dp[i][j][1] } continue } for k := i 1; k k = k 2 { // 枚舉操作符 for a := 0; a a { for b := 0; b 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 i { dp[i] = make([][2]int, n) } for i := n - 1; i i = i - 2 { for j := i; j j = j 2 { if i == j { dp[i][j][s[i]-] continue } for k := i 1; k k = k 2 { // 枚舉操作符 for a := 0; a a { for b := 0; b 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 i { dp[i] = make([][2]int, n) if i%2 == 0 { dp[i][i][int(s[i]-)] } } for length := 2; length length = length 2 { // 枚舉長度 for i := 0; i = n-length; i = i 2 { // 枚舉起點 j := i length // 确定終點 for k := i 1; k k = k 2 { // 枚舉操作符 for a := 0; a a { for b := 0; b 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題目，采用動态規劃

　　,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!