前言综述：
本次od机试考试一共三道题，第一道题和第二道题各100分，第三道题200分。本次考试的答案都是2.5h考试的时候写的，代码写的也许并不好。在考试中还是蛮紧张的，所以写代码的时候注重的是完成考试，对于时间复杂度和空间复杂度的优化没有做过考虑。还是建议大家考试前多刷刷牛客网的试题，我大概刷了39道题，很多时候一道题我能思考三四天。同一类型题只要一次理解了，基本上就可以举一反三。如果你们看完这几道题的答案，你们会发现，1和3题解法用的是一类。希望这些能帮到后面有需要的兄弟，我是个小白，但是心里也想着做一些有反馈的事情给到大家。
目录
前言综述：
第一题
题目描述
输入描述：
输出描述：
第一题考试的源代码答案如下：
输入：
输出：
说明：
第二题
题目描述
输入描述：
输出描述：
第二题考试的源代码答案如下：
输入：
输出：
第三题
题目描述
输入描述：
输出描述：
第三题考试的源代码答案如下：
输入：
输出：
第一题
题目描述
疫情过后，希望小学终于又重新开学了，三年二班开学第一天的任务是将后面的黑板报重新制作。黑板上已经写了N个正整数，同学们需要给每个数分别上一种颜色。为了让黑板报即没关又有学习意义，老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。现在请你帮帮小朋友们，算算最少需要多少种颜色才能给这N个数进行上色。
输入描述：
第一行有一个正整数N，其中1<=N<=100。
第二行有N个int型数（保证输入数据在[1,100]范围中），表示黑板上各个正整数的值。
输出描述：
输入只有一个整数，为最少需要的颜色种数。
第一题考试的源代码答案如下：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = sc.nextInt();
}
// 先对数组进行排序，方便遍历
Arrays.sort(array);
// 记录最少需要的颜色数量
int count = 0;
int[] s = new int[n];
for (int i = 0; i < n; i++) {
if (s[i] > 0) {
continue;
} else {
for (int j = i; j < n; j++) {
if ((array[j] % array[i]) == 0) {
s[j]++;
}
}
count++;
}
}
System.out.println(count);
}
}
}
输入：
3
2 4 6
输出：
1
说明：
所有数都能被2整除
第二题
题目描述
有一个N个整数的数组，和一个长度为M的窗口，窗口从数组内的第一个数开始滑动直到窗口不能滑动为止，每次窗口滑动产生一个窗口和（窗口内所有数和和），求窗口滑动产生的所有窗口和的最大值。
输入描述：
第一行输入一个正整数N，表示整数个数。（0<N<100000）
第二行输入N个整数，整数的取值范围为[-100,100]。
第三行输入一个正整数M，M代表窗口大小，M<=100000，且M<=N。
输出描述：
窗口滑动产生的所有窗口和的最大值。
第二题考试的源代码答案如下：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = sc.nextInt();
}
// 生成一个新数组，记录窗口大小m。
int m = sc.nextInt();
int[] arrM = new int[n - m + 1];
for (int i = 0; i < n - m + 1; i++) {
arrM[i] = 0;
for (int j = 0; j < m; j++) {
arrM[i] += array[i + j];
}
// System.out.println(arrM[i]);
}
// 排序，取出最后一个最大的值
Arrays.sort(arrM);
System.out.println(arrM[n - m]);
}
}
}
输入：
6
10 20 30 15 23 12
3
输出：
68
第三题
题目描述
入职后，导师会请你吃饭，你选择了火锅。
火锅里会在不同时间下很多菜。
不同食材要煮不同的时间，才能变得刚好合适。你希望吃到最多的刚好合适的菜，但你的手速不够快，用m代表手速，每次下手捞菜后至少要过m庙才能在捞（每次只能捞一个）。
那么用最合理的策略，最多能吃到多少刚好合适的菜？
输入描述：
第一行两个整数n，m，其中n代表往锅里下的菜的个数，m代表手速。
接下来有n行，每行有两个数x，y代表第x秒下的菜过y秒才能变得刚好合适。
（1 < n, m < 1000）
（1 < x, y < 1000）
输出描述：
输出一个整数代表用最合理的策略，最多能吃到刚好合适的菜的数量
第三题考试的源代码答案如下：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt();
int m = sc.nextInt();
int[] x = new int[n];
int[] y = new int[n];
for (int i = 0; i < n; i++) {
x[i] = sc.nextInt();
y[i] = sc.nextInt();
}
// 设置一个数组，存放每道菜可以吃到的时间。
int[] arrTime = new int[n];
for (int i = 0; i < n; i++) {
arrTime[i] = x[i] + y[i];
}
// 对数组进行从小到大进行排序，这样便于后面比较计算
Arrays.sort(arrTime);
// 新建一个数组，和数组arrTime对应，用于记录每道菜是否可以吃到，可以吃到标记加1.
int[] arrCount = new int[n];
int next = 0;
arrCount[0] = 1;
for (int i = 1; i < n; i++) {
if (arrTime[i] >= (arrTime[next] + m)) {
arrCount[i] = 1;
next = i;
}
}
int count = 0;
for (int i = 0; i < n; i++) {
if (arrCount[i] > 0) {
count++;
}
}
// 遍历输出结果
// for (int a : arrCount) {
// System.out.println(a);
// }
System.out.println(count);
}
}
}
输入：
2 1
1 2
2 1
输出：
1
|