自学内容网 自学内容网

Leetcode - 145双周赛

目录

一,3375. 使数组的值全部为 K 的最少操作次数

二,3376. 破解锁的最少时间 I

三,3377. 使两个整数相等的数位操作

四,3378. 统计最小公倍数图中的连通块数目


一,3375. 使数组的值全部为 K 的最少操作次数

本题的操作就是将最大值变成次大值,最后将nums数组中的所有值变成 k,但是需要满足条件 nums[i] < k,也就是说如果 min(nums) < k 的话,无法使元素变成 k。

分情况:

  • k > min(nums),返回 -1
  • k == min(nums),少操作一次,返回 nums 中不同元素的个数 - 1
  • k < min(nums),返回 nums 中不同元素的个数

代码如下:

class Solution {
    public int minOperations(int[] nums, int k) {
        int mn = nums[0];
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for(int x : nums){
            set.add(x);
            mn = Math.min(mn, x);
        }
        if(mn < k) return -1;
        if(set.contains(k)) return set.size() - 1;
        return set.size();
    }
}

二,3376. 破解锁的最少时间 I

原问题是计算打开 {1,2,3,...,n} 这 n 把锁需要的最少时间,假设第一次打开第 2 把锁,问题就变成了计算 {1,3,...,n} 这 n-1 把锁需要的最少时间。这时就变成了与原问题相同的子问题,可以使用dfs解决了。

代码如下:

class Solution {
    public int findMinimumTime(List<Integer> s, int k) {
        int n = s.size();
        memo = new int[1<<n];
        Arrays.fill(memo, -1);
        return dfs(0, 1, s, k);
    }
    int[] memo;
    int dfs(int i, int x, List<Integer> nums, int k){
        int n = nums.size();
        if(i == (1<<n)-1) return 0;
        if(memo[i] != -1) return memo[i];
        int res = Integer.MAX_VALUE;
        for(int t=0; t<n; t++){
            if(((i>>t)&1) == 1) continue;//判断第 i 把锁是否使用过
            //(nums.get(t)+x-1)/x = (nums.get(t)-x+x-1)/x + 1
            //nums.get(t)-x 表示打开这把锁还需要这么多能量
            //(nums.get(t)-x+x-1)/x 表示需要+X的次数
            //+1 表示打开锁需要 1 分钟
            res = Math.min(res, dfs(i|1<<t, x+k, nums, k) + (nums.get(t)+x-1)/x);
        }
        return memo[i] = res;
    }
}

三,3377. 使两个整数相等的数位操作

本题看上去是一道数学题,实际上是一道图论的题,简述一下题意:把 n -> m 看成起点和终点,将每个数位增加/减少1当成中间节点,x -> y 两个相邻节点之间的路径长度是 y,计算 n -> m 的最短路径且中间节点值不能为质数。

此时可以直观的看出这是一道关于 dijstra 的题,需要注意的是要使用埃式筛预处理1~10000的质数。

代码如下:

class Solution {
    static boolean[] f = new boolean[10001];
    static{
        f[0] = f[1] = true;
        for(int i=2; i<10001; i++){
            if(f[i]) continue;
            for(int j=i*i; j<10001; j+=i){
                f[j] = true;
            }
        }
    }
    public int minOperations(int n, int m) {
        if(!f[n] || !f[m]) return -1;
        int len = String.valueOf(n).length();
        PriorityQueue<int[]> que = new PriorityQueue<>((a,b)->a[1]-b[1]);
        que.offer(new int[]{n, n});
        int[] dis = new int[(int)Math.pow(10,len)];//n->i的最短距离
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[n] = n;
        while(!que.isEmpty()){
            int[] p = que.poll();
            int dx = p[0], val = p[1];
            if(dx == m) return val;
            if(dis[dx] < val) continue;
            int k = 1;
            while(dx / k > 0){
                int a = dx / k % 10;
                if(a > 0){
                    int x = dx - k;
                    int newD = dx - k + val;
                    if(f[x] && newD < dis[x]){
                        dis[x] = newD;
                        que.offer(new int[]{x, newD});
                    }
                }
                if(a < 9){
                    int x = dx + k;
                    int newD = dx + k + val;
                    if(f[x] && newD < dis[x]){
                        dis[x] = newD;
                        que.offer(new int[]{x, newD});
                    }
                }
                k *= 10;
            }
        }
        return -1;
    }
}

四,3378. 统计最小公倍数图中的连通块数目

最小公倍数 lcm(a,b) = a * b / gcd(a,b) <= threshold,当 gcd(a,b) 在分母的时候,一般可以枚举 gcd(a,b) 的值 g={1,2,...,t} 及 g 的倍数,而这里需要枚举两个数 a 和 b,所以它的时间复杂度为O((threshold/g)^2),g={1,2,...,t},很显然这会超时。

但是实际上,可以先确定 a 值,比如 g = 2,枚举{2,4,6,8,10,...},要想要将这些数连通起来,可以将每个数与 2 连接,这样也能表示这些数两两连接,所以 a = nums中最小的g的倍数,然后去枚举 b 就可以了。此时时间复杂度变成了O(threshold/g),g={1,2,...,t}。t/1 + t/2 + ... + t/t = t * (1+1/2+...+1/t) = tlogt

代码如下:

class Solution {
    int find(int x, int[] f){
        if(f[x] != x){
            f[x] = find(f[x], f);
        }
        return f[x];
    }
    public int countComponents(int[] nums, int threshold) {
        int n = nums.length;
        int[] f = new int[n];
        Arrays.setAll(f, i -> i);
        int[] idx = new int[threshold+1];
        Arrays.fill(idx, -1);
        for(int i=0; i<n; i++){
            int x = nums[i];
            if(x <= threshold)
                idx[x] = i;
        }
        for(int g=1; g<=threshold; g++){
            int p = -1;
            for(int x=g; x<=threshold; x+=g){
                if(idx[x] >= 0){
                    p = x;
                    break;
                }
            }
            if(p < 0) continue;
            int pa_p = find(idx[p], f);
            //p * y / g <= t
            //y <= t * g / p  
            int up = (int)((long)threshold * g / p);
            for(int y=p+g; y<=up; y+=g){
                if(idx[y] >= 0){
                    int pa_y = find(idx[y], f);
                    if(pa_y != pa_p){
                        f[pa_y] = pa_p;
                        n--;
                    }
                }
            }
        }
        return n;
    }
}


原文地址:https://blog.csdn.net/m0_74859835/article/details/144400045

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!