问一道前几天在版上看见的题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道前几天在版上看见的题

问一道前几天在版上看见的题# JobHunting - 待字闺中

w*y2013-06-05 07:06

1 楼

两个数，用第一个数里的digits，做一个比第二个数大的最小数
譬如第一个数 2241, 第二个 123, 答案是124
记得讨论过算法的，我忘记该怎么实现了

r*h2013-06-05 07:06

2 楼

greedy就可以吧
从第二个数的高位开始，每次尽量选择第一个数里面未使用且和第二个数的对应位相同
的数字match
总会有一个match不上的（否则相等），此时做一个标记，然后从剩下的数里面依次取
最小的
比如A=335678，B=3422
第一位取3，第二位没法match就取5，然后取剩下的最小数
得到3536

v*k2013-06-05 07:06

3 楼

这个题很恶心，考点可能在找不到怎么处理上

w*y2013-06-05 07:06

4 楼

恩我记得也是大概这样做，就是忘记很多细节怎么处理了。我能想到的就是2中情况
按照标记的这种思路，每一位都试图找跟它相等的数字or 次小数
1. 如果曾经用一个次小数放在‘高位’了，后面就取剩下的最小数
2. 如果到了某一位，找不到跟它相等or 比它稍微大一点的，就得往回退，我还没想明
白往回退是怎么弄的
譬如 A=2345678，B=3429, 怎么找到 3452呢？怎么把这种往回退的也标记成跟上一
个case一样？

【在 r**h 的大作中提到】

: greedy就可以吧
: 从第二个数的高位开始，每次尽量选择第一个数里面未使用且和第二个数的对应位相同
: 的数字match
: 总会有一个match不上的（否则相等），此时做一个标记，然后从剩下的数里面依次取
: 最小的
: 比如A=335678，B=3422
: 第一位取3，第二位没法match就取5，然后取剩下的最小数
: 得到3536

t*h2013-06-05 07:06

5 楼

from collections import defaultdict
num1=2345678
num2=3429
def convert2int(lst):
return int(''.join(map(str,lst)))
def compare(num, result,l,digits):
n1=convert2int(str(num)[:l+1])
n2=convert2int(result[:l+1])
if l==(digits-1):
return n2>n1
return n2>=n1
def find_next(x1,num,result,digits,l):
if l==digits:
print 'found:'+''.join(map(str,result))
return
for i in xrange(10):
x=x1.copy()
if x[i]>0:
result[l]=i
x[i]-=1
if compare(num,result,l,digits):
find_next(x,num,result,digits,l+1)
s1=str(num1)
s2=str(num2)
x=defaultdict(int)
for c in str(num1): x[int(c)]+=1
digits=len(s2)
result=[0]*5
find_next(x,num2,result,digits,0)

【在 w***y 的大作中提到】

: 恩我记得也是大概这样做，就是忘记很多细节怎么处理了。我能想到的就是2中情况
: 按照标记的这种思路，每一位都试图找跟它相等的数字or 次小数
: 1. 如果曾经用一个次小数放在‘高位’了，后面就取剩下的最小数
: 2. 如果到了某一位，找不到跟它相等or 比它稍微大一点的，就得往回退，我还没想明
: 白往回退是怎么弄的
: 譬如 A=2345678，B=3429, 怎么找到 3452呢？怎么把这种往回退的也标记成跟上一
: 个case一样？