d**s
发帖数: 98 | 1 非常规的解法：
http://blog.csdn.net/anchor89/article/details/6055412
经典面试题:设计包含min函数的栈,O(1)空间实现方法
分类： 数据结构和算法 2010-12-04 22:20 2102人阅读 评论(10) 收藏 举报
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数
min、push以及pop的时间复杂度都是O(1)。
注:这是06年一道Google的面试题.
先来说个常规解和他的一个优化,常规解的时间复杂度符合要求,但需要线性的额外空间.
常规解(参考 http://zhedahht.blog.163.com/blog/static/25411174200712895228171/):
除了题目要求的栈之外新开一个栈,用来记录最小值,每当在原栈中push数据后,与最小
值栈中的栈顶元素比较,如果新值较小,则在最小值栈中push新值;否则再次push栈顶元
素.
pop的时候,只要将最小值栈也pop一下就行了.
这样,min函数只需要返回最小值栈的栈顶元素即可.
常规解空间上的一个优化:
一般... 阅读全帖 |
|
j**l
发帖数: 2911 | 2 要求inplace对栈内的元素重新排序，你可以使用的方法
Push
Pop(不返回值)
Top
IsEmpty
是否应该递归，利用操作系统的隐含堆栈空间，得到一个伪inplace的算法？
假定栈元素是int，代码如下：
void Sort(Stack& s)
{
// 栈为空，无需排序
if (s.IsEmpty())
return;
// 先弹出栈顶元素x，对剩下的栈元素递归排序
int x = s.Top();
s.Pop();
Sort(s);
// 如果排好序的栈为空，把x送回栈即可，排序完成
if (s.IsEmpty())
{
s.Push(x);
return;
}
// 如果x不小于栈顶元素，同样把x送回栈即可，排序完成
int y = s.Top();
if (x >= y)
{
s.Push(x);
return;
}
// 否则, 令x归栈后，栈顶还是最大元素... 阅读全帖 |
|
d**s
发帖数: 98 | 3 http://zhedahht.blog.163.com/blog/static/2541117420071289522817
程序员面试题精选100题(02)－设计包含min函数的栈[数据结构]
2007-02-28 21:52:28| 分类： 栈 | 标签：编程 就业 找工作 |字号大中小 订阅
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数
min、push以及pop的时间复杂度都是O(1)。
分析：这是去年google的一道面试题。
我看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。
这样栈顶元素将是最小元素。但由于不能保证最后push进栈的元素最先出栈，这种思路
设计的数据结构已经不是一个栈了。
在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次push一个新元素进
栈的时候，如果该元素比当前的最小元素还要小，则更新最小元素。
乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素
被pop出去，如何才能得到下一个最小元素？
因此仅仅只添加一个成员变量存放最小元素（或最... 阅读全帖 |
|
j**l
发帖数: 2911 | 4 考虑直方图的每个元素（每根柱子)，以它为高度的最大矩形，宽度可以向左右扩展。
所以问题就转换为怎么确定左右边界。
我们使用了一个栈，从左到右每根柱子依次入栈。
情形一：如果栈不空并且当前将要入栈的柱子比栈顶的柱子低，则有：
1. 栈顶柱子的右边界完全确定，其对应的局部最大矩形面积可求(下面说明了左边界在
它入栈时已确定)。更新全局最大矩形面积后，栈顶柱子可以依次出栈，直到当前的栈
顶柱子比当前要入栈的柱子低或者栈变为空栈。
2. 连续的出栈操作使得当前的栈顶柱子比当前要入栈的柱子低或者栈变为空栈, 这时
候，当前要入栈的柱子的左边界也确定,可以入栈。
情形二：如果栈为空或者当前要入栈的柱子比栈顶柱子高，则无出栈操作，且当前要入
栈的柱子的左边界确定。
总结：
1. 每个入栈操作, 如果入栈柱子低于栈顶柱子,则它确定了栈中比要入栈柱子高的那些
柱子的右边界,可以对它们执行出栈操作。出栈的过程伴随着矩形面积的计算。
2. 每个入栈操作，不论是否引起出栈操作,我们都可以确定当前要入栈柱子的左边界。
3. 每次入栈后,栈内所剩柱子一定保持高度单调非递减的顺序。
4. 可令最后一根柱子高度为-1 |
|
z*j
发帖数: 42 | 5 说说我的理解:
基本上是在用栈模拟递归的后序遍历过程
对栈顶node, 要判断这个node是回溯过来的,还是刚push到栈顶的
case1:栈顶node左右孩子皆空, 到了叶节点.接下来就要回溯啦.
case2:左孩子回溯回来, 则访问右孩子(2sub cases)
case3:右孩子回溯回来, 则访问栈顶节点, 同时栈顶节点出栈
剩下case 是栈顶不是回溯回来的, 则继续压栈(深度优先搜索) |
|
y******6
发帖数: 49 | 6
可以吧。拿findmin来说，有一个min stack,栈顶存的是当前所有元素的最小值。每次
insertion的时候，新的元素跟栈顶的元素比较,如果小于栈顶元素，push进栈，否则只
是插入到hash表中就可以了。delete元素的时候，被delete的元素跟栈顶的元素比较，
如果比栈顶的大，那么只将元素从hash表中delete即可，否则还要minstack.pop(). |
|
p********7
发帖数: 549 | 7 第一个题预处理是必须的
先根据大小对数组排序，下面是他们的序号
2 5 6 10 80
然后创建一个hash table key是这些数值，value是这些数first greater number in the
array
然后遍历原数组，并且保持一个stack
遍历的逻辑如下
如果没查到这个数插入
如数比栈顶的大就弹出前面的，并且在table里面找到前面这个数，把后面这个数写入value，然后
继续比较栈顶，知道比栈顶的数小，最后压入栈顶。
如果比栈顶的小就压入
预处理结束后，查找的逻辑是
hash 查输入是不是存在，如果不存在，就binary 查找这个数字，如果这个数存在就能直接获得哪
个数是first greater value
最差复杂度是LogN
integer
in |
|
a*****s
发帖数: 1121 | 8 保留原始FIFO队列，再要一个栈，专门存最小值。
第一个元素直接进栈，后面来一个元素，跟栈顶比大小，大的不管，小于等于的进
栈顶。
min的时候直接取栈顶。队列delete（）的时候要检查是否是最小元素，若是则栈
也pop一个，保持同步。
没说不让用栈啊。 |
|
l*3
发帖数: 2279 | 9 给你个用stack的O(n)解法:
创立一个栈，最终栈内的元素从底到顶排起来就是所要的子字符串，这里直接用最终的
输出string t来表示这个栈，处理方法是：顺序扫描s的字符，如果当前字符没有在栈
中出现过，并且还比栈顶小，并且栈顶的字符在当前位置之后还有（也就是可以稍后再
添加），那么就把栈顶的字符扔掉，一会再加。
这是一个非常优雅的贪心法，其正确性并不显然，需要仔细琢磨琢磨。
c++ code 如下。注意，这里考虑了更general的情形，不仅限于 s 是由小写字母组成
的了。s实际上可以是任意字符处啊，以下code一样work, 时间复杂度还是 O(n)。
class Solution {
public:
string removeDuplicateLetters(string s) {
string t;
vector counts(256, 0);
for (char c : s) {
counts[c]++;
}
vector added(... 阅读全帖 |
|
d******o
发帖数: 13 | 10 Stack + 递归
之前面Twitter也被问到过，但是迷迷糊糊没想清楚。。。
需要一个 helper class: Pair(NestedList list, int position) 定义当前所在的位
置.
Iterator 需要实现 hasNext（） 和 next（）
hasNext 检查还有没有值，检查栈顶的Pair，如果当前所指的是Node，直接输出 true
即可。如果是List，就new 一个 Pair(curList, 0), push到stack上。然后递归的
call hasNext 进行检查。如果 栈顶的position 已经超出 当前list 的范围，说明已
经遍历完当前list， pop 掉当前元素，然后对新的栈顶元素（如果有的话）的
position ＋ 1， 之后同样 递归的 call hasNext 继续进行检查。
至于next，上面的 hasNext 保证了 如果还有值，会让栈顶的Pair指到一个Node，所以
直接输出即可，并将 position ＋ 1. |
|
d******o
发帖数: 13 | 11 Stack + 递归
之前面Twitter也被问到过，但是迷迷糊糊没想清楚。。。
需要一个 helper class: Pair(NestedList list, int position) 定义当前所在的位
置.
Iterator 需要实现 hasNext（） 和 next（）
hasNext 检查还有没有值，检查栈顶的Pair，如果当前所指的是Node，直接输出 true
即可。如果是List，就new 一个 Pair(curList, 0), push到stack上。然后递归的
call hasNext 进行检查。如果 栈顶的position 已经超出 当前list 的范围，说明已
经遍历完当前list， pop 掉当前元素，然后对新的栈顶元素（如果有的话）的
position ＋ 1， 之后同样 递归的 call hasNext 继续进行检查。
至于next，上面的 hasNext 保证了 如果还有值，会让栈顶的Pair指到一个Node，所以
直接输出即可，并将 position ＋ 1. |
|
e***l
发帖数: 710 | 12 直接用一个额外的数组（或者node对象的一个分量）记录颜色，颜色标记的顺序应该和
递归的方法相同：
所有node标白色;
root标灰色并入栈;
while(栈非空){
取得栈顶元素,//必为灰色
找到它第一个白色的邻接node,将其标灰并入栈, //注1
如果没有找到白色邻接node，将栈顶元素标黑并出栈。//所有邻接node已发现
}
注1：可以对每个node记录“已经访问到了第几个邻接node”,避免每次从头搜索 |
|
X****r
发帖数: 3557 | 13 你这个思路好！正如netghost所说，第二步可以改进。
每行的一维问题不用O(mn), 只要O(n)就可以，这样最后的总复杂度就是O(mn)。
思路是维持一个栈，每个元素是高度和位置。
从左到右扫描一遍，对每个新遇到的高度，
将栈处理到栈顶元素的高度不比当前高度高为止——这些矩阵已经无法扩展了。
然后如果当前高度比栈顶元素高的话将当前高度和某一适当位置压栈。
原数组后要加0 以使最后栈能自动清空。
用如下子程序，在for(y=0;y
int maxSize1D( const vector& v ) {
int best = 0 ;
vector vx(v), positions, heights;
vx.push_back( 0 );
for( int i = 0 ; i < vx.size() ; i ++ ) {
int leftest = i ;
while( heights.size() && heights[heights.size()-1] > vx[i] ) { |
|
d****j
发帖数: 293 | 14 这道题好像是facebook hacker cup 2011的第三题吧
刚开始没仔细看掉到陷阱了,直接sort连接..-_-
看到板上举得例子 "bc" "bca" 正解是 bcabc 而不是bcbca，才恍然大悟...
再看这个例子，如果是"bc" "bcd",那么sort再连接就没问题了
（楼上其他人举的例子和这个类似啦）
明显发现：如果一个词A=wx是另外一个词B=w的前缀，那么就需要考虑长单词多余部分x
和前缀w的大小,才能决定结果是AB 还是BA。
如果没有前缀关系，顺序连接打印就行了。
这就是我的idea，sort+栈+额外处理。
1.先sort.
2.第一个单词入栈
3.检查下一个单词cur是否以栈顶单词top为前缀，
a.如果不是，栈中元素全部 pop出，打印; cur入栈
b.是, 检查cur多余的部分x和top的大小
i. x<=top小，cur入栈
ii. x>top, top出栈打印
4. 重复3步骤直到单词表尾
5. 如果栈不为空，全部pop出栈打印
其中3步骤的几种情况，有的要下移一个单词检查，有的要继续检查当... 阅读全帖 |
|
x*****3
发帖数: 89 | 15 第十九回 云栈洞悟空收八戒 浮屠山玄奘受心经
（1） 各有心魔 （2） 老猪的简历 （3） 八戒的幸福就是苦 （4） 多心的心经 （5
） 为什么是多心经
（1）各有心魔
上回书说的是观音院唐僧脱难、高老庄大圣除魔。这三藏他们倒是从观音院脱难了，可
是在高老庄，这大圣除魔还真的说不上，故事的中心在第十九回呢。大圣充其量是把猪
头给赶跑了，而且这猪头到还真的不是魔，他只是给高太公的歪心眼充当了一回魔而已
、虽然猪头迷恋高家老三，但是他作为魔的角色纯属客串，谁叫那高太公心术不正呢。
如果这呆子真的是魔，那之前三番五次的道士和尚前来做法，肯定都不是被老猪给揍得
鼻青脸肿了。那些喜欢通过作法、符咒的手段来降妖伏魔的和尚道士，他们所能搞定的
，基本上都是那些另外空间的低灵鬼道之杂碎生物。如果稍微再厉害点的妖魔，这种术
类的手段就够呛了，为什么？因为擅长这种术类手段在人世间降妖伏魔的道人们，通常
都是没有神通的，差不多也就是天眼开了，能看到点阴间的东西、甚至大多数这样的人
他们连看都看不到。也就是说他们档次不够，才需要借助外法、符咒来召唤其它生灵来
替自己搞掂那些小鬼小魔小妖的。可是如果他们能... 阅读全帖 |
|
k******a
发帖数: 44 | 16 利用栈操作。
遇到（，压栈
遇到字母，压栈
遇到），开始出栈，将出栈字符放入一个队列，直到出栈的字符是（，
将这个队列的最后一个字符作为root，其他字符都是他的儿子，然后将这个root再压栈。
直到完成，输出栈顶。 |
|
R*****5
发帖数: 4915 | 17 你不要拿索南的经历和人家中学就过来的人比。
李飞飞聊天可以，但IT的中文专业名词她根本就不熟，她演讲一开始说google云的时候
就结巴了，因为想说cloud，你们索南都是用中文念的大学，熟悉物理化学数学和各种
计算机中文名词，李飞飞没有这个经历，中学大学博士都是一路英文词汇，本能就要说
英文。
但李飞飞会中文，在中国呆上一年，这些都不是问题。
你觉得李飞飞现在能看懂下面的中文吗？
“退栈前先检查是否已为空栈， 空则下溢；不空则作②，栈指针减1，指向栈顶。
栈可以用来在函数调用的时候存储断点，做递归时要用到栈" |
|
n******n
发帖数: 49 | 18 在想这题的时候 觉得它的思路跟largest rectangle under histogram的stack解法很
像。只是现在是栈顶元素比当前元素小的时候，弹出栈顶元素；之前histogram那题是
栈顶元素比当前元素大的时候，弹出。
原先那道histogram的题参考这个
http://wansishuang.appspot.com/?p=3002 |
|
n******n
发帖数: 49 | 19 在想这题的时候 觉得它的思路跟largest rectangle under histogram的stack解法很
像。只是现在是栈顶元素比当前元素小的时候，弹出栈顶元素；之前histogram那题是
栈顶元素比当前元素大的时候，弹出。
原先那道histogram的题参考这个
http://wansishuang.appspot.com/?p=3002 |
|
k*j
发帖数: 153 | 20 那次的讨论结果不知道怎么样，但我写下我当时的做法。
我面试的时候只用讲大概思路。写high level的code。
我当时的大体思路就是先把string转成word和长度。用－个stack记录pair
，碰到连续的space只记录成length=1。用一个variable len记录当前stack里所有word
length之和，
1。 当len>10的时候。check时候栈里是否只有一个word，如果是，即output整个word
到一行里（出题人的意思）。如果栈里多个word，则舍弃当前栈顶元素。然后再output
剩下的元素。还要注意这是的栈里是否有space，有则可以pad空格在中间。（这里我没太
仔细考虑，可能还需要改进）
2。 当len＝10
(a) 先check当前的word是不是空格，如果是，就把栈里的word一个个出栈，从右到左
output是的一行里。但当碰到stack里最后一个空格时，要check是否需要output多个空
格。因为出题人要求每一行的两头都必须是word，非空格。做法是check剩余要填满的
字符数是否是大于word里总和。差... 阅读全帖 |
|
g********r
发帖数: 89 | 21 Leetcode给的solution，在pop的时候，只要栈顶元素=minStack栈顶元素，就把
minStack的栈顶元素pop掉。如果有duplicates的话，比如stack里面5, 3, 3，
minStack里面是5, 3，在pop第一个3的时候，不应该把minStack里面的3 pop掉吧。否
则Stack里面变成了5, 3, minStack里面是5, 答案是不是有问题？
---- Leetcode solution
public void pop() {
if (stack.pop().equals(minStack.peek())) minStack.pop();
}
-----my solution
void pop() {
if(stk.empty()) return;
int tmp=stk.top();
stk.pop();
if(stk.empty() || (tmp == min_stk.top() && stk.top() > min_stk.top... 阅读全帖 |
|
w***g
发帖数: 5958 | 22 这个问题之所以会发生，本质上是因为编译器设计的时候决定了堆栈地址是往下长的。
函数运行的时候堆栈结构是像下面这样的：
高地址
[返回地址]
[局部变量A］
[局部变量B]
[局部变量C]
....
....
[栈顶]
低地址
调用函数的时候就往栈顶压入返回地址，然后再压入局部变量，等函数结束的时候取出
返回地址，然后把栈顶调整到函数未开始时的地址。
如果局部变量B是一个数组，那么你让数组越界(buffer overflow)后就会把高地址存的
返回地址覆盖掉，然后函数返回的时候就会跳到一个随机的地方了。实际情况往往比这
个复杂的多，比如C/C++很少会把buffer分配在堆栈(stack)上，而是一般都分配在堆(
heap)上。这时候数组越界能越到堆栈上的返回地址的可能性就会减少，所以越界就得
越的相当多才行。对于古老的系统，甚至可以越界到指令内存，用恶意指令把程序本身
都覆盖了。 |
|
c****p
发帖数: 6474 | 23 笨办法：
搭配一个优先级栈，栈元素的值和括号等级相同。
符号串： {[()()]}
优先级串：01222210
入栈左括号的时候如果发现优先级栈的栈顶值大于等于当前括号等级的时候则视为不合
法。【 在 csdfg (谁是东方郭) 的大作中提到: 】 |
|
j********r
发帖数: 127 | 24 我的做法是求必须删除的位置
碰到左括号，入栈索引
碰到右括号，如果栈顶是左括号，就出栈，否则就入栈右括号索引
最后栈里的就是需要删掉的左右括号了。
这能给出其中一组合理解，不能给出另一组。
估计他的followup是给出所有合法字串。 |
|
n*******w
发帖数: 687 | 25 1. A string consists of parentheses and brackets for example "(()([]))",
check if it is well formed.
用stack。遇到( 和 [ 入栈，遇到 ) 或者 ] 查栈顶是不是匹配。不匹配return false
。否则pop栈顶继续。到string结束，return true。
2. Given strings like "CB", "BD", "DE", find the sequence of alphabets.
The result is "CBDE" for the example.
topsort。重点是考虑node的入度和出度。有环的话可以检测出来。
3. Verify whether a string contains all the characters of another
string.
简单的数组，当做hashtable用。
4. Given two strings that one string contains the other string, while
th... 阅读全帖 |
|
b***e
发帖数: 1419 | 26 这个基本上就是每个线程保持一个normal iterator的栈。栈顶的iterator结束了就pop
out。否则就用栈顶的iterator继续next。 |
|
r**u
发帖数: 1567 | 27 思路是这样的，
1. 如果所有的bar都是按升序从左到右排起来的话，那么，就可以简单的用最小（最左
）的bar的高*n, n是bar的个数，这是一个面积，接着用次小的bar的高*(n-1), ...,
找到max area。
2. 一般bar不是完全按升序排列。就用一个vector去simulate a stack，如果下一个
bar比栈顶的bar高，入栈。
否则的话，pop栈里所有比next bar高的bar，再入栈next bar。并且要计算这过程
中这些pop掉的bar cover的area。
3. 最后处理剩在stack里面的bar。 |
|
k*****7
发帖数: 72 | 28 用栈吧，从左到右逐符入栈，遇到c就查栈顶两个是不是ba，是就都pop了，然后继续把
下一个入栈 |
|
l********s
发帖数: 30 | 29 个人意见：
1) flag per node: 需要修改数据结构。当然，可以用 hash table来代替，但总觉得
不 elegant；
2）two stacks: 好主意，代码很好写，很 elegant。但用的空间相对多一些，至少是
O(n)
3）只用一个 stack，同时用一个 prev 表示前一个被打印的。代码也比较好写，就是
得判断一些 case，没有两个stack 来得漂亮。但空间相对少。如果树是 balanced的话
，只要 O(logn) [直观地，每个level最多只有2两个结点同时在栈中]。
4）在栈中设置一些特殊标志：当遇到特殊标志，我们就知道栈顶结点应该要打印了。
idea 很不错，直观，代码也好写， elegant。空间最好的情况也是 O(logn)。 |
|
t******e
发帖数: 1293 | 30 两个local变量不一定准确
int a, b;
可能a在b之前，也可能b在a之前的。还是定义子函数的好。
因为每个函数都会在栈上有一个frame
这些frames都是在栈顶上涨的，所以，用这个来判断栈的生长方向是最准确的。 |
|
e*********l
发帖数: 136 | 31 内存那个有意思
是这样的
|表示栈帧的分割 || 表示栈顶
没有的话只是这样
.... function || free stack space (undefined values)
加了之后是
..... function | debug func || free stack space
debug func返回之后可以看到
..... function || free stack space（之前debug func留下来的栈帧没有清理，阴差
阳错对了）
比如free space全是零，然后有个二级pointer指向free space的某个地方，这样读取0作为二级指针的值，然后就是引用地址0
但是debug func加了之后，这个二级pointer指向的地方值改变了，不再是零了。所以二级指针可以用了 |
|
j********e
发帖数: 1192 | 32 我的做法也是用stack，可能简单些。
从左到右scan一遍，如果是"("或者0，就入栈，如果是“)”就
看栈顶3个元素是否“(00”，是的话，弹出这3个，
压入“0”(也就把子树替换成“0”)。
最后栈里只剩一个“0”就validated。
int validate(char *s, int len) {
if(s == NULL || len == 0 || s[0] != '(')
return -1;
int depth = 0, max_depth = 0;
char *t = new char[len+1];
int tlen = 0;
for(int i=0; i
if(s[i] == '(') {
depth++;
if(depth>max_depth)
max_depth = depth;
}
else if(s[i] == '0')
t[tlen++] = s[i]... 阅读全帖 |
|
j**l
发帖数: 2911 | 33 不需要更新。每当一个元素成为当前的栈顶元素，它的链域指向的一定是全局的最小。
当一个元素还不是栈顶元素的时候，它的链域指向的是它下方的所有元素(括它自己)中
的最小，但全局最小可能在它上方。
（1 |
|
w********g
发帖数: 106 | 34 这个方法没有用递归。题目要求必须用递归才行。我觉得这才是最难的地方。如果用
iteration，一个for循环就能实现向右的移动。可是如果必须用递归，怎么解决递归向
右和依靠push右侧兄弟导致的重复呢？
我的解决办法是：
任何一个node都只向下递归打印第一个child；
除了叶子以外，任何node都不向右递归自己的sibling；
只有叶子才向右侧递归打印；
只有当前node没有右侧的sibling时才递归打印栈顶的node，
这个栈顶的node其实就是当前node的先根遍历时的next node。
很多特殊情况还没考虑，但是大意就是这样。明天写一下code。 |
|
g********r
发帖数: 89 | 35 用不到counter，这个也浪费。
每次pop的时候，如果stack pop的元素和minStack栈顶想同，那么继续判断他下面的元
素是不是比minStack栈顶大，就知道他是不是第一个重复的元素了。 |
|
w*****1
发帖数: 245 | 36 在栈中设置一些特殊标志：当遇到特殊标志，我们就知道栈顶结点应该要打印了。
谁能具体说下这个怎么弄啊?? 想了半天也没想出来...
谢谢 |
|
q****x
发帖数: 7404 | 37 重复插入。pop时一直到栈顶比出栈院士大为止。
print。
烦。 |
|
w****x
发帖数: 2483 | 38
好吧, 那程序跑得时候一个线程对应一个stack, call 一个function就套一个stack,
return一个function就收起一个stack. stack表达方式就是esp寄存器是栈顶, ebi是栈
基址, ebi+xxx对参数寻址, ebi-xxx对局部变量寻址. 当函数返回的时候esp = ebi +
xxx(参数空间), 当call一个函数的时候先push参数, 然后ebi = esp, 然后esp + 所有
该函数对应的局部变量空间. 这么答差不多了吧.... |
|
w****x
发帖数: 2483 | 39
好吧, 那程序跑得时候一个线程对应一个stack, call 一个function就套一个stack,
return一个function就收起一个stack. stack表达方式就是esp寄存器是栈顶, ebi是栈
基址, ebi+xxx对参数寻址, ebi-xxx对局部变量寻址. 当函数返回的时候esp = ebi +
xxx(参数空间), 当call一个函数的时候先push参数, 然后ebi = esp, 然后esp + 所有
该函数对应的局部变量空间. 这么答差不多了吧.... |
|
f*******5
发帖数: 52 | 40 如果用python的话stack里不用放当前下标。当栈顶是数组的话就弹出数组， 然后逆序
入栈。以下是python代码，假定只有list 和 basic type 两种类型
class ListIter(object):
def __init__(self, lst):
self.stack = [lst]
def next(self):
if len(self.stack) == 0:
raise StopIteration
while isinstance(self.stack[-1],list):
l = self.stack.pop()
self.stack.extend([i for i in reversed(l) if not isinstance(i,
list) or len(i)>0])
if len(self.stack) == 0:
raise StopIteration
... 阅读全帖 |
|
j**l
发帖数: 2911 | 41 每个链，都指向该元素下方（包含该元素)的最小（不一定是全局最小)，这样栈顶的链，一定指向全局的最小。 |
|
r****o
发帖数: 1950 | 42 如果栈顶元素最小，结果把它pop了，那下面所有元素的链怎么更新呢？ |
|
y**i
发帖数: 1112 | 43 貌似他假定栈顶是在最上方，下面的元素的链只包含自己下方的元素 |
|
j**l
发帖数: 2911 | 44 你有调用Pop么？每个getmin，都是返回栈顶元素的链指向的那个元素
Push 1- 10 后的情形
stack元素序号 元素值 链域
9 10 0
8 9 0
7 8 0
6 7 0
5 6 0
4 5 0
3 4 0
2 3 0
1 2 0
0 1 0
（1 |
|
j**l
发帖数: 2911 | 45 看去不错，不过你的top，实际上是指向栈顶元素的上一个位置吧，这种用法不太符合
一般人的习惯。
另外用模板比较好，但为了方便应该可以用int写，然后再和面试官说可以用模板来支
持各种类型吧？
用异常也比较好。
白板的空间有限，时间也有限，如果写得太全太细，肯定会遇到费马的难处：这里边缘
太小，写不下。
是不是可以像我贴的代码那样尽量简化问题写，比如用int代替模板，用printf代替异
常，然后再和面试官提到模板和异常的技术？ |
|
d*******l
发帖数: 338 | 46 我没太明白，每次新来一个数，最多只跟栈顶比较一次，然后不是pop就是push，整体
不就是O(n)的吗？还是题意理解的不一样？ |
|
p*i
发帖数: 411 | 47 来自主题: JobHunting版 - 上一道题吧 感谢帮忙测试。我的已经通过了
基本思想是用一个stack s0，遇到'('就push当前的index，遇到')'就pop，说明发现一
个'('-')' pair
此时left和right分别记录这个pair的左边'('的位置和右边')'的位置
同时还有一个额外的s1，记录当前已经遇到的所有pair的左右位置
每次发现一个新的pair (lnew, rnew)，就与s1栈顶的pair(假设是lold, rold)进行比较
如果lnew == rold+1，说明他们是()()这种情况，所以需要合并
如果lnew < rold+1，说明是(())这种情况，也需要合并
一旦进行了第一个合并，就需要继续检查s1直到桟为空或者不能继续合并为止，应付()
(())这种情况
下面是我在leetcode上用的code
#include
using namespace std;
class Solution {
public:
int longestValidParentheses(string s) {
Start typing your ... 阅读全帖 |
|
s***e
发帖数: 403 | 48 其实可以优化一下。
只pop第一个，然后修改栈顶的数据。 |
|
w********g
发帖数: 106 | 49 太强了！！！你的最后一行code我写了很多行实现，分了各种情况。看了你的code，才
发现其实那么多种情况本质上就是递归调用到栈顶，顿时佩服得五体投地。万分感谢赐
教！
void printn(stack& waitStack , int n)
{
if(n == 0 || waitStack.empty())
return;
childList* curHead = waitStack.top();
waitStack.pop();
dealWith(curHead -> curNode -> data);
if(curHead -> next)
waitStack.push(curHead -> next);
if(curHead -> curNode -> children)
waitStack.push(curHead -> curNode -> children);
printn(waitStack , n-1);
} |
|
|
