LeetCode之Math题目汇总

LeetCode

我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode

---

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

---

文章目录：

---

Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

---

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode p1 = l1;
        ListNode p2 = l2;
        int carry = 0;
        ListNode head = new ListNode(0);
        ListNode result = head;
        while (carry != 0 || p1 != null || p2 != null) {
            int v1 = 0;
            if (p1 != null) {
                v1 = p1.val;
                p1 = p1.next;
            }
            int v2 = 0;
            if (p2 != null) {
                v2 = p2.val;
                p2 = p2.next;
            }
            int tmp = v1 + v2 + carry;
            carry = tmp / 10;
            head.next = new ListNode(tmp % 10);
            head = head.next;
        }
        return result.next;
    }

---

Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?
2. What are all the possible results?
3. How do they occur, periodically or randomly?
4. You may find this Wikipedia article useful.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

---

$$dr(n) = n−9⌊n−19⌋$$

    public int addDigits(int num) {
        return 1 + (num - 1) % 9;
    }

---

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

---

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode p1 = l1;
        ListNode p2 = l2;
        int carry = 0;
        ListNode head = new ListNode(0);
        ListNode result = head;
        while (carry != 0 || p1 != null || p2 != null) {
            int v1 = 0;
            if (p1 != null) {
                v1 = p1.val;
                p1 = p1.next;
            }
            int v2 = 0;
            if (p2 != null) {
                v2 = p2.val;
                p2 = p2.next;
            }
            int tmp = v1 + v2 + carry;
            carry = tmp / 10;
            head.next = new ListNode(tmp % 10);
            head = head.next;
        }
        return result.next;
    }

---

Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

---

题目中只有+ - ( )。遍历字符串，对于每个字符c：

1. 如果是数字，则一直遍历到非数字字符，把数字找出，并与结果相加
2. 如果是+-符号，将sign设置成对应的值
3. 如果是(，将rt和sign压入栈中，重置rt和sign
4. 如果是)，将sign和rt弹出栈，并计算结果

    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<Integer>();
        int sign = 1;// 符号位，1表示+，-1表示-
        int rt = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int val = c - '0';
                // 将数字取出
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    val = val * 10 + s.charAt(++i) - '0';
                }
                rt += sign * val;
            } else if (c == '-') {
                sign = -1;
            } else if (c == '+') {
                sign = 1;
            } else if (c == '(') {
                // 按照数字、符号的顺序，压入栈
                stack.push(rt);
                stack.push(sign);
                rt = 0;
                sign = 1;
            } else if (c == ')') {
                rt = rt * stack.pop() + stack.pop();
                sign = 1;
            }
        }
        return rt;
    }

---

Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

---

分两次遍历，第一次遍历时，遇到乘除符号就计算；第二次遍历，计算加减符号。

    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int val = c - '0';
                // 将数字取出
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    val = val * 10 + s.charAt(++i) - '0';
                }
                // 栈顶是 * / 运算符，计算
                if (!stack.isEmpty()
                        && (stack.peek() == 2 || stack.peek() == 3)) {
                    int sign = stack.pop();
                    int op = stack.pop();
                    int rt = 0;
                    if (sign == 2) {
                        rt = op * val;
                    } else {
                        rt = op / val;
                    }
                    stack.push(rt);
                } else {
                    stack.push(val);
                }
            } else if (c == ' ') {
                continue;
            } else {
                switch (c) {
                case '+':
                    stack.push(0);
                    break;
                case '-':
                    stack.push(1);
                    break;
                case '*':
                    stack.push(2);
                    break;
                case '/':
                    stack.push(3);
                    break;
                }
            }
        }
        if (stack.isEmpty()) {
            return 0;
        }
        // 因为要从左向右计算，所以要reverse
        Collections.reverse(stack);
        // 计算+-
        int rt = stack.pop();
        while (!stack.isEmpty()) {
            int sign = stack.pop();
            int op = stack.pop();
            if (sign == 0) {
                rt += op;
            } else {
                rt -= op;
            }
        }
        return rt;
    }

---

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

---

    public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return Integer.MAX_VALUE;
        }
        int result = 0;
        if (dividend == Integer.MIN_VALUE) {
            result = 1;
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
            dividend += Math.abs(divisor);
        }
        if (divisor == Integer.MIN_VALUE) {
            return result;
        }
        boolean isNeg = ((dividend ^ divisor) >>> 31 == 1) ? true : false;
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        int c = 0;
        while (divisor <= (dividend >> 1)) {
            divisor <<= 1;
            c++;
        }
        while (c >= 0) {
            if (dividend >= divisor) {
                dividend -= divisor;
                result += 1 << c;
            }
            divisor >>= 1;
            c--;
        }
        System.out.println(result);
        return isNeg ? -result : result;
    }

