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

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

🌟欢迎来到 我的博客 —— 探索技术的无限可能!

🌟博客的简介(文章目录)


【题解】—— 每日一道题目栏


上接:【题解】—— LeetCode一周小结40

7.最低加油次数

题目链接:871. 最低加油次数

汽车从起点出发驶向目的地,该目的地位于出发位置东面 target 英里处。

沿途有加油站,用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处,并且有 fueli 升汽油。

假设汽车油箱的容量是无限的,其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时,它可能停下来加油,将所有汽油从加油站转移到汽车中。

为了到达目的地,汽车所必要的最低加油次数是多少?如果无法到达目的地,则返回 -1 。

注意:如果汽车到达加油站时剩余燃料为 0,它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0,仍然认为它已经到达目的地。

示例 1:

输入:target = 1, startFuel = 1, stations = []

输出:0

解释:可以在不加油的情况下到达目的地。

示例 2:

输入:target = 100, startFuel = 1, stations = [[10,100]]

输出:-1

解释:无法抵达目的地,甚至无法到达第一个加油站。

示例 3:

输入:target = 100, startFuel = 10, stations =

[[10,60],[20,30],[30,30],[60,40]]

输出:2

解释:

出发时有 10 升燃料。

开车来到距起点 10 英里处的加油站,消耗 10 升燃料。将汽油从 0 升加到 60 升。

然后,从 10 英里处的加油站开到 60 英里处的加油站(消耗 50 升燃料),

并将汽油从 10 升加到 50 升。然后开车抵达目的地。

沿途在两个加油站停靠,所以返回 2 。

提示:

1 <= target, startFuel <= 109

0 <= stations.length <= 500

1 <= positioni < positioni+1 < target

1 <= fueli < 109

题解:

方法:贪心

       

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.length;
        int ans = 0;
        int prePosition = 0;
        int curFuel = startFuel;
        PriorityQueue<Integer> fuelHeap = new PriorityQueue<>((a, b) -> b - a); // 最大堆
        for (int i = 0; i <= n; i++) {
            int position = i < n ? stations[i][0] : target;
            curFuel -= position - prePosition; // 每行驶 1 英里用掉 1 升汽油
            while (!fuelHeap.isEmpty() && curFuel < 0) { // 没油了
                curFuel += fuelHeap.poll(); // 选油量最多的油桶
                ans++;
            }
            if (curFuel < 0) { // 无法到达
                return -1;
            }
            fuelHeap.offer(i < n ? stations[i][1] : 0); // 留着后面加油
            prePosition = position;
        }
        return ans;
    }
}

8.旅行终点站

题目链接:1436. 旅行终点站

给你一份旅游线路图,该线路图中的旅行线路用数组 paths 表示,其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站,即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路,因此恰有一个旅行终点站。

示例 1:

输入:paths = [[“London”,“New York”],[“New York”,“Lima”],[“Lima”,“Sao

Paulo”]]

输出:“Sao Paulo”

解释:从 “London” 出发,最后抵达终点站 “Sao Paulo” 。本次旅行的路线是 “London” -> “New York”

-> “Lima” -> “Sao Paulo” 。

示例 2:

输入:paths = [[“B”,“C”],[“D”,“B”],[“C”,“A”]]

输出:“A”

解释:所有可能的线路是:

“D” -> “B” -> “C” -> “A”.

“B” -> “C” -> “A”.

“C” -> “A”.

“A”.

显然,旅行终点站是 “A” 。

示例 3:

输入:paths = [[“A”,“Z”]]

输出:“Z”

提示:

1 <= paths.length <= 100

paths[i].length == 2

1 <= cityAi.length, cityBi.length <= 10

cityAi != cityBi

所有字符串均由大小写英文字母和空格字符组成。

题解:

方法:两次遍历

       

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> setA = new HashSet<>(paths.size()); // 预分配空间
        for (List<String> p : paths) {
            setA.add(p.get(0));
        }
        for (List<String> p : paths) {
            if (!setA.contains(p.get(1))) {
                return p.get(1);
            }
        }
        return "";
    }
}

9.找到按位或最接近 K 的子数组

题目链接:3171. 找到按位或最接近 K 的子数组

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个

子数组

,满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之,你需要选择一个子数组 nums[l…r] 满足 |k - (nums[l] OR nums[l + 1] … OR nums[r])| 最小。

请你返回 最小 的绝对差值。

子数组 是数组中连续的 非空 元素序列。

示例 1:

输入:nums = [1,2,4,5], k = 3

输出:0

解释:

子数组 nums[0…1] 的按位 OR 运算值为 3 ,得到最小差值 |3 - 3| = 0 。

示例 2:

输入:nums = [1,3,1,3], k = 2

输出:1

解释:

子数组 nums[1…1] 的按位 OR 运算值为 3 ,得到最小差值 |3 - 2| = 1 。

示例 3:

输入:nums = [1], k = 10

输出:9

解释:

只有一个子数组,按位 OR 运算值为 1 ,得到最小差值 |10 - 1| = 9 。

提示:

1 <= nums.length <= 105

1 <= nums[i] <= 109

1 <= k <= 109

题解:

方法:滑动窗口

       

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        int left = 0;
        int bottom = 0;
        int rightOr = 0;
        for (int right = 0; right < nums.length; right++) {
            rightOr |= nums[right];
            while (left <= right && (nums[left] | rightOr) > k) {
                ans = Math.min(ans, (nums[left] | rightOr) - k);
                left++;
                if (bottom < left) {
                    // 重新构建一个栈
                    for (int i = right - 1; i >= left; i--) {
                        nums[i] |= nums[i + 1];
                    }
                    bottom = right;
                    rightOr = 0;
                }
            }
            if (left <= right) {
                ans = Math.min(ans, k - (nums[left] | rightOr));
            }
        }
        return ans;
    }
}

