【问题】求问一个算法题

Albert115

2018/9/24镜像同步17 回复

一个字符串由0-9数字组成，删除其中出现多次的字符，只保留一次，保证前后关系不变的情况下，使得最后组成的数字最小？例子：1254601245 结果最小数字为：124605

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

fouzhe机器人#1 · 2018/9/24

状态压缩dp

a68415327机器人#2 · 2018/9/24

私以为最后的结果应该是124605 解法：先通过n复杂度扫描确定位数。然后从0-9的优先级填充位数即可… 我也不确定，等大佬

Albert115机器人#3 · 2018/9/24

【在 fouzhe 的大作中提到: 】 : 状态压缩dp 这个应该怎么写啊？

Albert115机器人#4 · 2018/9/24

【在 a68415327 的大作中提到: 】 : 私以为最后的结果应该是124605 : 解法：先通过n复杂度扫描确定位数。然后从0-9的优先级填充位数即可… : : ................... 对，结果应该是124605，我已经改了

fouzhe机器人#5 · 2018/9/24

dp[i][S]表示从第1位到第i位，选择的结果为S时组成的最小数字，从前往后递推即可。同时可以发现第一维可以用滚动数组优化。 S是一个10位二进制数，某个数字已经出现则相应二进制位为1，否则为0。感觉可能有贪心解法。【在 Albert115 的大作中提到: 】 :

intmain机器人#6 · 2018/9/24

扫描一遍所有digit, 记录0-9每个digit出现的个数。然后优先使结果数字的最高位尽可能的小，需要找出最高位的候选数字，候选数字包括最长的重复数字前缀后面再加一个非重复数字，因为重复数字都可以被删除。从中选出最小的数字作为首位，然后之前的数字被删除，数字被选中说明其他位置上的该数字被删除；依次选出后续的最高位即可得出结果～

Albert115机器人#7 · 2018/9/25

【在 fouzhe 的大作中提到: 】 : dp[i][S]表示从第1位到第i位，选择的结果为S时组成的最小数字，从前往后递推即可。同时可以发现第一维可以用滚动数组优化。 : S是一个10位二进制数，某个数字已经出现则相应二进制位为1，否则为0。 : 感觉可能有贪心解法。 : ................... 这个方法写出来在某种情况下是不对的，例如，输入12546015061245，输出是120564，正确结果是015624

fouzhe机器人#8 · 2018/9/25

应该是你的写法问题吧。这种应该是很正确的写法。【在 Albert115 的大作中提到: 】 :

Albert115机器人#9 · 2018/9/25

【在 fouzhe 的大作中提到: 】 : 应该是你的写法问题吧。 : 这种应该是很正确的写法。 : : 当输入12546015061245时，你的算法输出结果是120564，最小值是015624