作者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/cn.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