导语
每篇将有两道经典Java机试题，每道题后面均为大家附上代码，每一道题目力求：
- 能够在JDK11环境下编译
- 在Eclipse JavaIDE中运行通过
- 思路易想易懂易学
- 重点代码有注释
第019题 最大整数（难度：★★☆☆☆）
题目描述：
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数
输入描述：
第一行为一个数字n
接下来n行，每行一个数字，代表n组数字，
最后一行为一个数字m输出描述：
输出n行数字，每行一个数字，表示重新排列之后的最大整数
输入示例：
2
10,2
3,30,34,5,9
输出示例：
210
9534330
思路
这道题稍微理解一下题目意思，便可以知道，其实这道题考察的是对冒泡排序的熟知度；很明显，每个数字本身并没有拆分，那么可以将每个数字看成一个整体，其实这道题就是要对一组数字按照某种“大小”关系排序后，按照该定义“大小”关系的顺序进行冒泡排序，再按顺序将改组数字组合在一起，就是满足题目要求的“最大的数”
这里需要对“大小”关系进行定义和说明，是这道题稍微较绕的地方：
有a、b两个数，
第一种情况：
一般情况：比如是
123、245：
显然，这种情况下，245123是要比123245大，所以我们定义245比123大；这种情况，我们按位比较即可，相同位上，谁的数字大，那么这个数就大，即245的第一位2，比123的第一位1大，那么就认为245比123大
第二种情况：
比如是
34、345，
长的数字前面的某几位和短数字完全相同：我们将短数字位数设为n，这里n=2，那么关注点就放在了长数字的第n+1位；因为长数字前n位和短数字完全相同，；此时，我们将长的数字前n位去掉之后，剩余的数字再和短数字比较，那么又是第一种情况；因为一个递归搞定；记得注意递归出口，不能陷入死循环；
代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Demo {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//接受输入几组数据
int count = scanner.nextInt();
String[] inputStringArray = new String[count];
//跳转到下一行
scanner.nextLine();
//接受输入的数组
for (int i = 0; i < count; i++) {
inputStringArray[i] = scanner.nextLine();
}
scanner.close();
//保存排好序的数组
List<String[]> mResultIntegersList = new ArrayList<>();
for (int i = 0; i < inputStringArray.length; i++) {
String [] getStrings = sortAndGetReuslt(inputStringArray[i].split(","));
//保存当前这组的结果
mResultIntegersList.add(getStrings);
}
//打印最后结果
for (String[] resultArray: mResultIntegersList) {
String resultString = "";
//拼接结果
for (String stringNumber: resultArray) {
resultString = resultString + stringNumber;
}
System.out.println(resultString);
}
}
public static String[] sortAndGetReuslt(String[] arrayString) {
//采用冒泡排序，从大到小排列
for (int i = 0; i < arrayString.length - 1; i++) {
for (int j = 0; j < arrayString.length - i - 1; j++) {
if (compare(arrayString[j], arrayString[j + 1])) {
String tempString = arrayString[j];
arrayString[j] = arrayString[j + 1];
arrayString[j + 1] = tempString;
}
}
}
return arrayString;
}
//如果b > a,则返回true
public static boolean compare(String a, String b) {
int shortLength;
int longLength;
boolean isAShort = false;
if (a.length() >= b.length()) {
shortLength = b.length();
longLength = a.length();
} else {
shortLength = a.length();
longLength = b.length();
isAShort = true;
}
for(int i = 0; i < longLength; i++) {
//在a和b调用charAt都能取到值的情况下,b>a就返回true，否则返回false；
if ((i < shortLength) || (shortLength == longLength)) {
if (b.charAt(i) > a.charAt(i)) {
return true;
} else if(b.charAt(i) < a.charAt(i)) {
return false;
} else {
continue;
}
}
//只剩下34,345；34,343；34,344这种长的数字前面每一位都和短的数字相同的情况
//这种情况下345比34大，344比34大，而343比34小；
//就是比较多出来的那一位开始，再和短的数字，按照上述规则比较
if (isAShort) {
b = b.substring(shortLength, longLength);
} else {
a = a.substring(shortLength, longLength);
}
//开始递归
return compare(a, b);
}
return false;
}
}
运行结果
第020题 题目名称（难度：★☆☆☆☆）
题目描述：
将闭区间表示为[a,b]，a<=b，a和b为整数。输入多个闭区间，这多个闭区间覆盖的范围可能不连续，为了让覆盖的区间连续，请输出所有补齐区间。比如[1,4] [2,5] [8,9]：结果是[6,7]；
[-2,3] [1,4] [8,9]：结果是[5,7]；
[8,9] [2,3] [1,4] [6,9]：结果是[5,5]；
[1,4] [12,14] [2,5] [8,9]：结果是[6,7] [10,11]；
[1,4] [2,5]：结果是[]；输入示例：
3
1 4
2 5
8 9
——–
3
-2 3
1 4
8 9
———
4
8 9
2 3
1 4
6 9
———
4
1 4
12 14
2 5
8 9
———
2
1 4
2 5
输出示例：
[6,7]
[5,7]
[5,5]
[6,7] [10,11]
[]
输入说明：
第一行输入一个整数n，代表本组有n组区间；
之后n行，每一行输入两个数字代表区间
输出说明：
每个区间用[]括起来，区间中间用”,”分割，相邻区间不要有空格，区间不存在直接输出“[]”
思路
我们首先将给定的区间按照每组区间的左区间从小到大排序，比如：[1,4] [12,14] [2,5] [8,9]；排序后变成[1,4] [2,5] [8,9] [12,14]，然后每次拿前两个去处理，第一次：是[1,4] [2,5]，得出它俩的补齐区间，为空；然后将两个区间合并，合并的方式为取两段区间在数轴上的最后一段区间，那么[1,4]和[2,5]合并之后是[1,5]，（如果是[1,4] [6,7]合并，那么应该取数轴上最后一段区间，即[6,7]）;然后重复上述步骤，直至比较处理到最后两个区间。
下面的代码我没有用递归，直接简单粗暴的使用了列表的替换，伙伴们可以尝试写一个带有递归的程序；
代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Section> sectionList = new ArrayList<>();
List<Section> resultList = new ArrayList<>();
for(int i = 0; i < n; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
Section section = new Section(a, b);
sectionList.add(section);
}
scanner.close();
//按照左区间从小到大排序
Collections.sort(sectionList, new Comparator<Section>() {
@Override
public int compare(Section o1, Section o2) {
return o1.start - o2.start;
}
});
for (int i = 0; i < n - 1; i++) {
//每次拿两个区间
Section s1 = sectionList.get(i);
Section s2 = sectionList.get(i + 1);
//比较处理两个区间
Section resultSection = deal(s1, s2);
if (resultSection != null) {
//如果返回的区间不为null，则表明需要补充区间
resultList.add(resultSection);
}
//将拿去比较处理的两个区间合并
int replaceStart;
int replaceEnd;
if (s2.start <= s1.end + 1) {
replaceStart = s1.start;
replaceEnd = Math.max(s1.end, s2.end);
} else {
replaceStart = s2.start;
replaceEnd = s2.end;
}
//替换掉拿去比较的两个区间中的第二个区间
sectionList.set(i + 1, new Section(replaceStart, replaceEnd));
}
//输出结果
//如果结果列表为空，则是直接输出“[]”
if (resultList.isEmpty()) {
System.out.println("[]");
} else {
//否则依次输出
for (Section section: resultList) {
System.out.print("[" + section.start + "," + section.end + "]");
}
}
}
//返回当前两组区间之间，需要补齐的区间，没有则返回null
public static Section deal(Section s1, Section s2) {
if (s2.start > s1.end + 1) {
int strat = s1.end + 1;
int end = s2.start - 1;
if (strat <= end) {
return new Section(strat, end);
}
}
return null;
}
}
//数据结构
class Section {
int start;
int end;
public Section(int start, int end) {
this.start = start;
this.end = end;
}
}
运行结果
以上是本次两道Java机试题
如有不足，欢迎批评指正
欢迎阅读上一篇：
Java 100道典型机试笔试题（09）
欢迎阅读下一篇：
Java 100道典型机试笔试题（11）
作者：小南瓜
日期：2021年8月23日23:34