深入探索力扣第12题:整数转罗马数字的算法之旅

力扣(LeetCode)第12题“整数转罗马数字”提供了一个绝佳的学习机会,不仅让我们深入古罗马的数字系统,也锻炼了我们的编程技巧。一起看看其背后的逻辑。

罗马数字基础

罗马数字是一种古老的数字表示方法,广泛用于古罗马时期。不同于现代的十进制数字系统,罗马数字使用字母来表示不同的数值。以下是罗马数字的基本组成部分:

  • I(1)、V(5)、X(10)、L(50)、C(100)、D(500)、M(1000)

罗马数字的构造规则相对直观:通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

问题描述

力扣第12题要求我们将给定的整数转换为罗马数字表示,该整数范围从1到3999。这个范围的限定是由罗马数字表示的上限所决定的。

示例 1:

输入: num = 3
输出: "III"
示例 2:

输入: num = 4
输出: "IV"
示例 3:

输入: num = 9
输出: "IX"
示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

算法思路

要有效地解决这个问题,我们可以采用“贪心算法”来逐步构建罗马数字表示。贪心算法是一种在当前步骤中选取最优解的算法,以此希望整体达到最佳解的策略。

解题步骤

  1. 准备映射表:首先,创建一个映射表,列出所有单一罗马数字及其值,以及特殊的减法规则组合(如IV表示4)。
  2. 逐步减少:从最大的数值和对应的罗马数字开始,尽可能多地从输入整数中减去该数值,每次减去时,将相应的罗马数字添加到结果字符串中。
  3. 重复直到完成:继续此过程,直到整数减少到0。

代码实现(Python)

