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

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

这里是我的代码仓库✨

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

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

简单记一下做题感受。😶

✔️

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
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 []

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

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
题目数据保证列表表示的数字不含前导零

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

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

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 由英文字母、数字、符号和空格组成

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

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

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

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

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

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

86–分隔链表

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

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

示例：

输入：head = 1->4->3->2->5->2, x = 3
输出：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

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

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) 的 原地 算法。

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]

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

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

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

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 按升序排列

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

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

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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

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

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

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

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

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

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

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]

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

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

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

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 是非负整数，且不会超过输入数组的大小。

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

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

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

617–合并二叉树

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

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

示例 1:

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

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

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

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”
输出：[]

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

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

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

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 的余数即可。

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

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 也有类似的功能吧。

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

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 中不含重复的点

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 的问题发生，另一方面乘法的计算似乎比除法简单一些。

❌

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

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

可怕的动态规划。

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

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)

可怕的动态规划。

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

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

可怕的优先队列（堆）。

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是输入数组的大小。

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 []

可怕的并查集。

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) 互不相同

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

哎，练练敲代码吧。

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
不会有两块石头放在同一个坐标点上

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)

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

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

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 中只含有小写英文字母

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)

可怕的并查集。

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] 不含重复元素

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

可怕的拓扑排序。