周赛 - 😺 第 79 场力扣夜喵双周赛 - 《学习笔记》

6083. 判断一个数的数字计数是否等于数位的值
6084. 最多单词数的发件人
6085. 道路的最大总重要性
10011. 以组为单位订音乐会的门票

鉴于前两次双周赛发挥太差，没参加
然后t4就出了一个我不会的线段树用法，学习一下。

6083. 判断一个数的数字计数是否等于数位的值

给你一个下标从 0 开始长度为 n 的字符串 num ，它只包含数字。
如果对于每个 _0 <= i < n 的下标 i ，都满足数位 _i 在 num 中出现了 num[i]次，那么请你返回 true ，否则返回 false 。

示例 1：
输入：num = “1210” 输出：true 解释： num[0] = ‘1’ 。数字 0 在 num 中出现了一次。 num[1] = ‘2’ 。数字 1 在 num 中出现了两次。 num[2] = ‘1’ 。数字 2 在 num 中出现了一次。 num[3] = ‘0’ 。数字 3 在 num 中出现了零次。 “1210” 满足题目要求条件，所以返回 true 。
示例 2：
输入：num = “030” 输出：false 解释： num[0] = ‘0’ 。数字 0 应该出现 0 次，但是在 num 中出现了一次。 num[1] = ‘3’ 。数字 1 应该出现 3 次，但是在 num 中出现了零次。 num[2] = ‘0’ 。数字 2 在 num 中出现了 0 次。下标 0 和 1 都违反了题目要求，所以返回 false 。

提示：

n == num.length
1 <= n <= 10
num 只包含数字。

思路：
模拟

class Solution {
    public boolean digitCount(String num) {
        int[] cnt = new int[10];
        for (int i = 0; i < num.length(); i++) {
            cnt[num.charAt(i) - '0']++;
        }
        for (int i = 0; i < num.length(); i++) {
            int c = cnt[i];
            if (c != num.charAt(i) - '0')
                return false;
        }
        return true;
    }
}

6084. 最多单词数的发件人

给你一个聊天记录，共包含 n 条信息。给你两个字符串数组 messages 和 senders ，其中 messages[i] 是 senders[i] 发出的一条信息。
一条信息是若干用单个空格连接的单词，信息开头和结尾不会有多余空格。发件人的 单词计数 是这个发件人总共发出的 单词数 。注意，一个发件人可能会发出多于一条信息。
请你返回发出单词数最多的发件人名字。如果有多个发件人发出最多单词数，请你返回 字典序 最大的名字。
注意：

字典序里，大写字母小于小写字母。
“Alice” 和 “alice” 是不同的名字。

示例 1：
输入：messages = [“Hello userTwooo”,”Hi userThree”,”Wonderful day Alice”,”Nice day userThree”], senders = [“Alice”,”userTwo”,”userThree”,”Alice”] 输出：“Alice” 解释：Alice 总共发出了 2 + 3 = 5 个单词。 userTwo 发出了 2 个单词。 userThree 发出了 3 个单词。由于 Alice 发出单词数最多，所以我们返回 “Alice” 。
示例 2：
输入：messages = [“How is leetcode for everyone”,”Leetcode is useful for practice”], senders = [“Bob”,”Charlie”] 输出：“Charlie” 解释：Bob 总共发出了 5 个单词。 Charlie 总共发出了 5 个单词。由于最多单词数打平，返回字典序最大的名字，也就是 Charlie 。

提示：

n == messages.length == senders.length
1 <= n <= 104
1 <= messages[i].length <= 100
1 <= senders[i].length <= 10
messages[i] 包含大写字母、小写字母和 ‘ ‘ 。
messages[i] 中所有单词都由 单个空格 隔开。
messages[i] 不包含前导和后缀空格。
senders[i] 只包含大写英文字母和小写英文字母。

思路：
统计每个人发的单词数，返回发送最大单词数的人名，若有多个，返回字典序大的名字

