leetcode第12题

简介: 相当简洁了,主要就是把所有的组合列出来,因为罗马数字表示的大小就是把所有字母相加,所以每次 append 那个,再把对应的值减去就行了。时间复杂度:不是很清楚,也许是 O(1)?因为似乎和问题规模没什么关系了。空间复杂度:O(1)

image.png

top12

把数字转换成罗马数字,正常情况就是把每个字母相加,并且大字母在前,小字母在后,上边也介绍了像 4 和 9 那些特殊情况。

解法一

这个是自己的解法,主要思想就是每次取出一位,然后得到相应的罗马数字,然后合起来就行。

publicStringgetRoman(intnum,intcount){ //count 表示当前的位数,个位,十位...char[]ten={'I','X','C','M'}; //1,10,100,1000char[]five={'V','L','D'};//5,50,500Stringr="";
if(num<=3){
while(num!=0){
r+=ten[count];
num--;
        }
    }
if(num==4){
r=(ten[count]+"")+(five[count]+"");
    }
if(num==5){
r=five[count]+"";
    }
if(num>5&&num<9){
r=five[count]+"";
num-=5;
while(num!=0){
r+=ten[count];
num--;
        }
    }
if(num==9){
r= (ten[count] +"") + (ten[count+1] +"");
    }
returnr;
}
publicStringintToRoman(intnum) {
Stringr="";
intcount=0;
while(num!=0){
intpop=num%10;
r=getRoman(pop,count)+r;
count++;
num/=10;
    }
returnr;
}

时间复杂度:num 的位数 log_{10}(num)+1log10(num)+1所以时间复杂度是 O(log(n))。

空间复杂度:常数个变量,O(1)。

下边在分享一些 LeetCode 讨论里的一些解法。

解法二

https://leetcode.com/problems/integer-to-roman/discuss/6310/My-java-solution-easy-to-understand

publicStringintToRoman(intnum) {
int[] values= {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] strs= {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
StringBuildersb=newStringBuilder();
for(inti=0;i<values.length;i++) {
while(num>=values[i]) {
num-=values[i];
sb.append(strs[i]);
        }
    }
returnsb.toString();
}

相当简洁了,主要就是把所有的组合列出来,因为罗马数字表示的大小就是把所有字母相加,所以每次 append 那个,再把对应的值减去就行了。

时间复杂度:不是很清楚,也许是 O(1)?因为似乎和问题规模没什么关系了。

空间复杂度:O(1).


这道题感觉难度应该是 easy ,没有那么难,就是理清楚题意,然后就可以往出列举就行了。

目录
打赏
0
0
0
0
10
分享
相关文章
|
9月前
leetcode-472. 连接词
leetcode-472. 连接词
67 0
单链表反转 LeetCode 206
单链表反转 LeetCode 206
85 0
leetcode:53.最大字序和
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
63 0
每日算法系列【LeetCode 827】最大人工岛
每日算法系列【LeetCode 827】最大人工岛
143 0
LeetCode 389. 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
92 0
LeetCode 354. Russian Doll Envelopes
给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
88 0
LeetCode 354. Russian Doll Envelopes
leetcode第36题
一个 9 * 9 的数独的棋盘。判断已经写入数字的棋盘是不是合法。需要满足下边三点, • 每一行的数字不能重复 • 每一列的数字不能重复 • 9 个 3 * 3 的小棋盘中的数字也不能重复。 只能是 1 - 9 中的数字,不需要考虑数独最后能不能填满
104 0
leetcode第36题
leetcode第48题
将一个矩阵顺时针旋转 90 度,并且不使用额外的空间。大概属于找规律的题,没有什么一般的思路,观察就可以了。 解法一 可以先转置,然后把每列对称交换交换一下
100 0
leetcode第48题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等