目录

旅行终点站

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/destination-city

示例

输入：paths = [[“London”,“New York”],[“New York”,“Lima”],[“Lima”,“Sao Paulo”]]
输出：“Sao Paulo”
解释：从 “London” 出发，最后抵达终点站 “Sao Paulo” 。本次旅行的路线是 “London” -> “New York” -> “Lima” -> “Sao Paulo”

我的思路

出发站和终点站各做成一个列表。然后遍历终点站列表，不在出发站列表中的终点站即为所求。

我的代码

1
2
3
4
5
6
7
8
9

    class Solution:
        def destCity(self, paths) -> str:
            starts = [path[0] for path in paths]
            ends = [path[1] for path in paths]
            res = ""
            for end in ends:
                if end not in starts:
                    res += end
            return res

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-if-all-1s-are-at-least-length-k-places-away

示例

输入：nums = [1,0,0,0,1,0,0,1], k = 2
输出：true
解释：每个 1 都至少相隔 2 个元素。

我的思路

遍历一次nums，先找第一个1，然后用计数器cnt记录每个1之间的间隔，若遍历过程中有cnt小于k的情况，则返回False，否则返回True

我的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    class Solution:
        def kLengthApart(self, nums, k) -> bool:
            cnt = 0
            flag = False # 先找第一个1
            for num in nums:
                if flag:
                    if num == 1:
                        if cnt < k:
                            return False
                        cnt = 0
                    else:
                        cnt += 1
                else:
                    if num == 1:
                        flag = True
            return True

绝对值不超过限制的最长连续子数组

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit

示例

输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5

别人的思路1

想到了单调栈，但是没想到要维护两个。
本题思路是单调栈+双指针。
遍历nums，维护两个单调栈，一个是单调升序栈asc，维护最左边是栈内最小值，一个是单调递减栈dsc，维护最左边是栈内最大值。
栈内元素不仅是元素值，也维护元素值在nums内的索引位置，最左边的元素的索引位置也需维护为栈内元素索引中最左的索引。
for循环里的前两个while实现了上面两个维护。最后一个while循环则维护满足绝对值不超过limit的合法左右指针，合法子数组的长度即右指针和左指针的差值加1。

别人的代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def longestSubarray(self, nums, limit):
        asc = [] # 单调升序栈
        dsc = [] # 单调递减栈
        res = 0
        left = 0 # 记录栈中元素在nums中最左边的索引
        for right, num in enumerate(nums):
            while asc and num < asc[-1][0]:
                asc.pop()
            asc.append((num, right))
            while dsc and num > dsc[-1][0]:
                dsc.pop()
            dsc.append((num, right))

            while dsc[0][0] - asc[0][0] > limit:
                if left == asc[0][1]:
                    asc.pop(0)
                if left == dsc[0][1]:
                    dsc.pop(0)
                left += 1
            
            res = max(res, right - left + 1)
        return res

别人的思路2

利用Cpp里的 multiset 本身有序的特点来找最大绝对值差值

别人的代码2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int> s;
        int ans = 0;
        int i = 0; // 记录s中在nums最左边的数的索引
        for (int j = 0; j < nums.size(); j++) {
            s.insert(nums[j]);
            while (*s.rbegin() - *s.begin() > limit) {
                s.erase(s.find(nums[i]));
                i++;
            }
            ans = max(ans, j - i + 1);
        }
        return ans;
    }

作者：ikaruga
链接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/longest-continuous-subarray-by-ikaruga/

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows

示例

输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7

别人的思路1

用preSum记录之前累加的和，因为矩阵每行是递增的，所以前k小的数必然是从每次前k小的和中累加得的，所以每次只需保留前k小的和作为剪枝。
按行遍历矩阵，遍历行内元素，这些元素加上preSum的值得到新的preSum。挺巧妙的遍历。

别人的代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def kthSmallest(self, mat: List[List[int]], k: int) -> int:
        preSum = [0]
        for row in mat:
            tmp = []
            for cur in row:
                for pre in preSum:
                    tmp.append(cur + pre)
            preSum = sorted(tmp)[:k]
        return res[-1]

简化版：

1
2
3
4
5
6

    class Solution:
    def kthSmallest(self, mat: List[List[int]], k: int) -> int:
        res = [0]
        for row in mat:
            res = sorted([cur + pre for cur in row for pre in res])[:k]
        return res[-1]

别人的思路2

二分查找+DFS

别人的代码2

 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

class Solution {
public:
    vector<vector<int>>temp;
    int m,n;
    int kthSmallest(vector<vector<int>>& mat, int k) {
        temp=mat;
        m=mat.size(),n=mat[0].size();
        int left=0,right=0;
        for(int i=0;i<m;i++) left+=mat[i][0],right+=mat[i].back();
        int init=left;
        while(left<right){
            int mid=(left+right)>>1;
            int num=1;
            dfs(mid,0,init,num,k);
            if(num>=k) right=mid;
            else left=mid+1;
        }
        return left;
    }
    void dfs(int mid,int index,int sum,int& num,int k){
        if(sum>mid||index==m||num>k) return;
        dfs(mid,index+1,sum,num,k);
        for(int i=1;i<n;i++){
            if(sum+temp[index][i]-temp[index][0]<=mid){
                num++;
                dfs(mid,index+1,sum+temp[index][i]-temp[index][0],num,k);
            }else{
                break;
            }
        }
    }
};

作者：newbie-19
链接：https://leetcode-cn.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/solution/er-fen-by-newbie-19-3/

总结

仅AC前两题，排名 1039/3108。
迟到了1分钟，前2题用了8分钟。第3题大概写了10多分钟没写出来就没写了，因为大伯和伯妈要坐12点的火车，陪他们吃完饭就去送他们了，顺便拿我的车票。