w********g
发帖数: 106 | 1 就一道题目没见过，就不说具体是三家中的哪家了。
要求先根遍历一棵树。
不是binary tree。
每个parent都可以有很多children。各个parent的children数目可以不同。
node不知道自己的sibling。没有指向sibling的指针。
parent自己存了一个链表，里面是指向所有children的指针。
这棵树有几百万个node，所以不能一次pre-order travel完，因为内存不够大。
所以需要分多次遍历。
第一次从root开始pre-order遍历100个node，然后记住这第100个node的位置。
第二次就直接从第100个node开始先根遍历。
第三次就直接从第200个node开始先根遍历。。。
知道所有node都遍历完。
这里的第100、200个node是指：如果一次性把所有的几百万个node都先根走完的话所碰
到的第100、200个node。
所以题目就是问如何多次分块遍历一棵树。
要求用递归写，但是可以使用stack。
我想了想觉得很复杂，然后就跪了。 |
|
C******x
发帖数: 91 | 2 恩, 接口清晰很多了,正在临摹中。。。 多谢指教！
具体到算法，
对于没有parent指针的tree，
对于++运算符 , 两个方案，
1 迭代器中维护一个栈，好处是遍历一次的复杂度是O(n)， 坏处是空间， 如果是后
缀加加， 每次都要复制一遍栈~ 如果不小心用后缀++遍历, 实际复杂度是O(n^2)，用
前缀++没有
这个问题, 复杂度还是O(n)
2 每次++，都调用next函数，要么找右子节点的最小值，要么从root找起，找到下一
个节点~ 最坏复杂度还是O(n^2)
另外，如果还是--， 还得额外维护一个栈~
对于有parent指针的tree
方便的找next就好了，遍历一遍的平均复杂度应该是O(n)~ 最坏的情况下貌似也是O(
n)[不是非常确定]
问题:
知道板上有人面试面到这个题，貌似还是高频
请问到底到写到什么程度，要求所有的接口，然后写出上面的那种case啊？
网上找到一些代码，正在修改~
感觉如果真要写清楚，还要定义Node，BSTree, 然后才能定义Iterator， 不仅仅是单
纯的非递归中序遍历二叉树~
了。 |
|
r*******h
发帖数: 315 | 3 感觉树像文件系统的目录结构，企业环境中数百万个文件和目录的文件系统太常见了，
要求的前序遍历像unix命令tree。关键是如果栈溢出时，就得把栈的内容写入磁盘，比
如一次写一个文件，栈空的时候再按后写先读的顺序把文件一个个读入栈进行处理，其
余就是典型的前序遍历的算法。还可以考虑多线程双缓冲，这样遍历和栈的磁盘读写都
可以同时进行了。 |
|
b******u
发帖数: 469 | 4 递归？
遍历(a1-an) = a1 U 遍历(a2-an) U 遍历(a2-an) |
|
b***y
发帖数: 2799 | 5 ☆─────────────────────────────────────☆
CplusplusFan (C++ Fan) 于 (Sat Sep 27 17:45:03 2008) 提到:
最近在看binary search tree,在遍历概念上还是不太明白，
是不是pre-order，in-order和post-order都是属于DFS(深度优先)遍历，
而BFS(广度优先)则是另外一类遍历?
☆─────────────────────────────────────☆
CrendKing (Crend King) 于 (Sat Sep 27 22:46:32 2008) 提到:
对。DFS递归地访问每一个非叶节点的左子树，然后是又子树。BFS则是从左到右按层来
访问的。
☆─────────────────────────────────────☆
gandalf2008 (修练神功~) 于 (Tue Sep 30 22:02:11 2008) 提到:
dfs is very similar to pre-order
以下是附件内容: |
|
b***i
发帖数: 3043 | 6 纠正了：先描述一下树：
一个多叶子的树，每个节点有多个下层节点。每一个节点也有一个指针指向同层下一个
节点。这个图无法看，可以复制到notepad上看
1--2--3--4
| | | |
| | | 5
| | | |
| | | 6
| | |
| | 7--8
| | |
| | 9
| | |
| | A
| |
| B--C--D
| | |
| | E
| |
| F--G
| |
| H
|
I--J--K--L
如果要遍历1-2-3-4-5-6-7-8-9-A-B-C-D-E-F-G-H-I-J-K-L，并且进行处理则有如下程序
traverse(head){
if (head->needed){
action(head);
wait(50);
if (quit) return;
if (head->deeper)
traverse(head->de... 阅读全帖 |
|
d*****a
发帖数: 38 | 7 这应该和如何遍历没关系，总之就是遍历所有叶结点才能得到深度。 |
|
t*****j
发帖数: 1105 | 8 对于遍历二叉树的复杂度，一直有疑问。
先根遍历应该是O(n)吧，中根和后根呢？ |
|
h*********3
发帖数: 111 | 9 以前我的理解是hash表没有遍历一说。但sgi的实现有iterator.
是所有的hash_map实现都提供了iterator吗？
这个iterator是如何遍历的呢？复杂度是多少？ |
|
s*******3
发帖数: 22 | 10 题目要求用递归。直接iterative的话就不需要考虑call stack了不是吗？
也就是说，递归遍历前100个，遍历的同时要把上层的点(也就是你的call stack) 储存
到stack里。
结束第一次递归后释放了call stack内存，然后接着递归第101~200。
这时候就需要用到stack，不然你现在的call stack是空的，你不知道你上次递归调完
后call stack里有什么。 |
|
p**o
发帖数: 3409 | 11 “内存都够大。只是打印机的内存不够大，不能一次把所
有的node都存在打印机内存里，所以需要分批次打印。” 是什么意思？
整棵树在不在内存里？
如果在内存里，那么把遍历过程简单地写成迭代器，
每次不就可以从上次暂停的地方继续遍历和打印了？
是不是树太大要放磁盘上，每次只能载一部分到内存里，而你没有理解题意？ |
|
f******i
发帖数: 82 | 12 标准dfs遍历，也可以用queue做标准bfs遍历，这些都是基础，建议楼主多做点题
stack |
|
g*****y
发帖数: 94 | 13 C语言的题，对C语言不是很熟，如果下面的有语法错误的话，还请谅解。对树进行中序
遍历，initial代码如下：
void inorder(TreeNode* root) {
LABEL:
if (root == NULL) {
return;
}
// Left subtree
inorder(root->left);
// Print value
printf("%dn", root->val);
// Right subtree
root = root->right;
goto LABEL;
}
其实上面的代码对于右子树来说就是变相的recursive调用，面试官要求如何用些代码
来取代"goto LABEL;"这句，然后写些iterative的代码来实现这个中序遍历。其实要求
就是怎么做到左子树recursive，右子树iterative。怎么破这个？ |
|
z*********n
发帖数: 1451 | 14 lz标题应该叫最少点，不是最小点吧。。
读了3遍lz算法才猜出来题目是啥。是说最少需要几个起点，就能dfs遍历一个有向图的
所有点，是这意思吗？
如果是这个意思，那应该确实跟SCC没啥关系，反例很简单。一个图:A->B。这里有俩
SCC，但一个root A就能遍历全图。
如果我没理解错lz意思，那下面这么做应该就行了，不需要什么union find，写起来多
麻烦。
1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root。 |
|
发帖数: 1 | 15 大概懂你意思了，第一遍dfs遍历，类似于做了个toposort，因为第一遍时候你无法确
定没有visited的点是一个新的起点还是一个在path上的点
第二遍遍历的时候因为已经toposort过了。没有visited的点肯定是一个新的起点。
这个好厉害。。。 |
|
m********o
发帖数: 796 | 16 【 以下文字转载自 Linux 讨论区 】
发信人: momoxinduo (馍馍), 信区: Linux
标 题: 弱弱的问个内核遍历当前进程的子进程的一小段程序
发信站: BBS 未名空间站 (Wed Aug 21 01:23:39 2013, 美东)
linux内核里遍历当前进程的子进程的一小段程序有点看不太明白
struct task_struct *task;
struct list_head *list;
/* 这里的 struct list_head 的定义是两个指向他自己的指针
* struct list_head
* {
* struct list_head *next, *prev;
* }; */
/* 下面的list_for_each宏定义
*list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list. */
... 阅读全帖 |
|
b***y
发帖数: 2799 | 17 ☆─────────────────────────────────────☆
chaomian (超大碗牛肉面) 于 (Wed Jul 9 23:19:28 2008) 提到:
条件是不许用指针来遍历...
面试官是一个印度阿三
还问我Patricia tree..., 没搞过, 郁闷
☆─────────────────────────────────────☆
repast (xebec) 于 (Wed Jul 9 23:27:17 2008) 提到:
call 某个 function, 这个 function 替你遍历也行吧？
☆─────────────────────────────────────☆
Tevez99 (野兽99) 于 (Wed Jul 9 23:34:52 2008) 提到:
strlen???
☆─────────────────────────────────────☆
Tevez99 (野兽99) 于 (Wed Jul 9 23:36:02 2008) 提到:
glibc那个strlen用汇编实现的s |
|
w******t
发帖数: 241 | 18 【 以下文字转载自 CS 讨论区 】
发信人: webcraft (此处不留爷，自有留爷处；处处不留爷，爷), 信区: CS
标 题: 怎样遍历一个字母的组合
发信站: BBS 未名空间站 (Sun Nov 1 23:14:45 2009, 美东)
比如我现在有n个字母（n未知但是有限）a,b,c,d,e,....xx.
想写一个程序遍历这些字母的所有组合。比如ab,ac,ae,abc,abcde,abcdfg,bdefg....
etc.有没有什么好的方法写这个程序？谢谢 |
|
w****o
发帖数: 2260 | 19 【 以下文字转载自 JobHunting 讨论区 】
发信人: winhao (勇敢的人), 信区: JobHunting
标 题: 问一下STL里的queue, and stack 遍历的问题
发信站: BBS 未名空间站 (Sun Mar 4 02:36:31 2012, 美东)
好像std里queue 和stack的实现没有提供iterator,怎么遍历呢？就是说怎么查看queue
,stack里的elements?
感觉没法弄。比如queue,除非把queue给弄散了，一个一个的 front(), pop(),来查看
里面的东西，可是这样的话，queue就给破坏了。
stack也有同样的问题。
谁给说说有什么好的方法？难道要自己新创造一个实现？
谢谢！ |
|
c*********e
发帖数: 16335 | 20 按层遍历二叉树,无非就是把每个节点当作数组arr里的一個元素，一個index对应一個
节点。比如根节点index=０ (2的０次方 减 1）,第二层的最左边那个节点index=1 (2
的一次方 减 1）,第三层的最左边那个节点的index=3 (2的二次方 减 1 ）第四层的最
左边那个节点的index=7 (2的三次方 减 1）,etc.
所以，第一层就是arr[0]; (最左边节点index 0 为 2的０次方 减 1）
第二层就是arr[1]，arr[2]; (最左边节点index 1 为 2的1次方 减 1，最右边节点
index 2 为 下一层第一個节点的index（值为3） 减 1）
第三层就是arr[3]，arr[4],arr[5],arr[6]; (最左边节点index 3 为 2的2次方 减 1
，最右边节点index 6 为 下一层第一個节点的index（值为7） 减 1）
etc.
这样就可以按层遍历了。 |
|
s*******i
发帖数: 712 | 21 Why? 这种遍历空间复杂度怎么算的？如果说recursive的话，没有临时变量，算call
function的
次数也是每个node上都被调用过一次function, 空间也算O(n)吧。 |
|
r****o
发帖数: 1950 | 22 非递归求二叉树的高度，可以用按层次遍历的方法，层数就是高度。
还有其他方法可以非递归求二叉树高度吗? |
|
r****o
发帖数: 1950 | 23 然后pre-order遍历？
如果不改动节点数据结构的话，有什么方法可行吗? |
|
r**d
发帖数: 316 | 24 这个和实现有关，java.util.hashmap的办法是在array里面找下一个非空元素，这应该
是个链表头，然后再遍历链表。 |
|
d*******l
发帖数: 338 | 25 感觉这俩不大能类比。preorder遍历可以通过dfs来实现，不过dfs里是先处理左儿子还
是右儿子还是先输出节点都是随意的 |
|
C***y
发帖数: 2546 | 26 所有的bucket查一遍好像效率太低了
在考虑多线程 access的情况下，有啥好的遍历的方法吗？
谢谢 |
|
w**z
发帖数: 8232 | 27 遍历不是全查一遍嘛？
一般情况，HashTable是做查找用。 |
|
C***y
发帖数: 2546 | 28 是全查一遍
但是hashtable里面很多bucket是空的
如果避免在遍历的时候去查这些bucket |
|
w****o
发帖数: 2260 | 29 好像std里queue 和stack的实现没有提供iterator,怎么遍历呢？就是说怎么查看queue
,stack里的elements?
感觉没法弄。比如queue,除非把queue给弄散了，一个一个的 front(), pop(),来查看
里面的东西，可是这样的话，queue就给破坏了。
stack也有同样的问题。
谁给说说有什么好的方法？难道要自己新创造一个实现？
谢谢！ |
|
|
h*****r
发帖数: 73 | 31 queue 和 stack 本来就不该支持遍历。
queue |
|
d****o
发帖数: 1055 | 32 queue和stack就不是用来遍历用的
queue |
|
L***Q
发帖数: 508 | 33 想遍历的话可以自己用2个stack或者2个queue倒腾。 |
|
C******x
发帖数: 91 | 34 卡了一阵子了
知道这里藏龙卧虎, 跪求一个bst中序遍历 c++ class iterator代码参考
也可以私信我, 还请不吝赐教
写了很多次, 但是对于c++迭代器还是不熟悉, c++想写好着实不容易 汗
我写成下面这样, 看起来有点像java的(不对也请指出), c++的该怎么写啊, 跪求指导
和意见
class BSTreeInorderIterator
{
private:
stack st;
public:
BSTreeInorderIterator(BSTNode* root)
{
push_left(root);
}
bool hasNext()
{
return !st.empty();
}
BSTNode* next()
{
BSTNode* node = st.top();
st.pop();
push_left(node->right);
return node;
... 阅读全帖 |
|
b***p
发帖数: 700 | 35 这个是python solution, worst case 是O(n^2). 比普通的Greedy Solution, 有两个
改进
1. 计算bit map of word, and AND operation to check if there is common char
2. 遍历是从最长的word开始
还有一个可以改进的地方是，利用元音字母，用word_len+vowel 作key，减少不必要
的compare
class DiffWordsMaxLenProduct:
def __init__(self):
# dict: word -> word char bit map
self.dict_word_bit = {}
# dict: word_len -> [word1, word2, word3...]
self.dict_word_len = {}
#
# compute the bit map of word char
#
def bit_word(self... 阅读全帖 |
|
i**********n
发帖数: 196 | 36 假设忽略大小写，那么可以建一个n*26的bitmap矩阵。然后遍历各列，去除overlap的
word，这需要o（n）。
剩下的word都是互不overlap的，那么可以在线性时间内找到长度最大的两个word，返
回之。
整体的复杂度还是o（n） |
|
b****z
发帖数: 176 | 37 leetcode的一道题目，树的中序遍历，用普通的方法可以跑过。
但是网上看到有人用Threaded Binary Tree 。感觉这已经比较难了，像这样的问题
Threaded Binary Tree ， 在准备interview的时候需要掌握吗？ 会不会超过难度？ |
|
b****z
发帖数: 176 | 38 用queue 做树的广度优先遍历，空间复杂度是多少？
感觉好像不是O(n), 应该会比O(n)小？ 因为 空间复杂度应该是 树的底部的节点的数
量，因为每次都会dequeue。
大家觉得呢？ |
|
w********g
发帖数: 106 | 39 这个方法没有用递归。题目要求必须用递归才行。我觉得这才是最难的地方。如果用
iteration，一个for循环就能实现向右的移动。可是如果必须用递归，怎么解决递归向
右和依靠push右侧兄弟导致的重复呢？
我的解决办法是：
任何一个node都只向下递归打印第一个child；
除了叶子以外，任何node都不向右递归自己的sibling；
只有叶子才向右侧递归打印；
只有当前node没有右侧的sibling时才递归打印栈顶的node，
这个栈顶的node其实就是当前node的先根遍历时的next node。
很多特殊情况还没考虑，但是大意就是这样。明天写一下code。 |
|
p**t
发帖数: 157 | 40 取决于你哪种遍历方法
后序最麻烦 先序最简单
stack |
|
p**t
发帖数: 157 | 41 不会用栈遍历二叉树的 你让他用栈做DFS不是更不会。。。 |
|
p**t
发帖数: 157 | 42 先序会写吧？
先访问右子树的先序会不会写？
先访问左子树的后序遍历
就相当于先访问右子树的先序的结果做一个反序。。。
当然面试的时候我不建议你这么做 因为这显然不是考你的人想要的答案
到时候人家要你不反转的做你还是得老老实实的写。。。 |
|
发帖数: 1 | 43 准备一个一维数组存每个点的parent，另外一个一维数组记录是否访问过。
先找in-degree = 0的点，然后dfs，遍历时候记录每个点的parents，记录访问情况
如果是环，任意取一点dfs，同样记录每个点的parents，记录访问情况
最后用union find 找到最终root，然后数不同root的个数。
这样方法是否可行，看到有人说必须用strong-connect component，不知为何，还望举
例说明 |
|
w******t
发帖数: 241 | 44 比如我现在有n个字母（n未知但是有限）a,b,c,d,e,....xx.
想写一个程序遍历这些字母的所有组合。比如ab,ac,ae,abc,abcde,abcdfg,bdefg....
etc.有没有什么好的方法写这个程序？谢谢 |
|
n******t
发帖数: 4406 | 45 这就是标准的list 遍历，有什么问题么？无非写成了宏省事而已。 |
|
b******y
发帖数: 9224 | 46
是的，但底层Hashtable的实现，这个也要搞清楚。否则你就不知道如何优化。所以，
我总觉得算法和数据结构，还是值得不断研究的。
就这个遍历hashtable的问题来说，很明显的，就是直接iterate过array是最佳方案。
因为不用做hash的数学运算了。
否则，如果你拿出来所有的key, 程序必然要做hash数学运算，来找到hash到哪个位置
，当然不efficient了。 |
|
h****g
发帖数: 772 | 47 就是干这个事，我不会怎么写这个遍历？只好这么土土地干，谁能帮我走到任意深的目
录去make
clean呀
#!/bin/bash
for dir in `ls -l|grep ^d |awk '{print $NF}'`
do
cd $dir
for dir in `ls -l|grep ^d |awk '{print $NF}'`
do
cd $dir
for dir in `ls -l|grep ^d |awk '{print $NF}'`
do
cd $dir
for dir in `ls -l|grep ^d |awk '{print $NF}'`
do
cd $dir
if [ -f Makefile ];
then
pwd
make clean
... 阅读全帖 |
|
m********o
发帖数: 796 | 48 linux内核里遍历当前进程的子进程的一小段程序有点看不太明白
struct task_struct *task;
struct list_head *list;
/* 这里的 struct list_head 的定义是两个指向他自己的指针
* struct list_head
* {
* struct list_head *next, *prev;
* }; */
/* 下面的list_for_each宏定义
*list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list. */
#define list_for_each(pos, head)
for (pos = (head)->next; prefetch(pos->next), pos != (head); pos =
pos->next) ... 阅读全帖 |
|
d*****i
发帖数: 44 | 49 工作中遇到一个难题,请高手指教.
条件:只有一个coredump，gdb,我可以找到coredump中binary tree的root
使用gdb中的command,convenience variable可以支持简单的variable,loop,if else.
但是不支持array,而且没有stack（all variable are global).
请问如何遍历？不管效率。谢谢 |
|
r******9
发帖数: 129 | 50 用iterator遍历一个vector
然后当某个元素符合某种条件时，删掉这个元素
我一直想这么干
vector ::iterator iter = vec.begin();
while(iter != vec.end())
{
if(test(iter->content) == true)
{
vec.erase(iter);
}
++iter;
}
但是这样肯定不行，好像不能再循环体内改变vector
我现在的解决办法就是吧要删的元素的index记下来，然后再对这个index做循环，逐个
删。
高手们有没有好的办法啊？
谢谢啦 |
|
