左神算法之中级提升班（9）

目录

【案例1】

【题目描述】

 【思路解析】

【代码实现】

【案例2】

【题目描述】

【思路解析  平凡解技巧  从业务中分析终止条件 重点】

【代码实现】

【案例3】

【题目描述】

【思路解析】

【案例4】

【题目描述】

 【思路解析】

【代码实现】

【动态规划代码】

【案例5】

【题目描述】【很重要】【编辑距离问题】

【思路解析】

 【代码实现】

【案例6】

【题目描述】

【思路解析】

【代码实现】

---

【案例1】

【题目描述】

 【思路解析】

因为它数字的范围只能为1 - n，然后数组范围0 - n-1，所以说如果没有缺失值的话，每个i位置应该放i + 1，所以我们直接对每个数组完成这个操作，让每个i位置尽可能放i+1，如果有些位置不是i+1，则这些位置就是缺失值，遍历打印即可 。

【代码实现】

/*** @ProjectName: study3* @FileName: Ex1* @author:HWJ* @Data: 2023/7/31 9:48*/
public class Ex1 {public static void main(String[] args) {int[] arr = {1, 3, 4, 3};printNumberNoInArray(arr);}public static void printNumberNoInArray(int[] arr){if (arr == null || arr.length == 0){return;}for (int i : arr) {modify(i, arr);}for (int i = 0; i < arr.length; i++) {if (arr[i] != i + 1){System.out.println(i + 1);}}}// 这里实现让每个i位置上尽可能方i+1public static void modify(int value, int[] arr){while(arr[value - 1] != value){int tmp = arr[value - 1];arr[value - 1] = value;value = tmp;}}}

【案例2】

【题目描述】

【思路解析  平凡解技巧  从业务中分析终止条件 重点】

这道题容易想到使用暴力递归来解决，但限制条件只有一个cur == end，不足以作为basecase，需要补充限制条件，因为end和start均为偶数，且end > > start ，所以有一个只用点赞到达end的平凡解，如果高于这个花费的解，直接不考虑。

从业务中分析，因为他有一个私聊是可以-2，然后在递归中，它有一个分支可能一直在-2，导致无法到达end，所以限制条件增加一个为start已经小于0停止。

从业务中分析，他有一个*2的方式，但是总有一次*2可以使他第一次比b大，此时如果再次*2就会花费更多的私聊钱，再分析再次*2会大于2*b，所以增加一个限制条件start不能大于 2 * b；

【代码实现】

/*** @ProjectName: study3* @FileName: Ex2* @author:HWJ* @Data: 2023/7/31 10:39*/
public class Ex2 {public static void main(String[] args) {System.out.println(getMinMoney(3, 100, 1, 2, 6));}public static int getMinMoney(int x, int y, int z, int start, int end) {int limitCoin = ((end - start) / 2) * x;int limitAim = end * 2;return process(x, y, z, start, end, 0, limitCoin, limitAim);}// preMoney代表当前已经花了多少钱// limitCoin代表平凡解所需要花费的钱币// limitAim 代表当前start的上界public static int process(int x, int y, int z, int start, int end, int preMoney, int limitCoin, int limitAim) {if (start == end) {return preMoney;}if (start < 0) {return Integer.MAX_VALUE;}if (preMoney > limitCoin) {return Integer.MAX_VALUE;}if (start > limitAim) {return Integer.MAX_VALUE;}int p1 = process(x, y, z, start + 2, end, preMoney + x, limitCoin, limitAim);int p2 = process(x, y, z, start * 2, end, preMoney + y, limitCoin, limitAim);int p3 = process(x, y, z, start - 2, end, preMoney + z, limitCoin, limitAim);return Math.min(p1, Math.min(p2, p3));}}

【案例3】

【题目描述】

【思路解析】

可以通过后面关联矩阵生成一个图，然后从末尾H开始做一个图的宽度优先遍历，每个节点实现一个哈希表，然后哈希表里面维护当花费天数增加时，收益一定增加，然后每个节点就得到了它独自的哈希表，然后最后将所有哈希表汇总，这样就得到了所有完成方式。然后最后根据限制天数来查表即可。最后这里也可以用大根堆来做，只有小于限制天数的值才加入，然后里面根据收益大小来维护大根堆。两个方式都差不多。

【案例4】

【题目描述】

