面試題 08.14. 布爾運算 - 力扣（LeetCode）

Solution

這題的思路比較直接，就是枚舉最后一個進行計算的運算符，但是在實現過程中需要注意，定義范式f(l,r)表示l到r范圍，l和r必須為數字，l+1,r-1為運算符，返回值是一個二元組，包含結果為0的方案數和結果為1的方案數。

#include<iostream>
#include<vector>
using namespace std;class Solution {
public://首先知道偶數位上一定是0或者1，奇數位上一定是運算符//每次去枚舉最后一個進行計算的運算符int countEval(string s, int result) {int n = s.length();int dp[45][45][2];for (int i = 0; i < 45; ++i) {for (int j = 0; j < 45; ++j) {dp[i][j][0] = -1;}}vector<int>ans = f1(s, 0, n - 1, dp);return ans[result];}//規定一個范式，f函數中的區間[l,r]一定要保證l為數字，r為數字,l+1和r-1為運算符vector<int> f1(string s, int l, int r, int dp[45][45][2]) {if (dp[l][r][0] != -1) {return { dp[l][r][0],dp[l][r][1] };}if (l > r) return { 0,0 };if (l == r) {int ans0 = (s[l] == '1') ? 0 : 1;int ans1 = (s[l] == '1') ? 1 : 0;return { ans0,ans1 };}int res0 = 0, res1 = 0;//枚舉最后一個進行計算的運算符的位置for (int m = l + 1; m <= r - 1; m += 2) {vector<int>ans_left = f1(s, l, m - 1, dp);vector<int>ans_right = f1(s, m + 1, r, dp);int ans0, ans1;if (s[m] == '|') {ans0 = ans_left[0] * ans_right[0];ans1 = ans_left[0] * ans_right[1];ans1 += ans_left[1] * ans_right[0];ans1 += ans_left[1] * ans_right[1];}else if (s[m] == '&') {ans0 = ans_left[0] * ans_right[0];ans0 += ans_left[0] * ans_right[1];ans0 += ans_left[1] * ans_right[0];ans1 = ans_left[1] * ans_right[1];}else {ans0 = ans_left[0] * ans_right[0];ans0 += ans_left[1] * ans_right[1];ans1 = ans_left[0] * ans_right[1];ans1 += ans_left[1] * ans_right[0];}res0 += ans0;res1 += ans1;}dp[l][r][0] = res0, dp[l][r][1] = res1;return { res0,res1 };}
};int main() {return 0;
}