c*******t
发帖数: 123 | 1 用两个stack, best case 可以O(n)
第一个stack 不变量是：递增，所有元素比当前元素小。
第二个 stack不变量是：递减，所有元素比当前元素大。
比如 2 8 5 2 6 1
指针指向6时，stack 1: 1. stack2:empty output stack1.size();
指针指向2时， stack1: 1,6, stack2:empty. 6入 stack2, output stack1.size().
2 入stack1
stack1:1,2 stack2:6
省略。。。。。。
指针指向8时， stack1: 1,2,5 stack2: 6, rebalance stack, 6入1.
stack1: 1,2,5,6 stack2:empty
stack1:1,2,5,6,8, stack2:empty
最后指向2： rebalance stack, stack1:1 stack2: 8,... 阅读全帖 |
|
j*******a
发帖数: 61 | 2 will this work?
void f(NODE* r)
{
// define stack1, stack2;
stack1.push(r);
while(!stack1.empty && !stack2.empty)
{
while(!stack1.empty)
{
NODE* n=stack1.pop();
if(n->r) stack2.push(n->r);
if(n->l) stack2.push(n->l);
}
while(!stack2.empty)
{
NODE* n=stack2.pop();
if(n->l) stack1.push(n->l);
if(n->r) stack1.push(n->r);
}
}
} |
|
s****j
发帖数: 67 | 3 粗略想法：
再开一个stack
while (!stack.empty()) {
Node current=stack.top();
stack.pop();
//color current to grey
current->pos=stack.size(); // anyway, record current stack size
stack2.push(current);
//push all edge
while (!stack2.empty() && stack2.top()->pos==stack.size()) {
Node t=stack2.top();
//color t to black
stack2.pop();
}
} |
|
b*****d
发帖数: 23 | 4 #include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {1,2,3,4,5,6,7};
stack stack1;
stack stack2;
for(int i = 0; i<7; ++i)
stack1.push(a[i]);
int i = stack1.size();
while(!stack1.empty())
{
for(int j = 0; j
{
stack2.push(stack1.top());
stack1.pop();
}
in |
|
b******7
发帖数: 92 | 5 注意左移右移就行了
第一个栈[0...capacity0 - 1)
第二、三个栈[capacity0,...,N)分别一个从头开始++，一个从尾开始--
当第一个栈满而第二、三个栈不满时，做右移操作
反过来，但第二、三个栈满，而第一个栈伟满时，做左移操作
template
class TripleStack{
public:
TripleStack()
{
head0 = 0;
head1 = capacity0 = N/3;
head2 = N-1;
}
void push0(const T & e)
{
if(!isSubStackFull(0))
arr[head0++] = e;
else if(!isSubStackFull(1))
{
shiftRight();
arr[head0++] = e;
}
... 阅读全帖 |
|
x****a
发帖数: 1229 | 6 在新建的stack中，调用generic method
public E remove（）方法出错。如果把E改成char，运行成功。请解惑。谢谢
/**********************************************************************
作业是实现infix， postfix互换，读取string input，把数字push to a stack，遇到
括号再pop。
要求stack必须用doublyLinkedList形式生成，就是先建DoublyLinkedList class， 再
创建stack class： DoublyLinkedList stack = new DoublyLinkedList；再创
建新class 里有infix to postfix 和 postfix to infix两个method。
我两个method里，infix to postfix， 用stack1; postfix to infix
用stack2。
there i... 阅读全帖 |
|
m*****r
发帖数: 37 | 7 我是最近刚转Java的弱弱，有几个小问题，请牛牛们轻拍。
这次转java，总算像是某位说的那样，原来c++转java也就分分钟的事儿。写得顺的时
候，边google边写，也可以写得稀里糊涂、腾云架雾、行云流水；可问题是bug一出现
，立马歇菜！比如，min stack, stack1.peek()==stack2.peek(),顶上的两个数字明明
是相等的，为什么会return false呢？想去google都不知道该搜什么。。。等把java刷
一遍lc就算我可以写java了？
我有个function, public boolean dfdjdf(){return dfkld;} 为什么它一定要我在最
后一句话加个return啊，方法里的逻辑到那一步早就应该已经return了啊？
还有就是，刷lc搭了个local的架，本来没什么心理障碍，可是每遇到有Node,
ListNode, TreeNode的题就一股无名火，我不知道该把这些定义的类塞到哪里？试过两
种：
public class getIntersectionNode {
public class ListNode {
... 阅读全帖 |
|
z****n
发帖数: 1933 | 8 stack1.peek()==stack2.peek()
Stack里Java会把primitive 数字box成对象。虽然2个数字相同，但是他们的ref指向不
同的内存区域。你可以把对象转回primitive，然后比较。Integer.intValue() |
|
p****w
发帖数: 90 | 9 nn【在 mywater (梦)的大作中提到：】n：我是最近刚转Java的弱弱，有几个小问题，
请牛牛们轻拍。n：n：这次转java，总算像是某位说的那样，原来c++转java也就分分
钟的事儿。写得顺的时n：候，边google边写，也可以写得稀里糊涂、腾云架雾、行云
流水；可问题是bug一出现n：，立马歇菜！比如，min stack, stack1.peek()==stack2
.peek(),顶上的两个数字明明是相等的，为什么会return false呢？想去google都不知
道该搜什么。。。等把java刷一遍lc就算我可以写java了？n：n：我有个function,
public boolean dfdjdf(){return dfkld;} 为什么它一定要我在最n……nn--n[发自未
名空间Android客户端] |
|
