首页 > 编程语言 >小于n的最大数 - 贪心算法及证明 - 附python实现

小于n的最大数 - 贪心算法及证明 - 附python实现

时间:2024-06-18 14:28:53浏览次数:24  
标签:digits 最大数 python possible 给定 mp str 贪心 数位

一、问题描述?

        给定一个整数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

相关文章

  • Python - Meta Class
    Aspartofmetaprogramming,ametaclassisoneofthemostimportantconceptsinPython.AClassinPythondefinesthefunctionalityofitsobjectsusingattributesandmethods.Incontrast,ametaclassdefinesthefunctionalityoftheclasses,whereast......
  • python 开发工具IDE 之 thonny
    一、thonny简介    thonny是一款开源免费的pythonIDE(集成开发环境),其内置python解释器,无需安装python解释器和配置环境变量。下载thonny,安装即可使用,轻量简便,省去python环境安装及配置的烦恼。二、thonny优缺点   优点:简单轻便,免费开源,支持中文且功能不复杂,适......
  • 补充第一天的python学习笔记
    昨天晚上学习到10点左右太困了,没有完成既定目标,迁延一日。补充下昨天的学习内容,算是对第一天学习时的回顾。1.字符集编码(1)utf-8全球通用,一个字节等于8个二进制位,utf-8用于中文占3个字节(2)unicode全球通用,16位二进制以上(3)gbk专为中国人设计的编码,一个文字占2个字节......
  • Fatal error in launcher: Unable to create process using ‘“python.exe“ “\pyt
    1.设置环境变量将pip和python的路径加入环境变量中2.在cmd中,查看是否存在python,pip等3.把应用安装程序中的python.exe和python3.exe关闭4.正常使用详情请看微软的常见问题,链接如下:关于在Windows上使用Python的FAQ|MicrosoftLearn......
  • 每日一题——Python实现PAT甲级1132 Cut Integer(举一反三+思想解读+逐步优化)五千字好
    一个认为一切根源都是“自己不够强”的INTJ个人主页:用哲学编程-CSDN博客专栏:每日一题——举一反三Python编程学习Python内置函数Python-3.12.0文档解读目录 我的写法正确性和功能性时间复杂度空间复杂度其他点评总结我要更强优化后的时间复杂度和空间复杂度进一......
  • Python实现快速获取历史气象数据
    利用Python中pandas库的read_html功能从网站查历史天气(q-weather.info)获取历史气象数据,并使用tkinter库实现窗口可视化。代码如下:1.首先导入必要的库:importtkinterastkfromtkinterimportmessageboximportpandasaspd2.定义一个用法,使用户可以查看所有气象基准......
  • 深入解析:如何通过Python脚本将YOLO标注格式转换为COCO格式并进行验证
    深入解析:如何通过Python脚本将YOLO标注格式转换为COCO格式并进行验证随着深度学习和计算机视觉技术的飞速发展,物体检测成为了一个热门的研究领域。在物体检测任务中,YOLO(YouOnlyLookOnce)和COCO(CommonObjectsinContext)是两个非常重要的标注格式。YOLO因其高效的实时物......
  • 深入解析:如何通过Python脚本将LabelMe标注格式转换为YOLO格式并进行验证
    深入解析:如何通过Python脚本将LabelMe标注格式转换为YOLO格式并进行验证在计算机视觉领域,标注格式的转换是一个经常会遇到的问题。不同的标注格式有不同的应用场景和优势,能够灵活地进行转换是非常重要的技能。在这篇文章中,我们将详细介绍如何通过Python脚本将LabelMe标注格......
  • 【python】OpenCV—Segmentation
    文章目录cv2.kmeans牛刀小试cv2.kmeanscv2.kmeans是OpenCV库中用于执行K-Means聚类算法的函数。以下是根据参考文章整理的cv2.kmeans函数的中文文档:一、函数功能cv2.kmeans用于执行K-Means聚类算法,将一组数据点划分到K个簇中,使得簇内的数据点尽可能相......
  • 使用Python获取HTTP请求头数据
    前言在Web开发和API交互中,HTTP请求头扮演着至关重要的角色。它们不仅告诉服务器请求的类型(如GET、POST等),还包含了关于客户端、请求内容以及其他重要信息的数据。在Python中,我们可以使用requests库来发送HTTP请求,并查看服务器返回的响应头,但通常我们也需要了解我们发送的请求头内......