为了能够实现进大厂被资本家无情压迫的梦想，坚持每天一道题。🤑

先用 Python 写，学了 C++ 之后再刷一遍。😇

这里是我的代码仓库✨

不保证缩进正确，复制粘贴时候小心一点👀

主要是给我自己看的，所以解题思路我就不写了，我相信我能看懂自己的代码。😝

简单记一下做题感受。😶

To realize the dream of getting into a big company and being mercilessly exploited by the capitalists, I keep solving one problem every day.🤑

Write it in Python first, and go through it again after learning C++.😇

Here is my code repository✨

No guarantee that the indentation is correct, be careful when copy-pasting👀

This is mainly for myself, so I won’t write down the solution ideas. I believe I can understand my own code.😝

Just briefly record my feelings while solving problems.😶

✔️

1–两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

1–Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        '''
        就挺暴力的
        '''
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if target == nums[i] + nums[j]:
                    return [i,j]
        return []
    
    def twoSum_2(self, nums: List[int],target: int) -> List[int]:
        '''
        空间换时间
        '''
    	hashmap = {}
    	for i, num in enumerate(nums):
    		if target - num in hashmap:
    			return [hashmap[target - num] , i]
    		hashmap[num] = i

    	return []

两层循环是最好想的，第二种方法也不是很难，只是我还不习惯。
嗯… 应该努力让自己习惯。

The two-nested-loop solution is the easiest to think of. The second method isn’t hard either, I’m just not used to it yet.
Hmm… I should work on getting used to it.

2–两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

2–Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit.

Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

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
36
37
38
39
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    	'''
    	提交成功  时空性能较差
    	'''
        jinwei = 0
        head = ListNode(0)
        p = head
        head.next = p
        if l1 == None or l2 == None:
            return l1 or l2
        while l1 and l2:
            tmp = l1.val + l2.val + jinwei
            val = tmp % 10
            q = ListNode(val)
            p.next = q
            p = q
            jinwei = tmp // 10
            l1 = l1.next
            l2 = l2.next
        if l1 == None:l1 = l2
        while l1:
            tmp = l1.val +jinwei
            val = tmp%10
            q = ListNode(val)
            p.next = q
            p = q
            jinwei = tmp // 10
            l1 = l1.next
        if jinwei:
            q = ListNode(jinwei)
            p.next = q
            p = q
        p.next = None
        return head.next

和考研的数据结构题挺像的，我也是那个思想解的，肯定打不过他们的代码。

This is quite similar to the data structure problems in the postgraduate entrance exam. I solved it with the same idea too, and it definitely can’t beat their code.

3–无重复最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

示例 4:

输入: s = “”
输出: 0

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

3–Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: s = “abcabcbb”
Output: 3
Explanation: Because the longest substring without repeating characters is “abc”, its length is 3.

Example 2:

Input: s = “bbbbb”
Output: 1
Explanation: Because the longest substring without repeating characters is “b”, its length is 1.

Example 3:

Input: s = “pwwkew”
Output: 3
Explanation: Because the longest substring without repeating characters is “wke”, its length is 3.
Note that your answer must be the length of a substring, “pwke” is a subsequence and not a substring.

Example 4:

Input: s = “”
Output: 0

Constraints:

0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    	'''
    	背的答案  效果一般
    	'''
        n = len(s)
        if n < 2 :return n
        tmp = set(s[0])
        res = 0
        r = 0
        for i in range(n):
            while r + 1 < n and s[r+1] not in tmp:
                tmp.add(s[r+1])
                r = r + 1
            res = max(res,r+1 - i)
            tmp.remove(s[i])

        return res

这个题乍一看还挺简单的，但是我思考了好久，尝试了好多次都没做出来。
最后还是选择看了答案。
希望下次见到能做出来吧。

This problem looks quite simple at first glance, but I thought about it for a long time and tried many times without success.
In the end I chose to look at the answer.
Hopefully I can solve it the next time I see it.

7–整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

注意：

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

示例 1：

输入：x = 123
输出：321
示例 2：

输入：x = -123
输出：-321
示例 3：

输入：x = 120
输出：21
示例 4：

输入：x = 0
输出：0

提示：

-231 <= x <= 231 - 1

7–Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed.

Note:

Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. Based on this assumption, return 0 if the reversed integer overflows.

Example 1:

Input: x = 123
Output: 321
Example 2:

Input: x = -123
Output: -321
Example 3:

Input: x = 120
Output: 21
Example 4:

Input: x = 0
Output: 0

Constraints:

-231 <= x <= 231 - 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 reverse(self, x: int) -> int:
    	'''
    	做一道简单的放松一下
    	'''

        tag = 0
        if x < 0 :
            x = -x
            tag = 1

        tmp = []
        while x != 0:
            tmp.append(x % 10)
            x = x // 10
        n = len(tmp)
        for i in range(n):
            x = x + tmp[i]* (10 ** (n-i-1))
        if x > 2 ** 31 - 1:
            return 0
        if tag == 1:
            x = -x
        return x

这个题挺简单的，但是注意审题！第一次提交的时候忘记了判断反转之后是否越界。

~~我做题就是眼瞎，考研时候就是。~~😞

This one is pretty simple, but read the problem carefully! The first time I submitted, I forgot to check whether the reversed integer overflows.

~~I’m just blind when solving problems, and I was the same in the postgraduate entrance exam.~~😞

86–分隔链表

