[Leetcode Weekly Contest]320

链接：LeetCode

[Leetcode]2475. 数组中不等三元组的数目

给你一个下标从 0 开始的正整数数组 nums 。请你找出并统计满足下述条件的三元组 (i, j, k) 的数目：

• 0 <= i < j < k < nums.length
• nums[i]、nums[j] 和 nums[k] 两两不同 。
  换句话说：nums[i] != nums[j]、nums[i] != nums[k] 且 nums[j] != nums[k] 。

返回满足上述条件三元组的数目。

class Solution {
    public int unequalTriplets(int[] nums) {
        int n = nums.length, res = 0;
        for(int i=0;i<n;++i) {
            for(int j=i+1;j<n;++j) {
                for(int k=j+1;k<n;++k) {
                    if(nums[i] != nums[j] && nums[i]!=nums[k] && nums[j]!=nums[k]) res++;
                }
            }
        }
        return res;
    }
}

[Leetcode]2476. 二叉搜索树最近节点查询

给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。

请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：

• mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
• maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。
  返回数组 answer 。

中序遍历+二分法。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> nums = new ArrayList<Integer>();
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        dfs(root);
        List<List<Integer>> res = new ArrayList<>();
        for(var query:queries) {
            List<Integer> result = new ArrayList<>();
            result.add(getSmallerOrEqual(query));
            result.add(getLargerOrEqual(query));
            res.add(result);
        }
        return res;
    }

    public void dfs(TreeNode root) {
        if(root == null) return ;
        dfs(root.left);
        nums.add(root.val);
        dfs(root.right);
    }

    public int getSmallerOrEqual(Integer target) {
        int lo = 0, hi = nums.size()-1;
        while(lo<=hi) {
            int mid = lo+((hi-lo) >> 1);
            if(nums.get(mid) <= target) lo = mid + 1;
            else hi = mid -1 ;
        }
        return hi >= 0? nums.get(hi) : -1;
    }

    public int getLargerOrEqual(Integer target) {
        int lo = 0, hi = nums.size()-1;
        while(lo<=hi) {
            int mid = lo+((hi-lo) >> 1);
            if(nums.get(mid) < target) lo = mid + 1;
            else hi = mid -1 ;
        }
        return lo <= nums.size()-1? nums.get(lo) : -1;
    }
}

[Leetcode]2477. 到达首都的最少油耗

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。
每个城市里有一个代表，他们都要去首都参加一个会议。
每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。
城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
请你返回到达首都最少需要多少升汽油。

DFS.
以其中某棵树为例，算法的思想是将叶子节点的代表不断向上运输，直到运输到首都（0节点），每一次运输计算所要消耗的汽油的量。因为汽车的数量一定是足够的（每个节点都会提供一辆车），所以只考虑座位数量的限制。

class Solution {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    long res = 0L;
    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length+1;
        if(n==1) return res;
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for(var road:roads) {
            int from = road[0], to = road[1];
            graph.get(from).add(to);
            graph.get(to).add(from);
        }
        dfs(0, -1, seats);
        return res;
    }

    public long dfs(Integer cur, Integer father, Integer seats) {
        long size = 1;
        for(int node:graph.get(cur)) {
            if (node != father){
                size += dfs(node,cur,seats);
            }
        }
        if(cur != 0) res += ((size-1) / seats) + 1;
        return size;
    }
}

[Leetcode]2478. 完美分割的方案数

给你一个字符串 s ，每个字符是数字 '1' 到 '9' ，再给你两个整数 k 和 minLength 。
如果对 s 的分割满足以下条件，那么我们认为它是一个 完美 分割：
s 被分成 k 段互不相交的子字符串。
每个子字符串长度都 至少 为 minLength 。
每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数 数字。质数数字为 '2' ，'3' ，'5' 和 '7' ，剩下的都是非质数数字。
请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 \(10^9 + 7\) 取余 后的结果。
一个 子字符串 是字符串中一段连续字符串序列。

动态规划 + 前缀和。

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int beautifulPartitions(String S, int k, int l) {
        var s = S.toCharArray();
        var n = s.length;
        if (k * l > n || !isPrime(s[0]) || isPrime(s[n - 1])) // 剪枝
            return 0;
        var f = new int[k + 1][n + 1];
        f[0][0] = 1;
        for (var i = 1; i <= k; ++i) {
            var sum = 0;
            // 优化：枚举的起点和终点需要给前后的子串预留出足够的长度
            for (var j = i * l; j + (k - i) * l <= n; j++) {
                if (canPartition(s, j - l)) sum = (sum + f[i - 1][j - l]) % MOD; // j'=j-l 双指针
                if (canPartition(s, j)) f[i][j] = sum;
            }
        }
        return f[k][n];
    }

    private boolean isPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }

    // 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）
    private boolean canPartition(char[] s, int j) {
        return j == 0 || j == s.length || !isPrime(s[j - 1]) && isPrime(s[j]);
    }
}

参考：LeetCode