欢迎大家加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 的一个分割满足以下条件,我们称它是一个 美丽 分割:
- 数组 nums 分为三段 非空子数组:nums1 ,nums2 和 nums3 ,三个数组 nums1 ,nums2 和 nums3 按顺序连接可以得到 nums 。
- 子数组 nums1 是子数组 nums2 的前缀 或者 nums2 是 nums3 的前缀。
请你返回满足以上条件的分割 数目 。
子数组 指的是一个数组里一段连续 非空 的元素。
前缀 指的是一个数组从头开始到中间某个元素结束的子数组。
测试样例:
输入:nums = [1,2], k = 1
输出:3
解释:美丽分割如下:
- nums1 = [1] ,nums2 = [1,2] ,nums3 = [1] 。
- 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;
}
}
}