给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例：

输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5

86–Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        if head == None: return None
        xiaoyu = ListNode(head.val)
        p = xiaoyu
        dayu = ListNode(head.val)
        q = dayu
        h = head
        while h:
            if h.val < x:
                p.next = h
                p = p.next
            else:
                q.next = h
                q = q.next
            h = h.next
        p.next = dayu.next
        q.next = None
        return xiaoyu.next

嗯… 这题好像没啥说的，就… 挺简单的。

Hmm… Nothing much to say about this one, it’s just… pretty simple.

189–移动数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。

189–Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        temp = nums[n-k:]
        for i in range(n-k):
            nums[n-i-1] = nums[n-i-k-1]
        nums[0:k] = temp

    def rotate_2(self, nums: List[int], k: int) -> None:
    	'''
    	在数据结构的书上见过这种题：大概是三次 逆置 操作
    	'''
        n = len(nums)
        k %= n
        nums[:] = nums[::-1]
        nums[:k] = nums[:k][::-1]
        nums[k:] = nums[k:][::-1]

这题我就感觉在王道那个书上见过，三次逆置操作。

但是还是没有那么写，选了一个比较直观的思路。

我就是这么直，要改改了。😅

I felt like I’ve seen this problem in the “Wang Dao” book — the three-reversal trick.

But I still didn’t write it that way, and chose a more intuitive approach.

I’m just too straightforward, I need to change that.😅

228–汇总区间

给定一个无重复元素的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

“a->b” ，如果 a != b
“a” ，如果 a == b

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：[“0->2”,“4->5”,“7”]
解释：区间范围是：
[0,2] --> “0->2”
[4,5] --> “4->5”
[7,7] --> “7”

示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：[“0”,“2->4”,“6”,“8->9”]
解释：区间范围是：
[0,0] --> “0”
[2,4] --> “2->4”
[6,6] --> “6”
[8,9] --> “8->9”

示例 3：

输入：nums = []
输出：[]

示例 4：

输入：nums = [-1]
输出：["-1"]

示例 5：

输入：nums = [0]
输出：[“0”]

提示：

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
nums 按升序排列

228–Summary Ranges

You are given a sorted unique integer array nums.

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

“a->b” if a != b
“a” if a == b

Example 1:

Input: nums = [0,1,2,4,5,7]
Output: [“0->2”,“4->5”,“7”]
Explanation: The ranges are:
[0,2] --> “0->2”
[4,5] --> “4->5”
[7,7] --> “7”

Example 2:

Input: nums = [0,2,3,4,6,8,9]
Output: [“0”,“2->4”,“6”,“8->9”]
Explanation: The ranges are:
[0,0] --> “0”
[2,4] --> “2->4”
[6,6] --> “6”
[8,9] --> “8->9”

Example 3:

Input: nums = []
Output: []

Example 4:

Input: nums = [-1]
Output: ["-1"]

Example 5:

Input: nums = [0]
Output: [“0”]

Constraints:

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
All the values of nums are unique.
nums is sorted in ascending order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        result = []
        n = len(nums)
        if n == 0:return result
        if n == 1:return ["%s"%nums[0]]

        k = nums[0]
        for i in range(1,n):
            if nums[i] > nums[i-1]+1 :
                if nums[i-1] - k >0:
                    result.append("%s->%s"%(k,nums[i-1]))
                else:
                    result.append("%s"%k)
                k = nums[i]
    
        if nums[-1] - k >0:
            result.append("%s->%s"%(k,nums[-1]))
        else:
            result.append("%s"%nums[-1])
        
        return result

这题好像反复调了好几次，这种题就是思路是挺简单的，但是想一次把代码写对，还是挺难的。

I remember debugging this one a few times. The idea for this kind of problem is quite simple, but getting the code right on the first try is still pretty hard.

435–无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2: 输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

435–Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note: You may assume the interval’s end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: Removing [1,3] makes the rest of the intervals non-overlapping.

Example 2: Input: [ [1,2], [1,2], [1,2] ]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:
Input: [ [1,2], [2,3] ]
Output: 0
Explanation: You don’t need to remove any of the intervals since they’re already non-overlapping.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:     
	def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:         
		num = 0         
		thr = float("-inf")        
		while intervals:            
		    min_index = 0            
		    for i in range(1,len(intervals)):                 
		        if intervals[i][1] < intervals[min_index][1]:                 
		            min_index = i            
		    tmp = intervals.pop(min_index)            
		    if tmp[0] < thr:              
		        num += 1             
		    else:          
		        thr = tmp[1]         
		return num

这题和算法课上的一个例子很像。

用贪心策略，优先找先结束的。在这里就是 每一对数中第二个数比较小的一定在最优解中，与之矛盾的区间弹出，再找下一个这样的数对。

This problem is very similar to an example from my algorithms class.

Use a greedy strategy, always picking the one that ends first. Here, among each pair of numbers, the one with the smaller second number must be in the optimal solution; pop the intervals that conflict with it, then find the next such pair.

509–斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 30

509–Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is:

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), where n > 1
Given n, calculate F(n).

Example 1:

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1

Example 2:

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2

Example 3:

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3

Constraints:

0 <= n <= 30

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def fib(self, n: int) -> int:
    	if n < 2:
    		return n

    	p , q , r = 0 , 0 , 1
    	for i in range(2,n+1):
    		p , q = q , r
    		r = p + q

    	return r

