LeetCode Contest 428

欢迎大家加QQ群：623375442，可以方便群里面交流。今天状态太差了。

100474. Button with Longest Push Time

给你一个二维数组 events，表示孩子在键盘上按下一系列按钮触发的按钮事件。

每个 events[i] = [indexi, timei] 表示在时间 timei 时，按下了下标为 indexi 的按钮。

• 数组按照 time 的递增顺序排序。
• 按下一个按钮所需的时间是连续两次按钮按下的时间差。按下第一个按钮所需的时间就是其时间戳。

返回按下时间 最长 的按钮的 index。如果有多个按钮的按下时间相同，则返回 index 最小的按钮。

测试样例：

输入：events = [[1,2],[2,5],[3,9],[1,15]]

输出：1

解释：

• 下标为 1 的按钮在时间 2 被按下。
• 下标为 2 的按钮在时间 5 被按下，因此按下时间为 5 - 2 = 3。
• 下标为 3 的按钮在时间 9 被按下，因此按下时间为 9 - 5 = 4。
• 下标为 1 的按钮再次在时间 15 被按下，因此按下时间为 15 - 9 = 6。

最终，下标为 1 的按钮按下时间最长，为 6。

解答：按照题意，暴力计算。

class Solution {
    public int buttonWithLongestTime(int[][] events) {
        int time = Integer.MIN_VALUE, last = 0;
        int index = 0;
        for (int[] e : events) {
            int diff = e[1] - last;
            if (diff > time) {
                time = diff;
                index = e[0];
            } else if (diff == time) {
                index = Math.min(index, e[0]);
            }
            last = e[1];
        }
        return index;
    }
}

100458. Maximize Amount After Two Days of Conversions

给你一个字符串 initialCurrency，表示初始货币类型，并且你一开始拥有 1.0 单位的 initialCurrency。

另给你四个数组，分别表示货币对（字符串）和汇率（实数）：

• pairs1[i] = [startCurrencyi, targetCurrencyi] 表示在 第 1 天，可以按照汇率 rates1[i] 将 startCurrencyi 转换为 targetCurrencyi。
• pairs2[i] = [startCurrencyi, targetCurrencyi] 表示在 第 2 天，可以按照汇率 rates2[i] 将 startCurrencyi 转换为 targetCurrencyi。
• 此外，每种 targetCurrency 都可以以汇率 1 / rate 转换回对应的 startCurrency。

你可以在 第 1 天 使用 rates1 进行任意次数的兑换（包括 0 次），然后在 第 2 天 使用 rates2 再进行任意次数的兑换（包括 0 次）。

返回在两天兑换后，最大可能拥有的 initialCurrency 的数量。

注意：汇率是有效的，并且第 1 天和第 2 天的汇率之间相互独立，不会产生矛盾。

测试样例：

输入：initialCurrency = "EUR", pairs1 = [["EUR","USD"],["USD","JPY"]], rates1 = [2.0,3.0], pairs2 = [["JPY","USD"],["USD","CHF"],["CHF","EUR"]], rates2 = [4.0,5.0,6.0]

输出：720

解释：根据题目要求，需要最大化最终的 EUR 数量，从 1.0 EUR 开始：

• 第 1 天：
  • 将 EUR 换成 USD，得到 2.0 USD。
  • 将 USD 换成 JPY，得到 6.0 JPY。
• 第 2 天：
  • 将 JPY 换成 USD，得到 24.0 USD。
  • 将 USD 换成 CHF，得到 120.0 CHF。

最后将 CHF 换回 EUR，得到 720.0 EUR。

解答：两次图遍历，利用DFS寻找最大的汇率转换。

class Solution {
    public double maxAmount(String initialCurrency, List<List<String>> pairs1, double[] rates1, List<List<String>> pairs2, double[] rates2) {
        HashMap<String, HashMap<String, Double>> g1 = getGraph(pairs1, rates1), g2 = getGraph(pairs2, rates2);
        HashMap<String, Double> firstDayMem = new HashMap<>();
        getMax(initialCurrency, 1.0, firstDayMem, g1);
        double res = 1.0;
        for (Map.Entry<String, Double> firstDay : firstDayMem.entrySet()) {
            HashMap<String, Double> secondDayMem = new HashMap<>();
            getMax(firstDay.getKey(), firstDay.getValue(), secondDayMem, g2);
            res = Math.max(res, secondDayMem.getOrDefault(initialCurrency, 0.0));
        }
        return res;
    }

    private HashMap<String, HashMap<String, Double>> getGraph(List<List<String>> pairs, double[] rate) {
        int pos = 0;
        HashMap<String, HashMap<String, Double>> res = new HashMap<>();
        for (List<String> pair : pairs) {
            if (!res.containsKey(pair.get(0))) {
                res.put(pair.get(0), new HashMap<>());
            }
            res.get(pair.get(0)).put(pair.get(1), rate[pos]);
            if (!res.containsKey(pair.get(1))) {
                res.put(pair.get(1), new HashMap<>());
            }
            res.get(pair.get(1)).put(pair.get(0), 1 / rate[pos]);
            ++pos;
        }
        return res;
    }

    private void getMax(String cur, double val, HashMap<String, Double> mem, HashMap<String, HashMap<String, Double>> graph) {
        if (!mem.containsKey(cur) || mem.get(cur) < val) {
            mem.put(cur, val);
            if (graph.containsKey(cur)) {
                for (Map.Entry<String, Double> next : graph.get(cur).entrySet()) {
                    getMax(next.getKey(), val * next.getValue(), mem, graph);
                }
            }
        }
    }
}

