阿里3.19笔试 Java版本
菜鸡来攒人品~
第一题:
输入n个数字->a[n]
如果数组中a[i]不是平方，可以通过不限次+1或-1操作使其变为某个数的平方
若要将a[n]中一半的数字变成某数的平方，最少需要多少次操作
大顶堆
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main m = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
PriorityQueue<Integer> queue = new PriorityQueue<>((num1, num2) -> num2 - num1);
int len = a.length / 2 + a.length % 2;
int sum = 0;
for (int i = 0; i < a.length; i++) {
int opNum = m.opNum(a[i]);
sum += opNum;
queue.add(opNum);
if (queue.size() == len) {
sum -= queue.poll();
}
}
System.out.println(sum);
}
private int opNum(int num) {
int sqrt = (int) Math.sqrt(num);
if (Math.pow(sqrt, 2) == num) {
return 0;
}
return (int) Math.min(num - Math.pow(sqrt, 2), Math.pow(sqrt + 1, 2));
}
} 第二题:
输入2n个数
前n个记为int a[n]
后n个记为int b[n]
要求找到三个数i,j,k使得b[i] + b[j] + b[k]最小
其中0<i<j<k<n，a[i] <= a[j] <= a[k]
回溯
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int min = -1;
static int sum = 0;
static int[] mark = new int[3];
public static void main(String[] args) {
Main m = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
b[i] = sc.nextInt();
}
m.backtrace(a, b, 0, 0);
System.out.println(min);
}
void backtrace(int[] a, int[] b, int level, int index) {
if (level == 3) {
if (min == -1) min = sum;
else min = Math.min(min, sum);
return;
}
for (int i = index; i < a.length; i++) {
if (validate(level, a[i])) {
mark[level] = a[i];
sum += b[i];
backtrace(a, b, level + 1, i + 1);
sum -= b[i];
}
}
}
//判断是否符合题目条件
boolean validate(int level, int num) {
for (int i = 0; i < level; i++) {
if (mark[i] > num) {
return false;
}
}
return true;
}
}
