PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 面試問題followup

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