讨论/题目交流/🏆 第 187 场力扣周赛/
🏆 第 187 场力扣周赛
展开讨论
力扣 (LeetCode)发起于 2020-05-03

A: 旅行终点站

  1. 将地名映射为整数 ID,作为图上的点
  2. 保存每个点的出度,因为题目保证了有且仅有一个点的没有出度,找出那个点就是答案

B: 是否所有 1 都至少相隔 k 个元素

  1. 扫描整个数组,每遇到数字 1 就看看它和上一个数字 1 的下标差是否超过 k,超过则不合法
  2. 然后将当前数字 1 的下标更新为 “上一个数字 1 的下标”

C: 绝对差不超过限制的最长连续子数组

  1. 假设我们从左到右选元素,如果要选当前下标 idx,那么它左边的元素必须在范围 [nums[idx]-limit, nums[idx]+limit] 内
  2. 对于左边已经遍历过的元素,用一个能维护有序性质的数据结构来保存;对于当前元素,把有序数据结构中将 [nums[idx]-limit, nums[idx]+limit] 以外的元素删除,并记录被删除元素中最靠右的下标 p,那么当前的连续区间就是 [p+1, idx]

D: 有序矩阵中的第 k 个最小数组和

矩阵最大为 40 * 40,如果暴力枚举所有可能是 40^40,不可行。
留意到 k 最大只有 200, 我们可以换一种暴力的方案

  1. 先设行数为 n,列数为 m
  2. 最开始所有行都取 0 下标的元素,相加的和最小
  3. 对于当前的选取方案,将某一行的下标向右移动一格,新得到的和一定是最小的;因为我们把 n 种移动方案都枚举一次并保存下来
  4. 每次都从可能的方案中选择和最小的,然后再做一次 n 轮枚举,再插入可能方案中
  5. 可见,最多取 k(200) 次就结束;每次取出一个方案,要枚举 n(40)种移动,代价最大为 200 * 40

关注微信公众号:不爱睡觉的大猪,查看本轮比赛完整代码,一起讨论 LeetCode 和算法
捕获.JPG

14
展开全部 18 讨论