LeetCode Biweekly Contest 93

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;
    }
}