🌟欢迎来到 我的博客 —— 探索技术的无限可能！
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 的子数组
给你一个数组 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 值
给你一个数组 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; // 记忆化
}
}