Top Interview 150
  • 👋Welcome!
  • 数组-字符串
    • 合并两个有序数组
    • 移除元素
    • 删除有序数组中的重复项
    • 删除有序数组中的重复项II
    • 买卖股票的最佳时机
    • 买卖股票的最佳时机II
    • 多数元素
    • 罗马数字转整数
    • 轮转数组
    • 跳跃游戏
    • 跳跃游戏II
    • 找出字符串中第一个匹配项的下标
    • 柠檬水找零
    • 最长回文子串
    • H指数
    • O(1)时间插入、删除和获取随机元素
    • 除自身以外数组的乘积
    • 加油站
    • 分发糖果
    • 最后一个单词的长度
    • 整数转罗马数字
    • 最长公共前缀
    • 反转字符串重的单词
    • N字形变换
    • 文本左右对齐
  • 双指针
    • 验证回文串
    • 判断子序列
    • 两数之和 II - 输入有序数组
    • 三数之和
    • 盛最多水的容器
  • 滑动窗口
    • 长度最小的子数组
    • 无重复字符的最长子串
    • 串联所有单词的子串
    • 最小覆盖子串
  • 矩阵
    • 有效的数独
    • 螺旋矩阵
    • 旋转矩阵
    • 矩阵置零
    • 生命游戏
  • 哈希表
    • 赎金信
    • 两数之和
    • 快乐数
    • 同构字符串
    • 单词规律
    • 有效的字母异位词
    • 字母异位词分组
    • 存在重复元素 II
    • 最长连续序列
  • 区间
    • 汇总区间
    • 合并区间
    • 插入区间
    • 用最少数量的箭箭引爆气球
  • 栈
    • 有效的括号
    • 简化路径
    • 最小栈
    • 基本计算器
    • 逆波兰表达式求值
  • 链表
    • 环形链表
    • 两数相加
    • 合并两个有序链表
    • 复制带随机指针的链表
    • 反转链表 II
    • 删除链表的倒数第 N 个结点
    • 删除排序链表中的重复元素
    • 旋转链表
    • 分隔链表
    • LRU 缓存
    • K个一组翻转链表
  • 树
    • 二叉树的最大深度
    • 相同的树
    • 翻转二叉树
    • 对称二叉树
    • 填充每个节点的下一个右侧节点指针
    • 二叉树展开为链表
    • 从前序和中序遍历序列构造二叉树
    • 求根节点到叶节点数字之和
    • 二叉树中最大路径和
    • 二叉搜索树迭代器
    • 完全二叉树的节点个数
    • 二叉树的最近公共祖先
    • 二叉树的右视图
    • 二叉树的层平均值
    • 二叉树的层序遍历
    • 二叉树的锯齿形层序遍历
    • 二叉搜索树的最小绝对差
    • 二叉搜索树中第K小的元素
    • 验证二叉搜索树
  • 图
    • 岛屿数量
    • 被围绕的区域
    • 克隆图
    • 除法求值
    • 课程表
    • 课程表 II
  • 广度优先搜索
    • 蛇梯棋
    • 最小基因变化
    • 单词接龙
  • 深度优先搜索
  • 字典树
    • 实现 Trie (前缀树)
    • 添加与搜索单词 - 数据结构设计
    • 单词搜索 II
  • 回溯
    • 电话号码的字母组合
    • 组合
    • 全排列
    • 组合总和
    • 括号生成
    • n皇后问题II
    • 单词搜索
  • 分治
    • 将有序数组转换为二叉搜索树
    • 排序链表
  • Kadane 算法
    • 环形子数组的最大和
    • 最大子数组和
  • 二分查找
    • 搜索插入位置
    • 寻找峰值
    • 搜索二维矩阵
  • 堆
  • 位运算
    • 二进制求和
    • 颠倒二进制位
    • 位1的个数
    • 只出现一次的数字
    • 只出现一次的数字 II
    • 数字范围按位与
  • 数学
    • 回文数
    • 阶乘后的零
    • 加一
    • x 的平方根
    • Pow(x, n)
    • 直线上最多的点数
  • 动态规划
    • 爬楼梯
    • 打家劫舍
    • 单词拆分
    • 最长递增子序列
    • 零钱兑换
    • 三角形最小路径和
    • 最小路径和
    • 不同路径 II
    • 最长回文子串
    • 交错字符串
    • 编辑距离
由 GitBook 提供支持
在本页
  • 解题思路一:
  • 复杂度分析一
  • 解题思路二:
  • 复杂度分析二

这有帮助吗?

在GitHub上编辑
  1. 数组-字符串

整数转罗马数字

上一页最后一个单词的长度下一页最长公共前缀

最后更新于1年前

这有帮助吗?

题目链接:

解题思路一:

  1. 列出从高到低列出每个罗马数字对应的阿拉伯数字,额外再加上4、9、40、90、400、900对应的罗马数字

  2. 逐个取出阿拉伯数字,然后用num循环减去该数字,直至num小于阿拉伯数字再取下一个,每减一次,则在结果字符串上追加一个对应的罗马数字

var (
	values = []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
)

func intToRoman(num int) string {
	res := ""
	for _, value := range values {
		for num >= value {
			num -= value
			switch value {
			case 1000:
				res += "M"
			case 900:
				res += "CM"
			case 500:
				res += "D"
			case 400:
				res += "CD"
			case 100:
				res += "C"
			case 90:
				res += "XC"
			case 50:
				res += "L"
			case 40:
				res += "XL"
			case 10:
				res += "X"
			case 9:
				res += "IX"
			case 5:
				res += "V"
			case 4:
				res += "IV"
			case 1:
				res += "I"
			}
		}
		if num == 0 {
			break
		}
	}
	return res
}

复杂度分析一

  • 时间复杂度: 对 valuesvaluesvalues 进行了一次遍历,又在其中对 numnumnum 进行了循环处理,时间复杂度为 O(n2)O(n^2)O(n2)

  • 空间复杂度: valuesvaluesvalues 属于预定义数据,占用空间排除在算法外,空间复杂度为 O(1)O(1)O(1)

解题思路二:

  1. 列举出1到9,10-90,100-900,1000-3000对应的每个层级的罗马字符

  2. 对num进行处理,计算出每个层级对应的数字取出相应的罗马字符进行拼接

var (
	thousand = []string{"", "M", "MM", "MMM"}
	hundred  = []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
	ten      = []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
	one      = []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VII", "IX"}
)

func intToRoman(num int) string {
	return thousand[num/1000] + hundred[num%1000/100] + ten[num%100/10] + one[num%10]
}

复杂度分析二

  • 时间复杂度: 时间复杂度为 O(1)O(1)O(1)

  • 空间复杂度: 空间复杂度为 O(1)O(1)O(1)

https://leetcode.cn/problems/integer-to-roman