 【思路解析】

因为& | ^ 这几个运算都是二元运算，则表达式长度应该为奇数且大于1，满足奇数位上只有0或1，偶数位上只有&、|或^运算符，如果不满足此规则的字符串直接返回0.

然后对于组合就有如下定义，对于每一个确定的表达式组合应有确定的括号，对于不同的括号填充，则认为不同的组合方式。括号可以认为是进行运算时的顺序规定，不一定真的要在字符串上填充括号。

【代码实现】

import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex4* @author:HWJ* @Data: 2023/9/11 14:21*/
public class Ex4 {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str = input.next();boolean desire = input.nextBoolean();if (!check(str)){System.out.println(0);}else {char[] charArray = str.toCharArray();int ans = count(charArray, 0, charArray.length  - 1, desire);System.out.println(ans);}}public static boolean check(String str){// 因为 | & ^ 运算都是二元运算，所以有效字符串长度应该为奇数，并且奇数位是 1 或者 0， 偶数位是 二元运算符if (str.length() % 2 == 0 || str.length() == 1){return false;}char[] charArray = str.toCharArray();for (int i = 0; i < charArray.length; i+=2) {if (charArray[i] != '0' && charArray[i] != '1'){return false;}}for (int i = 1; i < charArray.length; i+=2) {if (charArray[i] != '|' && charArray[i] != '&' && charArray[i] != '^'){return false;}}return true;}public static int count(char[] chars, int L, int R, boolean desire) {if (L == R) {if (chars[L] == '0') {return desire ? 0 : 1;} else {return desire ? 1 : 0;}}int res = 0;for (int i = L + 1; i < R; i += 2) {if (desire) {switch (chars[i]) {case '&':res += count(chars, L, i - 1, true) * count(chars, i + 1, R, true);break;case '|':res += count(chars, L, i - 1, true) * count(chars, i + 1, R, true);res += count(chars, L, i - 1, true) * count(chars, i + 1, R, false);res += count(chars, L, i - 1, false) * count(chars, i + 1, R, true);break;case '^':res += count(chars, L, i - 1, true) * count(chars, i + 1, R, false);res += count(chars, L, i - 1, false) * count(chars, i + 1, R, true);break;}} else {switch (chars[i]) {case '|':res += count(chars, L, i - 1, false) * count(chars, i + 1, R, false);break;case '&':res += count(chars, L, i - 1, false) * count(chars, i + 1, R, false);res += count(chars, L, i - 1, true) * count(chars, i + 1, R, false);res += count(chars, L, i - 1, false) * count(chars, i + 1, R, true);break;case '^':res += count(chars, L, i - 1, true) * count(chars, i + 1, R, true);res += count(chars, L, i - 1, false) * count(chars, i + 1, R, false);break;}}}return res;}
}

【动态规划代码】

import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex4_2* @author:HWJ* @Data: 2023/9/11 15:10*/
public class Ex4_2 {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str = input.next();boolean desire = input.nextBoolean();int ans = dp(str, desire);System.out.println(ans);}public static boolean check(String str) {// 因为 | & ^ 运算都是二元运算，所以有效字符串长度应该为奇数，并且奇数位是 1 或者 0， 偶数位是 二元运算符if (str.length() % 2 == 0 || str.length() == 1) {return false;}char[] charArray = str.toCharArray();for (int i = 0; i < charArray.length; i += 2) {if (charArray[i] != '0' && charArray[i] != '1') {return false;}}for (int i = 1; i < charArray.length; i += 2) {if (charArray[i] != '|' && charArray[i] != '&' && charArray[i] != '^') {return false;}}return true;}public static int dp(String str, boolean desire) {if (!check(str)) {return 0;}int N = str.length();char[] charArray = str.toCharArray();int[][] tMap = new int[N][N];int[][] fMap = new int[N][N];for (int i = 0; i < N; i += 2) {tMap[i][i] = charArray[i] == '1' ? 1 : 0;fMap[i][i] = charArray[i] == '1' ? 0 : 1;}for (int row = N - 3; row >= 0; row -= 2) {for (int col = row + 2; col < N; col += 2) {for (int i = row + 1; i < N; i += 2) {switch (charArray[i]) {case '&':tMap[row][col] += tMap[row][i - 1] * tMap[i + 1][col];break;case '|':tMap[row][col] += tMap[row][i - 1] * tMap[i + 1][col];tMap[row][col] += tMap[row][i - 1] * fMap[i + 1][col];tMap[row][col] += fMap[row][i - 1] * tMap[i + 1][col];break;case '^':tMap[row][col] += tMap[row][i - 1] * fMap[i + 1][col];tMap[row][col] += fMap[row][i - 1] * tMap[i + 1][col];break;}switch (charArray[i]) {case '&':fMap[row][col] += fMap[row][i - 1] * tMap[i + 1][col];fMap[row][col] += fMap[row][i - 1] * fMap[i + 1][col];fMap[row][col] += tMap[row][i - 1] * fMap[i + 1][col];break;case '|':fMap[row][col] += fMap[row][i - 1] * fMap[i + 1][col];break;case '^':fMap[row][col] += tMap[row][i - 1] * tMap[i + 1][col];fMap[row][col] += fMap[row][i - 1] * fMap[i + 1][col];break;}}}}if (desire) {return tMap[0][N - 1];} else {return fMap[0][N - 1];}}
}

【案例5】

【题目描述】【很重要】【编辑距离问题】

【思路解析】

这里可以使用dp动态规划，来进行寻找最小代价。

这里的i和j表示str1使用i个字符，完成str2的j个字符
分为以下情况
（1）str1使用i-1个字符完成str2的j-1个字符，再将str1第i个字符替换为str2第j个字符，如果相等就可以剩去替换的过程
（2）str1使用i-1个字符完成str2的j个字符，再将str1第i个字符删去
  (3) str1使用i个字符完成str2的j-1个字符，再添加str2的第j个字符
则str1使用i个字符，完成str2的j个字符的最小使用，则为上面的最小值