---

Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

---

二十六进制

    public int titleToNumber(String s) {
        int n = 0;
        int p = 1;
        for (int i = s.length() - 1; i >= 0; i--) {
            n += (s.charAt(i) - 'A' + 1) * p;
            p *= 26;
        }
        return n;
    }

---

Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases.

---

    public String convertToTitle(int n) {
        if (n < 27) {
            return (char) ('A' + (n - 1)) + "";
        }
        if (n % 26 == 0) {
            return convertToTitle(n / 26 - 1) + 'Z';
        }
        return convertToTitle(n / 26) + convertToTitle(n % 26);
    }

---

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

**Note: **Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

---

结果转换成3进制，结尾有多少个连续的0？

在面试时，曾遇到这样的一道题：

30!结果转换成3进制，结尾有多少个连续的0？

第一次做的话，感觉没有思路，但是换个角度想，转换成3进制，那么十进制中的1~30，哪些因子相乘，才会贡献出三进制结尾的0呢？当然是：3的倍数。

3， 6， 9， 12， 15 ，18， 21， 24， 27， 30

---

那么，每一个因子贡献了多少个0呢？

贡献了1个0的因子

3 = 3 * 1
6 = 3 * 2
12 = 3 * 4
15 = 3 * 5
21 = 3 * 7
24 = 3 * 8
30 = 3 * 10

贡献了2个0的因子

9 = 3 * 3
18 = 3 * 3 * 2

贡献了3个0的因子

27 = 3 * 3 * 3

30/3+30/9+30/27所代表的，就是最终结果。

这是因为：30/3把所有贡献了0的因子都算了一次，9、18、27已经被算过一次了，但是9和18还有一个因子没有算，27中还有两个因子没有算。

30/9则计算了一次9、18、27，但是27中还有一个因子没有算。

30/27计算了一次27，至此，所有的因子都计算完毕。

答案就是 30/3+30/9+30/27=10+3+1=14

---

分析本题

n!中，结尾有多少个连续的0

不能像上题一样，直接除以10……因为10可以拆分成两个因子，2和5。但是也不能除以2，因为在任何情况下，2的个数都会多余5的个数，所以，最终除以5就好啦！

100！中，结尾有多少个连续的0？
100/5 + 100/25 + 100/125 = 20 + 4 + 0 = 24

---

计算公式

发挥我少的可怜的数学功底，写一个计算公式/(ㄒoㄒ)/~~

$$n!尾部连续0的个数=\sum_{i=1}^{log_5(n)} [{n \over 5^i}]$$

在代码中，一定要注意溢出的问题，如下代码（我的第一个代码）就不能通过测试。因为在n很大时，比如Integer.MAX_VALUE，i *= 5溢出了，i一直是小于等于n，所以是死循环！

    public static int trailingZeroes2(int n) {
        int rt = 0;
        for (int i = 5; i <= n; i *= 5) {
            rt += n / i;
        }
        return rt;
    }

解决方法，把n定义成long型。注意i也要定义成long型，否则在n很大时，主要是i * 5 > Integer.MAX_VALUE后会出错。

    public int trailingZeroes(int n) {
        int rt = 0;
        long N = n;
        for (long i = 5; i <= N; i *= 5) {
            rt += N / i;
        }
        return rt;
    }

---

Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

Credits:
Special thanks to @Shangrila for adding this problem and creating all test cases.

---

1. 首先判断符号，使用Math.signum()。如果是正数，返回1；负数，返回-1；是0，返回0。

   Returns the signum function of the argument; zero if the argument is zero, 1.0f if the argument is greater than zero, -1.0f if the argument is less than zero.

2. 考虑到溢出，辅助变量定义成long。这是因为如果：

   numerator = Integer.MAX_VALUE; 
   denominator = Integer.MAX_VALUE - 1;

   那么在numerator * 10 后，就溢出了。

3. 要取绝对值，因为 -2 % 3 = -2， -2 % -3 = -2

