😺 第 76 场力扣夜喵双周赛

太困了这场，总得找点理由，第四题复杂度没分析好，也没想到枚举中间两个，刚开始想的是回溯直接暴力，写完才发现复杂度至少是O(n^2)，会TLE，然后考虑枚举中间的点，但问题是我只想到了枚举中间的点，却没想明白枚举中间的两个点。。
下午LCCUP和AcWing的周赛再加上双周赛，脑子实在是没在转了。

6060. 找到最接近 0 的数字

给你一个长度为 n 的整数数组 nums ，请你返回 nums 中最 接近 0 的数字。如果有多个答案，请你返回它们中的 最大值 。

示例 1：
输入：nums = [-4,-2,1,4,8] 输出：1 解释： -4 到 0 的距离为 |-4| = 4 。 -2 到 0 的距离为 |-2| = 2 。 1 到 0 的距离为 |1| = 1 。 4 到 0 的距离为 |4| = 4 。 8 到 0 的距离为 |8| = 8 。 所以，数组中距离 0 最近的数字为 1 。
示例 2：
输入：nums = [2,-1,1] 输出：1 解释：1 和 -1 都是距离 0 最近的数字，所以返回较大值 1 。

提示：

• 1 <= n <= 1000
• -105 <= nums[i] <= 105

思路：
模拟即可 :::danger Wrong一次是因为一个变量中间写错了(第7行写成了res = v) :::

class Solution {
    public int findClosestNumber(int[] nums) {
        int res = 0x3f3f3f3f;
        for (int x : nums) {
            int v = Math.abs(x);
            if (v < Math.abs(res))
                res = x;
            else if (v == Math.abs(res))
                res = Math.max(res, x);
        }
        return res;
    }
}

6061. 买钢笔和铅笔的方案数

给你一个整数 total ，表示你拥有的总钱数。同时给你两个整数 cost1 和 cost2 ，分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱，去买任意数目的两种笔。
请你返回购买钢笔和铅笔的 不同方案数目 。

示例 1：
输入：total = 20, cost1 = 10, cost2 = 5 输出：9 解释：一支钢笔的价格为 10 ，一支铅笔的价格为 5 。 - 如果你买 0 支钢笔，那么你可以买 0 ，1 ，2 ，3 或者 4 支铅笔。 - 如果你买 1 支钢笔，那么你可以买 0 ，1 或者 2 支铅笔。 - 如果你买 2 支钢笔，那么你没法买任何铅笔。 所以买钢笔和铅笔的总方案数为 5 + 3 + 1 = 9 种。
示例 2：
输入：total = 5, cost1 = 10, cost2 = 10 输出：1 解释：钢笔和铅笔的价格都为 10 ，都比拥有的钱数多，所以你没法购买任何文具。所以只有 1 种方案：买 0 支钢笔和 0 支铅笔。

提示：

• 1 <= total, cost1, cost2 <= 106

思路：
模拟即可

class Solution {
    public long waysToBuyPensPencils(int tot, int c1, int c2) {
        long res = 0;
        for (int i = 0; i * c1 <= tot; i++) {
            int x = tot - i * c1;
            int v = x / c2;
            res += v + 1;
        }
        return res;
    }
}

6062. 设计一个 ATM 机器

一个 ATM 机器，存有 5 种面值的钞票：20 ，50 ，100 ，200 和 500 美元。初始时，ATM 机是空的。用户可以用它存或者取任意数目的钱。
取款时，机器会优先取 较大 数额的钱。

• 比方说，你想取 $300 ，并且机器里有 2 张 $50 的钞票，1 张 $100 的钞票和1 张 $200 的钞票，那么机器会取出 $100 和 $200 的钞票。
• 但是，如果你想取 $600 ，机器里有 3 张 $200 的钞票和1 张 $500 的钞票，那么取款请求会被拒绝，因为机器会先取出 $500 的钞票，然后无法取出剩余的 $100 。注意，因为有 $500 钞票的存在，机器 不能 取 $200 的钞票。

请你实现 ATM 类：

• ATM() 初始化 ATM 对象。
• void deposit(int[] banknotesCount) 分别存入 $20 ，$50，$100，$200 和 $500 钞票的数目。
• int[] withdraw(int amount) 返回一个长度为 5 的数组，分别表示 $20 ，$50，$100 ，$200 和 $500 钞票的数目，并且更新 ATM 机里取款后钞票的剩余数量。如果无法取出指定数额的钱，请返回 [-1] （这种情况下 不 取出任何钞票）。

