网站网页是怎么做的网上推广方式
目录
【案例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 "";}
}