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

看板Python作者 (suhang)時間5年前 (2019/04/24 12:35), 編輯推噓3(3推 0噓 1→)
留言4則, 3人參與, 5年前最新討論串1/1
問最小交換次數，使字元兩兩一致 例如 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
推
04/25 03:06, 5年前 , 1F
九章算法上類似題的討論 https://www.jiuzhang.com/qa/34/
04/25 03:06, 1F
→
04/26 04:02, 5年前 , 2F
okok tks, 我讀讀，感謝
04/26 04:02, 2F
推
04/26 17:42, 5年前 , 3F
aababb 只要交換一次，但你的方法給 2
04/26 17:42, 3F
推
04/26 17:45, 5年前 , 4F
可能要排列組合出所有目標，再找和初始狀態距離最短的
04/26 17:45, 4F
‣ 更多 suhang 的文章
文章代碼(AID): #1Sl-UKEn (Python)