由买买提看人间百态

topics

全部话题 - 话题: iteration
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
z*********8
发帖数: 2070
g*********e
发帖数: 14401
2
来自主题: JobHunting版 - binary tree的in-order iterator怎么写?
iterative inorder traversal without visited flag
void in_order_traversal_iterative(BinaryTree *root) {
stack s;
BinaryTree *current = root;
while (!s.empty() || current) {
if (current) {
s.push(current);
current = current->left;
} else {
current = s.top();
s.pop();
cout << current->data << " ";
current = current->right;
}
}
}
p*****2
发帖数: 21240
3
来自主题: JobHunting版 - binary tree的in-order iterator怎么写?

意思差不多。有了traversal,iterator就不难写。
j******2
发帖数: 362
4
比如binary search,两种都可以,用iteration会不会快点?
比如binary search in rotated array, 只能用recursion。
大家说说是不是这个理儿?
菜鸟问题,见笑了。
d******i
发帖数: 76
5
其实在面试的时候主要看考官,他的考察点在哪里
递归的特点就是代码简洁,容易理解,但是实际应用中可能会有诸多问题出现,比如
stack overflow等。
用递归实现的大都可以用遍历来实现,遍历实现代码一般会复杂些,但是在复杂度相同
的前提下,遍历的执行效率会较递归高些。
binary search in rotated array 这道题可以用iteration实现
http://www.leetcode.com/2010/04/searching-element-in-rotated-ar
f*********m
发帖数: 726
6
请大家推荐recursion以及把recursion转变为iteration的资料。
谢谢。
b***m
发帖数: 5987
7

嗯,比如binary tree的post order traversal用iterative就很麻烦。
f*********m
发帖数: 726
8
据说所有recursion都有对应的iteration,但有的不好转变。
说是可以用stack模拟递推过程,但有很多细节要结合具体的题,这就不好搞了。
H**********y
发帖数: 7928
9
这个,我觉得需要慢慢琢磨
看到一个题,recursion的,就想怎么变,实在想不明白,就放狗

