6939. Max Pair Sum in an Array
给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和 最大 的一对数，且这两个数数位上最大的数字相等。
返回最大和，如果不存在满足题意的数字对，返回 -1 。
测试样例：
输入：nums = [51,71,17,24,42]
输出：88
解释：
i = 1 和 j = 2 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 71 + 17 = 88 。 i = 3 和 j = 4 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 24 + 42 = 66 。可以证明不存在其他数对满足数位上最大的数字相等，所以答案是 88 。
解答：记录一下每个数字的最大数位，然后暴力循环寻找最大和。
class Solution {
public int maxSum(int[] nums) {
HashMap<Integer, List<Integer>> sum = new HashMap<>();
int res = -1;
for (int n : nums) {
int ds = digitSum(n);
if (!sum.containsKey(ds)) {
sum.put(ds, new ArrayList<>());
} else {
List<Integer> arr = sum.get(ds);
for (int old : arr) {
res = Math.max(res, old + n);
}
}
sum.get(ds).add(n);
}
return res;
}
private int digitSum(int n) {
int res = 0;
while (n > 0) {
res = Math.max(res, n % 10);
n /= 10;
}
return res;
}
}6914. Double a Number Represented as a Linked List
给你一个 非空 链表的头节点 head ，表示一个不含前导零的非负数整数。
将链表 翻倍 后，返回头节点 head 。
测试样例：
输入：head = [1,8,9]
输出：[3,7,8]
解释：
表示数字 189 。返回的链表表示数字 189 * 2 = 378 。
解答：这道题目需要仔细一点，本质上就是链表表示的数字之和。构建2个函数：翻转链表和相加，可以比较快速的得到结果。
class Solution {
public ListNode doubleIt(ListNode head) {
ListNode r = reverse(head);
ListNode res = addTwoNumbers(r, r);
return reverse(res);
}
private ListNode reverse(ListNode head) {
ListNode pre = null, t = head;
while(t != null) {
ListNode next = t.next;
t.next = pre;
pre = t;
t = next;
}
return pre;
}
private ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode res = new ListNode(0), cur = res;
int carry = 0;
while (l1 != null && l2 != null) {
int add = l1.val + l2.val + carry;
carry = 0;
if (add >= 10) {
carry = 1;
add -= 10;
}
cur.next = new ListNode(add);
cur = cur.next;
l1 = l1.next;
l2 = l2.next;
}
ListNode r = l1 == null ? l2 : l1;
while (r != null) {
int add = r.val + carry;
carry = 0;
if (add >= 10) {
add -= 10;
carry = 1;
}
cur.next = new ListNode(add);
cur = cur.next;
r = r.next;
}
if (carry == 1) {
cur.next = new ListNode(1);
}
return res.next;
}
}7022. Minimum Absolute Difference Between Elements With Constraint
给你一个下标从 0 开始的整数数组 nums 和一个整数 x 。
请你找到数组中下标距离至少为 x 的两个元素的 差值绝对值 的 最小值 。
换言之，请你找到两个下标 i 和 j ，满足 abs(i - j) >= x 且 abs(nums[i] - nums[j]) 的值最小。
请你返回一个整数，表示下标距离至少为 x 的两个元素之间的差值绝对值的 最小值 。
测试样例
输入：nums = [4,3,2,4], x = 2
输出：0
解释：
我们选择 nums[0] = 4 和 nums[3] = 4 。它们下标距离满足至少为 2 ，差值绝对值为最小值 0 。0 是最优解。
解答：Java存在红黑树。利用红黑树，这道题目就相当简单的。遍历数组，然后将之前的满足距离要求的数字放入红黑树。利用红黑树寻找最接近当前数字的数字就可以了。
class Solution {
public int minAbsoluteDifference(List<Integer> _nums, int x) {
int[] nums = transArr(_nums);
int res = Integer.MAX_VALUE;
TreeSet<Integer> set = new TreeSet<>();
for (int i = x; i < nums.length; ++i) {
set.add(nums[i - x]);
Integer ceil = set.ceiling(nums[i]), floor = set.floor(nums[i]);
if (ceil != null) {
res = Math.min(res, ceil - nums[i]);
}
if (floor != null) {
res = Math.min(res, nums[i] - floor);
}
}
return res;
}
private int[] transArr(List<Integer> _nums) {
int[] nums = new int[_nums.size()];
int p = 0;
for (int n : _nums) {
nums[p++] = n;
}
return nums;
}
}7023. Apply Operations to Maximize Score
给你一个长度为 n 的正整数数组 nums 和一个整数 k 。
一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大：
- 选择一个之前没有选过的 非空 子数组 nums[l, ..., r] 。
- 从 nums[l, ..., r] 里面选择一个 质数分数 最高的元素 x 。如果多个元素质数分数相同且最高，选择下标最小的一个。
- 将你的分数乘以 x 。
nums[l, ..., r] 表示 nums 中起始下标为 l ，结束下标为 r 的子数组，两个端点都包含。
一个整数的 质数分数 等于 x 不同质因子的数目。比方说， 300 的质数分数为 3 ，因为 300 = 2 2 3 5 5 。
请你返回进行至多 k 次操作后，可以得到的 最大分数 。
由于答案可能很大，请你将结果对 10^9 + 7 取余后返回。
测试样例
输入：nums = [8,3,9,3,8], k = 2
输出：81
解释：
进行以下操作可以得到分数 81 ：
- 选择子数组 nums[2, ..., 2] 。nums[2] 是子数组中唯一的元素。所以我们将分数乘以 nums[2] ，分数变为 1 * 9 = 9 。
- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 1 ，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为 9 * 9 = 81 。
81 是可以得到的最高得分。
解答：题目要求最大分数，那么可以利用排序，得到数组的大小关系，然后利用贪婪算法，尽可能的多乘大数。所以现在的问题，就变成了，每个数字有效的区间范围，这个可以利用单调栈来寻找每个数字的有效区间，并计算有效的子数组数量。
最后利用快速乘法，就能获得结果了。友情提示，需要注意一下数字范围，免得超了long范围。
class Solution {
private static final int mod = 1_000_000_007;
public int maximumScore(List<Integer> _nums, int k) {
int len = _nums.size();
long[] nums = transArr(_nums);
int[] scores = new int[len];
for (int i = 0; i < nums.length; ++i) {
scores[i] = getScore(nums[i]);
}
long[] effective = new long[len];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < len; ++i) {
while (!stack.isEmpty() && scores[stack.peek()] < scores[i]) {
long tmp = stack.pop();
effective[(int)tmp] = (tmp - (stack.isEmpty() ? -1 : stack.peek())) * (i - tmp);
}
stack.push(i);
}
while (!stack.isEmpty()) {
long tmp = stack.pop();
effective[(int)tmp] = (tmp - (stack.isEmpty() ? -1 : stack.peek())) * (len - tmp);
}
Integer[] sort = new Integer[len];
for (int i = 0; i < sort.length; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> ((int)(nums[b] - nums[a])));
long res = 1;
for (int i : sort) {
long num = nums[i], time = effective[i];
long min = Math.min(time, k);
res = (res * mul(num, min)) % mod;
k -= min;
if (k == 0) {
break;
}
}
return (int)res;
}
private long[] transArr(List<Integer> _nums) {
long[] nums = new long[_nums.size()];
int p = 0;
for (int n : _nums) {
nums[p++] = n;
}
return nums;
}
private int getScore(long n) {
int res = 0;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
++res;
while (n % i == 0) {
n /= i;
}
}
}
if (n != 1) {
++res;
}
return res;
}
private long mul(long n, long time) {
if (time == 0) {
return 1L;
} else if (time == 1) {
return n;
} else {
long tmp = mul(n, time / 2);
long res = (tmp * tmp) % mod;
if (time % 2 == 1) {
res = (res * n) % mod;
}
return res;
}
}
}