LeetCode Contest 327

6283. Maximum Count of Positive Integer and Negative Integer

给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。
注意：0 既不是正整数也不是负整数。

测试样例

输入：nums = [-2,-1,-1,1,2,3]

输出：3

解释：

共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。

解答：这题本意应该是希望我们使用二分查找，但是数据范围很小，竞赛的时候还是保证AC优先。所以我就直接暴力搜索了

class Solution {
    public int maximumCount(int[] nums) {
        int neg = 0, pos = 0;
        for (int n : nums) {
            if (n < 0) {
                ++neg;
            } else if (n > 0) {
                ++pos;
            }
        }
        return Math.max(neg, pos);
    }
}

6285. Maximal Score After Applying K Operations

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。

在一步 操作 中：

选出一个满足 0 <= i < nums.length 的下标 i ，

1. 将你的 分数 增加 nums[i] ，并且
2. 将 nums[i] 替换为 ceil(nums[i] / 3) 。
3. 返回在 恰好 执行 k 次操作后，你可能获得的最大分数。

向上取整函数 ceil(val) 的结果是大于或等于 val 的最小整数。

测试样例：

输入：nums = [10,10,10,10,10], k = 5

输出：50

解释：

对数组中每个元素执行一次操作。最后分数是 10 + 10 + 10 + 10 + 10 = 50 。

解答: 这题其实需要用到贪婪算法。越大的数字，就越有优先进行计算，然后按照要求向上取整返回队列。

都说到优先了，那用个优先队列也就不过分了。

class Solution {
    public long maxKelements(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (b.compareTo(a)));
        for (int n : nums) {
            queue.add(n);
        }
        long res = 0;
        while (k > 0) {
            int tmp = queue.poll();
            res += tmp;
            if (tmp % 3 == 0) {
                tmp /= 3;
            } else {
                tmp = tmp / 3 + 1;
            }
            queue.add(tmp);
            --k;
        }
        return res;
    }
}

6284. Make Number of Distinct Characters Equal

给你两个下标从 0 开始的字符串 word1 和 word2 。

一次 移动 由以下两个步骤组成：

• 选中两个下标 i 和 j ，分别满足 0 <= i < word1.length 和 0 <= j < word2.length ，
• 交换 word1[i] 和 word2[j] 。
  如果可以通过 恰好一次 移动，使 word1 和 word2 中不同字符的数目相等，则返回 true ；否则，返回 false 。

测试样例

输入：word1 = "ac", word2 = "b"

输出：false

解释：

交换任何一组下标都会导致第一个字符串中有 2 个不同的字符，而在第二个字符串中只有 1 个不同字符。

解答：这题一开始卡了我一会，本来想枚举什么情况下可以保证2个字符串交换一次字符后可以保证不同字符的数目相等。但是再想想，只要把一个字符串的字符情况统计一下，然后枚举一下所有交换可能，不就可以得到解了。

用人脑减枝，然后用电脑暴力一下就能AC了。

class Solution {
    public boolean isItPossible(String word1, String word2) {
        int[] m1 = distinct(word1), m2 = distinct(word2);
        for (int i = 0; i < 26; ++i) {
            if (m1[i] > 0) {
                for (int j = 0; j < 26; ++j) {
                    if (m2[j] != 0) {
                        m1[i] -= 1;
                        m1[j] += 1;
                        m2[i] += 1;
                        m2[j] -= 1;
                        if (distinctCount(m1) == distinctCount(m2)) {
                            return true;
                        }
                        m1[i] += 1;
                        m1[j] -= 1;
                        m2[i] -= 1;
                        m2[j] += 1;
                    }
                }
            }
        }
        return false;
    }

    private int[] distinct(String w) {
        int[] mem = new int[26];
        for (int i = 0; i < w.length(); ++i) {
            int o = w.charAt(i) - 'a';
            mem[o] += 1;
        }
        return mem;
    }

    private int distinctCount(int[] mem) {
        int res = 0;
        for (int i : mem) {
            if (i > 0) ++res;
        }
        return res;
    }
}

6306. Time to Cross a Bridge

共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 n 和 k，以及一个二维整数数组 time ，数组的大小为 k x 4 ，其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi] 。

一条河将两座仓库分隔，只能通过一座桥通行。旧仓库位于河的右岸，新仓库在河的左岸。开始时，所有 k 位工人都在桥的左侧等待。为了移动这些箱子，第 i 位工人（下标从 0 开始）可以：

