[问题] 最小交换次数使字符两两一致

楼主: suhang (suhang)   2019-04-24 12:35:29
问最小交换次数,使字符两两一致
例如 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
作者: vnon (路人)   2019-04-25 03:06:00
九章算法上类似题的讨论 https://www.jiuzhang.com/qa/34/
楼主: suhang (suhang)   2019-04-26 04:02:00
okok tks, 我读读,感谢
作者: eight0 (欸XD)   2019-04-26 17:42:00
aababb 只要交换一次,但你的方法给 2可能要排列组合出所有目标,再找和初始状态距离最短的

Links booklink

Contact Us: admin [ a t ] ucptt.com