BasedLeetCode

LeetCode learning records based on Java,Kotlin,Python...Github 地址

序號對應(yīng) LeetCode 中題目序號

9 判斷一個整數(shù)是否是回文數(shù)。不能使用輔助空間

什么是回文數(shù)：“回文”是指正讀反讀都能讀通的句子；如："123321","我為人人，人人為我"等

• Java 語言實現(xiàn)

    public static boolean isPalindrome(int x) {
        if (x < 0) {//負(fù)數(shù)不是回文數(shù)
            return false;
        } else if (x < 10) {
            return true;
        } else {
            int highLength = 1;
            //獲取 x 的最高位數(shù)量級，如 x=123,highLength=100,x=23451,highLength=10000...
            while ((x / highLength) >= 10) {
                highLength = highLength * 10;
            }
            int lowLength = 10;
            //(x / highLength) % 10 取待比較數(shù)的最高位數(shù)
            //(x % lowLength) / (lowLength / 10) 取待比較數(shù)的最低位
            while ((x / highLength) % 10 == (x % lowLength) / (lowLength / 10)) {
                if (highLength < lowLength) {
                    return true;
                }
                //相等時，最高位左移，最低位右移
                lowLength = lowLength * 10;
                highLength = highLength / 10;
                if (highLength < lowLength) {
                    return true;
                }
            }
            return false;
        }
    }

• Kotlin 語言實現(xiàn)

    fun isPalindrome(x: Int): Boolean {
        if (x < 0)
            return false
        if (x < 10)
            return true
        var highLength = 1
        var lowLength = 10
        while (x / highLength >= 10) {
            highLength *= 10
        }

        while (x / highLength % 10 == x % lowLength / (lowLength / 10)) {
            if (highLength < lowLength) return true
            highLength /= 10
            lowLength *= 10
            if (highLength < lowLength) return true
        }
        return false
    }

13 給定一個羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)

• 1.對應(yīng)羅馬——整數(shù)的轉(zhuǎn)換關(guān)系：I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)
• 2.規(guī)則：
  • 2.1：相同的數(shù)字連寫， 所表示的數(shù)等于這些數(shù)字相加得到的數(shù)。如 XXX表示 30；
  • 2.2：小的數(shù)字在大的數(shù)字的右邊， 所表示的數(shù)等于這些數(shù)字相加得到的數(shù) 如VIII 表示8；
  • 2.3：小的數(shù)字(限于I, X, C)在大的數(shù)字的左邊， 所表示的數(shù)等于大數(shù)減去小的數(shù)： 如IV 表示4；
  • 2.4：在一個數(shù)的上面畫一條橫線， 表示這個數(shù)增值1000倍(由于題目只考慮4000以內(nèi)的數(shù)，所以這條規(guī)則不用考慮)；
• 3.組數(shù)規(guī)則：
  • 3.1：I, X, C： 最多只能連用3個， 如果放在大數(shù)的左邊，只能用1個;
  • 3.2:V, L, D: 不能放在大數(shù)的左邊，只能使用一個;
  • 3.3:I 只能用在V和X的左邊。 IV表示4, IX表示9;
  • 3.4:X只能放在L,C左邊。 XL 表示40, XC表示90;
  • 3.5:C只能用在D, M左邊。 CD 表示400, CM表示900

• Java 語言實現(xiàn)

    public int romanToInt(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int sum = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (singleRomanToInt(s.charAt(i)) >= singleRomanToInt(s.charAt(i + 1))) {
                sum += singleRomanToInt(s.charAt(i));
            } else {
                sum -= singleRomanToInt(s.charAt(i));
            }
        }
        sum += singleRomanToInt(s.charAt(s.length() - 1));
        return sum;
    }

    private int singleRomanToInt(char c) {
        switch (c) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }

• Kotlin 語言實現(xiàn)

    fun romanToInt(s: String): Int {
        if (s.isEmpty()) {
            return 0
        }
        var sum = 0
        for (i in 0 until s.lastIndex) {
            if (singleRomanToInt(s[i]) >= singleRomanToInt(s[i + 1]))
                sum += singleRomanToInt(s[i])
            else
                sum -= singleRomanToInt(s[i])
        }
        sum += singleRomanToInt(s[s.lastIndex])
        return sum
    }

    private fun singleRomanToInt(char: Char): Int {
        if ('I' == char) return 1
        if ('V' == char) return 5
        if ('X' == char) return 10
        if ('L' == char) return 50
        if ('C' == char) return 100
        if ('D' == char) return 500
        if ('M' == char) return 1000
        return 0
    }