0
表达式得到期望结果的组成种数问题 - Grey Zeng
source link: https://www.cnblogs.com/greyzeng/p/16823219.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
表达式得到期望结果的组成种数问题
作者：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;
}
更多#
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK