有没有听说过ups把单反损坏的? - 未名空间MITBBS历史存档

有没有听说过ups把单反损坏的?# PhotoGear - 摄影器材

a*a2011-07-15 07:07

1 楼

在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
大牛怎么做
“给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
杂度，而且大小是确定好的”
数组里各个node是打乱的，不是topologically sorted的
update：
举个例子：
[3,1,4,1,5,7,2,6]
删index 1
得到
[x,x,4,x,5,7,2,6] （x代表被删除）
最终输出
[1,2,4,0,3]
我觉得主要难点在找到哪些index要删，最后往前挪补空缺的步骤比较trivial

p*j2011-07-15 07:07

2 楼

请问一下如果PP 140被RFE了，补交材料之后时间是怎么算？是从新材料收到起15天呢
，还是继续接着原来的时间算？

x*42011-07-15 07:07

3 楼

最近买了个单反，UPS好像迷路似的转运了6个地方。下周二才能送到我家。请问这样长
途跋涉会对单反有影响吗?收到货物之后怎样检查?

t*n2011-07-15 07:07

4 楼

建个数组of （位置，是否删除）。walk一遍拿到位置。再walk一遍同时search是否应
该删除。O(n)的时间和空间复杂度。总共连写code，最多10-15分钟应该搞定。

b*e2011-07-15 07:07

5 楼

从新材料收到起

【在 p***j 的大作中提到】

: 请问一下如果PP 140被RFE了，补交材料之后时间是怎么算？是从新材料收到起15天呢
: ，还是继续接着原来的时间算？

bz2011-07-15 07:07

6 楼

检查机子之前可以看个医生先。

【在 x***4 的大作中提到】

: 最近买了个单反，UPS好像迷路似的转运了6个地方。下周二才能送到我家。请问这样长
: 途跋涉会对单反有影响吗?收到货物之后怎样检查?

T*U2011-07-15 07:07

7 楼

请定义一下删除。
一般来说子树到父节点链接去掉就是删除了，那这里把这个节点指向parent的链接清掉
就行了。

【在 a*******a 的大作中提到】

: 在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
: 大牛怎么做
: “给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
: 数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
: index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
: 这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
: 杂度，而且大小是确定好的”
: 数组里各个node是打乱的，不是topologically sorted的
: update：
: 举个例子：

s*32011-07-15 07:07

8 楼

岂止是损坏，一年前UPS还偷了个无敌兔，幸亏我老最后索赔成功，要不然就亏大了

【在 x***4 的大作中提到】

: 最近买了个单反，UPS好像迷路似的转运了6个地方。下周二才能送到我家。请问这样长
: 途跋涉会对单反有影响吗?收到货物之后怎样检查?

k*l2011-07-15 07:07

9 楼

一两遍不行吧，走一遍发现这个节点的几个孩子,再走一遍又发现前面还有漏掉的孙子
，再走一遍重孙子。。。直到九族全灭

【在 t****n 的大作中提到】

: 建个数组of （位置，是否删除）。walk一遍拿到位置。再walk一遍同时search是否应
: 该删除。O(n)的时间和空间复杂度。总共连写code，最多10-15分钟应该搞定。

m*72011-07-15 07:07

10 楼

UPS怎么没把你给偷了去

【在 s**********3 的大作中提到】

: 岂止是损坏，一年前UPS还偷了个无敌兔，幸亏我老最后索赔成功，要不然就亏大了

t*n2011-07-15 07:07

11 楼

可以，walk的同时循环找parent，一直到r碰到一个已知被删除或保留的的节点。mark
所有的parent和grand。。。
结果还是线性的复杂度

【在 k**l 的大作中提到】

: 一两遍不行吧，走一遍发现这个节点的几个孩子,再走一遍又发现前面还有漏掉的孙子
: ，再走一遍重孙子。。。直到九族全灭

s*32011-07-15 07:07

12 楼

倒贴钱都没女人收我啊

【在 m****7 的大作中提到】

: UPS怎么没把你给偷了去

a*a2011-07-15 07:07

13 楼

就是最后输出一个把该删除的都删除掉了的新的数组
比如1，2，3是5的children，要删5，那么最后输出的数组里面，index 1，2，3，5都
被删
除掉了，其他
的往前挪，填空出来的位置

【在 T****U 的大作中提到】

: 请定义一下删除。
: 一般来说子树到父节点链接去掉就是删除了，那这里把这个节点指向parent的链接清掉
: 就行了。

a*i2011-07-15 07:07

14 楼

带着你秒杀无敌兔的D40就没问题了

【在 s**********3 的大作中提到】

: 倒贴钱都没女人收我啊

a*a2011-07-15 07:07

15 楼

你每search一个index是不是该删除，都要从它一直追溯到它的老祖宗，which is logn
in average，O(n) in the worst case，如何做到总共O(n)时间

【在 t****n 的大作中提到】

: 建个数组of （位置，是否删除）。walk一遍拿到位置。再walk一遍同时search是否应
: 该删除。O(n)的时间和空间复杂度。总共连写code，最多10-15分钟应该搞定。

s*32011-07-15 07:07

16 楼

用好D40，真的可以灭掉无敌兔的
不仅仅是对焦的问题，还有境界的问题

【在 a**i 的大作中提到】

: 带着你秒杀无敌兔的D40就没问题了

a*a2011-07-15 07:07

17 楼

I have updated an example above

f*y2011-07-15 07:07

18 楼

你指的是阿Q的境界？

【在 s**********3 的大作中提到】

: 用好D40，真的可以灭掉无敌兔的
: 不仅仅是对焦的问题，还有境界的问题

g*z2011-07-15 07:07

19 楼

但是在这logn步的追溯过程中，可以有logn个节点被确定是否被删除，等搜到他们的时
候就不用再追溯了，相当于确定每一个节点是否被删除只需要常数复杂度，所以应该是
O(n)没错的

logn

【在 a*******a 的大作中提到】

: 你每search一个index是不是该删除，都要从它一直追溯到它的老祖宗，which is logn
: in average，O(n) in the worst case，如何做到总共O(n)时间

s*32011-07-15 07:07

20 楼

乐在其中就行了，管他阿Q不阿Q呢

【在 f*******y 的大作中提到】

: 你指的是阿Q的境界？

t*n2011-07-15 07:07

21 楼

不需要每一个都到root，到一个已知的就结束了。第二次walk每个节点on average
touch最多两次。所以是线性的

logn

【在 a*******a 的大作中提到】

: 你每search一个index是不是该删除，都要从它一直追溯到它的老祖宗，which is logn
: in average，O(n) in the worst case，如何做到总共O(n)时间

x*42011-07-15 07:07

22 楼

这么快就跑题了。。。

t*n2011-07-15 07:07

23 楼

嗯，你的表达能力比我好，优势大大的

【在 g******z 的大作中提到】

: 但是在这logn步的追溯过程中，可以有logn个节点被确定是否被删除，等搜到他们的时
: 候就不用再追溯了，相当于确定每一个节点是否被删除只需要常数复杂度，所以应该是
: O(n)没错的
:
: logn

s*32011-07-15 07:07

24 楼

跑题是常态，不跑题才奇怪呢

【在 x***4 的大作中提到】

: 这么快就跑题了。。。

k*l2011-07-15 07:07

25 楼

我给你举个例子，要删除的节点logn-1代单传,
你n-logn个节点都得上述到根节点才能确定不删

【在 g******z 的大作中提到】

: 但是在这logn步的追溯过程中，可以有logn个节点被确定是否被删除，等搜到他们的时
: 候就不用再追溯了，相当于确定每一个节点是否被删除只需要常数复杂度，所以应该是
: O(n)没错的
:
: logn

f*y2011-07-15 07:07

26 楼

赞心态。。。

【在 s**********3 的大作中提到】

: 乐在其中就行了，管他阿Q不阿Q呢

a*a2011-07-15 07:07

27 楼

大牛第一遍walk拿位置指的是拿什么位置？

【在 t****n 的大作中提到】

: 不需要每一个都到root，到一个已知的就结束了。第二次walk每个节点on average
: touch最多两次。所以是线性的
:
: logn

t*n2011-07-15 07:07

28 楼

拿的是在input数组中的位置。目的是得到一个index to position的map。方便第二次
search parent

【在 a*******a 的大作中提到】

: 大牛第一遍walk拿位置指的是拿什么位置？

a*a2011-07-15 07:07

29 楼

想了想，恩你说的对，谢谢大牛

【在 g******z 的大作中提到】

: 但是在这logn步的追溯过程中，可以有logn个节点被确定是否被删除，等搜到他们的时
: 候就不用再追溯了，相当于确定每一个节点是否被删除只需要常数复杂度，所以应该是
: O(n)没错的
:
: logn

t*n2011-07-15 07:07

30 楼

懒得写了，你仔细想想，不删也是可以拿来short circuit 子孙的search的

【在 k**l 的大作中提到】

: 我给你举个例子，要删除的节点logn-1代单传,
: 你n-logn个节点都得上述到根节点才能确定不删

a*a2011-07-15 07:07

31 楼

大牛你说的对，谢谢。
你想的很周全，完全符合题意
其实题也没那么复杂
比如input【3，1，4，1，5，7，2，6】
拿index 0 来说，他的index就是0，他的parent是index 3，他的index就是数组中的
index，所以没必要拿位置。
你的意思我理解，如果他的index不是数组中index，就要按你说的做
大牛确实厉害。。。

【在 t****n 的大作中提到】

: 拿的是在input数组中的位置。目的是得到一个index to position的map。方便第二次
: search parent

a*a2011-07-15 07:07

32 楼

你自己画两个例子。。。最开始由于没有记录要找到祖宗，但是每找到一次祖宗（或要
删得node），你都可以把这条路径记录下来，哪些删哪些不删，下次碰到直接用结果就好

【在 k**l 的大作中提到】

: 我给你举个例子，要删除的节点logn-1代单传,
: 你n-logn个节点都得上述到根节点才能确定不删

k*l2011-07-15 07:07

33 楼

第一遍是n*logn，以后就不用再找了
anyway, 这个确实比我说的那个多次遍历好多了

就好

【在 a*******a 的大作中提到】

: 你自己画两个例子。。。最开始由于没有记录要找到祖宗，但是每找到一次祖宗（或要
: 删得node），你都可以把这条路径记录下来，哪些删哪些不删，下次碰到直接用结果就好

e*22011-07-15 07:07

34 楼

1)
for( int i : nums ){
find path p : i --> to the root;
if(p contains Integer.MAX_VALUE or node to be deleted somewhere)
then set the nodes between i (inclusive) and Integer.MAX_VALUE to
Integer.MAX_VALUE;
}
2)
compact the pierced array:
Say, exchange i and Integer.MAX_VALUE at j:
nums[j] = nums[i]
nums[i] = - j - 1;
3)
for( j in those not change position with Integer.MAX_VALUE){
if(nums[nums[j]] < 0)
nums[j] = - nums[nums[j]] - 1;
}

【在 a*******a 的大作中提到】

: 在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
: 大牛怎么做
: “给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
: 数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
: index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
: 这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
: 杂度，而且大小是确定好的”
: 数组里各个node是打乱的，不是topologically sorted的
: update：
: 举个例子：

l*s2011-07-15 07:07

35 楼

加个Hashmap做个反向索引把儿子老子的顺序改正了就行了吧

t*n2011-07-15 07:07

36 楼

说了几遍了。是n

【在 k**l 的大作中提到】

: 第一遍是n*logn，以后就不用再找了
: anyway, 这个确实比我说的那个多次遍历好多了
:
: 就好

T*U2011-07-15 07:07

37 楼

你的例子是不是有问题？
[3,1,4,1,5,7,2,6]
删index 1
得到
[x,x,4,x,5,7,2,6] （x代表被删除）
最终输出
[1,2,4,0,3]
1的父节点也是1，那它是根节点？
4->5->7->6->2->4 这个循环了吧
删完最后挪节点也不trivia吧，要重新建立索引关系。

【在 a*******a 的大作中提到】

: 在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
: 大牛怎么做
: “给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
: 数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
: index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
: 这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
: 杂度，而且大小是确定好的”
: 数组里各个node是打乱的，不是topologically sorted的
: update：
: 举个例子：

r*72011-07-15 07:07

38 楼

借个不就是有向图的dfs嘛
把递归的结果存起来如果递归遇到了指定的index就是要被删的节点。

【在 a*******a 的大作中提到】

: 在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
: 大牛怎么做
: “给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
: 数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
: index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
: 这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
: 杂度，而且大小是确定好的”
: 数组里各个node是打乱的，不是topologically sorted的
: update：
: 举个例子：

x*92011-07-15 07:07

39 楼

DFS + Visit标记。 O(n)空间复杂度，O(n)时间复杂度求到index的路径。（由child到
parent）
然后用个Hash表存这个路径，再一遍删掉就行了。

e*22011-07-15 07:07

40 楼

public class Solution {

public int[] deleteTree(int[] nums, int ind) {

if(ind == nums[ind]) return new int[0];

int max = Integer.MAX_VALUE;
nums[ind] = max;

int j, k, temp;
for(int i = 0; i < nums.length; ++i){

j = i;
while(nums[j] != j && nums[j] != max && nums[j] >= 0
){
j = nums[j];
}
if(nums[j] == max){
k = i;
while(k != j){
temp = nums[k];
nums[k] = max;
k = temp;
}
}else{
k = i;
if(nums[j] >= 0) nums[j] = - nums[j] - 1;
while(k != j){
temp = nums[k];
nums[k] = -nums[k] - 1;
k = temp;
}
}
}
System.out.println(Arrays.toString(nums));

temp = 0;
k = -1;
for(int i = 0; i < nums.length; ++i){

if(nums[i] < 0){
nums[i] = -nums[i] - 1;
}else{
++temp;
if(k == -1)
k = i;
}
}
System.out.println(Arrays.toString(nums) + " k = " + k);

for(int i = nums.length - 1; i >= k; --i){

if(nums[i] != max && nums[i] >= 0){

nums[k] = nums[i];
nums[i] = - k - 1;
while(k < nums.length && nums[k] != max){
++k;
}

}

}
System.out.println(Arrays.toString(nums));

for(int i = 0; i < nums.length; ++i){

if(nums[i] != max && nums[i] >= 0 && nums[nums[i]] < 0){

nums[i] = - nums[nums[i]] - 1;

}

}
System.out.println(Arrays.toString(nums));

return nums;
}

public static void main(String[] args){

Solution sol = new Solution();
int[] nums = new int[]{4, 4, 4, 4, 5, 5, 5, 5};
System.out.println(Arrays.toString(sol.deleteTree(nums, 4)));
System.out.println();
nums = new int[]{4, 4, 4, 4, 5, 5, 5, 5, 1, 1, 9};
System.out.println(Arrays.toString(sol.deleteTree(nums, 5)));

System.out.println();
nums = new int[]{4, 4, 4, 4, 5, 5, 5, 5, 1, 1, 9};
System.out.println(Arrays.toString(sol.deleteTree(nums, 9)));

System.out.println();
nums = new int[]{4, 4, 4, 4, 5, 5, 5, 5, 1, 1, 9};
System.out.println(Arrays.toString(sol.deleteTree(nums, 0)));

}
}
给了几个test，大体正确；空间O(1)，时间O(N)，返回左边>=0的entries。

【在 a*******a 的大作中提到】

: 在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
: 大牛怎么做
: “给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
: 数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
: index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
: 这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
: 杂度，而且大小是确定好的”
: 数组里各个node是打乱的，不是topologically sorted的
: update：
: 举个例子：

f*e2011-07-15 07:07

41 楼

if(ind == nums[ind]) return new int[0];-->错了这个，这不代表root

【在 e********2 的大作中提到】

: public class Solution {
:
: public int[] deleteTree(int[] nums, int ind) {
:
: if(ind == nums[ind]) return new int[0];
:
: int max = Integer.MAX_VALUE;
: nums[ind] = max;
:
: int j, k, temp;

f*e2011-07-15 07:07

42 楼

真没看懂，大牛，求贴code

【在 g******z 的大作中提到】

: 但是在这logn步的追溯过程中，可以有logn个节点被确定是否被删除，等搜到他们的时
: 候就不用再追溯了，相当于确定每一个节点是否被删除只需要常数复杂度，所以应该是
: O(n)没错的
:
: logn

m*a2011-07-15 07:07

43 楼

我也准备问的，看不懂阿，有人可以解释一下吗？

【在 T****U 的大作中提到】

: 你的例子是不是有问题？
: [3,1,4,1,5,7,2,6]
: 删index 1
: 得到
: [x,x,4,x,5,7,2,6] （x代表被删除）
: 最终输出
: [1,2,4,0,3]
: 1的父节点也是1，那它是根节点？
: 4->5->7->6->2->4 这个循环了吧
: 删完最后挪节点也不trivia吧，要重新建立索引关系。

l*32011-07-15 07:07

44 楼

就用recursion, 把是否该删除本节点的信息用函数递归带回来就行了，也不需要
hashmap, 不知道楼上们
为啥有些说的那么复杂。c++程序如下：
// helper function. 其中 parentIndices 是原来记录parent的数组，visited是记录
访问信息，toDelete是记录是否需要删除的信息，target是题目中给的目标节点。
void deleteHelper(vector& visited, vector& toDelete, vector
& parentIndices, int curIndex, int target) {
if (!visited[curIndex]) {
visited[curIndex] = true;
if (curIndex == target) {
toDelete[curIndex] = true;
} else {
deleteHelper(visited, toDelete, parentIndices, parentIndices[curIndex],
target);
if (toDelete[parentIndices[curIndex]) {
toDelete[curIndex] = true;
}
}
}
}
void deleteFunction(vector& parentIndices, int target) {
vector visited(parentIndices.size(), false);
vector toDelete(parentIndices.size(), false);
for (int i = 0; i < parentIndices.size(); i++) {
deleteHelper(visited, toDelete, parentIndices, i, target);
}
}
做完以后，所有该删除的节点都在 toDelete里标记出来了。

l*32011-07-15 07:07

45 楼

楼上是在留言白板里打的，没有缩进，看着有点痛苦不好意思。

s*f2011-07-15 07:07

46 楼

发信人: svcef (svcef), 信区: JobHunting
标题: 你是否愿意通过自学转行成为一个软件工程师
发信站: BBS 未名空间站 (Sat Jun 13 18:23:13 2015, 美东)
(这个机会仅仅适用于位于硅谷南湾的人, 谢谢。 Our office is on Walsh Ave,
Santa Clara. CA, 95050 )
这个帖子，前一阵子，发过一次，由于大家反馈非常好，就再发一次，希望对更
多的朋友有帮助。绝对不收任何费用，我们提供完全免费的转行软件工程师的机会。
这个帖子是写给那些朋友，以前由于各种原因，没能够成为计算机专业学
生，现在愿意通过自学成为一个软件工程师.
这可以做到嘛？
实际上，任何人通过自学成为一个软件编程的高手都不是什么难的事情。只要肯花许
多时间学习和练习，加上有人可以指导答疑, 每个愿意成为软件工程师的人都可以通
过一段时间的学习成为一个不错的软件工程师。
如果你正想成为一个软件工程师，请联系我们。我们能够提供机会帮助你成为一个软
件工程师。绝对不收任何费用。
我们提供一个边工作，边学习的机会。
只有一个要求，希望你现在还有努力学习的动力和勤奋精神。
注1: 许多软件编程的高手都不是计算机专业学生. 举例来说，微软的Bill Gates，
Facebook的Mark Zuckerberg, 都是软件编程的高手，但都不是学计算机专业的. Bill
Gates本来大概要学法律， Mark Zuckerberg本来是心理学专业的。
只要你有真材实料，转行到软件，是不需要一个CS的学位的。
注2: 如果您本身是一个软件工程师，读到这个帖子，请您手下留情，请不要为
“码工”这个职业泼冷水。您也许不知道，有许多人羡慕你的职业呢？正想成为一
个软件工程师？软件工程师, 工作有挑战性，收入也不错。我们就是希望提供机会
给这样的朋友。
注3:　我们这个项目绝对不收任何费用。
注4：我们和硅谷任何别的软件培训，职业培训， bootcamp没有任何关系。
我们也不是这样的一个软件培训，职业培训， bootcamp机构。我们提供的学习
机会是完全免费的。
如果你正在考虑下一个工作方向, 如果你正想成为一个软件工程师，有许多时间可以
用来学习，站内请联系我们。我们能够提供机会帮助你成为一个软件工程师。
关于我们这个项目的说明：
我们是一家初创startup Internet software 公司，这个项目为我们自己公司培养人
才。希望你可以用来学习工作的时间不少于一周至25小时,来我
们位于硅谷南湾的办公室工作。对于有意和我们共同长期把公司做成功的，
公司会发原始股。
我们主要开发Internet software for Enterprise Application，用的语言是：
Python, Java, PHP, MySQL. (不要求你有相关语言和背景，只要求你有强烈意愿学
习)。
技术工作主要做网站server端的开发（包括， Python, Java, PHP, Django, etc)，
也有客户端的开发。客户端的开发包括 web front end 以及手机App和Facebook Apps.
详情, 请站内联系。
请给我们一个机会，也给你自己一个机会。也许这就是你长久等待的一个机会。
(This opportunity is 仅仅限于硅谷南湾, 谢谢, Our office is on Walsh Ave,
Santa Clara. CA, 95050.
如果你不在硅谷南湾，很对不起，我们这个项目不合适你。)
如果您对这个项目不感兴趣，请不要给别人泼冷水。
已经有多人从我们这个项目受益。

c*s2011-07-15 07:07

47 楼

同没看懂这个例子，我画出来也是一个环，有人来解释下么

【在 m******a 的大作中提到】

: 我也准备问的，看不懂阿，有人可以解释一下吗？

s*u2011-07-15 07:07

48 楼

树里面有环，什么鸟例子。不挂才怪。

a*a2011-07-15 07:07

49 楼

例子错了！随手打的！不该有环！

l*82011-07-15 07:07

50 楼

显然是用hash啊，这题在lc顶天算中级吧。。。

【在 a*******a 的大作中提到】

: 在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
: 大牛怎么做
: “给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
: 数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
: index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
: 这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
: 杂度，而且大小是确定好的”
: 数组里各个node是打乱的，不是topologically sorted的
: update：
: 举个例子：

l*n2011-07-15 07:07

51 楼

vector deleteSubtree(vector tree, int index)
{
if (tree.empty() || index < 0 || index >= tree.size())
return tree;
vector visited = vector(tree.size(), false); // Used to
avoid revisit the ancetor path again and again.
// loop through each index in tree. Walking up its ancestor path to a
node that either it is the index to delete or it points to itself (the root)
// Or it is has been visited (cyclic)
for (int i = 0; i < tree.size(); i++)
{
if (!visited[i])
{
stack path;
int p = i;
for (; !visited[p] && p != index && tree[p] != p; p = tree[p])
{
visited[p] = true;
path.push(p);
}
if (!visited[p]) visited[p] = true;
// p is either index or tree[p] is the root or it has been
visited.
if (p == index || tree[p] == -1)
{
// Mark tree[index] to -1 indicating it is deleted.
tree[p] = -1;
// Delete all its children found so far
while (!path.empty())
{
int node = path.top();
tree[node] = -1;
path.pop();
}
}
}
}
// Now we need to compact the tree by removing the holes.

// Count the maximum number of -1's at tree[i]
vector counts(tree.size(), 0);
int count = 0;
for (int i = 0; i < tree.size(); i++)
{
if (tree[i] == -1)
{
count++;
}
counts[i] = count;
}
int i = -1;
int j = 0;
for (; j < tree.size(); j++)
{
if (tree[j] != -1)
{
int p = tree[j];
// Move j to i+1
tree[++i] = tree[j] - counts[p];
}
}
// Remove i+1 to tree.size()-1 from the tree
for (int j = tree.size() - 1; j > i; j--)
{
tree.pop_back();
}
return tree;
}

C*o2011-07-15 07:07

52 楼

hash + stack
hash: key is the parent node, value is the vector of the children nodes
hash can be constructed by traverse the array once. space O(n), time O(n)
stack is used to traverse the subtree. space O(n), time O(n)
Push the first node into stack;
while( stack.size() > 0 ) {
Pop the first node, mark it deleted;
Use the hash to find its children nodes and push them into stack
}

【在 l******8 的大作中提到】

: 显然是用hash啊，这题在lc顶天算中级吧。。。

f*e2011-07-15 07:07

53 楼

看懂了，请接受偶的膜拜

【在 s***f 的大作中提到】

: 发信人: svcef (svcef), 信区: JobHunting
: 标题: 你是否愿意通过自学转行成为一个软件工程师
: 发信站: BBS 未名空间站 (Sat Jun 13 18:23:13 2015, 美东)
: (这个机会仅仅适用于位于硅谷南湾的人, 谢谢。 Our office is on Walsh Ave,
: Santa Clara. CA, 95050 )
: 这个帖子，前一阵子，发过一次，由于大家反馈非常好，就再发一次，希望对更
: 多的朋友有帮助。绝对不收任何费用，我们提供完全免费的转行软件工程师的机会。
: 这个帖子是写给那些朋友，以前由于各种原因，没能够成为计算机专业学
: 生，现在愿意通过自学成为一个软件工程师.
: 这可以做到嘛？

p*n2011-07-15 07:07

54 楼

Idea: time O(n) space O(n)
Keep a size N mark vector to indicate whether to delete a node or not.
1st pass, for each index i, traverse back up to its parent node towards the
root. Keep a stack S of the traversed nodes.
During the traverse until the root, if its predecessor is marked as “keep
” then stop and mark all the nodes in current traversal stack S as “keep
”; if its predecessor is at “the input delete index” or marked as “
delete” then stop and mark all the nodes in current stack as “delete”.
2nd pass, keep a new index mapping vector of size N to get new index for
each remaining node.
3rd pass, move the remaining nodes to a new vector
------------
#include
#include
using namespace std;
class Solution{
public:
vector deleteSubTree(vector& tree, int deletePos){
vector trimmedTree;
if(tree.empty() || deletePos>=tree.size()) return trimmedTree;

vector travNodes;
vector treeMark(tree.size(), 'u'); //unknown state
treeMark[ deletePos ] = 'd';//mark the input delete pos as delete
for(int i=0; iif( treeMark[i] != 'u' ) continue;
else{
travNodes.clear();//start a new upwards traverse
int current=i;
while( treeMark[ current ]=='u') {
travNodes.push_back( current );
if( tree[ current ] == current ) break;//reach root
current = tree[ current ] ; //up to its parent
}
if( treeMark[ current ]=='d' ) {
for(int k=0; ktreeMark[ travNodes[k] ] = 'd';
}
else {
for(int k=0; ktreeMark[ travNodes[k] ] = 'k';
}
}
}
vector newIdxMap(treeMark.size(), -1);
int totalDelete=0;
for(int i=0; iif( treeMark[i]=='d' ) totalDelete++;
newIdxMap[i]= i - totalDelete;
}

for(int i=0; iif( treeMark[i] != 'd')
trimmedTree.push_back( newIdxMap[ tree[i] ] );
}
return trimmedTree;
}
};
int main() {
// your code goes here
int treeArray[]={3,1,4,1,5,7,6,6};
vector tree(&treeArray[0], &treeArray[0]+8);
Solution mysol;
vector result;
result = mysol.deleteSubTree(tree, 1);

for(int i=0; icout<}
cout<return 0;
}
-----
Success time: 0 memory: 3460 signal:0
1 2 4 3 3

【在 a*******a 的大作中提到】

: 在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
: 大牛怎么做
: “给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
: 数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
: index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
: 这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
: 杂度，而且大小是确定好的”
: 数组里各个node是打乱的，不是topologically sorted的
: update：
: 举个例子：