class Solution {
    public String largestWordCount(String[] messages, String[] senders) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < senders.length; i++) {
            int c = messages[i].split(" ").length;
            map.merge(senders[i], c, Integer::sum);
        }
        int max = 0;
        String res = "";
        for (String s : map.keySet()) {
            int x = map.get(s);
            if (x > max) {
                max = x;
                res = s;
            } else if (x == max && s.compareTo(res) > 0)
                res = s;
        }
        return res;
    }
}

6085. 道路的最大总重要性

给你一个整数 n ，表示一个国家里的城市数目。城市编号为 0 到 n - 1 。
给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] 表示城市 ai 和 bi 之间有一条双向道路。
你需要给每个城市安排一个从 1 到 n 之间的整数值，且每个值只能被使用一次。道路的 重要性 定义为这条道路连接的两座城市数值之和。
请你返回在最优安排下，所有道路重要性 之和最大为多少。

示例 1：

输入：n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]] 输出：43 解释：上图展示了国家图和每个城市被安排的值 [2,4,5,3,1] 。 - 道路 (0,1) 重要性为 2 + 4 = 6 。 - 道路 (1,2) 重要性为 4 + 5 = 9 。 - 道路 (2,3) 重要性为 5 + 3 = 8 。 - 道路 (0,2) 重要性为 2 + 5 = 7 。 - 道路 (1,3) 重要性为 4 + 3 = 7 。 - 道路 (2,4) 重要性为 5 + 1 = 6 。所有道路重要性之和为 6 + 9 + 8 + 7 + 7 + 6 = 43 。可以证明，重要性之和不可能超过 43 。
示例 2：

输入：n = 5, roads = [[0,3],[2,4],[1,3]] 输出：20 解释：上图展示了国家图和每个城市被安排的值 [4,3,2,5,1] 。 - 道路 (0,3) 重要性为 4 + 5 = 9 。 - 道路 (2,4) 重要性为 2 + 1 = 3 。 - 道路 (1,3) 重要性为 3 + 5 = 8 。所有道路重要性之和为 9 + 3 + 8 = 20 。可以证明，重要性之和不可能超过 20 。

提示：

