表達式得到期望結果的組成種數問題
表達式得到期望結果的組成種數問題
作者：Grey
原文地址：
題目描述
給定一個只由 0(假)、1(真)、&(邏輯與)、|(邏輯或)、^(異或)五種字元組成的字元串 exp，再給定一個布爾值 desired。返回 exp 能有多少種組合方式，可以達到 desired 的結果。
例如：
exp =”1^0|0|1″，desired = false 只有 1^((0|0)|1) 和 1^(0|(0|1)) 的組合可以得到 false，返回 2；
exp =”1″，desired = false，無組合可以得到 false，返回0。
題目鏈接見：牛客-表達式得到期望結果的組成種數
暴力解法
首先，我們可以做一次初步過濾，初步判斷下 exp 的合法性，程式碼和注釋如下：
// 初步篩選一下exp串的合法性
public static boolean errorFormat(char[] exp, int n) {
if ((n & 1) == 0) {
// 表達式不能為偶數個長度
return true;
}
for (int i = 0; i < n; i += 2) {
if (exp[i] != '1' && exp[i] != '0') {
// 0,2,4,8...n-1位置上一定只能是 1 或者 0
return true;
}
}
for (int i = 1; i < n; i += 2) {
if (exp[i] != '|' && exp[i] != '^' && exp[i] != '&') {
return true;
}
}
return false;
}
定義遞歸函數
int p(char[] exp, int L, int R, boolean desired)
遞歸含義表示：exp 這個字元串，從 L 到 R 區間內，可以得到 desired 結果的組合數量是多少。
首先考慮 base case，即：只有一個字元的時候，此時 L == R，
有如下三種情況：
if (L == R) {
// 只有一個字元的時候，
if (desired && exp[L] == '1') {
return 1;
} else if (!desired && exp[L] == '0') {
return 1;
} else {
return 0;
}
}
接下來是普遍情況，分別枚舉每個操作符可能在的位置的左右兩側的組合數量，然後做乘積即可，程式碼如下
for (int i = L + 1; i < R; i++) {
if (exp[i] == '&') {
if (desired) {
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true);
} else {
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true);
}
} else if (exp[i] == '|') {
if (desired) {
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true);
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true);
} else {
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false);
}
} else {
// exp[i] == '^'
if (desired) {
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true);
} else {
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true);
}
}
}
暴力解法的完整程式碼如下:
public static int getDesiredNum(String exp, boolean desired) {
char[] str = exp.toCharArray();
int N = str.length;
if (errorFormat(str, N)) {
return 0;
}
return p(str, 0, N - 1, desired);
}
// 初步篩選一下exp串的合法性
public static boolean errorFormat(char[] exp, int n) {
if ((n & 1) == 0) {
// 表達式不能為偶數個長度
return true;
}
for (int i = 0; i < n; i += 2) {
if (exp[i] != '1' && exp[i] != '0') {
// 0,2,4,8...n-1位置上一定只能是 1 或者 0
return true;
}
}
for (int i = 1; i < n; i += 2) {
if (exp[i] != '|' && exp[i] != '^' && exp[i] != '&') {
return true;
}
}
return false;
}
public static int p(char[] exp, int L, int R, boolean desired) {
if (L == R) {
if (desired && exp[L] == '1') {
return 1;
} else if (!desired && exp[L] == '0') {
return 1;
} else {
return 0;
}
}
int res = 0;
for (int i = L + 1; i < R; i++) {
if (exp[i] == '&') {
if (desired) {
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true);
} else {
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true);
}
} else if (exp[i] == '|') {
if (desired) {
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true);
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true);
} else {
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false);
}
} else {
// exp[i] == '^'
if (desired) {
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, true);
} else {
res += p(exp, L, i - 1, false) * p(exp, i + 1, R, false);
res += p(exp, L, i - 1, true) * p(exp, i + 1, R, true);
}
}
}
return res;
}
本題中，使用暴力遞歸解法已經可以 AC。
動態規劃解法
上述暴力遞歸方法中，有三個可變參數 L ， R 和 desired，我們可以定義兩個二維數組
int[][] tMap = new int[N][N];
int[][] fMap = new int[N][N];
其中
tMap[i][j]表示 i 到 j 能組成 true 的數量是多少,即暴力遞歸中的p(exp,i,j,true)；
fMap[i][j]表示 i 到 j 能組成 false 的數量是多少,即暴力遞歸中的p(exp,i,j,false)；
這個二維數組的對角線下半區無用。
tMap[i][j] 和 fMap[i][j] 的轉移方程可以根據暴力遞歸方法來實現，完整程式碼如下：
public static int getDesiredNum(String exp, boolean desired) {
char[] str = exp.toCharArray();
int N = str.length;
if (errorFormat(str, N)) {
return 0;
}
//tMap[i][j] 表示i到j能組成true的數量是多少，所以對角線下半區無用
int[][] tMap = new int[N][N];
//fMap[i][j] 表示i到j能組成false的數量是多少，所以對角線下半區無用
int[][] fMap = new int[N][N];
for (int i = 0; i < N; i += 2) {
// 忽視符號位
tMap[i][i] = str[i] == '1' ? 1 : 0;
fMap[i][i] = str[i] == '0' ? 1 : 0;
}
for (int L = N - 3; L >= 0; L -= 2) {
for (int R = L + 2; R < N; R += 2) {
for (int i = L + 1; i < R; i += 2) {
if (str[i] == '&') {
tMap[L][R] += tMap[L][i - 1] * tMap[i + 1][R];
fMap[L][R] += tMap[L][i - 1] * fMap[i + 1][R];
fMap[L][R] += fMap[L][i - 1] * fMap[i + 1][R];
fMap[L][R] += fMap[L][i - 1] * tMap[i + 1][R];
} else if (str[i] == '|') {
tMap[L][R] += tMap[L][i - 1] * fMap[i + 1][R];
tMap[L][R] += tMap[L][i - 1] * tMap[i + 1][R];
tMap[L][R] += fMap[L][i - 1] * tMap[i + 1][R];
fMap[L][R] += fMap[L][i - 1] * fMap[i + 1][R];
} else {
tMap[L][R] += tMap[L][i - 1] * fMap[i + 1][R];
tMap[L][R] += fMap[L][i - 1] * tMap[i + 1][R];
fMap[L][R] += fMap[L][i - 1] * fMap[i + 1][R];
fMap[L][R] += tMap[L][i - 1] * tMap[i + 1][R];
}
}
}
}
return desired ? tMap[0][N - 1] : fMap[0][N - 1];
}
public static boolean errorFormat(char[] exp, int n) {
if ((n & 1) == 0) {
// 表達式不能為偶數個長度
return true;
}
for (int i = 0; i < n; i += 2) {
if (exp[i] != '1' && exp[i] != '0') {
// 0,2,4,8...n-1位置上一定只能是 1 或者 0
return true;
}
}
for (int i = 1; i < n; i += 2) {
if (exp[i] != '|' && exp[i] != '^' && exp[i] != '&') {
return true;
}
}
return false;
}
