Leetcode Bio-Weekly Contest Round 63

唠嗑

最近一直在大搞项目八股文，所以没怎么搞算法，算是半自暴自弃了。这段时间也就参加了一场LCP力扣杯的周赛的团体赛，总之队友很给力，首先要感谢NumPy爷和涛爷，那是真的牛批。

秋招总之过的稀烂，自己还是脸皮太薄，还患上了严重的interview jitters

写代码的时候不喜欢被人盯着看，写出了bug也不敢现场debug，还感觉自己丢人显眼，搞得面试官还以为我是不会debug。人啊，还是要自信一点，自己都不自信还指望别人帮你体面么😔。

18号就要MS第一轮面试了，找点感觉做把双周赛吧。

T1 2037. 使每位学生都有座位的最少移动次数

题目

一个房间里有 n 个座位和 n 名学生，房间用一个数轴表示。给你一个长度为 n 的数组 seats ，其中 seats[i] 是第 i 个座位的位置。同时给你一个长度为 n 的数组 students ，其中 students[j] 是第 j 位学生的位置。

你可以执行以下操作任意次：

• 增加或者减少第 i 位学生的位置，每次变化量为 1 （也就是将第 i 位学生从位置 x 移动到 x + 1 或者 x - 1）
  请你返回使所有学生都有座位坐的 最少移动次数 ，并确保没有两位学生的座位相同。

请注意，初始时有可能有多个座位或者多位学生在 同一 位置。

示例 1：

输入：seats = [3,1,5], students = [2,7,4]
输出：4

解释：学生移动方式如下：

• 第一位学生从位置 2 移动到位置 1 ，移动 1 次。

• 第二位学生从位置 7 移动到位置 5 ，移动 2 次。

• 第三位学生从位置 4 移动到位置 3 ，移动 1 次。

  总共 1 + 2 + 1 = 4 次移动。

示例 2：

输入：seats = [4,1,5,9], students = [1,3,2,6]
输出：7

解释：学生移动方式如下：

• 第一位学生不移动。

• 第二位学生从位置 3 移动到位置 4 ，移动 1 次。

• 第三位学生从位置 2 移动到位置 5 ，移动 3 次。

• 第四位学生从位置 6 移动到位置 9 ，移动 3 次。

  总共 0 + 1 + 3 + 3 = 7 次移动。

示例 3：

输入：seats = [2,2,6,6], students = [1,3,2,6]
输出：4

解释：学生移动方式如下：

• 第一位学生从位置 1 移动到位置 2 ，移动 1 次。

• 第二位学生从位置 3 移动到位置 6 ，移动 3 次。

• 第三位学生不移动。

• 第四位学生不移动。

  总共 1 + 3 + 0 + 0 = 4 次移动。

提示：

• $n == seats.length == students.length$
• $1 \leq n \leq 100$
• $1 \leq seats[i], students[j] \leq 100$

题解

简单的贪心

算是一种直觉吧，我们把学生和座位都从小到大排好序，然后一一对应入座肯定是最优解。反之，可以自己想想，如果学生之间互相交叉换座的话，开销必然会增大。交换任意两个学生对应的座位不会产生更少的移动次数。

简易的代码如下：

class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        Arrays.sort(seats);
        Arrays.sort(students);
        int len = seats.length;
        int res = 0;
        for(int i = 0; i < len; i++){
            res += Math.abs(seats[i] - students[i]);
        }
        return res;
    }
}

T2 5886. 如果相邻两个颜色均相同则删除当前颜色

题目

总共有 n 个颜色片段排成一列，每个颜色片段要么是 'A' 要么是 'B' 。给你一个长度为 n 的字符串 colors ，其中 colors[i] 表示第 i 个颜色片段的颜色。

Alice 和 Bob 在玩一个游戏，他们 轮流 从这个字符串中删除颜色。Alice 先手 。

• 如果一个颜色片段为 'A' 且 相邻两个颜色 都是颜色 'A' ，那么 Alice 可以删除该颜色片段。Alice 不可以 删除任何颜色 'B' 片段。

• 如果一个颜色片段为 'B' 且 相邻两个颜色 都是颜色 'B' ，那么 Bob 可以删除该颜色片段。Bob 不可以 删除任何颜色 'A' 片段。

• Alice 和 Bob 不能 从字符串两端删除颜色片段。

• 如果其中一人无法继续操作，则该玩家 输 掉游戏且另一玩家 获胜 。

  假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回 true，否则 Bob 获胜，返回 false。

