最右10.22笔试
题目1
import java.util.Random;
import java.util.Scanner;
/**
* @author wanna
* @version v1.0
* @Package com.wanna.main45
* @date 2021/10/19 8:19 下午
*/
public class Main {
/*
@ 最右1
找到一个数组中第一个缺少的正数
比如arr=[-3,2,3]，缺少的第一个正数为1
比如arr[-3,1,3]，缺少的第一个正数是2
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = scanner.nextInt();
}
quickSort(arr); // 先使用快排按照从小到大去进行排序
// mergeSort(arr);
// 如果最后一个元素都<=0，那么直接输出1
if (arr[N - 1] <= 0) {
System.out.println(1);
return;
}
for (int i = 0; i < arr.length; i++) {
// 如果arr[i]<=0 并且arr[i+1]<=0，那么continue，还不是我们应该讨论的
if (i + 1 < arr.length && arr[i] <= 0 && arr[i + 1] <= 0) {
continue;
}
// 如果arr[i]<=0并且arr[i+1]>0，也就是先出现了负数(含0)，然后出现了正数
// 需要讨论arr[i+1]是否为1，如果为1，continue，不是1直接输出1，因为一定缺少1
if (i + 1 < arr.length && arr[i] <= 0 && arr[i + 1] > 0) {
// 如果arr[i+1]是1的话，那么continue
// 比如-2 1这种，因为下一个是1，不会缺少1，那么continue
// 如果arr[i+1]不是1，比如-2 2，因为下一个是2，所以必然缺少1，进行输出
if (arr[i + 1] == 1) {
continue;
}
// 如果这个元素不是1，那么输出1
System.out.println(1);
return;
}
// 如果arr[i]>0并且arr[i+1]>0，也就是两个正数的情况
// 1.如果arr[i]==arr[i+1]，那么它之间并不缺少元素，continue
// 2.如果arr[i]+1==arr[i+1]，之间也是不缺少元素，continue
if (i + 1 < arr.length && arr[i] > 0 && arr[i + 1] > 0) {
// 如果两者相等的话，那么continue
// 如果当前元素+1=下一个元素，那么continue，因为之间不可能缺了元素
if (arr[i] == arr[i + 1] || arr[i] + 1 == arr[i + 1]) {
continue;
}
System.out.println(arr[i] + 1);
return;
}
}
// 有可能一个数组中所有元素都为正数，有可能全部都为负数
// 如果全部为负数，在上面已经处理过了，这里只需要处理全是正数并且不还不符合缺少了数的情况，需要输出arr[N-1]+1
System.out.println(arr[N - 1] + 1);
}
public static void mergeSort(int[] arr) {
mSort(arr, 0, arr.length - 1, new int[arr.length]);
}
public static void mSort(int[] arr, int left, int right, int[] temp) {
if (right <= left) {
return;
}
int mid = left + ((right - left) >> 1);
mSort(arr, left, mid, temp);
mSort(arr, mid + 1, right, temp);
merge(arr, left, mid + 1, right, temp);
}
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int L = left, R = mid, index = L;
for (; L < mid && R <= right; ) {
temp[index++] = arr[L] > arr[R] ? arr[R++] : arr[L++];
}
for (; L < mid; ) {
temp[index++] = arr[L++];
}
for (; R <= right; ) {
temp[index++] = arr[R++];
}
System.arraycopy(temp, left, arr, left, right - left + 1);
}
public static void quickSort(int[] arr) {
qSort(arr, 0, arr.length - 1);
}
public static void qSort(int[] arr, int left, int right) {
if (right <= left) {
return;
}
int random = left + new Random().nextInt(right - left + 1);
swap(arr, random, right);
int[] partition = partition(arr, left, right);
qSort(arr, left, partition[0] - 1);
qSort(arr, partition[1] + 1, right);
}
public static int[] partition(int[] arr, int left, int right) {
int pivlot = arr[right];
int less = left - 1;
int more = right;
for (; left < more; ) {
if (arr[left] < pivlot) {
swap(arr, left++, ++less);
} else if (arr[left] > pivlot) {
swap(arr, left, --more);
} else {
left++;
}
}
swap(arr, right, more);
return new int[]{less + 1, more};
}
public static void swap(int[] arr, int i, int j) {
if (arr[i] == arr[j]) {
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
题目2
import java.util.Scanner;
/**
* @author wanna
* @version v1.0
* @Package com.wanna.main46
* @date 2021/10/19 8:20 下午
*/
public class Main {
/*
@最右2 AC 80% TLE
一共有N层
第一行会输入N，代表学生的层数
第二行会输入每一层的学生数量，比如[1,2,3]代表第一层有1个学生，第二层有2个学生，第三层有3个学生
第二行之后会输入N行
每一行的第一个数代表的是第i层的人向上走一层的体力消耗，每一行的第二个数代表第i层的人向下走一层的体力消耗
如果走向上走j层/向下走j层，那么就得j*对应的体力消耗
要选定一个k，代表最终要开会的层数，要求的是所有学生到k的体力消耗总数最小
最终要输出的就是最小的消耗体力的数量
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt(); // 行数，也就是对应的行数
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = scanner.nextInt(); // 每一层的学生的个数
}
int[][] consume = new int[N][2];
for (int i = 0; i < N; i++) {
consume[i][0] = scanner.nextInt(); // 第i层的人向上走的一层单位体力消耗
consume[i][1] = scanner.nextInt(); // 第i层的人向下走的一层单位体力消耗
}
process(consume, arr, N);
}
// 可以向上走，可以向下走，求所有学生的最小的体力消耗
// AC 80% 然后TLE(时间超出)了...整体时间复杂度在O(n^2)
public static void process(int[][] consume, int[] arr, int N) {
int min = Integer.MAX_VALUE; // 初始化一个min代表最终需要输出的最小体力消耗
// 如果开会选在第i层的话，最后的总消耗是多少呢？
for (int i = 0; i < N; i++) {
int currentConsume = 0; // currentConsume代表选在i层开会最终的体力消耗
// 在i层以上的学生走到第i层的最终总消耗
for (int j = i + 1; j < N; j++) {
// j-i获取的是第j层楼到第i层楼差了几层楼
// consume[j][1]也就是1个人向下走1层需要进行的消耗
// arr[j]代表的是第j层的学生消耗体力的数量
currentConsume += (j - i) * consume[j][1] * arr[j];
}
// 在i层以下的学生走到第i层的最终总消耗，分析过程和在i层以上的学生走到第i层的最终总消耗完全类似
for (int j = i - 1; j >= 0; j--) {
currentConsume += (i - j) * consume[j][0] * arr[j];
}
// 如果选用当前i层的最终消耗比以前的消耗低了，那么就得更新最终的结果
min = Math.min(currentConsume, min);
}
System.out.println(min);
}
}
查看8道真题和解析