c******0
发帖数: 260 | 1 1。BT(binary tree), want to find the LIS(largest independent set) of the BT
LIS: if the current node is in the set, then its children should not be in
the set. So that the set has the largest number of nodes.
这题看着很眼熟，就是不知道怎么做。。。。
2.the most frequent urls in the past minute, hour, day
这题貌似很常见。我看stackoverflow上有人说用count-min sketch. 不知道还有没有
简便点的方法。
3.system deisign: design amazon product page
问这题是因为不明白对于这种system design 的题需要考虑哪些要点。
4.一个二维数组，元素是0或1，找出最大的由1构成的"X"形状
这题应该是用DP，但是还是不知道怎么做。。。。。 | x****g
发帖数: 1512 | 2 抛砖引玉一下? 呵呵.
1: "its children"我的理解是直属子节点? 如果间接也算方法类似?
每个节点保持2个值表示以自己为根子树,改节点参与和不参与的最大node set.
那么有NULL节点0,0. 那么
dp[root][0] = max(dp[root->left][0],dp[root->left][1]) +
max(dp[root->right][0],dp[root->right][1])
dp[root][1] = dp[root->left][0]+dp[root->right][0] + 1
//0表示自己不参与,1表示自己参与.
实际代码只要f(node, inMax&, notInMax&)递归就可以了,最后返回跟节点2个数字
中大的那个即可.
4: "X形状" 我理解为奇数的n*n? 对于任何一个点 i,j,分4个方向分别表示以该点为
右下,左下,右上,左上斜着的连续的1的个数(含自己).
那么该点为中心的最大X中1的个数为min(4个方向计数)*4-3.
这个值存在dp关系,以右下为例
dp[i][j][0]=dp[i-1][j-1][0]+1 A[i][j]==1
=0 A[i][j]==0
四个方向道理一样,类似求解dp[i][j][1..3]
完了就可以得出最大的那个了.
O(N^2)
想不出更好的,呵呵.
BT
【在 c******0 的大作中提到】
: 1。BT(binary tree), want to find the LIS(largest independent set) of the BT
: LIS: if the current node is in the set, then its children should not be in
: the set. So that the set has the largest number of nodes.
: 这题看着很眼熟，就是不知道怎么做。。。。
: 2.the most frequent urls in the past minute, hour, day
: 这题貌似很常见。我看stackoverflow上有人说用count-min sketch. 不知道还有没有
: 简便点的方法。
: 3.system deisign: design amazon product page
: 问这题是因为不明白对于这种system design 的题需要考虑哪些要点。
: 4.一个二维数组，元素是0或1，找出最大的由1构成的"X"形状
| c******0
发帖数: 260 | 3 第一题，我找到类似题的答案了，思路应该跟你说的一样
http://mypathtothe4.blogspot.com/2013/03/dynamic-programming-co
最后一题应该分奇数和偶数两种情况，思路应该跟你处理奇数是差不多的。
DP就是好难啊！！！
【在 x****g 的大作中提到】
: 抛砖引玉一下? 呵呵.
: 1: "its children"我的理解是直属子节点? 如果间接也算方法类似?
: 每个节点保持2个值表示以自己为根子树,改节点参与和不参与的最大node set.
: 那么有NULL节点0,0. 那么
: dp[root][0] = max(dp[root->left][0],dp[root->left][1]) +
: max(dp[root->right][0],dp[root->right][1])
: dp[root][1] = dp[root->left][0]+dp[root->right][0] + 1
: //0表示自己不参与,1表示自己参与.
: 实际代码只要f(node, inMax&, notInMax&)递归就可以了,最后返回跟节点2个数字
: 中大的那个即可.
| c******0
发帖数: 260 | 4 我写了一下，不知道对不对。。。求指教
struct Node{
int val;
Node *left, *right;
Node(int v): val(v), left(NULL), right(NULL){}
};
void maxNodeHelp(Node *root, int &direct, int &undirect){
if(!root) return;
int nextDirect = 1, nextUndirect = 0;
maxNodeHelp(root->left, nextDirect, nextUndirect);
maxNodeHelp(root->right, nextDirect, nextUndirect);
direct += nextUndirect;
undirect += max(nextDirect, nextUndirect);
}
int maxNode(Node *root){
if(!root) return 0;
int direct = 1, undirect=0;
maxNodeHelp(root, direct, undirect);
return max(direct, undirect);
}
【在 x****g 的大作中提到】
: 抛砖引玉一下? 呵呵.
: 1: "its children"我的理解是直属子节点? 如果间接也算方法类似?
: 每个节点保持2个值表示以自己为根子树,改节点参与和不参与的最大node set.
: 那么有NULL节点0,0. 那么
: dp[root][0] = max(dp[root->left][0],dp[root->left][1]) +
: max(dp[root->right][0],dp[root->right][1])
: dp[root][1] = dp[root->left][0]+dp[root->right][0] + 1
: //0表示自己不参与,1表示自己参与.
: 实际代码只要f(node, inMax&, notInMax&)递归就可以了,最后返回跟节点2个数字
: 中大的那个即可.
| g*****g
发帖数: 212 | 5 int maxNode(Node *root, bool parentSet){
if(!root) return 0;
if (parentSet)
{
return maxNode(root->left, false) + maxNode(root->right, false);
}
else
{
int n1 = 1 + maxNode(root->left, true) + maxNode(root->right, true);
int n2 = maxNode(root->left, false) + maxNode(root->right, false);
return max(n1, n2);
}
} | f**********t
发帖数: 1001 | 6 // BT(binary tree), want to find the LIS(largest independent set) of the BT
LIS: if the current node is in the set, then its children should not be in
the set. So that the set has the largest number of nodes.
vector MaxIndependentSet(TreeNode *r) {
if (!r) {
return vector();
}
static unordered_map> resultTable;
if (resultTable.find(r) != resultTable.end()) {
return resultTable[r];
} else {
vector vl, vll, vlr, vr, vrl, vrr;
if (r->left) {
vl = MaxIndependentSet(r->left);
vll = MaxIndependentSet(r->left->left);
vlr = MaxIndependentSet(r->left->right);
}
if (r->right) {
vr = MaxIndependentSet(r->right);
vrl = MaxIndependentSet(r->right->left);
vrr = MaxIndependentSet(r->right->right);
}
if (1 + vll.size() + + vlr.size() + vrl.size() + vrr.size() <
vl.size() + vr.size()) {
vl.insert(vl.end(), vr.begin(), vr.end());
resultTable[r] = vl;
} else {
vll.insert(vll.end(), vrr.begin(), vrr.end());
vll.insert(vll.end(), vrl.begin(), vrl.end());
vll.insert(vll.end(), vlr.begin(), vlr.end());
vll.push_back(r->val);
resultTable[r] = vll;
}
}
return resultTable[r];
} |
|