示例 1：

输入：colors = “AAABABB”
输出：true

解释：
AAABABB -> AABABB
Alice 先操作。
她删除从左数第二个 ‘A’ ，这也是唯一一个相邻颜色片段都是 ‘A’ 的 ‘A’ 。

现在轮到 Bob 操作。
Bob 无法执行任何操作，因为没有相邻位置都是 ‘B’ 的颜色片段 ‘B’ 。
因此，Alice 获胜，返回 true 。

示例 2：

输入：colors = “AA”
输出：false

解释：
Alice 先操作。
只有 2 个 ‘A’ 且它们都在字符串的两端，所以她无法执行任何操作。
因此，Bob 获胜，返回 false 。

示例 3：

输入：colors = “ABBBBBBBAAA”
输出：false

解释：
ABBBBBBBAAA -> ABBBBBBBAA
Alice 先操作。
她唯一的选择是删除从右数起第二个 ‘A’ 。

ABBBBBBBAA -> ABBBBBBAA
接下来轮到 Bob 操作。
他有许多选择，他可以选择任何一个 ‘B’ 删除。

然后轮到 Alice 操作，她无法删除任何片段。
所以 Bob 获胜，返回 false 。

提示：

• $1 \leq colors.length \leq 10^5$
• colors 只包含字母 'A' 和 'B'

题解

别被吓到了就行，哈哈哈哈

你以为的Alice和Bob游戏：完美的博弈论，Alice和Bob互相挖坑，Alice卡着让Bob消除上分不成，同时努力上分。Bob同理。

实际上：Alice和Bob你拿你的，我拿我的。AAAAA再长也只能消成AA，永远都不会影响到隔壁的B组合，也就是说Alice和Bob各自的消除次数都是完全确定的。

以A序列为例，A和AA都无法构成消除，但是连续长度在3以上的A序列，就可以完成len - 2次消除。B序列也同理，然后由于是Alice先手，那我们保证Alice的总消除次数大于Bob的总消除次数时返回true即可。

简易代码如下：

class Solution {
    public boolean winnerOfGame(String colors) {
        int len = colors.length();
        Character prev = null;
        int cnt = 0;
        int a = 0, b = 0;
        for(int i = 0; i < len; i++){
            char ch = colors.charAt(i);
            if(prev == null || prev != ch){
                if(prev == null){
                    
                }
                else if(prev == 'A'){
                    a += cnt - 2> 0? cnt - 2 : 0;
                }
                else if(prev == 'B'){
                    b += cnt - 2> 0? cnt - 2 : 0;
                }
                prev = ch;
                cnt = 1;
            }
            else{
                cnt++;
            }
        }
        if(prev == null){
          
        }
        else if(prev == 'A'){
        		a += cnt - 2> 0? cnt - 2 : 0;
        }
        else if(prev == 'B'){
          	b += cnt - 2> 0? cnt - 2 : 0;
        }
        //System.out.println(a + " " + b);
        return a > b;
    }
}

真的是写的老长老长了。。。我真是个废物，到头来，这个不比我那个好看多了🤔：

class Solution {
    public boolean winnerOfGame(String colors) {
        int count = 0;
        for(int i = 0; i < colors.length()-2; i++){
            if(colors.substring(i,i+3).equals("AAA")) count++;
            if(colors.substring(i,i+3).equals("BBB")) count--;
        }
        return count > 0;
    }
}

T3 2039. 网络空闲的时刻

题目

给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示服务器 ui 和 vi 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 数目的信息。再给你一个长度为 n 且下标从 0 开始的整数数组 patience 。

题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。

编号为 0 的服务器是 主 服务器，其他服务器为 数据 服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 最优 线路传输，也就是说每个信息都会以 最少时间 到达主服务器。主服务器会处理 所有 新到达的信息并 立即 按照每条信息来时的路线 反方向 发送回复信息。

在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每 一秒最 开始 时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：

• 如果还没收到任何回复信息，那么该服务器会周期性 重发 信息。数据服务器 i 每 patience[i] 秒都会重发一条信息，也就是说，数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒 后 会重发一条信息给主服务器。
• 否则，该数据服务器 不会重发 信息。

当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。

请返回计算机网络变为 空闲 状态的 最早秒数 。

示例 1：

输入：edges = [[0,1],[1,2]], patience = [0,2,1]
输出：8

解释：

0 秒最开始时，

