【题解】—— 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