4. 分析57，余数分别是 5 1 3 2 6 4 5，到5处就出现了循环。因为余数必然在[0,7)范围内，如果不能除尽，必然是无限循环小数。循环的位置，就是某余数第一次出现的位置，至当前该余数出现的位置（该余数是所有余数中，第一个出现2次的）。

         ·         ·
       0.7 1 4 2 8 5
       - - - - - - - 
   7 ）5 0
       4 9
       - - - - - - - 
         1 0       
           7       
           - - - - -
           3 0     
           2 8     
           - - - - -
             2 0   
             1 4   
             - - - -
               6 0 
               5 6 
               - - -
                 4 0
                 3 5
                 - -
                   5

   如上图所示（希望没画错）。在程序中，就是用Map来表示，key是n/10，也就是整数部分除完后，剩下的余数。余数肯定比被除数小；value是key出现的位置。

   map中key和value出现的顺序：

   key     value
    5        0
    1        1
    3        2
    2        3
    6        4
    4        5

   下一个n/10是5，map中存在，即可在0处插入“(”，在最后插入“)”。

    public String fractionToDecimal(int numerator, int denominator) {
        String sign = "";
        if (Math.signum(numerator) * Math.signum(denominator) < 0) {
            sign = "-";
        }
        long n = Math.abs(numerator);
        long d = Math.abs(denominator);
        String intPart = Math.abs(n / d) + "";
        // 如果整除，直接返回结果
        if (n % d == 0) {
            return sign + intPart;
        }
        // 计算小数部分
        n %= d;
        n *= 10;
        StringBuilder sb = new StringBuilder();
        Map<Long, Integer> mod = new HashMap<Long, Integer>();
        for (int i = 0; n != 0; i++) {
            long q = n / d;
            Integer start = mod.get(n / 10);
            if (start != null) {
                sb.insert(start, "(");
                sb.append(")");
                break;
            }
            sb.append(Math.abs(q));
            mod.put(n / 10, i);
            n %= d;
            n *= 10;
        }
        String fractionalPart = sb.toString();
        return sign + intPart + "." + fractionalPart;
    }

---

Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

---

罗马数字的计数方法

基本字符	I	V	X	L	C	D	M
阿拉伯数字表示	1	5	10	50	100	500	1000

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
3. 小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
4. 正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）；
5. 在一个数的上面画一条横线，表示这个数扩大1000倍。

    public String intToRoman(int num) {
        final int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5,
                4, 1 };
        final String[] symbol = { "M", "CM", "D", "CD", "C", "XC", "L", "XL",
                "X", "IX", "V", "IV", "I" };
        StringBuilder result = new StringBuilder();
        for (int i = 0; num > 0; i++) {
            int count = num / values[i];
            num %= values[i];
            for (; count > 0; count--) {
                result.append(symbol[i]);
            }
        }
        return new String(result);
    }

---

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

---

    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null) {
            return "";
        }
        int[] paper = new int[num1.length() + num2.length()];
        char[] _num1 = num1.toCharArray();
        char[] _num2 = num2.toCharArray();
        for (int i = 0; i < _num1.length; i++) {
            for (int j = 0; j < _num2.length; j++) {
                paper[paper.length - (i + j + 2)] += (_num1[i] - '0')
                        * (_num2[j] - '0');
            }
        }
        // add
        for (int i = 0; i < paper.length - 1; i++) {
            paper[i + 1] += paper[i] / 10;
            paper[i] %= 10;
        }
        String s = "";
        for (int i = paper.length - 1; i > 0; i--) {
            if ("" == s && paper[i] == 0) {
                continue;
            }
            s += paper[i];
        }
        s += paper[0];
        return s;
    }
    // can't be accepted in leetcode
    public String multiply2(String num1, String num2) {
        if (num1 == null || num2 == null) {
            return "";
        }
        BigInteger n1 = new BigInteger(num1);
        BigInteger n2 = new BigInteger(num2);
        return n1.multiply(n2).toString();
    }

---

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

1. Beware of overflow.

---

参考：http://blog.csdn.net/xudli/article/details/46798619

    public int countDigitOne(int n) {
        int ones = 0;
        for (long m = 1; m <= n; m *= 10) {
            long a = n / m, b = n % m;
            ones += (a + 8) / 10 * m;
            if (a % 10 == 1)
                ones += b + 1;
        }
        return ones;
    }

---

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

---

    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        if (x >= 0 && x < 10) {
            return true;
        }
        int d = 1;
        while (x / d >= 10) {
            d *= 10;
        }
        while (x != 0) {
            if (x % 10 != x / d) {
                return false;
            }
            x = x % d / 10;
            d /= 100;
        }
        return true;
    }

---

Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

