注意：这篇文章上次更新于1290天前，文章内容可能已经过时。
为了能够实现进大厂被资本家无情压迫的梦想，坚持每天一道题。🤑
先用 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
只会存在一个有效答案
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
题目数据保证列表表示的数字不含前导零
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 由英文字母、数字、符号和空格组成
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
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
# 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) 的 原地 算法。
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 按升序排列
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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
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
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]
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 是非负整数，且不会超过输入数组的大小。
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
注意: 合并必须从两个树的根节点开始。
# 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”
输出：[]
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
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
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 中不含重复的点
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
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
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
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是输入数组的大小。
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) 互不相同
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 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,1] 同行。
- 移除石头 [2,1] ，因为它和 [0,1] 同列。
- 移除石头 [1,2] ，因为它和 [1,0] 同行。
- 移除石头 [1,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。
示例 2：
输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,0] 同行。
- 移除石头 [2,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。
示例 3：
输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。
提示：
1 <= stones.length <= 1000
0 <= xi, yi <= 104
不会有两块石头放在同一个坐标点上
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 中只含有小写英文字母
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] 不含重复元素
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可怕的拓扑排序。
