早上出去玩了😛晚上补做的。。
第一题：旅行终点站
难度简单
题目描述
给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。
题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。
示例 1：
|
1 2 3 4 |
输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]] 输出："Sao Paulo" 解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。 |
示例 2：
|
1 2 3 4 5 6 7 8 9 |
输入：paths = [["B","C"],["D","B"],["C","A"]] 输出："A" 解释：所有可能的线路是： "D" -> "B" -> "C" -> "A". "B" -> "C" -> "A". "C" -> "A". "A". 显然，旅行终点站是 "A" 。 |
示例 3：
|
1 2 3 |
输入：paths = [["A","Z"]] 输出："Z" |
提示：
1 <= paths.length <= 100paths[i].length == 21 <= cityAi.length, cityBi.length <= 10cityAi != cityBi- 所有字符串均由大小写英文字母和空格字符组成。
题目链接
https://leetcode-cn.com/problems/destination-city/
思路:
集合运算。所有的站点去掉所有作为出发站的站点即为结果。
代码:
|
1 2 3 4 5 6 7 8 |
class Solution: def destCity(self, paths: List[List[str]]) -> str: x = [x for x, y in paths] y = [y for x, y in paths] ans = (set(x) | set(y)) - set(x) return ans.pop() |
第二题：是否所有 1 都至少相隔 k 个元素
难度中等
题目描述
给你一个由若干 0 和 1 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素，则返回 True ；否则，返回 False 。
示例 1：
|
1 2 3 4 |
输入：nums = [1,0,0,0,1,0,0,1], k = 2 输出：true 解释：每个 1 都至少相隔 2 个元素。 |
示例 2：
|
1 2 3 4 |
输入：nums = [1,0,0,1,0,1], k = 2 输出：false 解释：第二个 1 和第三个 1 之间只隔了 1 个元素。 |
示例 3：
|
1 2 3 |
输入：nums = [1,1,1,1,1], k = 0 输出：true |
示例 4：
|
1 2 3 |
输入：nums = [0,1,0,1], k = 1 输出：true |
提示：
1 <= nums.length <= 10^50 <= k <= nums.lengthnums[i]的值为0或1
题目链接
https://leetcode-cn.com/problems/check-if-all-1s-are-at-least-length-k-places-away/
思路:
记录上一次1出现的位置，每次新出现1计算中间相隔了多少元素即可。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution: def kLengthApart(self, nums: List[int], k: int) -> bool: last = -99999 for i, num in enumerate(nums): if num == 1: if i - last <= k: return False last = i return True |
第三题：绝对差不超过限制的最长连续子数组
难度中等
题目描述
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
示例 1：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
输入：nums = [8,2,4,7], limit = 4 输出：2 解释：所有子数组如下： [8] 最大绝对差 |8-8| = 0 <= 4. [8,2] 最大绝对差 |8-2| = 6 > 4. [8,2,4] 最大绝对差 |8-2| = 6 > 4. [8,2,4,7] 最大绝对差 |8-2| = 6 > 4. [2] 最大绝对差 |2-2| = 0 <= 4. [2,4] 最大绝对差 |2-4| = 2 <= 4. [2,4,7] 最大绝对差 |2-7| = 5 > 4. [4] 最大绝对差 |4-4| = 0 <= 4. [4,7] 最大绝对差 |4-7| = 3 <= 4. [7] 最大绝对差 |7-7| = 0 <= 4. 因此，满足题意的最长子数组的长度为 2 。 |
示例 2：
|
1 2 3 4 |
输入：nums = [10,1,2,4,7,2], limit = 5 输出：4 解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。 |
示例 3：
|
1 2 3 |
输入：nums = [4,2,2,2,4,4,2,2], limit = 0 输出：3 |
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^90 <= limit <= 10^9
题目链接
思路:
维护一个滑动窗口。窗口内最大值减去最小值小于等于limit。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution: def longestSubarray(self, nums: List[int], limit: int) -> int: asc = [] ans = 0 left = 0 for right, num in enumerate(nums): bisect.insort(asc, num) while asc[-1] - asc[0] > limit: # 最大减最小 idx = bisect.bisect_left(asc, nums[left]) asc.pop(idx) left += 1 ans = max(ans, right - left + 1) return ans |
第四题：有序矩阵中的第 k 个最小数组和
难度困难
题目描述
给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
示例 1：
|
1 2 3 4 5 |
输入：mat = [[1,3,11],[2,4,6]], k = 5 输出：7 解释：从每一行中选出一个元素，前 k 个和最小的数组分别是： [1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。 |
示例 2：
|
1 2 3 |
输入：mat = [[1,3,11],[2,4,6]], k = 9 输出：17 |
示例 3：
|
1 2 3 4 5 |
输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7 输出：9 解释：从每一行中选出一个元素，前 k 个和最小的数组分别是： [1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。 |
示例 4：
|
1 2 3 |
输入：mat = [[1,1,10],[2,2,9]], k = 7 输出：12 |
提示：
m == mat.lengthn == mat.length[i]1 <= m, n <= 401 <= k <= min(200, n ^ m)1 <= mat[i][j] <= 5000mat[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)入堆。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class Solution: def kthSmallest(self, mat: List[List[int]], k: int) -> int: m = len(mat) n = len(mat[0]) def get_sum(indics): re = 0 for i in range(m): re += mat[i][indics[i]] return re used = set() heap = [] indics = (0,) * m heappush(heap, (get_sum(indics),) + indics) used.add(indics) # print(heap) count = 0 while heap: data = heappop(heap) num = data[0] count += 1 if count == k: return num indics = data[1:] for i in range(m): temp = list(indics) temp[i] += 1 nxt_indics = tuple(temp) if temp[i] < n and nxt_indics not in used: heappush(heap, (get_sum(nxt_indics),) + nxt_indics) used.add(nxt_indics) |
