记住大概的方法就行了

1.无重复字符的最短字串（滑动窗口）

原题：给定一个字符串，找出不含有重复字符的最长字串（字串是连续的）。

滑动窗口：主要思想是随着左边窗口的移动，右边窗口也一定会向右边移动。每一次循环找的都是以charAt(i)开头的最长字串。由于i在增加，在每次移动的同时保存最长字串的长度就是结果。

判断是否重复：当右指针遍历到hashset含有的元素就停止右移。为了保证i移动的同时，后续字符都是以i这个元素开头的，当前循环结束以后需要把charAt(i)从hashset剔除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int lengthOfLongestSubstring(String s) {
    //检查重复性
    HashSet<Character> hashSet = new HashSet<>();
    int max = 0;
    //p是最右边的指针
    int p = 0;
    for (int i = 0; i < s.length(); i++) {
        //p一直向右边移动，直到碰到set里面有的元素，就进行下一次大循环
        while (p < s.length()){
            if (!hashSet.contains(s.charAt(p))){
                hashSet.add(s.charAt(p));
                p++;
            }
            else {
                break;
            }
        }
        //留一个max来返回最大值
        max = Math.max(max,hashSet.size());
        //在下一次大循环前保证set只有当前元素以后的，所以要把上一个元素从set删除
        hashSet.remove(s.charAt(i));
    }
    return max;
}

2.最长回文字串（二维动态规划）

原题：给你一个字符串，找到最长的回文字串。

动态规划：回文子串的性质是，把最开始和最末尾的元素删除还是一个回文字串。状态转移方程为
$$
dp[i][i] = 1
$$
$$
dp[i][j] = dp[i+1][j-1] \land (S_{i} == S_{j})
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public String longestPalindrome(String s) {
    boolean[][] dp = new boolean[s.length()][s.length()];
    int length = 1;
    int head = 0,tail=0;
    //对角线上的元素都为1
    for (int i = 0; i < s.length(); i++) {
        dp[i][i] = true;
    }
    //沿着对角线逐渐增大，而不是根据表格行列遍历
    for (int k = 1; k < s.length(); k++) {
        for (int i = 0; i < s.length() - 1; i++) {
            //字串长度为2的时候单独考虑
            if (k == 1){
                //aa，bb这种字串
                if (s.charAt(i) == s.charAt(i+k)){
                    dp[i][i+k] = true;
                    //循环外部变量保存最大值和起始点和重点，因为返回的是具体的字串，需要调用substring
                    if (length < k+1){
                        length = k+1;
                        head = i;tail = i+k;
                    }
                }
            }
            //其余长度
            //只有dp[i+1][i+k-1]为回文字串且[i]和[i+k]相同的时候才是一个回文字串
            if (i+k < s.length() && s.charAt(i) == s.charAt(i+k) && dp[i+1][i+k-1]){
                dp[i][i+k] = true;
                if (k+1 > length){
                    length = k+1;
                    head = i;tail = i+k;
                }
            }

        }
    }
    //System.out.println(Arrays.deepToString(dp));
    return s.substring(head,tail+1);
}

3.最大子数组和（动态规划）

原题：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

动态规划：pre表示的是i之前的最大子数组和的最大值.如果pre是负数，那就相当于拖nums[i]后腿了，与其加上前面的不如自己作为开头。状态转移方程：

$$f(i) = max ( f(i-1)+nums[i],nums[i] ) $$

1
2
3
4
5
6
7
8
9
public int maxSubArray(int[] nums) {
    int pre = 0;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        pre = Math.max(pre+nums[i],nums[i]);
        max = Math.max(max,pre);
    }
    return max;
}

4.最长公共子序列（二维动态规划，与dp[i-1][j-1],dp[i-1][j],dp[i][j-1]有关）

这道题和编辑长度是一个类型的

原题：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

需要考虑dp[i-1][j-1],dp[i-1][j],dp[i][j-1]，所以dp[][]要多一行一列，状态转移方程：

  • text1.charAt(i) == text2.charAt(j):$dp[i][j] = dp[i-1][j-1]+1$
  • text1.charAt(i) != text2.charAt(j):$dp[i][j] = max(dp[i-1][j],dp[i][j-1])$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int longestCommonSubsequence(String text1, String text2) {
    //二维动态规划
    int[][] dp = new int[text1.length()+1][text2.length()+1];
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1]+1;
            }
            else {
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    return dp[dp.length-1][dp[0].length-1];
}

5.编辑距离（二维动态规划，与dp[i-1][j-1],dp[i-1][j],dp[i][j-1]有关）

原题：给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

与上面那个很相似，如果两个字符是相同的话就看dp[i-1][j-1]，但是不同的话也需要看dp[i-1][j-1]，因为即便字符不同也可以通过替换解决。状态转移方程为：

  • text1.charAt(i) == text2.charAt(j):$dp[i][j] = dp[i-1][j-1]$
  • text1.charAt(i) != text2.charAt(j):$dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1$

还有不同的就是初始化边缘不再都是0了，根据插入字符的数量决定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minDistance(String word1, String word2) {
    int[][] dp = new int[word1.length()+1][word2.length()+1];
    for (int i = 0; i < dp.length; i++) {
        dp[i][0] = i;
    }
    for (int i = 0; i < dp[0].length; i++) {
        dp[0][i] = i;
    }
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1];
            }
            else {
                dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
            }
        }
    }
    //System.out.println(Arrays.deepToString(dp));
    return dp[dp.length-1][dp[0].length-1];
}