一、旅行终点站
给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。
题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。
class Solution:
def destCity(self, paths: List[List[str]]) -> str:
lista=[i[0] for i in paths]
listb=[i[1] for i in paths]
return (set(listb)-set(lista)).pop()
二、是否所有 1 都至少相隔 k 个元素
给你一个由若干 0 和 1 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素，则返回 True ；否则，返回 False 。
class Solution:
def kLengthApart(self, nums: List[int], k: int) -> bool:
temp=float('-inf')
for i in range(len(nums)):
if nums[i]==1:
if i-temp<=k: return False
else:temp=i
return True
三、绝对差不超过限制的最长连续子数组
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
话说dp和双指针好像，双指针的话最后一个十几万数的测试用例超时了。。。
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
if not nums: return 0
ans=1
a=len(nums)
for l in range(0,a-1):
minnum,maxnum=10**9,1
for r in range(l+1,a):
minnum=min([nums[l],nums[r],minnum])
maxnum=max([nums[l],nums[r],maxnum])
if maxnum-minnum<=limit:
ans=max(ans,r-l+1)
else:
break
return ans
from copy :
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
i = j = 0
st = []
ans = 0
while j < len(nums):
bisect.insort(st, nums[j])
while st[-1] - st[0] > limit:
st.remove(nums[i])
i += 1
j += 1
ans = max(ans, len(st))
return ans
四、有序矩阵中的第 k 个最小数组和
给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个最小数组和。
利用sorted逐行更新。。
from copy:
class Solution:
def kthSmallest(self, mat: List[List[int]], k: int) -> int:
ans = [0]
for row in mat:
ans = sorted([a + r for a in ans for r in row])[: k]
return ans[-1]