---

动态规划，求解最优化问题，自底向上。

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 将所有平方数置1
        for (int i = 0; i * i <= n; i++) {
            dp[i * i] = 1;
        }
        for (int a = 1; a <= n; a++) {
            for (int b = 1; a + b * b <= n; b++) {
                // 取较小值，a + b * b也可能是平方数
                dp[a + b * b] = Math.min(dp[a] + 1, dp[a + b * b]);
            }
        }
        return dp[n];
    }

---

Permutation Sequence

The set [1,2,3,…,_n_] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

---

首先想到的是递归，按照顺序寻找字符串，然后计数，计算到第k个就是所求字符串。但是这样太慢，在n=9，k很大时会超时。

然后根据规律来，我们发现当n=3时排列是3! = 6组，其中以“1”，“2”，“3”开头的分别有2组。

以“1”开头的排列中，第2位是“2”、“3”的分别有1组。

如果n=4呢？会发现以1开头的排列有6组，其中以2为第2位的排列有2组。

总结规律：第一位数字在数组中的序号肯定是：

k1/(n−1)!

k1=k

第二位数字在剩余数组中的序号肯定是：

k2/(n−2)!

k2=k1

    public String getPermutation(int n, int k) {
        if (n <= 0 || k <= 0) {
            return "";
        }
        String result = "";
        List<Integer> list = new ArrayList<Integer>();
        int fact = 1;
        for (int i = 1; i <= n; i++) {
            list.add(i);
            fact *= i;
        }
        k--;
        for (int i = 0; i < n; i++) {
            fact /= (n - i);
            int index = k / fact;
            result += list.get(index);
            list.remove(index);
            k %= fact;
        }
        return result;
    }

---

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

---

    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0) {
            return null;
        }
        int[] rt = new int[digits.length + 1];
        digits[digits.length - 1]++;
        for (int i = digits.length - 1; i >= 0; i--) {
            rt[i + 1] += digits[i];
            rt[i] += rt[i + 1] / 10;
            rt[i + 1] %= 10;
        }
        if (rt[0] == 0) {
            return Arrays.copyOfRange(rt, 1, rt.length);
        } else {
            return rt;
        }
    }

---

Power of Two

Given an integer, write a function to determine if it is a power of two.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

---

    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        return (n & (n - 1)) == 0;
    }

---

Pow(x, n)

Implement pow(x, n).

---

    public double myPow(double x, int n) {
        if (n < 0) {
            return 1 / pow(x, -n);
        } else {
            return pow(x, n);
        }
    }
    private double pow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double v = pow(x, n / 2);
        if (n % 2 == 0) {
            return v * v;
        } else {
            return v * v * x;
        }
    }
}

---

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Assume that the total area is never beyond the maximum possible value of int.

Credits:
Special thanks to @mithmatt for adding this problem, creating the above image and all test cases.

---

题目要求的是两个矩形总的面积，不是相交的面积……

1. 不考虑两个矩形相交，分别求出每个矩形的面积，相加
2. 如果两个矩形不相交，直接返回结果
3. 如果两个矩形相交，减去相交部分面积

    public int computeArea(int A, int B, int C, int D, int E, int F, int G,
            int H) {
        int area = (C - A) * (D - B) + (G - E) * (H - F);
        if (A >= G || B >= H || C <= E || D <= F) {
            return area;
        }
        int top = Math.min(D, H);
        int bottom = Math.max(B, F);
        int left = Math.max(A, E);
        int right = Math.min(C, G);
        return area - (top - bottom) * (right - left);
    }

---

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Update (2014-11-10):
Test cases had been added to test the overflow behavior.

---

    public int reverse(int x) {
        if (x == Integer.MIN_VALUE) {
            return 0;
        }
        if (x < 0) {
            return -reverse(-x);
        }
        int rt = 0;
        do {
            // y * 10 + x % 10 > Integer.MAX_VALUE
            if (rt > (Integer.MAX_VALUE - x % 10) / 10) {
                return 0;
            }
            rt = rt * 10 + x % 10;
            x = x / 10;
        } while (x > 0);
        return rt;
    }

---

Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

---

罗马数字的计数方法

