目录
一，3386. 按下时间最长的按钮
本题就是求最短的时间间隔下的indexi，如果时间间隔相同，返回最小的indexi。
代码如下：
class Solution {
public int buttonWithLongestTime(int[][] events) {
int pre = 0;
int ans = 0;
int idx = -1;
for(int[] e : events){
int t = e[1] - pre;
if(ans == t && e[0] < idx || ans < t){
ans = t;
idx = e[0];
}
pre = e[1];
}
return idx;
}
}二，3387. 两天自由外汇交易后的最大货币数
本题实际上是一个图论题，这里介绍两种做法：
- 双层图：直接建立一个图计算一次dfs，画个图理解一下：
class Solution {
Map<String, List<Data>> map = new HashMap<>();
String initial;
double ans = 1.0;
public record Data(String key, double val){}
public double maxAmount(String initialCurrency, List<List<String>> pairs1, double[] rates1, List<List<String>> pairs2, double[] rates2) {
//图一的双向边
for(int i=0; i<rates1.length; i++){
List<String> x = pairs1.get(i);
String a = x.get(0), b = x.get(1);
map.computeIfAbsent(a, e -> new ArrayList<Data>()).add(new Data(b, rates1[i]));
map.computeIfAbsent(b, e -> new ArrayList<Data>()).add(new Data(a, 1/rates1[i]));
}
//连单向边
for(String a : map.keySet()){
map.computeIfAbsent(a, e -> new ArrayList<Data>()).add(new Data(a+"2", 1.0));
}
//图二的双向边
for(int i=0; i<rates2.length; i++){
List<String> x = pairs2.get(i);
String a = x.get(0)+"2", b = x.get(1)+"2";
map.computeIfAbsent(a, e->new ArrayList<>()).add(new Data(b, rates2[i]));
map.computeIfAbsent(b, e -> new ArrayList<Data>()).add(new Data(a, 1/rates2[i]));
}
//终点 = initialCurrency+"2"
initial = initialCurrency+"2";
dfs(initialCurrency, "-1", 1.0);
return ans;
}
void dfs(String x, String fa, double s){
if(x.equals(initial)){
ans = Math.max(ans, s);
return;
}
for(Data y : map.getOrDefault(x, new ArrayList<Data>())){
if(!y.key().equals(fa)){
dfs(y.key(), x, s*y.val());
}
}
}
}- Floyd算法：建立两个图，相当于dfs两次，分别计算第一天货币之间的最大汇率（f1[x][y]）和第二天货币之间的最大汇率（f2[x][y]），枚举第一天和第二天交接的货币i，要计算从initialCurrency(简写 t ) 经过转换之后的最大汇率，就是计算max(f1[t][i] * f2[i][t])
代码如下：
class Solution {
public double maxAmount(String initialCurrency, List<List<String>> pairs1, double[] rates1, List<List<String>> pairs2, double[] rates2) {
Map<String, Integer> map = new HashMap<>();
int k = 0;
for(List<String> x : pairs1){
String a = x.get(0), b = x.get(1);
if(!map.containsKey(a)) map.put(a, k++);
if(!map.containsKey(b)) map.put(b, k++);
}
for(List<String> x : pairs2){
String a = x.get(0), b = x.get(1);
if(!map.containsKey(a)) map.put(a, k++);
if(!map.containsKey(b)) map.put(b, k++);
}
double[][] f1 = new double[k][k];
for(int i=0; i<rates1.length; i++){
String a = pairs1.get(i).get(0), b = pairs1.get(i).get(1);
int x = map.get(a), y = map.get(b);
f1[x][y] = rates1[i];
f1[y][x] = 1/rates1[i];
}
for(int a=0; a<k; a++){
for(int x=0; x<k; x++){
for(int y=0; y<k; y++){
if(x!=y && x!=a && y!=a){
f1[x][y] = Math.max(f1[x][a] * f1[a][y], f1[x][y]);
}
}
}
}
int t = map.getOrDefault(initialCurrency, -1);
if(t == -1) return 1.0;
double[][] f2 = new double[k][k];
for(int i=0; i<rates2.length; i++){
String a = pairs2.get(i).get(0), b = pairs2.get(i).get(1);
int x = map.get(a), y = map.get(b);
f2[x][y] = rates2[i];
f2[y][x] = 1/rates2[i];
}
for(int a=0; a<k; a++){
for(int x=0; x<k; x++){
for(int y=0; y<k; y++){
if(x!=y && x!=a && y!=a){
f2[x][y] = Math.max(f2[x][a] * f2[a][y], f2[x][y]);
}
}
}
}
double ans = 1.0;
for(int i=0; i<k; i++){
ans = Math.max(ans, f1[t][i] * f2[i][t]);
}
return ans;
}
}三，3388. 统计数组中的美丽分割
本题判断前前缀是否相同，直接联想到 z函数算法（z[i] = s[:] 和 s[i:] 的最长前缀），由于数据范围较小，可以直接枚举 nums1 和 nums2，nums2 和 nums3 之间的分割点 i，j
- nums1 的范围是 [0，i)
- nums2 的范围是 [i，j)
- nums3 的范围是 [j，n)
按照题目要求，如果nums1是nums2的前缀或者nums2是nums3的前缀，那么它就满足条件，接下来就是如何使用 z函数来判断 x 是否是 y 的前缀（都有一个大前提 y.length > x.length）。
- 对于 nums1 和 nums2 来说，z[i] >= i，z[i] 表示 nums[i:] 和 nums 的最长前缀是 nums[0: z[i]]，如果 z[i] < i，说明 nums[0:z[i]] 是 nums[i:]的最长前缀，不满足nums1是nums2的前缀这一条件。（i >= j-i && z[i] >= i）
- 对于nums2和nums3来说，这里计算z函数它的范围是nums[j:]，和上述一模一样的推理，这里不详写了，结论 n-j >= j-i && z[j-i] >= j-i
代码如下：
class Solution {
//z函数-前前缀的最长长度
int[] zBox(int[] nums){
int n = nums.length;
int[] z = new int[n];
int l = 0, r = 0;
for(int i=1; i<n; i++){
z[i] = i < r ? Math.min(z[i-l], r-i) : 0;
while(i+z[i] < n && nums[z[i]] == nums[i+z[i]]){
z[i]++;
}
if(i + z[i] > r){
l = i;
r = i + z[i];
}
}
return z;
}
public int beautifulSplits(int[] nums) {
int n = nums.length;
int ans = 0;
int[] z0 = zBox(nums);
for(int i=1; i<n; i++){
//Arrays.copyOfRange(数组,l,r) -> [l,r)
int[] z1 = zBox(Arrays.copyOfRange(nums, i, n));
for(int j=i+1; j<n; j++){
if(i<=j-i && z0[i] >= i || j-i<=n-j && z1[j-i] >= j-i){
ans++;
}
}
}
return ans;
}
}四，3389. 使字符频率相等的最少操作次数
本题是一个分类讨论的题，先区分三种操作，（cnt 数组统计每个字符出现次数）：
- 操作一：删除一个字符，cnt[i]--
- 操作二：添加一个字符，cnt[i]++
- 操作三：将一个字符转换成字母表中的下一个字符，cnt[i]-- && cnt[i]++，注：'z' 不能到 'a'
根据上述条件，得到一下结论：
- 操作三 = 操作二 + 操作一，如果在满足一定的条件下，尽可能使用操作三
- 操作三不能连续使用，比如 'a' -> 'b' -> 'c' -> ... -> 'z'，实际效果就是cnt['a']--，cnt['z']++，只需要执行2次，使用操作三，也是要执行25次。不能连续执行操作三，可以联想到打家劫舍，也就是说本题可能使用DP
求将 s 变好的最少操作次数，对于26个字符来说，要么 cnt[i] = 0，要么 cnt[i] = target（target表示最终每个字符出现次数），假设 x，y 是相邻的两个字母，分类讨论：
- 对 x/y 单独执行操作：1. cnt[x] -> target，需要 abs(cnt[x]-target) 次操作；2. cnt[x] -> 0，需要 cnt[x] 次操作一。
- cnt[y] >= target 时，由于使用操作三会使得 cnt[y] 变大，需要额外执行多次操作一将 cnt[y] -> target/0，明显使得操作次数增多，不能使用操作三
- 如果 cnt[y] < target， 有两种情况
- cnt[x] >= target，可以将 cnt[x]、cnt[y] 都变成 target，需要 max(cnt[x]-target，target - cnt[y])
- cnt[x] < target，可以将 cnt[x] 变成 0、cnt[y] 变成 target，需要 max(cnt[x]，target - cnt[y])
这里画了cnt[x] >= target 的两种情况，cnt[x] < target 的两种情况与之类似，可以自己画一画：
得出上述结论后，就可以使用DP计算了，枚举target的值，定义 f[i]: [i，25]的字母出现次数变成target 所需要的操作次数。
- 对字母 i 进行单独操作，f[i] = f[i+1] + min(abs(cnt[i] - target), cnt[i])
- cnt[i+1] < target，可以执行操作三：
- 1. cnt[i] >= target，f[i] = min(f[i]，f[i+2] + max(cnt[x]-target，target - cnt[y]))
- 2. cnt[i] < target，f[i] = min(f[i]，f[i+2] + max(cnt[x]，target - cnt[y]))
代码如下:
class Solution {
//枚举 target
//对 x 单个字符进行操作:
// cnt[x] -> target, abs(cnt[x]-target)
// cnt[x] -> 0, abs(cnt[x])
//对 x,y 相邻字符进行操作(x < y, cnt[y] < target):
// a->b->c->...不能连续使用3
public int makeStringGood(String s) {
int[] cnt = new int[26];
int mx = 0;
//统计每个字符出现次数 cnt
for(char c : s.toCharArray()){
cnt[c-'a']++;
mx = Math.max(mx, cnt[c-'a']);
}
int ans = Integer.MAX_VALUE;
int[] f = new int[27];
//枚举 target
for(int t=0; t<=mx; t++){
f[25] = Math.min(cnt[25], Math.abs(cnt[25]-t));
for(int i=24; i>=0; i--){
int x = cnt[i];
int y = cnt[i+1];
f[i] = f[i+1] + Math.min(x, Math.abs(x-t));
if(y < t){
if(x >= t)
f[i] = Math.min(f[i], f[i+2]+Math.max(x-t,t-y));
else
f[i] = Math.min(f[i], f[i+2]+Math.max(x,t-y));
}
}
ans = Math.min(ans, f[0]);
}
return ans;
}
}