Fw: [問題] 最小交換次數使字元兩兩一致

看板Prob_Solve作者 (suhang)時間5年前 (2019/04/24 12:35), 編輯推噓1(1推 0噓 1→)
留言2則, 2人參與, 5年前最新討論串1/1
※ [本文轉錄自 Python 看板 #1Sl-UKEn ] 作者: suhang (suhang) 看板: Python 標題: [問題] 最小交換次數使字元兩兩一致 時間: Wed Apr 24 12:35:29 2019 問最小交換次數，使字元兩兩一致 例如 abcabc -> aabbcc or bbaacc or ccaabb 皆可 https://paste.ubuntu.com/p/4g2wbn5S2P/ 這題感覺好像DP, 但不知道怎麼DP 我寫了一個recursie, 可以找到aabbcc但是又無法證明這是"最小"次數 從 i = 0開始， 如果 s[i] != s[i+1] 那就開始線性搜尋可以交換的字元，交換之後遞歸往下 我這個做法是greedy嗎？ 遇到不相同字元，去找最近可以交換過來的字元，(感覺很貪婪) (我一直很不了解greedy的精神) 請問這題該怎麼解呢? tks -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.189.14.17 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1556080532.A.3B1.html ※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: suhang (73.189.14.17), 04/24/2019 12:35:50
→
04/24 22:45, 5年前 , 1F
題目敘述完整一點吧
04/24 22:45, 1F
推
04/25 02:44, 5年前 , 2F
是只能跟隔壁交換還是任意兩位置都能換
04/25 02:44, 2F
‣ 更多 suhang 的文章
文章代碼(AID): #1Sl-Ud4t (Prob_Solve)