2 <= n <= 5 * 104
1 <= roads.length <= 5 * 104
roads[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
没有重复道路。

思路：
贪心，按连接到每个城市的道路数从小到大排序，并据此分配重要性

class Solution {
    public long maximumImportance(int n, int[][] roads) {
        int[][] cnt = new int[n][2];
        for (int[] r : roads) {
            int a = r[0], b = r[1];
            cnt[a][0]++;
            cnt[b][0]++;
        }
        for (int i = 0; i < n; i++)
            cnt[i][1] = i;
        Arrays.sort(cnt, (o1, o2) -> (o1[0] - o2[0]));
        int[] score = new int[n];
        for (int i = 0; i < n; i++) {
            score[cnt[i][1]] = i + 1;
        }
        long sum = 0;
        for (int[] r : roads) {
            int a = r[0], b = r[1];
            sum += score[a] + score[b];
        }
        return sum;
    }
}

10011. 以组为单位订音乐会的门票

一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：

同一组的 k 位观众坐在 同一排座位，且座位连续 。
k 位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。

由于观众非常挑剔，所以：

只有当一个组里所有成员座位的排数都 小于等于 maxRow ，这个组才能订座位。每一组的 maxRow 可能不同。
如果有多排座位可以选择，优先选择最小的排数。如果同一排中有多个座位可以坐，优先选择号码最小的。

请你实现 BookMyShow 类：

BookMyShow(int n, int m) ，初始化对象，n 是排数，m 是每一排的座位数。
int[] gather(int k, int maxRow) 返回长度为 2 的数组，表示 k 个成员中 第一个座位 的排数和座位编号，这 k 位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的 r 和 c 满足第 r 排中 [c, c + k - 1] 的座位都是空的，且 r <= maxRow 。如果无法安排座位，返回 [] 。
boolean scatter(int k, int maxRow) 如果组里所有 k 个成员 不一定 要坐在一起的前提下，都能在第 0 排到第 maxRow 排之间找到座位，那么请返回 true 。这种情况下，每个成员都优先找排数最小，然后是座位编号最小的座位。如果不能安排所有 k 个成员的座位，请返回 false 。

示例 1：
输入： [“BookMyShow”, “gather”, “gather”, “scatter”, “scatter”] [[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]] 输出： [null, [0, 0], [], true, false] 解释： BookMyShow bms = new BookMyShow(2, 5); // 总共有 2 排，每排 5 个座位。 bms.gather(4, 0); // 返回 [0, 0] // 这一组安排第 0 排 [0, 3] 的座位。 bms.gather(2, 0); // 返回 [] // 第 0 排只剩下 1 个座位。 // 所以无法安排 2 个连续座位。 bms.scatter(5, 1); // 返回 True // 这一组安排第 0 排第 4 个座位和第 1 排 [0, 3] 的座位。 bms.scatter(5, 1); // 返回 False // 总共只剩下 2 个座位。

提示：

1 <= n <= 5 * 104
1 <= m, k <= 109
0 <= maxRow <= n - 1
gather 和 scatter 总调用次数不超过 5 * 104 次。

思路：
需要一个数据结构，在线维护一个数组并支持以下操作：

求第一个大等于 k 的元素；
求第一个前缀和大等于 k 的下标；
修改单个元素的值。

在线段树上二分可以做到以上操作。
时间复杂度：O((n + q)logn)

class BookMyShow {
    class Node {
        int l, r;
        int maxv;
        long sum;
        Node(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }
    Node[] tr;
    int n, m;
    int lastRow = 0;
    int remain;
    public BookMyShow(int n, int m) {
        tr = new Node[n * 4];
        this.n = n;
        this.m = m;
        build(1, 0, n - 1);
    }
    public int[] gather(int k, int maxRow) {
        if (tr[1].maxv < k)
            return new int[0];
        int row = queryMax(1, k);
        if (row > maxRow) return new int[0];
        modify(1, row, remain);
        return new int[]{row, m - remain - k};
    }
    public boolean scatter(int k, int maxRow) {
        if (tr[1].sum < k)
            return false;
        int row = queryPrefix(1, k);
        if (row > maxRow)
            return false;
        while (lastRow < row)
            modify(1, lastRow++, 0);
        modify(1, row, remain);
        return true;
    }
    private int queryPrefix(int u, int k) {
        if (tr[u].l == tr[u].r) {
            remain = (int)(tr[u].sum - k);
            return tr[u].l;
        } else {
            if (tr[u << 1].sum >= k)
                return queryPrefix(u << 1, k);
            else
                return queryPrefix(u << 1 | 1, (int)(k - tr[u << 1].sum));
        }
    }
    private void modify(int u, int row, int remain) {
        if (tr[u].l == row && tr[u].r == row) {
            tr[u].maxv = remain;
            tr[u].sum = remain;
        } else {
            int mid = tr[u].l + tr[u].r >> 1;
            if (row <= mid) modify(u << 1, row, remain);
            else modify(u << 1 | 1, row, remain);
            pushup(u);
        }
    }
    private int queryMax(int u, int k) {
        if (tr[u].l == tr[u].r) {
            remain = tr[u].maxv - k;
            return tr[u].l;
        }
        if (tr[u << 1].maxv >= k)
            return queryMax(u << 1, k);
        else
            return queryMax(u << 1 | 1, k);
    }
    private void build(int u, int ll, int rr) {
        if (ll == rr) {
            tr[u] = new Node(ll, rr);
            tr[u].maxv = m;
            tr[u].sum = m;
        } else {
            tr[u] = new Node(ll, rr);
            int mid = ll + rr >> 1;
            build(u << 1, ll, mid);
            build(u << 1 | 1, mid + 1, rr);
            pushup(u);
        }
    }
    private void pushup(int u) {
        tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
        tr[u].maxv = Math.max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
    }
}
/**
 * Your BookMyShow object will be instantiated and called as such:
 * BookMyShow obj = new BookMyShow(n, m);
 * int[] param_1 = obj.gather(k,maxRow);
 * boolean param_2 = obj.scatter(k,maxRow);
 */