每道题附链接跳转
12. 整数转罗马数字
罗马数字包含以下七种字符: I
, V
, X
, L
,C
,D
和 M
。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000
例如, 罗马数字 2 写做 II
,即为两个并列的 1。12 写做 XII
,即为 X
+ II
。 27 写做 XXVII
, 即为 XX
+ V
+ II
。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 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。
给你一个整数,将其转为罗马数字。
示例 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.
实现思路
这道题目和13题是一个相互的过程,一个是整数转罗马数字,一个是罗马数字转整数,相比较之下,罗马数字转整数会更简单一点(下题目)。本题的话有一个实现过程,先理清楚这个对应关系:int numN[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
char map[][3] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
然后考虑转化过程,140有很多种分解方法,(140=100+40 140=50+50+40等),但对应过来就是先取大的大一个
代码实现
char* intToRoman(int num) {
char* res = (char*)malloc(sizeof(char) * 100);
int numN[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
char map[][3] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int i = 0, index = 0;
while (num != 0) {
i=0;
while(numN[i]>num){
i++;
}
if (numN[i] <= num) {
num = num - numN[i];
for (int j = 0; j < strlen(map[i]); j++) {
res[index] = map[i][j];
index++;
}
}
}
res[index] = '\0';
return res;
}
13. 罗马数字转整数
罗马数字包含以下七种字符: I
, V
, X
, L
,C
,D
和 M
。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000
例如, 罗马数字 2
写做 II
,即为两个并列的 1 。12
写做 XII
,即为 X
+ II
。 27
写做 XXVII
, 即为 XX
+ V
+ II
。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 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。
给定一个罗马数字,将其转换成整数。
示例 1:
输入: s = "III"
输出: 3
示例 2:
输入: s = "IV"
输出: 4
示例 3:
输入: s = "IX"
输出: 9
示例 4:
输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
实现思路
这道题的实现思路很残暴,直接列举每一种可能出现的罗马数字的情况,遍历输出
代码实现
int romanToInt(char* s) {
char map[]={'I','V','X','L','C','D','M'};
int sum=0;
for(int i=0;i<strlen(s);i++){
if(s[i]==map[0]&&s[i+1]!=map[1]&&s[i+1]!=map[2]){
sum+=1;
}else if(s[i]==map[0]&&s[i+1]==map[1]){
sum+=4;i++;
}else if(s[i]==map[0]&&s[i+1]==map[2]){
sum+=9;i++;
}else if(s[i]==map[1]){
sum+=5;
}else if(s[i]==map[2]&&s[i+1]!=map[3]&&s[i+1]!=map[4]){
sum+=10;
}else if(s[i]==map[2]&&s[i+1]==map[3]){
sum+=40;i++;
}else if(s[i]==map[2]&&s[i+1]==map[4]){
sum+=90;i++;
}else if(s[i]==map[3]){
sum+=50;
}else if(s[i]==map[4]&&s[i+1]!=map[5]&&s[i+1]!=map[6]){
sum+=100;
}else if(s[i]==map[4]&&s[i+1]==map[5]){
sum+=400;i++;
}else if(s[i]==map[4]&&s[i+1]==map[6]){
sum+=900;i++;
}else if(s[i]==map[5]){
sum+=500;
}else if(s[i]==map[6]){
sum+=1000;
}
}
return sum;
}
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""
。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
实现思路
先找到最小的字符串,记录下它的长度min,然后依次遍历数组的第0-min个元素,如果有不相同的结束,如果能够正常退出,该最小字符串的长度就是最长的公共前缀
代码实现
char* longestCommonPrefix(char** strs, int strsSize) {
int min=1000;
for(int i=0;i<strsSize;i++){
if(strlen(strs[i])<min)
{
min=strlen(strs[i]);
}
}
char *s=(char *)malloc(sizeof(char)*(min+1));
int flag=0,i;
for(i=0;i<min;i++){
s[i]=strs[0][i];
for(int j=1;j<strsSize;j++){
if(s[i]!=strs[j][i]){
flag++;
}
}
if(flag!=0){
break;
}
}
s[i]='\0';
return s;
}
344. 反转字符串
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s
的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1:
输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]
示例 2:
输入:s = ["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]
实现思路
双指针同时像中间移动
代码实现
void reverseString(char* s, int sSize) {
for(int i=0;i<(sSize/2);i++){
int temp=s[i];
s[i]=s[sSize-1-i];
s[sSize-1-i]=temp;
}
}
541. 反转字符串 II
给定一个字符串 s
和一个整数 k
,从字符串开头算起,每计数至 2k
个字符,就反转这 2k
字符中的前 k
个字符。
- 如果剩余字符少于
k
个,则将剩余字符全部反转。 - 如果剩余字符小于
2k
但大于或等于k
个,则反转前k
个字符,其余字符保持原样。
示例 1:
输入:s = "abcdefg", k = 2
输出:"bacdfeg"
示例 2:
输入:s = "abcd", k = 2
输出:"bacd"
实现思路
这道题如果直接遍历回溯,看起来过程会非常臃肿,我们可以参考上一道题的代码用相同的思想进行简化,如果剩余字符多余k个(即包含多余k小于2k和多余2k)都是前k个反转,如果剩余字符不足k个,将剩余字符串全部反转
代码实现
char* reverseStr(char* s, int k) {
int i;
for(i=0;i<strlen(s);i+=2*k){
//剩余字符少于k个
if((strlen(s)-i)<k){
for(int j=i;j<(i+strlen(s))/2;j++){
char temp=s[j];
s[j]=s[strlen(s)-1-j+i];
s[strlen(s)-1-j+i]=temp;
}
}
//剩余字符多余k个
else{
for(int j=i;j<i+k/2;j++){
char temp=s[j];
s[j]=s[i+k-1-j];
s[i+k-1-j]=temp;
}
}
}
return s;
}
151. 反转字符串中的单词
给你一个字符串 s
,请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s
中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意:输入字符串 s
中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。
示例 1:
输入:
the sky is blue
输出:
blue is sky the
示例 2:
输入:s = " hello world "
输出:"world hello"
解释:反转后的字符串中不能存在前导空格和尾随空格。
示例 3:
输入:s = "a good example"
输出:"example good a"
解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。
思路实现
本题采用逆序读入,遇到空格输出后面的单词,然后每个单词后加入一个空格
代码实现
char* reverseWords(char* s) {
int count=0,index=0,flag=0;
for(int p=0;p<strlen(s);p++){
if(s[p]!=' '){
flag=p;
break;
}
}
char *res = (char*)malloc(sizeof(char)*(strlen(s)+1));
for(int i=strlen(s)-1;i>=0;i--){
count++;
int temp=count;
if(s[i]==' '||i==0){
if(i==0&&s[i]!=' '){
res[index]=s[0];
index++;
}
for(int j=i+1;j<i+count;j++){
res[index]=s[j];
index++;
}
count=0;
}
if(s[i]==' '&&temp>1&&i>flag){
res[index]=' ';
index++;
}
}
res[index] = '\0';
return res;
}