10.优质数对的总数 I

题目链接:3162. 优质数对的总数 I

给你两个整数数组 nums1 和 nums2,长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以除尽 nums2[j] * k,则称数对 (i, j) 为 优质数对(0 <= i <= n - 1, 0 <= j <= m - 1)。

返回 优质数对 的总数。

示例 1:

输入:nums1 = [1,3,4], nums2 = [1,3,4], k = 1

输出:5

解释:

5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2:

输入:nums1 = [1,2,4,12], nums2 = [2,4], k = 3

输出:2

解释:

2个优质数对分别是 (3, 0) 和 (3, 1)

提示:

1 <= n, m <= 50

1 <= nums1[i], nums2[j] <= 50

1 <= k <= 50

题解:

方法:暴力枚举

       

class Solution {
    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int ans = 0;
        for (int x : nums1) {
            for (int y : nums2) {
                if (x % (y * k) == 0) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

11.优质数对的总数 II

题目链接:3164. 优质数对的总数 II

给你两个整数数组 nums1 和 nums2,长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除,则称数对 (i, j) 为 优质数对(0 <= i <= n - 1, 0 <= j <= m - 1)。

返回 优质数对 的总数。

示例 1:

输入:nums1 = [1,3,4], nums2 = [1,3,4], k = 1

输出:5

解释:

5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2:

输入:nums1 = [1,2,4,12], nums2 = [2,4], k = 3

输出:2

解释:

2个优质数对分别是 (3, 0) 和 (3, 1)。

提示:

1 <= n, m <= 105

1 <= nums1[i], nums2[j] <= 106

1 <= k <= 103

题解:

方法:枚举因子

       

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums1) {
            if (x % k != 0) {
                continue;
            }
            x /= k;
            for (int d = 1; d * d <= x; d++) { // 枚举因子
                if (x % d > 0) {
                    continue;
                }
                cnt.merge(d, 1, Integer::sum); // cnt[d]++
                if (d * d < x) {
                    cnt.merge(x / d, 1, Integer::sum); // cnt[x/d]++
                }
            }
        }
        long ans = 0;
        for (int x : nums2) {
            ans += cnt.getOrDefault(x, 0);
        }
        return ans;
    }
}

12.求出出现两次数字的 XOR 值

题目链接:3158. 求出出现两次数字的 XOR 值

给你一个数组 nums ,数组中的数字 要么 出现一次,要么 出现两次。

请你返回数组中所有出现两次数字的按位 XOR 值,如果没有数字出现过两次,返回 0 。

示例 1:

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

输出:1

解释:

nums 中唯一出现过两次的数字是 1 。

示例 2:

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

输出:0

解释:

nums 中没有数字出现两次。

示例 3:

输入:nums = [1,2,2,1]

输出:3

解释:

数字 1 和 2 出现过两次。1 XOR 2 == 3 。

提示:

1 <= nums.length <= 50

1 <= nums[i] <= 50

nums 中每个数字要么出现过一次,要么出现过两次。

题解:

方法:位运算

       

class Solution {
    public int duplicateNumbersXOR(int[] nums) {
        int ans = 0;
        long vis = 0;
        for (int x : nums) {
            if ((vis >> x & 1) > 0) { // x 在 vis 中
                ans ^= x;
            } else {
                vis |= 1L << x; // 把 x 加到 vis 中
            }
        }
        return ans;
    }
}

13.鸡蛋掉落-两枚鸡蛋

题目链接:1884. 鸡蛋掉落-两枚鸡蛋

给你 2 枚相同 的鸡蛋,和一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ,满足 0 <= f <= n ,任何从 高于 f 的楼层落下的鸡蛋都 会碎 ,从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。

每次操作,你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下(满足 1 <= x <= n)。如果鸡蛋碎了,你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎,则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少?

示例 1:

输入:n = 2

输出:2

解释:我们可以将第一枚鸡蛋从 1 楼扔下,然后将第二枚从 2 楼扔下。

如果第一枚鸡蛋碎了,可知 f = 0;

如果第二枚鸡蛋碎了,但第一枚没碎,可知 f = 1;

否则,当两个鸡蛋都没碎时,可知 f = 2。

示例 2:

输入:n = 100

输出:14

解释: 一种最优的策略是:

  • 将第一枚鸡蛋从 9 楼扔下。如果碎了,那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下,然后每扔一次上一层楼,在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
  • 如果第一枚鸡蛋没有碎,那么再把第一枚鸡蛋从 22 层扔下。如果碎了,那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下,然后每扔一次上一层楼,在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
  • 如果第一枚鸡蛋没有再次碎掉,则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。 不管结果如何,最多需要扔 14 次来确定 f 。

提示:

1 <= n <= 1000

题解:

方法:动态规划

       

class Solution {
    private static final int[] memo = new int[1001];
    public int twoEggDrop(int n) {
        if (n == 0) {
            return 0;
        }
        if (memo[n] > 0) { // 之前计算过
            return memo[n];
        }
        int res = Integer.MAX_VALUE;
        for (int j = 1; j <= n; j++) {
            res = Math.min(res, Math.max(j, twoEggDrop(n - j) + 1));
        }
        return memo[n] = res; // 记忆化
    }
}

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


相关文章
|
1天前
|
机器学习/深度学习
|
1天前
|
人工智能 BI
|
1天前
|
机器学习/深度学习
|
3月前
|
算法
【题解】—— LeetCode一周小结36
LeetCode每日一道一周小结36
|
6月前
|
人工智能 BI
|
6月前
|
算法