示例 1：
输入： [“ATM”, “deposit”, “withdraw”, “deposit”, “withdraw”, “withdraw”] [[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]] 输出： [null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]] 解释： ATM atm = new ATM(); atm.deposit([0,0,1,2,1]); // 存入 1 张 $100 ，2 张 $200 和 1 张 $500 的钞票。 atm.withdraw(600); // 返回 [0,0,1,0,1] 。机器返回 1 张 $100 和 1 张 $500 的钞票。机器里剩余钞票的数量为 [0,0,0,2,0] 。 atm.deposit([0,1,0,1,1]); // 存入 1 张 $50 ，1 张 $200 和 1 张 $500 的钞票。 // 机器中剩余钞票数量为 [0,1,0,3,1] 。 atm.withdraw(600); // 返回 [-1] 。机器会尝试取出 $500 的钞票，然后无法得到剩余的 $100 ，所以取款请求会被拒绝。 // 由于请求被拒绝，机器中钞票的数量不会发生改变。 atm.withdraw(550); // 返回 [0,1,0,0,1] ，机器会返回 1 张 $50 的钞票和 1 张 $500 的钞票。

提示：

• banknotesCount.length == 5
• 0 <= banknotesCount[i] <= 109
• 1 <= amount <= 109
• 总共 最多有 5000 次 withdraw 和 deposit 的调用。
• 函数 withdraw 和 deposit 至少各有 一次 调用。

思路：
考察面向对象

class ATM {
    long[][] a = new long[5][2];
    public ATM() {
        a[0][0] = 20;
        a[1][0] = 50;
        a[2][0] = 100;
        a[3][0] = 200;
        a[4][0] = 500;
    }
    public void deposit(int[] b) {
        for (int i = 0; i < b.length; i++)
            a[i][1] += b[i];
    }
    public int[] withdraw(int amount) {
        int[] b = new int[5];
        for (int i = 4; i >= 0; i--) {
            int x = (int)Math.min(amount / a[i][0], a[i][1]);
            b[i] = x;
            a[i][1] -= x;
            amount -= x * a[i][0];
        }
        if (amount == 0) return b;
        else {
            for (int i = 0; i < 5; i++)
                a[i][1] += b[i];
            return new int[]{-1};
        }
    }
}
/**
 * Your ATM object will be instantiated and called as such:
 * ATM obj = new ATM();
 * obj.deposit(banknotesCount);
 * int[] param_2 = obj.withdraw(amount);
 */

6063. 节点序列的最大得分

给你一个 n 个节点的 无向图 ，节点编号为 0 到 n - 1 。
给你一个下标从 0 开始的整数数组 scores ，其中 scores[i] 是第 i 个节点的分数。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] ，表示节点 ai 和 bi 之间有一条 无向 边。
一个合法的节点序列如果满足以下条件，我们称它是 合法的 ：

• 序列中每 相邻 节点之间有边相连。
• 序列中没有节点出现超过一次。

节点序列的分数定义为序列中节点分数之 和 。
请你返回一个长度为 4 的合法节点序列的最大分数。如果不存在这样的序列，请你返回 -1 。

示例 1：

输入：scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]] 输出：24 解释：上图为输入的图，节点序列为 [0,1,2,3] 。 节点序列的分数为 5 + 2 + 9 + 8 = 24 。 观察可知，没有其他节点序列得分和超过 24 。 注意节点序列 [3,1,2,0] 和 [1,0,2,3] 也是合法的，且分数为 24 。 序列 [0,3,2,4] 不是合法的，因为没有边连接节点 0 和 3 。
示例 2：

输入：scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]] 输出：-1 解释：上图为输入的图。 没有长度为 4 的合法序列，所以我们返回 -1 。

提示：

• n == scores.length
• 4 <= n <= 5 * 104
• 1 <= scores[i] <= 108
• 0 <= edges.length <= 5 * 104
• edges[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• 不会有重边。

思路：
对每个点对其相邻边按权重排序，枚举边，即固定中间两个点，枚举边缘两个点，因为可能有重复，所以各自需要延展3个点才可以
复杂度分析：选3个最优值的复杂度其实是O(n + m)

class Solution {
    public int maximumScore(int[] w, int[][] edges) {
        int n = w.length;
        List<int[]>[] list = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            list[a].add(new int[]{w[b], b});
            list[b].add(new int[]{w[a], a});
        }
        for (int i = 0; i < n; i++) {
            Collections.sort(list[i], (o1, o2) -> (o2[0] - o1[0]));
            if (list[i].size() > 3) {
                list[i] = new ArrayList<>(list[i].subList(0, 3));
            }
        }
        int max = -1;
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            for (int[] a : list[x]) {
                for (int[] b : list[y]) {
                    if (a[1] != b[1] && a[1] != y && b[1] != x)
                        max = Math.max(max, w[x] + w[y] + a[0] + b[0]);
                }
            }
        }
        return max;
    }
}