本文主要是介绍面试题 08.14. 布尔运算,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
链接:. - 力扣(LeetCode)
题解:dp[i][j][0/1] 表示,从下标i到下标j之间,满足0/1的情况是多少
class Solution {
public:int countEval(string s, int result) {int size = s.size();if (size <= 0) {return 0;}//std::vector<int> tmp(2, 0);//std::vector<std::vector<int>> tmp2(size, tmp);//std::vector<std::vector<std::vector<int>>> dp(size, tmp2);vector<vector<vector<int>>> dp(size, vector<vector<int>>(size, vector<int>(2, 0)));for (int i = 0; i < size; i += 2) {dp[i][i][s[i]-'0'] = 1;//dp[i][i][0] = (s[i] - '0' == 0) ? 1 : 0;//dp[i][i][1] = (s[i] - '0' == 1) ? 1 : 0;}for (int len = 3; len <= size; len += 2) {for (int i = 0; i + len - 1 < size; i += 2) {int j = i + len - 1;for (int k = i + 1; k <= j-1; k += 2) {cout << s[k] << endl;if (s[k] == '&') {dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][0];dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][1];} else if (s[k] == '|') {dp[i][j][1] += dp[i][k-1][1] * dp[k+1][j][0] + dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][1];dp[i][j][0] += dp[i][k-1][0] * dp[k+1][j][0];} else {dp[i][j][0] += dp[i][k-1][1] * dp[k+1][j][1] + dp[i][k-1][0] * dp[k+1][j][0];dp[i][j][1] += dp[i][k-1][0] * dp[k+1][j][1] + dp[i][k-1][1] * dp[k+1][j][0]; }}}}return dp[0][size-1][result];}
};
这篇关于面试题 08.14. 布尔运算的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!