• 从左岸（新仓库）跨过桥到右岸（旧仓库），用时 leftToRighti 分钟。
• 从旧仓库选择一个箱子，并返回到桥边，用时 pickOldi 分钟。不同工人可以同时搬起所选的箱子。
• 从右岸（旧仓库）跨过桥到左岸（新仓库），用时 rightToLefti 分钟。
• 将箱子放入新仓库，并返回到桥边，用时 putNewi 分钟。不同工人可以同时放下所选的箱子。

如果满足下面任一条件，则认为工人 i 的 效率低于 工人 j ：

• leftToRighti + rightToLefti > leftToRightj + rightToLeftj
• leftToRighti + rightToLefti == leftToRightj + rightToLeftj 且 i > j

工人通过桥时需要遵循以下规则：

• 如果工人 x 到达桥边时，工人 y 正在过桥，那么工人 x 需要在桥边等待。
• 如果没有正在过桥的工人，那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待，那么 效率最低 的工人会先过桥。
• 如果没有正在过桥的工人，且桥右边也没有在等待的工人，同时旧仓库还剩下至少一个箱子需要搬运，此时在桥左边的工人可以过桥。如果同时有多个工人在左边等待，那么 效率最低 的工人会先过桥。
• 所有 n 个盒子都需要放入新仓库，请你返回最后一个搬运箱子的工人 到达河左岸 的时间。

测试样例：

输入：n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]

输出：6

解释：

从 0 到 1 ：工人 2 从左岸过桥到达右岸。

从 1 到 2 ：工人 2 从旧仓库搬起一个箱子。

从 2 到 6 ：工人 2 从右岸过桥到达左岸。

从 6 到 7 ：工人 2 将箱子放入新仓库。

整个过程在 7 分钟后结束。因为问题关注的是最后一个工人到达左岸的时间，所以返回 6 。

解答：这道题目需要仔细读题，然后一步步拆分。

1. 排序：按照题目第一部分的要求，我们要对工人的效率进行排序
2. 模拟过桥：这部分真的是硬编码了。我们可以认为过桥是一个生产者消费者队列。系统存在左右，2个生产者队列和过桥这个消费者队列。
   1. 首先判断是否有人可以过桥：如果可以过桥，更新当前时间，工人开始过桥
   2. 判断过桥期间，是否有工人完成箱子搬运。有的话，则加入待过桥队列
   3. 如果待过桥队列都是空，则需要直接下次开始过桥时间

class Solution {
    public int findCrossingTime(int n, int k, int[][] time) {
        Integer[] map = new Integer[k];
        for (int i = 0; i < k; ++i) {
            map[i] = i;
        }
        Arrays.sort(map, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                Integer t1 = time[o1][0] + time[o1][2];
                Integer t2 = time[o2][0] + time[o2][2];
                if (!t1.equals(t2)) {
                    return t2.compareTo(t1);
                } else {
                    return o2.compareTo(o1);
                }
            }
        });

        Integer[] sort = new Integer[k];
        for (int i = 0; i < k; ++i) {
            sort[map[i]] = i;
        }

        PriorityQueue<Integer> leftWorker = new PriorityQueue<>((a, b) -> (sort[a].compareTo(sort[b])));
        for (int i = 0; i < k; ++i) {
            leftWorker.add(i);
        }
        PriorityQueue<Integer> rightWorker = new PriorityQueue<>((a, b) -> (sort[a].compareTo(sort[b])));
        PriorityQueue<int[]> timePoint = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        int nextBridgeFree = 0, oldLeft = n;
        int res = 0;

        while (n > 0) {
            if (!rightWorker.isEmpty()) {
                int w = rightWorker.poll();
                nextBridgeFree += time[w][2];
                timePoint.add(new int[]{nextBridgeFree + time[w][3], w, 1});
            } else if (oldLeft > 0 && !leftWorker.isEmpty()) {
                int w = leftWorker.poll();
                nextBridgeFree += time[w][0];
                --oldLeft;
                timePoint.add(new int[]{nextBridgeFree + time[w][1], w, 0});
            } else if (!timePoint.isEmpty()) {
                nextBridgeFree = timePoint.peek()[0];
            }
            while (!timePoint.isEmpty() && timePoint.peek()[0] <= nextBridgeFree) {
                int[] t = timePoint.poll();
                if (t[2] == 1) {
                    res = Math.max(res, t[0] - time[t[1]][3]);
                    --n;
                    leftWorker.add(t[1]);
                } else {
                    rightWorker.add(t[1]);
                }
            }
        }
        return res;
    }
}

相比上一周的题目，这周题目难度真的是陡增。