请大家推荐recursion以及把recursion转变为iteration的资料。
谢谢。
R**y
发帖数: 72
10
题目如下,要求recursive 和 non recursive解法
write a program that given a 7 digit telephone number, could print all
possible combinations of letters that each number could represent.
second part: if the telephone number changes to 12 digits one
recursive 解法很清晰,建立一个字典,然后递归就好了。
iterative 解法,我就卡住了,google了一下,有一个解法如下:
private static ArrayList processOneNumber(ArrayList input, int[] phoneNum,
int currentNum) {
ArrayList output = new ArrayList();
int numberToProcess = phoneNum[currentNum];
char c;
... 阅读全帖
c********t
发帖数: 5706
11
我用两个stack, DFS比较,可是因为null无法进入stack,每次人前都要一堆if判断比较
,感觉很差。
有没有好点的iterative的解法?
多谢!
c********t
发帖数: 5706
12
我用两个stack, DFS比较,可是因为null无法进入stack,每次人前都要一堆if判断比较
,感觉很差。
有没有好点的iterative的解法?
多谢!
o*******1
发帖数: 2
13
class Solution {
public:
bool isSymmetric(TreeNode *root) {
std::vector stack, buf;
std::vector::iterator it, ite;
if (!root)
return true;
stack.push_back(root->left);
stack.push_back(root->right);

while (stack.size()) {
if (stack.size() % 2)
return false;

it = stack.begin();
ite = it + 1;
while (it < stack.end()) {
... 阅读全帖
p*****2
发帖数: 21240
14
来自主题: JobHunting版 - iterator 实现 如何 peek(),pop()?

iterator 是immutable的吧?
p*****2
发帖数: 21240
15
来自主题: JobHunting版 - iterator 实现 如何 peek(),pop()?

我记得只能iterate不能改变吧
j*****y
发帖数: 1071
16
来自主题: JobHunting版 - iterator 实现 如何 peek(),pop()?
这样的话,你这里的 iterator 也提供了 pop()操作,也是改变了,是吧?
j*****y
发帖数: 1071
17
来自主题: JobHunting版 - iterator 实现 如何 peek(),pop()?
明白了,你的这个 iterator就是一个没有 push操作的 stack, 是吧?
p*****2
发帖数: 21240
18
来自主题: JobHunting版 - iterator 实现 如何 peek(),pop()?

感觉iterator和stack还不是一回事。
不过这个题目的定义比较confusing
应该是hasNext, next比较好。
h*********o
发帖数: 230
19
Implement peek() and pop() from java iterator().
for example [1,2,3,4,5], peek() = 1, pop() = 1, peek() = 2, peek() = 2, pop(
) = 2
p*****2
发帖数: 21240
20
class MyIterator[T](it:Iterator[T]){
private[this] var curr:T=_
private[this] var has=false

def peek():T={
if(has) return curr
if(it.hasNext){has=true; curr=it.next; curr} else null.asInstanceOf[
T]
}

def pop():T={
if(has) has=false; return curr
if(it.hasNext) it.next else null.asInstanceOf[T]
}
}
j******2
发帖数: 362
21
题不难,但是只会recursive解,有没有大牛给个iterative解啊?谢了。
l**h
发帖数: 893
22
好像FB考过,一时找不到了。
一个嵌套Map,就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。
n****r
发帖数: 120
23
来自主题: JobHunting版 - 讨论一道题:deep iterator
没有见过详细的原题,感觉是应该是要求实现嵌套map的Iterator,做过的面过的大侠
讲讲吧
s**x
发帖数: 7506
24
来自主题: JobHunting版 - 讨论一道题:deep iterator
这个是不是跟那个 vector of vector 的 iterator 类似?
我被问过, 当时直接就晕菜了。
l*****a
发帖数: 14598
25
来自主题: JobHunting版 - 讨论一道题:deep iterator
实话实说,这题真的没必要考虑design pattern
2爷你还不了解,什么东西学了就想用用,都想往上面靠
学了dynamic P 就什么都用DP
学个scala什么都是scala
....
当然iterator本身就是23种DP之一吧
s*******u
发帖数: 220
A**u
发帖数: 2458
27
来自主题: JobHunting版 - 问道题目 Map的iterator
别人的面经
一个嵌套Map, 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
s*****r
发帖数: 43070
28
来自主题: JobHunting版 - 问道题目 Map的iterator
每遇到一个Map都建一个iterator,用stack保存
w***y
发帖数: 6251
29
来自主题: JobHunting版 - 问道题目 Map的iterator
ok 这个是不是更general的solution? 就是做成一个iterator的样子,可以支持
hasNext() getNext()
如果只是要遍历,是不是可以写成recursive就行了? 遇到map就继续NestedIterator?
j****y
发帖数: 684
30
但是很多recursion 很简单,但iterative的可不好写
r*********n
发帖数: 4553
31
简单的recursion可以转换为iterative解法,遇到复杂的,等你想出来,面试时间都没
了。
比如hanoi tower, sudoku
n*****o
发帖数: 849
32
我怎么记得我本科学的时候,汉诺塔的recursion到iteration转换属于简单类里面的?
r**h
发帖数: 1288
33
来自主题: JobHunting版 - 晕了,有人用iteration解n queens么
iteration有什么好解法吗?
N重循环还是next permutation?
C******x
发帖数: 91
34
来自主题: JobHunting版 - bst中序遍历c++ class iterator
卡了一阵子了
知道这里藏龙卧虎, 跪求一个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;
... 阅读全帖
w**x
发帖数: 362
35
来自主题: JobHunting版 - bst中序遍历c++ class iterator
The next() should be operator() ++
No GetIter() function.
No iter in class.
w**x
发帖数: 362
36
来自主题: JobHunting版 - bst中序遍历c++ class iterator
your code is not C++, but C.
No constructor.
No operator()++.
No destructor.
No current iter.
why void PushLefts(NODE* pNode) ?
Left is left not lefts.
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet... 阅读全帖
w**x
发帖数: 362
37
来自主题: JobHunting版 - bst中序遍历c++ class iterator
不牛,你自己可以按我说得去一个一个写。需要有个iter in private.
w******j
发帖数: 185
38
来自主题: JobHunting版 - bst中序遍历c++ class iterator
来个java的吧,带parent pointer和不带的,preorder和inorder的
import java.util.NoSuchElementException;
import java.util.Stack;
public class BST {
private Node root;
private static class Node {
int key;
Node left, right, parent;
Node(int key) {
this.key = key;
}
}
public BST(){

}

public BSTIterator inorderIterator() {
return new InorderIterator();
}
public BSTIterator preorderIterator() {
return new PreorderI... 阅读全帖
C******x
发帖数: 91
39
来自主题: JobHunting版 - bst中序遍历c++ class iterator
恩, 接口清晰很多了,正在临摹中。。。 多谢指教!
具体到算法,
对于没有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, 不仅仅是单
纯的非递归中序遍历二叉树~

了。
s**x
发帖数: 7506
40
能有人说说这个原题是怎么问得吗? 我曾被问过 vector of vector 的 iterator.
现在也不是很清楚该怎么做。
u*****o
发帖数: 1224
41
你已经好厉害了啊。。当场写iterator很难的啊。。。我看懂别人的答案都费牛劲,更
别说当场写了。。。加油!offer不远了!!
w******j
发帖数: 185
42
来个java的吧,带parent pointer和不带的,preorder和inorder的
import java.util.NoSuchElementException;
import java.util.Stack;
public class BST {
private Node root;
private static class Node {
int key;
Node left, right, parent;
Node(int key) {
this.key = key;
}
}
public BST(){

}

public BSTIterator inorderIterator() {
return new InorderIterator();
}
public BSTIterator preorderIterator() {
return new PreorderI... 阅读全帖
c********p
发帖数: 1969
43
iteration有啥比recursion的好处?
c********p
发帖数: 1969
44
遍历不是要用个stack 么?

iterator
c********p
发帖数: 1969
45
这题目到底有多少解法啊。。。
请教一下这个非recursion非iteration的解法是神马啊!
n****e
发帖数: 678
46
来自主题: JobHunting版 - 问tree的iterative traversal
这个binary tree iterative traversal 的codes 貌似不对,再仔细看看
n****e
发帖数: 678
47
来自主题: JobHunting版 - 问tree的iterative traversal
你太客气了,不用抱歉哈 :)
这个codes还是不对,你是想写post-order iterative traversal吧
你试着run这个test:
1
2 3
4 5 6 7
这个condition: if(!node->right && !node->left) 对node 2, node 3 不work
P*******r
发帖数: 210
48
来自主题: JobHunting版 - 小弟求问LinkedIn那道Deep Iterator的题
这道题目好像有好几个版本,你确认可以直接拿ArrayList的Iterator吗?
好像见过一个Generic的 linked list,每个Node 有 down 和 next.
不过基本上用到Stack是必须的。

0,
p*u
发帖数: 136
49
来自主题: JobHunting版 - 小弟求问LinkedIn那道Deep Iterator的题
电面写的这段代码,过了。
class Collection
{
public:
T next() {

if (_type == 0)
{
if (_index == 0)
{
_index++;
return _value
}
else
{
throw Exception;
}
}
else
{
while (_index < buckets.size())
{
if (_buckets[_index].hasN... 阅读全帖
D*T
发帖数: 75
50
来自主题: JobHunting版 - 小弟求问LinkedIn那道Deep Iterator的题
想了一下,这个问题好像不是那么容易。楼主的code如果末尾有个空的List会出错。我
不太懂C++所以pdu的只是半懂,不过感觉我的想法和ta估计差不多。moridin的code很
神奇,我实在看不太懂。
下面是我的code,搞ArrayList还成,搞LinkedList可能就惨了。另外remove好像是ok
的。
import java.util.*;
class ArrayPosition {
ArrayList array;
int index;
ArrayPosition(ArrayList array) {
this.array = array;
index = 0;
}
Object peekItem() {
return array.get(index);
}
Object takeItem() {
return array.get(index++);
}
}
public class DeepIteratorII implements ... 阅读全帖
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)