def intToRoman(num: int) -> str:
    roman_map = [
(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
(100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
(10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")
]
    roman_numeral = ""
    for value, symbol in roman_map:
    while num >= value:
        num -= value
        roman_numeral += symbol
return roman_numeral

性能分析

对于该算法,其时间和空间复杂度都可以认为是O(1),因为罗马数字表示的整数有一个上限(3999),算法运行时间和所需空间并不随输入整数的大小而变化。

算法图解

动态GIF图

为了将上述绘图过程转换成动态GIF图片,我们需要在Python中采用稍微不同的方法。这通常涉及到在每个绘图步骤中保存图像,并最后使用这些图像来创建GIF。下面是一个如何实现这一过程的示例:

  1. 保存每一步的图像:在循环中,每执行一次操作(即每次从数字中减去一个罗马数字值),我们都将保存当前的图表状态作为一个图像文件。
  2. 创建GIF:使用这些图像文件创建GIF。我们可以使用像imageio这样的库来完成这个任务。

bb425c7b1df14e7385349539ee093b38.gif

代码实现(Python)

首先,确保你已经安装了imageio库。如果还没有安装,你可以通过运行pip install imageio来安装它。

接下来,让我们更新代码来实现这个过程:

 

import matplotlib.pyplot as plt
import imageio
import os

# 定义罗马数字映射和待转换的数字
numerals = [
    (1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
    (100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
    (10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')
]
num = 1994
original_num = num

# 准备存放每一帧图像的目录
frames_dir = "frames_dir"
os.makedirs(frames_dir, exist_ok=True)

filenames = []  # 存储每一帧图像文件名

# 转换过程
result = ""  # 累积的罗马数字
for value, symbol in numerals:
    while num >= value:
        num -= value
        result += symbol

        # 绘图
        fig, ax = plt.subplots(figsize=(10, 6))
        ax.text(0.5, 0.7, f'Converting: {original_num} to Roman Numerals', ha='center', va='center', fontsize=14)
        ax.text(0.5, 0.5, f'- {symbol} ({value})', ha='center', va='center', fontsize=20, color='red')
        ax.text(0.5, 0.4, f'Remaining: {num}', ha='center', va='center', fontsize=14)
        ax.text(0.5, 0.6, f'Converted: {result}', ha='center', va='center', fontsize=14)
        ax.axis('off')

        # 保存图像
        filename = os.path.join(frames_dir, f'frame_{original_num - num}.png')
        plt.savefig(filename)
        plt.close()
        filenames.append(filename)

# 生成GIF
gif_filename = 'roman_conversion.gif'
with imageio.get_writer(gif_filename, mode='I', duration=0.5) as writer:
    for filename in filenames:
        image = imageio.imread(filename)
        writer.append_data(image)

# 清理临时文件
for filename in filenames:
    os.remove(filename)
os.rmdir(frames_dir)

print(f"GIF saved as {gif_filename}")

执行步骤解析

  1. 初始化和映射定义:设置罗马数字映射和待转换的数字。
  2. 创建帧目录:为每一步生成的图像帧创建一个存放目录。
  3. 绘图和保存:对每个罗马数字减法操作,绘制并保存一帧图像。
  4. GIF生成:使用imageio读取所有帧图像并合成GIF。
  5. 清理:删除所有临时帧图像和目录。

结论

通过动态的GIF图示我们更好的掌握算法的运行步骤

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/518950.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

linux安装和使用Rancher

linux安装和使用Rancher Rancher介绍请看如下博客 arm架构安装Rancher并导入k8s集群解决Error: no objects passed to apply 华为云arm架构安装k8s(kubernetes) linux下安装Rancher Rancher部署监控k8s集群状态等,比Dashboard插件强大 提前安装好K8S 在master上执行#如果…

【GFS】大数据技术的基石,分布式文件系统的鼻祖

目录 1.概述 1.1.分布式文件系统在大数据中的基石地位 1.1.谷歌当初面对的问题 1.2.谷歌如何解决这些问题的 1.数据量大,数据格式复杂,有大文件也有小文件 2.运行在普通机器上,失效是常态 2.系统架构 3.读操作 4.写操作 5.追加操作…

TiDB 社区智慧合集丨解码 TiDB 性能谜题:让你的数据库发挥最强动力!

来自社区,回归社区。非常感谢各位 TiDBer 在之前 【TiDBer 唠嗑茶话会丨征集 TiDB 数据库性能优化大师,你是如何优化 TiDB 数据库性能的呐?】( https://asktug.com/t/topic/1005563 )里提供的各种性能优化方法。这篇帖子收集整理了大家推荐的…

STL库 —— string 类的编写

目录 一、成员函数 1.1 构造函数 1.1.1 无参构造 1.1.2 传参构造 1.1.3 优化 1.2 析构函数 1.3 拷贝构造函数 1.4 赋值运算符重载 二、容量成员 2.1 size 函数 2.2 capacity 函数 2.3 reserve 函数 2.3 resize 函数 2.4 clear 函数 三、元素访问成员 3.1 [] 的…

希尔排序解读

在算法世界中,排序算法是至关重要的一部分。而希尔排序(Shell Sort)作为一种基于插入排序的改进算法,通过允许交换非相邻元素,从而在一定程度上提高了排序效率。本文将深入探讨希尔排序的原理、实现方式以及它的性能特…

InternLM2-Chat-1.8B 模型测试

在interStudio进行InternLM2-Chat-1.8B模型访问,进入开发机后 配置基础环境 新建conda环境并且进入 conda create -n demo python3.10 -y conda activate demo 下载pytorch等相关包 conda install pytorch2.0.1 torchvision0.15.2 torchaudio2.0.2 pytorch-cuda11.…

力扣 76.最小覆盖子串

题目: 题目理解:这题属于最小滑动窗口。所求得的连续滑动窗口包含来t中的字符,不一定要按照t中的顺序。 class Solution {public String minWindow(String s, String t) {// table表示字符串t里的字符if (s null || s.length() 0 || t n…

ThingsBoaed、系统模块层级讲解

系统管理员能够使用租户配置文件为多个租户配置通用设置。每个租户在单个时间点都拥有唯一的个人资料。 让我们一一查看租户配置文件中的可用设置。 配置文件配置 这些设置允许系统管理员配置对租户创建的实体数量的限制,设置每月最大消息数、API 调用数的限制&…

Java集合详解(一)-- List集合

1.集合简介 java集合可分为Set、List、Queue和Map四种体系。 Java集合就像一种容器,可以把多个对象(实际上是对象的引用,但习惯上都称对象)“丢进”该容器中。从Java 5 增加了泛型以后,Java集合可以记住容器中对象的数…

02-JDK新特性-try-with-resources自动管理资源关闭

try-with-resources 为什么要介绍这个了 看看一下以下代码: public static void fileCopyByTryWithResources(File src, File des) throws IOException {try (FileInputStream fis new FileInputStream(src); FileOutputStream fos new FileOutputStream(des);…

SecureCRT防止超时自动断开

Options——>Session Options——>Terminal——>选择 Send protocol NO-OP ——>60seconds(每一分钟发送一次请求)

【考研数学】《1800》《660》还是《880》?怎么刷效果最好?

刷题吃不透,做了再多也没用! 你目前连1800都没法拿下,你还着急要做660和880,是认真的吗? 这《接力题典1800》有啥特色呢?知识点全面覆盖,题目中规中矩,配合汤老师的视频看效果更佳…

【二分查找】Leetcode 二分查找

题目解析 二分查找在数组有序可以使用,也可以在数组无序的时候使用(只要数组中的一些规律适用于二分即可) 704. 二分查找 算法讲解 当left > right的时候,我们循环结束,但是当left和right缩成一个点的时候&#x…

【Java SE】继承与组合

🥰🥰🥰来都来了,不妨点个关注叭! 👉博客主页:欢迎各位大佬!👈 文章目录 1. 再谈初始化2. 再谈protected关键字2.1 子类可见性2.2 访问修饰限定符的选择 3. 继承与组合 1. 再谈初始化…

Python实现获取某手视频评论【自动生成did】

今天在获取某手视频评论的时候,总是会出发风控导致web_did失效,就算登录了也没用,还会导致账号被风控,app端抓包和逆向难度又大,那么有没有一种不需要登录而且不会出发风控的方法来获取评论列表呢?当然有&a…

Python球球大作战

文章目录 写在前面球球大作战程序设计注意事项写在后面 写在前面 安装pygame的命令: pip install -i https://pypi.tuna.tsinghua.edu.cn/simple pygame球球大作战 《球球大作战》是一款简单易上手、充满趣味性和竞技性的休闲手游。游戏的核心玩法可以用一句话概…

机器学习 | 基于Scikit-learn中手写数字集的交叉验证

在本文中,我们将讨论交叉验证及其在手写数字集上的使用。此外,我们将看到使用手写数字集的代码实现。 什么是交叉验证? 手写数字集的交叉验证将允许我们选择最佳参数,避免过度拟合训练数据集。它是一个试验的尝试程序&#xff0…

【Python】Tkinter模块(巨详细)

专栏文章索引:Python 有问题可私聊:QQ:3375119339 目录 一、窗口设计 1.创建窗口 2.窗口属性 3.窗口位置 4.Widget 一、窗口设计 1.创建窗口 实例-创建空白窗口: from tkinter import * # 导入tkinter模块win Tk() # 通…

算法(二分查找)

我们有三种方式可以使用二分查找 1.朴素的二分查找,这种方式可能存在局限性 2.查找左边界的二分查找 3.查找右边界的二分查找 1.二分查找 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums…

JVM调优参数介绍

堆配置 -Xms:初始堆大小 -Xms:最大堆大小 -XX:NewSizen:设置年轻代大小 -XX:NewRation:设置年轻代和年老代的比值。如:为3表示年轻代和年老代比值为1:3,年轻代占整个年轻代年老代和的1/4 -XX:SurvivorRation:年轻代中Eden区与…