哎，怎么说呢，下次遇到这种题可别用递归了，像是大一新生。

Sigh, what can I say. Next time I meet this kind of problem, don’t use recursion, that’s like a freshman.

547–省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

547–Number of Provinces

There are n cities, some of which are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints:

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] is 1 or 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        label = [0] * n 
        queue = []
        result = 0
        if isConnected:
            for i in range(n):
                if label[i] == 0:
                    queue.append(i)
                    result += 1
                    while queue:
                        tmp = queue.pop(0)
                        for j in range(n):
                            if isConnected[tmp][j] == 1 and label[j] == 0:
                                label[j] = 1
                                queue.append(j)
        

        return result

能自主做上一道图论的题，太不容易了。😪

虽然只是个广度优先遍历而已。

It’s so rare that I managed to solve a graph theory problem on my own.😪

Even though it’s just a breadth-first traversal.

605–种花问题

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

示例 1:

输入: flowerbed = [1,0,0,0,1], n = 1
输出: True

示例 2:

输入: flowerbed = [1,0,0,0,1], n = 2
输出: False

注意:

数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。

605–Can Place Flowers

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule, otherwise return false.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

The input array won’t violate the no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won’t exceed the input array size.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if n == 0: return True
        if len(flowerbed) < 2 * n - 1:
            return False
        if len(flowerbed) > 2:
            if flowerbed[0] == 0 and flowerbed[1] == 0:
                flowerbed[0] = 1
                n -= 1
            for i in range(1,len(flowerbed) - 1):
                if flowerbed[i-1] == 0 and flowerbed[i] == 0 and flowerbed[i+1] == 0:
                    flowerbed[i] = 1
                    n -= 1
            if flowerbed[-1] == 0 and flowerbed[-2] == 0:
                flowerbed[-1] = 1
                n -= 1
            return n <= 0
        else:
            return True if (n == 1 and max(flowerbed) == 0) else False

这题好像也根据不过的测试用例反复调了几次。

也是贪心策略吧，题解懒得看，大体上差不多。

I think this one also needed a few rounds of fixes based on failing test cases.

It’s also a greedy strategy, I guess. Too lazy to read the editorial, the idea is more or less the same.

617–合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。

617–Merge Two Binary Trees

You are given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Example 1:

Input:
Tree 1 Tree 2
1 2
/ \ /
3 2 1 3
/ \
5 4 7
Output:
Merged tree:
3
/ 4 5
/ \
5 4 7
Note: The merging process must start from the root nodes of both trees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val, left = None,right = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
    	if not t1:
    		return t2
    	if not t2:
    		return t1

    	merged = TreeNode(t1.val + t2.val)
    	merged.left = self.mergeTrees(t1.left,t2.left)
    	merged.right = self.mergeTrees(t1.right.t2.right)

    	return merged

这个好像是前几个遇到的题，不算难。但是我好像还是参考答案了。

This one seems to be from the problems I encountered earlier, not too hard. But I think I still referenced the answer.

830–寻找字符串中较大分组

在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 s = “abbxxxxzyy” 中，就含有 “a”, “bb”, “xxxx”, “z” 和 “yy” 这样的一些分组。

分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 “xxxx” 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

示例 1：

输入：s = “abbxxxxzzy”
输出：[[3,6]]
解释：“xxxx” 是一个起始于 3 且终止于 6 的较大分组。

示例 2：

输入：s = “abc”
输出：[]
解释：“a”,“b” 和 “c” 均不是符合要求的较大分组。

示例 3：

输入：s = “abcdddeeeeaabbbcd”
输出：[[3,5],[6,9],[12,14]]
解释：较大分组为 “ddd”, “eeee” 和 “bbb”

示例 4：

输入：s = “aba”
输出：[]

830–Positions of Large Groups

In a string s of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like s = “abbxxxxzyy” has the groups “a”, “bb”, “xxxx”, “z”, and “yy”.

A group is identified by an interval [start, end], where start and end denote the start and end indices (inclusive) of the group. In the above example, “xxxx” has the interval [3,6].

We call a group a large group if it has 3 or more characters.

Return the intervals of every large group sorted in increasing order by start index.

Example 1:

Input: s = “abbxxxxzzy”
Output: [[3,6]]
Explanation: “xxxx” is a large group starting at 3 and ending at 6.

Example 2:

Input: s = “abc”
Output: []
Explanation: “a”,“b” and “c” are not large groups.

Example 3:

Input: s = “abcdddeeeeaabbbcd”
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are “ddd”, “eeee” and “bbb”

Example 4:

Input: s = “aba”
Output: []

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        result = []
        if len(s) < 3:
            return result
        i = 0
        while i < len(s) - 2:
            j = i + 1
            while j < len(s):
                if s[j] != s[i]:
                    break
                j += 1
            if j - i > 2:
                result.append([i,j - 1])
                i = j
            else:
                i += 1        
        return result

大概就是遍历试，记录下标。

Roughly just iterate through and record the indices.

1018–可被 5 整除的二进制前缀

给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。

返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

示例 1：

输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。
示例 2：

输入：[1,1,1]
输出：[false,false,false]
示例 3：

输入：[0,1,1,1,1,1]
输出：[true,false,false,false,true,false]
示例 4：

输入：[1,1,1,0,1]
输出：[false,false,false,false,false]

提示：

1 <= A.length <= 30000
A[i] 为 0 或 1

