asp网站源码安装流程,joomla网站建设,公司网站规划案例,wordpress 后台显示id目录 【案例1】
【题目描述】 【思路解析】
【代码实现】
【案例2】
【题目描述】
【思路解析 平凡解技巧 从业务中分析终止条件 重点】
【代码实现】
【案例3】
【题目描述】
【思路解析】
【案例4】
【题目描述】 【思路解析】
【代码实现】
【动态规划代码】…目录 【案例1】
【题目描述】 【思路解析】
【代码实现】
【案例2】
【题目描述】
【思路解析 平凡解技巧 从业务中分析终止条件 重点】
【代码实现】
【案例3】
【题目描述】
【思路解析】
【案例4】
【题目描述】 【思路解析】
【代码实现】
【动态规划代码】
【案例5】
【题目描述】【很重要】【编辑距离问题】
【思路解析】 【代码实现】
【案例6】
【题目描述】
【思路解析】
【代码实现】 【案例1】
【题目描述】 【思路解析】
因为它数字的范围只能为1 - n然后数组范围0 - n-1所以说如果没有缺失值的话每个i位置应该放i 1所以我们直接对每个数组完成这个操作让每个i位置尽可能放i1如果有些位置不是i1则这些位置就是缺失值遍历打印即可 。
【代码实现】
/*** 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位置上尽可能方i1public 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; i2) {if (charArray[i] ! 0 charArray[i] ! 1){return false;}}for (int i 1; i charArray.length; i2) {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个字符 分为以下情况 1str1使用i-1个字符完成str2的j-1个字符再将str1第i个字符替换为str2第j个字符如果相等就可以剩去替换的过程 2str1使用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个字符// 分为以下情况// 1str1使用i-1个字符完成str2的j-1个字符再将str1第i个字符替换为str2第j个字符如果相等就可以剩去替换的过程// 2str1使用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码值最大为256int[] 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 ;}
}
