作者suhang (suhang)
看板Prob_Solve
标题Fw: [问题] 最小交换次数使字元两两一致
时间Wed Apr 24 12:35:50 2019
※ [本文转录自 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://webptt.com/cn.aspx?n=bbs/Python/M.1556080532.A.3B1.html
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 转录者: suhang (73.189.14.17), 04/24/2019 12:35:50
1F：→ s89162504: 题目叙述完整一点吧 04/24 22:45
2F：推 GYLin: 是只能跟隔壁交换还是任意两位置都能换 04/25 02:44