点击刷新
96. Unique Binary Search Trees
https://www.cnblogs.com/grandyang/p/4299608.html
3由dp[1]*dp[1]、dp[0]*dp[2]、dp[2]*dp[0]相加而成
从2开始
class Solution { public: int numTrees(int n) { vector<int> dp(n+1); dp[0] = 1; dp[1] = 1; for(int i = 2;i <= n;i++){ for(int j = 0;j < i;j++){ dp[i] += dp[j] * dp[i-1-j]; } } return dp[n]; } };
也可以从1开始
class Solution { public: int numTrees(int n) { vector<int> dp(n+1,0); dp[0] = 1; for(int i = 1;i <= n;i++){ for(int j = 0;j < i;j++){ dp[i] += dp[j] * dp[i-j-1]; } } return dp[n]; } };
95. Unique Binary Search Trees II
https://www.cnblogs.com/grandyang/p/4301096.html
这个题与96. Unique Binary Search Trees不同，96. Unique Binary Search Trees是求生成的二叉搜索树的个数，这个题是把所有可能找出来。
使用分治的方法做，左半边构成左子树，右半边构成右子树。
因为数字是从小到大排列，自然能形成二叉搜索树。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<TreeNode*> generateTrees(int n) { if(n == 0) return {}; return generateTrees(1,n); } vector<TreeNode*> generateTrees(int start,int end){ if(start > end) return {NULL}; vector<TreeNode*> res; for(int i = start;i <= end;i++){ vector<TreeNode*> left = generateTrees(start,i-1); vector<TreeNode*> right = generateTrees(i+1,end); for(int j = 0;j < left.size();j++){ for(int k = 0;k < right.size();k++){ TreeNode* root = new TreeNode(i); root->left = left[j]; root->right = right[k]; res.push_back(root); } } } return res; } };
241. Different Ways to Add Parentheses
https://www.cnblogs.com/grandyang/p/4682458.html
这个题和95. Unique Binary Search Trees II的做法很像，分成当前位置和左侧、右侧。不同的是，这里的当前位置必须是符号出现的时候。
最后可能出现没有符号的情况，这个时候就需要将整个字符串转成int型数字输出。
注意：第一个是input.substr(0, i)，而不是input.substr(0, i-1)。很容易像95. Unique Binary Search Trees II那样写成i - 1，实质上left确实等于i-1前的，但是substr第二个参数是字符的个数，前i-1个的个数就是i。
class Solution { public: vector<int> diffWaysToCompute(string input) { vector<int> res; for(int i = 0;i < input.size();i++){ if(input[i] == '+' || input[i] == '-' || input[i] == '*'){ vector<int> left = diffWaysToCompute(input.substr(0,i)); vector<int> right = diffWaysToCompute(input.substr(i+1)); for(int j = 0;j < left.size();j++){ for(int k = 0;k < right.size();k++){ if(input[i] == '+') res.push_back(left[j] + right[k]); else if(input[i] == '-') res.push_back(left[j] - right[k]); else res.push_back(left[j] * right[k]); } } } } if(res.empty()) res.push_back(stoi(input)); return res; } };
© 著作权归作者所有
举报
相关热门文章
发表评论
0/200
