【题解】—— LeetCode一周小结18

简介: 【题解】—— LeetCode一周小结18

29.将矩阵按对角线排序

题目链接:1329. 将矩阵按对角线排序

矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线,沿右下方向一直到矩阵末尾的元素。例如,矩阵 mat 有 6 行 3 列,从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。

给你一个 m * n 的整数矩阵 mat ,请你将同一条 矩阵对角线 上的元素按升序排序后,返回排好序的矩阵。

示例 1:

输入:mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]

输出:[[1,1,1,1],[1,2,2,2],[1,2,3,3]]

示例 2:

输入:mat =

[[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]

输出:[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

提示:

m == mat.length

n == mat[i].length

1 <= m, n <= 100

1 <= mat[i][j] <= 100

题解:

方法:排序

       

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] a = new int[Math.min(m, n)];
        for (int k = 1 - n; k < m; k++) { // k = i - j
            int leftI = Math.max(k, 0);
            int rightI = Math.min(k + n, m);
            for (int i = leftI; i < rightI; i++) {
                a[i - leftI] = mat[i][i - k];
            }
            Arrays.sort(a, 0, rightI - leftI);
            for (int i = leftI; i < rightI; i++) {
                mat[i][i - k] = a[i - leftI];
            }
        }
        return mat;
    }
}

30.满足目标工作时长的员工数目

题目链接:2798. 满足目标工作时长的员工数目

公司里共有 n 名员工,按从 0 到 n - 1 编号。每个员工 i 已经在公司工作了 hours[i] 小时。

公司要求每位员工工作 至少 target 小时。

给你一个下标从 0 开始、长度为 n 的非负整数数组 hours 和一个非负整数 target 。

示例 1:

输入:hours = [0,1,2,3,4], target = 2

输出:3

解释:公司要求每位员工工作至少 2 小时。

  • 员工 0 工作 0 小时,不满足要求。
  • 员工 1 工作 1 小时,不满足要求。
  • 员工 2 工作 2 小时,满足要求。
  • 员工 3 工作 3 小时,满足要求。
  • 员工 4 工作 4 小时,满足要求。

共有 3 位满足要求的员工。

示例 2:

输入:hours = [5,1,4,2,2], target = 6

输出:0

解释:公司要求每位员工工作至少 6 小时。

共有 0 位满足要求的员工。

提示:

1 <= n == hours.length <= 50

0 <= hours[i], target <= 105

题解:

方法:遍历

       

class Solution {
    public int numberOfEmployeesWhoMetTarget(int[] hours, int target) {
        int ans = 0;
        for (int h : hours) {
            if (h >= target) {
                ans++;
            }
        }
        return ans;
    }
}

2024.5

1.雇佣 K 位工人的总代价

题目链接:2462. 雇佣 K 位工人的总代价

给你一个下标从 0 开始的整数数组 costs ,其中 costs[i] 是雇佣第 i 位工人的代价。

同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人:

总共进行 k 轮雇佣,且每一轮恰好雇佣一位工人。

在每一轮雇佣中,从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人,如果有多位代价相同且最小的工人,选择下标更小的一位工人。

比方说,costs = [3,2,7,7,1,2] 且 candidates = 2 ,第一轮雇佣中,我们选择第 4 位工人,因为他的代价最小 [3,2,7,7,1,2] 。

第二轮雇佣,我们选择第 1 位工人,因为他们的代价与第 4 位工人一样都是最小代价,而且下标更小,[3,2,7,7,2] 。注意每一轮雇佣后,剩余工人的下标可能会发生变化。

如果剩余员工数目不足 candidates 人,那么下一轮雇佣他们中代价最小的一人,如果有多位代价相同且最小的工人,选择下标更小的一位工人。

一位工人只能被选择一次。

返回雇佣恰好 k 位工人的总代价。

示例 1:

输入:costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4

输出:11

解释:我们总共雇佣 3 位工人。总代价一开始为 0 。

  • 第一轮雇佣,我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ,有两位工人,我们选择下标更小的一位工人,即第 3 位工人。总代价是 0 + 2 = 2 。
  • 第二轮雇佣,我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ,下标为 4 ,总代价是 2 + 2 = 4 。
  • 第三轮雇佣,我们从 [17,12,10,7,11,20,8] 中选择,最小代价是 7 ,下标为 3 ,总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。

总雇佣代价是 11 。

示例 2:

输入:costs = [1,2,4,1], k = 3, candidates = 3

输出:4