1018–Binary Prefix Divisible By 5

You are given a binary array A (a list of 0s and 1s). We define N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most significant bit to least significant bit).

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example 1:

Input: [0,1,1]
Output: [true,false,false]
Explanation:
The input numbers are 0, 01, 011; which are 0, 1, and 3 in decimal. Only the first number is divisible by 5, so answer[0] is true.
Example 2:

Input: [1,1,1]
Output: [false,false,false]
Example 3:

Input: [0,1,1,1,1,1]
Output: [true,false,false,false,true,false]
Example 4:

Input: [1,1,1,0,1]
Output: [false,false,false,false,false]

Constraints:

1 <= A.length <= 30000
A[i] is 0 or 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def prefixesDivBy5(self, A: List[int]) -> List[bool]:
    	'''
    	一开始暴力解题  超时了
    	后来看了答案  发现每次增加一个数只是上一个数的左移加当前数值 也就是2倍加当前数值  快了一些
    	再后来发现 被 5 整除只需要记录个位数就行了 也就是除 10 取余数
    	但是，对于个位数 6 ，6 = 1 + 5， 6 * 2 = （1 + 5）* 2，6 * 2 % 10 = (1 + 5) * 2 % 10 = 2 
    	因此每次记录除以 5 的余数即可。 
    	'''
        n = len(A)
        ans = [False] * n
        tmp = 0
        for i in range(n):
            tmp = (tmp * 2 + A[i]) % 5
            if tmp == 0:
                ans[i] = True
        return ans

一开始暴力解题 超时了 🤕
后来看了答案 发现每次增加一个数只是上一个数的左移加当前数值 也就是2倍加当前数值 快了一些
再后来发现 被 5 整除只需要记录个位数就行了 也就是除 10 取余数
又因为，对于个位数 6 ，6 = 1 + 5， 6 * 2 = （1 + 5）* 2，6 * 2 % 10 = (1 + 5) * 2 % 10 = 2
因此每次记录除以 5 的余数即可。

At first I used brute force and it timed out 🤕
Then I read the answer and realized that each time you add one digit, it’s just the previous number shifted left plus the current digit, i.e., twice the previous number plus the current digit, which is faster.
Later I found that checking divisibility by 5 only needs the ones digit, i.e., the remainder of division by 10.
Also, for the ones digit 6, 6 = 1 + 5, 6 * 2 = (1 + 5) * 2, 6 * 2 % 10 = (1 + 5) * 2 % 10 = 2
Therefore, just record the remainder of division by 5 each time.

1046–最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000

1046–Last Stone Weight

You are given an array of integers stones where stones[i] is the weight of the ith stone.

On each turn, we choose the heaviest two stones and smash them together. Suppose the stones have weights x and y with x <= y. The possible results of this smash are:

If x == y, both stones are completely destroyed;
If x != y, the stone of weight x is completely destroyed, and the stone of weight y has new weight y - x.
At the end, there is at most one stone left. Return the weight of the last remaining stone. If there are no stones left, return 0.

Example:

