LeetCode 第187场周赛

早上出去玩了😛晚上补做的。。

第一题:旅行终点站

难度简单

题目描述

给你一份旅游线路图,该线路图中的旅行线路用数组 paths 表示,其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站,即没有任何可以通往其他城市的线路的城市

题目数据保证线路图会形成一条不存在循环的线路,因此只会有一个旅行终点站。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi != cityBi
  • 所有字符串均由大小写英文字母和空格字符组成。

题目链接

https://leetcode-cn.com/problems/destination-city/

思路:

  集合运算。所有的站点去掉所有作为出发站的站点即为结果。

代码:

第二题:是否所有 1 都至少相隔 k 个元素

难度中等

题目描述

给你一个由若干 01 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素,则返回 True ;否则,返回 False

示例 1:

示例 2:

示例 3:

示例 4:

提示:

  • 1 <= nums.length <= 10^5
  • 0 <= k <= nums.length
  • nums[i] 的值为 01

题目链接

https://leetcode-cn.com/problems/check-if-all-1s-are-at-least-length-k-places-away/

思路:

  记录上一次1出现的位置,每次新出现1计算中间相隔了多少元素即可。

代码:

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

难度中等

题目描述

给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit

如果不存在满足条件的子数组,则返回 0

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= limit <= 10^9

题目链接

https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

思路:

  维护一个滑动窗口。窗口内最大值减去最小值小于等于limit

代码:

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

难度困难

题目描述

给你一个 m * n 的矩阵 mat,以及一个整数 k ,矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。

示例 1:

示例 2:

示例 3:

示例 4:

提示:

  • m == mat.length
  • n == mat.length[i]
  • 1 <= m, n <= 40
  • 1 <= k <= min(200, n ^ m)
  • 1 <= mat[i][j] <= 5000
  • mat[i] 是一个非递减数组

题目链接

https://leetcode-cn.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/

思路:

  这题居然暴力都能过。。。

  我的解法是最小堆+类似广度优先搜索,用一个最小堆存放数组和以及选出这个数组和的下标。每次出堆时将所有下一个可能的下标入堆。用一个集合保存访问过的下标组。最终第k次出堆的元素就是结果。

  例如,刚开始时堆内的下标组为(0, 0, 0, 0)。出堆后分别将(1, 0, 0, 0)(0, 1, 0, 0)(0, 0, 1, 0)(0, 0, 0, 1)入堆。

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注