华为OD机试（41-60）老题库解析&Java源码系列连载ing_华为java机试题库及答案

---

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

---

41.寻找相同子串

题目描述

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

输入描述

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

输出描述

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

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

源码和解析
解析：

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

示例代码：

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);
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

代码运行示意图：

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

题目描述

无

输入描述

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

输出描述

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

用例

源码和解析
解析：

这个题重在理解，可以使用动态规划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);
		}

	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

代码运行示意图：

43.全量和已占用字符集

题目描述

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

输入描述

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

输出描述

• 输出可用字符集
• 不同的输出字符集之间用回车换行
• 注意 输出的字符顺序要跟输入的一致，如下面用例不能输出b:3,a:2,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(",");
			}
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

代码运行示意图：

44.密钥格式化

题目描述

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

输入描述

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

输出描述

转换后的字符串

用例

源码和解析
解析：

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

示例代码：

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));
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码运行示意图：

45.数字字符串组合倒序

题目描述

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

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

输入描述

无

输出描述

无

用例

源码和解析
解析：

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

示例代码：

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) + " ");
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

代码运行示意图：

46.查找接口成功率最优时间段

题目描述

服务之间交换的接口成功率作为服务调用关键质量特性，某个时间段内的接口失败率使用一个数组表示，数组中每个元素都是单位时间内失败率数值，数组中的数值为0~100的整数，给定一个数值(minAverageLost)表示某个时间段内平均失败率容忍值，即平均失败率小于等于minAverageLost，找出数组中最长时间段，如果未找到则直接返回NULL。

输入描述

输入有两行内容，第一行为{minAverageLost}，第二行为{数组}，数组元素通过空格(” “)分隔，minAverageLost及数组中元素取值范围为0~100的整数，数组元素的个数不会超过100个。

输出描述

找出平均值小于等于minAverageLost的最长时间段，输出数组下标对，格式{beginIndex}-{endIndx}(下标从0开始)，

如果同时存在多个最长时间段，则输出多个下标对且下标对之间使用空格(” “)拼接，多个下标对按下标从小到大排序。

用例

解析

这个题逻辑层面来看 比较简单。但是编程时发现还是蛮痛苦的。

1. 最小值和输入数组的初始化
2. 找出这个数组中 满足连续的 几个数的平均数小于 等于最小值的 下标范围
   例如：
   输入
   3
   1 2 3 5 8 1 1 1
   首先肯定 能找到的 0-3 因为 1+2+3+ 5=11 再除以4 其值小于3 的
   然后就是 后面的 三个1 即 5-7
   因此可以输出结果 0-3 5-7 但是真实结果真是这样的吗？ 这个8就一定会被舍弃掉吗？其实这个答案是有问题的。如果你把所有内容全部求平均 其结果为 22/8 是小于3的 所以这个结果应该为0-7 而并非 0-3 5-7
3. 可以考虑使用递归的方式来做，不断的移动数组的游标，尽可能找出以该游标开始的最大的范围的结束索引。下次递归时，就在该区间范围外进行递归即可。

示例代码

import java.util.Scanner;

