华为OD机试算法题新老题库练习及源码
郑重声明: 1.博客中涉及题目为网上搜索而来,若侵权,请联系作者删除。 源码内容为个人原创,仅允许个人学习使用。
2.博客中涉及的源码非官方答案,不保证正确性。
3.切勿将博客内容用于官方考试,若应用于官方考试,后果自行承担,与原作者无关。
4.原作者保留知识版权,且有权向侵权者追究刑事责任
41.寻找相同子串
题目描述
输入描述
输出描述
源码和解析
解析:
示例代码:
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.找出经过特定点的路径长度
题目描述
输入描述
输出描述
用例
源码和解析
解析:
因此可以使用动态规划算法进行求解,不懂的可以到我的个人主页去算法专栏查找。
示例代码:
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.全量和已占用字符集
题目描述
输入描述
输出描述
用例
源码和解析
解析:
示例代码:
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.密钥格式化
题目描述
输入描述
输出描述
用例
源码和解析
解析:
示例代码:
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.数字字符串组合倒序
题目描述
输入描述
输出描述
用例
源码和解析
解析:
示例代码:
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-dent
String 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) + " ");
}
}
}
代码运行示意图: