[問題] C/C++字串處理問題

看板C_and_CPP作者 (猜猜我4誰)時間7年前 (2018/09/21 14:01), 7年前編輯推噓11(11推 0噓 16→)
留言27則, 12人參與, 7年前最新討論串1/3 (看更多)
最近練習時寫到一個題目 給一個只由兩個字元(x、y)組成的字串(不超過30字) 例：xxyxxyxyy 把字串內相同的字劃分成一組 變成：xx y xx y x yy，如此就有6個組 再把有兩個相同字以上的組刪除 例如：xxyxxyxyy→xxyxxyx→xxyyxxx→xxxxx→空字串 題目：隨機給定一字串，判斷此字串最後能不能變成空字串 列出了很多組字串思考，原本是想找有aba或bab單獨存在的字串，但後來發現無論如何都會 有例外，一直找不到可以直接判斷的方法，想請問有沒有大大對這題有任何想法可以一起討 論，我想了好幾天都想不出來... 謝謝大家QQQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.102.238 ※ 文章網址: https://www.ptt.cc/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
→
09/21 14:17, 7年前 , 1F
就一直跑看會不會變空字串不就好了
09/21 14:17, 1F
推
09/21 14:48, 7年前 , 2F
我的想法是存入vector，用for，如果iter值跟下一個相同
09/21 14:48, 2F
→
09/21 14:48, 7年前 , 3F
，就再檢查下一個，直至不相同，然後刪除中間區塊，iter
09/21 14:48, 3F
→
09/21 14:48, 7年前 , 4F
--，iter到底後檢查vector是否為空，結案。 值得思考的
09/21 14:48, 4F
→
09/21 14:48, 7年前 , 5F
是，有沒有特解是要先消後面一組的，而不能用貪心法解。
09/21 14:48, 5F
→
09/21 14:49, 7年前 , 6F
當我沒說，哈哈，你的例子，我的方法就無用了
09/21 14:49, 6F
→
09/21 15:10, 7年前 , 7F
樓上的作法感覺先做一遍reverse後可以解?
09/21 15:10, 7F
推
09/21 17:03, 7年前 , 8F
但是這個你的這個規律會因為消的順序不同有不同結果
09/21 17:03, 8F
推
09/21 17:23, 7年前 , 9F
它應該就是只要找到一個順序可以全消就算吧
09/21 17:23, 9F
→
09/21 17:35, 7年前 , 10F
樓樓上一講我才發現原PO給的例子好像兩個xx位移了XD
09/21 17:35, 10F
→
09/21 18:30, 7年前 , 11F
的確是，只要找到可以消完的方法就算可以，而消字串的
09/21 18:30, 11F
→
09/21 18:30, 7年前 , 12F
順序不需固定
09/21 18:30, 12F
目前有關於線性串列的想法，如果把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
推
09/21 18:51, 7年前 , 13F
那我想到第二種做法，Y取代yy，Y左右都是x，則x均取代
09/21 18:51, 13F
→
09/21 18:51, 7年前 , 14F
成X，直至無法取代，檢查無小寫字就過關。
09/21 18:51, 14F
→
09/21 18:52, 7年前 , 15F
Y左右檢查不受大寫字影響
09/21 18:52, 15F
推
09/21 18:55, 7年前 , 16F
話說這應該去prob_solve
09/21 18:55, 16F
推
09/21 19:51, 7年前 , 17F
樓上一樣, 決定取代的順序會有差
09/21 19:51, 17F
→
09/21 21:11, 7年前 , 18F
用 stack
09/21 21:11, 18F
→
09/21 21:15, 7年前 , 19F
哦 原來刪的順序有差 QQ
09/21 21:15, 19F
推
09/22 23:45, 7年前 , 20F
感覺這不是要發在prob_solve嗎？
09/22 23:45, 20F
推
09/23 00:04, 7年前 , 21F
檢查左右是不是相同字元
09/23 00:04, 21F
→
09/23 00:04, 7年前 , 22F
是的話優先消掉?
09/23 00:04, 22F
推
09/23 10:18, 7年前 , 23F
這題應該可以用 DP，我有空發文
09/23 10:18, 23F
→
09/23 11:30, 7年前 , 24F
想順便問大大那題的 judge 在哪，想先確定無 bug
09/23 11:30, 24F
推
09/24 03:11, 7年前 , 25F
能走回中間=>可變成空字串
09/24 03:11, 25F
→
09/25 18:53, 7年前 , 26F
https://pastebin.com/SjiDRPjC 用上面的想法通過題目了
09/25 18:53, 26F
推
09/26 19:06, 7年前 , 27F
樓上水喔～
09/26 19:06, 27F
‣ 更多 a106a106 的文章
文章代碼(AID): #1Rf8aTlF (C_and_CPP)
‣ 更多 a106a106 的文章
文章代碼(AID): #1Rf8aTlF (C_and_CPP)