---

郑重声明： 1.博客中涉及题目为网上搜索而来，若侵权，请联系作者删除。 源码内容为个人原创，仅允许个人学习使用。
2.博客中涉及的源码非官方答案，不保证正确性。
3.切勿将博客内容用于官方考试，若应用于官方考试，后果自行承担，与原作者无关。
4.原作者保留知识版权，且有权向侵权者追究刑事责任

---

41.寻找相同子串

题目描述

给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。
变换规则：交换字符串中任意两个不同位置的字符。

输入描述

一串小写字母组成的字符串s

输出描述

按照要求进行变换得到的最小字符串。

• s是都是小写字符组成
• 1 ≤ s.length ≤ 1000

输入	abcdef
输出	abcdef
说明	abcdef已经是最小字符串，不需要交换。

输入	bcdefa
输出	acdefb
说明	a和b进行位置交换，可以得到最小字符串

源码和解析
解析：

先排序，找出排序后顺序交换位置距离最远的那个进行交换即可

示例代码：

import java.util.Arrays;
import java.util.Scanner;/*** 一次变换要想得到最小 那么交换时，肯定是将最小的字符往前提 如果那个最小字符有多个，则肯定是提取最后一个* 比如 bacada===> aacadb=> 最后一个a和首字符交换 *  解决思路 先排序 查找从前往后字符串变化的地方*/
public class T41 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);String rawWord=sc.nextLine();char[] cArr=rawWord.toCharArray();Arrays.sort(cArr);boolean flag=false;for(int i=0;i<cArr.length;i++) {if(cArr[i]!=rawWord.charAt(i)) {char obj=cArr[i];//要替换的目标字符int lastIndex=rawWord.lastIndexOf(obj); //要替换的目标字符 最后的索引StringBuilder sb=new StringBuilder(rawWord);char rawObj=sb.charAt(i);//目标字符提前的索引对应字符 目标字符要和谁换sb.setCharAt(i, obj);sb.setCharAt(lastIndex, rawObj);System.out.println(sb.toString());flag=true;break; }}if(flag==false){System.out.println(rawWord);}}
}

代码运行示意图：

42.找出经过特定点的路径长度

题目描述

无

输入描述

输入一个字符串，都是以大写字母组成，每个相邻的距离是 1，
第二行输入一个字符串，表示必过的点。
说明每个点可过多次。

输出描述

经过这些必过点的最小距离是多少

用例

输入	ANTSEDXQOKPUVGIFWHJLYMCRZB ABC
输出	28
说明	无

源码和解析
解析：

这个题重在理解，可以使用动态规划DP算法进行求解。
在用例
ANTSEDXQOKPUVGIFWHJLYMCRZB
ABC
中 A->0 B-25 C-22 那么从起点字符串开始的起点A -> 目标点A距离为0 A到B距离为25-0=25 B-C= |25-22|=3 那么ABC的最小距离为28
倘若字符串中包含多个A或者多个B的情况
那么{A:[ 1,3,5…],B:[4,6,8],C:[12,13]}
==》ABC 为三个列表的有序组合 [1,4,12] 距离为 （1-0）+（4-1）+（12-4）
==》ABBC 则为四个列表的有序组合

因此可以使用动态规划算法进行求解，不懂的可以到我的个人主页去算法专栏查找。
示例代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class T42 {static int num[] = null;// 记录 每次dfs产生的 临时数据static String objInput = "";static int min = -1;// 最小路径距离static Map<Character, List<Integer>> map = null;public static void main(String[] args) {String input = "ANTBSEDXQOKPUAVGIFWHJLYMCRZB";objInput = "ABCB";map = new HashMap<Character, List<Integer>>();for (int i = 0; i < objInput.length(); i++) {if (!map.containsKey(objInput.charAt(i))) {map.put(objInput.charAt(i), new ArrayList<Integer>());}for (int j = 0; j < input.length(); j++) {if (input.charAt(j) == objInput.charAt(i)) {if (map.get(input.charAt(j)).contains(j))continue;map.get(input.charAt(j)).add(j);}}}System.out.println(map);num = new int[objInput.length()];dfs(0);System.out.println(min);}/*** * @param p*            位置序号 从0开始 通过该序号 可以取到键及其对应的列表*/public static void dfs(int p) {if (p >= objInput.length()) {int tempDistance = num[0];//// System.out.print(num[0]+" ");for (int i = 1; i < num.length; i++) {tempDistance += Math.abs(num[i] - num[i - 1]);// System.out.print(num[i]+" ");}// System.out.println();if (min == -1) {min = tempDistance;}if (tempDistance < min) {min = tempDistance;}return;}for (int i = 0; p < num.length&& i < map.get(objInput.charAt(p)).size(); i++) {num[p] = map.get(objInput.charAt(p)).get(i);dfs(p + 1);}}}

代码运行示意图：

43.全量和已占用字符集

题目描述

给定两个字符集合，一个是全量字符集，一个是已占用字符集，已占用字符集中的字符不能再使用。

输入描述

1. 输入一个字符串 一定包含@，@前为全量字符集 @后的为已占用字符集
2. 已占用字符集中的字符一定是全量字符集中的字符
3. 字符集中的字符跟字符之间使用英文逗号隔开
4. 每个字符都表示为字符+数字的形式用英文冒号分隔，比如a:1标识一个a字符
5. 字符只考虑英文字母，区分大小写
6. 数字只考虑正整型 不超过100
7. 如果一个字符都没被占用 @标识仍存在，例如 a:3,b:5,c:2@

输出描述

• 输出可用字符集
• 不同的输出字符集之间用回车换行
• 注意 输出的字符顺序要跟输入的一致，如下面用例不能输出b:3,a:2,c:2
• 如果某个字符已全部占用 则不需要再输出

用例

输入	a:3,b:5,c:2@a:1,b:2
输出	a:2,b:3,c:2
说明	全量字符集为三个a，5个b，2个c 已占用字符集为1个a，2个b 由于已占用字符不能再使用 因此剩余可用字符为2个a，3个b，2个c 因此输出a:2,b:3,c:2

源码和解析
解析：

题目过于简单，考查基础知识。字符串操作，Map集合的使用

示例代码：

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;public class T43 {public static void main(String[] args) {String input = "a:3,b:5,c:2,d:10@a:1,b:2,d:3";String allKeyValue[] = input.split("@")[0].split(",");String usedKeyValue[] = input.split("@")[1].split(",");Map<String, Integer> map = new HashMap<String, Integer>();String lastKey = "";for (String keyValue : allKeyValue) {String key = keyValue.split(":")[0];int value = Integer.parseInt(keyValue.split(":")[1]);map.put(key, value);lastKey = key;}for (String keyValue : usedKeyValue) {String key = keyValue.split(":")[0];int value = Integer.parseInt(keyValue.split(":")[1]);map.put(key, map.get(key) - value);}for (Entry<String, Integer> entry : map.entrySet()) {System.out.print(entry.getKey() + ":" + entry.getValue());if (!entry.getKey().equals(lastKey)) {System.out.print(",");}}}
}

代码运行示意图：

44.密钥格式化

题目描述

给定一个非空字符串 S，其被 N 个’-‘分隔成 N+1 的子串，给定正整数 K，要求除第一个子串外，其余的串每 K 个用’-‘分隔，并将小写字母转换为大写。

输入描述

正整数 K 和‘-’分割的字符串，如：
2
25G3C-abc-d

输出描述

转换后的字符串

用例

输入	4 5F3Z-2e-9-w
输出	5F3Z-2E9W
说明	字符串 S 被分成了两个部分，每部分 4 个字符； 注意，两个额外的破折号需要删掉。

输入	2 2-5g-3-J
输出	2-5G-3J
说明	字符串 S 被分成了 3 个部分，按照前面的规则描述，第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。

源码和解析
解析：

重在考查字符串操作基础知识

示例代码：

import java.util.Scanner;public class T44 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = Integer.parseInt(scanner.nextLine());String input = scanner.nextLine();String[] wordArr = input.split("-");StringBuilder sb = new StringBuilder();for (int i = 1; i < wordArr.length; i++) {sb.append(wordArr[i].toUpperCase());}System.out.print(wordArr[0]);for (int i = 0; i < sb.length(); i++) {if (i % num == 0)System.out.print("-");System.out.print(sb.charAt(i));}}
}