基本字符	I	V	X	L	C	D	M
阿拉伯数字表示	1	5	10	50	100	500	1000

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
3. 小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
4. 正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）；
5. 在一个数的上面画一条横线，表示这个数扩大1000倍。

    public String intToRoman(int num) {
        final int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5,
                4, 1 };
        final String[] symbol = { "M", "CM", "D", "CD", "C", "XC", "L", "XL",
                "X", "IX", "V", "IV", "I" };
        StringBuilder result = new StringBuilder();
        for (int i = 0; num > 0; i++) {
            int count = num / values[i];
            num %= values[i];
            for (; count > 0; count--) {
                result.append(symbol[i]);
            }
        }
        return new String(result);
    }

---

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

---

    public int mySqrt(int x) {
        // 首先对负数和0进行处理
        if (x < 0) {
            return -1;
        } else if (x == 0) {
            return 0;
        }
        int start = 1;
        int end = x;
        while (start < end) {
            // 不能直接相加除以2，因为两个数相加可能溢出
            int m = start + (end - start) / 2;
            // 不能用m^2，(m+1)^2，因为可能溢出
            int m1 = x / m;
            int m2 = x / (m + 1);
            // m*2 == x
            if (m == m1) {
                return m;
            }
            // (m+1)^2 == x
            if (m + 1 == m2) {
                return m + 1;
            }
            // m*2 <= x && (m+1)^2 > x
            if (m < m1 && m + 1 > m2) {
                return m;
            }
            // m*2 > x
            if (m1 < m) {
                end = m;
            } else {
                // (m+1)^2 < x
                start = m + 1;
            }
        }
        return 1;
    }

---

String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button  to reset your code definition.

spoilers alert... click to show requirements for atoi.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

---

1. 无效的格式，如：”+-1234”, “+-c1234”；
2. 有效的格式，如：”-123c4”, “+1234”；
3. 数据溢出，如：”2147483648”；
4. 注意字符串首尾的空格。

    public int myAtoi(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] c = str.toCharArray();
        int i = 0, flag = 1, rt = 0;
        for (; i < c.length; i++) {
            if (c[i] == ' ') {
                continue;
            } else {
                break;
            }
        }
        if (c[i] == '+') {
            i++;
        } else if (c[i] == '-') {
            flag = -1;
            i++;
        }
        for (; i < c.length; i++) {
            if (c[i] > '9' || c[i] < '0') {
                break;
            }
            if (rt > Integer.MAX_VALUE / 10
                    || (rt == Integer.MAX_VALUE / 10 && (c[i] - '0') > Integer.MAX_VALUE % 10)) {
                return (flag == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            rt = rt * 10 + c[i] - '0';
        }
        return rt * flag;
    }

---

Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

---

    public boolean isUgly(int num) {
        if (num < 1) {
            return false;
        }
        while (num != 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else if (num % 3 == 0) {
                num /= 3;
            } else if (num % 5 == 0) {
                num /= 5;
            } else {
                return false;
            }
        }
        return true;
    }

---

Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

1. The naive approach is to call isUgly for every number until you reach the n^th one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L₁, L₂, and L₃.
4. Assume you have U_k, the k^th ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

---

维持一个数组，依次存入丑数序列。

    public int nthUglyNumber(int n) {
        int[] nums = new int[n];
        nums[0] = 1;
        int i = 0, j = 0, k = 0, t = 1;
        while (t < n) {
            int min = Math.min(Math.min(nums[i] * 2, nums[j] * 3), nums[k] * 5);
            nums[t++] = min;
            if (nums[i] * 2 == min) {
                i++;
            }
            if (nums[j] * 3 == min) {
                j++;
            }
            if (nums[k] * 5 == min) {
                k++;
            }
        }
        return nums[n - 1];
    }

---

Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button  to reset your code definition.

---

    public boolean isNumber(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        char[] chars = s.toCharArray();
        int start = 0, end = chars.length - 1;
        // 除去前后的空格
        while ((start < end) && chars[start] == ' ') {
            start++;
        }
        while ((start < end) && chars[end] == ' ') {
            end--;
        }
        // 因为while的循环条件是start < end，s为空格时，会剩下一个空格
        if (chars[start] == ' ') {
            return false;
        }
        boolean dot = false;
        boolean num = false;
        boolean ex = false;
        for (int i = start; i <= end; i++) {
            char c = chars[i];
            if (c >= '0' && c <= '9') {
                num = true;
            } else if (c == 'e') {
                if (ex)
                    return false;
                if (!num)
                    return false;
                ex = true;
                num = false;
                dot = false;
            } else if (c == '.') {
                if (dot) {
                    return false;
                }
                if (ex) {
                    return false;
                }
                dot = true;
            } else if (c == '+' || c == '-') {
                if (num || dot) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return num;
    }