数据服务器 1 给主服务器发出信息（用 1A 表示）。

数据服务器 2 给主服务器发出信息（用 2A 表示）。

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

1 秒时，

信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。

数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。

数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

2 秒时，

回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。

信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。

服务器 2 重发一条信息（用 2C 表示）。
…

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

4 秒时，

回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。
…

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

7 秒时，回复信息 2D 到达服务器 2 。

从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。

所以第 8 秒是网络变空闲的最早时刻。

示例 2：

输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
输出：3

解释：数据服务器 1 和 2 第 2 秒初收到回复信息。
从第 3 秒开始，网络变空闲。

提示：

• $n == patience.length$
• $2 \leq n \leq 10^5$
• $patience[0] == 0$
• 对于 $1 \leq i < n$ ，满足 $1 \leq patience[i] \leq 10^5$
• $1 \leq edges.length \leq min(10^5, n * (n - 1) / 2)$
• $edges[i].length == 2$
• $0 \leq ui, vi < n$
• ui != vi
• 不会有重边。
• 每个服务器都直接或间接与别的服务器相连。

题解

私以为这道题目的关键并不是图的问题，确定各个节点到达根节点的距离其实是很好做的，当我们维护好我们的图之后，直接通过BFS就可以得到距离数组。

感觉更容易出错的地方是关于这个最后一次发送的时机的确定：

例如示例1中的节点2，他到根节点的距离是2，因此一趟来回需要4s。第一次发送出去的报文2A在，4时刻得到了回应，因而节点2放弃了原定的发送计划。最后一次发送的报文是上一次的2D，发送时刻是3秒时，因此2D报文的接受时刻是7秒时。于是在8秒时节点2彻底空闲。

而在示例2中，以节点1为例，他到根节点的距离是1。1A报文在0秒时发送，2秒时会收到回复，3秒时当前节点空闲。因此我们知道1A就是最后一次发送的报文，而他的发送时刻就是0秒，接受时刻是0 + 2 = 2秒时刻。

综上，我们的重点就很明确了。我们需要找到最后一次那个报文的发送时刻，然后加上两倍的距离等价的中途传递时间，我们就得到了最后一个报文的到达时间。再加一，我们就得到了当前节点的空闲时刻。

关键是我们如何衡量最后一次报文的发送时刻呢，最后一次报文的发送时刻必须严格在第一个报文到达前发出（即使是等于也是不允许的，例如刚才举的第一个例子，在时刻4，由于回复报文已经到达了，也就无需发送了，最后一次报文的发送时刻就不是4了，而是3）。

假设中途的传递时间我们记为time，那么必有time = 2 * dist。如果time整除了patience时间，也就意味着在某个时刻收到了回复消息，但是很显然这个时刻我们是选择不发送的，最后一个发送时刻是上个时刻，也就是(time / patience[i] - 1) * patience[i]。如果没有整除，那就说明没有相交的位置，直接向下取即可，也就是time / patience[i] * patience[i]。

代码如下：

class Solution {
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int len = patience.length;
        int[] dist = new int[len];
      //建立邻接表，并将边的相关信息填入
        List<List<Integer>> neighbour = new ArrayList<>();
        for(int i = 0; i < len; i++) neighbour.add(new ArrayList<Integer>());
        for(int[] edge: edges){
            neighbour.get(edge[0]).add(edge[1]);
            neighbour.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[len];
        visited[0] = true;
      //使用队列完成BFS搜索操作，完成dist数组的填充，即各个点到根的距离
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        int step = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int cur = queue.poll();
                dist[cur] = step;
                for(int x: neighbour.get(cur)){
                    if(!visited[x]) {
                        visited[x] = true;
                        queue.offer(x);
                    }
                }
            }
            step++;
        }
        int res = 0;
        for(int i = 1; i < len; i++){
          //解释如上
            int time = 2 * dist[i];
            int addi = 0;
            if(time % patience[i] == 0) addi = (time / patience[i] - 1) * patience[i];
            else addi = time / patience[i] * patience[i];
            res = Math.max(res, time + addi);
        }
        return res + 1;
    }
}

T4 2040. 两个有序数组的第 K 小乘积

题目

给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k ，请你返回第 k （从 1 开始编号）小的 nums1[i] * nums2[j] 的乘积，其中 0 <= i < nums1.length 且 0 <= j < nums2.length 。

示例 1：

输入：nums1 = [2,5], nums2 = [3,4], k = 2
输出：8

