LeetCode 题解 —— 简单题篇（2）

9. 回文数

• 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
  • 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

解题思路

借鉴第七题 7. 整数反转思想，取反后比较两数是否相同

代码

class Solution {
    public boolean isPalindrome(int x) {
        int temp = x;
        int sum = 0;
        while(temp > 0) {
            sum = sum * 10 + temp % 10;
            temp /= 10;
        }
        
        return sum == x ? true : false; 
    }
}

13. 罗马数字转整数

• 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

解题思路

• 一开始想法很复杂，考虑前后位置上的减法

• 后来借鉴思路是抓核心问题，对于第一个字符对应的数值，依次向后找，遇到比它还大的则减去，否则累加和。最后再处理最后一位上的加和，得到结果。

• 值得多斟酌，单个 for 循环，算法复杂度为 O (n)

代码

class Solution {
    public int romanToInt(String s) {
        int sum = 0;
        int num_former = transform(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            int num_latter = transform(s.charAt(i));
            if(num_former < num_latter)
                sum -= num_former;
            else
                sum += num_former;
            num_former = num_latter;
        }
        return sum+num_former;
    }
    
    private int transform(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;
        }
    }
}