WHCSRL 技术网

LeetCode 第63场双周赛复盘

LeetCode 第63场双周赛复盘

背景

2022秋招以0 offer基本结束,没有收到很满意的offer,基本上大厂全挂。对自己这样一个结果并不满意,为了能在春招上收获到满意的offer,于是决定继续参加周赛,提高自己的算法能力。

结果

前面二道过了,第二题wa了9次。全球排名4603 / 9524,全国排名1499/2828,妥妥的中位数。下次的目标是进前50%%%%

复盘

第一题[简单贪心]:

传送门

题目描述:

一个房间里有 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 次移动。

题目解答:

翻译翻译就是,给这些懒得多走路的学生找位置坐,使得他们走的路是最少的。

当时竞赛的解答:

我的想法非常朴素,是给每个懒学生找离他们最近的位子坐。

主要是靠经验,因为周赛一般来说第一题都很简单,通常就是贪心题。比较常见的贪心做法就是先排序。

class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        Arrays.sort(seats);
        Arrays.sort(students);
        int n = seats.length;
        int res = 0;
        for(int i=0;i<n;i++){
            res+=Math.abs(seats[i]-students[i]);
        }
        return res;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

贪心题的证明[想要提高必须要吃的苦]

证明上述的贪心做法是正确的,别看写的多,其实就是去绝对值

  • n=1时,只能有去做那个位置

  • n=2时,设两个座位位置分别是a,b,满足a<b;设两个学生c,d,满足c<d;

    • 方案一,按照大小关系一一对应,即cost1=|a-c|+|b-d|
    • 方案二,不按照方案一,那么选择的代价cost2=|a-d|+|b-c|;

    要证明方案一的代价要比方案二的代价小,即cost1<cost2,也就是cost1-cost2<0

    要求绝对值,就得判断大小关系,题设有a<b;c<d;

    情况一:a<b<c<d;
    ∣ a − c ∣ + ∣ b − d ∣ − ( ∣ a − d ∣ + ∣ b − c ∣ ) = c − a + d − b − ( d − a + c − b ) |a-c|+|b-d|-(|a-d|+|b-c|)=c-a+d-b-(d-a+c-b) ac+bd(ad+bc)=ca+db(da+cb)

    = c − a + d − b − d + a − b − c = 0 =c-a+d-b-d+a-b-c=0 =ca+dbd+abc=0

    情况二:c<d<a<b;两种方案一样

∣ a − c ∣ + ∣ b − d ∣ − ( ∣ a − d ∣ + ∣ b − c ∣ ) = 0 |a-c|+|b-d|-(|a-d|+|b-c|)=0 ac+bd(ad+bc)=0

​ 情况三:a<c<b<d;
∣ a − c ∣ + ∣ b − d ∣ − ( ∣ a − d ∣ + ∣ b − c ∣ ) = 2 ( c − b ) < 0 |a-c|+|b-d|-(|a-d|+|b-c|)=2(c-b)<0 ac+bd(ad+bc)=2(cb)<0
​ 情况四:c<a<d<b;
∣ a − c ∣ + ∣ b − d ∣ − ( ∣ a − d ∣ + ∣ b − c ∣ ) = 2 ( c − d ) < 0 |a-c|+|b-d|-(|a-d|+|b-c|)=2(c-d)<0 ac+bd(ad+bc)=2(cd)<0

​ 情况五:a<c<d<b:
∣ a − c ∣ + ∣ b − d ∣ − ( ∣ a − d ∣ + ∣ b − c ∣ ) = c − a + b − d − ( d − a + b − c ) = 2 ( c − d ) < 0 |a-c|+|b-d|-(|a-d|+|b-c|)=c-a+b-d-(d-a+b-c)=2(c-d)<0 ac+bd(ad+bc)=ca+bd(da+bc)=2(cd)<0

  • n>2时,用数学归纳法证明

第二题Alice和Bob

传送门

题目描述

总共有 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 。

题目解答

就是找出两个人可以操作的次数,因为alice先开始,所以如果alice的操作次数大于bob的操作次数+1的话,那么alice就赢了

wa了9次,才想出的,可以看出写出的代码也很烂。看别人的代码也有用字符串写的