解释：第 2 小的乘积计算如下：

• nums1[0] * nums2[0] = 2 * 3 = 6

• nums1[0] * nums2[1] = 2 * 4 = 8

  第 2 小的乘积为 8 。

示例 2：

输入：nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
输出：0

解释：第 6 小的乘积计算如下：

• nums1[0] * nums2[1] = (-4) * 4 = -16

• nums1[0] * nums2[0] = (-4) * 2 = -8

• nums1[1] * nums2[1] = (-2) * 4 = -8

• nums1[1] * nums2[0] = (-2) * 2 = -4

• nums1[2] * nums2[0] = 0 * 2 = 0

• nums1[2] * nums2[1] = 0 * 4 = 0

  第 6 小的乘积为 0 。

示例 3：

输入：nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
输出：-6

解释：第 3 小的乘积计算如下：

• nums1[0] * nums2[4] = (-2) * 5 = -10

• nums1[0] * nums2[3] = (-2) * 4 = -8

• nums1[4] * nums2[0] = 2 * (-3) = -6

  第 3 小的乘积为 -6 。

提示：

$1 \leq nums1.length, nums2.length \leq 5 * 10^4$
$-10^5 \leq nums1[i], nums2[j] \leq 10^5$
$1 \leq k \leq nums1.length * nums2.length$
nums1 和 nums2 都是从小到大排好序的。

题解

这道题？感觉很像这个：668. 乘法表中第k小的数

emmm，又很像这个？剑指 Offer II 061. 和最小的 k 个数对

首先，对两个数组进行嵌套遍历的话复杂度高了，另外如果我们直接使用PriorityQueue对nums1和nums2对所有情况进行遍历，产生的数据量可能会直接撑爆优先队列，总之死搞是不行的。

我们看到两个数组都是有序的，照理说题目会简单一些，如果全部都是正数的话，我们直接按照上面提到的两个题目的思路去做就可以了。但是，两个数组中都有可能带有负数，我们都知道负负得正，负正得负，所以这里就有的我们扯的了。

首先，我们把nums1分成neg1和pos1，分别表示nums1的负数部分和非负数部分；

把nums2分成neg2和pos2，分别表示nums2的负数部分和非负数部分；

• 情形一：$nums1[i] \geq 0, nums2[j] \geq 0$，分别对应pos1和pos2
• 情形二：$nums1[i] < 0, nums2[j] \geq 0$，分别对应neg1和pos2
• 情形三：$nums1[i] \geq 0, nums2[j] < 0$，分别对应pos1和neg2
• 情形四：$nums1[i] < 0, nums2[j] < 0$，分别对应neg1和neg2

总之这道题就是梦回初中了属于是

我们可以直接二分套二分，选择对结果进行二分，每次去计算小于当前limit的数量，计算的过程也是一个二分。

class Solution 
{
    int [] A;
    int [] B;
    long k;

    public boolean check(long uplimit)
    {
        long res = 0;
        int n1 = A.length;
        int n2 = B.length;

        for (int x : A)
        {
            if (x < 0)
            {
                //----如果最小的都大了，就过0
                if ((long)x * B[n2 - 1] > uplimit)
                {
                    continue;
                }
                else
                {
                    //----二分最左
                    int l = 0;
                    int r = n2 - 1;
                    while (l < r)
                    {
                        int mid = l + r >> 1;
                        if ((long)x * B[mid] <= uplimit)
                            r = mid;
                        else    
                            l = mid + 1;
                    }
                    res += (n2 - l);
                }
            }
            else if (x > 0)
            {
                //----如果最小的都大了，就过
                if ((long)x * B[0] > uplimit)
                {
                    continue;
                }
                else
                {
                    //----二分最右
                    int l = 0;
                    int r = n2 - 1;
                    while (l < r)
                    {
                        int mid = l + r + 1 >> 1;
                        if ((long)x * B[mid] <= uplimit)
                            l = mid;
                        else
                            r = mid - 1;
                    }
                    res += (l + 1);
                }
            }
            else
            {
                if (uplimit >= 0)
                {
                    res += n2;
                }
            }

        }
        return res >= k;
    }

    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) 
    {
        this.A = nums1;
        this.B = nums2;
        this.k = k;

        //--------二分最左
        long l = (long)(-1e10);
        long r = (long)(1e10);
        while (l < r)
        {
            long mid = l + r >> 1;
            if (check(mid) == true)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
}