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);
}
}
} |
|
b*****d
发帖数: 23 | 3 #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 |
|
g*****i
发帖数: 2162 | 4 可能我说的不清楚,用个图解一下.
如果char[i]!=char[i-1] &&char[i]!=char[i-2],push to "newest stack" 一开始也
就是stack0
如果char[i]=char[i-1]的的时候,偶数palindrome,new queue1, new stack1, char[i]
进去stack1,stack0.pop()进入queue1.
如果char[i]=char[i-2],奇数palindrome,char[i-1],char[i-2]都要从stack0 pop出来
进去queue1, char[i]还是进入stack1
如果stack0空了,是个solution.
在这过程中任何时候stack0+queue1+stack1都可以看成一个整体的stack
一旦又出现char[i]!=char[i-1] &&char[i]!=char[i-2],那么newest stack变成stack1
,循环下去.以后发现可能的palindrome时候要从新到旧把前面的stack和queue都清空才
是solution. |
|
c********1
发帖数: 161 | 5 我也演算了你的算法，我觉得还有问题啊，比如给个复杂的例子，你的算法怎么work呢
？CASE: ABCDCACDCBA,
在这个例子里面，第一个可能是palindrome的地方发生在(AB）CDC 处， 可是紧接下来
的A不satisfy B，所以按照你的算法，原先的stack1变成new stack，结果，就变成
stack0(top -> bottom):BA, queue1（front -> back）：DC， stack1（new stack
now， top->bottom）:AC
接下来是C， 因为C和stack1中的C(AC中的C)吻合，所以满足char[i] = char[i-2]，接
下来你的算法是“循环下去.以后发现可能的palindrome时候要从新到旧把前面的stack
和queue都清空才是solution”,我实在没弄明白这里是什么意思，接下来要怎么处理？
？？？？？？ |
|
g*****i
发帖数: 2162 | 6 stack0+queue1+stack1看成一个stack, pop的时候从最后一个stack1开始,最后一个空
了从倒数第二个queue1开始pop(由于是queue,所以实际上是queue的remove()).
stack |
|
b******7
发帖数: 92 | 7 注意左移右移就行了
第一个栈[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;
}
... 阅读全帖 |
|
i****y
发帖数: 84 | 8 请问如果push的时候stack1满了，那怎么办呢？是不是queue的长度达不到2倍的stack？ |
|
x****a
发帖数: 1229 | 9 在新建的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 | 10 我是最近刚转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 | 11 stack1.peek()==stack2.peek()
Stack里Java会把primitive 数字box成对象。虽然2个数字相同，但是他们的ref指向不
同的内存区域。你可以把对象转回primitive，然后比较。Integer.intValue() |
|
p****w
发帖数: 90 | 12 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客户端] |
|