 【代码实现】

import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex5* @author:HWJ* @Data: 2023/9/11 15:01*/
public class Ex5 {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str1 = input.next();String str2 = input.next();int add = input.nextInt();int del = input.nextInt();int replace = input.nextInt();int ans = dp(str1, str2, add, del, replace);System.out.println(ans);}public static int dp(String str1, String str2, int add, int del, int replace){int N1 = str1.length();int N2 = str2.length();int[][] map = new int[N1 + 1][N2 + 1];for (int i = 1; i <= N2; i++) {map[0][i] = i * add;}for (int i = 1; i <= N1; i++) {map[i][0] = i * del;}for (int i = 1; i <= N1; i++) {for (int j = 1; j <= N2; j++) {// 这里的i和j表示str1使用i个字符，完成str2的j个字符// 分为以下情况// （1）str1使用i-1个字符完成str2的j-1个字符，再将str1第i个字符替换为str2第j个字符，如果相等就可以剩去替换的过程// （2）str1使用i-1个字符完成str2的j个字符，再将str1第i个字符删去//  (3) str1使用i个字符完成str2的j-1个字符，再添加str2的第j个字符// 则str1使用i个字符，完成str2的j个字符的最小使用，则为上面的最小值map[i][j] = map[i - 1][j] + del;map[i][j] = Math.min(map[i][j], map[i][j - 1] + add);map[i][j] = Math.min(map[i][j], map[i][j - 1] + str1.charAt(i - 1) == str2.charAt(j - 1) ? 0 : replace);}}return map[N1][N2];}}

【案例6】

【题目描述】

【思路解析】

建立一个每个字符的词频表，然后从当前位置开始遍历每一个字符，经历一个字符就词频减1，当出现某个字符词频为0时，就在所有经历过的字符中，选择一个字典序最小的字符，然后删去除了他其他相同的字符，并删去在他之前的字符。直到所有字符的词频都为1.

【代码实现】

import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex6* @author:HWJ* @Data: 2023/9/11 16:14*/
public class Ex6 {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str = input.next();String s = delete(str);System.out.println(s);}public static String delete(String str){if (str.length() <= 1){return str;}// 这里假设字符的ascii码值最大为256；int[] map = new int[256];int max = 1;for (int i = 0; i < str.length(); i++) {map[str.charAt(i)] += 1;max = Math.max(max, map[str.charAt(i)]); }if(max == 1){return str;}else {for (int i = 0; i < str.length(); i++) {map[str.charAt(i)] -= 1;if (map[str.charAt(i)] == 0){int min = Integer.MAX_VALUE;int index = -1;for (int j = 0; j <= i; j++) {min = Math.min(min, str.charAt(j));index = min == str.charAt(j) ? j : index;}return String.valueOf(str.charAt(index)) +delete(str.substring(index + 1).replace(String.valueOf(str.charAt(index)), ""));}}}return "";}
}