class Solution {
    public boolean winnerOfGame(String colors) {
        int n = colors.length();
        int prevA = -1;
        int cnt1 = 0;
        int cnt2 = 0;
        int lenA = 0;
        int prevB = -1;
        int lenB = 0;
        for(int i=0;i<n;i++){
            if(colors.charAt(i)=='A'){
                prevB = i;
                if(lenB>=3){
                    cnt2+=lenB-2;
                }
                lenB=0;
                lenA = Math.max(lenA,i-prevA);//统计当前连续的A
            }else{
                prevA = i;
                if(lenA>=3){
                    cnt1+=lenA-2;
                  //如果A的连续断了就将这一段可以操作的次数加上去
                }
                lenA = 0;
                lenB = Math.max(lenB,i-prevB);
            }
        }
       //统计末尾的情况
        if(lenA>=3){
            cnt1+=lenA-2;
        }
        if(lenB>=3){
            cnt2+=lenB-2;
        }
        if(cnt1>=cnt2+1){
            return true;
        }else{
            return false;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

字符串分割写法

参考链接

    public static boolean winnerOfGame(String colors) {
        String A[] = colors.split("B");
      	//比如"AAABABB",划分出来的就是[AAA,A]
        String B[] = colors.split("A");
      	//划分出来的就是[ , , ,B,BB]
        int cnt1 = 0, cnt2 = 0;
        for (String str : A) {
            if (str.length() > 2) {
                cnt1 += (str.length() - 2);//只有大于三才能操作
            }
        }
        for (String str : B) {
            if (str.length() > 2) {
                cnt2 += (str.length() - 2);
            }
        }
        if (cnt1 == 0) return false;
        if (cnt1 <= cnt2) return false;
        else return true;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

第三题[无向图的最短路径]

传送门

题目描述:

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

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

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

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

如果还没收到任何回复信息,那么该服务器会周期性 重发 信息。数据服务器 i 每 patience[i] 秒都会重发一条信息,也就是说,数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒 后 会重发一条信息给主服务器。
否则,该数据服务器 不会重发 信息。
当没有任何信息在线路上传输或者到达某服务器时,该计算机网络变为 空闲 状态。

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

题目解答:

图这一块还是老样子,老是做不出来

下面是参考借鉴的大佬思路

T i T_i Ti表示 i i i号服务器完成所有传输需要的最短时间, d i s t i dist_i disti表示 i i i号服务器与0号服务器(也叫主服务器)的距离, p a t i e n c e i patience_i patiencei表示 i i i号服务器对应的重发等待时间

从i号服务器发送到主服务器,再从主服务器传回给i号服务器
T i = 2 ∗ d i s t i + [ ( 2 ∗ d i s t i − 1 ) / p a t i e n c e i ] ∗ p a t i e n c e i T_i=2*dist_i+[(2*dist_i-1)/patience_i]*patience_i Ti=2disti+[(2disti1)/patiencei]patiencei

public int networkBecomesIdle(int[][] edges, int[] patience) {
        int n = patience.length;
        int res = 0;
        //建图
        HashMap<Integer,List<Integer>> adj = new HashMap<>();
        for(int[] e:edges){
            int x = e[0], y = e[1];
            adj.putIfAbsent(x,new ArrayList<>());
            adj.putIfAbsent(y,new ArrayList<>());//无向图建两次
            adj.get(x).add(y);
            adj.get(y).add(x);
        }
        //bfs求最短路径
        int INF = (int)1e9;
        int[] dmin = new int[n];
        Arrays.fill(dmin,INF);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        dmin[0] = 0;
        while (!q.isEmpty()){
            int x = q.poll();
            if (x!=0){
                int time = dmin[x];
                int cur_cost = 2*time+(2*time-1)/patience[x]*patience[x];
                res = Math.max(res,cur_cost);
            }
            for (int y : adj.getOrDefault(x, new ArrayList<>())) {
                if(dmin[x]+1<dmin[y]){
                    dmin[y] = dmin[x]+1;
                    q.offer(y);
                }
            }
        }
        return res+1;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

这个代码完全可以总结出求最小路径的模版

        //建图
        HashMap<Integer,List<Integer>> adj = new HashMap<>();
        for(int[] e:edges){
            int x = e[0], y = e[1];
            adj.putIfAbsent(x,new ArrayList<>());
            adj.putIfAbsent(y,new ArrayList<>());//无向图建两次
            adj.get(x).add(y);
            adj.get(y).add(x);
        }
			  //bfs求最短路径
        int INF = (int)1e9;
        int[] dmin = new int[n];
        Arrays.fill(dmin,INF);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        dmin[0] = 0;
        while (!q.isEmpty()){
            int x = q.poll();
            if (x!=0){
                int time = dmin[x];
            }
            for (int y : adj.getOrDefault(x, new ArrayList<>())) {
                if(dmin[x]+1<dmin[y]){
                    dmin[y] = dmin[x]+1;
                    q.offer(y);
                }
            }
        }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

第四题

传送门

题目描述:

给你两个 从小到大排好序 且下标从 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 。

数据范围:

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

题目解答:

从数据范围上去看,O(n^2)的算法肯定是过不了的

于是思考时间复杂度低的算法,二分

二分中套二分

public class Solution {
    int[] A;
    int[] B;
    long k;
    public void mswap(int[] a,int[] b){
        int[] c = a;
        a = b;
        b = c;
    }
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        A=nums1;
        B=nums2;
        this.k=k;
        long l = (long)(-1e10);
        long r = (long)(1e10);
        //二分找一个数mid 使得小于mid的数正好有k个
        while (l<r){
            long mid = (l+r)>>1;
            if (check(mid)){
                r=mid;
            }else {
                l=mid+1;
            }
        }
        return l;
    }

    private boolean check(long uplimit) {
        long res = 0;
        if (A.length > B.length)
        {
            mswap(A, B);
        }
        //A代表的是长度小的数组
        //B代表的是长度大的数组
        int n1 = A.length;//两个数组都是从小到大排的
        int n2 = B.length;

        for (int x : A)
        {   //对A数组中的每一个数分奇偶来判断
            if (x < 0)//如果这个数是负数,那么它乘以B数组里最大的数就是最小的
            {
                //----如果最小的都大了,就过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;
                    }
                    //由于x是负数,x乘以l的右边的数都小于uplimit,
                    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;
                    }
                    //由于x是负数,x乘以l的左边的数都小于uplimit,
                    res += (l + 1);
                }
            }
            else
            {
                if (uplimit >= 0)
                {
                    res += n2;
                }
            }

        }
        return res >= k ? true : false;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
推荐阅读