Map

• 332 重新安排行程
  使用Map统计时写法：

for (int i = 0; i < keys.length; i++) {
    if (!map.containsKey(keys[i]))
        map.put(keys[i], new ArrayList<>());
    map.get(keys[i]).add(values[i]);
}

字符串

• Api of string.h
  strlen: 返回值是unsigned int，注意unsigned int不能直接与负数比较。
  strcpy: char *strcpy(char *dest, const char *src)。
  strcat: extern char *strcat(char *dest, const char *src)，dest不可以是常量池的字符串，必须是实例化后，且长度足够。
• Api of limits.h
  INT_MIN: -2147483648
  INT_MAX: 2147483647
• 344 反转字符串
  不使用额外变量交换数值 II：

a = a+b;
b = a-b;
a = a-b;

• 7 整数反转
  数值越界判断：

while (x != 0) {
    int pop = x % 10;
    x /= 10;
    if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
    if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
    rev = rev * 10 + pop;
}

• 125 验证回文串
  双指针法 II: 设置头尾指针，遇到不合法情况跳过，合法情况下比较。

while (i<j){
    while (('0'>s[i] || s[i]>'9') && ('a'>s[i] || s[i]>'z') && ('A'>s[i] || s[i]>'Z') && i<j)
        i++;
    while (('0'>s[j] || s[j]>'9') && ('a'>s[j] || s[j]>'z') && ('A'>s[j] || s[j]>'Z') && i<j)
        j--;
    if (s[i] != s[j])
        if ( ('0'<=s[i] && s[i]<='9') || !equalIgnoreCast(s[i],s[j]))
            return false;
    i++;
    j--;
}

• 8 字符串转换整数 (atoi)
  计算的位数：
  各位数字构造负数：

rev = rev*10 - pop;

• 28 实现strStr()
  模式匹配常规模板：

while (i<mainLen && j<pLen){
    if (main[i] == p[j]){
      i++;
      j++;
    }else{
        i = i - j;
        j = 0;
    }
}

KMP求next数组： 当p[0...k-1] == p[j-k...j-1]时，next[j] = k。

• 14 最长公共前缀
  分治法：问题规模为1时返回原值，求左右两侧子问题解，取左右子解的LCP。
  二分查找法：取最短字符串作为初始串，取其左部分与全字符串数组比较，若是LCP，则取左；否则取右。直至左指针小于右指针跳出循环。

while (low <= high) {
    int middle = (low + high) / 2;
    if (isCommonPrefix(strs, middle))
        low = middle + 1;
    else
        high = middle - 1;
}
return strs[0].substring(0, (low + high) / 2);