解释:我们总共雇佣 3 位工人。总代价一开始为 0 。

  • 第一轮雇佣,我们从 [1,2,4,1] 中选择。最小代价为 1 ,有两位工人,我们选择下标更小的一位工人,即第 0 位工人,总代价是 0 + 1 = 1 。注意,下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。
  • 第二轮雇佣,我们从 [2,4,1] 中选择。最小代价为 1 ,下标为 2 ,总代价是 1 + 1 = 2 。
  • 第三轮雇佣,少于 3 位工人,我们从剩余工人 [2,4] 中选择。最小代价是 2 ,下标为 0 。总代价为 2 + 2 = 4 。

总雇佣代价是 4 。

提示:

1 <= costs.length <= 105

1 <= costs[i] <= 105

1 <= k, candidates <= costs.length

题解:

方法:模拟

       

class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        int n = costs.length;
        long ans = 0;
        if (candidates * 2 + k > n) {
            Arrays.sort(costs);
            for (int i = 0; i < k; i++) {
                ans += costs[i];
            }
            return ans;
        }

        PriorityQueue<Integer> pre = new PriorityQueue<>();
        PriorityQueue<Integer> suf = new PriorityQueue<>();
        for (int i = 0; i < candidates; i++) {
            pre.offer(costs[i]);
            suf.offer(costs[n - 1 - i]);
        }

        int i = candidates;
        int j = n - 1 - candidates;
        while (k-- > 0) {
            if (pre.peek() <= suf.peek()) {
                ans += pre.poll();
                pre.offer(costs[i++]);
            } else {
                ans += suf.poll();
                suf.offer(costs[j--]);
            }
        }
        return ans;
    }
}

2.雇佣 K 名工人的最低成本

题目链接:857. 雇佣 K 名工人的最低成本

有 n 名工人。 给定两个数组 quality 和 wage ,其中,quality[i] 表示第 i 名工人的工作质量,其最低期望工资为 wage[i] 。

现在我们想雇佣 k 名工人组成一个工资组。在雇佣 一组 k 名工人时,我们必须按照下述规则向他们支付工资:

对工资组中的每名工人,应当按其工作质量与同组其他工人的工作质量的比例来支付工资。

工资组中的每名工人至少应当得到他们的最低期望工资。

给定整数 k ,返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。。

示例 1:

输入: quality = [10,20,5], wage = [70,50,30], k = 2

输出: 105.00000

解释: 我们向 0 号工人支付 70,向 2 号工人支付 35。

示例 2:

输入: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3

输出: 30.66667

解释: 我们向 0 号工人支付 4,向 2 号和 3 号分别支付 13.33333。

提示:

n == quality.length == wage.length

1 <= k <= n <= 104

1 <= quality[i], wage[i] <= 104

题解:

方法:贪心 排序

       

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Integer[] id = new Integer[n];
        Arrays.setAll(id, i -> i);
        // 按照 r 值排序
        Arrays.sort(id, (i, j) -> wage[i] * quality[j] - wage[j] * quality[i]);

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int sumQ = 0;
        for (int i = 0; i < k; i++) {
            pq.offer(quality[id[i]]);
            sumQ += quality[id[i]];
        }

        // 选 r 值最小的 k 名工人
        double ans = sumQ * ((double) wage[id[k - 1]] / quality[id[k - 1]]);

        // 后面的工人 r 值更大
        // 但是 sumQ 可以变小,从而可能得到更优的答案
        for (int i = k; i < n; i++) {
            int q = quality[id[i]];
            if (q < pq.peek()) {
                sumQ -= pq.poll() - q;
                pq.offer(q);
                ans = Math.min(ans, sumQ * ((double) wage[id[i]] / q));
            }
        }
        return ans;
    }
}

3.去掉最低工资和最高工资后的工资平均值

题目链接:1491. 去掉最低工资和最高工资后的工资平均值

给你一个整数数组 salary ,数组里每个数都是 唯一 的,其中 salary[i] 是第 i 个员工的工资。

请你返回去掉最低工资和最高工资以后,剩下员工工资的平均值。

示例 1:

输入:salary = [4000,3000,1000,2000]

输出:2500.00000

解释:最低工资和最高工资分别是 1000 和 4000 。

去掉最低工资和最高工资以后的平均工资是 (2000+3000)/2= 2500

示例 2:

输入:salary = [1000,2000,3000]

输出:2000.00000

解释:最低工资和最高工资分别是 1000 和 3000 。

去掉最低工资和最高工资以后的平均工资是 (2000)/1= 2000