Input: [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1, so the array converts to [2,4,1,1,1],
then we combine 2 and 4 to get 2, so the array converts to [2,1,1,1],
then we combine 2 and 1 to get 1, so the array converts to [1,1,1],
finally we combine 1 and 1 to get 0, and the final array converts to [1], which is the weight of the last remaining stone.

Constraints:

1 <= stones.length <= 30
1 <= stones[i] <= 1000

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
class Solution:
    def lastStoneWeight(self, stones: list) -> int:
        while 1:
            if len(stones) == 0:
                return 0
            if len(stones) == 1:
                return stones[0]
            Max1 = max(stones)
            stones.pop(stones.index(Max1))
            Max2 = max(stones)
            stones.pop(stones.index(Max2))
            if Max1 != Max2:
                stones.append(Max1 - Max2 if Max1 > Max2 else Max2 - Max1)


    #### heapq 实现大根堆
    def lastStoneWeight_1(self, stones: List[int]) -> int:
        # 初始化
        heap = [-stone for stone in stones]
        heapq.heapify(heap)

        # 模拟
        while len(heap) > 1:
            x,y = heapq.heappop(heap),heapq.heappop(heap)
            if x != y:
                heapq.heappush(heap,x-y)

        if heap: return -heap[0]
        return 0

我的代码用了好多函数和方法，感觉有点无耻。但是 C++ 里的 vector 也有类似的功能吧。

我也不太确定做这种题 方法和函数 怎么用才不算过分。

My code uses a lot of functions and methods, which feels a bit shameless. But the vector in C++ probably has similar functionality too.

I’m not really sure how much is too much when using methods and functions for this kind of problem.

1232–缀点成线

在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。

请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。

示例 1：

输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true
示例 2：

输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

提示：

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates 中不含重复的点

1232–Check If It Is a Straight Line

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. The array represents a set of points in an XY-coordinate system.

Check if these points make a straight line in the XY plane. Return true if they do, otherwise return false.

Example 1:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true
Example 2:

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false

Constraints:

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates contains no duplicate points

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        n = len(coordinates)
        if n == 2:return True
        dx = coordinates[1][0] - coordinates[0][0]
        dy = coordinates[1][1] - coordinates[0][1]

        for i in range(2,n):
            dx1 = coordinates[i][0] - coordinates[0][0]
            dy1 = coordinates[i][1] - coordinates[0][1]
            if dx1 * dy != dy1 * dx: 
                return False
        return True

注意，比较斜率相等与否，把除法转换成乘法，一方面可以避免除 0 的问题发生，另一方面乘法的计算似乎比除法简单一些。

❌

Note that when comparing whether slopes are equal, convert division into multiplication. On the one hand, it avoids division by zero; on the other hand, multiplication seems cheaper to compute than division.

123–买股票的最佳时机（三）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 105

123–Best Time to Buy and Sell Stock III

You are given an array where the ith element is the price of a given stock on day i.

Design an algorithm to calculate the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, because that would be engaging in multiple transactions at the same time. You must sell the stock before buying again.
Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, so the maximum profit is 0.
Example 4:

Input: prices = [1]
Output: 0

Constraints:

1 <= prices.length <= 105
0 <= prices[i] <= 105

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy1 = buy2 = -prices[0]
        sell1 = sell2 = 0
        for i in range(1,len(prices)):
            buy1 = max(buy1,-prices[i])
            sell1 = max(sell1,buy1+prices[i])
            buy2 = max(buy2,sell1-prices[i])
            sell2 = max(sell2,buy2+prices[i])
        
        return sell2

可怕的动态规划。

Terrifying dynamic programming.

188–买股票的最佳时机（四）

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：
0 <= k <= 109
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

188–Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Design an algorithm to calculate the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (you must sell the stock before you buy again).

Example 1:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Constraints:
0 <= k <= 109
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

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
36
37
38
39
40
41
42
43
class Solution:
    def maxProfit(self, k: int , prices: [int]) -> int:
        if not prices:
        	return 0

        n = len(prices)
        k = min(k, n // 2)
        buy = [[0] * (k + 1) for _ in range(n)]
        sell = [[0] * (k + 1) for _ in range(n)]

        buy[0][0],sell[0][0] = -prices[0],0

        for i in range(1,k + 1):
        	buy[0][i] = sell[0][i] = float("-inf")


        for i in range(1,k + 1):
        	buy[i][0] = max(buy[i-1][0],sell[i-1][0] - prices[i])
        	for j in range(1,n):
        		buy[i][j] = max(buy[i - 1][j],sell[i - 1][j] - prices[i])
        		sell[i][j] = max(sell[i - 1][j],buy[i-1][j-1] + prices[i])

        return max(sell[n-1])
    def maxProfit_Opt(self, k:int , prices:[int]) -> int:
    	if not prices:
    		return 0

    	n = len(prices)
    	k = min(k, n // 2)
    	buy = [0] * (k+1)
    	sell = [0] * (K+1)

    	buy[0],sell[0] = -prices[0] ,0
    	for i in range(1,k + 1):
    		buy[i] = sell[i] = float("-inf")

    	for i in range(1,n):
    		buy[0] = max(buy[0],sell[0] - prices[i])
    		for j in range(1 , k + 1):
    			buy[j] = max(buy[j],sell[j] - prices[i])
    			sell[j] = max(sell[j],buy[j-1] + prices[i])

    	return max(sell)

可怕的动态规划。

Terrifying dynamic programming.

239–滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：

输入：nums = [1], k = 1
输出：[1]
示例 3：

输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4：

输入：nums = [9,11], k = 2
输出：[11]
示例 5：

输入：nums = [4,-2], k = 2
输出：[4]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

239–Sliding Window Maximum

You are given an array of integers nums, and there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the maximum in the sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:

Input: nums = [1], k = 1
Output: [1]
Example 3:

Input: nums = [1,-1], k = 1
Output: [1,-1]
Example 4:

Input: nums = [9,11], k = 2
Output: [11]
Example 5:

Input: nums = [4,-2], k = 2
Output: [4]

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

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 maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        '''
        头脑简单的超时解法
        '''
        result = []
        for i in range(len(nums) - k + 1):
            result.append(max(nums[i:i+k]))
        return result
    def maxSlidingWindow_2(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # 注意 Python 默认的优先队列是小根堆
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)

        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heapq.heappop(q)
            ans.append(-q[0][0])
        
        return ans

可怕的优先队列（堆）。

Terrifying priority queue (heap).

684–冗余连接

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 1：

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
1
/
2 - 3
示例 2：

输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1 - 2
| |
4 - 3
注意:

输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。

684–Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with N nodes (labeled with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed in the tree.

The result graph is represented as a 2D-array of edges. Each edge is a pair of [u, v] with u < v, that represents an undirected edge connecting vertices u and v.

Return an edge that can be removed so that the resulting graph is a tree with N nodes. If there are multiple answers, return the edge that appears last in the input 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
1
/
2 - 3
Example 2:

Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
| |
4 - 3
Note:

The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:

        nodesCount = len(edges)
        parent = list(range(nodesCount + 1))

        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1: int, index2: int):
            parent[find(index1)] = find(index2)

        for node1, node2 in edges:
            if find(node1) != find(node2):
                union(node1, node2)
            else:
                return [node1, node2]
        
        return []

可怕的并查集。

Terrifying union-find.

803–敲砖块

有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：

一块砖直接连接到网格的顶部，或者
至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。

返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。

注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

示例 1：

输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
输出：[2]
解释：
网格开始为：
[[1,0,0,0]，
[1,1,1,0]]
消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0]
[0,1,1,0]]
两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
[[1,0,0,0],
[0,0,0,0]]
因此，结果为 [2] 。
示例 2：

输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
输出：[0,0]
解释：
网格开始为：
[[1,0,0,0],
[1,1,0,0]]
消除 (1,1) 处加粗的砖块，得到网格：
[[1,0,0,0],
[1,0,0,0]]
剩下的砖都很稳定，所以不会掉落。网格保持不变：
[[1,0,0,0],
[1,0,0,0]]
接下来消除 (1,0) 处加粗的砖块，得到网格：
[[1,0,0,0],
[0,0,0,0]]
剩下的砖块仍然是稳定的，所以不会有砖块掉落。
因此，结果为 [0,0] 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] 为 0 或 1
1 <= hits.length <= 4 * 104
hits[i].length == 2
0 <= xi <= m - 1
0 <= yi <= n - 1
所有 (xi, yi) 互不相同

