一 : 跳石板

1.题目

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3…
这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
例如：
N = 4，M = 24：
4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板

2.解题

2.1思路分析

2.2具体代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] step = new int[m + 1];//防止下标越界
        /*
            一开始,数组下标都初始化为无穷大
        */
        for (int i = 0; i < m + 1; i++) {
            step[i] = Integer.MAX_VALUE;
        }
        //从n号石板开始,所以到达n号石板所需步数为0
        step[n] = 0;
        for (int i = n; i < m; i++) {
            //说明根本跳跃不到这一步石阶
            if (step[i] == Integer.MAX_VALUE) {
                continue;
            }
            //求i的约数
            List<Integer> list = div(i);
            for (int j : list) {
            //j代表此时我们一步可以条几个台阶
                if (i + j <= m && step[i + j] != Integer.MAX_VALUE) {
                    step[i + j] = Math.min(step[i + j], step[i] + 1);
                } else if (i + j <= m) {
                    //此时是第一次到达这一台阶,直接复制即可
                    step[i + j] = step[i] + 1;
                }
            }
        }
        if (step[m] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(step[m]);
        }
    }
    public static List<Integer> div(int num) {
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                list.add(i);
                if (num / i != i) {
                    list.add(num / i);
                }
            }
        }
        return list;
    }
}

二 :查找两个字符串a,b中的最长公共子串

1.题目

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

2.解题

2.1 思路分析

2.2具体代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        if (str1.length() < str2.length()) {
            System.out.println(maxSubString(str1, str2));
        } else {
            System.out.println(maxSubString(str2, str1));
        }
    }

    private static String maxSubString(String str1, String str2) {
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        int len1 = arr1.length;
        int len2 = arr2.length;
        int start = 0;//最长子串起始位置
        int max = 0;//最长子串的长度
        //数组下标从0开始,而字符串匹配时从1,1字符开始,所以增加辅助状态,相当于
        //二维数组第0行和第0列不用
        int[][] maxSubLength = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (arr1[i - 1] == arr2[j - 1]) {
                    maxSubLength[i][j] = maxSubLength[i - 1][j - 1] + 1;
                    if (max < maxSubLength[i][j]) {
                        max = maxSubLength[i][j];
                        start = i - max;
                    }
                }
            }
        }
        return str1.substring(start, start + max);
    }
}

三 : 字符串通配符

1.题目

描述
问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：

2.解题

2.1 思路分析

2.2具体代码

import java.util.*;

public class Main {
    public static boolean process(String s1, String s2) {
        int n1 = s1.length(); // 通配符串
        int n2 = s2.length(); // 匹配串
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        // 二维表中，横的是通配符串，纵的是匹配串
        boolean[][] dp = new boolean[n2 + 1][n1 + 1];
        // 初始化
        dp[0][0] = true;
        for(int i = 1; i <= n2; i++) { // c2 和空串匹配，永远为 false
            dp[i][0] = false;
        }
        boolean flg = false;
        for(int j = 1; j <= n1; j++) {
            // c1 只有 *，则和空串匹配为 true，出现一个非 *，则匹配为 false
            if(!flg && c1[j - 1] == '*') {
                dp[0][j] = true;
            } else {
                flg = true;
                dp[0][j] = false;
            }
        }

        for(int i = 1; i <= n2; i++) {
            for(int j = 1; j <= n1; j++) {
                if(c1[j - 1] == '*') {
                    // 只有英文字母和数字能被通配符匹配
                    if((c2[i - 1] >= '0' && c2[i - 1] <= '9') || (c2[i - 1] >= 'a' && c2[i - 1] <= 'z')
                            || (c2[i - 1] >= 'A' && c2[i - 1] <= 'Z')) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];
                    } else { // 不匹配，为 false
                        dp[i][j] = false;
                    }
                } else { // ? 和普通字符
                    if(match(c1[j - 1], c2[i - 1])) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = false;
                    }
                }
            }
        }
        return dp[n2][n1];
    }

    public static boolean match(char c1, char c2) {
        if(c1 == '?') return true;
        // 小写字母全部转为大写字母再比较
        if(c1 >= 'a' && c1 <= 'z') {
            c1 = (char)(c1 - 'a' + 'A');
        }
        if(c2 >= 'a' && c2 <= 'z') {
            c2 = (char)(c2 - 'a' + 'A');
        }
        return c1 == c2;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        System.out.println(process(s1, s2));
    }
}

