1.最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

子串的种类 O(n^2);
子序列O(n^3);

暴力法：相向型双指针。for 起点 for 重点 {判断是否是回文串} 时间复杂度O（N^3）异常检测要注意，忌讳看到i j k等的命令，最好是完整的单词，合理的缩进~，缩进不要超过三层，合理的封装。
马拉车算法，O（n），但是不是面试官想要实现的算法，原因：写出来了只会证明你是背的。面试官可能也不会~
基于中心线枚举的算法。[优化思路，内层的回文串已经判断了一次，外层的回文串还是要重新判断一次。abcba]。。。奇数长度的回文串中心点有n个，n - 1个偶数长度的回文串的中心。

不能有重复代码！！！工程中尽量避免全局变量。

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int start = 0, len = 0, longest = 0;
        for (int i = 0; i < s.length(); i++) {
            len = findLongestPalindromeFrom(s, i, i);
            if (len > longest) {
                longest = len;
                start = i - len / 2;
            }
            len = findLongestPalindromeFrom(s, i, i + 1);
            if (len > longest) {
                longest = len;
                start = i - len / 2 + 1;
            }
        }
        return s.substring(start, start + longest);
    }
    private int findLongestPalindromeFrom(String s, int left, int right) {
        int len = 0;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            len += left == right ? 1 : 2;
            left--;
            right++;
        }
        return len;
    }
}

动态规划：两头相等+ 中间也是一个回文串。（状态 + 状态转移。）

public class Solution {
 public String longestPalindrome(String s) {
     if (s == null || s.length() == 0) {
         return "";
     }
     int n = s.length();
     boolean[][] isPalindrome = new boolean[n][n];
     int longest = 1, start = 0;
     for (int i = 0; i < n; i++) {
         isPalindrome[i][i] = true;
     }
     for (int i = 0; i < n - 1; i++) {
         isPalindrome[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
         if (isPalindrome[i][i + 1]) {
             start = i;
             longest = 2;
         }
     }
     for (int i = n - 1; i >= 0; i--) {
         for (int j = i + 2; j < n; j++) {
             isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && 
                 s.charAt(i) == s.charAt(j);
             if (isPalindrome[i][j] && j - i + 1 > longest) {
                 start = i;
                 longest = j - i + 1;
             }
         }
     }
     return s.substring(start, start + longest);
 }
}

插播：面试考点

不一定要用最优复杂度的算法来解决问题。
代码真的不是写出来就可以过。代码质量
1. bug free
2. 好的代码风格：变量命名规范，合理的使用空格善用空行。
3. 容易让人读懂的逻辑，复杂的事情简单化。
4. 没有冗余代码
5. 有边界检测和异常处理
优化Coding Quality

2.字符串查找

面试分析
1. kmp这个考点不太好。- substring这个方法好像也不能用,而且会花时间额外创建一个字符串。空间时间浪费。
2. 真问我比n^2 更好的算法？
实际算法

Rabin-karp算法：加速判断字符串是否相等的过程。整数的比较~ ==》字符串变成整数，一一对应关系。也就是哈希函数
abc-bcd怎么变？

加速了hashcode不一样的话，原来的字符串一定不一样的情况。
只有hashcode相同的时候，才会做目标串长度次的比较。

乘以任何一个数都可以，31比较常用。经验值，还可以% 一个数 10^6

public class Solution {
    /**
     * @param source a source string
     * @param target a target string
     * @return an integer as index
     */
    public int strStr2(String source, String target) {
        if(target == null) {
            return -1;
        }
        int m = target.length();
        if(m == 0 && source != null) {
            return 0;
        }
        if(source == null) {
            return -1;
        }
        int n = source.length();
        if(n == 0) {
            return -1;
        }
        // mod could be any big integer
        // just make sure mod * 33 wont exceed max value of int.
        int mod = Integer.MAX_VALUE / 33;
        int hash_target = 0;
        // 33 could be something else like 26 or whatever you want
        for (int i = 0; i < m; ++i) {
            hash_target = (hash_target * 33 + target.charAt(i) - 'a') % mod;
            if (hash_target < 0) {
                hash_target += mod;
            }
        }
        int m33 = 1;
        for (int i = 0; i < m - 1; ++i) {
            m33 = m33 * 33 % mod;
        }
        int value = 0;
        for (int i = 0; i < n; ++i) {
            if (i >= m) { //达到了目标串长度，就删去最左边的。
                value = (value - m33 * (source.charAt(i - m) - 'a')) % mod;
            }
            value = (value * 33 + source.charAt(i) - 'a') % mod;
            if (value < 0) {
                value += mod;
            }
            if (i >= m - 1 && value == hash_target) {
                // 重新计算。hashcode值相等的时候再做一次检查。
                if (target.equals(source.substring(i - m + 1, i + 1))) {
                    return i - m + 1;
                }
            }
        }
        return -1;
    }
}

3. 算法的复杂度理论

时间复杂度-核心考察点
1. 多项式复杂度
  1. 时间复杂度O（n）的算法：双指针，打擂台【枚举法】，单调栈，单调队列
2. 非多项式复杂度
空间复杂度-次要考察点
编程复杂度-能看得懂
思维复杂度-能想得出
4. 双指针的算法
注意O(max(m,n)) = O (m+ n),逼近法。

两边往中间走。

4.1 有效回文串

判断一个字符串忽略大小写和非法字符之后是一个回文串。

public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int front = 0;
        int end = s.length() - 1;
        while (front < end) {
            while (front < s.length() && !isvalid(s.charAt(front))) { // nead to check range of a/b
                front++;
            }
            if (front == s.length()) { // for empty string “.,,,”     
                return true; 
            }           
            while (end >= 0 && ! isvalid(s.charAt(end))) { // same here, need to check border of a,b
                end--;
            }
            if (Character.toLowerCase(s.charAt(front)) != Character.toLowerCase(s.charAt(end))) {
                break;
            } else {
                front++;
                end--;
            }
        }
        return end <= front; 
    }
    private boolean isvalid (char c) {
        return Character.isLetter(c) || Character.isDigit(c);
    }
}