803–Bricks Falling Down

There is a binary grid of m x n cells, where 1 represents a brick and 0 represents an empty space. A brick is stable (does not fall) if:

  • It is directly connected to the top of the grid, or
  • At least one of its adjacent bricks (in one of the 4 directions) is stable.

You are given an array hits, which are positions of bricks to be erased sequentially. Whenever we erase a brick located at hits[i] = (rowi, coli), the brick at that location (if it exists) will disappear, and then other bricks may drop as a result of this operation. Once a brick drops, it immediately disappears from the grid (i.e., it does not land on other stable bricks).

Return an array result, where result[i] is the number of bricks that will drop after the ith erasure.

Note that an erasure may refer to a position where no brick exists; if so, no brick drops.

Example 1:

Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: [2]
Explanation:
The grid begins:
[[1,0,0,0]，
[1,1,1,0]]
Erasing the bolded brick at (1,0), the grid becomes:
[[1,0,0,0]
[0,1,1,0]]
The two bolded bricks are no longer stable because they are no longer connected to the top, nor adjacent to another stable brick, so they will fall. The grid becomes:
[[1,0,0,0],
[0,0,0,0]]
Therefore, the result is [2] .
Example 2:

Input: grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
Output: [0,0]
Explanation:
The grid begins:
[[1,0,0,0],
[1,1,0,0]]
Erasing the bolded brick at (1,1), the grid becomes:
[[1,0,0,0],
[1,0,0,0]]
The remaining bricks are all stable, so no bricks fall. The grid remains:
[[1,0,0,0],
[1,0,0,0]]
Next, erasing the bolded brick at (1,0), the grid becomes:
[[1,0,0,0],
[0,0,0,0]]
The remaining bricks are still stable, so no bricks fall.
Therefore, the result is [0,0] .

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] is 0 or 1
1 <= hits.length <= 4 * 104
hits[i].length == 2
0 <= xi <= m - 1
0 <= yi <= n - 1
All (xi, yi) are unique.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class UnionFind:
	def __init__(self):
		self.father = {}
		self.size_of_set = {}

	def get_size_of_set(self,x):
		'''
		获取所在连通块的大小
		'''
		return self.size_of_set[self.find(x)]

	def find(size,x):
		root = x

		while self.father[root] != None:
			root = self.father[root]

		# 路径压缩
		while x != root:
			original_father = self.father[x]
			self.father[x] = root
			x = original_father
		
		return root

	def is_connected(self,x,y):
		return self.find(x) == self.find(y)

	def merge(self,x,y):
		root_x,root_y = self.find(x),self.find(y)

		if root_x != root_y:
			self.father[root_x] = root_y
			# 更新根节点连通块数量
			self.size_of_set[root_y] += self.size_of_set[root_x]
			del self.size_of_set[root_x]

	def add(self,x):
		if x not in self.father:
			self.father[x] = None
			self.size_of_set[x] = 1



class Solution:
	def __init__(self):
		self.CEILING = (-1,-1)
		self.DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))

	def initalize(self,uf,m,n,grid,hits):
		'''
		初始化
		'''
		# 添加天花板
		uf.add(self.CEILING)

		# 敲掉所有要敲掉的砖块
		for x,y in hits:
			grid[x][y] -= 1

		# 连接，合并剩余的砖块
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					uf.add((i,j))

		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					self.merge_neighbors(uf,m,n,grid,i,j)

		# 与天花板合并
		for j in range(n):
			if grid[0][j] == 1:
				uf.merge((0,j),self.CEILING)

	def is_valid(self,x,y,grid,m,n):
		return 0 <= x < m and 0 <= y < n and grid[x][y] == 1

	def merge_neighbors(self,uf,m,n,grid,x,y):
		'''
		与上下左右的砖块合并
		'''
		for dx,dy in self.DIRECTION:
			nx,ny = x + dx,y+dy
			if not self.is_valid(nx,ny,grid,m,n):
				continue
			uf.merge((x,y),(nx,ny))


    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
    	uf = UnionFind()
    	m,n = len(grid),len(grid[0])
    	res = [0] + len(hits)

    	# 初始化
    	self.initalize(uf,m,n,grid,hits)

    	for i in range(len(hits)-1,-1,-1):
    		x,y = hits[i][0],hits[i][1]

    		# 还原敲击
    		grid[x][y] += 1

    		# 敲的地方原本就不是砖块
    		if grid[x][y] != 1:
    			continue

哎，练练敲代码吧。

Sigh, let’s practice writing code a bit more.

947–移除最多的同行或同列石头

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

示例 1：

