-
第 21 楼 / webdriver
- 时间: 2014-9-25 00:44推荐答案来了 (in C++) ...
dp.
代码:
class Solution {
public:
int numTrees(int n) {
int dp[n+1];
memset(dp, 0, sizeof(dp));
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];
}
}; -
-
- 时间: 2014-9-25 00:46
-
-
- 时间: 2014-9-25 00:47推荐答案来了 (in C++) ...
1. DFS directly. (from the Internet)
2. DP + DFS. (my solution)
a. Generate trees for 'n' from 1 to n. (DP)
b. When generate trees for n = i, get the left and right subtrees
by copying tree structures of dp[1...i-1]. (copy tree uses DFS)
代码:
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
return generateTrees_1(n);
}
// solution 1
vector<TreeNode *> generateTrees_1(int n) {
return generateTreesRe(1, n);
}
vector<TreeNode*> generateTreesRe(int l, int r) {
vector<TreeNode*> res;
if (l > r) {
res.push_back(NULL);
return res;
}
for (int k = l; k <= r; k++) {
vector<TreeNode*> leftTrees = generateTreesRe(l, k-1);
vector<TreeNode*> rightTrees = generateTreesRe(k+1, r);
for (size_t i = 0; i < leftTrees.size(); i++) {
for (size_t j = 0; j < rightTrees.size(); j++) {
TreeNode* root = new TreeNode(k);
root->left = leftTrees[i];
root->right = rightTrees[j];
res.push_back(root);
}
}
}
return res;
}
// solution 2
vector<TreeNode *> generateTrees_2(int n) {
vector<TreeNode *> dp[n+1];
dp[0] = vector<TreeNode *>(1, (TreeNode *)NULL);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= i; ++j)
{
for (int m = 0; m < dp[j-1].size(); ++m)
{
for (int k = 0; k < dp[i-j].size(); ++k)
{
TreeNode *root = new TreeNode(j);
CopyTree(dp[j-1][m], root->left, 0);
CopyTree(dp[i-j][k], root->right, j);
dp[i].push_back(root);
}
}
}
}
return dp[n];
}
void CopyTree(TreeNode *original, TreeNode *&newNode, int diff)
{
if (!original) return;
newNode = new TreeNode(original->val + diff);
CopyTree(original->left, newNode->left, diff);
CopyTree(original->right, newNode->right, diff);
}
};
-
- 时间: 2014-9-25 00:50算法问题: Unique Paths
问题描述:
A robot is located at the top-left corner of a m x n grid.
The robot can only move either down or right at any point in time. The robot is trying to reach
the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there? -
- 时间: 2014-9-25 00:52推荐答案来了 (in C++) ...
1. Use formula C(x,t) = t!/(x!*(t-x)!) (x should be large for calculation).
2. Dynamic programming. UP(i,j) = UP(i-1,j) + UP(i,j-1).
代码:
class Solution {
public:
int uniquePaths_1(int m, int n) {
if (m == 1 || n == 1) return 1;
int t = (m-1)+(n-1);
int x = (m > n) ? (m-1) : (n-1);
long long res = 1;
for (int i = t; i > x; i--)
res *= i;
for (int i = t-x; i > 1; i--)
res /= i;
return res;
}
int uniquePaths_2(int m, int n) {
int dp[m][n];
for (int i = 0; i < m; i++)
dp[i][0] = 1;
for (int j = 0; j < n; j++)
dp[0][j] = 1;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
return dp[m-1][n-1];
}
}; -
- 时间: 2014-9-25 00:55算法问题: Unique Paths II
问题描述:
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100. -
- 时间: 2014-9-25 00:57推荐答案来了 (in C++) ...
Dynamic programming.
代码:
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
int dp[m][n];
if (obstacleGrid[0][0] == 1) return 0;
dp[0][0] = 1;
for (int i = 1; i < m; i++)
dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i-1][0];
for (int j = 1; j < n; j++)
dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j-1];
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = obstacleGrid[i][j] == 1 ? 0: dp[i-1][j] + dp[i][j-1];
return dp[m-1][n-1];
}
};
-
- 时间: 2014-9-25 01:00算法问题: Validate Binary Search Tree
问题描述:
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees. -
- 时间: 2014-9-25 01:02推荐答案来了 (in C++) ...
Recursion. 1. Add lower & upper bound. O(n)
2. Inorder traversal with one additional parameter (value of predecessor). O(n)
代码:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode *root) {
return isValidBST_1(root);
}
// solution 1: lower bound + higher bound
bool isValidBST_1(TreeNode *root) {
return isValidBSTRe_1(root, INT_MIN, INT_MAX);
}
bool isValidBSTRe_1(TreeNode *node, int lower, int upper){
if (!node) return true;
if (node->val <= lower || node->val >= upper) return false;
return isValidBSTRe_1(node->left, lower, node->val) &&
isValidBSTRe_1(node->right, node->val, upper);
}
// solution 2: inorder
bool isValidBST_2(TreeNode *root) {
int val = INT_MIN;
return isValidBSTRe_2(root, val);
}
bool isValidBSTRe_2(TreeNode *node, int &val)
{
if (!node) return true;
if (node->left && !isValidBSTRe_2(node->left, val))
return false;
if (node->val <= val)
return false;
val = node->val;
if (node->right && !isValidBSTRe_2(node->right, val))
return false;
return true;
}
};
-
- 时间: 2014-9-25 01:02
Leetcode Hacking Practice -- Solution in C++ Part 5
