作者a106a106 (猜猜我4誰)
看板C_and_CPP
標題[問題] C/C++字串處理問題
時間Fri Sep 21 14:00:59 2018
最近練習時寫到一個題目
給一個只由兩個字元(x、y)組成的字串(不超過30字)
例：xxyxxyxyy
把字串內相同的字劃分成一組
變成：xx y xx y x yy，如此就有6個組
再把有兩個相同字以上的組刪除
例如：xxyxxyx
yy→xxy
xxyx→xx
yyxxx→
xxxxx→空字串
題目：隨機給定一字串，判斷此字串最後能不能變成空字串
列出了很多組字串思考，原本是想找有aba或bab單獨存在的字串，但後來發現無論如何都會
有例外，一直找不到可以直接判斷的方法，想請問有沒有大大對這題有任何想法可以一起討
論，我想了好幾天都想不出來...
謝謝大家QQQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.102.238
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1537509661.A.BCF.html
※ 編輯: a106a106 (27.242.102.238), 09/21/2018 14:05:06
※ 編輯: a106a106 (27.242.102.238), 09/21/2018 14:08:32
1F：→ MOONRAKER: 就一直跑看會不會變空字串不就好了09/21 14:17
2F：推 s4300026: 我的想法是存入vector，用for，如果iter值跟下一個相同09/21 14:48
3F：→ s4300026: ，就再檢查下一個，直至不相同，然後刪除中間區塊，iter09/21 14:48
4F：→ s4300026: --，iter到底後檢查vector是否為空，結案。 值得思考的 09/21 14:48
5F：→ s4300026: 是，有沒有特解是要先消後面一組的，而不能用貪心法解。 09/21 14:48
6F：→ s4300026: 當我沒說，哈哈，你的例子，我的方法就無用了09/21 14:49
7F：→ sarafciel: 樓上的作法感覺先做一遍reverse後可以解?09/21 15:10
8F：推 a21802: 但是這個你的這個規律會因為消的順序不同有不同結果09/21 17:03
9F：推 cphe: 它應該就是只要找到一個順序可以全消就算吧09/21 17:23
10F：→ sarafciel: 樓樓上一講我才發現原PO給的例子好像兩個xx位移了XD09/21 17:35
11F：→ a106a106: 的確是，只要找到可以消完的方法就算可以，而消字串的09/21 18:30
12F：→ a106a106: 順序不需固定 09/21 18:30
目前有關於線性串列的想法，如果把xyxxxyyx轉成陣列{1, 1, 3, 2, 1}的表示，如果把中
間3個x刪掉後就變成{1, (1+2), 1}，再刪掉3個y變成{2}，即可成為空字串。
問題是消除的順序有很多種可能，目前我找不到完美的公式可以解決的
※ 編輯: a106a106 (27.242.102.238), 09/21/2018 18:36:09
13F：推 s4300026: 那我想到第二種做法，Y取代yy，Y左右都是x，則x均取代 09/21 18:51
14F：→ s4300026: 成X，直至無法取代，檢查無小寫字就過關。 09/21 18:51
15F：→ s4300026: Y左右檢查不受大寫字影響 09/21 18:52
16F：推 s4300026: 話說這應該去prob_solve 09/21 18:55
17F：推 LPH66: 樓上一樣, 決定取代的順序會有差 09/21 19:51
18F：→ longlongint: 用 stack 09/21 21:11
19F：→ longlongint: 哦 原來刪的順序有差 QQ 09/21 21:15
20F：推 oToToT: 感覺這不是要發在prob_solve嗎？ 09/22 23:45
21F：推 scott870430: 檢查左右是不是相同字元 09/23 00:04
22F：→ scott870430: 是的話優先消掉? 09/23 00:04
23F：推 alan23273850: 這題應該可以用 DP，我有空發文 09/23 10:18
24F：→ alan23273850: 想順便問大大那題的 judge 在哪，想先確定無 bug 09/23 11:30
27F：推 alan23273850: 樓上水喔～ 09/26 19:06