Integers & Numbers

Roman to Integer

two things that need to consider

• how to initialize the map efficiently
  • look at the Java 8 features, how to initialize map in a smart way
• how to deal with "IV" , "IX" ...
  • will attempt to parse the two characters as a whole, and then parse the single character.

class Solution {
    public int romanToInt(String s) {
        Map<String, Integer> map = mapInit();

        int sum = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (i + 1 < s.length() && map.containsKey(s.substring(i, i + 2))) {
                sum += map.get(s.substring(i, i + 2));
                i++;
                continue;
            } 

            sum += map.get(String.valueOf(s.charAt(i)));
        }

        return sum;
    }

    private static Map<String, Integer> mapInit() {

        return Collections.unmodifiableMap(new HashMap<String, Integer>(){
            {
                put("I", 1);
                put("V", 5);
                put("X", 10);
                put("L", 50);
                put("C", 100);
                put("D", 500);
                put("M", 1000);
                put("IV", 4);
                put("IX", 9);
                put("XL", 40);
                put("XC", 90);
                put("CD", 400);
                put("CM", 900);
            }
        });
    }
}

String to Integer(atoi)

a lot of things that need to notice.

• it's better to use trim() to remove leading and trailing zeros.
• should deal with first char in advance.
• when we get a middle value, we should compare it with Integer.MAX_VALUE and Integer.MIN_VALUE.

class Solution {
    public int myAtoi(String str) {
        if (str == null || str.length() == 0) return 0;

        str = str.trim();
        char firstChar = str.toCharArray().length > 0 ? str.charAt(0) : ' ';

        int sign = 1, start = 0, len = str.length();
        long sum = 0;
        if (firstChar == '+') {
            sign = 1;
            start++;
        }else if (firstChar == '-') {
            sign = -1;
            start++;
        }

        for (int i = start; i < len; ++i) {
            if (!Character.isDigit(str.charAt(i))) {
                return (int)(sign * sum);
            }
            sum = sum * 10 + str.charAt(i) - '0';
            if (sign == 1 && sum > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            } else if (sign == -1 && (-1) * sum < Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
        }
        return (int)(sign * sum);
    }
}

Reverse Integers

Note that, the modulo operator with negative numbers is a little bit tricky.

So for this problem, we don't need to care about the sign of the number.

class Solution {
    public int reverse(int x) {
        long answer = 0;
        while (x != 0) {
            answer = 10 * answer + x % 10;
            x /= 10;
        }
        return (answer > Integer.MAX_VALUE || answer < Integer.MIN_VALUE) ? 0 : (int)answer;
    }
}

Largest Integers

the key is how to sort the string value: here we can give a smart way: Assume that (without loss of generality), for some pair of integers a and b, our comparator dictates that a should precede b in sorted order. This means that a || b > b || a (where || represents concatenation). For the sort to produce an incorrect ordering, there must be some c for which b precedes c and c precedes a. This is a contradiction because a||b>b||a and b||c>c||b implies a||c>c||a. In other words, our custom comparator preserves transitivity, so the sort is correct.

Once the array is sorted, the most "signficant" number will be at the front. There is a minor edge case that comes up when the array consists of only zeroes, so if the most significant number is 0, we can simply return 0. Otherwise, we build a string out of the sorted array and return it.

class Solution {
    public String largestNumber(int[] nums) {
        // get input integers as Strings
        String[] asStrs = new String[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            asStrs[i] = String.valueOf(nums[i]);
        }

        // sort strings accordings to the custom comparactor
        Arrays.sort(asStrs, new LargerNumberComparator());

        if (asStrs[0].equals("0")) {
            return "0";
        }

        // build largest number from sorted array
        StringBuilder sb = new StringBuilder();
        for (String numAsStr : asStrs) {
            sb.append(numAsStr);
        }
        return sb.toString();
    }

    private class LargerNumberComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            String order1 = a + b;
            String order2 = b + a;

            return order2.compareTo(order1);    // reverse order, b + a is larger than a + b...
        }
    }
}

PlusOne

most convenient way to solve the problem is to process the original array directly.

class Solution {
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0){
            return new int[0];
        }

        int leading = 1;
        for (int i = digits.length - 1; i >= 0; i--){
            int val = digits[i] + leading;
            digits[i] = val % 10;
            leading = val == 10 ? 1 : 0;
        }

        if (leading == 0){
            return digits;
        }

        int[] res = new int[digits.length + 1];
        res[0] = 1;
        for (int i = 0; i < digits.length; i++){
            res[i + 1] = digits[i];
        }

        return res;
    }
}