表达式得到期望结果的组成种数问题
作者：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;
}