2496. Maximum Value of a String in an Array
一个由字母和数字组成的字符串的 值 定义如下：
如果字符串 只 包含数字，那么值为该字符串在 10 进制下的所表示的数字。
否则，值为字符串的 长度 。
给你一个字符串数组 strs ，每个字符串都只由字母和数字组成，请你返回 strs 中字符串的 最大值。测试样例
输入：strs = ["alic3","bob","3","4","00000"]
输出：5
解释：
- "alic3" 包含字母和数字，所以值为长度 5 。
- "bob" 只包含字母，所以值为长度 3 。
- "3" 只包含数字，所以值为 3 。
- "4" 只包含数字，所以值为 4 。
- "00000" 只包含数字，所以值为 0 。
所以最大的值为 5 ，是字符串 "alic3" 的值。
解答: 根据题意，判断字符串是否完全有数字构成。如果是数字，则Integer.valueOf否则获取字符串长度。用max保存当前最大值
class Solution {
public int maximumValue(String[] strs) {
int max = -1;
for (String str : strs) {
if (isAllDigit(str)) {
max = Math.max(Integer.valueOf(str), max);
} else {
max = Math.max(max, str.length());
}
}
return max;
}
private boolean isAllDigit(String str) {
for (int i = 0; i < str.length(); ++i) {
if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
continue;
} else {
return false;
}
}
return true;
}
}2497. Maximum Star Sum of a Graph
给你一个 n 个点的无向图，节点从 0 到 n - 1 编号。给你一个长度为 n 下标从 0 开始的整数数组 vals ，其中 vals[i] 表示第 i 个节点的值。
同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条双向边。
星图是给定图中的一个子图，它包含一个中心节点和 0 个或更多个邻居。换言之，星图是给定图中一个边的子集，且这些边都有一个公共节点。
星和 定义为星图中所有节点值的和。
给你一个整数 k ，请你返回 至多 包含 k 条边的星图中的 最大星和 。
测试样例
输入：vals = [1,2,3,4,10,-10,-20], edges = [[0,1],[1,2],[1,3],[3,4],[3,5],[3,6]], k = 2
输出：16
解释：
最大星和对应的星图在上图中用蓝色标出。中心节点是 3 ，星图中还包含邻居 1 和 4 。
无法得到一个和大于 16 且边数不超过 2 的星图。
解答： 这道题主要考察阅读能力。由于每个点只能获取最大的K个领接点。所以使用一个优先队列记录。然后遍历edges，更新每个点最优的领接节点。最后扫描每个点的数值输出即可。
class Solution {
public int maxStarSum(int[] vals, int[][] edges, int k) {
PriorityQueue<Integer>[] qs = new PriorityQueue[vals.length];
int res = Integer.MIN_VALUE;
for (int i = 0; i < qs.length; ++i) {
qs[i] = new PriorityQueue<>();
res = Math.max(res, vals[i]);
}
for (int[] e : edges) {
qs[e[0]].add(vals[e[1]]);
if (qs[e[0]].size() > k) {
qs[e[0]].poll();
}
qs[e[1]].add(vals[e[0]]);
if (qs[e[1]].size() > k) {
qs[e[1]].poll();
}
}
for (int i = 0; i < qs.length; ++i) {
PriorityQueue<Integer> q = qs[i];
int sum = vals[i];
while (!q.isEmpty()) {
int tmp = q.poll();
if (tmp > 0) {
sum += tmp;
}
}
res = Math.max(res, sum);
}
return res;
}
}2498. Frog Jump II
给你一个下标从 0 开始的整数数组 stones ，数组中的元素 严格递增 ，表示一条河中石头的位置。
一只青蛙一开始在第一块石头上，它想到达最后一块石头，然后回到第一块石头。同时每块石头至多到达 一次。
一次跳跃的 长度 是青蛙跳跃前和跳跃后所在两块石头之间的距离。
- 更正式的，如果青蛙从 $stones[i]$ 跳到 $stones[j]$ ，跳跃的长度为 $|stones[i] - stones[j]|$ 。
一条路径的 代价 是这条路径里的 最大跳跃长度 。请你返回这只青蛙的 最小代价 。
测试样例：
输入：stones = [0,2,5,6,7]输出：5
解释：
这条路径的代价是 5 ，是这条路径中的最大跳跃长度。
无法得到一条代价小于 5 的路径，我们返回 5 。
解答：本质上是一道脑筋急转弯。简单的思路就是出发时，青蛙一次跳的越近，则返程时必然就会更长。所以最优的方案就是间隔着跳来减少距离。贪心即可
class Solution {
public int maxJump(int[] stones) {
int res = Integer.MIN_VALUE;
int last = 0;
for (int i = 0; i < stones.length; i = i + 2) {
res = Math.max(stones[i] - last, res);
last = stones[i];
}
if (last != stones[stones.length - 1]) {
res = Math.max(res, stones[stones.length - 1] - last);
}
last = 0;
for (int i = 1; i < stones.length; i = i + 2) {
res = Math.max(stones[i] - last, res);
last = stones[i];
}
if (last != stones[stones.length - 1]) {
res = Math.max(res, stones[stones.length - 1] - last);
}
return res;
}
}2499. Minimum Total Cost to Make Arrays Unequal
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两者长度都为 n 。
每次操作中，你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的 和 。
你的目标是对于所有的 0 <= i <= n - 1 ，都满足 nums1[i] != nums2[i] ，你可以进行任意次操作，请你返回达到这个目标的 最小 总代价。
请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ，如果无法达成目标，返回 -1 。
测试样例：
输入：nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
输出：10
解释：
实现目标的其中一种方法为：
- 交换下标为 0 和 3 的两个值，代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。
- 交换下标为 1 和 2 的两个值，代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。
- 交换下标为 0 和 4 的两个值，代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。
最后，对于每个下标 i ，都有 nums1[i] != nums2[i] 。总代价为 10 。
还有别的交换值的方法，但是无法得到代价和小于 10 的方案。
解答：这道题目算是这一周最难的一道题目了。它的主要思路其实和大数据里面的quorum read类似。如果要保证一个数据写入成功，则$read + write > total_machine_number$。这道题就是这个思路。你可以把nums1认为是某个数据块写，nums2认为是某个数据块读。一旦满足quorum read，则返回-1。
否则则分析所有相同的位置。如果相同的位置不存在quroum read，则累和。否则需要增加元素，直到quorum不存在。
题目里面，看着转移代价很唬人。其实0号index的节点不会产生代价。所以可以把0号节点作为中转来完成数据转换。
class Solution {
public long minimumTotalCost(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> m1 = count(nums1), m2 = count(nums2);
int len = nums1.length;
for (Map.Entry<Integer, Integer> kv : m1.entrySet()) {
if (len - kv.getValue() < m2.getOrDefault(kv.getKey(), 0)) {
return -1;
}
}
Set<Integer> set = new HashSet<>();
long res = 0;
for (int i = 0; i < len; ++i) {
if (nums1[i] == nums2[i]) {
set.add(i);
res += i;
}
}
HashMap<Integer, Integer> m = count(nums1, set);
for (Map.Entry<Integer, Integer> kv : m.entrySet()) {
if (set.size() - kv.getValue() < kv.getValue()) {
int key = kv.getKey(), l = set.size(), t = kv.getValue() * 2;
for (int i = 0; i < len; ++i) {
if (!set.contains(i) && nums1[i] != key && nums2[i] != key) {
res += i;
++l;
if (l >= t) break;
}
}
}
}
return res;
}
private HashMap<Integer, Integer> count(int[] num) {
HashMap<Integer, Integer> res = new HashMap<>();
for (int i : num) {
res.put(i, res.getOrDefault(i, 0) + 1);
}
return res;
}
private HashMap<Integer, Integer> count(int[] num, Set<Integer> set) {
HashMap<Integer, Integer> res = new HashMap<>();
for (int i : set) {
res.put(num[i], res.getOrDefault(num[i], 0) + 1);
}
return res;
}
}