Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

二分法，但是用除法来检测，避免溢出。

public class Solution {
    //Time: O(logn)  Space: O(1)
    public int sqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        
        int left = 1;
        int right = x;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (x / mid == mid) {
                return mid;
            } else if (x / mid > mid) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (x / right > right) {
            return right;
        } else {
            return left;
        }
    }
}

Pow(x, n)

Implement pow(x, n).

二分法，注意n = 1和0的特殊情况

public class Solution {
    //Time: O(logn)
    public double pow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        
        boolean isNeg = false;
        if (n < 0) {
            n = -n;
            isNeg = true;
        }
        
        double half = pow(x, n / 2);
        if (n % 2 == 0) {
            return isNeg ? 1 / (half * half) : half * half;
        } else {
            return isNeg ? 1 / (half * half * x) : half * half * x;
        }
    }
}

Palindrome Number

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

这种题其实有很多细节不明确，需要和面试官交流，比如如何判断负数。

直观解法是reverse integer，但是会遇到溢出的问题。

可以每次尝试求第一位和最后一位，进行比较。

public class Solution {
    //Time: O(n)
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        
        int bigdiv = 1;
        while (x / bigdiv >= 10) {
            bigdiv *= 10;
        }
        
        while (x > 0) {
            int left = x / bigdiv;
            int right = x % 10;
            if (left != right) {
                return false;
            }
            x = x % bigdiv;
            x = x / 10;
            bigdiv = bigdiv / (100);
        }
        return true;
    }
}

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

螺旋数组，其实就是找出数学规律。

public class Solution {
    //Time: O(n^2)  Space: O(n^2)
    public int[][] generateMatrix(int n) {
        int count = 0;
        int[][] matrix = new int[n][n];
        generate(matrix, n, count, 0);
        return matrix;
    }
    
    private void generate(int[][] matrix, int size, int count, int offset) {
        if (count == matrix.length * matrix.length) {
            return;
        }
        
        for (int i = 0; i < size; i++) {
            matrix[offset][offset + i] = ++count;
        }
        for (int i = 1; i < size; i++) {
            matrix[offset + i][offset + size - 1] = ++count;
        }
        for (int i = size - 2; i >= 0; i--) {
            matrix[offset + size - 1][offset + i] = ++count;
        }
        for (int i = size - 2; i > 0; i--) {
            matrix[offset + i][offset] = ++count;
        } 
        generate(matrix, size - 2, count, offset + 1);
    }
}

Roman to Integer & Integer to Roman

Given a roman numeral, convert it to an integer.

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

规则：

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，例如：III = 3
2. 小的数字在大的数字右边，所表示的数等于这些数字相加得到的数，例如：VIII = 8
3. 小的数字，限于（I、X和C）在大的数字左边，所表示的数等于大数减去小数所得的数，例如：IV = 4
4. 正常使用时，连续的数字重复不得超过三次

public class Solution {
    public int romanToInt(String s) {
        //Time: O(n)  Space: O(n)
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        
        int res = map.get(s.charAt(s.length() - 1));
        for (int i = s.length() - 2; i >= 0; i--) {
            int cur = map.get(s.charAt(i));
            int pre = map.get(s.charAt(i + 1));
            if (cur >= pre) {
                res += cur;
            } else {
                res -= cur;
            }
        }
        return res;
    }
}

Given an integer, convert it to a roman numeral.

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

public class Solution {
    public String intToRoman(int num) {
        int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbol = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int digit = 0;
        StringBuilder res = new StringBuilder();
        while (num > 0) {
            int times = num / nums[digit];
            num -= nums[digit] * times;
            while (times > 0) {
                res.append(symbol[digit]);
                times--;
            }
            digit++;
        }
        return res.toString();
    }
}

Reverse Integer

Reverse digits of an integer.

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

把一个整数reverse，需要考虑两点：1. 判断数的正负  2. 反转是否会溢出。对于第二点，我用long作为函数类型，这样排除了溢出的可能性。

public class Solution {
    //Time: O(num of digits in x)  Space: O(1)
    public long reverse(int x) {
        boolean isNeg = false;
        if (x < 0) {
            x = -x;
            isNeg = true;
        }
        long res = 0;
        while (x > 0) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        if (isNeg) {
            res = -res;
        }
        return res;
    }
}