4.2 回文串二

是否可以在去掉一个字符的情况下成为回文串。

4.3 两数之和

相向型双指针。
哈希表 | 排序 + 双指针。

Follow Up 1:

如果输入数据已经排序，哪个算法更好？

Follow Up 2:

如果需要返回所找的两个数在数组中的下标，哪个算法更好？【双指针带着index一起排序，二元组定义一个Pair】

public class Solution {
  class Pair implements Comparable<Pair> {
      int number, index;

      public Pair(int number, int index) {
          this.number = number;
          this.index = index;
      }

      public int compareTo(Pair other) {
          return number - other.number;
      }
  }
  /**
   * @param numbers: An array of Integer
   * @param target: target = numbers[index1] + numbers[index2]
   * @return: [index1, index2] (index1 < index2)
   */
  public int[] twoSum(int[] numbers, int target) {
      int[] result = {-1, -1};

      if (numbers == null) {
          return result;
      }

      Pair[] pairs = getSortedPairs(numbers);

      int left = 0, right = pairs.length - 1;
      while (left < right) {
          if (pairs[left].number + pairs[right].number < target) {
              left++;
          } else if (pairs[left].number + pairs[right].number > target) {
              right--;
          } else {
              result[0] = Math.min(pairs[left].index, pairs[right].index);
              result[1] = Math.max(pairs[left].index, pairs[right].index);
              return result;
          }
      }

      return result;
  }

  private Pair[] getSortedPairs(int[] numbers) {
      Pair[] pairs = new Pair[numbers.length];
      for (int i = 0; i < numbers.length; i++) {
          pairs[i] = new Pair(numbers[i], i);
      }
      Arrays.sort(pairs);

      return pairs;
  }
}

5. 排序

5.1 快速排序

核心思想是分治。左半部分右半部分排起来啊！。

为了避免数组的值全都是一样，然后每次只能分一个有序的，在碰到等于的情况下，也要跳出来。

import java.util.Random;

public class Solution {
    /*
     * @param A: an integer array
     * @return: 
     */
    public Random rand;
    public void sortIntegers2(int[] A) {
        rand = new Random();
        // write your code here
        quickSort(A, 0, A.length - 1);
    }

    public void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }

        int index = rand.nextInt(end - start + 1)  + start;
        int pivot = A[index]; // 标杆数。pivot的选取可以随机化。
        int left = start;
        int right = end;

        while (left <= right) {
            while (left <= right && A[left] < pivot) {
                left ++;
            }
            while (left <= right && A[right] > pivot) {
                right --;
            }

            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;

                left ++;
                right --;
            }
        }
        // A[start... right] 
        quickSort(A, start, right);
        // A[left ... end]
        quickSort(A, left, end);
    }
}

    public int partition(int[] nums,int start,int end) {
        //[start,end+1)
        int randomIndex = (int)(Math.random() * (end + 1 - start)) + start;
        swap(nums,start,randomIndex);
        int pivotNum = nums[start];
        int left = start, right = end;
        while (left < right) {
            while(left < right && nums[right] > pivotNum) {
                right--;
            }
            if (left < right) {
                nums[left] = nums[right];
                left++;
            }
            while(left < right && nums[left] < pivotNum) {
                left++;
            }
            if (left < right) {
                nums[right] = nums[left];
                right--;
            }
        }
        nums[left] = pivotNum;
        return left;
    }

刷题