代码运行示意图：

45.数字字符串组合倒序

题目描述

对数字，字符，数字串，字符串，以及数字与字符串组合进行倒序排列。
字符范围：由 a 到 z， A 到 Z，
数字范围：由 0 到 9
符号的定义：

• “-”作为连接符使用时作为字符串的一部分，例如“20-years”作为一个整体字符串呈现；
• 连续出现 2 个 “-” 及以上时视为字符串间隔符，如“out--standing”中的”–“视为间隔符，是 2 个独立整体字符串”out”和”standing”；
• 除了 1，2 里面定义的字符以外其他的所有字符，都是非法字符，作为字符串的间隔符处理，倒序后间隔符作为空格处理；
• 要求倒排后的单词间隔符以一个空格表示；如果有多个间隔符时，倒排转换后也只允许出现一个字格间隔符；

输入描述

无

输出描述

无

用例

输入	I am an 20-years out--standing @ * -stu- dent
输出	dent stu standing out 20-years an am I
说明	无

源码和解析
解析：

正则匹配 字符串替换 字符串拆分

示例代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class T45 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();// I am an 20-years out--standing @ * -stu-dentString str1 = "[^0-9a-zA-Z-]";// 非法字符 //空格 @ *String[] items1 = input.split(str1);List<String> wordList = new ArrayList<String>();for (String w : items1) {if (w.replaceAll(" ", "").length() == 0) {continue;}if (w.indexOf("--") != -1) {w = w.replaceAll("--", "&");// 后面用&符号统一分割一次}if (w.indexOf("-") != -1) {// 解决头尾出现的问题 即可if (w.charAt(0) == '-' || w.endsWith("-")) {w = w.replaceAll("-", "&").replace(" ", "");}}for (String item : w.split("&")) {if (item.replaceAll(" ", "").length() == 0) {continue;}wordList.add(item);}}for (int i = wordList.size() - 1; i >= 0; i--) {System.out.print(wordList.get(i) + " ");}}
}

代码运行示意图：