一、问题描述?
给定一个整数n,并从1~9中给定若干个可以使用的数字,根据上述两个条件,得到每一位都为给定可使用数字的、最大的小于整数n的数。
例如,给定可以使用的数字为 {2,3,8} 三个数:
给定 n=3589,输出3388;给定 n=8234,输出8233;……
二、解题思路
m : 求解目标值
若m位数为 n位数-1 显然m 各位上的值取digits中最大值,
以下仅讨论 m位数 与 n位数 相等的情况
定义A, B, C
A : m中与n中对应数位上的数 a, b; a = b 时称之为A数位
B : m中与n中对应数位上的数 a, b; a < b 时称之为B数位
C : m中与n中对应数位上的数 a, b; a > b 时称之为C数位
则m的形式必定为 A...A B C...C
① B数位的个数 有且仅有一个
若不存在B数位,m显然大于n
若存在多个B数位, 显然存在一个大于m的解 (即 将第二个B数位修改为C数位)
② B数位之前仅存在A数位
若存在C数位则 m > n
若存在B数位则不满足 B数位的个数 有且仅有一个
③ A数位个数可为0
显然为求m的最大值应使得A数位尽量长;由数位定义可知
A数位上数字存在于digits中
B数位为 digits中 小于n中对应数位值的 最大数
C数位为max(digits)
由②可知若A数位的范围为 str(n)[0:i]
则B数位的范围为 str(n)[0:i + 1]
作者:florem
链接:https://leetcode.cn/circle/discuss/zE5rg7/
def max_m(n, digits):
s_n = str(n)
s_digits = sorted(map(str, digits), reverse=True)
mp = dict() # k : v digits中小于k的最大值
for k in '0123456789':
mp[k] = '#'
for v in s_digits:
if v < k:
mp[k] = v
break
possible_b = -1
for i, c in enumerate(s_n):
if mp[c] != '#':
possible_b = i
if c not in s_digits:
break
ret = s_digits[0] * (len(s_n) - 1)
if possible_b != -1:
ret = s_n[:possible_b] + mp[s_n[possible_b]] + s_digits[0] * (len(s_n) - possible_b - 1)
return int(ret)
标签:digits,最大数,python,possible,给定,mp,str,贪心,数位
From: https://blog.csdn.net/qq_52058966/article/details/139772346