LeetCode(67) -- 8, 12

P8. String to Integer (atoi) (Medium)

把一个字符串转化成整数。这个字符串可能含有空格，字母，去掉开头的空格后，可以有一个+或-，后面跟数字。

我的思路

把各种可能性考虑全了即可。

我的代码

public class P8_StringtoInteger {
    public int myAtoi(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        str = str.trim();
        if (str.length() == 0 || (!str.startsWith("-") && !str.startsWith("+") && !Character.isDigit(str.charAt(0)))) {
            return 0;
        }
        char[] chars = str.toCharArray();
        boolean negative = false;
        long myInt = 0L;
        for (int i = 0; i < chars.length; i++) {
            if (i == 0 && chars[i] == '-') {
                negative = true;
                continue;
            }
            if (i == 0 && chars[i] == '+') {
                continue;
            }
            if (!Character.isDigit(chars[i]) || myInt > Integer.MAX_VALUE) {
                break;
            }
            int digit = chars[i] - '0';
            myInt = myInt * 10 + digit;
        }
        if (negative) {
            myInt = -myInt;
        }
        if (myInt < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        if (myInt > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        return (int)myInt;
    }
}

55%

最优解

class Solution {
    public int myAtoi(String str) {
        int res = 0;
        int i = 0;
        int sign = 1;
        while(i < str.length() && str.charAt(i) == ' '){
            i++;
        }
        if(i == str.length() || (str.charAt(i) != '-'&& str.charAt(i) != '+' && !Character.isDigit( str.charAt(i)))) return res;
        int j = i;
        if(str.charAt(i) == '+'){
            i++;
            j++;
        }else if(str.charAt(i) == '-'){
            i++;
            j++;
            sign = -1;
        }
        while(j < str.length() && Character.isDigit(str.charAt(j))){
            j++;
        }
        if(j == i) return res;
        while(i < j){
             if(sign* res > Integer.MAX_VALUE/10|| (sign*res == Integer.MAX_VALUE/10 && str.charAt(i) - '0' > 7))
                return Integer.MAX_VALUE;
            if(sign * res < Integer.MIN_VALUE/10|| (sign*res == Integer.MIN_VALUE/10 && str.charAt(i) - '0' > 8))
                return Integer.MIN_VALUE;
            res = res*10 + str.charAt(i) -'0';
            i++;
               }
        return res*sign;
        
    }
}

P12. Integer to Roman (Medium)

把一个整数转化为罗马数字。

我的思路

每一位数字都是独立的，只要把该位数字代表1，5，10的三个字母改变一下，逻辑都是一样的。把每种可能性清楚地表示出来即可。

我的代码

public class P12_IntegertoRoman {
    StringBuilder sb = new StringBuilder();
    public String intToRoman(int num) {
        if (num >= 1000) {
            for (int i = 0; i < num / 1000; i++) {
                sb.append('M');
            }
            num = num % 1000;
        }
        convert (num, 100, 'C', 'D', 'M');
        num %= 100;
        convert (num, 10, 'X', 'L', 'C');
        num %= 10;
        convert (num, 1, 'I', 'V', 'X');
        return sb.toString();
    }

    private void convert (int num, int divisor, char one, char five, char ten) {
        if (num >= divisor) {
            int currentDigit = num / divisor;
            if (currentDigit <= 3) {
                for (int i = 0; i < currentDigit; i++) {
                    sb.append(one);
                }
            } else if (currentDigit == 4 || currentDigit == 9) {
                sb.append(one);
                if (currentDigit == 4) {
                    sb.append(five);
                } else {
                    sb.append(ten);
                }
            } else {
                sb.append(five);
                for (int i = 0; i < currentDigit - 5; i++) {
                    sb.append(one);
                }
            }
        }
    }

    public static void main(String[] args) {
        String s = new P12_IntegertoRoman().intToRoman(1994);
        System.out.println("s = " + s);
    }
}

100%

最优解

class Solution {
    public String intToRoman(int num) {
        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"};
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0 ; i < values.length ; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(strs[i]);
            }
        }
        return sb.toString();
    }
}