输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：

  1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
  2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
  3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
  4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
  5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
    石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。
    示例 2：

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：

  1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
  2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
  3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
    石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。
    示例 3：

输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。

提示：

1 <= stones.length <= 1000
0 <= xi, yi <= 104
不会有两块石头放在同一个坐标点上

947–Most Stones Removed with Same Row or Column

n stones are placed on a 2D plane at some integer coordinate points. There can be at most one stone per coordinate point.

If a stone shares either the same row or the same column as another stone, it can be removed.

You are given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the maximum possible number of stones that can be removed.

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Explanation: One way to remove 5 stones is as follows:

  1. Remove stone [2,2] because it shares the same row as [2,1].
  2. Remove stone [2,1] because it shares the same column as [0,1].
  3. Remove stone [1,2] because it shares the same row as [1,0].
  4. Remove stone [1,0] because it shares the same column as [0,0].
  5. Remove stone [0,1] because it shares the same row as [0,0].
    Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.
    Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Explanation: One way to remove 3 stones is as follows:

  1. Remove stone [2,2] because it shares the same row as [2,0].
  2. Remove stone [2,0] because it shares the same column as [0,0].
  3. Remove stone [0,2] because it shares the same row as [0,0].
    Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.
    Example 3:

Input: stones = [[0,0]]
Output: 0
Explanation: [0,0] is the only stone on the plane, so you cannot remove it.

Constraints:

1 <= stones.length <= 1000
0 <= xi, yi <= 104
No two stones are at the same coordinate point.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class Solution:
	def removeStones(self, stones: List[List[int]]) -> int:
		'''
		优化建图 + 深度优先
		'''
		n = len(stones)
		edge = collections.defaultdict(list)
		rec = collections.defaultdict(list)
		for i,(x,y) in enumerate(stones):
			rec[x].append(i)
			rec[1000 + y].append(i)

		for vec in rec.values():
			k = len(vec)
			for i in range(1,k):
				edge[vec[i]].append(vec[i-1])
				edge[vec[i-1]].append(vec[i])

		def dfs(node):
			vis.add(node)
			for y in edge[node]:
				if y not in vis:
					dfs(y)

		vis = set()
		num = 0
		for i in range(n):
			if i not in vis:
				num += 1
				dfs(i)

		return n - num




    def removeStones_1(self, stones: List[List[int]]) -> int:
    	'''
    	深度优先
    	'''
        n = len(stones)
        edge = collections.defaultdict(list)
        for i, (x1, y1) in enumerate(stones):
            for j, (x2, y2) in enumerate(stones):
                if x1 == x2 or y1 == y2:
                    edge[i].append(j)
        
        def dfs(x: int):
            vis.add(x)
            for y in edge[x]:
                if y not in vis:
                    dfs(y)
        
        vis = set()
        num = 0
        for i in range(n):
            if i not in vis:
                num += 1
                dfs(i)
        
        return n - num







    def removeStones_2(self, stones: List[List[int]]) -> int:
    	'''
    	优化建图 + 并查集
    	'''
        dsu = DisjointSetUnion()
        for x, y in stones:
            dsu.unionSet(x, y + 10000)
        return len(stones) - dsu.numberOfConnectedComponent()
class DisjointSetUnion:
    def __init__(self):
        self.f = dict()
        self.rank = dict()
    
    def find(self, x: int) -> int:
        if x not in self.f:
            self.f[x] = x
            self.rank[x] = 1
            return x
        if self.f[x] == x:
            return x
        self.f[x] = self.find(self.f[x])
        return self.f[x]
    
    def unionSet(self, x: int, y: int):
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return
        if self.rank[fx] < self.rank[fy]:
            fx, fy = fy, fx
        self.rank[fx] += self.rank[fy]
        self.f[fy] = fx

    def numberOfConnectedComponent(self) -> int:
        return sum(1 for x, fa in self.f.items() if x == fa)

对于这种题，我现在的目标只有一个，就是看见能看出题目背景下隐藏的是什么数据结构或者算法问题。

刚看第一眼以为是图？看着不像啊。动态规划？也不会。手工算法都想不出来，更别提写代码了。😪

For this kind of problem, my only goal now is to be able to see, at first glance, what data structure or algorithm is hidden behind the problem statement.

At first glance I thought it was a graph? Doesn’t look like one. Dynamic programming? Don’t know it either. I can’t even come up with a hand algorithm, let alone write code.😪

1202–交换字符串中的元素

给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

示例 1:

输入：s = “dcab”, pairs = [[0,3],[1,2]]
输出：“bacd”
解释：
交换 s[0] 和 s[3], s = “bcad”
交换 s[1] 和 s[2], s = “bacd”
示例 2：

输入：s = “dcab”, pairs = [[0,3],[1,2],[0,2]]
输出：“abcd”
解释：
交换 s[0] 和 s[3], s = “bcad”
交换 s[0] 和 s[2], s = “acbd”
交换 s[1] 和 s[2], s = “abcd”
示例 3：

输入：s = “cba”, pairs = [[0,1],[1,2]]
输出：“abc”
解释：
交换 s[0] 和 s[1], s = “bca”
交换 s[1] 和 s[2], s = “bac”
交换 s[0] 和 s[1], s = “abc”

提示：

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母

