前言

既然你可以获得幸福
那就去抓紧幸福
不然我们根本没法接受

整体评价

t1, t2有些简单，t3有点意思（自定义比较函数），t4经典单调栈题

这场整体难度稍低，适合节日热身训练

1. 仅执行一次字符串交换能否使两个字符串相等

1790. 仅执行一次字符串交换能否使两个字符串相等

模拟题吧，就是找不同，可以保存所有不同的索引，然后特例枚举2个不同的情况.

Java

class Solution {
    
    public boolean areAlmostEqual(String s1, String s2) {

        List<Integer> arr = new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            if (c1 != c2) {
                arr.add(i);
            }
        }
        
        if (arr.size() == 0) return true;
        if (arr.size() == 1 || arr.size() > 2) return false;
        
        int k1 = arr.get(0), k2 = arr.get(1);
        
        return s1.charAt(k1) == s2.charAt(k2) && s1.charAt(k2) == s2.charAt(k1);
        
    }
    
}

2. 找出星型图的中心节点

1791. 找出星型图的中心节点

简单模拟题，就是统计点的度（无向边的度）

Java

class Solution {
    
    public int findCenter(int[][] edges) {
        
        int n = edges.length + 1;
        int[] deg = new int[n+1];
        
        for (int[] e: edges) {
            deg[e[0]]++;
            deg[e[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if(deg[i] == n - 1) return i;
        }
        // unreachable
        return 0;
    }
    
}

3. 最大平均通过率

1792. 最大平均通过率

算是模拟+贪心，使用优先队列，但这题有点意思。

它不是按照分子/分母的最小值去贪心

而是递增量的概念

令 $C_{i} = A_{i} / B_{i}$ ， $A_{i} 是分子， B_{i} 是分母$

则 $D (i) = C_{i + 1} - C_{i} = (A_{i} + 1) / (B_{i} + 1) - A_{i} / B_{i}$

然后根据 $D_{i} {0 \leq i < n}$ 按大的排序

就是按照收益增量最大的贪心+模拟

Java

class Solution {
    
    public double maxAverageRatio(int[][] classes, int extraStudents) {

        // 模拟吗？
        int n = classes.length;
        
        PriorityQueue<Integer> pp = new PriorityQueue<>((a, b) -> {
            int[] t1 = classes[a], t2 = classes[b];
            
            double res1 = (1l * (t1[0] + 1) * t1[1]  - 1l * (t1[1] + 1) * t1[0]) * 1.0 / (1l * (t1[1] + 1) * t1[1]);
            double res2 = (1l * (t2[0] + 1) * t2[1]  - 1l * (t2[1] + 1) * t2[0]) * 1.0 / (1l * (t2[1] + 1) * t2[1]);
            
            if (res1 != res2) return res1 < res2 ? 1 : -1;
            return 0;
        });
        for (int i = 0; i < n; i++) {
            pp.offer(i);
        }
        
        while (extraStudents > 0) {
            int cur = pp.poll();
            extraStudents--;
            classes[cur][0]++;
            classes[cur][1]++;
            pp.offer(cur);
        }
        
        double acc = 0;
        for (int[] c: classes) {
            acc += 1.0 * c[0] / c[1];
        }
        
        return acc / n;
        
    }
    
    
}

4. 好子数组的最大分数

1793. 好子数组的最大分数

这种多因子的最优解，常规的做法就是固定一个变量，然后求最优解。

那这题固定的变量是啥呢，就是枚举最小值，假设某个值为最小值，那就覆盖的区间越大越好

求这个区间范围最大，就是单调栈的经典使用了。

从左侧维护递增的单调栈，均摊 $O (1)$ 找到左边界
同理从右侧维护递增的单调栈，均摊 $O (1)$ 找到右边界

Java

class Solution {
    
    public int maximumScore(int[] nums, int k) {
    
        // 单调栈应用
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            
            if (stack.isEmpty()) left[i] = 0;
            else left[i] = stack.peek() + 1;
            
            stack.push(i);
        }
        
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            
            if (stack.isEmpty()) right[i] = n - 1;
            else right[i] = stack.peek() - 1;
            
            stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (left[i] <= k && right[i] >= k) {
                ans = Math.max(ans, (right[i] - left[i] + 1) * nums[i]);
            }
        }
        
        return ans;
        
    }
    
}