《刷题笔记》 力扣 罗马数字转整数 + 最长公共前缀 （一刷）

《刷题笔记》 力扣 罗马数字转整数 + 最长公共前缀 （一刷）

文章目录

• 《刷题笔记》 力扣 罗马数字转整数 + 最长公共前缀 （一刷）
• • 罗马数字转整数
  • • 题目描述：
    • 思路：
    • 代码：
    • 运行截图：
  • 最长公共前缀
  • • 题目描述：
    • 思路：
    • 模拟写法的代码：
    • 运行截图：
    • 二分写法的代码：
    • 运行截图：
    • 总结：

罗马数字转整数 题目描述：

思路：

其实按照题目要求就可以轻松地模拟出来了，值得注意的是，当最后一个字母没有被遍历到时，我们可以认为它是独立存在的，并没有与其他字母组成一个罗马数字。

比较简单的模拟题

代码：

class Solution {

    public int romanToInt(String s) {
        int n = 0;
        int i = 0;
        char s1 = 0;
        char s2 = 0;
        for(i=0;i<s.length()-1;i++){
            s1 = s.charAt(i);
            s2 = s.charAt(i+1);
            if(s1 == 'M'){
                n+=1000;
            }else if(s1 == 'D'){
                n+=500;
            }else if(s1=='C'&&s2!='M'&&s2!='D'){
                n+=100;
            }else if(s1=='C'&&s2=='M'){
                n+=900;
                i++;
            }else if(s1=='C'&&s2=='D'){
                n+=400;
                i++;
            }else if(s1=='L'){
                n+=50;
            }else if(s1=='X'&&s2!='L'&&s2!='C'){
                n+=10;
            }else if(s1=='X'&&s2=='L'){
                n+=40;
                i++;
            }else if(s1=='X'&&s2=='C'){
                n+=90;
                i++;
            }else if(s1=='V'){
                n+=5;
            }else if(s1=='I'&&s2!='V'&&s2!='X'){
                n+=1;
            }else if(s1=='I'&&s2=='V'){
                n+=4;
                i++;
            }else if(s1=='I'&&s2=='X'){
                n+=9;
                i++;
            }
        }
        if(i==s.length()-1){
            s1 = s.charAt(i);
            if(s1=='M'){
                n+=1000;
            }else if(s1 == 'D'){
                n+=500;
            }else if(s1 == 'C'){
                n+=100;
            }else if(s1 == 'L'){
                n+=50;
            }else if(s1 == 'X'){
                n+=10;
            }else if(s1 == 'V'){
                n+=5;
            }else if(s1 == 'I'){
                n+=1;
            }
        }
        return n;
    }
}

运行截图：

最长公共前缀 题目描述：

思路：

这道题其实正常的去模拟就好，用第一个字符串每个字母与后续的字符串的每个字母比较，用个计数变量计数下相同的最小个数即可了。

但是也可以使用二分的思路。

模拟写法的代码：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int min = 200;
        int g = 0;
        StringBuilder sb = new StringBuilder();
        if(strs.length==0){
            return sb.toString();
        }
        for(int i = 0;i<strs.length;i++){
            g = 0;
            int j = 0;
            int m = 0;
            while(j<strs[0].length()&&m<strs[i].length()){
                char s1 = strs[0].charAt(j);
                char s2 = strs[i].charAt(m);
                if(s1==s2){
                    g++;
                }else{
                    break;
                }
                j++;
                m++;
            }
            if(min>g){
                min = g;
            }
        }
        for(int i=0;i<min;i++){
            char s = strs[0].charAt(i);
            sb.append(s);
        }
        return sb.toString();
    }
}

运行截图：

二分写法的代码：

class Solution {
    public Boolean issame(String[] strs,int len){
        String str1 = strs[0].substring(0,len);
        for(int i = 0;i < strs.length;i++){
            for(int j = 0;j < len;j++){
                if(str1.charAt(j)!=strs[i].charAt(j)){
                    return false;
                }
            }
        }
        return true;
    }
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minlen = 200;
        for(int i = 0;i<strs.length;i++){
            int len = strs[i].length();
            if(minlen>len){
                minlen = len;
            }
        }
        int low = 0;
        int hight = minlen;
        while(low < hight){
            int mid = (hight - low + 1) / 2 + low;
            if(issame(strs,mid)){
                low = mid;
            }else{
                hight = mid-1;
            }
        }
        return strs[0].substring(0,low);
    }
}

运行截图：

总结：

二分判断字符串的做法是需要学习的，模拟的速度不够快，还得多加练习