6990. Account Balance After Rounded Purchase
一开始，你的银行账户里有 100 块钱。
给你一个整数purchaseAmount ，它表示你在一次购买中愿意支出的金额。
在一个商店里，你进行一次购买，实际支出的金额会向 最近 的 10 的 倍数 取整。换句话说，你实际会支付一个 非负 金额 roundedAmount ，满足 roundedAmount 是 10 的倍数且 abs(roundedAmount - purchaseAmount) 的值 最小 。
如果存在多于一个最接近的 10 的倍数，较大的倍数 是你的实际支出金额。
请你返回一个整数，表示你在愿意支出金额为 purchaseAmount 块钱的前提下，购买之后剩下的余额。
注意： 0 也是 10 的倍数。
测试样例
输入：purchaseAmount = 9
输出：9
解释：这个例子中，最接近 9 的 10 的倍数是 10 。所以你的账户余额为 100 - 10 = 90 。
解答：按照题意10的倍数做一下取整。
class Solution {
public int accountBalanceAfterPurchase(int purchaseAmount) {
int remain = 100 - purchaseAmount;
int r = remain / 10, o = r + 1;
if (remain - r * 10 <= o * 10 - remain) {
return r * 10;
} else {
return o * 10;
}
}
}6940. Insert Greatest Common Divisors in Linked List
给你一个链表的头 head ，每个结点包含一个整数值。
在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。
请你返回插入之后的链表。
两个数的 最大公约数 是可以被两个数字整除的最大正整数。
测试样例：
输入：head = [7]
输出：[7]
解释：
没有相邻结点，所以返回初始链表。
解答: 考察最小公约数的计算与链表遍历。
class Solution {
public ListNode insertGreatestCommonDivisors(ListNode head) {
ListNode res = head, cur = head, next = head.next;
while (next != null) {
ListNode add = new ListNode(gcd(cur.val, next.val));
cur.next = add;
add.next = next;
cur = next;
next = next.next;
}
return res;
}
private int gcd(int x, int y) {
while (y != 0) {
int tmp = x % y;
x = y;
y = tmp;
}
return x;
}
}6956. Minimum Seconds to Equalize a Circular Array
给你一个下标从 0 开始长度为 n 的数组 nums 。
每一秒，你可以对数组执行以下操作：
- 对于范围在 [0, n - 1] 内的每一个下标 i ，将 nums[i] 替换成 nums[i] ，nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n] 三者之一。
注意，所有元素会被同时替换。
请你返回将数组 nums 中所有元素变成相等元素所需要的 最少 秒数
测试样例：
输入：nums = [1,2,1,2]
输出：1
解释：
我们可以在 1 秒内将数组变成相等元素：
- 第 1 秒，将每个位置的元素分别变为 [nums[3],nums[1],nums[3],nums[3]] 。变化后，nums = [2,2,2,2] 。
1 秒是将数组变成相等元素所需要的最少秒数。
解答: 这道题目有点脑筋急转弯。选定一个数字之后，那么就可以计算数组中每个数字到达最近选定数字的距离。因为提示给的范围还是比较大的1 <= n == nums.length <= 10^5，不能直接使用暴力算法。所以就把数组按照数字聚合，并记录一下位置。利用一下数学公式可以快速计算出到达选定数字的最短距离。
class Solution {
public int minimumSeconds(List<Integer> nums) {
HashMap<Integer, List<Integer>> map = new HashMap<>();
int offset = 0;
for (int n : nums) {
if (!map.containsKey(n)) {
map.put(n, new ArrayList<>());
}
map.get(n).add(offset++);
}
int res = Integer.MAX_VALUE;
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
List<Integer> pos = entry.getValue();
int internal = (nums.size() - (pos.get(pos.size() - 1) - pos.get(0))) / 2;
for (int i = 1; i < pos.size(); ++i) {
int diff = (pos.get(i) - pos.get(i - 1));
internal = Math.max(internal, diff / 2);
}
res = Math.min(res, internal);
}
return res;
}
}
6987. Minimum Time to Make Array Sum At Most x
给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i] 。操作 完成后 ，你可以进行如下操作：
- 选择任一满足 0 <= i < nums1.length 的下标 i ，并使 nums1[i] = 0 。
同时给你一个整数 x 。
请你返回使 nums1 中所有元素之和 小于等于 x 所需要的 最少 时间，如果无法实现，那么返回 -1 。
测试样例：
输入：nums1 = [1,2,3], nums2 = [1,2,3], x = 4
输出：4
第 1 秒，我们对 i = 0 进行操作，得到 nums1 = [0,2+2,3+3] = [0,4,6] 。
第 2 秒，我们对 i = 1 进行操作，得到 nums1 = [0+1,0,6+3] = [1,0,9] 。
第 3 秒，我们对 i = 2 进行操作，得到 nums1 = [1+1,0+2,0] = [2,2,0] 。
现在 nums1 的和为 4 。不存在更少次数的操作，所以我们返回 3 。
解答: 如果n秒之后，理想的选择能够让数组满足要求，我们就可以停止计算。然后需要思考到，我们最多进行nums1.length次操作（这个时候，所有nums1中的数字都清零了，之后的操作无法减去更多的数字了）。其次还有一个需要思考到，同一个位置最多进行一次操作。否则假设一个位置进行了2次操作，t1和t2。那么t1的那一次操作本质上是没有意义的，只要进行t2的操作就可以了。t1的操作可以让给别的位置以求最大化。
最后我们需要知道理想的选择是如何选择，利用动态规划可以计算出当前位置的最佳选择方案。
class Solution {
public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
nums1 = buildArr(nums1);
nums2 = buildArr(nums2);
long sum1 = getSum(nums1), sum2 = getSum(nums2);
if (sum1 <= x) {
return 0;
}
int len = nums1.size();
Integer[] sort = new Integer[len];
for (int i = 0; i < sort.length; ++i) {
sort[i] = i;
}
List<Integer> finalNums = nums2;
Arrays.sort(sort, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return finalNums.get(o1).compareTo(finalNums.get(o2));
}
});
long[] mem = new long[len];
for (long n = 1; n <= nums1.size(); ++n) {
long[] nextMem = new long[len];
long max = 0;
for (int i = 0; i < len; ++i) {
if (i == 0) {
nextMem[sort[i]] = nums1.get(sort[i]) + nums2.get(sort[i]) * n;
} else {
nextMem[sort[i]] = Math.max(nextMem[sort[i - 1]],
mem[sort[i - 1]] + nums1.get(sort[i]) + nums2.get(sort[i]) * n);
}
max = Math.max(nextMem[sort[i]], max);
}
if (sum1 + sum2 * n - max <= x) {
return (int)n;
}
mem = nextMem;
}
return -1;
}
private long getSum(List<Integer> nums) {
long sum = 0;
for (int n : nums) {
sum += n;
}
return sum;
}
private List<Integer> buildArr(List<Integer> nums) {
List<Integer> res = new ArrayList<>(nums);
return res;
}
}