leetcode biweekly contest 79

leetcode biweekly contest 79

最近几次的双周赛最后一题都比较难，感觉双周赛的题目质量明显好于周赛质量，当然毕竟只是面试题目，感觉模板化很严重。

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

题目

给你一个下标从 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 只包含数字。

地址

https://leetcode.cn/problems/check-if-number-has-equal-digit-count-and-digit-value/

题意

直接遍历即可

思路

1. 直接统计字符出现次数即可，然后依次遍历即可。
2. 复杂度分析：

• 时间复杂度：$O(n)$, 其中 $n$ 为数组的长度。
• 空间复杂度：$O(\Sigma)$。

  代码

  class Solution {
  public:
      bool digitCount(string num) {
          vector<int> cnt(10);
          for(auto c : num) {
              cnt[c - '0']++;
          }
          for (int i = 0; i < num.size(); i++) {
              int x = num[i] - '0';
              if (x != cnt[i]) {
                  return false;
              }
          }
          return true;
      }
  };

2284. 最多单词数的发件人

题目

给你一个聊天记录，共包含 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] 只包含大写英文字母和小写英文字母。

地址

https://leetcode.cn/problems/sender-with-largest-word-count

题意

hash统计

思路

1. 直接 $hash$ 统计出每个发件人发送的单词数目即可，然后找到最大值即可。
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 为字符串的长度。
• 空间复杂度：$O(n)$, 其中 $n$ 为字符串的长度。

  代码

  class Solution {
  public:
      vector<string> split(const string & word) {
          vector<string> res;
          int pos = 0;
          while (pos < word.size()) {
              while (pos < word.size() && word[pos] == ' ') {
                  pos++;
              }
              int curr = pos;
              while (pos < word.size() && word[pos] != ' ') {
                  pos++;
              }
              if (curr < word.size()) {
                  res.emplace_back(word.substr(curr, pos - curr));
              }
          }
          return res;
      }
      
      string largestWordCount(vector<string>& messages, vector<string>& senders) {
          string res;
          int maxVal = 0;
          int n = messages.size();
          unordered_map<string, int> cnt;
          for (int i = 0; i < n; i++) {
              vector<string> words = split(messages[i]);
              cnt[senders[i]] += words.size();
          }
          for (auto & [name, freq] : cnt) {
              if (freq > maxVal) {
                  maxVal = freq;
                  res = name;
              } else if (freq == maxVal && name > res) {
                  res = name;
              }
          }
          return res;
      }
  };

2285. 道路的最大总重要性

题目

给你一个整数 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
  没有重复道路。

地址

https://leetcode.cn/problems/maximum-total-importance-of-roads

题意

贪心算法

思路

1. 这个题目感觉就是简单题目了，设每个节点 $i$ 的度为 $i$ 则我们可以知道道路重要性之和为 $\sum_{i=0}^{n-1}(i \times degree[i])$，所以我们优先将最大的编号分配给度最大的节点即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log n)$, 其中 $n$ 为节点的数目。
• 空间复杂度：$O(n)$，其中 $n$ 为节点的数目。

  代码

  class Solution {
  public:
      long long maximumImportance(int n, vector<vector<int>>& roads) {
          vector<int> degree(n);
          long long res = 0;
          for (int i = 0; i < roads.size(); i++) {
              int x = roads[i][0];
              int y = roads[i][1];
              degree[x]++;
              degree[y]++;
          }
          vector<pair<int,int>> arr;
          for (int i = 0; i < n; i++) {
              arr.emplace_back(degree[i], i);
          }
          sort(arr.begin(), arr.end());
          for (int i = n - 1; i >= 0; i--) {
              res += (long long) (i + 1) * arr[i].first;
          }
          return res;
      }
  };

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

题目

一个音乐会总共有 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 次。

地址

https://leetcode.cn/problems/booking-concert-tickets-in-groups

题意

二分查找 + 线段树

思路

1. 这个题目确实超纲了，当然也是第一次见到线段树上二分的情况，还是非常不错的题目，线段树上二分这个方法确实太棒了，有许多地方都可以应用这个动态更新和变换的解法。当然题目中最关键的一点需要明白，对于每一排作为，不管如何选择，每一排的座位中一定是前半部分是坐满的，后半部分是全空的，因为题目要求不管是 gather 还是 scatter 操作每次都是贪心的从每一排的最左边的空位置开始的，所以这样一定保证每一排的座位被分成两部分, 前 $i$ 个座位上一定坐满了人，$i+1$ 以后的座位全部是空的。
2. 可以参考题解, 所以我们可以设线段树，设区间 $[l,r]$, 我们用 $tsum[l,r]$ 记录区间从 $i$ 排到 $j$ 排的座位空座位数目，$tmin[l,r]$ 记录区间从 $i$ 排到 $j$ 的空座位的最小起点，对于前缀和的 $sum$ 操作很简单，难点在于线段树上的二分：

