首页 > 阿里3.19笔试 Java版本
头像
创新港蔡徐坤
编辑于 2021-04-19 08:51
+ 关注

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


全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