|
g*********e
发帖数: 14401 | 2 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
意思差不多。有了traversal，iterator就不难写。 |
|
j******2
发帖数: 362 | 4 比如binary search，两种都可以，用iteration会不会快点？
比如binary search in rotated array, 只能用recursion。
大家说说是不是这个理儿？
菜鸟问题，见笑了。 |
|
|
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
iterator 是immutable的吧？ |
|
|
j*****y
发帖数: 1071 | 16 这样的话，你这里的 iterator 也提供了 pop()操作，也是改变了，是吧？ |
|
j*****y
发帖数: 1071 | 17 明白了，你的这个 iterator就是一个没有 push操作的 stack, 是吧？ |
|
p*****2
发帖数: 21240 | 18
感觉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 没有见过详细的原题，感觉是应该是要求实现嵌套map的Iterator，做过的面过的大侠
讲讲吧 |
|
s**x
发帖数: 7506 | 24 这个是不是跟那个 vector of vector 的 iterator 类似？
我被问过， 当时直接就晕菜了。 |
|
l*****a
发帖数: 14598 | 25 实话实说,这题真的没必要考虑design pattern
2爷你还不了解,什么东西学了就想用用,都想往上面靠
学了dynamic P 就什么都用DP
学个scala什么都是scala
....
当然iterator本身就是23种DP之一吧 |
|
|
A**u
发帖数: 2458 | 27 别人的面经
一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法 |
|
s*****r
发帖数: 43070 | 28 每遇到一个Map都建一个iterator，用stack保存 |
|
w***y
发帖数: 6251 | 29 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 iteration有什么好解法吗？
N重循环还是next permutation？ |
|
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;
... 阅读全帖 |
|
w**x
发帖数: 362 | 35 The next() should be operator() ++
No GetIter() function.
No iter in class. |
|
w**x
发帖数: 362 | 36 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 不牛，你自己可以按我说得去一个一个写。需要有个iter in private. |
|
w******j
发帖数: 185 | 38 来个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 恩, 接口清晰很多了,正在临摹中。。。 多谢指教！
具体到算法，
对于没有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 这个binary tree iterative traversal 的codes 貌似不对，再仔细看看 |
|
n****e
发帖数: 678 | 47 你太客气了，不用抱歉哈 :)
这个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 这道题目好像有好几个版本，你确认可以直接拿ArrayList的Iterator吗？
好像见过一个Generic的 linked list,每个Node 有 down 和 next.
不过基本上用到Stack是必须的。
0, |
|
p*u
发帖数: 136 | 49 电面写的这段代码，过了。
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 想了一下，这个问题好像不是那么容易。楼主的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 ... 阅读全帖 |
|