public class Test1 {
	public static boolean flag = false;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int minAvg = Integer.parseInt(sc.nextLine());
		String input = sc.nextLine();
		String inputArr[] = input.split(" ");
		int arr[] = new int[inputArr.length];
		for (int i = 0; i < inputArr.length; i++) {
			arr[i] = Integer.parseInt(inputArr[i]);
		}
		dfs(0, arr, minAvg);
		if (!flag) {
			System.out.println("NULL");
		}
	}

	// 计算 某个索引 开始 一直到数组最后的 最大可能值 1
	public static void dfs(int left, int arr[], int minAvg) {
		if (left == arr.length)
			return;
		int count = 0;
		double sum = 0.0;
		int tempLeft = left;
		int objRight = left;// 目标最值右
		for (; tempLeft < arr.length; tempLeft++) {
			sum += arr[tempLeft];
			count++;
			if (sum / count <= minAvg) {
				objRight = tempLeft;
			}
		}
		if (objRight > left) {
			flag = true;
			System.out.print(left + "-" + objRight + " ");
			left = objRight; // 找到一个 区间满足 那下次从这个区间的下一个开始往下找 不然 找出的 可能为该区间的子区间
		}
		dfs(left + 1, arr, minAvg);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

代码运行结果

47.在字符串中找出连续最长的数字串(含“±”号)

输入描述

请在一个字符串中找出连续最长的数字串，并返回这个数字串。

如果存在长度相同的连续数字串，返回最后一个。

如果没有符合条件的字符串，返回空字符串””。

注意：

• 数字串可以由数字”0-9″、小数点”.”、正负号”±”组成，长度包括组成数字串的所有符号。
• “.”、“±”仅能出现一次，”.”的两边必须是数字，”±”仅能出现在开头且其后必须要有数字。
• 长度不定，可能含有空格。

输入描述

一串字符

输出描述

连续最长的数字串（合法）
否则 输出 “”

用例

解析

1. 使用正则表达式匹配出数字即可， 这种方式比直接拆分数组简单很多
   这里面有个非常重要的点
   1.1 匹配模式 可以写为 ([±]{0,1}\d+\.{0,1}\d+)
   1.2 当输入的内容为 1234567890abcd9.+12345.678.999999ed-205 时 匹配结果为+12345.678 长度是10位 但是经过核对发现 678.999999 也是10位 且为合法数字。如果只是简单的使用正则去找的话，估计像上述这个字符串匹配不出来。
   1.3 类似于1.2中的这种字符 我逆向进行了匹配来提高匹配情况。我也相信，即使这样做也可能并不能完全找到所有的正确答案。

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class T47 {
	public static void main(String[] args) {
		String input = "1234567890abcd9.+12345.678.999999ed-205";
		String regex = "([+-]{0,1}\\d+\\.{0,1}\\d+)";// ()括号是匹配表达式 []匹配之内的一个即可
		String res = calcResult(regex, input, true);
		String reverseRes = calcResult(regex, new StringBuilder(input).reverse().toString(), false);
		reverseRes = new StringBuilder(reverseRes).reverse().toString();
//		System.out.println(res);
//		System.out.println(reverseRes);
		if (input.indexOf(res) > input.indexOf(reverseRes)) {
			System.out.println(res);
		} else {
			System.out.println(reverseRes);
		}
	}

	/**
	 * 
	 * @param regex 匹配模式
	 * @param input 匹配字符
	 * @param flag  true 正向 false 反向
	 * @return
	 */
	public static String calcResult(String regex, String input, boolean flag) {
		Pattern p = Pattern.compile(regex);
		Matcher matcher = p.matcher(input);
		String res = "";
		while (matcher.find()) {
			if (flag && matcher.group().length() >= res.length()) {
				res = matcher.group(); // 正向取后
			} else if ((!flag) && matcher.group().length() > res.length()) {
				res = matcher.group(); // 反向取前
			}
		}
		return res;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

代码运行示意图

48. 找终点

题目描述

给定一个正整数数组，设为nums，最大为100个成员，求从第一个成员开始，正好走到数组最后一个成员，所使用的最少步骤数。

要求：

1. 第一步必须从第一元素开始，且1<=第一步的步长<len/2;（len为数组的长度，需要自行解析）。
2. 从第二步开始，只能以所在成员的数字走相应的步数，不能多也不能少, 如果目标不可达返回-1，只输出最少的步骤数量。
3. 只能向数组的尾部走，不能往回走。

输入描述

由正整数组成的数组，以空格分隔，数组长度小于100，请自行解析数据数量。

输出描述

正整数，表示最少的步数，如果不存在输出-1

用例

源码和解析
解析：

1. 理解题目
2. 通过不断地切换第一步的步数，来找到步数最少且刚好达到末尾

示例代码：

import java.util.ArrayList;
import java.util.List;

public class T48 {
	public static boolean flag;// 是否存在 默认为false

	public static void main(String[] args) {
		String input = "1 2 3 7 1 5 9 3 2 1 2"; // "1 2 3 7 1 5 9 3 2 1";//
												// "7 5 9 4 2 6 8 3 5 4 3 9";
		List<Integer> nums = new ArrayList<Integer>();
		for (String str : input.split(" ")) {
			nums.add(Integer.parseInt(str));
		}
		System.out.println(nums);
		int res = dfs(nums);
		if (flag)
			System.out.println("结果为：" + res);
		if (!flag)
			System.out.println("结果为：-1");
	}

	public static int dfs(List<Integer> nums) {
		int objCount = nums.size();// 步数数量
		int stype = 0;// 第几步
		if (nums.get(0) <= 0) {// 第一个数 可能 负数或0 那么步子无法迈出去
			return -1;
		}
		for (stype = 1; stype < nums.size() / 2; stype++) {
			boolean f = false;// 第一步位stype 看下是否能移动到nums的最后一个成员
			int tempStype = stype;
			int index = 0;// 移动的索引
			int count = 0;// 一开始就第一步 后面每挪动一次就加1
			int tempCount = 0;
			while (tempStype < nums.size()) {
				index += tempStype;
				// System.out.println("index:"+index+" tempStype:"+tempStype);;
				count++;
				if (index == nums.size() - 1) {
					tempCount = count;
					// System.out.println("找到了,第一步为" + stype+"步数为"+count);
					f = true;
				} else if (index < nums.size()) {
					tempStype = nums.get(index);
				} else {
					// 越界了 没找到
					break;
				}
			}
			if (f) {
				flag = true;
				if (objCount > tempCount) {
					objCount = tempCount;
				}
			}

		}
		return objCount;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

代码运行示意图

49.执行时长

题目描述

为了充分发挥GPU算力，需要尽可能多的将任务交给GPU执行，现在有一个任务数组，数组元素表示在这1秒内新增的任务个数且每秒都有新增任务。

假设GPU最多一次执行n个任务，一次执行耗时1秒，在保证GPU不空闲情况下，最少需要多长时间执行完成。

输入描述

• 第一个参数为GPU一次最多执行的任务个数，取值范围[1, 10000]
• 第二个参数为任务数组长度，取值范围[1, 10000]
• 第三个参数为任务数组，数字范围[1, 10000]

输出描述

• 执行完所有任务最少需要多少秒。

用例

解析

这个题目重在理解题，理解后可以使用递归进行问题解决
例如下图 可以增强对这个题的执行过程理解

示例代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class T49 {
	static List<Integer> taskList = new ArrayList<Integer>();
	static int count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int gpu = Integer.parseInt(sc.nextLine());
		int taskNum = Integer.parseInt(sc.nextLine());
		String strTask = sc.nextLine();
		for (String item : strTask.split(" ")) {
			taskList.add(Integer.parseInt(item));
		}
		deal(gpu, 0);
		System.out.println(count);
	}

	public static void deal(int gpu, int toDeal) {
		if (taskList.size() == 0 && toDeal == 0) {
			return;
		}
		if (taskList.size() == 0) {
			count++;
			if (gpu < toDeal) {
				toDeal = toDeal - gpu;
				deal(gpu, toDeal);
			}
		} else if (toDeal > 0) {
			count++;
			toDeal = taskList.get(0) + toDeal - gpu;
			if (toDeal < 0) {
				toDeal = 0;
			}
			taskList.remove(0);
			deal(gpu, toDeal);
		} else if (toDeal == 0) {
			toDeal = taskList.get(0) - gpu < 0 ? 0 : taskList.get(0) - gpu;
			count++;
			taskList.remove(0);
			deal(gpu, toDeal);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

运行示例

50.用户调度问题

题目描述

在通信系统中，一个常见的问题是对用户进行不同策略的调度，会得到不同的系统消耗和性能。

假设当前有n个待串行调度用户，每个用户可以使用A/B/C三种不同的调度策略，不同的策略会消耗不同的系统资源。请你根据如下规则进行用户调度，并返回总的消耗资源数。

规则：

1.    相邻的用户不能使用相同的调度策略，例如，第1个用户使用了A策略，则第2个用户只能使用B或者C策略。

2.    对单个用户而言，不同的调度策略对系统资源的消耗可以归一化后抽象为数值。例如，某用户分别使用A/B/C策略的系统消耗分别为15/8/17。

3.    每个用户依次选择当前所能选择的对系统资源消耗最少的策略（局部最优），如果有多个满足要求的策略，选最后一个。

输入描述

第一行表示用户个数n

接下来每一行表示一个用户分别使用三个策略的系统消耗resA resB resC

输出描述

最优策略组合下的总的系统资源消耗数

用例

题目解析

这个题目有的人使用迭代去做，迭代的思想相对来说简单些。每次取出一个资源，并把索引记录下来。往下迭代产生结果。
这个题为在解决的时候使用了动态规划算法。不熟悉的可以参考我的另一篇博客。
【算法】使用数位算法生成0至某个数之间的整数（for循环之外的另一种实现方式，蛮长见识的）
针对上述用例，用图可以展示为

其中黄线区域所连接的为不可达，因为题目要求相邻的用户不能使用相同的调度策略
最后计算每个叶子节点路径和 并求出最小值即可。

示例代码java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class T50 {
	static int num[] = null;
	static int minResouce = Integer.MAX_VALUE;// 资源最小

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int userNo = Integer.parseInt(sc.nextLine());
		List<List<Integer>> resourceList = new ArrayList<List<Integer>>();
		for (int i = 0; i < userNo; i++) {
			List<Integer> resList = new ArrayList<Integer>();
			Arrays.stream(sc.nextLine().split(" ")).forEach(s -> resList.add(Integer.parseInt(s)));
			;
			resourceList.add(resList);
		}
		num = new int[userNo];
		System.out.println(resourceList);
		dfs(0, resourceList, -1);
		System.out.println(minResouce);
	}

	/**
	 * 
	 * @param p            取第p个子列表
	 * @param resourceList 所有的资源List
	 * @param p1           上一个列表中取了哪一个索引
	 */
	public static void dfs(int p, List<List<Integer>> resourceList, int p1) {
		if (p >= resourceList.size()) {
			// 计算
			int sum = 0;
			for (int r : num) {
				sum += r;
				System.out.print(r + " ");
			}
			if (sum < minResouce) {
				minResouce = sum;
			}
			System.out.println();
			return;
		}
		List<Integer> itemList = resourceList.get(p);
		for (int i = 0; i < itemList.size(); i++) {
			if (i == p1)
				continue;
			num[p] = itemList.get(i);
			dfs(p + 1, resourceList, i); // i不能写成p 会产生错乱
		}

	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

代码运行示意图

51.查找众数及中位数

题目描述

众数是指一组数据中出现次数量多的那个数，众数可以是多个。

中位数是指把一组数据从小到大排列，最中间的那个数，如果这组数据的个数是奇数，那最中间那个就是中位数，如果这组数据的个数为偶数，那就把中间的两个数之和除以2，所得的结果就是中位数。

查找整型数组中元素的众数并组成一个新的数组，求新数组的中位数。

输入描述

输入一个一维整型数组，数组大小取值范围 0<N<1000，数组中每个元素取值范围 0<E<1000

输出描述

输出众数组成的新数组的中位数

用例

题目解析

这个题属于逻辑题，先将输入的字符串解析成数组，然后转换到map中去，顺便把出现最多的次数记录下来。

遍历map将次数等于最多次数的数装入一个List

对List进行排序，排序后根据列表长度来确认中位数

示例代码Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * 求众数排列后的中位数 1.求众数 2.求中位数 10 11 21 19 21 17 21 16 21 18 15 2 1 5 4 3 3 9 2 7 4
 * 6 2 15 4 2 4 5 1 5 3 5 2 5 5 7 6 7 3 7 11 7 55 7 9 98 9 17 9 15 9 9 1 39
 */
public class T51 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		int max[] = new int[1];
		Arrays.stream(sc.nextLine().split(" ")).forEach(s -> {
			int key = Integer.parseInt(s);
			map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);
			if (max[0] < map.get(key)) {
				max[0] = map.get(key).intValue();// 求出出现的最大次数
			}
		});
		System.out.println(map);
		
		// 过滤
		Set<Integer> keySet = map.keySet();
		List<Integer> numList = new ArrayList<Integer>();
		Iterator<Integer> it = keySet.iterator();
		while (it.hasNext()) {
			Integer key = it.next();
			if (map.get(key) == max[0]) {
				for (int i = 0; i < map.get(key); i++) {
					numList.add(key);
				}
			}
		}
		System.out.println(numList);

		// 求中位数
		numList.sort(new Comparator<Integer>() {
			@Override
			public int compare(Integer arg0, Integer arg1) {
				if (arg0 < arg1)
					return -1;
				if (arg0 > arg1)
					return 1;
				return 0;
			}
		});
		int middle = numList.size() % 2 == 1 ? numList.get(numList.size() / 2)
				: (numList.get(numList.size() / 2) + numList.get(numList.size() / 2 - 1)) / 2;
		System.out.println(middle);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

代码运行示意图

52.最大N个数与最小N个数的和

题目描述

给定一个数组，编写一个函数来计算它的最大N个数与最小N个数的和。你需要对数组进行去重。

说明：

• 数组中数字范围[0, 1000]
• 最大N个数与最小N个数不能有重叠，如有重叠，输入非法返回-1
• 输入非法返回-1

输入描述

• 第一行输入M， M标识数组大小
• 第二行输入M个数，标识数组内容
• 第三行输入N，N表达需要计算的最大、最小N个数

输出描述

输出最大N个数与最小N个数的和

用例

解析

典型的逻辑处理题型，需要掌握字符串拆分，排序等知识点。

示例代码Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

//5
//95 88 83 64 100
//2
public class T52 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<Integer> numList = new ArrayList<>();
		int count = Integer.parseInt(sc.nextLine());
		Arrays.stream(sc.nextLine().split(" ")).forEach(s -> {
			if (!numList.contains(Integer.parseInt(s)))
				numList.add(Integer.parseInt(s));
		});

		numList.sort(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if (o1 > o2)
					return 1;
				if (o1 < o2)
					return -1;
				return 0;
			}
		});
		int num = Integer.parseInt(sc.nextLine());
		List<Integer> num1 = new ArrayList<>();
		num1 = numList.subList(0, num);
		System.out.println(num1);
		boolean flag = false;
		List<Integer> num2 = new ArrayList<>();
		num2 = numList.subList(numList.size() - num, numList.size());
		System.out.println(num2);
		for (int i = 0; i < num1.size(); i++) {
			if (num2.contains(num1.get(i))) {
				System.out.println("-1");
				flag = true;
				break;
			}
		}

		if (!flag) {
			int sum[] = new int[1];
			num1.stream().forEach(s -> {
				sum[0] += s;
			});
			num2.stream().forEach(s -> {
				sum[0] += s;
			});
			System.out.println(sum[0]);
		}

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

代码运行示例

53.最长连续子序列

题目描述

有N个正整数组成的一个序列。给定整数sum，求长度最长的连续子序列，使他们的和等于sum，返回此子序列的长度，

如果没有满足要求的序列，返回-1。

---

输入描述

第一行输入是：N个正整数组成的一个序列

第二行输入是：给定整数sum

---

输出描述

最长的连续子序列的长度

备注

• 输入序列仅由数字和英文逗号构成，数字之间采用英文逗号分隔
• 序列长度：1 <= N <= 200
• 输入序列不考虑异常情况

用例

题目解析

1. 使用双指针找到对相邻的数进行求和。若和正确，那么就判断长度是否比前面出现的长度都大，若大就进行记录。
2. 若和大于，那么就证明该区间内不存在目标序列。左指针右移，临和减掉移出的左侧的那个。
3. 若和小于，就证明该区间还可以往右扩充，右指针右移，临和加上移入的那一个。这样就避免了在内部在使用循环计算区间和了。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class T53 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.nextLine();
		int sum = Integer.parseInt(sc.nextLine());
		List<Integer> numList = new ArrayList<>();
		Arrays.stream(input.split(",")).forEach(s -> {
			numList.add(Integer.parseInt(s));
		});
		int left = 0;
		int right = 0;
		int tempSum = numList.get(left);// 临时的区间和
		int len = -1;
		while (right < numList.size()) {
			if (tempSum < sum) {
				right++;
				if (right == numList.size())
					break;// 超出了
				tempSum += numList.get(right);
				// System.out.println(tempSum);
			} else if (tempSum > sum) {
				tempSum -= numList.get(left);
				left++;
			} else {
				// System.out.println(right - left + "-");
				// System.out.println(right + "-----" + left);
				if (len < right - left) {
					len = right - left + 1;
				}
				tempSum -= numList.get(left);
				left++;

			}
		}
		System.out.println(len);
	}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

代码运行示意图

54.数组去重和排序

题目描述

给定一个乱序的数组，删除所有的重复元素，使得每个元素只出现一次，并且按照出现的次数从高到低进行排序，相同出现次数按照第一次出现顺序进行先后排序。

---

输入描述

一个数组

---

输出描述

去重排序后的数组

用例

---

题目解析

使用List装入Map对象，每个map存储一个数字为键，值为键对应的出现的次数。最后再对List根据排序规则排序就可

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class T54 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.nextLine();
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		List<Integer> keyList = new ArrayList<>();// 记录顺序
		Arrays.stream(input.split(",")).forEach(s -> {
			Integer key = Integer.parseInt(s);
			map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);
			if (!keyList.contains(key)) {
				keyList.add(key);
			}
		});
		// System.out.println(map);
		// System.out.println(keyList);
		List<Map<Integer, Integer>> mapList = new ArrayList<>();
		for (Integer key : keyList) {
			Map<Integer, Integer> m = new HashMap<>();
			m.put(key, map.get(key));
			mapList.add(m);
		}
		mapList.sort(new Comparator<Map<Integer, Integer>>() {
			@Override
			public int compare(Map<Integer, Integer> m1, Map<Integer, Integer> m2) {
				Integer v1 = m1.values().iterator().next();
				Integer v2 = m2.values().iterator().next();
				if (v1 > v2)
					return -1;
				if (v2 < v1)
					return 1;
				if (v2 == v1) {
					// 取key顺序来判断
					Integer k1 = m1.keySet().iterator().next();
					Integer k2 = m2.keySet().iterator().next();
					if (k1 > k2)
						return 1;
					if (k1 < k2)
						return -1;
				}
				return 0;
			}
		});
		mapList.forEach(m -> {
			System.out.print(m.keySet().iterator().next() + ",");
		});
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

---

代码运行示意图

55.数组拼接

题目描述

现在有多组整数数组，需要将它们合并成一个新的数组。

合并规则，从每个数组里按顺序取出固定长度的内容合并到新的数组中，取完的内容会删除掉，如果该行不足固定长度或者已经为空，则直接取出剩余部分的内容放到新的数组中，继续下一行。

输入描述

第一行是每次读取的固定长度，0 < 长度 < 10

第二行是整数数组的数目，0 < 数目 < 1000

第3-n行是需要合并的数组，不同的数组用回车换行分隔，数组内部用逗号分隔，最大不超过100个元素。

输出描述

输出一个新的数组，用逗号分隔。

用例

---

题目解析

1. 使用List 内部装入一个List类型的集合。这样就可以将所有数据装入一个List中，其结构体现为[ [],[],[],[],[] ]
2. 遍历外层的List，每次取出从一个集合中取出对应的n个数据，如果该子列表的数据被取完，那么就将其从外层List中移出。
3. 直到所有子列表都移出完成，即外层List的长度为0，那么就结束程序。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

//3
//2
//2,5,6,7,9,5,7
//1,7,4,3,4
public class T55 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = Integer.parseInt(sc.nextLine());
		int line = Integer.parseInt(sc.nextLine());
		List<List<Integer>> numList = new ArrayList<List<Integer>>();
		for (int i = 0; i < line; i++) {
			List<Integer> list = new ArrayList<Integer>();
			Arrays.stream(sc.nextLine().split(",")).forEach(n -> {
				list.add(Integer.parseInt(n));
			});
			numList.add(list);
		}
		List<Integer> resList = new ArrayList<Integer>();
		while (numList.size() > 0) {
			for (int i = 0; i < numList.size(); i++) {
				List<Integer> itemList = numList.get(i);
				int count = 0;
				while (count < num) {
					resList.add(itemList.get(0));
					itemList.remove(0);
					count++;
					if (itemList.size() == 0)
						break;
				}
				if (itemList.isEmpty()) {
					numList.remove(itemList);
					i--;// 注意 移除后集合的大小会少一个，因此i--，再i++之后，正好是移除后的下一个
				}
			}
		}
		System.out.println(resList);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

代码运行示意图

56.整数对最小和

题目描述

给定两个整数数组array1、array2，数组元素按升序排列。

假设从array1、array2中分别取出一个元素可构成一对元素，现在需要取出k对元素，

并对取出的所有元素求和，计算和的最小值。

注意：

两对元素如果对应于array1、array2中的两个下标均相同，则视为同一对元素。

输入描述

输入两行数组array1、array2，每行首个数字为数组大小size(0 < size <= 100);

0 < array1[i] <= 1000

0 < array2[i] <= 1000

接下来一行为正整数k

0 < k <= array1.size() * array2.size()

输出描述

满足要求的最小和

用例

题目解析

具体思路看代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class T56 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n1 = sc.nextInt();
		int nums1[] = new int[n1];
		for (int i = 0; i < n1; i++)
			nums1[i] = sc.nextInt();

		int n2 = sc.nextInt();
		int nums2[] = new int[n2];
		for (int i = 0; i < n2; i++)
			nums2[i] = sc.nextInt();
		int count = sc.nextInt();
		List<Integer> pointSumList = new ArrayList<Integer>();
		for (int s1 : nums1) {
			for (int s2 : nums2) {
				pointSumList.add(s1 + s2);
			}
		}
		pointSumList.sort((a, b) -> a - b);
		System.out.println(pointSumList);
		int sum = 0;
		while (count > 0) {
			count--;
			sum += pointSumList.get(count);
		}
		System.out.println(sum);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

代码运行示例

57.乱序整数序列两数之和绝对值最小

题目描述

给定一个随机的整数（可能存在正整数和负整数）数组 nums，请你在该数组中找出两个数，其和的绝对值(|nums[x]+nums[y]|)为最小值，并返回这个两个数（按从小到大返回）以及绝对值。

每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

输入描述

一个通过空格分割的有序整数序列字符串，最多1000个整数，且整数数值范围是 [-65535, 65535]。

输出描述

两数之和绝对值最小值

用例

解析

1. 使用for循环暴力组合破解
2. 将数分组 正数一组，负数一组 分组后排序
   2.1. 若全正，则找最小的两个 若全负 则找最大的两个
   2.2. 若正负结合，则合并两个列表 使用双指针进行求解

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
//-1 -3 7 5 11 15
public class T57 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<Integer> positiveNums = new ArrayList<Integer>();
		List<Integer> negativeNums = new ArrayList<Integer>();
		Arrays.stream(sc.nextLine().split(" ")).forEach(item -> {
			int num = Integer.parseInt(item);
			if (num < 0) {
				negativeNums.add(num);
			} else {
				positiveNums.add(num);
			}
		});
		positiveNums.sort((a, b) -> a - b);// 升序
		negativeNums.sort((a, b) -> b - a);// 降序
		//System.out.println(positiveNums);
		//System.out.println(negativeNums);
		if(positiveNums.size()==0) {
			//纯负数
			System.out.println(negativeNums.get(1)+" "+negativeNums.get(0)+" "+Math.abs(negativeNums.get(1)+negativeNums.get(0)));
		}
		if(negativeNums.size()==0) {
			System.out.println(positiveNums.get(0)+" "+positiveNums.get(1)+" "+Math.abs(positiveNums.get(0)+positiveNums.get(1)));
		}
		if(negativeNums.size()>0&&positiveNums.size()>0) {
			//组合 就得组合了 说不定负数那边前两个 正数那边前两个 亦或者 一正一负
			int min=Integer.MAX_VALUE;
			int minNumber=negativeNums.get(negativeNums.size()-1);
			int maxNumber=positiveNums.get(positiveNums.size()-1);
			if(negativeNums.size()>=2&&negativeNums.get(0)+negativeNums.get(1)<min) {
				min=Math.abs(negativeNums.get(0)+negativeNums.get(1));
				minNumber=negativeNums.get(1);
				maxNumber=negativeNums.get(0);
			}
			if(positiveNums.size()>=2&&positiveNums.get(0)+positiveNums.get(1)<min) {
				min=Math.abs(positiveNums.get(0)+positiveNums.get(1));
				minNumber=positiveNums.get(0);
				maxNumber=positiveNums.get(1);
			}
			//双指针
			int left=0;
			int right=1;
			List<Integer> numsList=new ArrayList<Integer>();
			numsList.addAll(negativeNums);
			numsList.addAll(positiveNums);
			while(left<numsList.size()-1) {
				right=left+1;
				while(right<numsList.size()) {
					if(min>Math.abs(numsList.get(left)+numsList.get(right))) {
						min=Math.abs(numsList.get(left)+numsList.get(right));
						minNumber=numsList.get(left);
						maxNumber=numsList.get(right);
					}
					//System.out.println(numsList.get(left)+"-"+numsList.get(right)+"-");
					right++;
				}
				left++;
			}
			System.out.println(minNumber+" "+maxNumber+" "+ min);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

58.检查是否存在满足条件的数字组合

题目描述

给定一个正整数数组，检查数组中是否存在满足规则的数字组合

规则：A = B + 2C

输入描述

第一行输出数组的元素个数。

接下来一行输出所有数组元素，用空格隔开。

输出描述

如果存在满足要求的数，在同一行里依次输出规则里A/B/C的取值，用空格隔开。

如果不存在，输出0。

备注

1. 数组长度在3-100之间。
2. 数组成员为0-65535，数组成员可以重复，但每个成员只能在结果算式中使用一次。如：数组成员为[0, 0, 1, 5]，0出现2次是允许的，但结果0 = 0 + 2 * 0是不允许的，因为算式中使用了3个0。
3. 用例保证每组数字里最多只有一组符合要求的解。

用例

题目解析

1. 需要明确的是每个数字出现的次数不大于数组中出现的次数，也就意味着每个索引只能使用一次。A=B+2C 这个A、B、C其实是可以重复的 如数组[0,0,0,1]中 是允许出现ABC分别为0，且满足条件的。

2. 使用三重for循环 强行破解

3. 使用数位规划算法来解题

for循环强行破解

import java.util.Scanner;

public class Y1 {
	static int rawNums[]=null;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int num=Integer.parseInt(sc.nextLine());
		rawNums=new int[num];
		for(int i=0;i<num;i++) {
			rawNums[i]=sc.nextInt();
		}
		for(int i=0;i<num;i++) {
			for(int j=0;j<num;j++) {
				for(int k=0;k<num;k++) {
					if(i==j||i==k||k==j)continue;
					if(rawNums[i]==rawNums[j]+2*rawNums[k]) {
						System.out.println(rawNums[i]+" "+rawNums[j]+" "+rawNums[k]);
						System.exit(0);
					}
					if(rawNums[i]==rawNums[k]+2*rawNums[j]) {
						System.out.println(rawNums[i]+" "+rawNums[k]+" "+rawNums[j]);
						System.exit(0);
					}
				}
			}
		}
		System.out.println(0);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

数位DP算法进行求解

import java.util.Scanner;

public class T58 {
	static int rawNums[] = null;
	static int tempNum[] = new int[3];// 存储取出的ABC

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = Integer.parseInt(sc.nextLine());
		rawNums = new int[num];
		for (int i = 0; i < num; i++) {
			rawNums[i] = sc.nextInt();
		}
		dp(0, -1, -1);
		System.out.println(0);
	}

	/**
	 * 
	 * @param p       取到哪一层
	 * @param first   第一层取了哪个索引
	 * @param sencond 第二层取了哪个索引
	 */
	public static void dp(int p, int first, int sencond) {
		if (p == 3) {
			if (tempNum[0] == tempNum[1] + tempNum[2] * 2) {
				System.out.println(tempNum[0] + " " + tempNum[1] + " " + tempNum[2]);
				System.exit(0);
			}
			return;
		}
		for (int i = 0; i < rawNums.length; i++) {
			if (i != first && i != sencond) {
				tempNum[p] = rawNums[i];
				if (p == 0) {
					dp(p + 1, i, sencond);
				}
				if (p == 1) {
					dp(p + 1, first, i);
				}
				if (p == 2) {
					dp(p + 1, first, sencond);
				}
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

代码运行示意图

59.ABR 车路协同场景

题目描述

数轴×有两个点的序列 A={A1， A2, …, Am}和 B={B1, B2, ..., Bn}， Ai 和 Bj 均为正整数， A、 B 已经从小到大排好序， A、 B 均肯定不为空，

给定一个距离 R（正整数），列出同时满足如下条件的所有（Ai， Bj）数对

条件：

1. Ai <= Bj
2. Ai,Bj 距离小于等于 R，但如果 Ai 找不到 R 范围内的 Bj，则列出距它最近的 1 个 Bj，当然此种情况仍然要满足 1，

但如果仍然找不到，就丢弃 Ai。

原型：

车路协同场景，一条路上发生了有很多事件（ A），要通过很多路测设备（ B）广播给路上的车，需要给每个事件找到一个合适的路测设备去发送广播消息。

输入描述

按照人易读的格式输入一行数据，参见输入样例，其中“ ABR={， }”中的每个字符都是关键分割符，输入中无空格，其他均为任意正整数，

输入 A 和 B 已经排好序， A 和 B 的大小不超过 50，正整数范围不会超过 65535。

输出描述

（ Ai,Bj）数对序列，排列顺序满足序列中前面的 Ax<=后面的 Ay，前面的 Bx<=后面的 By，

因为输入 A 和 B 已经排好序，所以实际上输出结果不用特意排序，排序不是考察点。

用例

解析
把题目读懂就完事了，主要是对于没有b-a=r时，要取一个比之前取过的更大一点的b…逻辑不是很绕,具体看代码

示例代码

public class T59 {
	public static void main(String[] args) {
		int[] arrA = { 1, 3, 5 };
		int[] arrB = { 2, 4, 7 };
		int r = 1;
		for (int a : arrA) {
			int tempB = -1;// 上次取了哪个b
			int near = -1;// 距离a近的
			boolean flag = false;// 是否找到一个b和a匹配
			for (int b : arrB) {
				if (b - a == r && b > tempB) {
					System.out.print("(" + a + "," + b + ")");
					tempB = b;
					flag = true;
					break;
				}
				if (b - a > r) {
					near = b;
					break;
				}
			}
			if (flag == false && near != -1) {
				// 没找到 那么就找一个离a 较近的 若找不到就放弃
				System.out.print("(" + a + "," + near + ")");
			}
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

代码运行截图

60.AI面板识别

题目描述

AI识别到面板上有N（1 ≤ N ≤ 100）个指示灯，灯大小一样，任意两个之间无重叠。

由于AI识别误差，每次别到的指示灯位置可能有差异，以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1，右下角x2,y2)，

请输出先行后列排序的指示灯的编号，排序规则：

1. 每次在尚未排序的灯中挑选最高的灯作为的基准灯，
2. 找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 ≤ 灯高度的一半）。

---

输入描述

第一行为N，表示灯的个数
接下来N行，每行为1个灯的坐标信息，格式为：

编号 x1 y1 2 y2

• 编号全局唯一
• 1 ≤ 编号 ≤ 100
• 0 ≤ x1 < x2 ≤ 1000
• 0  ≤  y1 < y2 ≤ 1000

---

输出描述

排序后的编号列表，编号之间以空格分隔

用例

解析

1. 这个题用例中说明图例2和3编号写反了，注意理解题目的意思
2. 给出的坐标是左上角和右下角，且排序是找所有未排序的点的最高点作为基准点，然后找到基准点那一行进行排序，例如说明中的图（编号1和3位是1行 2是1行 4和5 是一行 ）
3. 请注意排序规则
   每次在尚未排序的灯中挑选最高的灯作为的基准灯，
   找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 ≤ 灯高度的一半）

若按照排序规则来说的画，1,2，3 属于同一行 且排序时，先行后列，则 最终排序结果为1,2，3 而并非1,3，2

4. 这个题可以使用List来进行灯坐标存储，然后先找出未排序的最大的，然后是找出和最大的灯处于同一行的，按x1坐标进行排序。谁小谁排在前。每次找完一行，就把找到的数据移出。

5. 例如输入
   5
   1 0 0 2 2
   2 3 0 5 3
   3 6 0 8 2
   4 0 6 2 7
   5 4 6 6 7
   图形展示如下：
   
   那么输出id顺序应该为 1 2 3 4 5 其中 1 2 3 为一行

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class T60 {
	static class Light {
		int id, x1, y1, x2, y2;

		public Light(int id, int x1, int y1, int x2, int y2) {
			super();
			this.id = id;
			this.x1 = x1;
			this.y1 = y1;
			this.x2 = x2;
			this.y2 = y2;
		}
	}

	static List<Light> lightList = new ArrayList<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = Integer.parseInt(sc.nextLine());
		for (int i = 0; i < num; i++) {
			String line = sc.nextLine();
			String numStrArr[] = line.split(" ");
			int id = Integer.parseInt(numStrArr[0]);
			int x1 = Integer.parseInt(numStrArr[1]);
			int y1 = Integer.parseInt(numStrArr[2]);
			int x2 = Integer.parseInt(numStrArr[3]);
			int y2 = Integer.parseInt(numStrArr[4]);
			Light light = new Light(id, x1, y1, x2, y2);
			lightList.add(light);
		}
		while (lightList.size() > 0) {
			Light maxLight = getMaxLight();
			System.out.print(maxLight.id + " ");
			List<Light> sameLineLights = getSameLineLights(maxLight);
			sameLineLights.sort(new Comparator<Light>() {
				@Override
				public int compare(Light l1, Light l2) {
					if (l1.x1 < l2.x1)
						return -1;
					if (l1.x1 > l2.x1)
						return 1;
					return 0;
				}
			});
			for (Light l : sameLineLights) {
				System.out.print(l.id + " ");
			}
		}
	}

	// 找出未排序的最大的那个
	public static Light getMaxLight() {
		Light light = null;
		for (Light lt : lightList) {
			if (light == null) {
				light = lt;
			}
			if (lt.y1 < light.y1) {
				light = lt;
			}
			if (lt.y1 == light.y1) {
				// 高度一样 那么以左侧为主
				if (lt.x1 < light.x1) {
					light = lt;
				}
			}
		}
		lightList.remove(light);
		return light;
	}

	// 找出和最大的灯处于同一行的
	public static List<Light> getSameLineLights(Light light) {
		List<Light> lights = new ArrayList<>();
		for (Light lt : lightList) {
			if (lt.y1 == light.y1 || (light.y1 - lt.y1) >= (light.y1 - light.y2) / 2) {
				lights.add(lt);
			}
		}
		lightList.removeAll(lights);
		return lights;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

代码运行示例