奇安信8.1笔试

8.1号下午考的，Java软件开发岗。

题目总体中等偏下，选择题大部分都遇到过。

大部分都是操作系统和网络问题。这一部分需要多练。

两道编程题思路也很简单，常刷leetcode基本上都能秒掉。

1.笔试题型

考试时间120分钟

1.单选题：20道（40分）

2.多选题：10道（20分）

3.编程题：2道（40分，每道20分）

2.Coding1

题目描述：

1.2020年春节之际，新冠肺炎爆发，国内医疗资源大量紧缺

2.小明作为一位采购员，被派到国外采购紧缺物资

3.由于国内需要的物资种类很多，不同品牌种类的物资在疫情中的使用价值也不同

4.在了解商品情况后，小明开始为采购哪些物资才最合适而烦恼。

5.假如给定了采购预算 T , 每种物资的价格Pn和使用价值 Wn

6.每种物资的可采购数量不限，你能帮他快速决定出应该采购的物资吗？

7.要求采购物资的总价格不能超过采购预算

8.在这个前提下给出的采购列表要使得这批物资的使用价值最大。

输入描述:
每个测试输入包含一个测试用例
第一行是总预算(不大于200000)
第二行是物资种类总数 n (不大于20)
后面有n行数据，每一行代表一种物资的价格和使用价值，被空格分成两列，每列数据值不大于15000

例如第3行数据中第一列是物资1的价格P1, 第二列是物资2的使用价值 W1
第4行数据中第一列是物资2的价格 P2, 第二列是物资2的使用价值 W2。
以此类推，第 n+2 行中第一列是物资 n 的价格 Pn ，第二列是物资 n 的价格 Wn。

输出描述:
输出采购物资能达到的最高使用价值，格式是单独的一行数值

示例1：
输入
100
5
77 92
22 22
29 36
50 46
99 90

输出
114

说明
100预算、5种商品情况下，购买 1个商品一和 1个商品二可以达到最大使用价值114

示例2：
输入
200
8
79 83
58 81
86 54
110 1500
62 52
45 48
68 62
30 22

输出
253

说明
200预算、8种商品情况下，购买 1个商品二、 1个商品四和一个商品八可以达到最大使用价值253

备注:
注意：每种物资的可采购数量没有限制

思路：

这题就是一个完全背包问题，非常的经典。

背包问题也是笔试常考的dp知识点了。

建议去这里刷背包问题：https://www.acwing.com/problem/content/3/

参考代码：

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int money = scanner.nextInt();
        int n = scanner.nextInt();
        int[] p = new int[n];
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }

        int[] dp = new int[money + 1];
        dp[0] = 0;
        for (int curMoney = 1; curMoney <= money; curMoney++) {
            for (int j = 1; j <= n; j++) {
                if (curMoney >= p[j - 1]) {
                    dp[curMoney] = Math.max(dp[curMoney], dp[curMoney - p[j - 1]] + w[j - 1]);
                }
            }
        }
        System.out.println(dp[money]);
    }

3.Coding2

题目描述：

1.如果一个正整数可以被7整除，我们称之为亲7数

2.对于给出的一组个位数字，请找出使用所有的数字排列出的数中的亲7数的个数。

3.其中给出的个位数字数组中每一个都是不相关的，即使有重复的数字

4.如{1，1，2}排列出的数为{112，121，112，121，211，211}，亲7数为{112，112}共2个。

输入：个位数字数组，数组有m个元素

输出：亲7数个数

示例1:
输入
[1,1,2]

输出
2

思路：

这题也没有什么难点，暴力 +回溯求所有可能的排列就行。

不过回溯可能会超时，需要优化一下。

回溯使用的是一个很经典的回溯模板。

建议刷这个：
https://leetcode-cn.com/problems/permutations-ii/

参考代码：

这题很友好的没有要求写输入输出，和平时刷题一样，写代码交就行。😊

    private int count = 0;

    public int code(int[] digit) {
        LinkedList<Integer> track = new LinkedList<>();
        boolean[] flag = new boolean[digit.length];
        backtrace(digit, digit.length, track, flag);
        return count;
    }

    /**
     * 回溯
     *
     * @param nums  元素数组
     * @param size  元素个数
     * @param track 记录list
     * @param flag  元素标记
     */
    public void backtrace(int[] nums, int size, LinkedList<Integer> track, boolean[] flag) {
        //递归结束条件
        if (track.size() == size && check(track)) {
            count++;
        }
        //开始遍历元素
        for (int i = 0; i < size; i++) {
            if (flag[i]) {
                continue;
            }
            flag[i] = true;
            track.add(nums[i]);
            backtrace(nums, size, track, flag);
            track.pollLast();
            flag[i] = false;
        }
    }

    /**
     * 判断是否是亲7数
     */
    public boolean check(LinkedList<Integer> list) {
        StringBuilder s = new StringBuilder();
        for (int i : list) {
            s.append(i);
        }
        int n = Integer.parseInt(s.toString());
        return n % 7 == 0;
    }

代码写的很垃圾，大佬请忽略。😅