示例 3:

输入:salary = [6000,5000,4000,3000,2000,1000]

输出:3500.00000

示例 4:

输入:salary = [8000,9000,2000,3000,6000,1000]

输出:4750.00000

提示:

3 <= salary.length <= 100

10^3 <= salary[i] <= 10^6

salary[i] 是唯一的。

与真实值误差在 10^-5 以内的结果都将视为正确答案。

题解:

class Solution {
    public double average(int[] salary) {
        int s = 0;
        int m = Integer.MAX_VALUE;
        int M = Integer.MIN_VALUE;
        for (int x : salary) {
            s += x;
            m = Math.min(m, x);
            M = Math.max(M, x);
        }
        int n = salary.length;
        return (double) (s - m - M) / (n - 2);
    }
}

4.规划兼职工作

题目链接:1235. 规划兼职工作

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]。

给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大报酬。

注意,时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束,那么你可以立刻进行在时间 X 开始的下一份工作。

示例 1:

输入:startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]

输出:120

解释:

我们选出第 1 份和第 4 份工作,

时间范围是 [1-3]+[3-6],共获得报酬 120 = 50 + 70。

示例 2:

输入:startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit =

[20,20,100,70,60]

输出:150

解释:

我们选择第 1,4,5 份工作。

共获得报酬 150 = 20 + 70 + 60。

示例 3:

输入:startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]

输出:6

提示:

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4

1 <= startTime[i] < endTime[i] <= 10^9

1 <= profit[i] <= 10^4

题解:

方法:二分查找 动态规划

       

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][];
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]); // 按照结束时间排序

        int[] f = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int j = search(jobs, i, jobs[i][0]);
            f[i + 1] = Math.max(f[i], f[j + 1] + jobs[i][2]);
        }
        return f[n];
    }

    // 返回 endTime <= upper 的最大下标
    private int search(int[][] jobs, int right, int upper) {
        int left = -1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (jobs[mid][1] <= upper) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

5.拆炸弹

题目链接:1652. 拆炸弹

你有一个炸弹需要拆除,时间紧迫!你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。

为了获得正确的密码,你需要替换掉每一个数字。所有数字会 同时 被替换。

如果 k > 0 ,将第 i 个数字用 接下来 k 个数字之和替换。

如果 k < 0 ,将第 i 个数字用 之前 k 个数字之和替换。

如果 k == 0 ,将第 i 个数字用 0 替换。

由于 code 是循环的, code[n-1] 下一个元素是 code[0] ,且 code[0] 前一个元素是 code[n-1] 。

给你 循环 数组 code 和整数密钥 k ,请你返回解密后的结果来拆除炸弹!

示例 1:

输入:code = [5,7,1,4], k = 3

输出:[12,10,16,13]

解释:每个数字都被接下来 3 个数字之和替换。解密后的密码为 [7+1+4, 1+4+5, 4+5+7,

5+7+1]。注意到数组是循环连接的。

示例 2:

输入:code = [1,2,3,4], k = 0

输出:[0,0,0,0]

解释:当 k 为 0 时,所有数字都被 0 替换。

示例 3:

输入:code = [2,4,9,3], k = -2

输出:[12,5,6,13]

解释:解密后的密码为 [3+9, 2+3, 4+2, 9+4] 。注意到数组是循环连接的。如果 k 是负数,那么和为 之前 的数字。

提示:

n == code.length

1 <= n <= 100

1 <= code[i] <= 100

-(n - 1) <= k <= n - 1

题解:

方法:滑动窗口

       

class Solution {
    public int[] decrypt(int[] code, int k) {
        int n = code.length;
        int[] ans = new int[n];
        int r = k > 0 ? k + 1 : n;
        k = Math.abs(k);
        int s = 0;
        for (int i = r - k; i < r; i++) {
            s += code[i]; // 计算 ans[0]
        }
        for (int i = 0; i < n; i++) {
            ans[i] = s;
            s += code[r % n] - code[(r - k) % n];
            r++;
        }
        return ans;
    }
}

下接:【题解】—— LeetCode一周小结19



相关文章
|
1月前
|
索引
【题解】—— LeetCode一周小结41
【题解】—— LeetCode一周小结41
|
2月前
|
机器人
|
2月前
|
人工智能 BI
|
2月前
|
算法
【题解】—— LeetCode一周小结36
LeetCode每日一道一周小结36
|
3月前
|
Perl
|
3月前
|
人工智能 BI
|
4月前
|
算法
|
5月前
|
算法