Tips

整数和 SUM(1,n)= n+ n-1 + n-2 ... 1;

SUM(1,n) = n (n+1) /2 SUM(m,n) = SUM(1,n) - SUM(1, m-1) = n(n+1)/2 - m*(m-1)/2

排序和组合

P(n, r) 从n个物品中取r 个物品的排序 , 排列可以是先取组合，然后进行一次r的全排列。

P(n, r) = C(n,r) * r! =n*(n-1)...(n-r+1) = n! /(n-r)!

C(n,r) 从n个物品中取r 个物品的组合

C(n, r) = P(n, r) / r! = n! / (n-r)! * r!

C(n, r) = C(n, n-r);

http://chowkafat.net/Enumeration2.html

数组反序

public void reverse(int[] nums, int l, int h){
    while(l<h){
        swap(nums, l++, h--);
    }
}

字符串反序

public void reverse(char[] s, int i, int j){
    while(i<j){
        char temp = s[i];
        s[i]=s[j];
        s[j]=temp;
        i++;
        j--;
    }
}
等同于
StringBuffer(str).reverse();

整数反序

public int reverse(int x) {
    if(x == 0)
        return x;
    long rev = 0;
    while(x != 0){
        rev = rev * 10 + x % 10;
        x = x / 10;
         if( rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE)
            return 0;
    }
    return (int)rev;
}

构造回文 Palindrome

public long createPalindrome(int num){
    String value = num + new StringBuilder(Long.toString(num)).reverse().toString();
    return Long.parseLong(value);
}

判断回文1

// right = left or right = left + 1
private void extendPalindrome(String s, int left, int right) {
    // 判断左右扩展的字符是不是回文
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    if (maxLen < right - left - 1) {
        lo = left + 1;
        maxLen = right - left - 1;
    }
}

判断回文2

private boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) return false;
    int lo = 0, hi = s.length() - 1;
    while (lo < hi) {
        if (s.charAt(lo) != s.charAt(hi)) return false;
        lo++;
        hi--;
    }
    return true;
}