g***j
发帖数: 1275 | 1 刚刚面的
1 给一个bst，返回第k大de元素
2 给一个set，比如1，2，3，返回所有的power set
都很简单，但是感觉要写对还很难。
请问谁提供一下解法？ |
s****0
发帖数: 117 | 2 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
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
|
w****x
发帖数: 2483 | 3 ”给一个bst，返回第k大de元素“
能不能自定义node结构? 可以的话每个node记录它作为根的树的节点个数， 然后二分 |
h*********o
发帖数: 230 | 4 返回所有的power set 是什么意思？
详细点？
【在 g***j 的大作中提到】
: 刚刚面的
: 1 给一个bst，返回第k大de元素
: 2 给一个set，比如1，2，3，返回所有的power set
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
|
l*******b
发帖数: 2586 | 5 clrs 上的order statistic tree ? 不过不需要做平衡。
【在 w****x 的大作中提到】
: ”给一个bst，返回第k大de元素“
: 能不能自定义node结构? 可以的话每个node记录它作为根的树的节点个数， 然后二分
|
d**********x
发帖数: 4083 | 6 这应该是后续问题吧。。
二分
【在 l*******b 的大作中提到】
: clrs 上的order statistic tree ? 不过不需要做平衡。
|
l*******b
发帖数: 2586 | 7 返回power set 吧，所有子集的集合。不是所有的power set
【在 h*********o 的大作中提到】
: 返回所有的power set 是什么意思？
: 详细点？
|
l*******b
发帖数: 2586 | 8 嗯，有道理
【在 d**********x 的大作中提到】
: 这应该是后续问题吧。。
:
: 二分
|
p*****2
发帖数: 21240 | 9 第一题难道不是traverse一遍就行了？
第二题就是subset问题？要考虑重复吗？ |
g***j
发帖数: 1275 | 10 第一题不用traverse 完吧？
第二题不考虑重复
【在 p*****2 的大作中提到】
: 第一题难道不是traverse一遍就行了？
: 第二题就是subset问题？要考虑重复吗？
|
|
|
g***j
发帖数: 1275 | 11 为什么better iterative？
【在 s****0 的大作中提到】
: 1order traversal . better iterative .
: 2 count up. the 1 bits gives the power set
|
p*****2
发帖数: 21240 | 12
嗯。最多一遍。碰到K就可以结束了。
第二题不考虑重复就更简单了。
【在 g***j 的大作中提到】
: 第一题不用traverse 完吧？
: 第二题不考虑重复
|
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 14 def dfs(arr, start, buf)
p buf if buf.length>0
(start...arr.length).each do |i|
buf<
dfs(arr,i+1,buf)
buf.pop
end
end
def subset(arr)
buf=[]
dfs(arr,0,buf)
end
subset([1,2,3]) |
j*****y
发帖数: 1071 | 15 第一道题:
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
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
|
j*****y
发帖数: 1071 | 16 第二道题能用 count up的思路写个代码吗？ 好学一下。一直用 recursive写，觉得不
太
professional.
【在 s****0 的大作中提到】
: 1order traversal . better iterative .
: 2 count up. the 1 bits gives the power set
|
s********l
发帖数: 998 | 17 不是找最大的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;
: }
:
|
l*****a
发帖数: 14598 | 18 生成如下序列，1的地方就是输出相应item
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
【在 j*****y 的大作中提到】
: 第二道题能用 count up的思路写个代码吗？ 好学一下。一直用 recursive写，觉得不
: 太
: professional.
|
j*****y
发帖数: 1071 | 19 题目好像是说 第 k 大
【在 s********l 的大作中提到】
: 不是找最大的kth吗？
: 你怎么先跑到左边去了呢？
: inorder traversal 反过来就可以了把~
|
s********l
发帖数: 998 | 20 我是说这个意思
in order traverse 翻过来就好了呀~
【在 j*****y 的大作中提到】
: 题目好像是说 第 k 大
|
|
|
p*****2
发帖数: 21240 | 21
这种方法长度有限制。
【在 j*****y 的大作中提到】
: 第二道题能用 count up的思路写个代码吗？ 好学一下。一直用 recursive写，觉得不
: 太
: professional.
|
l*****a
发帖数: 14598 | 22 用array ,not binary
【在 p*****2 的大作中提到】
:
: 这种方法长度有限制。
|
j*****y
发帖数: 1071 | 23 比如 in-order traversal 以后 是 1 2 3 4 5,
那 第 1大的元素是 1 还是 5 阿？
不过我的理解是 第 k 个元素，而不是第 k大个元素
可能我的理解不对。
【在 s********l 的大作中提到】
: 我是说这个意思
: in order traverse 翻过来就好了呀~
|
l*****a
发帖数: 14598 | 24 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 翻过来就好了呀~
|
s********l
发帖数: 998 | 25 我是说 in order 反过来
54321
第二大 就是4 其实 in order做到4的时候就可以停了
【在 j*****y 的大作中提到】
: 比如 in-order traversal 以后 是 1 2 3 4 5,
: 那 第 1大的元素是 1 还是 5 阿？
: 不过我的理解是 第 k 个元素，而不是第 k大个元素
: 可能我的理解不对。
|
s********l
发帖数: 998 | 26 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);
: }
|
p*****2
发帖数: 21240 | 27
那跟直接生成比也没啥优势吧？
【在 l*****a 的大作中提到】
: 用array ,not binary
|
j*****y
发帖数: 1071 | 28 那可以这样写
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
发帖数: 21240 | 29
java 有 ref吗？
【在 s********l 的大作中提到】
: i know you are showing off your java~
|
s********l
发帖数: 998 | 30 这个看懂了
前面那个没看懂。。
【在 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
发帖数: 998 | 31 他会java 我不会。。。
besides, i'm kidding~
【在 p*****2 的大作中提到】
:
: java 有 ref吗？
|
j*****y
发帖数: 1071 | 32 前面那个是我理解错了意思了。我以为是找第 K 个元素。
【在 s********l 的大作中提到】
: 这个看懂了
: 前面那个没看懂。。
|
l*****a
发帖数: 14598 | 33 no,1) i copied from the others
2) that seems to be c#
【在 s********l 的大作中提到】
: i know you are showing off your java~
|
s********l
发帖数: 998 | 34 whatever~
you are showing off~ :P
【在 l*****a 的大作中提到】
: no,1) i copied from the others
: 2) that seems to be c#
|
j*****y
发帖数: 1071 | 35 你这个序列是根据什么规律生成的？ 能给个 生成序列的code 吗？ 多谢
【在 l*****a 的大作中提到】
: 生成如下序列，1的地方就是输出相应item
: 0000
: 0001
: 0010
: 0011
: 0100
: 0101
: 0110
: 0111
: 1000
|
l*****a
发帖数: 14598 | 36 二进制加法
或者去看一下PIE的相关题目
【在 j*****y 的大作中提到】
: 你这个序列是根据什么规律生成的？ 能给个 生成序列的code 吗？ 多谢
|
j*****y
发帖数: 1071 | 37 多谢，二进制加法明白了。pie里面有这道题，好像它不是用二进制加法实现的吧？
【在 l*****a 的大作中提到】
: 二进制加法
: 或者去看一下PIE的相关题目
|
s********l
发帖数: 998 | 38 pie里面哪个？
【在 l*****a 的大作中提到】
: 二进制加法
: 或者去看一下PIE的相关题目
|
l*******b
发帖数: 2586 | 39 试一下scala写的第一个程序。。。
val list = Array[Int](1,3,4,5,7,9)
def powerSet(l: Array[Int]) = {
def select(i: Int, n:Int) =
for(j <- 0 to n if((i & (1 << j)) != 0)) yield l(j)
val n = l.length - 1
val p = (1 << (n+1)) - 1
val power = for(i <- 0 to p) yield select(i,n).mkString(" ")
power.mkString("\n")
}
【在 j*****y 的大作中提到】
: 多谢，二进制加法明白了。pie里面有这道题，好像它不是用二进制加法实现的吧？
|
l*****a
发帖数: 14598 | 40 电话号码对应单词
【在 s********l 的大作中提到】
: pie里面哪个？
|
|
|
l*****a
发帖数: 14598 | 41 基本相当于加1吧。
【在 j*****y 的大作中提到】
: 多谢，二进制加法明白了。pie里面有这道题，好像它不是用二进制加法实现的吧？
|
j*****y
发帖数: 1071 | 42 写了一个，确实简单多了.
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
|
j*****y
发帖数: 1071 | 43 也搞了一个数字有重复的 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
|
c*******i
发帖数: 30 | 44
【在 g***j 的大作中提到】
: 刚刚面的
: 1 给一个bst，返回第k大de元素
: 2 给一个set，比如1，2，3，返回所有的power set
: 都很简单，但是感觉要写对还很难。
: 请问谁提供一下解法？
|