100511. Count Beautiful Splits in an Array

给你一个整数数组 nums 。

如果数组 nums 的一个分割满足以下条件，我们称它是一个 美丽 分割：

1. 数组 nums 分为三段 非空子数组：nums1 ，nums2 和 nums3 ，三个数组 nums1 ，nums2 和 nums3 按顺序连接可以得到 nums 。
2. 子数组 nums1 是子数组 nums2 的前缀 或者 nums2 是 nums3 的前缀。

请你返回满足以上条件的分割 数目 。

子数组 指的是一个数组里一段连续 非空 的元素。

前缀 指的是一个数组从头开始到中间某个元素结束的子数组。

测试样例：

输入：nums = [1,2], k = 1

输出：3

解释：美丽分割如下：

1. nums1 = [1] ，nums2 = [1,2] ，nums3 = [1] 。
2. nums1 = [1] ，nums2 = [1] ，nums3 = [2,1] 。

解答：前缀hash可以轻松过。有点hash碰撞的问题，就暴力多几个前缀hash，强行过了。

class Solution {
    private static final int[] mul = {53, 67, 109};
    private static final int[] inv = {56603774, 686567169, 9174312};

    public int beautifulSplits(int[] nums) {
        RangeHash[] hashs = new RangeHash[3];
        for (int i = 0; i < 3; ++i) {
            hashs[i] = new RangeHash(nums, mul[i], inv[i]);
        }
        int res = 0;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i + 2; j < nums.length; ++j) {
                int[] r1 = {0, i}, r2 = {i + 1, j - 1}, r3 = {j, nums.length - 1};
                boolean isValid = false;
                if (isEqual(hashs, r1, r2)) {
                    isValid = true;
                }
                if (isEqual(hashs, r2, r3)) {
                    isValid = true;
                }
                if (isValid) {
                    ++res;
                }
            }
        }
        return res;
    }

    private boolean isEqual(RangeHash[] hashs, int[] r1, int[] r2) {
        if (r1[1] - r1[0] <= r2[1] - r2[0]) {
            for (RangeHash hash : hashs) {
                if (hash.getRangeHash(r1[0], r1[1]) != hash.getRangeHash(r2[0], r2[0] + (r1[1] - r1[0]))) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
}

class RangeHash {
    private static final int mod = 1_000_000_007;
    private int oneMul;
    private int inv;
    private long[] prefix, div;

    public RangeHash(int[] word, int oneMul, int inv) {
        this.oneMul = oneMul;
        this.inv = inv;
        prefix = new long[word.length + 1];
        div = new long[word.length + 1];
        long mul = oneMul;
        div[0] = 1;
        for (int i = 0; i < word.length; ++i) {
            int t = word[i];
            prefix[i + 1] = (prefix[i] + t * mul) % mod;
            mul = (mul * oneMul) % mod;
            div[i + 1] = div[i] * inv % mod;
        }
    }

    public long getRangeHash(int st, int ed) {
        long diff = (prefix[ed + 1] - prefix[st] + mod) % mod;
        return diff * div[st] % mod;
    }
}

100480. Minimum Operations to Make Character Frequencies Equal

给你一个字符串 s 。

如果字符串 t 中的字符出现次数相等，那么我们称 t 为 好的 。

你可以执行以下操作 任意次 ：

• 从 s 中删除一个字符。
• 往 s 中添加一个字符。
• 将 s 中一个字母变成字母表中下一个字母。

注意 ，第三个操作不能将 'z' 变为 'a' 。

请你返回将 s 变 好 的 最少 操作次数。

测试样例：

输入：s = "acab"

输出：1

删掉一个字符 'a' ，s 变为好的。

解答：这题着实难度不大。一共26个字符，然后s.length <= 2 * 10^4。直接暴力枚举所有可能性，最小变化次数。每个位置就2种可能，补齐到当前可能或者清空。利用动态规划计算一下。

class Solution {
    public int makeStringGood(String s) {
        int[] count = new int[26];
        int max = 0, res = 0;
        for (int i = 0; i < s.length(); ++i) {
            count[s.charAt(i) - 'a'] += 1;
        }
        for (int n : count) {
            max = Math.max(max, n);
            res += n;
        }
        for (int i = 1; i <= max; ++i) {
            res = Math.min(res, minimum(count, i));
        }
        return res;
    }

    private int minimum(int[] count, int target) {
        Integer[][] dp = new Integer[26][2];
        return minimumDp(count, dp, 0, 0, target);
    }

    private int minimumDp(int[] count, Integer[][] dp, int pos, int carry, int target) {
        if (pos == 26) {
            return carry;
        }
        int o = carry > 0 ? 1 : 0;
        if (dp[pos][o] == null) {
            // 当前为0或者target，跳过，把上一个第三个操作的buffer清空
            if (count[pos] == 0 || count[pos] == target) {
                dp[pos][o] = carry + minimumDp(count, dp, pos + 1, 0, target);
            // 这种情况最复杂，选择补齐或者进入buffer
            } else if (count[pos] < target) {
                int add = addCarry(count[pos], carry, target);
                dp[pos][o] = Math.min(add + minimumDp(count, dp, pos + 1, 0, target),
                        carry + minimumDp(count, dp, pos + 1, count[pos], target));
            // 过大，直接delete或者进入buffer到和目标一致。
            } else {
                dp[pos][o] = carry + minimumDp(count, dp, pos + 1, count[pos] - target, target);
            }
        }
        return dp[pos][o];
    }

    private int addCarry(int cur, int carry, int target) {
        if (cur + carry >= target) {
            return carry;
        } else {
            return target - cur;
        }
    }
}