Re: [問題] 反轉字串裡面的字元
※ 引述《famayo (砝碼)》之銘言：
: 使用語言是C
: 想請問一下假如我要把"how are you"
: 反轉成"you are how" 我該怎麼做呢
我補一下這例子。
這題是某科技廠 (keyword: NAS) 熱門的面試考題，
我只憑印象取出相關題組和至今我有些疑惑的地方 (其他題目就跳過了)，
它面試的流程大概是這樣。
Q1 : 字串反轉題組
(1.1) 寫個字串原地反轉的例子
char buf[] = "abcd";
strrev(buf) ;
/* buf = "dcba" */
(1.2) 說明 (1.1) 寫出的 strrev 流程與原理
(1.3) (1.1) 中有沒有辦法不用暫存變數做交換？
第一個題組其實算基本題
Q2 : 單字反轉題組
(2.1) 有沒有辦法針對單字部份做反轉「之取出」？
"how are you" ---> "you are how"
一開始我給的 solution 比較不好，須要額外的儲存空間，
關鍵在於 Src遇到空白前的字串，從 Buf 後面填進來，過程中紀錄 T1, T2
t1 t2
src ｈｏｗ ａｒｅ ｙｏｕ
dst ｈｏｗ
t1 t2
上面示意圖有很多思考空間，思考一下應可知道小弟在說什麼。
最後再把 dst 複製回 src 裡面去，接著再對白板解釋程式碼。
(2.2) 那，有沒有辦法不使用額外儲存空間？
細思，「當時」情況並沒有要求做存回動作，只要依序取出就行了，
所以我用的算法是
(a) "how are you" --> 整個反轉 ---> "uoy era woh"
(b) "uoy era woh" --> 依序取 strtok(.., " ")
(b.1) 取出 "uoy" --> 再做反轉輸出 --> "you"
(b.2) 取出 "era" --> 再做反轉輸出 --> "are"
(b.3) 取出 "woh" --> 再做反轉輸出 --> "how"
當然還要再寫 code, 附上當參考
char * part_rev(char * p)
{
char * ret = p;
char * q = Strrev(p) ;
char * div = strtok(q, " ");
while(div) {
div = Strrev(div);
printf("%s ", div);
div = strtok(NULL, " ");
}
puts("");
return ret;
}
好啦，我承認這段 code 其實有點問題啦，原因在於有多個連續空白時會有問題，
但這問題在面試當時並不是主要重點，重點是要反向取出單字。當然還要再解釋
上面這些 code.
(2.3) Strrev 是你剛剛寫的，strtok 那是什麼？作用是什麼？原理是什麼？
這個不用我講了吧？
(2.4) 如果不能用 strtok 時，你會怎麼處理？
我回答還蠻直接，當下還蠻怕這個答案不能被接受的：
我會改用 strchr，這函式對準確性會比較好，但步驟比上面繁雜；
再不能用的話會直接寫一個 strtok 或 strchr。
事後跟面試官求證，其實覺得我用 strtok 算是不錯的解法了。
Others
其實上面 Q2 從第二個問題我用蠻偷懶的方式，前提假設都是在於
「不用存入，只要依序取出」，所以狗急跳牆才想到用 strtok + strrev。
然後有問到兩個問題事後還蠻感興趣的
(1) plug-in 怎麼設計(掛)
(2) vc 在 debug 裡面，可以偵測出記憶體使用是否超界，這原理是什麼？
怎麼設計？
其實 (2) 算是半閒聊聊到的，因聊到 dbg_malloc / dbg_free 怎麼設計，
然後小弟講了一些作法，所以就被追問說怎麼偵測出記憶體使用是否超界。
但這題我很疑惑，在 heap 上可以抓到 (加上 hex speaker 偷雞)，
但針對放在 stack 上的 array，要怎麼抓？我主要是死在這，
不知版友有沒有什麼看法？
為避免太過跳針模糊焦點，其他的問題就暫不附上了。
--
「自從我學了 C# , 人都變聰明 , 考試都考一百分」
「自從我學了 VB , 皮膚都變好 , 人也變漂亮了 」
「自從我學了 Java , 明顯變壯 , 個子也變高了 」
「自從我學了 C++ , 內分泌失調 , 頭都禿了... 」
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.76.161
推
10/23 15:11, , 1F
10/23 15:11, 1F
推
10/23 15:21, , 2F
10/23 15:21, 2F
→
10/23 15:22, , 3F
10/23 15:22, 3F
→
10/23 16:30, , 4F
10/23 16:30, 4F
→
10/23 17:22, , 5F
10/23 17:22, 5F
→
10/23 17:22, , 6F
10/23 17:22, 6F
→
10/23 17:23, , 7F
10/23 17:23, 7F
→
10/23 17:25, , 8F
10/23 17:25, 8F
推
10/23 17:35, , 9F
10/23 17:35, 9F
→
10/23 17:36, , 10F
10/23 17:36, 10F
→
10/23 17:37, , 11F
10/23 17:37, 11F
→
10/23 17:38, , 12F
10/23 17:38, 12F
→
10/23 18:27, , 13F
10/23 18:27, 13F
推
10/23 18:40, , 14F
10/23 18:40, 14F
→
10/23 21:23, , 15F
10/23 21:23, 15F
→
10/23 21:27, , 16F
10/23 21:27, 16F
推
10/23 22:01, , 17F
10/23 22:01, 17F
→
10/24 01:52, , 18F
10/24 01:52, 18F
→
10/24 05:00, , 19F
10/24 05:00, 19F
→
10/25 23:10, , 20F
10/25 23:10, 20F
→
10/25 23:11, , 21F
10/25 23:11, 21F
討論串 (同標題文章)