• 用线段树维护每个区间上的空座位的起点最小值 $ \textit{tmin}$
  • 如果当前区间 $\textit{tmin} > m−k $，则此时剩余的座位数位 $m - \textit{tmin} < k$, 肯定无法满足坐满连续的 $k$ 个人；
  • 如果当前区间只包含一个元素，则返回该元素的下标；
  • 如果左半部分 $\textit{tmin} \le m−k$，说明左区间存在可以连续坐满 $k$ 个人的空座位的排，递归左半部分；
  • 否则如果 $\textit{maxRow}$ 在右半部分内，则递归右半部分；
  • 否则返回 $0$。
    确实非常桥面的线段上二分的解法。

1. 复杂度分析：

• 时间复杂度：$\text{gather}$ 的时间复杂度为 $O(\log n)$, 其中 $n$ 为排数，$\text{scatter}$ 的时间复杂度为 $O((n + q)\log n)$。
• 空间复杂度：$O(n)$, 其中 $n$ 为排数。

代码

#define CHL(x) (2 * (x))
#define CHR(x) (2 * (x) + 1)

class BookMyShow {
public:
    BookMyShow(int n, int m) {
        this->row = n;
        this->col = m;
        this->tsum = vector<long long>(n * 4 + 1);
        this->tmin = vector<int>(n * 4 + 1);
        build(0, n - 1, 1);
    }
    
    vector<int> gather(int k, int maxRow) {
        int i = queryIndex(col - k, maxRow, 0, row - 1, 1);
        if (i == -1) {
            return {};
        }
        int curr = col - querySum(i, i, 0, row - 1, 1);
        vector<int> res = {i, curr};
        update(i, k, 0, row - 1, 1);
        return res;
    }

    bool scatter(int k, int maxRow) {
        long long sum = querySum(0, maxRow, 0, row - 1, 1);
        if (sum < k) {
            return false;
        }
        for (int i = queryIndex(col - 1, maxRow, 0, row - 1, 1); k > 0 && i <= maxRow; i++) {
            int left = querySum(i, i, 0, row - 1, 1);
            int add = min(left, k);
            update(i, add, 0, row - 1, 1);
            k -= add;
        }
        return true;
    }
    
    void build(int l, int r, int idx) {
        if (l == r) {
            tsum[idx] = col;
            tmin[idx] = 0;
        } else {
            int mid = (l + r) >> 1;
            build(l, mid, CHL(idx));
            build(mid + 1, r, CHR(idx));
            tsum[idx] = tsum[CHL(idx)] + tsum[CHR(idx)];
            tmin[idx] = min(tmin[CHL(idx)], tmin[CHR(idx)]);
        }
    }

    void update(int x, int val, int l, int r, int idx) {
        if (l > x || r < x) {
            return;
        }
        if (l == x && r == x) {
            tsum[idx] -= val;
            tmin[idx] += val;
        } else {
            int mid = (l + r) >> 1;
            if (x <= mid) {
                update(x, val, l, mid, CHL(idx));
            } else {
                update(x, val, mid + 1, r, CHR(idx));
            }
            tsum[idx] = tsum[CHL(idx)] + tsum[CHR(idx)];
            tmin[idx] = min(tmin[CHL(idx)], tmin[CHR(idx)]);
        }
    }

    int queryIndex(int minIndex, int maxRow, int l, int r, int idx) {
        if (l > maxRow) {
            return -1;
        }
        if (tmin[idx] > minIndex) {
            return -1;
        }
        if (l == r) {
            return l;
        } else {
            int mid = (l + r) >> 1;
            if (tmin[CHL(idx)] <= minIndex) {
                return queryIndex(minIndex, maxRow, l, mid, CHL(idx));
            }
            if (mid < maxRow) {
                return queryIndex(minIndex, maxRow, mid + 1, r, CHR(idx));
            }
            return -1;
        }
    }

    long long querySum(int start, int end, int l, int r, int idx) {
        if (l > end || r < start) {
            return 0;
        }
        if (start <=l  && r <= end) {
            return tsum[idx];
        } else {
            int mid = (l + r) >> 1;
            if (end <= mid) {
                return querySum(start, end, l, mid, CHL(idx));
            } else if (start > mid) {
                return querySum(start, end, mid + 1, r, CHR(idx));
            } else {
                return querySum(start, mid, l, mid, CHL(idx)) + \
                       querySum(mid + 1, end, mid + 1, r, CHR(idx));
            }
        }
    }
private:
    long long row, col;
    vector<long long> tsum;
    vector<int> tmin;
};

#

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