LeetCode Contest 341

6376. Row With Maximum Ones

给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。

如果有多行包含最多的 1 ，只需要选择 行下标最小 的那一行。

返回一个由行下标和该行中 1 的数量组成的数组。

测试样例

输入：mat = [[0,1],[1,0]]

输出：[0,1]

解释：两行中 1 的数量相同。所以返回下标最小的行，下标为 0 。该行 1 的数量为 1 。所以，答案为 [0,1] 。

解答：暴力计算每一行1的个数，然后判断最大值

class Solution {
    public int[] rowAndMaximumOnes(int[][] mat) {
        int offset = 0;
        int[] res = {-1,-1};
        for (int[] r : mat) {
            int c = 0;
            for (int n : r) {
                c += n;
            }
            if (c > res[1]) {
                res[0] = offset;
                res[1] = c;
            }
            ++offset;
        }
        return res;
    }
}

6350. Find the Maximum Divisibility Score

给你两个下标从 0 开始的整数数组 nums 和 divisors 。

divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。

返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。

测试样例：

输入：nums = [4,7,9,3,9], divisors = [5,2,3]

输出：3

解释：
divisors 中每个元素的可整除性得分为：

1. divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 5 整除。
2. divisors[1] 的可整除性得分为 1 ，因为 nums[0] 能被 2 整除。
3. divisors[2] 的可整除性得分为 3 ，因为 nums[2]、nums[3] 和 nums[4] 都能被 3 整除。

因此，返回 divisors[2] ，它的可整除性得分最大。

解答：有条件：1 <= nums.length, divisors.length <= 1000， 暴力遍历计算count就可以了

class Solution {
    public int maxDivScore(int[] nums, int[] divisors) {
        int maxScore = -1, div = -1;
        for (int d : divisors) {
            int c = 0;
            for (int n : nums) {
                if (n % d == 0) {
                    ++c;
                }
            }
            if (c > maxScore) {
                maxScore = c;
                div = d;
            } else if (c == maxScore) {
                div = Math.min(div, d);
            }
        }
        return div;
    }
}

6375. Minimum Additions to Make Valid String

给你一个字符串 word ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 word 有效 需要插入的最少字母数。

如果字符串可以由 "abc" 串联多次得到，则认为该字符串 有效 。

测试样例

输入：word = "b"

输出：2

解释：

在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。

解答：记录一下当前位置应该出现的字母。如果不符合，那res += 1。否则进入下一位判断。需要注意的是：还需要判断一下word遍历完毕之后，abc是否也同时刚好遍历完一次。否则还需要在word末尾填补。

class Solution {
    public int addMinimum(String word) {
        int count = 0, res = 0;
        int pos = 0;
        while (pos < word.length()) {
            if (word.charAt(pos) - 'a' != count) {
                ++res;
            } else {
                ++pos;
            }
            count = (count + 1) % 3;
        }
        while (count != 0) {
            count = (count + 1) % 3;
            ++res;
        }
        return res;
    }
}

6378. Minimize the Total Price of the Trips

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

测试样例

输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]

输出：23

解释：

• 第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
• 第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
• 第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。

所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。

解答：首先这道题目是一颗树，所以每一次trip的路线是固定的（否则必然存在引入额外节点的问题，cost只会单向上升）。这样我们第一步直接将每一次trip会途径的点遍历出来，然后生成一个count数组（即每个节点在完成所有trip，需要途径的次数）。我在竞赛的时候偷懒了，直接暴力遍历了trip，实际上应该有更好的算法。

生成count数组之后，这道题目就变成一道动态规划题了。因为目标是选择一些非相邻节点价格减半，同时要所有旅行的最小价格总和。我们可以利用动态规划，记录当前节点减半和不减半 2 种可能。然后计算得出最小值。

class Solution {
    private List<Integer>[] edges;
    private Integer[][] mem;
    private int[] count, price;

    public int minimumTotalPrice(int n, int[][] _edges, int[] price, int[][] trips) {
        if (n == 1) {
            int res = 0;
            for (int[] t : trips) {
                res += price[0] / 2;
            }
            return res;
        }

        edges = new List[n];
        for (int i = 0; i < n; ++i) {
            edges[i] = new ArrayList<>();
        }
        for (int[] e : _edges) {
            edges[e[0]].add(e[1]);
            edges[e[1]].add(e[0]);
        }
        this.price = price;

        this.count = new int[n];
        for (int[] t : trips) {
            LinkedList<Integer> path = new LinkedList<>();
            boolean[] isMet = new boolean[n];
            dfsTrip(t[0], t[1], path, isMet);
            for (int i : path) {
                count[i] += 1;
            }
        }
        mem = new Integer[n][2];
        return dfsPrice(_edges[0][0], 0, -1);
    }

    public boolean dfsTrip(int node1, int node2, LinkedList<Integer> path, boolean[] isMet) {
        if (isMet[node1]) {
            return false;
        }
        isMet[node1] = true;
        path.add(node1);
        if (node1 == node2) {
            return true;
        }
        for (int n : edges[node1]) {
            if (dfsTrip(n, node2, path, isMet)) {
                return true;
            }
        }
        path.removeLast();
        return false;
    }

    private int dfsPrice(int node, int last, int previousNode) {
        if (mem[node][last] == null) {
            mem[node][last] = price[node] * count[node];
            for (int i : edges[node]) {
                if (i != previousNode) {
                    mem[node][last] += dfsPrice(i, 0, node);
                }
            }
            if (last == 0) {
                int tmp = price[node] * count[node] / 2;
                for (int i : edges[node]) {
                    if (i != previousNode) {
                        tmp += dfsPrice(i, 1, node);
                    }
                }
                mem[node][last] = Math.min(mem[node][last], tmp);
            }
        }
        return mem[node][last];
    }
}