Re: [問題] Google Interview Question (1)
看板Prob_Solve (計算數學 Problem Solving)作者pnpncat (meow)時間11年前 (2013/03/29 16:49)推噓1(1推 0噓 19→)留言20則, 3人參與討論串10/16 (看更多)
※ 引述《RockLee (Now of all times)》之銘言：
: 原始網址:
: http://www.careercup.com/question?id=14539805
: 題目:
: Three strings say A, B, C are given to you.
: Check weather 3rd string is interleaved from string A and B.
: Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)
: 用 Dynamic Programming 應該可在 O(n^2) 的時間內解決
: 但要在 O(n) 的時間內解決就想不出來了 Orz...
: CareerCup 上的討論看來都無法在 O(n) 的時間內正確的解決
: 不知道板上有沒有人有什麼 idea?
這題不能直接這樣做嗎？
1. 將A, B, C分別放進stackA, stackB, stackC
2. 以下列函數判別答案是否為真
bool foo() {
while ( stackC is not empty ) {
if ( top of stackC == top of stackA ) {
pop stackC;
pop stackA;
} else if (top of stackC == top of stackB ) {
pop stackC;
pop stackB;
} else {
return false;
}
}
return true;
}
--
直接閱讀《琴劍六記》
http://gs.cathargraph.com/p/list.html
《琴劍六記》Facebook專頁
https://www.facebook.com/GSannals
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.176.10.104
→
03/29 18:05, , 1F
03/29 18:05, 1F
→
03/29 18:05, , 2F
03/29 18:05, 2F
→
03/29 21:12, , 3F
03/29 21:12, 3F
→
03/29 21:13, , 4F
03/29 21:13, 4F
→
03/29 21:21, , 5F
03/29 21:21, 5F
→
03/29 21:21, , 6F
03/29 21:21, 6F
→
03/29 21:21, , 7F
03/29 21:21, 7F
→
03/29 21:22, , 8F
03/29 21:22, 8F
→
03/29 21:23, , 9F
03/29 21:23, 9F
→
03/29 21:24, , 10F
03/29 21:24, 10F
→
03/29 21:25, , 11F
03/29 21:25, 11F
→
03/29 21:25, , 12F
03/29 21:25, 12F
→
03/29 22:03, , 13F
03/29 22:03, 13F
→
03/29 22:04, , 14F
03/29 22:04, 14F
→
03/29 22:05, , 15F
03/29 22:05, 15F
→
03/29 22:05, , 16F
03/29 22:05, 16F
→
03/29 23:46, , 17F
03/29 23:46, 17F
→
03/29 23:54, , 18F
03/29 23:54, 18F
我多加一個空的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)
推
03/31 02:12, , 19F
03/31 02:12, 19F
→
03/31 22:54, , 20F
03/31 22:54, 20F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