四 : 最大子数组和

1.题目

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

2.题解

方法一 : 动态规划

这是一道典型的使用「动态规划」解决的问题，需要我们掌握动态规划问题设计状态的技巧（无后效性），并且需要知道如何推导状态转移方程，最后再去优化空间 .

关键 1 : 题目要我们找出和最大的连续子数组的值是多少 , **「连续」**是关键字，连续很重要，不是子序列 . 题目只要求返回结果，不要求得到最大的连续子数组是哪一个 . 这样的问题通常可以使用「动态规划」解决 .

关键 2：如何定义子问题(如何定义状态) .

设计状态思路：把不确定的因素确定下来，进而把子问题定义清楚，把子问题定义得简单 . 动态规划的思想通过解决了一个一个简单的问题，进而把简单的问题的解组成复杂的问题的解 .

第一种设计思路 :

例如，示例 1 输入数组是 [-2,1,-3,4,-1,2,1,-5,4] ，我们可以求出以下子问题：

子问题 1：经过 -2−2 的连续子数组的最大和是多少；
子问题 2：经过 11 的连续子数组的最大和是多少；
子问题 3：经过 -3−3 的连续子数组的最大和是多少；
子问题 4：经过 44 的连续子数组的最大和是多少；
子问题 5：经过 -1−1 的连续子数组的最大和是多少；
子问题 6：经过 22 的连续子数组的最大和是多少；
子问题 7：经过 11 的连续子数组的最大和是多少；
子问题 8：经过 -5−5 的连续子数组的最大和是多少；
子问题 9：经过 44 的连续子数组的最大和是多少。

一共 9 个子问题，这些子问题之间的联系并没有那么好看出来，这是因为子问题的描述还有不确定的地方-----有后效性 .

例如「子问题 3」: 经过 -3的连续子数组的最大和是多少 .

「经过 -3 的连续子数组」我们任意举出几个 :

[-2,1,-3,4] ，-3 是这个连续子数组的第 3 个元素；
[1,-3,4,-1] ，-3 是这个连续子数组的第 2 个元素；
……

我们不确定的是：-3−3 是连续子数组的第几个元素。那么我们就把 -3−3 定义成连续子数组的最后一个元素。在新的定义下，我们列出子问题如下：

子问题 1：以 -2−2 结尾的连续子数组的最大和是多少；
子问题 2：以 11 结尾的连续子数组的最大和是多少；
子问题 3：以 -3−3 结尾的连续子数组的最大和是多少；
子问题 4：以 44 结尾的连续子数组的最大和是多少；
子问题 5：以 -1−1 结尾的连续子数组的最大和是多少；
子问题 6：以 22 结尾的连续子数组的最大和是多少；
子问题 7：以 11 结尾的连续子数组的最大和是多少；
子问题 8：以 -5−5 结尾的连续子数组的最大和是多少；
子问题 9：以 44 结尾的连续子数组的最大和是多少。

我们加上了「结尾的」，这些子问题之间就有了联系 .输入数组是 [-2,1,-3,4,-1,2,1,-5,4] .

我们单独看子问题 1 和子问题 2：

子问题 1：以 -2 结尾的连续子数组的最大和是多少；
以 -2 结尾的连续子数组是 [-2]，因此最大和就是 -2。

子问题 2：以 1 结尾的连续子数组的最大和是多少；
以 1 结尾的连续子数组有 [-2,1] 和 [1] ，其中 [-2,1] 就是在「子问题 1」的后面加上 1 得到。-2 + 1 = -1 < 1−2+1=−1<1 ，因此「子问题 2」 的答案是 1 .

