作者phoenixrace (殘存亦陌路 兵敗如山倒)
看板Prob_Solve
標題[問題] 面試問題followup
時間Wed Oct 17 04:42:48 2018
問題是給你一串字串,相鄰兩個字母是一樣的要消掉.
Example1:
"aabccb" --> "" (全部消完)
Example2:
"add" --> "a" ("dd"可以消掉)
我的解法是用stack, 解完後面試官要求只用 O(1)space, 我就沒想到該怎麼解...
請問有人知道只用 O(1)space 解這題嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.251.165.125
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1539722570.A.162.html
1F：推 DJWS: 有阿 就是面試官 為何不當場問他或者寄信問他 10/17 06:16
我有跟他要hint, 他說用pointer,不過到現在還是沒想出來, 所以我猜是不是用pointer simulate stack
※ 編輯: phoenixrace (24.251.165.125), 10/17/2018 07:06:03
2F：推 DJWS: 那麼接下來你可以寄信跟他要code 10/17 10:30
3F：推 FRAXIS: 就把 input array 當 stack 用 然後用一個 index 維護 10/17 11:08
4F：→ FRAXIS: 還沒處理過的部分 10/17 11:08
5F：推 DJWS: 所以說 in-place => O(1) space ? 10/17 12:05
6F：→ phoenixrace: 感謝Fraxis，我還真的沒有想到input string是mutabl 10/17 14:52
7F：→ phoenixrace: e，感謝開示，這樣應該可以用兩個pointer做到 10/17 14:52
8F：→ FRAXIS: 一般來說 in-place 就是 O(1) space 10/17 21:09
9F：→ FRAXIS: 精確來說是 O(1) variables 10/17 21:09
10F：→ FRAXIS: 因為輸入陣列長度是 n 的話 存 index 就要O(lg n) bits 10/17 21:09
11F：→ FRAXIS: 不過面試官大概不會注意這種差異.. 10/17 21:10
12F：推 DJWS: 了解 謝謝 10/17 22:21
13F：推 alan23273850: 我想問這題和 C/C++ 板的 #1Rf8aTlF 這篇差在哪 10/18 09:06
14F：→ alan23273850: 那邊有很多人討論這題，也萌生出一些解法，不過還沒 10/18 09:06
15F：→ alan23273850: 看到有 O(1) space 的 10/18 09:06
16F：推 ckc1ark: 連續兩個以上可以刪 和 連續兩個 有差別 10/18 10:26