注意了，Wordly Wise 3000 Online有哭胖了# Parenting - 为人父母
g*j
1 楼
刚刚面的
1 给一个bst，返回第k大de元素
2 给一个set，比如1，2，3，返回所有的power set
都很简单，但是感觉要写对还很难。
请问谁提供一下解法？
1 给一个bst，返回第k大de元素
2 给一个set，比如1，2，3，返回所有的power set
都很简单，但是感觉要写对还很难。
请问谁提供一下解法？
s*0
3 楼
1order traversal . better iterative .
2 count up. the 1 bits gives the power set
【在 g***j 的大作中提到】
: 刚刚面的
: 1 给一个bst，返回第k大de元素
: 2 给一个set，比如1，2，3，返回所有的power set
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
2 count up. the 1 bits gives the power set
【在 g***j 的大作中提到】
: 刚刚面的
: 1 给一个bst，返回第k大de元素
: 2 给一个set，比如1，2，3，返回所有的power set
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
w*x
4 楼
”给一个bst，返回第k大de元素“
能不能自定义node结构? 可以的话每个node记录它作为根的树的节点个数， 然后二分
能不能自定义node结构? 可以的话每个node记录它作为根的树的节点个数， 然后二分
h*o
5 楼
返回所有的power set 是什么意思？
详细点？
【在 g***j 的大作中提到】
: 刚刚面的
: 1 给一个bst，返回第k大de元素
: 2 给一个set，比如1，2，3，返回所有的power set
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
详细点？
【在 g***j 的大作中提到】
: 刚刚面的
: 1 给一个bst，返回第k大de元素
: 2 给一个set，比如1，2，3，返回所有的power set
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
l*b
6 楼
clrs 上的order statistic tree ? 不过不需要做平衡。
【在 w****x 的大作中提到】
: ”给一个bst，返回第k大de元素“
: 能不能自定义node结构? 可以的话每个node记录它作为根的树的节点个数， 然后二分
【在 w****x 的大作中提到】
: ”给一个bst，返回第k大de元素“
: 能不能自定义node结构? 可以的话每个node记录它作为根的树的节点个数， 然后二分
d*x
7 楼
这应该是后续问题吧。。
二分
【在 l*******b 的大作中提到】
: clrs 上的order statistic tree ? 不过不需要做平衡。
二分
【在 l*******b 的大作中提到】
: clrs 上的order statistic tree ? 不过不需要做平衡。
l*b
8 楼
返回power set 吧，所有子集的集合。不是所有的power set
【在 h*********o 的大作中提到】
: 返回所有的power set 是什么意思？
: 详细点？
【在 h*********o 的大作中提到】
: 返回所有的power set 是什么意思？
: 详细点？
l*b
9 楼
嗯，有道理
【在 d**********x 的大作中提到】
: 这应该是后续问题吧。。
:
: 二分
【在 d**********x 的大作中提到】
: 这应该是后续问题吧。。
:
: 二分
p*2
10 楼
第一题难道不是traverse一遍就行了？
第二题就是subset问题？要考虑重复吗？
第二题就是subset问题？要考虑重复吗？
g*j
11 楼
第一题不用traverse 完吧？
第二题不考虑重复
【在 p*****2 的大作中提到】
: 第一题难道不是traverse一遍就行了？
: 第二题就是subset问题？要考虑重复吗？
第二题不考虑重复
【在 p*****2 的大作中提到】
: 第一题难道不是traverse一遍就行了？
: 第二题就是subset问题？要考虑重复吗？
g*j
12 楼
为什么better iterative？
【在 s****0 的大作中提到】
: 1order traversal . better iterative .
: 2 count up. the 1 bits gives the power set
【在 s****0 的大作中提到】
: 1order traversal . better iterative .
: 2 count up. the 1 bits gives the power set
p*2
13 楼
嗯。最多一遍。碰到K就可以结束了。
第二题不考虑重复就更简单了。
【在 g***j 的大作中提到】
: 第一题不用traverse 完吧？
: 第二题不考虑重复
p*2
14 楼
对了第二题是set，所以没有重复。
p*2
15 楼
def dfs(arr, start, buf)
p buf if buf.length>0
(start...arr.length).each do |i|
buf<
buf.pop
end
end
def subset(arr)
buf=[]
dfs(arr,0,buf)
end
subset([1,2,3])
p buf if buf.length>0
(start...arr.length).each do |i|
buf<
buf.pop
end
end
def subset(arr)
buf=[]
dfs(arr,0,buf)
end
subset([1,2,3])
j*y
16 楼
第一道题:
bool isKth(TreeNode * root, TreeNode* &lastNode, int & k, int K)
{
if(root->left)
{
if(isKth(root->left, lastNode, k, K)
{
return true;
}
}
++k;
lastNode = root;
if(k == K)
{
return true;
}
if(root->right)
{
if(isKth(root->right, lastNode, k, K))
{
return true;
}
}
return false;
}
第二道题:
vector > power(vector & v, int start)
{
vector > result;
if(start == v.size() - 1)
{
result.push_back(vector());
result.push_back(vector(1, v[start]));
return result;
}
vector > tmp = power(v, start + 1);
result = tmp;
for(int i = 0; i < tmp.size(); ++i)
{
vector to_insert = tmp[i];
to_insert.insert(to_insert.begin(), v[start]);
result.push_back(to_insert);
}
return result;
}
【在 g***j 的大作中提到】
: 刚刚面的
: 1 给一个bst，返回第k大de元素
: 2 给一个set，比如1，2，3，返回所有的power set
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
bool isKth(TreeNode * root, TreeNode* &lastNode, int & k, int K)
{
if(root->left)
{
if(isKth(root->left, lastNode, k, K)
{
return true;
}
}
++k;
lastNode = root;
if(k == K)
{
return true;
}
if(root->right)
{
if(isKth(root->right, lastNode, k, K))
{
return true;
}
}
return false;
}
第二道题:
vector
{
vector
if(start == v.size() - 1)
{
result.push_back(vector
result.push_back(vector
return result;
}
vector
result = tmp;
for(int i = 0; i < tmp.size(); ++i)
{
vector
to_insert.insert(to_insert.begin(), v[start]);
result.push_back(to_insert);
}
return result;
}
【在 g***j 的大作中提到】
: 刚刚面的
: 1 给一个bst，返回第k大de元素
: 2 给一个set，比如1，2，3，返回所有的power set
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
j*y
17 楼
第二道题能用 count up的思路写个代码吗？ 好学一下。一直用 recursive写，觉得不
太
professional.
【在 s****0 的大作中提到】
: 1order traversal . better iterative .
: 2 count up. the 1 bits gives the power set
太
professional.
【在 s****0 的大作中提到】
: 1order traversal . better iterative .
: 2 count up. the 1 bits gives the power set
s*l
18 楼
不是找最大的kth吗？
你怎么先跑到左边去了呢？
inorder traversal 反过来就可以了把~
【在 j*****y 的大作中提到】
: 第一道题:
: bool isKth(TreeNode * root, TreeNode* &lastNode, int & k, int K)
: {
: if(root->left)
: {
: if(isKth(root->left, lastNode, k, K)
: {
: return true;
: }
:
你怎么先跑到左边去了呢？
inorder traversal 反过来就可以了把~
【在 j*****y 的大作中提到】
: 第一道题:
: bool isKth(TreeNode * root, TreeNode* &lastNode, int & k, int K)
: {
: if(root->left)
: {
: if(isKth(root->left, lastNode, k, K)
: {
: return true;
: }
:
l*a
19 楼
生成如下序列，1的地方就是输出相应item
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
【在 j*****y 的大作中提到】
: 第二道题能用 count up的思路写个代码吗？ 好学一下。一直用 recursive写，觉得不
: 太
: professional.
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
【在 j*****y 的大作中提到】
: 第二道题能用 count up的思路写个代码吗？ 好学一下。一直用 recursive写，觉得不
: 太
: professional.
j*y
20 楼
题目好像是说 第 k 大
【在 s********l 的大作中提到】
: 不是找最大的kth吗？
: 你怎么先跑到左边去了呢？
: inorder traversal 反过来就可以了把~
【在 s********l 的大作中提到】
: 不是找最大的kth吗？
: 你怎么先跑到左边去了呢？
: inorder traversal 反过来就可以了把~
s*l
21 楼
我是说这个意思
in order traverse 翻过来就好了呀~
【在 j*****y 的大作中提到】
: 题目好像是说 第 k 大
in order traverse 翻过来就好了呀~
【在 j*****y 的大作中提到】
: 题目好像是说 第 k 大
p*2
22 楼
这种方法长度有限制。
【在 j*****y 的大作中提到】
: 第二道题能用 count up的思路写个代码吗？ 好学一下。一直用 recursive写，觉得不
: 太
: professional.
l*a
23 楼
用array ,not binary
【在 p*****2 的大作中提到】
:
: 这种方法长度有限制。
【在 p*****2 的大作中提到】
:
: 这种方法长度有限制。
j*y
24 楼
比如 in-order traversal 以后 是 1 2 3 4 5,
那 第 1大的元素是 1 还是 5 阿？
不过我的理解是 第 k 个元素，而不是第 k大个元素
可能我的理解不对。
【在 s********l 的大作中提到】
: 我是说这个意思
: in order traverse 翻过来就好了呀~
那 第 1大的元素是 1 还是 5 阿？
不过我的理解是 第 k 个元素，而不是第 k大个元素
可能我的理解不对。
【在 s********l 的大作中提到】
: 我是说这个意思
: in order traverse 翻过来就好了呀~
l*a
25 楼
static void bstVisit(Node p_node, ref int n)
{
if (p_node == null || n < 0 ) return;
bstVisit(p_node.right, ref n);
n--;
if (n == 0) System.Console.WriteLine(p_node.Num);
bstVisit(p_node.left, ref n);
}
【在 s********l 的大作中提到】
: 我是说这个意思
: in order traverse 翻过来就好了呀~
{
if (p_node == null || n < 0 ) return;
bstVisit(p_node.right, ref n);
n--;
if (n == 0) System.Console.WriteLine(p_node.Num);
bstVisit(p_node.left, ref n);
}
【在 s********l 的大作中提到】
: 我是说这个意思
: in order traverse 翻过来就好了呀~
s*l
26 楼
我是说 in order 反过来
54321
第二大 就是4 其实 in order做到4的时候就可以停了
【在 j*****y 的大作中提到】
: 比如 in-order traversal 以后 是 1 2 3 4 5,
: 那 第 1大的元素是 1 还是 5 阿？
: 不过我的理解是 第 k 个元素，而不是第 k大个元素
: 可能我的理解不对。
54321
第二大 就是4 其实 in order做到4的时候就可以停了
【在 j*****y 的大作中提到】
: 比如 in-order traversal 以后 是 1 2 3 4 5,
: 那 第 1大的元素是 1 还是 5 阿？
: 不过我的理解是 第 k 个元素，而不是第 k大个元素
: 可能我的理解不对。
s*l
27 楼
i know you are showing off your java~
【在 l*****a 的大作中提到】
: static void bstVisit(Node p_node, ref int n)
: {
: if (p_node == null || n < 0 ) return;
: bstVisit(p_node.right, ref n);
: n--;
: if (n == 0) System.Console.WriteLine(p_node.Num);
: bstVisit(p_node.left, ref n);
: }
【在 l*****a 的大作中提到】
: static void bstVisit(Node p_node, ref int n)
: {
: if (p_node == null || n < 0 ) return;
: bstVisit(p_node.right, ref n);
: n--;
: if (n == 0) System.Console.WriteLine(p_node.Num);
: bstVisit(p_node.left, ref n);
: }
p*2
28 楼
那跟直接生成比也没啥优势吧？
【在 l*****a 的大作中提到】
: 用array ,not binary
j*y
29 楼
那可以这样写
bool isKth(TreeNode * root, TreeNode* &lastNode, int & k, int K)
{
if(root->right)
{
if(isKth(root->right, lastNode, k, K))
{
return true;
}
}
++k;
lastNode = root;
if(k == K)
{
return true;
}
if(root->left)
{
if(isKth(root->left, lastNode, k, K)
{
return true;
}
}
return false;
}
【在 s********l 的大作中提到】
: 我是说 in order 反过来
: 54321
: 第二大 就是4 其实 in order做到4的时候就可以停了
bool isKth(TreeNode * root, TreeNode* &lastNode, int & k, int K)
{
if(root->right)
{
if(isKth(root->right, lastNode, k, K))
{
return true;
}
}
++k;
lastNode = root;
if(k == K)
{
return true;
}
if(root->left)
{
if(isKth(root->left, lastNode, k, K)
{
return true;
}
}
return false;
}
【在 s********l 的大作中提到】
: 我是说 in order 反过来
: 54321
: 第二大 就是4 其实 in order做到4的时候就可以停了
p*2
30 楼
java 有 ref吗？
【在 s********l 的大作中提到】
: i know you are showing off your java~
s*l
31 楼
这个看懂了
前面那个没看懂。。
【在 j*****y 的大作中提到】
: 那可以这样写
: bool isKth(TreeNode * root, TreeNode* &lastNode, int & k, int K)
: {
: if(root->right)
: {
: if(isKth(root->right, lastNode, k, K))
: {
: return true;
: }
: }
前面那个没看懂。。
【在 j*****y 的大作中提到】
: 那可以这样写
: bool isKth(TreeNode * root, TreeNode* &lastNode, int & k, int K)
: {
: if(root->right)
: {
: if(isKth(root->right, lastNode, k, K))
: {
: return true;
: }
: }
s*l
32 楼
他会java 我不会。。。
besides, i'm kidding~
【在 p*****2 的大作中提到】
:
: java 有 ref吗？
besides, i'm kidding~
【在 p*****2 的大作中提到】
:
: java 有 ref吗？
j*y
33 楼
前面那个是我理解错了意思了。我以为是找第 K 个元素。
【在 s********l 的大作中提到】
: 这个看懂了
: 前面那个没看懂。。
【在 s********l 的大作中提到】
: 这个看懂了
: 前面那个没看懂。。
l*a
34 楼
no,1) i copied from the others
2) that seems to be c#
【在 s********l 的大作中提到】
: i know you are showing off your java~
2) that seems to be c#
【在 s********l 的大作中提到】
: i know you are showing off your java~
s*l
35 楼
whatever~
you are showing off~ :P
【在 l*****a 的大作中提到】
: no,1) i copied from the others
: 2) that seems to be c#
you are showing off~ :P
【在 l*****a 的大作中提到】
: no,1) i copied from the others
: 2) that seems to be c#
j*y
36 楼
你这个序列是根据什么规律生成的？ 能给个 生成序列的code 吗？ 多谢
【在 l*****a 的大作中提到】
: 生成如下序列，1的地方就是输出相应item
: 0000
: 0001
: 0010
: 0011
: 0100
: 0101
: 0110
: 0111
: 1000
【在 l*****a 的大作中提到】
: 生成如下序列，1的地方就是输出相应item
: 0000
: 0001
: 0010
: 0011
: 0100
: 0101
: 0110
: 0111
: 1000
l*a
37 楼
二进制加法
或者去看一下PIE的相关题目
【在 j*****y 的大作中提到】
: 你这个序列是根据什么规律生成的？ 能给个 生成序列的code 吗？ 多谢
或者去看一下PIE的相关题目
【在 j*****y 的大作中提到】
: 你这个序列是根据什么规律生成的？ 能给个 生成序列的code 吗？ 多谢
j*y
38 楼
多谢，二进制加法明白了。pie里面有这道题，好像它不是用二进制加法实现的吧？
【在 l*****a 的大作中提到】
: 二进制加法
: 或者去看一下PIE的相关题目
【在 l*****a 的大作中提到】
: 二进制加法
: 或者去看一下PIE的相关题目
s*l
39 楼
pie里面哪个？
【在 l*****a 的大作中提到】
: 二进制加法
: 或者去看一下PIE的相关题目
【在 l*****a 的大作中提到】
: 二进制加法
: 或者去看一下PIE的相关题目
l*b
40 楼
试一下scala写的第一个程序。。。
val list = Array[Int](1,3,4,5,7,9)
def powerSet(l: Array[Int]) = {
def select(i: Int, n:Int) =
for(j val n = l.length - 1
val p = (1 << (n+1)) - 1
val power = for(i power.mkString("\n")
}
【在 j*****y 的大作中提到】
: 多谢，二进制加法明白了。pie里面有这道题，好像它不是用二进制加法实现的吧？
val list = Array[Int](1,3,4,5,7,9)
def powerSet(l: Array[Int]) = {
def select(i: Int, n:Int) =
for(j val n = l.length - 1
val p = (1 << (n+1)) - 1
val power = for(i power.mkString("\n")
}
【在 j*****y 的大作中提到】
: 多谢，二进制加法明白了。pie里面有这道题，好像它不是用二进制加法实现的吧？
l*a
41 楼
电话号码对应单词
【在 s********l 的大作中提到】
: pie里面哪个？
【在 s********l 的大作中提到】
: pie里面哪个？
l*a
42 楼
基本相当于加1吧。
【在 j*****y 的大作中提到】
: 多谢，二进制加法明白了。pie里面有这道题，好像它不是用二进制加法实现的吧？
【在 j*****y 的大作中提到】
: 多谢，二进制加法明白了。pie里面有这道题，好像它不是用二进制加法实现的吧？
j*y
43 楼
写了一个，确实简单多了.
class Solution {
public:
vector > subsets(vector &S) {
sort(S.begin(), S.end());
vector > result;
vector v(S.size(), false);
int i = 0;
while(true)
{
if(i == -1)
{
break;
}
vector tmp;
for(int j = 0; j < v.size(); ++j)
{
if(v[j])
{
tmp.push_back(S[j]);
}
}
result.push_back(tmp);
for(i = v.size() - 1; i > -1; --i)
{
if(v[i])
{
v[i] = false;
}
else
{
v[i] = true;
break;
}
}
}
return result;
}
};
【在 l*****a 的大作中提到】
: 用array ,not binary
class Solution {
public:
vector
sort(S.begin(), S.end());
vector
vector
int i = 0;
while(true)
{
if(i == -1)
{
break;
}
vector
for(int j = 0; j < v.size(); ++j)
{
if(v[j])
{
tmp.push_back(S[j]);
}
}
result.push_back(tmp);
for(i = v.size() - 1; i > -1; --i)
{
if(v[i])
{
v[i] = false;
}
else
{
v[i] = true;
break;
}
}
}
return result;
}
};
【在 l*****a 的大作中提到】
: 用array ,not binary
j*y
44 楼
也搞了一个数字有重复的 power set
class Solution {
public:
vector > subsetsWithDup(vector &S) {
sort(S.begin(), S.end());
vector denominator;
vector counter;
int i;
for(i = 0; i < S.size();)
{
denominator.push_back(S[i]);
int j = i;
while(j < S.size() && S[j] == S[i])
{
++j;
}
counter.push_back(j - i);
i = j;
}
vector > result;
vector v(denominator.size(), 0);
i = 0;
while(true)
{
if(i == -1)
{
break;
}
vector tmp;
for(int j = 0; j < v.size(); ++j)
{
for(int k = 1; k <= v[j]; ++k)
{
tmp.push_back(denominator[j]);
}
}
result.push_back(tmp);
for(i = denominator.size() - 1; i > -1; --i)
{
if(v[i] == counter[i])
{
v[i] = 0;
}
else
{
++v[i];
break;
}
}
}
return result;
}
};
【在 l*****a 的大作中提到】
: 用array ,not binary
class Solution {
public:
vector
sort(S.begin(), S.end());
vector
vector
int i;
for(i = 0; i < S.size();)
{
denominator.push_back(S[i]);
int j = i;
while(j < S.size() && S[j] == S[i])
{
++j;
}
counter.push_back(j - i);
i = j;
}
vector
vector
i = 0;
while(true)
{
if(i == -1)
{
break;
}
vector
for(int j = 0; j < v.size(); ++j)
{
for(int k = 1; k <= v[j]; ++k)
{
tmp.push_back(denominator[j]);
}
}
result.push_back(tmp);
for(i = denominator.size() - 1; i > -1; --i)
{
if(v[i] == counter[i])
{
v[i] = 0;
}
else
{
++v[i];
break;
}
}
}
return result;
}
};
【在 l*****a 的大作中提到】
: 用array ,not binary
c*i
45 楼
【在 g***j 的大作中提到】
: 刚刚面的
: 1 给一个bst，返回第k大de元素
: 2 给一个set，比如1，2，3，返回所有的power set
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
相关阅读
把孩子送去台湾人开的中文学校？不发烧24小时之后。。。这样的条件,小孩上大学能申请financial aid 吗？到底是什么让孩子说出我的父母就是黑社会4 years old boy removed one bad tooth, need a "SPACER"理工自然科学类团购专楼Re: 想起刚做老鼠实验时的囧事 (转载)也来说说女孩的培养继续欣赏钢琴完蛋娃孩子的教育问题令人纠结问个三番学区的问题父母版申请代发活动奖励 (转载)孩子上游泳课都会考试分水平吗？Re: [竞选] Parenting 版版主---sheanne (转载)刚满五岁可以自己坐校车回家吗？少儿不宜吗?Re: 投诉parenting版三sheanne举办活动却不给奖金 (转载)边吃饭边做别的事情有多不好？给小孩办旅行证需要预约么？来说一说和家人存在的那些代沟