Integer

• int 32 bits integer
  • Maximum: 2147483647
  • Minimum: -2147483648
  • Integer.MAX_VALUE + 1 == Integer.MIN_VALUE and Integer.MIN_VALUE - 1 == Integer.MAX_VALUE
  • Math.abs(Integer.MIN_VALUE) == -2147483648
• 除法的特殊情况
  • overflow:
    • Integer.MIN_VALUE / (-1)
    • anything / 0
• tips
  • 当需要进行乘方尤其是2的n次方运算时，可以直接利用左移运算符1<<n
• test case
  • 1431655765, huge number,溢出
    • 处理方法：
  • 当遇到需要进行乘法运算的时候，注意大数会溢出 e.g sqrt(x)
    • 尽可能转化成除法来比较（要排除除数为0的情况）
    • 用long进行定义，最后在返回int
  • 在涉及到乘除法计算问题时候，要考虑除数/乘数是否可能为负数的情况

Palindrome

• 获取最后一位%10

Check if int is Palindrome

同理还可以用于主动构建Palindrome

public static boolean isPalindrome(int integer) {
    int palindrome = integer;
    int reverse = 0;

    // Compute the reverse
    while (palindrome != 0) {
        int remainder = palindrome % 10;
        reverse = reverse * 10 + remainder;
        palindrome = palindrome / 10;
    }

    // The integer is palindrome if integer and reverse are equal
    return integer == reverse; // Improved by Peter Lawrey

}

//or use stringbuilder
public static boolean isPalindrome(int integer) {
    String intStr = String.valueOf(integer); 
    return intStr.equals(new StringBuilder(intStr).reverse().toString());
}

Largest Palindrome Product

• 当回文数很大的时候，
  • 发现输入范围n∈[1, 8]，除n = 1以外于n取1到8的，n值最大回文数palindrome的位数均为偶数，可以拆分为half与reversed(half)左右两半

位移

binary

• 二进制数可以通过每次/2再%2获取每一位的值

计算

Pow(x, n)

• 分情况讨论，注意这里关注的是n，n为整数
  • n == 0
  • n < 0
  • n % 2 == 1
  • n % 2 == 0

//recursive 
double myPow(double x, int n) { 
    if(n==0) return 1;
    if(n<0){
        n = -n;
        x = 1/x;
    }
    return n%2==0 ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
}

Integer to Roman

  int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
    String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

    StringBuilder sb = new StringBuilder();

    for(int i=0;i<values.length;i++) {
        while(num >= values[i]) {
            num -= values[i];
            sb.append(strs[i]);
        }
    }
    return sb.toString();