[問題] 面試問題followup phoenixrace PTT批踢踢實業坊

作者: phoenixrace (救世劍) 2018-10-17 04:42:48

問題是給你一串字串,相鄰兩個字母是一樣的要消掉.
Example1:
"aabccb"

作者: DJWS (...) 2018-10-17 06:16:00

有阿就是面試官為何不當場問他或者寄信問他那麼接下來你可以寄信跟他要code

作者: FRAXIS (喔喔) 2018-10-17 11:08:00

就把 input array 當 stack 用然後用一個 index 維護還沒處理過的部分

作者: DJWS (...) 2018-10-17 12:05:00

所以說 in-place => O(1) space ?

作者: phoenixrace (救世劍) 2018-10-17 14:52:00

感謝Fraxis，我還真的沒有想到input string是mutable，感謝開示，這樣應該可以用兩個pointer做到

作者: FRAXIS (喔喔) 2018-10-17 21:09:00

一般來說 in-place 就是 O(1) space精確來說是 O(1) variables因為輸入陣列長度是 n 的話存 index 就要O(lg n) bits不過面試官大概不會注意這種差異..

作者: DJWS (...) 2018-10-17 22:21:00

了解謝謝

作者: alan23273850 2018-10-18 09:06:00

我想問這題和 C/C++ 板的 #1Rf8aTlF 這篇差在哪那邊有很多人討論這題，也萌生出一些解法，不過還沒看到有 O(1) space 的

作者: ckc1ark (偽物) 2018-10-18 10:26:00

連續兩個以上可以刪和連續兩個有差別

繼續閱讀