双向BFS
对称迷宫
package java_Algorithm.self.train01; import java.util.*; /** * wlxsq有一个N*N的网格迷宫,每一个网格都有一个字母编号。 * 他要从左上角(1,1)出发,走到右下角(n, n),由于wlxsq很懒,所以他每次只会往右或者往下走一格。 * 由于最后到终点的路径方案太多太多了,所以wlixsq想让你计算出所有不同的对称的路径个数。 * 例如:N = 3 * ABA * BBB * ABA * 对称路径6条:有ABABA(2条)、ABBBA(4条) * 不同的对称路径有:有ABABA、ABBBA * 输入 * 第一行输入一个数N,表示迷宫的大小。 * 接下来输入N *N的字母迷宫 * 输出 * 输出对称路径的数量 * <p> * 样例 * 输入3ABABBBABA * 输出2 * 提示 * 【评测用例规模与约定】 * 对于40%的数据,2<= N<=11 * 对于100%的数据,2<= N=18 */ public class demo72_对称迷宫_dbfs { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Set<String> set = new HashSet<>();//储存最终结果 int n = Integer.parseInt(sc.nextLine()); char[][] map = new char[n][n]; for (int i = 0; i < n; i++) { String string = sc.nextLine(); map[i] = string.toCharArray(); } Queue<node> q1 = new LinkedList<>();//右下的队列 Queue<node> q2 = new LinkedList<>();//左上的队列 for (int i = 0; i < n; i++) {//遍历对角线上的每个node q1.clear(); q2.clear(); Set<String> set1 = new HashSet<>();//储存右下 Set<String> set2 = new HashSet<>();//储存左上 q1.add(new node(i, n - 1 - i, "" + map[i][n - 1 - i])); q2.add(new node(i, n - 1 - i, "" + map[i][n - 1 - i])); while (!q1.isEmpty() && !q2.isEmpty()) { node team = q1.poll(); node team2 = q2.poll(); if (team.x == n - 1 && team.y == n - 1) {//到终点,将路径储存 set1.add(team.path); set2.add(team2.path); } else { if (team.x < n - 1) //可以向下 q1.add(new node(team.x + 1, team.y, team.path + map[team.x + 1][team.y])); if (team.y < n - 1) //可以向右 q1.add(new node(team.x, team.y + 1, team.path + map[team.x][team.y + 1])); if (team2.x > 0) //上 q2.add(new node(team2.x - 1, team2.y, team2.path + map[team2.x - 1][team2.y])); if (team2.y > 0) //左 q2.add(new node(team2.x, team2.y - 1, team2.path + map[team2.x][team2.y - 1])); } } for (String va : set1) if (set2.contains(va)) set.add(va); } System.out.println(set.size()); } static class node { int x; int y; String path; public node(int x, int y, String team) { this.x = x; this.y = y; this.path = team; } } }
打开转盘锁
package java_Algorithm.self.train01; import java.util.*; /** * @Author: LiangXinRui * @Date: 2023/03/07/9:06 * @Description: https://leetcode.cn/problems/open-the-lock/ */ public class demo72_打开转盘锁_dbfs { static String star, tag; static Set<String> set = new HashSet<>(); public static void main(String[] args) { String[] deadends = {"0201", "0101", "0102", "1212", "2002"}; String target = "0202"; System.out.println(openLock(deadends, target)); } private static int openLock(String[] deadends, String target) { star = "0000"; tag = target; if (star.equals(tag)) return 0; Collections.addAll(set, deadends); if (set.contains(star)) return -1; return dbfs(); } private static int dbfs() { // q1 代表从起点 star 开始搜索(正向) , q2 代表从结尾 tag 开始搜索(反向) Queue<String> q1 = new LinkedList<>(), q2 = new LinkedList<>(); /* * m1 和 m2 分别记录两个方向出现的状态是经过多少次转换而来 * e.g. * m1 = {"1000":1} 代表 "1000" 由 s="0000" 旋转 1 次而来 * m2 = {"9999":3} 代表 "9999" 由 t="9996" 旋转 3 次而来 */ Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>(); q1.offer(star); m1.put(star, 0); q2.offer(tag); m2.put(tag, 0); /* * 只有两个队列都不空,才有必要继续往下搜索 * 如果其中一个队列空了,说明从某个方向搜到底都搜不到该方向的目标节点 * e.g. * 例如,如果 q1 为空了,说明从 star 搜索到底都搜索不到 tag,反向搜索也没必要进行了 */ while (!q1.isEmpty() && !q2.isEmpty()) { int ans; if (q1.size() <= q2.size()) { ans = update(q1, m1, m2); } else { ans = update(q2, m2, m1); } if (ans != -1) return ans; } return -1; } private static int update(Queue<String> queue, Map<String, Integer> cur, Map<String, Integer> other) { int len = queue.size(); while (len-- > 0) { String poll = queue.poll(); char[] chars = poll.toCharArray(); int step = cur.get(poll); // 枚举替换哪个字符 for (int i = 0; i < 4; i++) { // 能「正向转」也能「反向转」,这里直接枚举偏移量 [-1,1] 然后跳过 0 for (int j = -1; j <= 1; j++) { if (j == 0) continue; // 求得替换字符串 str int origin = chars[i] - '0'; int next = (origin + j) % 10; if (next == -1) next = 9; char[] clone = chars.clone(); clone[i] = (char) (next + '0'); String str = String.valueOf(clone); if (set.contains(str)) continue; if (cur.containsKey(str)) continue; // 如果在「另一方向」找到过,说明找到了最短路,否则加入队列 if (other.containsKey(str)) { return step + 1 + other.get(str); } else { queue.offer(str); cur.put(str, step + 1); } } } } return -1; } }
单词接龙
package java_Algorithm.self.train01; import java.util.*; /** * @Author: LiangXinRui * @Date: 2023/03/05/19:22 * @Description: https://leetcode.cn/problems/word-ladder/submissions/ * 已知目标顶点的情况下,可以分别从起点和目标顶点(终点)执行广度优先遍历,直到遍历的部分有交集。这就是双向广度优先遍历的思想,这种方式搜索的单词数量会更小一些; * 更合理的做法是,每次从单词数量小的集合开始扩散; * 这里 beginVisited 和 endVisited 交替使用,等价于单向 BFS 里使用队列,每次扩散都要加到总的 visited 里。 */ public class demo72_单词接龙_双向bfs { public static void main(String[] args) { ArrayList<String> wordList = new ArrayList<>(); wordList.add("hot"); wordList.add("dot"); wordList.add("dog"); wordList.add("lot"); wordList.add("log"); wordList.add("cog"); System.out.println(ladderLength("hit", "cog", wordList)); } static int ladderLength(String beginWord, String endWord, List<String> wordList) { // 第 1 步:先将 wordList 放到哈希表里,便于判断某个单词是否在 wordList 里 Set<String> wordSet = new HashSet<>(wordList); if (wordSet.size() == 0 || !wordSet.contains(endWord)) { return 0; } // 第 2 步:已经访问过的 word 添加到 visited 哈希表里 Set<String> visited = new HashSet<>(); // 分别用左边和右边扩散的哈希表代替单向 BFS 里的队列,它们在双向 BFS 的过程中交替使用 Set<String> beginVisited = new HashSet<>(); beginVisited.add(beginWord); Set<String> endVisited = new HashSet<>(); endVisited.add(endWord); // 第 3 步:执行双向 BFS,左右交替扩散的步数之和为所求 int step = 1; while (!beginVisited.isEmpty() && !endVisited.isEmpty()) { // 优先选择小的哈希表进行扩散,考虑到的情况更少 if (beginVisited.size() > endVisited.size()) { Set<String> temp = beginVisited; beginVisited = endVisited; endVisited = temp; } // 逻辑到这里,保证 beginVisited 是相对较小的集合,nextLevelVisited 在扩散完成以后,会成为新的 beginVisited Set<String> nextLevelVisited = new HashSet<>(); for (String word : beginVisited) { if (changeWordEveryOneLetter(word, endVisited, visited, wordSet, nextLevelVisited)) { return step + 1; } } // 原来的 beginVisited 废弃,从 nextLevelVisited 开始新的双向 BFS beginVisited = nextLevelVisited; step++; } return 0; } //尝试对 word 修改每一个字符,看看是不是能落在 endVisited 中,扩展得到的新的 word 添加到 nextLevelVisited 里 static boolean changeWordEveryOneLetter(String word, Set<String> endVisited, Set<String> visited, Set<String> wordSet, Set<String> nextLevelVisited) { char[] charArray = word.toCharArray(); for (int i = 0; i < word.length(); i++) { char originChar = charArray[i]; for (char c = 'a'; c <= 'z'; c++) { if (originChar == c) { continue; } charArray[i] = c; String nextWord = String.valueOf(charArray); if (wordSet.contains(nextWord)) { if (endVisited.contains(nextWord)) { return true; } if (!visited.contains(nextWord)) { nextLevelVisited.add(nextWord); visited.add(nextWord); } } } // 恢复,下次再用 charArray[i] = originChar; } return false; } }
滑动窗口
滑动窗口算法也是一种思想,是双指针的拓展和延伸,很多算法题目都可以基于该思想来解决,所以我们就将两者放在一起学习。 首先明白什么是滑动、什么是窗口: - 滑动:说明这个窗口是移动的,也就是移动是按照一定方向来的。 - 窗口:窗口大小并不是固定的,可以不断扩容直到满足一定的条件;也可以不断缩小,直到找到一个满足条件的最小窗口;当然也可以是固定大小。 滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。 简而言之,滑动窗口算法在一个特定大小的字符串或数组上进行操作,而不在整个字符串和数组上操作,这样就降低了问题的复杂度,从而也达到降低了循环的嵌套深度。其实这里就可以看出来滑动窗口主要应用在数组和字符串上。 滑动窗口算法的思路是这样: 1. 我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个「窗口」。 2. 我们先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符)。 3. 此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。 4. 重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。 这个思路其实也不难,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。
上述过程对于非固定大小的滑动窗口,可以简单地写出如下基本框架:
string s, t; // 在 s 中寻找 t 的「最小覆盖子串」 int left = 0, right = 0; string res = s; while(right < s.size()) { window.add(s[right]); right++; // 如果符合要求,说明窗口构造完成,移动 left 缩小窗口 while (window 符合要求) { // 如果这个窗口的子串更短,则更新 res res = minLen(res, window); window.remove(s[left]); left++; } } return res;
与双指针基本一致,但是对于固定窗口大小k,此时不需要依赖 left 指针了,因为left = right-k可以总结如下:
// 固定窗口大小为 k string s; // 在 s 中寻找窗口大小为 k 时的所包含最大元音字母个数 int right = 0; while(right < s.size()) { window.add(s[right]); right++; // 如果符合要求,说明窗口构造完成, if (right>=k) { // 这是已经是一个窗口了,根据条件做一些事情 // ... 可以计算窗口最大值等 // 最后不要忘记把 right -k 位置元素从窗口里面移除 } } return res;
固定窗口例题:滑动窗口(单调队列)
先简单描述一下单调队列:
单调队列和单调栈类似,就是队列内的元素是单调的,并且是满足出队顺序的单调性。它可以维护局部的单调性。由于单调队列可以队首出队以及前面的元素一定比后面的元素先入队的性质,使得它可以维护局部的单调性,并且当队首元素不在区间之内则可以出队,其复杂度也是线性的。
问题描述:
有一个长度为 n 的数列和一个大小为 k 的窗口, 窗口可以在数列上来回移动. 现在我们想知道在窗口从左往右滑的时候,每次窗口内数的最大值和最小值分别是多少. 例如:
input: 输入有两行。第一行两个整数n 和k 分别表示数列的长度和滑动窗口的大小,1 ≤ k ≤ n ≤ 1000000 第二行有n个整数表示数列。 output: 输出有两行。第一行输出滑动窗口在从左到右的每个位置时,滑动窗口中的最小值。第二行是最大值。 样例输入: 8 3 1 3 -1 -3 5 3 6 7 1 2 样例输出: -1 -3 -3 -3 3 3 3 3 5 5 6 7
解题思路:
由于是求解区间内的最大最小值,是一个局部的概念,那么我们就是使用单调队列。我们可以维护一个单调递增队列和一个单调递减队列, 队列中的元素均属于当前窗口,当元素不属于当前窗口时, 将队首元素弹出即可。
我们可以通过两个下标,来模拟队列的队首和队尾指针,对于一个元素,其有两个域,一个是数值域,一个是下标域。由于单调队列复杂度为线性,那么我们可以使用一次for循环来实现对区间中最小值的查找,并且使用单调递增队列,这样我们就能保证队首为窗口最小值。查找最大值则相反。然后再用一次for循环实现对区间中最大值的差找。对于要压入队列的元素,我们首先要判断它是不是小于队尾元素,如果小于,将队尾元素弹出栈,直到满足条件为止。其次,由于每次只压入一个元素,我们可以通过一个if语句,判断当前元素的下标和队首元素的下标差是否大于窗口大小,若大于,将队首弹出栈。这样,我们当前压入队列所在的窗口中的最小值就是队首元素。这样我们就能找到所有元素所在窗口的最小元素,求最大值则将数组逆序利用单调递减队列即可。
public class demo90_滑动窗口_固定窗口_单调队列 { static int n, k; static int[] left = new int[1000010];//窗口最小值 static int[] right = new int[1000010];//窗口最大值 static num[] queue1 = new num[1000010]; static num[] queue2 = new num[1000010]; static num[] array = new num[1000010]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); k = scanner.nextInt(); for (int i = 1; i <= n; i++) { array[i] = new num(scanner.nextInt(), i); } int top = 1, tail = 0; for (int i = 1; i <= n; i++) { //若队尾元素大于新元素,则弹出队尾元素 while (top <= tail && queue1[tail].date > array[i].date) tail--; queue1[++tail] = array[i]; //如果大于窗口长度 ,弹出队首元素(tail - top) /*由于是从前往后遍历的数组,先遍历到的元素下标小, 理应用队尾元素的下标-队首元素的下标 得到正数(大下标-小下标)*/ if ((queue1[tail].location - queue1[top].location + 1) > k) top++;//写在弹队尾的后面可以防止queue1[tail]为null的情况 int indexR = queue1[tail].location; left[indexR] = queue1[top].date;//当前元素所在窗口的最小值 } top = 1; tail = 0; for (int i = n; i >= 1; i--) {//最大值同理 //若队尾元素小于新元素,则弹出队尾元素 while (top <= tail && queue2[tail].date < array[i].date) tail--; queue2[++tail] = array[i]; //如果大于窗口长度 ,弹出队首元素(top - tail) /*由于是从后往前遍历的数组,先遍历到的元素下标更大, 理应用队首元素的下标-队尾元素的下标 得到正数(大下标-小下标)*/ if ((queue2[top].location - queue2[tail].location + 1) > k) top++; int indexR = queue2[tail].location; right[indexR] = queue2[top].date;//当前元素所在窗口的最大值 } int window = n - k + 1; for (int i = k; i <= n; i++) System.out.print(left[i] + " "); System.out.println(); for (int i = 1; i <= n - k + 1; i++) System.out.print(right[i] + " "); } static class num { int date = 0;//元素 int location = 0;//下标 public num(int date, int location) { this.date = date; this.location = location; } } }
倍增的运用
ST表的原理和实现
我们定义ST[i][k]表示区间 [i, i + 2^k - 1]的最值,那么显然ST[i][0] = a0
Init
static void init() { for (int i = 0; i < n; i++) { ST[i][0] = array[i]; } for (int k = 1; k < f; k++) { for (int s = 0; s + (1 << k) <= n; s++) {// 1 << k 表示2的k次方 ST[s][k] = Math.max(ST[s][k - 1], ST[s + (1 << (k - 1))][k - 1]); } } }
query
static int query(int begin, int end) { int len = end - begin + 1; int k = (int) (Math.log(len) / Math.log(2)); return Math.max(ST[begin][k], ST[end - (1 << k) + 1][k]); }
区间最大值
- (int) Math.ceil(Math.log(n) / Math.log(2));//求得长度是2的多少次方
- 1 << k 表示2的k次方
package java_Algorithm.self.train01; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @Author: LiangXinRui * @Date: 2023/03/02/14:28 * @Description: https://www.lanqiao.cn/problems/1205/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=8&name=%E5%8C%BA%E9%97%B4 */ public class Main { static int n, q, f; static int[] array; static int[][] ST; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { String[] fist = br.readLine().split(" "); n = Integer.parseInt(fist[0]);//数组长度 q = Integer.parseInt(fist[1]);//询问个数 f = (int) Math.ceil(Math.log(n) / Math.log(2));//求得长度是2的多少次方 array = new int[n]; ST = new int[n][f]; String[] second = br.readLine().split(" "); for (int i = 0; i < n; i++) { array[i] = Integer.parseInt(second[i]); } init(); //每个询问包含两个整数 L,R,表示区间的左右端点 for (int i = 0; i < q; i++) { String[] split = br.readLine().split(" "); System.out.println(query(Integer.parseInt(split[0]) - 1, Integer.parseInt(split[1]) - 1)); } } static void init() { for (int i = 0; i < n; i++) { ST[i][0] = array[i]; } for (int k = 1; k < f; k++) { for (int s = 0; s + (1 << k) <= n; s++) {// 1 << k 表示2的k次方 ST[s][k] = Math.max(ST[s][k - 1], ST[s + (1 << (k - 1))][k - 1]); } } } static int query(int begin, int end) { int len = end - begin + 1; int k = (int) (Math.log(len) / Math.log(2)); return Math.max(ST[begin][k], ST[end - (1 << k) + 1][k]); } }
蓝桥杯例题:m计划
输入输出样例 示例 *输入 5 3 5 3 2 4 1 *输出 2 2 1
package java_Algorithm.self.train01; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @Author: LiangXinRui * @Date: 2023/03/01/21:31 * @Description: */ public class demo079_倍增_m计划 { static int n, m, f;//n:总长度 m:与询问次数有关的参数 f:确定一共有多少种长度的区间 static int[] array;//原数组 static int[][] ST;//ST表 (本质是dp) static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { //处理输入 String[] split = br.readLine().split(" "); n = Integer.parseInt(split[0]); m = Integer.parseInt(split[1]); f = (int) Math.ceil(Math.log(n) / Math.log(2));//计算出一共需要构造多少种不同长度的区间 array = new int[n]; ST = new int[n][f]; String[] line = br.readLine().split(" "); for (int i = 0; i < n; i++) { array[i] = Integer.parseInt(line[i]); } //初始化 init(); //查询 for (int i = 1; i <= n - m + 1; i++) { System.out.println(query(i - 1, i + m - 2)); } br.close(); } static void init() { //构建长度为一的区间(自身) for (int i = 0; i < n; i++) { ST[i][0] = array[i]; } for (int k = 1; k < f; k++) {//枚举区间长度 for (int s = 0; s + (1 << k) <= n; s++) {//枚举区间左端点,左端点 + 区间长度 = 右端点 <= n ST[s][k] = Math.min(ST[s][k - 1], ST[s + (1 << (k - 1))][k - 1]);//合并前一种区间长度的两个小区间作为新的区间 } } } static int query(int beginIndex, int endIndex) { int len = endIndex - beginIndex + 1; int k = (int) (Math.log(len) / Math.log(2)); return Math.min(ST[beginIndex][k], ST[endIndex - (1 << k) + 1][k]);//合并两个小区间,得到询问区间的最值 } }
KMP
KMP字符匹配
步骤
先写kmp创建部分匹配表的方法:public static int[] kmpNext(String dest)
再写出kmp的搜索方法:public static int kmpSearch(String str1, String str2, int[] next)
在主函数中:
先定义主字符串str1和要匹配的字符串str2
将str2作为参数,调用kmpNext(str2)方法得到部分匹配表,并用int[] next接收
将str1、str2、next作为参数,调用kmpSearch(str1, str2, next),并用int index接收
输出index,即为匹配到的第一个下标,若没有匹配到的,则返回index的值为-1
kmpNext() 注意是next[ j - 1 ]
public static int[] kmpNext(String dest) { int[] next = new int[dest.length()]; int j = 0; for(int i = 1; i < dest.length(); i++) { while(j > 0 && dest.charAt(i) != dest.charAt(j)) { j = next[j-1]; } if(dest.charAt(i) == dest.charAt(j)) { j++; } next[i] = j; } return next; }
kmpSearch() 注意while里面的i 和 j、str1和str2 ,不要写错了
public static int kmpSearch(String str1, String str2, int[] next) { int j = 0; for (int i = 0; i < str1.length(); i++) { while (j > 0 && str1.charAt(i) != str2.charAt(j)) { j = next[j - 1]; } if (str1.charAt(i) == str2.charAt(j)) { j++; } if (j == str2.length()) { return i - j + 1; } } return -1; }
综合代码
public class KMPAlgorithm { /*//KMP算法核心点, 可以验证...!!!!!!!!!!!!!!!! while( j > 0 && str1.charAt(i) != str2.charAt(j)) { j = next[j-1]; }*/ public static void main(String[] args) { String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD"; //String str2 = "BBC"; int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0] System.out.println("next=" + Arrays.toString(next)); int index = kmpSearch(str1, str2, next); System.out.println("index=" + index); // 15了 } //写出我们的kmp搜索算法 /** * @param str1 源字符串 * @param str2 子串 * @param next 部分匹配表, 是子串对应的部分匹配表 * @return 如果是-1就是没有匹配到,否则返回第一个匹配的位置 */ public static int kmpSearch(String str1, String str2, int[] next) { //遍历 for(int i = 0, j = 0; i < str1.length(); i++) { //需要处理 str1.charAt(i) != str2.charAt(j), 去调整j的大小 //KMP算法核心点, 可以验证... while( j > 0 && str1.charAt(i) != str2.charAt(j)) { j = next[j-1]; } if(str1.charAt(i) == str2.charAt(j)) { j++; } if(j == str2.length()) {//找到了 // j = 3 i return i - j + 1; } } return -1; } //获取到一个字符串(子串) 的部分匹配值表 public static int[] kmpNext(String dest) { //创建一个next 数组保存部分匹配值 int[] next = new int[dest.length()]; next[0] = 0; //如果字符串是长度为1 部分匹配值就是0 for(int i = 1, j = 0; i < dest.length(); i++) { //当dest.charAt(i) != dest.charAt(j) ,我们需要从next[j-1]获取新的j //直到我们发现 有 dest.charAt(i) == dest.charAt(j)成立才退出 //这是kmp算法的核心点 while(j > 0 && dest.charAt(i) != dest.charAt(j)) { j = next[j-1]; } //当dest.charAt(i) == dest.charAt(j) 满足时,部分匹配值就是+1 if(dest.charAt(i) == dest.charAt(j)) { j++; } next[i] = j; } return next; } }
题目:小明的字符串
package java_code_lxr; import java.util.Scanner; //https://www.lanqiao.cn/problems/1203/learning/ public class demo81_KMP_小明的字符串 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str1 = scanner.nextLine(); String str2 = scanner.nextLine(); int[] next = kmpNext(str2); int temp; for (int i = str2.length(); i > 0; i--) { temp = kmpSearch(str1, str2.substring(0, i), next); if (temp != -1) { System.out.println(temp); break; } } } private static int kmpSearch(String str1, String str2, int[] next) { int j = 0; for (int i = 0; i < str1.length(); i++) { while (j > 0 && str1.charAt(i) != str2.charAt(j)) j = next[j - 1]; if (str1.charAt(i) == str2.charAt(j)) j++; if (j == str2.length()) return str2.length(); } return -1; } private static int[] kmpNext(String str2) { int[] next = new int[str2.length()]; int j = 0; for (int i = 1; i < str2.length(); i++) { while (j > 0 && str2.charAt(i) != str2.charAt(j)) j = next[j - 1]; if (str2.charAt(i) == str2.charAt(j)) j++; next[i] = j; } return next; } }
DP动态规划
/** * 凡是dp问题,记住一句话:当前的结果都是由之前的过程推导出来的。 * 我们要把之前推导的过程列出来,从而知道当前结果是怎么推导出来的(画表格), * 进而写出递推方程式 * 找出base情况 * 根据方程式计算出 dp 中其他内容 */
爬楼梯问题:
//N级台阶,每次爬一级或者爬两级,爬上去一共有多少种不同的办法? public class dp_ClimbStairs { public static void main(String[] args) { int n = 5; int[] dp = new int[n + 1]; // 定义动态方程式 // 在第i级台阶时,有多少种不同的办法? // dp[i] = dp[i-1]+dp[i-2] dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } System.out.println(dp[n]); } }
最大的子串(连续)和:
/** * 【最大的子串(连续)和是多少】 * array = [-2,1,-3,4,-1,2,1,-5,4] * <p> * 4,-1,2,1 =》6 * dp[i] => 以第i位为结尾的子串,最大的和是多少? */ /** * dp[i] => 查看前面的数字 * (1)如果dp[i-1]是正数,把前面的加起来 * (2)如果dp[i-1]是负数,用自己当一个子串 * if(dp[i-1]<0) => dp[i] = dp[i] * else => dp[i] = num[i] + dp[i-1] * 动态方程式:dp[i] = Math.max(dp[i], num[i]+dp[i-1]) */ public class dp_MaxSubArray { public static void main(String[] args) { int[] array = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}; int n = array.length; int[] dp = new int[n]; // base: 每一位都是自己为一个子串 for (int i = 0; i < n; i++) { dp[i] = array[i]; } int max = Integer.MIN_VALUE; for (int i = 1; i < n; i++) { // 如果前面为正数进行累加,如果为负数就用自己当子串 dp[i] = Math.max(array[i] + dp[i - 1], dp[i]); max = Math.max(max, dp[i]); } System.out.println(max); } }
长的升序子序列(可以不连续):
/** * 【最长的升序子序列(可以不连续)的长度是多少?】 * array=[1,2,10,5,20,100,30] * * 1,2,10,20,100 => 5 * 1,2,5,20,100 => 5 * 1,2,5,20,30 => 5 * * dp[i] => 以第i位为结尾的升序子序列,最长的长度是什么? */ import java.util.Arrays; public class dp_IncreasingSubSqu { public static void main(String[] args) { int[] array = new int[]{1, 2, 10, 5, 20, 100, 30}; int n = array.length; int[] dp = new int[n]; // base:每一位都用自己当一个子序列 Arrays.fill(dp, 1); int max = dp[0]; // i代表当前这一个数字 for (int i = 0; i < n; i++) { // 查看i前面范围内,能否把自己放上去 for (int j = 0; j < i; j++) { if (array[i] > array[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); max = Math.max(max, dp[i]); } } } System.out.println(max); } }
01背包问题:
dp[i][j] = max( 上方单元格的价值,剩余空间的价值 + 当前商品的价值 ) = max( dp[i-1][j],dp[i-1][j-当前商品的体积] + 当前商品的价值 ) = max( dp[i-1][j],dp[i-1][j-w[i]] + v[i] ) 其中,dp[i][j]表示表格中的第i行第j列单元格中的值 01降维 dp[j] = max( dp[j] , v[i] + dp[j - w[i]] )
public class demo73采药01dp { static int M = 105;//开出的空间比给出范围大一点 static int N = 1005;//开出的空间比给出范围大一点 static int m, n;//m行(每行代表一种物品) n列(每列代表一个时间点) static int[][] dp = new int[M][N];//创建动态表格 static int[] t = new int[M];//存时间(对应背包中的物品重量) static int[] v = new int[M];//存价值 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); scanner.nextLine(); for (int i = 1; i <= m; i++) { t[i] = scanner.nextInt(); v[i] = scanner.nextInt(); scanner.nextLine(); } for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (j >= t[i])//如果当前表格的时间大于采摘第i个药品所需要的时间(即能装下) dp[i][j] = Math.max(dp[i - 1][j], (v[i] + dp[i - 1][j - t[i]]));//前者为不拿当前物品的价值,后者为装入当前物品的价值+剩余容量再上一次中能拿到的最大价值 else//表示当前物品的容量超出了当前表格的容量 --> 直接将上一层中同容量的数据填入表格 dp[i][j] = dp[i - 1][j]; System.out.println(dp[m][n]); } }
上述代码是一个满分代码,但是不够完美。因为此算法存在一个显著缺陷:dp[M][N]数组在M或N取值较大时可能会出现爆内存的现象。因此,我们需要设法进行降维。从哪儿降呢?要么变成dp[M],要么变成dp[N]。如果是保留dp[M],这意味着在进行状态转移时,是以草药的种类来进行的(即在二维表格中填表时按列进行),这和前面我们采取的填表方式相悖;而如果是保留dp[N],那么我们在进行状态转移时就是以背包容量来进行的(即在二维表格中填表时按行进行),这和前面采取的填表方式一致。这就提示我们,可以将药的种类省略,而仅用一个和背包容量相当的一位数组dp[N]来进行状态转移。此时,我们可以利用一个循环,来将输入的数据不断与前面的数据进行计算、比较,并将最新结果保存至dp[N]中。据此,可以得到新的递推式为:
dp[j] = max(dp[j] , dp[j - w[i]] + v[i])
但是这里有个新问题,当在一维数组中从左至右更新dp[N]数组时,由于dp[j - w[i]] + v[i]总是大于dp[j],因此这将使得某个物品被反复拿多次。以上面的例子举例(在以下物品中拿最大价值,背包总容量为4):
那么在利用递推式:
dp[j] = max(dp[j] , dp[j - w[i]] + v[i])
1
进行动态转移时,其更新过程如下(注:dp[N]数组在初始情况下的所单元格中的值均为0):
第一个单元格,此时dp[1]=max(dp[1], dp[1-1]+1500)=max(0, 0+1500)=1500;
第二个单元格,此时dp[2]=max(dp[2], dp[2-1]+1500)=max(dp[2], dp[1]+1500)=max(0, 1500+1500)=3000;
第三个单元格,此时dp[3]=max(dp[3], dp[3-1]+1500)=max(dp[3], dp[2]+1500)=max(0, 3000+1500)=4500;
第四个单元格,此时dp[4]=max(dp[4], dp[4-1]+1500)=max(dp[4], dp[3]+1500)=max(0, 4500+1500)=6000;
……
可以发现,从第2个单元格开始,后面将一直错下去,因为这之后的每次更新都会利用前面的计算结果(实际上,这样的执行流程在逻辑上表示重复取当前物品,即某件物品不再是被拿了一次,而是被拿了多次)。
备注:这里的“错误”做法,洽洽又是后面完全背包问题的正确处理办法。
这又该如何处理呢?我们来分析出现这种情况的原因。由于大容量的背包在存放物品时可能不仅能存放前面已经存放的,或许还会因为大容量而使得其能拿更多的物品,从而出现反复拿小体积物品的情况。因此在自左向右更新的过程中,由于取 max(dp[j] , dp[j - w[i]] + v[i]) 而使得后面的数组在更新时不断利用前面已经保留好的结果来进行状态转转移,进而不断出错(即对某件物品反复拿取)。
虽然如此,但这个递推公式本身是正确的,只是在使用过程中由于更新方向而出现了一些错误。试想,如果从右向左对数组进行更新是否可行呢?在这种情况下,当用到:
dp[j] = max(dp[j] , dp[j - w[i]] + v[i])
时,由于dp[j - w[i]]指向的数组还未进行更新,此时其存放的结果是在前一种情况下(只能拿前一种及其更之前的物品时),对应容量背包所能存放的最大价值。故此时max(dp[j] , dp[j - w[i]] + v[i]) 表示的含义正是:“在当前背包容量下,怎样的拿取方案具有更大价值:延续上一种拿取方案 or 拿当前物品再加上除开当前物品体积后剩余背包容量所具有的最大价值后的总价值”。这和我们所期望的效果是一致的。下面给出改进后(降维使用滚动数组)的完整代码:
public class demo73采药01dp_降维 { //这里只写降维后需要注意的地方,其余注释见二维的代码 static int M = 105; static int N = 1005; static int m, n; static int[] dp = new int[N];//创建降维的动态表格,第几次存就代表存的第几行,一共N列 static int[] t = new int[M]; static int[] v = new int[M]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); scanner.nextLine(); for (int i = 1; i <= m; i++) { t[i] = scanner.nextInt(); v[i] = scanner.nextInt(); scanner.nextLine(); } for (int i = 1; i <= m; i++) for (int j = n; j >= t[i]; j--)//如果当前表格的时间大于采摘第i个药品所需要的时间(即能装下),否则不作处理,代表沿用上一次的数据 if (j >= t[i]) dp[j] = Math.max(dp[j], (v[i] + dp[j - t[i]])); System.out.println(dp[n]); } }