阿里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;
    }
}

#阿里巴巴##Java工程师##笔经#