→ flere:當top stack of C跟top A,B一樣的時候,無法判斷pop哪一個 03/29 18:05
→ flere:stack才會是正確的~ 03/29 18:05
→ pnpncat:咦@@ 是這樣嗎? 不是隨便pop哪一個都一樣嗎? 我把code裡 03/29 21:12
→ pnpncat:面的A B對調 應該還是會得到同樣的結果吧 03/29 21:13
→ flere:A=ab,B=ac,C=acab,你看到第一個a的時候,如果popA的a的話 03/29 21:21
→ flere:等等看到c就會找不到對應的了(還是我誤會了嗎??XDD 03/29 21:21
→ pnpncat:瞭解了^^" 03/29 21:21
→ pnpncat:是我想錯XD 03/29 21:22
→ pnpncat:等等 不對啊 這樣等下會找到c啊........... 03/29 21:23
→ pnpncat:那時候c就在stackB上面不是嗎? 03/29 21:24
→ pnpncat:我剛重想了一下 這算法應該是沒錯的 就跟沒有蓋牌的接龍 03/29 21:25
→ pnpncat:道理一樣 不可能會接不起來吧 03/29 21:25
→ flere:可是這時候stackB最上面會是a耶,如果你說最上面會是c的話, 03/29 22:03
→ flere:那我改成A=ba,B=ca,C=baca 03/29 22:04
→ flere:因為pop a同時有兩個stack符合,所以會不確定pop哪個stack才 03/29 22:05
→ flere:對~ 03/29 22:05
→ pnpncat:確實耶@@ 雖然直接用A往下搜到完也能解 但就不是O(n)了... 03/29 23:46
→ pnpncat:看來還是要多用一個容器 把沒有match的依序存起來才行 03/29 23:54
我多加一個空的queue做做看
bool foo() {
while (stackC is not empty) {
if (top of stackC == top of stackA) {
pop stackC;
pop stackA;
} else {
enqueue(top of stackC);
pop stackC;
}
}
if (stackA is not empty) return false;
while (queue is not empty) {
if (head of queue == top of stackB) {
dequeue;
pop stackB;
} else {
return false;
}
}
return true;
}
這樣就還是 O(n)......... 這次有想錯嗎??
※ 編輯: pnpncat 來自: 180.176.10.104 (03/30 00:14)
推 ledia:"accc", "bcbc", "abcccbcc" 03/31 02:12
→ pnpncat:看來是我把它想得太簡單了@@ 03/31 22:54