1202–Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates two indices (0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = “dcab”, pairs = [[0,3],[1,2]]
Output: “bacd”
Explanation:
Swap s[0] and s[3], s = “bcad”
Swap s[1] and s[2], s = “bacd”
Example 2:

Input: s = “dcab”, pairs = [[0,3],[1,2],[0,2]]
Output: “abcd”
Explanation:
Swap s[0] and s[3], s = “bcad”
Swap s[0] and s[2], s = “acbd”
Swap s[1] and s[2], s = “abcd”
Example 3:

Input: s = “cba”, pairs = [[0,1],[1,2]]
Output: “abc”
Explanation:
Swap s[0] and s[1], s = “bca”
Swap s[1] and s[2], s = “bac”
Swap s[0] and s[1], s = “abc”

Constraints:

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lowercase English letters.

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
36
37
38
39
40
41
42
43
44
class DisjointSetUnion:
	'''
	并查集 还要学 先记录下来
	'''
    def __init__(self, n: int):
        self.n = n
        self.rank = [1] * n
        self.f = list(range(n))
    
    def find(self, x: int) -> int:
        if self.f[x] == x:
            return x
        self.f[x] = self.find(self.f[x])
        return self.f[x]
    
    def unionSet(self, x: int, y: int):
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return
        if self.rank[fx] < self.rank[fy]:
            fx, fy = fy, fx
        self.rank[fx] += self.rank[fy]
        self.f[fy] = fx
        
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        dsu = DisjointSetUnion(len(s))
        for x, y in pairs:
            dsu.unionSet(x, y)
        
        mp = collections.defaultdict(list)
        for i, ch in enumerate(s):
            mp[dsu.find(i)].append(ch)
        
        for vec in mp.values():
            vec.sort(reverse=True)
        
        ans = list()
        for i in range(len(s)):
            x = dsu.find(i)
            ans.append(mp[x][-1])
            mp[x].pop()
        
        return "".join(ans)

可怕的并查集。

Terrifying union-find.

1203–项目管理

公司共有 n 个项目和 m 个小组，每个项目要不无人接手，要不就由 m 个小组之一负责。

group[i] 表示第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）小组可能存在没有接手任何项目的情况。

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

同一小组的项目，排序后在列表中彼此相邻。
项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。
如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

示例 1：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
输出：[6,3,4,1,5,2,0,7]
示例 2：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
输出：[]
解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。

提示：

1 <= m <= n <= 3 * 104
group.length == beforeItems.length == n
-1 <= group[i] <= m - 1
0 <= beforeItems[i].length <= n - 1
0 <= beforeItems[i][j] <= n - 1
i != beforeItems[i][j]
beforeItems[i] 不含重复元素

1203–Sort Items by Groups Respecting Dependencies

There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it’s equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have any number of items that belong to it.

Help us sort the items and return the sorted list of items:

Items that belong to the same group should be next to each other in the sorted list.
There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).
If there are multiple solutions, return any one of them. If there is no solution, return an empty list.

Example 1:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]
Example 2:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
Output: []
Explanation: This is basically the same as example 1 except that 4 must be placed before 6 in the sorted list.

Constraints:

1 <= m <= n <= 3 * 104
group.length == beforeItems.length == n
-1 <= group[i] <= m - 1
0 <= beforeItems[i].length <= n - 1
0 <= beforeItems[i][j] <= n - 1
i != beforeItems[i][j]
beforeItems[i] does not contain duplicate elements.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution:
	'''
	两次拓扑排序
	'''
    def topological_sort(self,items,indegree,neighbors):
        # 建立队列和访问顺序
        queue = collections.deque()
        res = []
        
        # 初始化队列
        for item in items:
            if not indegree[item]:
                queue.append(item)
                
        if not queue: return []
        
        # BFS
        while queue:
            cur = queue.popleft()
            res.append(cur)
            
            # 遍历邻居节点
            for neighbor in neighbors[cur]:
                indegree[neighbor] -= 1
                if not indegree[neighbor]:
                    queue.append(neighbor)
                    
        return res
    
    
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        max_group_id = m
        for task in range(n):
            if group[task] == -1:
                group[task] = max_group_id
                max_group_id += 1
                
        task_indegree = [0] * n    
        group_indegree = [0] * max_group_id
        task_neighbors = [[] for _ in range(n)]
        group_neighbors = [[] for _ in range(max_group_id)]
        group_to_tasks = [[] for _ in range(max_group_id)]
        
        for task in range(n):
            group_to_tasks[group[task]].append(task)
            
            for prerequisite in beforeItems[task]:
                
                # 判断相关联的两个项目是否属于同一组
                if group[prerequisite] != group[task]:
                    
                    # 不是同组，给小组建图
                    group_indegree[group[task]] += 1
                    group_neighbors[group[prerequisite]].append(group[task])
                else:
                    # 同组，给组内项目建图
                    task_indegree[task] += 1
                    task_neighbors[prerequisite].append(task)
                    

        res = []
        
        # 得到小组的访问顺序
        group_queue = self.topological_sort([i for i in range(max_group_id)],group_indegree,group_neighbors)

        if len(group_queue) != max_group_id: return []
        
        for group_id in group_queue:
            # 得到每组项目的访问顺序
            task_queue = self.topological_sort(group_to_tasks[group_id],task_indegree,task_neighbors)

            if len(task_queue) != len(group_to_tasks[group_id]):
                return []
            res += task_queue
                    
        return res

可怕的拓扑排序。

Terrifying topological sort.