如果编号为 i 的子问题的结果是负数或者 00 ，那么编号为 i + 1 的子问题就可以把编号为 i 的子问题的结果舍弃掉（这里 i 为整数，最小值为 1 ，最大值为 8），这是因为：

• 一个数 a 加上负数的结果比 a 更小；
• 一个数 a 加上 0 的结果不会比 a 更大；

而子问题的定义必须以一个数结尾，因此如果子问题 i 的结果是负数或者 0，那么子问题 i + 1 的答案就是以 nums[i] 结尾的那个数 .

接下来我们按照编写动态规划题解的步骤，把「状态定义」「状态转移方程」「初始化」「输出」「是否可以空间优化」全都写出来 .

参考代码 :

public class Solution {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[len];
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }

        // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

时间复杂度：O(N) ，这里 N 是输入数组的长度 ;
空间复杂度：O(N) ，这里 N 是输入数组的长度 .

优化代码(使用滚动变量).

public class Solution {

    public int maxSubArray(int[] nums) {
        int pre = 0;
        int res = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            res = Math.max(res, pre);
        }
        return res;
    }
}

通过一次循环 , 就可以达到上面两次循环的目的 .

时间复杂度：O(N) ，这里 N 是输入数组的长度 ;
空间复杂度：O(N) ，这里 N 是输入数组的长度 .

关于无后效性

李煜东著《算法竞赛进阶指南》，摘录如下：

为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响 . 这个条件也被叫做「无后效性」 . 换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序 . 有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」 .

我的解释：

每一个子问题只求解一次，以后求解问题的过程不会修改以前求解的子问题的结果；

换句话说：如果之前的阶段求解的子问题的结果包含了一些不确定的信息，导致了后面的阶段求解的子问题无法得到，或者很难得到，这叫「有后效性」，我们在当前这个问题第 1 次拆分的子问题就是「有后效性」的；
解决「有后效性」的办法是固定住需要分类讨论的地方，记录下更多的结果。在代码层面上表现为：

• 状态数组增加维度，例如：「力扣」的股票系列问题 ;
• 把状态定义得更细致、准确，例如：前天推送的第 124 题：状态定义只解决路径来自左右子树的其中一个子树 .

方法二 : 分治法

分治法的思路是这样的，其实也是分类讨论 .

连续子序列的最大和主要由这三部分子区间里元素的最大和得到：

第 1 部分：子区间 [left, mid]；
第 2 部分：子区间 [mid + 1, right]；
第 3 部分：包含子区间 [mid , mid + 1] 的子区间，即 nums[mid] 与 nums[mid + 1] 一定会被选取。
对这三个部分求最大值即可。

public class Solution {
		 /**
		 主要的功能函数
		 **/
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        return maxSubArraySum(nums, 0, len - 1);
    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 一定会包含 nums[mid] 这个元素
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        // 左半边包含 nums[mid] 元素，最多可以到什么地方
        // 走到最边界，看看最值是什么
        // 计算以 mid 结尾的最大的子数组的和
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        // 右半边不包含 nums[mid] 元素，最多可以到什么地方
        // 计算以 mid+1 开始的最大的子数组的和
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }

    private int maxSubArraySum(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        return max3(maxSubArraySum(nums, left, mid),
                maxSubArraySum(nums, mid + 1, right),
                maxCrossingSum(nums, left, mid, right));
    }

    private int max3(int num1, int num2, int num3) {
        return Math.max(num1, Math.max(num2, num3));
    }
}

分治法重在了解其思路 , 代码比较复杂 .

时间复杂度：O(N \log N)O(NlogN)，这里递归的深度是对数级别的，每一层需要遍历一遍数组（或者数组的一半、四分之一）；
空间复杂度：O(\log N)O(logN)，需要常数个变量用于选取最大值，需要使用的空间取决于递归栈的深度。

本题结束 !