Leetcode刷题记录

目录

1、以下代码结果为？22/7/27

2、判断整数是否是回文  22/7/27

3、罗马数字转整数 22/7/28

---

1、以下代码结果为？22/7/27

2、判断整数是否是回文  22/7/27

---

1、以下代码结果为？22/7/27

public class Test {
    public static void main(String args[]) {
        int x = -5;
        int y = -12;
        System.out.println(y % x);
    }
}

解答：x与y之间运算，当x,y符号相同时取模取余的符号也相同

当x，y符号不相同时，取余取头，取模取尾，取余结果符号与x相同，取模与y相同

Arrays.asList()方法返回的列表是Arrays.ArrayList类型的，并不是java.util.ArrayList；

2、判断整数是否是回文  22/7/27

我的方案：

 public static boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            sb.append(chars[i]);
        }

        if (sb.reverse().toString().equals(s)){
            return true;
        }
        return false;
    }

存在的问题：内存消耗过大，代码过于复杂化，当数字过大时会引起溢出。

解决方案：

/**
     * 不需要将整数全部反转再判断，可以取一般进行比较，取整数的后面几位与前面几位比较
     */
    public static boolean isPalindrome(int x) {

        //先将结果一定不是回文的列举
        /**
         * 小于0带符号不是回文
         * 末尾是0的非0整数
         */
        if (x < 0 || (x % 10 == 0 && x != 0)){
            return false;
        }
        //后面尾数
        int revertedNmuber = 0;
        //当x小于等于revertedNmuber时说明提取的尾数已过半，只需要比较一半
        while ( x > revertedNmuber){
            //x%10就是取最后一位数，第一次循环取最后一个数，第二次循环就是取前一个尾数乘以10再加上当前的尾数
            revertedNmuber = revertedNmuber * 10 + x % 10;
            x /= 10;
        }
        //如果x=revertedNmuber 则说明前后相等是回文
        //如果x=revertedNmuber/10 说明除去中间一位数其他位数都相等121 1=21/10 则为回文
        return x == revertedNmuber || x == revertedNmuber/10;
    }

总结： 求回文数的一般思维就是将数字全部逆序然后判断逆序后的数字字符串与原数字字符串比较，这样虽然易懂，但是方法更加繁琐，浪费时间和空间不值当，而通过改进方法，只提取整数一半字符串的值进行比较，12321，只取12  和尾数 12进行比较，节约了空间，提高系统性能。

3、罗马数字转整数 22/7/28

主要思想：将符号与对应数值存放在Map集合中，对输入的字符串进行遍历，如果左边的字符比右边的小就对两者对减法运算，如果左边大于右边做加法运算，

例如 XIV 可视作 X−I+V=10−1+5=14

    public static int romanToInt(String s) {
        //s = I 1， V 5 ， X 10， L 50，C 100，D 500, M 1000。
        Map<Character,Integer> sLists = new HashMap<>();
        sLists.put('I',1);
        sLists.put('V',5);
        sLists.put('X',10);
        sLists.put('L',50);
        sLists.put('C',100);
        sLists.put('D',500);
        sLists.put('M',1000);

        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            //获取当前字符串对应的值
            int value = sLists.get(s.charAt(i));
            //这里做小于的判断是为了防止i+1溢出，当i=s.length() - 1说明到最后一个元素，不能再+1操作
            if (i < s.length() - 1 && value < sLists.get(s.charAt(i + 1)))
                sum -= value;
            else {
                sum += value;
            }
        }
        return sum;
    }
}

总结：防止循环溢出可以与最后一个元素做判断，小于最后一个元素就继续执行。