这个笔记用来记录 第一次刷 LeetCode Hot 100

1. 两数之和1-251210

tag: 哈希表

1
2
3
4
5
6
7
8
9
class Solution:
	def twoSum(self, nums: List[int], target: int) -> List[int]:
		dic = {}
		for i in range(len(nums)):
			residual = target - nums[i]
		if nums[i] in dic.keys():
			return [i, dic[nums[i]]]
		if residual not in dic.keys():
			dic[residual] = i

对每个数 留下 索引（value） 以及 到 target 的差（index），之后遇到 target差 的数，直接读出索引就行

2. 字母异位词分组49-251210

tag: 哈希表 排序

思路一：哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:

	def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
		map = {}
		for item in strs:
			v = self.str2value(item)
			if v in map.keys():
				map[v].append(item)
			else:
				map[v] = [item]
		return list(map.values())
	
	def str2value(self, stR:str) -> int :
		res = 0
		for char in stR:
			index = ord(char)-ord('a')
			res += 10**(index)
		return res*len(stR)

第一次的思路就是 把一个 str 得到一个顺序无关的哈希值。但是复杂度好像有点高。

更好的实现方式：使用了 from collections import defaultdict 内置函数

使用 defaultdict 是内置 dict 的子类，核心特性是，当访问不存在的键时，会自动创建这个键并赋值为 指定默认值 而不是抛出 KeyError。例如：初始化 mp=collections.defaultdict(list) 如果访问了不存在的键就会默认为空list （传入int就是默认0）

还有一个 dict 的索引不能是 list dict set，可以是int float tuple str bool None frozenset ，list 可以转为tuple

1
2
3
4
5
6
7
8
9
10
class Solution:
	def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
		dic = collections.defaultdict(list)
		for s in strs:
			count = [0] * 26
			for c in s:
				count[ord(c)-ord('a')]+=1
			# 这一步的时间复杂度是 O(k)+1 ,k=26 tuple生成这个hash值需要 list长度的时间
			dic[tuple(count)].append(s)
		return list(dic.values())

这个方法时间复杂度是 O(n(k+s)) s是字符集的大小 26，每个 str 要 k 来遍历字符， s来生成 hash表的键。

思路二-排序* 最优

对每个str排序，然后将排序的这个 字符串 当做字典的索引（哈希值）时间复杂度是 O(nklogk)

内置函数 sorted 函数 输入字符串 返回一个按照 unicode 编码的 char list
‘’.join(list(char)) 把charlist 拼成一个串 注意这个join是 字符串的子函数

1
2
3
4
5
6
7
class Solution:
	def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
		dic = collections.defaultdict(list)
		for s in strs:
			index = ''.join(sorted(s))
			dic[index].append(s)
		return list(dic.values())

3. 最长连续序列128-251210

tag: 并查集 set

这个题要求了时间复杂度为O(n) 所以不考虑排序的方法，首先用 set 对 nums 去重，然后找到 所有序列开头的数字 并计算 这个序列的长度，由于每个数仅进入一次内层循环，所以时间复杂度符合要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	def longestConsecutive(self, nums: List[int]) -> int:
		res = 0
		nums_set = set(nums)
		for i in nums_set:
			if i-1 in nums_set:
				continue
			# 否则说明这个数是 一个序列的开头
			l = 1
			p = i+1
			while p in nums_set:
				l+=1
				p+=1
			res = max(res,l)
		return res

下面这个节省20ms的时间

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
	def longestConsecutive(self, nums: List[int]) -> int:
		res = 0
		nums_set = set(nums)
		for i in nums_set:
			if i-1 in nums_set:
				continue
			# 否则说明这个数是 一个序列的开头
			p = i+1
			while p in nums_set:
				p+=1
			res = max(res,p-i)
		return res

这个算法的关键是找到起点 避免对一个数的重复遍历
list 转 set 还有 判断 in set 的操作 时间复杂度是 O(1), 如果是用 list 的 in 时间复杂度是 O(n)

4. 移动零283-251210

tag: 双指针 快慢指针

思路一 遇到零放后面

list ： remove是移除 第一个 value，pop是删掉指定index的item
顺序遍历，把0移到最后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	def moveZeroes(self, nums: List[int]) -> None:
		"""
		Do not return anything, modify nums in-place instead.
		"""
		i=0
		last = len(nums)
		while i < last :
			if nums[i] == 0 :
				nums.pop(i)
				nums.append(0)
				last-=1
				i-=1
			i+=1

思路二 栈 遇到非零压入栈

1
2
3
4
5
6
7
8
class Solution:
	def moveZeroes(self, nums: List[int]) -> None:
		stack_size=0
		for num in nums:
			if num :
				nums[stack_size] = num
				stack_size+=1
		nums[stack_size:len(nums)] = [0]*(len(nums)-stack_size)

这个方法在最坏的情况下（全是0） 要遍历两次数组

思路三 双指针* 最优

依次把非零元素移动到 数组靠左边的空位置上。参考快速排序的想法，快拍要确定一个待分割的元素x作为中间点，然后小于等于x放到左边，大于x放到右边。

一个指向第一个0 另一个遇到第一个非零就和第一个0换位置，然后指向第一个0的后移一位（仍然是第一个0） （这个理解好像不太好）

换一个想法，两个指针，慢的说明 其左边 全部都是 保留顺序的非零（也就是指向待处理序列的第一个，只有交换了也就是处理好了，才移动），快的去找下一个需要被处理的非零数字。这样保留了原本的顺序。

1
2
3
4
5
6
7
8
class Solution:
	def moveZeroes(self, nums: List[int]) -> None:
		slow=fast=0
		while fast < len(nums):
			if nums[fast]:
				nums[slow],nums[fast]=nums[fast],nums[slow]
				slow+=1
			fast+=1

5. 盛最多水的容器11-251210

tag: 双指针

首先对于壁 i<j 有: .
每次移动 width 一定会减少1，那么只有 min h 变大才会得到更多的水，所以每次需要让短的板子移动。
为什么双指针合理呢？我觉得有的算法的做法就是通过数学思路，舍弃掉 暴搜 的大部分区域，对于这个而言，爆搜的空间有 , 然后通过证明可以省掉很多搜索空间。

得到代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	def S(self,i,j,h):
		h = h[i] if h[i]<h[j] else h[j]
		return abs(i-j)*h
	  
	def maxArea(self, height: List[int]) -> int:
		ans=0
		i,j = 0,len(height)-1
		while i!=j :
			ans = max(self.S(i,j,height),ans)
			if height[i]<height[j] :
				i+=1
			else :
				j-=1
		return ans

另一种想法，移动一边一定导致宽度下降，那么如果min(h,h)没有变大，就不需要计算，直接跳过就可以，直到高的最小值变大：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
	def maxArea(self, height: List[int]) -> int:
		l, r = 0, len(height) - 1
		ans = 0
		while l < r:
		# w = r - l
		h = min(height[l], height[r])
		ans = max(ans, (r - l) * h)
		while height[l] <= h and l < r: l += 1
		while height[r] <= h and l < r: r -= 1
	return ans

通过节省搜索空间的想法，还可以进一步，通过记录高度的最大值，得到最大的S，然后直接return

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
	def maxArea(self, height: List[int]) -> int:
		max_area = 0
		l, r = 0, len(height) - 1
		max_height = max(height)
		  
		while l < r:
			if max_height * (r - l) < max_area:
				return max_area
			cur_area = min(height[l], height[r]) * (r - l)
			if cur_area > max_area:
				max_area = cur_area
			if height[l] > height[r]:
				r -= 1
			else:
				l += 1
		return max_area

6. 三数之和15-251211

tag: 双指针

最简单的想法 对于每个数 当做一个两数之和来做，但是由于两数之和的解法复杂度是 ，这种做法的复杂度是 .

还有一种是用双指针，来找和为 0 的 也是最优的。

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
class Solution:
	def threeSum(self, nums: List[int]) -> List[List[int]]:
		nums.sort()
		ans = []
		n = len(nums)
		for i in range(n - 2):
			x = nums[i]
			if i > 0 and x == nums[i - 1]: # 跳过重复数字
				continue
			if x > 0 or nums[-1]<0 : # 优化一
				break
			if x + nums[-2] + nums[-1] < 0: # 优化二
				continue
			j = i + 1
			k = n - 1
			while j < k:
				s = x + nums[j] + nums[k]
				if s > 0:
					k -= 1
				elif s < 0:
					j += 1
				else: # 三数之和为 0
					ans.append([x, nums[j], nums[k]])
					j += 1
					while j < k and nums[j] == nums[j - 1]: # 跳过重复数字
						j += 1
					k -= 1
					while k > j and nums[k] == nums[k + 1]: # 跳过重复数字
						k -= 1
		return ans

这个方法和 第一个复杂度都是 但是双指针要快一些啊，是因为 枚举 + 哈希表法虽是 O (n²)，但哈希表的额外开销、随机内存访问导致常数项远大于双指针；1. 双指针法的「」是真 （外层 n 次，内层 n 次），且常数项极小；

7. 接雨水42-251211

tag: 单调栈 动态规划 双指针

思路一：单调栈*

最开始的思路是 遍历所有h 而不是index 有一个问题就是，如果相等的话之后来了更高的没办法记录宽度，所以尝试用index做一下

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
	def trap(self, height: List[int]) -> int:
		stack = []
		ans = 0
		for i,h in enumerate(height) :
			while stack and h > height[stack[-1]] :
				top = stack.pop()
				if not stack :
					break
				# 这个是重点部分 好好想一下
				ans += (min(height[stack[-1]],h)-height[top])*(i-stack[-1]-1)
			stack.append(i)
		return ans

这个部分我觉得最难的是 每次加多少面积，由于单调栈有单调递减的特征，所以栈顶元素一定是最小的，计算的思路就是 记录 每次pop 添加的水 是一排 就是接雨水 水平线往上的？

思路二：动态规划

每个位置 i 能接的水的数量 = min( i 左边的最大高度, i 右边的最大高度) - h[i] ,所以暴力搜索就是：

1
2
3
4
5
6
7
8
9
class Solution:
	def trap(self, height: List[int]) -> int:
		ans = 0
		l = len(height)
		dp = [0] * l
		# 暴力
		for i in range(1,l-1) :
			dp[i] = max(min(max(height[0:i]),max(height[i+1:])) - height[i],0)
		return sum(dp)

在内循环中，在数组中找max操作复杂度为 , 所以这个暴力搜索的复杂度为 ，通过 动态规划的思路 先用两个list： 来记录 index i 左边的最大和右边的最大height是多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
	def trap(self, height: List[int]) -> int:
		l = len(height)
		ans = [0] * l
		# 左侧最大值 不包括
		leftMax = [0] * l
		# 右侧最大值 不包括
		rightMax = [0] * l
		maxh = 0
		maxr = 0
		# 这里也可以用动态规划的状态转移方程 会更快
		for i in range(l) :
			leftMax[i] = maxh
			maxh = maxh if maxh > height[i] else height[i]
			rightMax[l-1-i] = maxr
			maxr = maxr if maxr > height[l-1-i] else height[l-1-i]
		for i in range(1,l-1) :
			# ans[i] = max(min(max(height[0:i]),max(height[i+1:])) - height[i],0)
			ans[i] = max(min(leftMax[i],rightMax[i]) - height[i],0)
		return sum(ans)

思路三：双指针

本质上和动态规划类似，只是用双指针的方法可以把空间复杂度减到O1，时间复杂度还是 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	def trap(self, height: List[int]) -> int:
		ans = 0
		left, right = 0, len(height) - 1
		leftMax = rightMax = 0
		while left < right:
			leftMax = max(leftMax, height[left])
			rightMax = max(rightMax, height[right])
			if height[left] < height[right]:
				ans += leftMax - height[left]
				left += 1
			else:
				ans += rightMax - height[right]
				right -= 1
		return ans

8. 无重复字符的最长子串3-251212

tag: 滑动窗口

这个比较简单，可以学习一下别人的代码思路。下面这个是我的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	def lengthOfLongestSubstring(self, s: str) -> int:
		ans,i,l = 0,0,len(s)
		window = collections.deque()
		count = collections.defaultdict(int)
		while i < l :
			while i < l and count[s[i]] == 0 :
				window.append(s[i])
				count[s[i]] += 1
				i += 1
				ans = max(len(window),ans)
			while i < l and count[s[i]]!=0 :
				f = window.popleft()
				count[f] -= 1
		return ans

用 set（字典本身就适合处理 是否重复这样的事情）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 滑动窗口
        left = 0
        window = set()
        max_length = 0
        for right in range(len(s)):
            while s[right] in window:
                window.remove(s[left])
                left += 1
            window.add(s[right])
            if len(window) > max_length:
                max_length = len(window)
        return max_length

这个2ms 最快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	def lengthOfLongestSubstring(self, s: str) -> int:
		n = len(s)
		if n <= 1:
			return n
		_dict = {}
		start = -1
		res = 0
		for i, c in enumerate( s ):
			if c in _dict and _dict[c] > start:
				start = _dict[c]
			res = max(res, i - start)
			_dict[c] = i
		return res

9. 找到字符串中所有字母异位词438-251212

tag: 滑动窗口

自己写的解

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
class Solution:
	def findAnagrams(self, s: str, p: str) -> List[int]:
		ans = []
		count = {}
		window = collections.deque()
		for c in p :
			count[c] = 0
		for c in p :
			count[c] -= 1
		count['other'] = 0
		start = 0
		for c in s :
			window.append(c)
			if c in count.keys() :
				count[c] += 1
				while count[c] > 0 :
					f = window.popleft()
					start += 1
					count[f] -= 1
			else :
				count['other'] += 1
			while count['other'] != 0 :
				f = window.popleft()
				start += 1
				if f in count.keys() :
					count[f] -= 1
				else :
					count['other'] -= 1
			if len(window) == len(p) :
				ans.append(start)
		return ans

10. 和为 K 的子数组560-251212

tag: 前缀和

维护一个前n项和 sumn 然后 如果遇到 现在的 sumn - k 存在（x个） 那么就 有x个子数组符合

1
2
3
4
5
6
7
8
9
class Solution:
	def subarraySum(self, nums: List[int], k: int) -> int:
		ans,sumn = 0, 0
		cnt = collections.defaultdict(int)
		for n in nums:
			cnt[sumn] += 1
			sumn += n
			ans += cnt[sumn - k ]
		return ans

直到思路之后写了一次也没写对，当成两数之和了，存了index 应该是维护一个sumn为一个数的序列个数，之后再做一次

11. 滑动窗口最大值239-251215

tag: 大根堆 / 单调队列 优先队列

思路一：大根堆

对于最大值这种问题，可以 维护一个 优先队列（大根堆）来做，也就是放入新元素是按照 我们想要的顺序存好。这个思路很容易想到，要善用这个数据结构。暴力的方法是，每次加入新元素就用 来找一下窗口中的最大值，但是每个元素在整个流程中几乎被遍历k次，可以节省时间的方法就是记录在窗口中的元素的大小信息。也就是排序，但是如果每次来新的都排序，时间反而大于，因此需要我们维护一个 大根堆来做。在python中 最小堆是 ：heapq.heapify(list) 可以将一个list转换成最小堆 这个只保证堆顶是 最小的 而不是有序的

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
	def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
		maxheap = [(-nums[i],i) for i in range(0,k) ]
		# 这个python 标准库的最小堆
		heapq.heapify(maxheap)
		ans = [ -maxheap[0][0] ]
		for i in range(k,len(nums)) :
			heapq.heappush(maxheap,(-nums[i],i))
			while maxheap[0][1] < i-k+1 :
				heapq.heappop(maxheap)
			ans.append(-maxheap[0][0])
		return ans

思路二：单调队列（优先队列）*

对于下标 且 如果 nums[i] 在窗口中，那么 nums[j] 一定也在. 所以如果出现这样的递增子序列，就可以将 i 给删除掉。
因此我们可以维护一个没有被移除的队列，这个队列是单调递减的。有因为窗口滑动，左侧还需要弹出，所以用双端队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
	def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
		q = collections.deque()
		ans = []
		for i in range(0,len(nums)) :
			while q and nums[i] >= nums[q[-1]] :
				q.pop()
			q.append(i)
			while q[0] <= i-k :
				q.popleft()
			if i >= k-1 :
				ans.append(nums[q[0]])
		return ans

维护了这样的单调递减序列，保证 开头是最大的，而且开头还得在窗口中。

12. 最小覆盖子串76-251215

tag: 滑动窗口

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
class Solution:
	def minWindow(self, s:str, t: str) -> str:
		# 维护一个缺少多少的表
		w = collections.deque()
		rq = {}
		ansl ,l = 9999999,0
		ans = ''
		for c in t :
			if c in rq.keys() :
				rq[c] += 1
			else :
				rq[c] = 1
		# 处理队列，保证 rq 都得是 0
		for c in s :
			w.append(c)
			l += 1
			if c in rq.keys() :
				rq[c] -= 1
			while w :
				if w[0] in rq.keys() :
					print(rq[w[0]])
				if w[0] in rq.keys() :
					if rq[w[0]] >= 0 :
						break
					else :
						rq[w[0]] += 1
				w.popleft()
				l -= 1
			jump = False
			for i in rq.values() :
				if i > 0 :
					jump = True
			if ansl > l and jump == False :
				ansl = l
				ans = ''.join(w)
		return ans

13. 最大子数组和53-251215

tag: 动态规划 分治法 前缀和 做题目的时候不要被刷过的题目的思路限制住方向 也要做新的想法尝试

思路一：DP

以 index 为 结尾 的最大子序列和

1
2
3
4
5
6
7
class Solution :
	def maxSubArray(self, nums: List[int]) -> int :
		# 以index 为结尾的最大值
		dp = [0] * len(nums)
		for i,n in enumerate(nums) :
			dp[i] = max(dp[i-1]+nums[i],nums[i])
		return max(dp)

思路二：分治法（还没学1216）

官方题解说这个类似于 「线段树求解最长公共上升子序列问题」的pushup操作

思路三： 前缀和

参考 5盛水最多的容器中的动态规划方法，记录一个index左边最大和右边最小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# class Solution:
# def maxSubArray(self, nums: List[int]) -> int:
# # 一个index左边的最小值，一个index右边的最大值
# leftMin,rightMax = [10001]*(len(nums)+1),[-10001]*(len(nums)+1)
# sn = [0] * (len(nums)+1)
# for i in range(len(nums)) :
# sn[i+1] = nums[i]
# for i in range(1,len(sn)) :
# sn[i] += sn[i-1]
# leftMin[0] = sn[0]
# rightMax[-1] = sn[-1]
# for i in range(1,len(sn)) :
# leftMin[i] = min(leftMin[i-1],sn[i])
# rightMax[len(sn)-1-i] = max(rightMax[len(sn)-i],sn[len(sn)-1-i])
# ans = -99999999
# for i in range(len(sn)-1) :
# if ans < rightMax[i+1] - leftMin[i] :
# ans = rightMax[i+1] - leftMin[i]
# return ans

维护两个太慢了，因为这个主要的约束 是 最小值在最大值的右边，通过记录最小值，然后计算 s[n] 和 min 的差 来更新 结果：

1
2
3
4
5
6
7
8
class Solution :
	def maxSubArray(self, nums: List[int]) -> int :
		tsum, tmin, ans = 0, 0, -99999
		for n in nums :
			tsum += n
			ans = max(ans,tsum-tmin)
			tmin = min(tmin,tsum)
		return ans

14. 合并区间56-251216

tag: 排序 数组 单调栈

这个重点在于 排序的时候使用 lambda 表达式 lambda是个函数，lambda x: y 意思是输入 x 输出 y ，排序时候用sort(key =)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 20ms
class Solution:
	def merge(self, intervals: List[List[int]]) -> List[List[int]]:
		intervals.sort(key=lambda x: x[0])
		i = 0
		while True :
			if i+1 >= len(intervals) :
				break
			if intervals[i][1] >= intervals[i+1][0] :
				new_iv = [intervals[i][0],max(intervals[i][1],intervals[i+1][1])]
				intervals.remove(intervals[i+1])
				intervals[i] = new_iv
			else : i += 1
		return intervals

现在这种 每次的 remove 很慢 总体 20ms左右，还有一种方法是 维护一个 单调的栈，可以合并就合并后压栈否则就直接压. 这样结果就会快一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 5ms
class Solution:
	def push(self,res_inv,item) :
		if len(res_inv) == 0 :
			res_inv.append(item)
		top = res_inv[-1]
		if top[1] >= item[0] :
			res_inv.pop()
			item = [top[0],max(top[1],item[1])]
		res_inv.append(item)
		return res_inv
		  
	def merge(self, intervals: List[List[int]]) -> List[List[int]]:
		ans = []
		intervals.sort(key=lambda x:x[0])
		for iv in intervals :
			self.push(ans,iv)
		return ans

15. 轮转数组189-251216

1
2
3
4
5
6
7
class Solution:
	def rotate(self, nums: List[int], k: int) -> None:
		"""
		Do not return anything, modify nums in-place instead.
		"""
		k = k%len(nums)
		nums[:] = nums[len(nums)-k:] + nums[:len(nums)-k]

需要注意的两个是 k 可能超过 nums 的长度，需要通过%来计算 时间移动了多少步
然后 下一行中 如果 nums[:] 写成 nums ，那么nums就不会被修改 这个是python的一个特性 写成nums就是修改的这个局部变量 而不是修改了这个引用。

这个时间复杂度是

*最快的办法是反转数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        # [1,2,3,4,5,6,7]
        # 1. 反转数组 [7,6,5,4,3,2,1]
        # 2. 反转前k=3个元素 [5,6,7, 4,3,2,1]
        # 3. 反转剩余元素 [5,6,7, 1,2,3,4]
        n = len(nums)
        k = k % n
        nums.reverse()
        nums[:k] = nums[:k][::-1]
        nums[k:] = nums[k:][::-1]

16. 除自身以外数组的乘积238-251216

#前后缀

思路一：前后缀积

这个 也是用 前缀后缀积 但是不需要 维护两个list 因为我们知道最后的目的是 在 index位置 ans[i] = 所以不妨 先正向遍历拿到前面的积 再反向遍历，拿到后面的积。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        answer = [0] * length
        answer[0] = 1
        for i in range(1, length):
            answer[i] = nums[i - 1] * answer[i - 1]
        R = 1
        for i in reversed(range(length)):
            answer[i] = answer[i] * R 
            R *= nums[i]
        return answer

UES

这个解法考虑了0 同时用了reduce函数可以看一下

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        if 0 in nums:
            ret= [0]*len(nums)
            if nums.count(0)>=2:
                return ret
            ret[nums.index(0)]=reduce(mul,(i for i in nums if i!=0),)
            return ret
        p=reduce(mul,nums,)
        if p!=0:
            return [p//i for i in nums]

Trash

用 前缀积 后缀积 来在 时间复杂度解决这个问题 但是 空间复杂度是 

1
2
3
4
5
6
7
8
9
10
11
class Solution:
	def productExceptSelf(self, nums: List[int]) -> List[int]:
		fD, bD = nums[:], nums[:] # 定义前缀后缀积
		for i in range(1,len(nums)) :
			fD[i] *= fD[i-1]
			bD[len(nums)-i-1] *= bD[len(nums)-i]
		ans = [ bD[1] ]
		for i in range(1,len(nums)-1) :
			ans.append( fD[i-1] * bD[i+1] )
		ans.append(fD[-2])
		return ans

17. 缺失的第一个正数41-251216

思路一：原地哈希(节省内存)

参考这个：寻找文件副本

ans 最大的情况 就是 1,len(nums)都在 ，那么如果把 nums 中的 值 作为 index 那么肯定有 index 用不完的情况，第一个没用的就是 答案。
v[index] 是负数，那么这个index 可以直接拿来用，如果 v[i]>0 那么我们就需要把 这个 v[i] 也给记录下来。向链表一样顺着找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
	def firstMissingPositive(self, nums: List[int]) -> int:
		l = len(nums)
		for i in range(len(nums)) :
			target = nums[i]-1
			if target < 0 or target >= l :
				continue
			while nums[target] <= l and nums[target] > 0 :
				if nums[target] == target + 1 :
					break
				next_target = nums[target] - 1
				nums[target] = target + 1
				target = next_target
			nums[target] = target + 1
		for i in range(len(nums)) :
			if i+1 != nums[i] :
				return i+1
		else :
			return l+1

题解中的原地哈希，这个比上面的方法更好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	def firstMissingPositive(self, nums: List[int]) -> int:
		n = len(nums)
		for i in range(n):
			if nums[i] <= 0:
			nums[i] = n + 1
		for i in range(n):
			num = abs(nums[i])
			if num <= n:
				nums[num - 1] = -abs(nums[num - 1])
		for i in range(n):
			if nums[i] > 0:
				return i + 1
		return n + 1

Trash

题目中限制了空间复杂度是常数，如果不考虑空间，这个方法很快

1
2
3
4
5
6
7
8
9
class Solution:
	def firstMissingPositive(self, nums: List[int]) -> int:
		ans = len(nums)+1
		s = set(nums)
		for i in range(len(nums),0,-1) :
			if i in s :
				continue
			else : ans = min(ans,i)
		return ans

18. 矩阵置零73-251216

先处理行再处理列 这个是 时间复杂度。空间复杂度是 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	def setZeroes(self, matrix: List[List[int]]) -> None:
		"""
		Do not return anything, modify matrix in-place instead.
		"""
		c_index = set()
		for i,n in enumerate(matrix) :
			if 0 in n :
				index = [ -1 if n[index]!=0 else index for index in range(len(n)) ]
				[c_index.add(x) for x in index]
				matrix[i] = [0] * len(n)
		for i,n in enumerate(matrix) :
			for j in range(len(n)) :
				if j in c_index:
					matrix[i][j] = 0

19. 螺旋矩阵54-251216

遇到墙换方向

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
class Solution:
	def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
		ans = []
		i,j = 0,0
		down = len(matrix)
		right = len(matrix[0])
		total = down * right
		left = 1
		up = 1
		  
		di,dj = 0,1
		cnt = 0
		if right == 1 :
			ans = [ i[0] for i in matrix ]
			return ans
		  
		while True :
			print(i,j)
			ans.append(matrix[i][j])
			cnt += 1
			if cnt == total :
				break
				i,j = i+di,j+dj
			if j == right-1 and di == 0 and dj == 1 :
				di,dj = 1,0
				up = up + 1
			if i == down-1 and di == 1 and dj == 0 :
				di,dj = 0,-1
				right = right - 1
			if j == left - 1 and di == 0 and dj == -1 :
				di,dj = -1,0
				down = down - 1
			if i == up - 1 and di == -1 and dj == 0 :
				di,dj = 0,1
				left = left + 1
		return ans

20. 旋转图像48-251216

主要是下标处理 这几个矩阵相关的题目

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

21. 搜索二维矩阵 II240-251216

tag: 二分查找 分治法

思路一：Z字形查找

最简单的想法，时间复杂度是 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
	def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
		maxColIndex = len(matrix[0])-1
		for i,n in enumerate(matrix[0]) :
			if n >= target :
				maxColIndex = i-1
			if n == target :
				return True
		print(maxColIndex)
		for i in range(0,maxColIndex+1):
			for j in range(len(matrix)) :
				if matrix[j][i] == target :
					return True
				if matrix[j][i] > target :
					break
		return False

思路二：二分查找

1
2
3
4
5
6
7
8
9
class Solution:
	def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
		for row in matrix:
			if row[0] > target :
				break
			idx = bisect.bisect_left(row, target)
			if idx < len(row) and row[idx] == target:
				return True
		return False

防止不会 自己写一下 binary search

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 bs(self,nums,target):
		mid = (len(nums))//2
		print(mid,nums)
		if nums[0] > target :
			return None
		if nums[-1] < target :
			return None
		if nums[mid] > target :
			return self.bs(nums[0:mid],target)
		elif nums[mid] < target :
			return self.bs(nums[mid+1:],target)
		else : return mid
	
	def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
		for row in matrix:
			if row[0] > target :
				break
			idx = self.bs(row, target)
			if idx!=None :
				return True
		return False

思路三：贪心Z* 从左下角开始搜索！

操了 这个和前面的 Z搜索区别在于 从左下角开始搜索，这样的话就可以沿着 减增减 的序列搜索了 可以排除更多不可能区域. 我觉得这个想法非常好。
参考题解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
	def searchMatrix(self, matrix, target) -> bool :
		i, j = len(matrix)-1,0
		while i>=0 and j<=len(matrix[0])-1 :
			if matrix[i][j] == target :
				return True
			i,j = (i-1,j) if matrix[i][j] > target else (i,j+1)
			# if matrix[i][j] > target :
			# 	i -= 1
			# else :
			#  	j += 1
		return False

22. 相交链表160-251217

思路一：双指针*******************************

这个太帅了

1
2
3
4
5
6
7
class Solution:
	def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
		pA, pB = headA, headB
		while pA != pB :
			pA = pA.next if pA else headB
			pB = pB.next if pB else headA
		return pA

思路二：哈希

在这个过程中改变了list结构，这样的方法就是记录那些节点是访问过的
可以 用一个 set 记录哪些访问过，就不用这个了 但是用 Set 需要 o(m)的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
	def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
		startA = headA
		while headA :
			headA.val = -1 - headA.val
			headA = headA.next
		ans = None
		while headB :
			if headB.val < 0 and ans == None :
			# headB.val = -headB.val - 1
				ans = headB
				break
			headB = headB.next
		headA = startA
		while headA :
			headA.val = -headA.val - 1
			headA = headA.next
		return ans

思路三：对齐开始

先全部遍历一下，找到两个的长度，然后将较长的往前移动几个，这下 AB list 长度相同，接下来就直接一起同步 next 就可以 但是 实际时间复杂度是 O(m+2n-len(chonghe))

23. 反转链表206-251217

tag: 递归 迭代 非暴力迭代

思路一：递归

写递归算法时候的一定要理清思路，想好怎么递归调用的。

首先思路很明确，就是要reverse [A, …] 就是 reverse … ,然后把A 拼在后面。 有两点需要注意的，第一个是A 的next 需要变成None ，第二个就是 … 的tail 的next 需要变成 A 然后递归下去就好。

另外做这个题的时候需要 return list 的 head 所以要在开始先把 tail 给记录下来以return

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 递归
class Solution:
	# reverse head 后面的 包括head
	def r(self,head) :
	# print(head)
	# tail = head
	# while tail.next!=None :
	# tail = tail.next
	if head.next :
		self.r(head.next)
		head.next.next = head
		head.next = None
	# print(tail)
	  
	def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
		if head == None :
			return
		tail = head
		while tail.next!=None :
			tail = tail.next
		self.r(head)
		return tail

思路二：迭代*：

找到head开头的链的末端 往前指 前一个指空 （这是一个的垃圾方法），好好理理下面的那个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 不用看这个 复杂度不对
class Solution:
	def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
		tail = head
		if head is None :
			return
		while tail.next : tail = tail.next
		while head.next :
			# 找head的tail
			p = head
			pre = None
			while p.next :
				pre = p
				p = p.next
			else :
				p.next = pre
				pre.next = None
		return tail

这个时间复杂度很高 应该换一个，逐步对每个都处理：

1
2
3
4
5
6
7
8
9
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, p = None, head
        while p :
            n = p.next
            p.next = prev
            prev = p
            p = n
        return prev

后来又写了一个 和这个人的方法 一模一样了，是这样做到的：反转列表 对于每一个 node ，next置none 然后把原本的next 的 next 置为这个node 这样会得到一个很不好的 循环。但是换一个思路，从第二个开始来说 相当于我要做的是 将这个 next 置为 prev （而不是把下一个的next 置为自己，这个是区别所在），那么我需要保留prev即可 然后 这个ptr 每次移动一个。由于next会改，所以要在最开始先记住node.next

1
2
3
4
5
6
7
8
def reverseKOnce(self, head) :
    prev = None
    while head :
        n = head.next 
        head.next = prev
        prev = head
        head = n
    return prev

24. 回文链表234-251217

思路一： 栈判断

用栈判断 但是感觉写的不好 很多下标处理：

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
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # 先统计长度 然后用栈 判断
        stack = []
        p, l = head, 0
        while p : 
            p = p.next
            l += 1
        if l == 1 :
            return True
        mid = l//2
        isJumpMid = True if l%2 == 1 else False
        i, p = 1, head
        while p :
            if i <= mid :
                stack.append(p.val)
            else :
                if stack.pop() != p.val :
                    return False
            if i == mid and isJumpMid :
                i+=1
                p = p.next
            i+=1
            if p :
                p = p.next
        return True

思路二：复制到数组后双指针

这个方法也很快

1
2
3
4
5
6
7
8
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        current_node = head
        while current_node is not None:
            vals.append(current_node.val)
            current_node = current_node.next
        return vals == vals[::-1]

思路三：快慢指针

反转后面部分的 list 然后再 用两个指针比较 

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
class Solution:

    def isPalindrome(self, head: ListNode) -> bool:
        if head is None:
            return True

        # 找到前半部分链表的尾节点并反转后半部分链表
        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)

        # 判断是否回文
        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            first_position = first_position.next
            second_position = second_position.next

        # 还原链表并返回结果
        first_half_end.next = self.reverse_list(second_half_start)
        return result

    def end_of_first_half(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous

25. 环形链表141-251217

tag: 快慢指针 集合 重复

思路一：用集合判断是否访问过

这个方法空间复杂度是 ,时间复杂度也是 

1
2
3
4
5
6
7
8
9
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        visited = set()
        while head :
            if head in visited :
                return True
            visited.add(head)
            head = head.next
        return False

思路二： 快慢指针*

空间复杂度，时间复杂度看是否重合。下面捋一下思路：
对于一个有环的 list ，环外的 长度为 ，环长度 为 ，那么如果一个快指针 一次走两个，慢指针一次走一个，那么，慢的先走x，同时 相当于 快的进入环内后走了x，然后两者相遇的方程 ：
,对于这个 同余方程 一定有解，可以搜一下。

虽然快指针一次走两个，但是快慢之间的距离，其实是每次只减少一。所以一定会相遇

1
2
3
4
5
6
7
8
9
10
11
12
# 快慢指针
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        if not head :
            return False
        while slow and fast :
            slow = slow.next
            fast = fast.next.next if fast.next and fast.next.next else None
            if slow == fast and slow :
                return True
        return False

我的判断逻辑写得不好，可以学一下别人的：

1
2
3
4
5
6
7
8
9
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

26. 环形链表 II142-251217

思路一：集合

这个空间复杂度高 简单 不写了

思路二：快慢指针*

一个list 非环长 x 环长 L ，slow 走到环开头， fast 距离环开头 x 。此时 fast 还需要追 L-x ，由于每次 移动 fast 和 slow 的距离-=1 ，然后可以计算出 第一相遇位置，距离 环开头（倒退数） L-x （还需要L-x步，两者距离减为0），距离环结尾（前进数）x 。有了meetAt 这个点，再在 开头放置一个 ptr ，ptr 和 slow 一起同步移动，两者都移动 x 就都到了 开头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ptr, slow, fast, meetAt = head, head, head, None
        # l = 0
        while fast and fast.next :
            slow = slow.next
            # l += 1
            fast = fast.next.next
            if slow == fast :
                meetAt = slow 
                break
        if not meetAt :
            return
        while ptr != slow :
            ptr = ptr.next
            slow = slow.next
        return ptr

我觉得这两个题都很有意思

27. 合并两个有序链表21-251217

先找到小的开头，作为 p1 然后 比较插入即可

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
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 :
            return list2
        if not list2 :
            return list1
        if list1.val < list2.val :
            p1, p2 = list1, list2
        else :
            p1, p2 = list2, list1
        ans = p1
        while p2 :
            # print(f'1 1: {p1}')
            # print(f'1 2: {p2}')
            while p1.next and p1.next.val <= p2.val :
                # print(f'2 1: {p1}')
                # print(f'2 2: {p2}')
                p1 = p1.next
            # print(f'2-1: {p1}')
            # print(f'2-2: {p2}')
            if p1.next :
                # p2 插入到 p1 和 下一个之间
                # print(f'3 1: {p1}')
                # print(f'3 2: {p2}')
                p2n = p2.next
                p1n = p1.next
                p1.next = p2
                p2.next = p1n
                p2 = p2n
            else :
                p1.next = p2
                break
        return ans

学习一下别人写的，用了一个新的节点 作为开头，之后在这个开头后添加 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = cur = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        
        cur.next = list1 or list2
        return dummy.next

28. 两数相加2-251218

这个不难 重要的是细节处理

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
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        Csignal = 0
        ans, pl1, pl2 = l1, None, None
        while l1 and l2 :
            val = (l1.val + l2.val + Csignal)%10
            Csignal = (l1.val + l2.val + Csignal)//10
            l1.val = val
            pl1, pl2 = l1, l2
            l1, l2 = l1.next, l2.next
        if not l1 and not l2 and Csignal:
            pl1.next = ListNode(Csignal)
            return ans
        if not l1 :
            pl1.next = l2
            l1 = pl1.next
        while l1 :
            val = (l1.val + Csignal)%10
            Csignal = (l1.val + Csignal)//10
            l1.val = val
            if not l1.next and Csignal :
                l1.next = ListNode(Csignal)
                break
            l1 = l1.next
        return ans

29. 删除链表的倒数第 N 个结点19-251218

#快慢指针

遍历一次的方法 是 快慢指针 这个一开始没想到 ！！！！！！！！！！！！
相当于我手动留了两个距离为 n 的 ptr 后面的到了结尾 前面的到 倒数第n个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        slow = fast = head
        preSlow = None
        while n :
            fast = fast.next
            n -= 1
        while fast :
            fast = fast.next
            preSlow = slow
            slow = slow.next
        if not preSlow :
            return head.next
        preSlow.next = slow.next
        return head

30. 两两交换链表中的节点24-251218

虽然很简单，但是感觉写的不好，可以学一下别的人代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, ptr = None, head
        ans = head.next if head and head.next else head
        flag = 0
        while ptr :
            if flag < 1 :
                if prev :
                    prev.next = ptr.next if ptr.next else ptr
                prev = ptr
                ptr = ptr.next
                flag += 1
                continue
            flag = 0
            n = ptr.next 
            ptr.next = prev
            prev.next = n
            ptr = n
        return ans

官方的迭代方法：我发现 官方在做list 相关的题目时候，喜欢用一个dummyhead来作为答案。应该参考一下这个想法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummyHead = ListNode(0)
        dummyHead.next = head
        temp = dummyHead
        while temp.next and temp.next.next:
            node1 = temp.next
            node2 = temp.next.next
            temp.next = node2
            node1.next = node2.next
            node2.next = node1
            temp = node1
        return dummyHead.next

31. K 个一组翻转链表25-251218

上一题是这个题目 k=2 的特殊情况。用迭代的做法写，逐个找所有的k长子list 然后reverse

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
class Solution:
    # 反转k个
    def reverseKOnce(self, head) :
        tail = head
        prev = None
        while head :
            n = head.next 
            head.next = prev
            prev = head
            head = n
        return prev,tail

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        ans = prev_subtail = ListNode(0)
        if k == 1:
            return head
        n = None
        while True :
            start = head
            sublen = 1
            while head :
                head = head.next 
                sublen += 1
                if sublen == k and head :
                    n = head.next 
                    head.next = None
                    head = n
                    break
            if head or not n:
                subhead,subtail = self.reverseKOnce(start)
                prev_subtail.next = subhead
                prev_subtail = subtail
                if not n :
                    break
            else :
                prev_subtail.next = start
                break
        return ans.next

32. 随机链表的复制138-251218-重新写

这个方法复杂度应该是 先按照next 的方向复制list 然后找random 方法是 对于一个node 从两个list的头开始找，知道找origin的random 然后就把 新的random也置为这个

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
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        p = dummyHead = Node(0)
        phead = head
        while phead :
            p.next = Node(phead.val)
            phead = phead.next
            p = p.next
        # 到这里先复制list 到dummy 之后处理random
        p = dummyHead.next
        p_origin = head
        while p :
            if p_origin.random is None :
                p.random = None
                p = p.next 
                p_origin = p_origin.next
                if not p :
                    break

            q_origin = head
            q = dummyHead.next
            while q :
                if q_origin == p_origin.random :
                    p.random = q
                    break
                q = q.next 
                q_origin = q_origin.next
            p = p.next 
            p_origin = p_origin.next
        return dummyHead.next

        while dummyHead :
            print(f"{dummyHead.val}-{dummyHead.random.val if dummyHead and dummyHead.random else 'null'}",end=' ')
            dummyHead = dummyHead.next

别人的方法 还没看

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 copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if head is None:
            return None

        
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next
        
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        
        cur = head.next
        while cur.next:
            cur.next = cur.next.next
            cur = cur.next

        return head.next

必须要看看题解 然后好好做一下 这会儿太累了，之后看吧留个坑

33. 排序链表148-251219*-重新写

#并归排序

这个可以分为 自底向上并归 和 自顶向下并归（需要递归）。

自顶向下，用了递归 空间复杂度是 

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
class Solution:
    def merge(self, head1: Optional[ListNode], head2: Optional[ListNode]) :
        p = dummy = ListNode(-999) 
        while head1 and head2 :
            if head1.val < head2.val :
                p.next = head1
                head1 = head1.next
            else :
                p.next = head2
                head2 = head2.next
            p = p.next 
        if head1 :
            p.next = head1
        if head2 :
            p.next = head2
        return dummy.next

    # start包括  end不包括
    def sort(self,start ,end) :
        if not start :
            return start
        if start.next == end :
            start.next = None
            return start
        fast = slow = start
        while fast != end :
            slow = slow.next
            fast = fast.next
            if fast != end :
                fast = fast.next
        mid = slow
        return self.merge(self.sort(start,mid),self.sort(mid,end))


    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.sort(head,None)

自底向上：这个我写不动了 之后回来再写一次吧，重要的是 获取长度 然后处理

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
class Solution:
    def merge(self, head1: Optional[ListNode], head2: Optional[ListNode]) :
        p = dummy = ListNode(-999) 
        while head1 and head2 :
            if head1.val < head2.val :
                p.next = head1
                head1 = head1.next
            else :
                p.next = head2
                head2 = head2.next
            p = p.next 
        if head1 :
            p.next = head1
        if head2 :
            p.next = head2
        return dummy.next
    
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        length = 0
        node = head
        while node:
            length += 1
            node = node.next
        
        dummyHead = ListNode(0, head)
        subLength = 1
        while subLength < length:
            prev, curr = dummyHead, dummyHead.next
            while curr:
                head1 = curr
                for i in range(1, subLength):
                    if curr.next:
                        curr = curr.next
                    else:
                        break
                head2 = curr.next
                curr.next = None
                curr = head2
                for i in range(1, subLength):
                    if curr and curr.next:
                        curr = curr.next
                    else:
                        break
                
                succ = None
                if curr:
                    succ = curr.next
                    curr.next = None
                
                merged = self.merge(head1, head2)
                prev.next = merged
                while prev.next:
                    prev = prev.next
                curr = succ
            subLength <<= 1
        
        return dummyHead.next

34. 合并 K 个升序链表23-251219

最开始想的用单调栈 好像不可行，现在考虑用最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # val,node
        minHeapNode = []
        for i, n in enumerate(lists) :
            if n :
                minHeapNode.append((n.val,i,n))
        heapq.heapify(minHeapNode)
        p = dummy = ListNode(0)
        i = len(lists)
        while minHeapNode :
            # print(minHeapNode)
            top = heapq.heappop(minHeapNode)[2]
            p.next = top
            p = p.next
            if top.next :
                heapq.heappush(minHeapNode,(top.next.val,i,top.next))
            i += 1
        return dummy.next

35. LRU 缓存146-251219

题解思路：双链表+hash

用collections . orderDict

双链表用来维护出入队列，然后hash用来快速根据key找到value

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
class LRUCache:
    def __init__(self, capacity: int):
        self.used = 0
        self.capacity = capacity
        self.dummyStart = Node(-2,-2,None,None)
        self.dummyEnd = Node(-1,-1,None,None)
        self.dummyStart.next = self.dummyEnd
        self.dummyEnd.prev = self.dummyStart
        self.key2addr = {}

    def get(self, key: int) -> int:
        if not key in self.key2addr.keys() :
            return -1
        ptr = self.key2addr[key]
        ptr.prev.next = ptr.next
        ptr.next.prev = ptr.prev

        ptr.next = self.dummyEnd
        ptr.prev = self.dummyEnd.prev
        self.dummyEnd.prev.next = ptr
        self.dummyEnd.prev = ptr
        # self.print('get')
        return ptr.value
        

    def put(self, key: int, value: int) -> None:
        if key in self.key2addr.keys() :
            self.removeNode(self.key2addr[key])
            self.used -= 1
        if self.used == self.capacity :
            self.key2addr.pop(self.dummyStart.next.key)
            self.removeNode(self.dummyStart.next)
        else : self.used += 1
        new = Node(key=key,value=value,prev=self.dummyEnd.prev,next=self.dummyEnd)
        self.dummyEnd.prev.next = new
        self.dummyEnd.prev = new
        self.key2addr[key] = new
        # self.print('put')

    def removeNode(self,ptr) :
        ptr.prev.next = ptr.next
        ptr.next.prev = ptr.prev

    def print(self,str) :
        p = self.dummyStart
        print(f'{str}',end=' ')
        while p :
            print(f'({p.key}-{p.value})',end=' ')
            p = p.next
        print(f'used:{self.used}/{self.capacity}')

class Node :
    def __init__(self, key=0, value=0, next=None, prev=None) :
        self.value = value
        self.key = key
        self.next = next
        self.prev = prev

Trash

用队列，但是 get put 的复杂度是 O(capacity) remove
为什么要用双链？因为remove操作 需要 o© 去找到 value ，但是如果用Node，可以在字典中存入其地址。O(1) 就可以找到。

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
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dic = {}
        self.used = 0 # que 的 size
        self.que = []
    def get(self, key: int) -> int:
        if key not in self.dic.keys() :
            return -1
        value = self.dic[key]
        self.que.remove(key)
        self.que.append(key)
        # print(f'get {self.dic},{self.que}')
        return value
    def put(self, key: int, value: int) -> None:
        if key in self.dic.keys() :
            self.dic[key] = value
            self.que.remove(key)
            self.que.append(key)
            # print(f'put {self.dic},{self.que}')
            return 
        if self.used < self.capacity :
            self.que.append(key)
            self.dic[key] = value
            self.used += 1
            # print(f'put {self.dic},{self.que}')
            return
        delkey = self.que[0]
        self.que = self.que[1:]
        self.dic.pop(delkey)
        self.que.append(key)
        self.dic[key] = value
        # print(f'put {self.dic},{self.que}')

36. 二叉树的中序遍历94-251222

要知道中序遍历和先序遍历的while写法是不一样的，区别在于先append还是先 访问（cur=）

思路一：递归

这个写法比较简单

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def mid(self,root,ans):
        if root :
            self.mid(root.left,ans)
            ans.append(root.val)
            self.mid(root.right,ans)

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        self.mid(root,ans)
        return ans

思路二：迭代**

我觉得这个迭代写的很好，下来再看看

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = []
        ans = []
        while stack or root :
            while root :
                stack.append(root)
                root = root.left
            root = stack.pop()
            ans.append(root.val)
            root = root.right
        return ans

自己写的

1
2
3
4
5
6
7
8
9
stk = []
while stk or root :
    while root :
        stk.append(root)
        root = root.left
    root = stk.pop()
    print(root.val, end=' ')
    print(stk)
    root = root.right

37. 二叉树的最大深度104-251222

思路一：DFS

1
2
3
4
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root : return 0
        return max(self.maxDepth(root.left)+1,self.maxDepth(root.right)+1)

思路二：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        que = [root]
        next_que = []
        if not root :
            return 0
        while que :
            node = que[0]
            que.remove(node)
            if node.left :
                next_que.append(node.left)
            if node.right :
                next_que.append(node.right)
            if not que :
                ans += 1
                que = next_que
                next_que = []
        return ans

38. 翻转二叉树226-251222

思路一：BFS

对每一个节点 进行左右节点的互换，因为所有节点只访问一次。所以可行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        que = [root]
        next_que = []
        if not root :
            return root
        while que :
            node = que[0]
            que.remove(node)
            t = node.left
            node.left = node.right
            node.right = t
            if node.left :
                next_que.append(node.left)
            if node.right :
                next_que.append(node.right)
            if not que :
                que = next_que
                next_que = []
        return root

思路二：递归

递归的方法都比较简单

1
2
3
4
5
6
7
8
9
10
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root :
            return
        t = root.left
        root.left = root.right
        root.right = t
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

39. 对称二叉树101-251222

思路一：递归

递归的思路比较简单

1
2
3
4
5
6
7
8
9
10
class Solution:
    def digui(self,left,right):
        if not left and not right :
            return True
        if left and right and left.val == right.val :
            return True & self.digui(left.left,right.right) & self.digui(left.right,right.left)
        else : return False
        
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.digui(root,root)

思路二：迭代

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 isSymmetric(self, root) -> bool :
        left_ptr = right_ptr = root
        left_que = [root.left]
        right_que = [root.right]
        while left_que and right_que :
            left_ptr, right_ptr = left_que[0], right_que[0]
            left_que.remove(left_que[0])
            right_que.remove(right_que[0])
            if ( left_ptr and not right_ptr ) or ( not left_ptr and right_ptr ) :
                return False
            if left_ptr and right_ptr and left_ptr.val != right_ptr.val :
                return False
            if not left_ptr and not right_ptr :
                continue
            # append 的时候也要 对称
            left_que.append(left_ptr.left)
            left_que.append(left_ptr.right)
            right_que.append(right_ptr.right)
            right_que.append(right_ptr.left)
        return True

40. 二叉树的直径543-251222

思路一：递归

每一个节点的 计算出来的直径都是 左边的深度加右边的深度，只需要维护一个最大的就可以，但是这里把工具函数 以及self.ans写在solution函数内，这么做方便维护max

1
2
3
4
5
6
7
8
9
10
11
12
class Solution :
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.ans = -1 
        def DepthOfNode(n):
            if not n :
                return 0
            l = DepthOfNode(n.left)
            r = DepthOfNode(n.right)
            self.ans = max(self.ans, l+r)
            return max(l,r)+1
        DepthOfNode(root)
        return self.ans

思路二：迭代

找深度还是递归，但是只是用BFS来更新ans

Trash Ologn^2

超时了，记录每个叶子节点的path 然后计算路径

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
class Solution:
    def distance(self,path1,path2) -> int :
        # 非公共长度的和
        if path1 == '' or path2 == '' :
            return max(len(path1),len(path2))
        i=0
        while path1[i] == path2[i] :
            i += 1
        return len(path1) + len(path2) - i*2


    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        que = deque([root])
        root.path = ''
        mp = {}
        paths = []
        while que :
            ptr = que.popleft()
            if not ptr :
                continue
            if not ptr.left and not ptr.right :
                paths.append(ptr.path)
            que.append(ptr.left)
            que.append(ptr.right)
            if ptr.left : ptr.left.path = ptr.path + 'l'
            if ptr.right : ptr.right.path = ptr.path + 'r'
        ans = len(paths[-1])
        for i in range(len(paths)) :
            for j in range(i+1,len(paths)) :
                ans = max(ans,self.distance(paths[i],paths[j]))
        return ans

41. 二叉树的层序遍历102-251222

BFS即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root : return []
        que = deque([root])
        next_que = []
        ans = []
        while que :
            ans.append([])
            while que :
                cur = que.popleft()
                if not cur :
                    continue
                ans[-1].append(cur.val)
                if cur.left : next_que.append(cur.left)
                if cur.right : next_que.append(cur.right)
            que = deque(next_que)
            next_que = []
        return ans

42. 将有序数组转换为二叉搜索树108-251223

思路一：递归

一个sorted 数组转换成 树，root节点一定是mid，那么只需要向归并排序一样 依次将左右的的根节点找到即可

1
2
3
4
5
6
7
8
9
10
class Solution:
    def nums2tree(self, nums) -> TreeNode :
        if nums == [] : return None
        mid = len(nums)//2
        left_nums = nums[0:mid] if mid != 0 else []
        right_nums = nums[mid+1:] if mid<len(nums)-1 else []
        return TreeNode(val=nums[mid],left=self.nums2tree(left_nums),right=self.nums2tree(right_nums))

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.nums2tree(nums)

题解中有别的思路基于中序遍历

43. 验证二叉搜索树98-251223***

思路一：中序遍历判断数组是否有序

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

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.nums = []
        def front(root):
            if not root : return
            if root.left :
                front(root.left)
            self.nums.append(root.val)
            if root.right :
                front(root.right)
        front(root)
        p = -999999999999
        for n in self.nums :
            if p >= n : return False
            p = n
        return True

思路二：递归***

我觉得这个递归有点难，需要处理 右子树的最小值不能超过root 左子树的最大值不能超过 root，学一下官方的思路。helper用来判断 一个树 是不是 BST。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def helper(node, lower = float('-inf'), upper = float('inf')) -> bool:
            if not node:
                return True
            val = node.val
            if val <= lower or val >= upper:
                return False
            if not helper(node.right, val, upper):
                return False
            if not helper(node.left, lower, val):
                return False
            return True
        return helper(root)

下面是自己写的 上面是题解写的 题解写的递归思路 更更更更 好

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def isBST(node,lowwer=float('-inf'),upper=float('+inf')):
            if not node :
                return True
            # print(node.left.val if node.left else None,node.val,node.right.val if node.right else None,lowwer,upper)
            if ( node.left and node.left.val >= node.val ) or ( node.right and node.right.val <= node.val ):
                return False
            if (node.left and node.left.val <= lowwer) or (node.right and node.right.val >= upper) :
                return False
            return isBST(node.left,lowwer=lowwer,upper=node.val) and isBST(node.right,lowwer=node.val,upper=upper)
        return isBST(root)

44. 二叉搜索树中第 K 小的元素230-251223

思路一：中序遍历

将二叉查找树转换成数组 然后 查找一次即可 下面是递归写法

1
2
3
4
5
6
7
8
9
10
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.ans = []
        def mid_iter(root):
            if not root : return 
            if root.left : mid_iter(root.left)
            self.ans.append(root.val)
            if root.right: mid_iter(root.right)
        mid_iter(root)
        return self.ans[k-1]

下面是迭代的写法 注意每次while中的意思：遇到左叶子存在就优先处理左叶子，然后先把现在存起到栈中。知道遇到没有左叶子的，遍历这个节点，然后处理右叶子。这个流程构成了一个循环。

换一种理解，先往左走找到最小的 然后 找到大的进入 stk的pop 和 进入右叶子 我觉得第一个更好理解一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stk = []
        nums = []
        while stk or root :
            while root : 
                stk.append(root)
                root = root.left
            root = stk.pop()
            nums.append(root.val)
            k -= 1
            if k == 0 :
                return root.val
            root = root.right

思路二：记录node 的节点数（看题解）下面这两个还是学一下吧

思路三：转成AVL平衡二叉树（看题解）

45. 二叉树的右视图199-251223

思路一：BFS

通过BFS把每一行加入队列的最后一个记录下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# BFS 找到最后一个
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        que = deque([root])
        next_que = []
        ans = []
        if not root : return []
        while que :
            ans.append(que[-1].val)
            while que :
                cur = que.popleft()
                if not cur : continue
                if cur.left : next_que.append(cur.left)
                if cur.right: next_que.append(cur.right)
            que = deque(next_que)
            next_que = []
        return ans

思路二：DFS**** 之前都没写过DFS，DFS使用stk 把左右加进来

在深度优先搜索时 如果优先搜索 右侧节点，那么每层访问的第一个 节点 一定是最右侧的节点，那么我们可以记录一个深度。遇到第一个这个深度的节点，就记录下来。下面是题解的做法 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        rightmost_value_at_depth = dict() # 深度为索引，存放节点的值
        max_depth = -1

        stack = [(root, 0)]
        while stack:
            node, depth = stack.pop()

            if node is not None:
                # 维护二叉树的最大深度
                max_depth = max(max_depth, depth)

                # 如果不存在对应深度的节点我们才插入
                rightmost_value_at_depth.setdefault(depth, node.val)

                stack.append((node.left, depth + 1))
                stack.append((node.right, depth + 1))

        return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]

要知道中序遍历和先序遍历的while写法是不一样的，区别在于先append还是先 访问（cur=）

46. 二叉树展开为链表114-251223

Trash 用了新的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root : return 
        dummy = TreeNode(0,None,None)
        ptr = dummy
        stk = [root]
        while stk :
            cur = stk.pop()
            if not cur : continue
            ptr.right = TreeNode(cur.val,None,None)
            ptr = ptr.right
            # print(cur.val,end='')
            stk.append(cur.right)
            stk.append(cur.left)

        root.right = dummy.right.right
        root.left = None

思路一：存下来prev

因为cur已经被访问过了所以可以修改了，prev执指向现在cur 就可以修改其左右叶子值了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        stack = [root] if root else []
        prev = None
        while stack:
            cur = stack.pop()
            if prev:
                prev.left, prev.right = None, cur
            if cur.right: stack.append(cur.right)
            if cur.left: stack.append(cur.left)
            prev = cur

思路二：找到前驱节点***

这个题题解的方法也很多，之后仔细看一下。下面这个方法是常数空间复杂度的方法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def flatten(self, root: TreeNode) -> None:
        curr = root
        while curr:
            if curr.left:
                predecessor = nxt = curr.left
                while predecessor.right:
                    predecessor = predecessor.right
                predecessor.right = curr.right
                curr.left = None
                curr.right = nxt
            curr = curr.right

47. 从前序与中序遍历序列构造二叉树105-251223

思路一：递归（没看

终点在于根据 index i 找到 preorder的左右 但是这个递归还是很慢 也是 Trash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if preorder == [] : return None
        # for i,n in enumerate(inorder) :
        #     if n == preorder[0] :
        #         break
        i = inorder.index(preorder[0])
        left_inorder = inorder[0:i]
        right_inorder = inorder[i+1:]
        # 可以知道 i 左右的数量
        left_preorder = preorder[1:i+1]
        # for x in preorder :
        #     if x in left_inorder :
        #         left_preorder.append(x)
        right_preorder = preorder[i+1:]
        # for x in preorder :
        #     if x in right_inorder :
        #         right_preorder.append(x)
        # print(left_preorder,right_preorder)
        return TreeNode(preorder[0],self.buildTree(left_preorder,left_inorder),self.buildTree(right_preorder,right_inorder))

下面是我的改进 还不是最优的：重点在于通过v找i时候用hash 把复杂度降低为 

1
2
3
4
5
6
7
8
9
# # 递归 
class Solution:
    def buildTree_helper(self, preorder: List[int], inorder: List[int], abs_start=0) -> Optional[TreeNode]:
        if len(preorder) == 0 : return None
        i = self.mp[preorder[0]] - abs_start
        return TreeNode(preorder[0],self.buildTree_helper(preorder[1:i+1],inorder[0:i],abs_start=abs_start),self.buildTree_helper(preorder[i+1:],inorder[i+1:],abs_start=abs_start+i+1))
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        self.mp = { v:i for i,v in enumerate(inorder) }
        return self.buildTree_helper(preorder, inorder)

******下面是官方的递归方法，速度快了很多

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
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBuildTree(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            
            # 前序遍历中的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = index[preorder[preorder_root]]
            
            # 先把根节点建立出来
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归地构造左子树，并连接到根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
            return root
        
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0, n - 1, 0, n - 1)

思路二：迭代（没看

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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None

        root = TreeNode(preorder[0])
        stack = [root]
        inorderIndex = 0
        for i in range(1, len(preorder)):
            preorderVal = preorder[i]
            node = stack[-1]
            if node.val != inorder[inorderIndex]:
                node.left = TreeNode(preorderVal)
                stack.append(node.left)
            else:
                while stack and stack[-1].val == inorder[inorderIndex]:
                    node = stack.pop()
                    inorderIndex += 1
                node.right = TreeNode(preorderVal)
                stack.append(node.right)

        return root

Trash：递归拆分先序nums时候超时

答案对但是超时了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if preorder == [] : return None
        for i,n in enumerate(inorder) :
            if n == preorder[0] :
                break
        left_inorder = inorder[0:i]
        right_inorder = inorder[i+1:]
        left_preorder = []
        for x in preorder :
            if x in left_inorder :
                left_preorder.append(x)
        right_preorder = []
        for x in preorder :
            if x in right_inorder :
                right_preorder.append(x)
        # print(left_preorder,right_preorder)
        return TreeNode(preorder[0],self.buildTree(left_preorder,left_inorder),self.buildTree(right_preorder,right_inorder))

48. 路径总和 III437-251224

思路一：前缀和*

用递归深度搜索 去遍历所有节点，记录前缀和，然后用hash来找到对应的，如果找到就把他拿出。那么最大的问题是：例如根节点，hash中记录了左子树的所有需要的哈希值，然后对于右子树 如果查到，就会出现一条通过root的路径，解决办法就是：记录的 （需要找到的）prefix+sum 只在子树范围内生效。（我觉得也是这个题的难点）
hash中记录的是，prefix+sum（像两数之和一样，遇到val 就查 target-val在不在。但是这个是两数之差）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        if not root : return 0
        mp = defaultdict(int)
        mp[targetSum] = 1
        self.ans = 0

        def DFS(root,fatherPrefix):
            if not root : return
            root.prefixSum = fatherPrefix + root.val
            self.ans += mp[root.prefixSum]
            mp[root.prefixSum+targetSum]+=1
            DFS(root.left,root.prefixSum)
            DFS(root.right,root.prefixSum)
            ##########################################
            #这一句很重要 保证了 这个节点只在子树中记录在mp中
            mp[root.prefixSum+targetSum]-=1 ##########
        
        DFS(root,0)
        
        return self.ans

思路二：深度优先搜索-非最优

这个思路没啥用我觉得 时间复杂度是 上一个复杂度是 这个思路就是写一个helper 用于找到起点为root的所有和为sum 的path数量，然后（DFS）遍历所有的node 得到所有path

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # 定义一个helper函数求出 以 root 为起点 并且和为 Sum 的数量
        def startRootSum(root,Sum) :
            if not root : return 0
            return (1 if root.val == Sum else 0) + startRootSum(root.left,Sum-root.val) + startRootSum(root.right,Sum-root.val)
        # 遍历所有节点，找到以所有节点开头 path 和为 targetSum 的数量 这个递归就是一个 DFS
        if not root : return 0
        ans = 0
        ans += startRootSum(root,targetSum)
        ans += self.pathSum(root.left,targetSum)
        ans += self.pathSum(root.right,targetSum)
        return ans

Trash 迭代前缀和

先尝试了用迭代方法去写前缀和：跑不通。接下来尝试用递归去求

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
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        if not root : return 0
        self.mp = {targetSum:1}
        self.ans = 0
        def DFS(root):
            stk = [root]
            root.prefixSum = root.val
            while stk :
                cur = stk.pop()
                if cur == root.right or cur == root.left :
                    if root.val != 0:
                        self.mp = { targetSum:1 ,root.val+targetSum:1}
                    else :
                        self.mp = {targetSum:2}
                print(cur.val,cur.prefixSum)
                if cur.prefixSum in self.mp.keys():
                    self.ans += self.mp[cur.prefixSum]
                    print(cur.val)
                if  targetSum+cur.prefixSum in self.mp.keys() :
                    self.mp[targetSum+cur.prefixSum] += 1
                else :
                    self.mp[targetSum+cur.prefixSum] = 1

                if cur.right:
                    stk.append(cur.right)
                    cur.right.prefixSum = cur.prefixSum + cur.right.val
                if cur.left :
                    stk.append(cur.left)
                    cur.left.prefixSum = cur.prefixSum + cur.left.val
                print(self.mp,self.ans)
        DFS(root)
        print(self.ans)
        return self.ans

print位置换一下就是前中后序遍历，但是迭代的写法很不一样，谦虚需要while + stk 中序需要 while+que

1
2
3
4
5
def DFS(root):
    if not root : return
    DFS(root.left)
    print(root.val)
    DFS(root.right)

49. 二叉树的最近公共祖先236-251224

思路一：记录所有节点的father，然后用set查

1.先用DFS遍历树，然后记录每个节点的father 2.把p的所有father存在在个set 3.遍历q的father（从q开始）遇到 在 set:p.fathers 中的节点就返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def DFS(root):
            if not root : return
            if root.left : root.left.father  = root
            if root.right: root.right.father = root
            DFS(root.left)
            DFS(root.right)
        DFS(root)
        root.father = None
        pFathers = set()
        while p :
            pFathers.add(p)
            p=p.father
        while q :
            if q in pFathers :
                return q
            q = q.father

思路二：递归

写一个工具函数判断 这个root节点为根的树中包不包含 p，q ，那么最后结果一定是 ans 包含，ans的左右孩子都不包含，下面是自己的写法，但是感觉把问题写复杂了，之后可以学习一下题解的写法。

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
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def DFS(root,p,q) :
            if not root : return 
            root.p_in = False
            root.q_in = False
            if not root.left and not root.right :
                root.q_in = False
                root.p_in = False
            if root.val == p.val :
                root.p_in = True
                root.q_in = False
                # print(f'p-{root}')
            if root.val == q.val :
                root.p_in = False
                root.q_in = True
                # print(f'q-{root}')
            DFS(root.left,p,q)
            DFS(root.right,p,q)
            lpi = root.left.p_in if root.left else False
            rpi = root.right.p_in if root.right else False
            lqi = root.left.q_in if root.left else False
            rqi = root.right.q_in if root.right else False
            root.p_in = lpi or rpi or root.p_in
            root.q_in = lqi or rqi or root.q_in
            # print(f'val:{root.val},p_in:{root.p_in},q_in:{root.q_in}')
        DFS(root,p,q)
        while root.p_in and root.q_in :
            # print(root.val)
            if root.left and root.left.p_in and root.left.q_in :
                root = root.left
            elif root.right and root.right.p_in and root.right.q_in :
                root = root.right
            else : return root

题解写法没有py我没粘 这个是前面的写法 （* 这个想法好好啊 *）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 如果当前节点为p或者q 公共父节点是p或者q本身
        # 如果左右都找到了可能的父节点，返回公共节点
        # 左右都没找到，返回空节点
        if root in (None,p,q):
            # 3元组
            return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)

        if left and right:
            return root
        
        # 左和右 谁找到了就返回谁
        return left or right

50. 二叉树中的最大路径和124-251224

思路一：递归-从trash优化过来的

在trash中 每次求解 root 树的最大路径 都要再递归找各个节点的 路径，对这个做法优化：在一个递归中得到 从一个节点开始的最大值 ，这样不用每次找一个节点都要找。而是存在一个属性内

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    # root 树的最大path
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        if not root :
            return 0
        left_child_max = self.maxPathSum(root.left) if root.left else -1001
        right_child_max = self.maxPathSum(root.right) if root.right else -1001 
        start_l_max = root.left.startRootMax if root.left else 0
        start_r_max = root.right.startRootMax if root.right else 0
        child_max = max(left_child_max,right_child_max)
        root.startRootMax = root.val + max(0, start_l_max, start_r_max)
        # print(f'val-{root.val},sMax-{root.startRootMax},{left_child_max}-{right_child_max}-{root.val + start_l_max + start_r_max}')
        include_root = max(root.val, root.startRootMax, root.val + start_l_max + start_r_max)
        return max(include_root,child_max)

这是一个题解的方法，可以参考一下：很简洁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        res = -inf
        def findmax(root):
            if not root:
                return 0
            nonlocal res
            left = findmax(root.left)
            if left < 0:
                left = 0
            right = findmax(root.right)
            if right < 0:
                right = 0
            if left + right + root.val > res:
                res = left + right + root.val
            return max(left,right) + root.val
        findmax(root)
        return res

参考后来写的方法！！！！！！！这个写的可以

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.ans = -inf
        # 从root开始的最大path,但是在每个节点判断 root 连接两边的是不是更大
        def dfs(root):
            if not root : return 0
            left = max(dfs(root.left),0)
            right = max(dfs(root.right),0)
            # print(root.val,left,right,left+right+root.val)
            self.ans = max(self.ans,left+right+root.val)
            return root.val + max(left,right)
        dfs(root)
        return self.ans

Trash: 超时了

第一想法是这样的 但是有两层递归 太慢了

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    # root 树的最大path
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        # 以root为起点的 path 最大值
        def startRootMax(root) :
            if not root :
                return 0
            return root.val + max(0, startRootMax(root.left), startRootMax(root.right))
        if not root :
            return 0
        start_root = max(root.val, startRootMax(root), root.val + startRootMax(root.left)+startRootMax(root.right))
        return max(start_root,self.maxPathSum(root.left) if root.left else -1001,self.maxPathSum(root.right) if root.right else -1001)

51. 岛屿数量200-251224

思路一：DFS

深度搜索，处理越界。如果还是1则置为已经遍历过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i,j):
            if i<0 or i>=len(grid): return 0
            if j<0 or j>=len(grid[0]): return 0
            if grid[i][j] != '1' : return 0
            grid[i][j] = '2'
            dfs(i-1,j)
            dfs(i+1,j)
            dfs(i,j-1)
            dfs(i,j+1)
            return 1
        ans = 0
        for i in range(len(grid)) :
            for j in range(len(grid[0])) :
                ans += dfs(i,j)
        return ans

思路二：BFS 队列和栈 在入的时候就标记

发现一个问题：如果这么写的话会超时 因为同一个点多次入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        r = len(grid)
        c = len(grid[0])
        ans = 0
        for i in range(r) :
            for j in range(c) :
                if grid[i][j] == '1' :
                    ans += 1
                    que = deque([(i,j)])
                    while que :
                        row,col = que.popleft()
                        grid[row][col] = '2'
                        for x,y in [ (row-1,col), (row+1,col), (row,col-1), (row,col+1) ] :
                            if 0<=x<r and 0<=y<c and grid[x][y]=='1' :
                                que.append((x,y))
        return ans

应该这样写才是对的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        r = len(grid)
        c = len(grid[0])
        ans = 0
        for i in range(r) :
            for j in range(c) :
                if grid[i][j] == '1' :
                    ans += 1
                    grid[i][j] = '2'
                    que = deque([(i,j)])
                    while que :
                        row,col = que.popleft()
                        # grid[row][col] = '2'
                        for x,y in [ (row-1,col), (row+1,col), (row,col-1), (row,col+1) ] :
                            if 0<=x<r and 0<=y<c and grid[x][y]=='1' :
                                que.append((x,y))
                                grid[x][y] = '2'
        return ans

思路三：并查集

看题解吧，这一次没写这个

类似题目岛屿的周长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        r = len(grid)
        c = len(grid[0])
        self.ans = 0
        def dfs(i,j) :
            self.ans += 4
            grid[i][j] = 2
            for x,y in [ (i-1,j), (i+1,j), (i,j-1), (i,j+1) ]:
                if 0<=x<r and 0<=y<c and grid[x][y] >= 1 :
                    self.ans -= 1
                if 0<=x<r and 0<=y<c and grid[x][y] == 1 :   
                    dfs(x,y)
        for i in range(r) :
            for j in range(c) :
                if grid[i][j] == 1 :
                    dfs(i,j)            
        return self.ans

52. 腐烂的橘子994-251224

思路：多源广度优先搜索

把多个2加入到一个list里面 然后从这一个list开始BFS 而不是一个单一的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        r = len(grid)
        c = len(grid[0])
        def BFS(que: List):
            time = 0
            if not que : return 0
            que = deque(que)
            next_que = []
            while que :
                row,col = que.popleft()
                for x,y in [ (row+1,col), (row-1,col), (row,col+1), (row,col-1) ] :
                    if 0<=x<r and 0<=y<c and grid[x][y] == 1 :
                        next_que.append((x,y))
                        grid[x][y] = 2
                if not que :
                    time += 1
                    print(time, next_que)
                    que = deque(next_que)
                    next_que = []
            return time-1
        start = []
        for i in range(r) :
            for  j in range(c) :
                if grid[i][j] == 2 :
                    start.append((i,j))
        ans = BFS(start)
        for i in range(r) :
            for  j in range(c) :
                if grid[i][j] == 1 :
                    return -1
        return ans

Trash: 单源广度优先搜索

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 Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        r = len(grid)
        c = len(grid[0])
        mp = defaultdict(int)
        g = copy.deepcopy(grid)
        def BFS(i,j,grid) :
            time = 1
            que = deque([(i,j)])
            mp[(i,j)] = 0
            next_que = []
            while que :
                row,col = que.popleft()
                for x,y in [ (row-1,col), (row+1,col), (row,col-1), (row,col+1) ] :
                    if 0<=x<r and 0<=y<c and (grid[x][y]==1)  :
                        next_que.append((x,y))
                        grid[x][y] = 2
                        mp[(x,y)] = min(time,mp[(x,y)]) if mp[(x,y)] != 0 else time
                        # print(mp[(x,y)])
                if not que :
                    que = deque(next_que)
                    next_que = []
                    time += 1
            return time
        ans = 0
        flag = False
        for i in range(r) :
            for j in range(c) :
                if grid[i][j] == 2 :
                    g = copy.deepcopy(grid)
                    ans = max(BFS(i,j,g),ans)
                    # print(mp)
        
        for i in range(r) :
            for j in range(c) :
                if grid[i][j] == 1 and (i,j) not in mp.keys() :
                    return -1
        
        return max(mp.values()) if mp.values() else 0

53. 课程表207-251224**********两个方法

这个题目主要是要判断 依赖关系组成的单链表（hash）中有没有环，先看一下拓扑排序课程表 II

1
2
3
4
5
6
7
8
9
10
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        mp = {}
        for l in prerequisites :
            if l[0] in mp.keys() :
                mp[l[0]].append(l[1])
            else :
                mp[l[0]] = [l[1]]
        # 判断哈希表中有没有环

思路一：DFS

拓扑排序 省去了排序 只判断环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        status = [0] * numCourses
        mp = defaultdict(list)
        for i in prerequisites :
            mp[i[0]].append(i[1])
        def dfs(u: int):
            status[u] = 1
            for v in mp[u]:
                if status[v] == 0 :
                    if dfs(v) : return True
                elif status[v] == 1 :
                    # 有环
                    return True
            status[u] = 2
        for i in range(numCourses) :
            if dfs(i) : return False
        return True

思路二：BFS

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 canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        in_edges = [0] * numCourses
        # 维护哈希表
        mp = defaultdict(list)
        for i in prerequisites :
            mp[i[0]].append(i[1])
            in_edges[i[1]] += 1
        # 找到最先学的
        que = deque()
        for i in range(numCourses):
            if in_edges[i] == 0 :
                que.append(i)
        visited = 0
        while que :
            visited += 1
            cur = que.popleft()
            print(cur,end=' ')
            for v in mp[cur] :
                in_edges[v] -= 1
                if in_edges[v] == 0 :
                    que.append(v)
        return visited == numCourses

课程表II-DFS

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 findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 记录每个节点，维护每个节点的状态，0是还没搜索，1是正在搜索，2是搜索完了
        status = [0] * numCourses
        # 先获取依赖关系
        mp = defaultdict(list)
        for i in prerequisites :
            mp[i[0]].append(i[1])
        existCycle = False
        ans = []
        def dfs(u: int) :
            status[u] = 1
            for v in mp[u]:
                if status[v] == 0 :
                    if dfs(v) : return True
                elif status[v] == 1 :
                    # 说明遇到了环
                    return True
            status[u] = 2
            ans.append(u)
            return False
        
        for i in range(numCourses):
            if not existCycle and status[i] == 0 :
                if dfs(i) :
                    return []
                
        return ans if not existCycle else []

54. 实现 Trie (前缀树)208-251225

插入和查找 用 dict 就可以简单实现，所以关键点在于 startWith
如果用暴力的方法那么如下，这个方法的 startwith是不可接受的（1750ms），能不能用一个新的结构来做呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Trie:

    def __init__(self):
        self.list = []

    def insert(self, word: str) -> None:
        self.list.append(word)

    def search(self, word: str) -> bool:
        return word in self.list

    def startsWith(self, prefix: str) -> bool:
        lp = len(prefix)
        for v in self.list :
            p = v[0:min(lp,len(v))]
            if p == prefix :
                return True
        return False

稍微为字典优化一下就变成：75ms 还是挺慢的 正态mu是56

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Trie:

    def __init__(self):
        self.list = {}

    def insert(self, word: str) -> None:
        self.list[word] = True
        sub = ''
        for c in word :
            sub+=c
            if sub not in self.list.keys() :
                self.list[sub] = False

    def search(self, word: str) -> bool:
        if word not in self.list.keys() :
            return False
        return self.list[word]

    def startsWith(self, prefix: str) -> bool:
        return prefix in self.list.keys()

思路：字典树

字典套字典感觉太难理解了

不好的写法

递归insert字典树 感觉有点慢 5.24%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def c2i(char) -> int :
    return 0 if char=='#' else ord(char) -ord('a') + 1

class Trie:
    def __init__(self):
        self.next = [ None ] * 27
    def insert(self, word: str) -> None:
        if not word : return
        if word[-1] != '#' : word += '#'
        node = Trie() if not self.next[c2i(word[0])] else self.next[c2i(word[0])]
        node.insert(word[1:])
        self.next[c2i(word[0])] = node

    def search(self, word: str) -> bool:
        return self.startsWith(word+'#')

    def startsWith(self, prefix: str) -> bool:
        node = self
        for c in prefix :
            i = c2i(c)
            node = node.next[i]
            if not node : return False
        return True

好的写法之后再写一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Trie:
    def __init__(self):
        self.trie = {}
    
    def insert(self, word: str) -> None:
        node = self.trie
        for char in word:
			####### 下面这一行是重点 如果 char 在key中 就返回node[char] 
			####### 如果不在 就node[char]={}再返回
            node = node.setdefault(char, {})
        node['#'] = True  # 标记单词结束
    
    def search(self, word: str) -> bool:
        return self.startsWith(word+'#')

    def startsWith(self, prefix: str) -> bool:
        node = self.trie
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

55. 全排列46-251225

复杂度是

用递归做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def Digui(nums):
    ans = []
    if len(nums) == 1 :
        return [[nums[0]]]
    for i in range(len(nums)) :
        cp = nums[:]
        t = cp[0]
        cp[0] = cp[i]
        cp[i] = t
        sub_ans = Digui(cp[1:])
        for b in  sub_ans :
            a = [cp[0]] + b
            ans.append(a)
    return ans

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return Digui(nums)

题解的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]] :
        # index 尾巴 全排列
        def dfs(index):
            if index == len(nums):
                return res.append(nums[:])
            for i in range(index , len(nums)):
                nums[i],nums[index] = nums[index],nums[i]
                dfs(index+1)
                nums[index],nums[i] = nums[i],nums[index]
        res = []
        dfs(0)
        return res

56. 子集78-251229

递归，和上一个思路一样。但是这个是组合 把输出分成 1和 后面的 先求解 digui(后面的) 然后再在后面的解中每个和1 结合，加上 后面的解 就是 一个完成的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def Digui(nums) :
    print(nums)
    if len(nums)==1 :
        return [nums,[]]
    sub_ans = Digui(nums[1:])
    ans = sub_ans[:]
    # print(sub_ans)
    for s in sub_ans :
        a = [nums[0]] + s
        print(f'-- {a} {[nums[0]]} {s}')
        ans.append(a)
    # print(ans)
    return ans

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        return Digui(nums)

57. 电话号码的字母组合17-20251229

递归

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
mp = {
    2:['a','b','c'],
    3:['d','e','f'],
    4:['g','h','i'],
    5:['j','k','l'],
    6:['m','n','o'],
    7:['p','q','r','s'],
    8:['t','u','v'],
    9:['w','x','y','z'],
}

def c2i(char) :
    return ord(char)-ord('0')

def Digui(str):
    index,remain = c2i(str[0]),str[1:]
    wl = mp[index]
    if len(remain) == 0 :
        return wl
    sub_ans = Digui(remain)
    ans = []
    for sub in sub_ans :
        for c in wl :
            ans.append(c+sub)
    return ans

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        return Digui(digits)

58. 组合总和39-20251229* 跳过了 之后自己写一下

这个是最快的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(summ,startIndex):
            if summ == target:
                res.append(path[:])
                return
            for i in range(startIndex,n):
                if summ + candidates[i] > target:
                    break
                path.append(candidates[i])
                backtrack(summ+candidates[i],i)
                path.pop()


        res=[]
        path = []
        n = len(candidates)
        candidates.sort()
        summ,startIndex = 0,0
        backtrack(summ,startIndex)
        return res

59. 括号生成22-20251230

思路一：动态规划 递归 Catalan 结构

这个递归的思路可以看看 重点在于 把每个问题 拆分成 (a)b 找到 ab的子问题，ab可以为空。我觉得本质还是递归，不太懂跟动态规划有什么具体关系，下次刷到可以再想想。
另外关于拆分子问题这个，其实就是 n-1 对的 sub_ans 然后把这一对新的括号加在任意的位置

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    @lru_cache(None)
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return ['']
        ans = []
        for c in range(n):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(n-1-c):
                    ans.append('({}){}'.format(left, right))
        return ans

别的思路

递归得到所有的 组合，然后用一个函数遍历测试对不对，但是这个复杂度有指数项 不好。

60. 单词搜索79-20251230

无优化的回溯-DFS

这个方法的时间完全不能接受，找到开头，然后dfs所有的path

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
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        r = len(board)
        c = len(board[0])
        def dfs(i,j,target) :
            cur_char = board[i][j]
            board[i][j] = '#'
            if len(target) == 1 : 
                board[i][j] = cur_char
                return cur_char == target
            target_char, next_target_char = target[0], target[1]
            if cur_char != target_char : 
                board[i][j] = cur_char
                return False
            for t in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)] :
                u,v = t[0],t[1]
                if 0 <= u < r and 0 <= v < c and board[u][v] != '#' :
                    if dfs(u,v,target[1:]) : return True
            board[i][j] = cur_char
            return False

        for i in range(r) :
            for j in range(c) :
                if board[i][j] == word[0] and dfs(i,j,word) : return True
        return False

题解写的回溯：

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
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def check(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            
            visited.add((i, j))
            result = False
            for di, dj in directions:
                newi, newj = i + di, j + dj
                if 0 <= newi < len(board) and 0 <= newj < len(board[0]):
                    if (newi, newj) not in visited:
                        if check(newi, newj, k + 1):
                            result = True
                            break
            
            visited.remove((i, j))
            return result

        h, w = len(board), len(board[0])
        visited = set()
        for i in range(h):
            for j in range(w):
                if check(i, j, 0):
                    return True
        
        return False

优化方法

  1. 统计word 中各个字母的数量，如果board 中不符合 就直接 return False
  2. 找到 word[0] word[-1] 这两个字母哪个在 board 中出现的少，如果 word[-1] 出现的少，那么就把word reverse 这样可以减少入口的数量。
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
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i,j,target):
            if board[i][j] != target[0] : return False
            if len(target) == 1 : return True
            res = False
            t, board[i][j] = board[i][j], '#'
            for (u,v) in [(0, 1), (0, -1), (1, 0), (-1, 0)] :
                u,v = i+u, j+v
                if 0<=u<len(board) and 0<=v<len(board[0]):
                    if dfs(u,v,target[1:]) : 
                        res = True
                        break
            board[i][j] = t
            return res
        ws = set(word)
        mp = defaultdict(int)
        for x in range(len(board)) :
            for y in range(len(board[0])) :
                if board[x][y] in ws :
                    mp[board[x][y]] += 1
        ifReverse = mp[word[0]] > mp[word[-1]]
        for c in word :
            mp[c]-=1
            if mp[c]<0 : return False
        word = word[::-1] if ifReverse else word[:]
        for x in range(len(board)) :
            for y in range(len(board[0])) :
                if board[x][y] == word[0] and dfs(x,y,word) :
                    return True
        return False

再优化一次

延续上面的2思路，是不是找到一个位置，使该位置两边的搜索数量最少，就可以了？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i,j,target):
            if board[i][j] != target[0] : return False
            if len(target) == 1 : return True
            res = False
            t, board[i][j] = board[i][j], '#'
            for (u,v) in [(0, 1), (0, -1), (1, 0), (-1, 0)] :
                u,v = i+u, j+v
                if 0<=u<len(board) and 0<=v<len(board[0]):
                    if dfs(u,v,target[1:]) : 
                        res = True
                        break
            board[i][j] = t
            return res
        ws = set(word)
        mp = defaultdict(int)
        for x in range(len(board)) :
            for y in range(len(board[0])) :
                if board[x][y] in ws :
                    mp[board[x][y]] += 1
        min_=100
        start = 0
        for i in range(len(word)-1):
            sum_ = mp[word[i]] + mp[word[i+1]] 
            if sum_ < min_ :
                min_ = sum_
                start = i

        for c in word :
            mp[c]-=1
            if mp[c]<0 : return False
        
        target1 = word[0:start] if word[0:start] else ' '
        target2 = word[start:] if word[start:] else ' '
        target1 = target1[::-1]

        ans1 = set()
        ans2 = set()
        
        for x in range(len(board)) :
            for y in range(len(board[0])) :
                if board[x][y] == target1[0] and dfs(x,y,target1) :
                    ans1.add((x,y))
                if board[x][y] == target2[0] and dfs(x,y,target2) :
                    ans2.add((x,y))
        if start == 0 or start == len(word)-1 :
            if len(ans1) + len(ans2) != 0 :
                return True
        if not (len(ans1) and len(ans2)) : return False
        for i,j in ans2 :
            if any((i + dx, j + dy) in ans1 for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)] ) :
                return True
        return False

动态规划

题解下面的动态规划做法 有时间了学一下

61. 分割回文串131-20260104**

思路一：DP+回溯

思路都在注释里面

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 partition(self, s: str) -> List[List[str]]:
        l = len(s)
        # 用动态规划记录 i,j 是不是回文串 # dp 的本质就是 用已有状态（解） 递推 之后的状态（解）
        dp = [ [False] * (l) for i in range(l) ]
        for i in range(l) :
            for j in range(l):
                if i>=j : dp[i][j] = True
        for i in range(l,-1,-1) :
            for j in range(i+1,l) :
                dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
        # 到这里位置 记录了每个 i,j（包含） 是否是回文
        
        ret = list()
        ans = list()
        # 下面回溯搜索：从下标i开始，把 s[i:] 切成 若干回文子串，枚举所有可能的切法
        def dfs(i: int):
            if i == l:
                ret.append(ans[:])
                return
            for j in range(i, l):
                if dp[i][j]:
                    ans.append(s[i:j+1])
                    dfs(j + 1)
                    ans.pop()
        # 其实意思就是 从 0 开始 然后依次找 从合法的位置分割，对于每个合法的分割位置，再当做开头，再对后面的分割
        # 分割到 l 就把这一次分割的答案记下来
        dfs(0)
        return ret

62. N 皇后51-20260104******

思路一：按行搜索

好难啊😭，看了题解之后按照题解的思路做了一个。题解里面的想法是按行搜索，而不是按照位置搜索。是因为行本身可以作为一个索引，每次搜索一行的答案就行了。这样的话就没有那么难处理。（相比于按照按位置处理）

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
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        diag_add = set()
        diag_mns = set()
        # 找到 第row行 Q可以放在哪
        def tuple2board(tl):
            res = []
            for i,j in tl :
                t = ['.'] * n
                t[j] = 'Q'
                res.append(''.join(t))
            ans.append(res)

        def dfs(row):
            if row == n :
                tuple2board(tuple_ans)
                return
            for i in range(n) :
                if i in col or (row+i) in diag_add or (row-i) in diag_mns :
                    continue
                col.add(i)
                diag_add.add(row+i)
                diag_mns.add(row-i)
                tuple_ans.append((row,i))
                dfs(row+1)
                tuple_ans.pop()
                col.remove(i)
                diag_add.remove(row+i)
                diag_mns.remove(row-i)
        tuple_ans = []
        ans = []
        dfs(0)
        return ans

思路二：位运算******

pass 还没学暂时 脑子转不动了

63. 搜索插入位置35-20260105

Binary Search

第一次写的时候 def bs(num_list, target): 但是这样有个问题是index不好处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def bs(nl,tar):
            l = len(nl)
            if l == 0 : return 0
            mid = l//2
            if nl[mid] == tar : return mid
            if nl[mid] >  tar : 
                res = bs(nl[:mid],tar) 
                return res 
            if nl[mid] <  tar : 
                res = bs(nl[mid+1:],tar)
                # 我觉得这个比较关键, 找后部分的数组时候要把现在的 mid 给存下来
                # 还有一种方法是 直接用 left right 去找
                return  mid + res + 1
        
        return bs(nums,target)

用left rihgt 写的 bs 这个是 闭闭区间

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
            
        return left

64. 搜索二维矩阵74-20260105

二分搜索，思路挺简单的，先对行首二分搜索，然后对定位到的行继续二分搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 先找到在哪一行,up down 是个 闭开区间
        up, down = 0, len(matrix)
        while up < down :
            mid = (up+down)//2
            if matrix[mid][0] == target : return True
            if matrix[mid][0]  > target :
                down = mid
            if matrix[mid][0]  < target :
                up = mid + 1
        nums=matrix[up-1][:]
        up, down = 0, len(nums)
        while up < down :
            mid = (up+down)//2
            if nums[mid] == target : return True
            if nums[mid]  > target :
                down = mid
            if nums[mid]  < target :
                up = mid + 1
        return False

二分搜索的几种写法 注意循环不变量

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
# lower_bound 返回最小的满足 nums[i] >= target 的 i
# 如果数组为空，或者所有数都 < target，则返回 len(nums)
# 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]

# 闭区间写法
def lower_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    while left <= right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right+1] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right]
        else:
            right = mid - 1  # 范围缩小到 [left, mid-1]
    return left

# 左闭右开区间写法
def lower_bound2(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)  # 左闭右开区间 [left, right)
    while left < right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right)
        else:
            right = mid  # 范围缩小到 [left, mid)
    return left  # 或者 right

# 开区间写法
def lower_bound3(nums: List[int], target: int) -> int:
    left, right = -1, len(nums)  # 开区间 (left, right)
    while left + 1 < right:  # 区间不为空
        mid = (left + right) // 2
        # 循环不变量：
        # nums[left] < target
        # nums[right] >= target
        if nums[mid] < target:
            left = mid  # 范围缩小到 (mid, right)
        else:
            right = mid  # 范围缩小到 (left, mid)
    return right

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return lower_bound(nums, target)  # 选择其中一种写法即可

作者：灵茶山艾府
链接：https://leetcode.cn/problems/search-insert-position/solutions/2023391/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-nq23/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

65. 在排序数组中查找元素的第一个和最后一个位置34-20260105

先用二分找到这个数的位置，然后找下一个数的位置，得到结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 找到的是 左到右 第一个大于或等于 target 的 index
        def bs(nums_list,tar) :
            # print(nums_list,tar) 
            left, right = 0, len(nums_list)
            while left < right :
                mid = (left+right)//2
                if nums_list[mid] <  tar : left = mid + 1
                if nums_list[mid] >= tar : right = mid
            return left
        if not nums : return [ -1, -1 ]
        start = bs(nums,target)
        if start >= len(nums) or nums[start] != target : return [ -1, -1 ]
        return [ start, bs(nums,target+1)-1 ]

但是这样要两次 bs ，（而且我好像发现 二分搜索 闭闭区间 好像更好写）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def findlowerindex(nums: List[int], target: int)-> int:
    left = 0
    right = len(nums)-1
    
    while left<=right:
        mid = (left + right )//2
        if nums[mid]<target:
            left = mid+1
        else:
            right = mid-1
    return left



class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if findlowerindex(nums,target)==len(nums) or nums[findlowerindex(nums,target)] != target:
            return [-1,-1]
        return[findlowerindex(nums, target),findlowerindex(nums, target+1)-1]

66. 搜索旋转排序数组33-20260105

做一下 寻找旋转排序数组中的最小值这个可以，我觉得这个66题目的下标处理很麻烦，一定要注意

思路一：两次bs

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
class Solution:
    # 153. 寻找旋转排序数组中的最小值（返回的是下标）
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < nums[right]:
                right = mid
            else:
                left = mid + 1
        return right

    # 有序数组中找 target 的下标
    def lower_bound(self, nums: List[int], left: int, right: int, target: int) -> int:
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            # 循环不变量：
            # nums[right] >= target
            # nums[left] < target
            if nums[mid] >= target:
                right = mid  # 范围缩小到 (left, mid)
            else:
                left = mid  # 范围缩小到 (mid, right)
        return right if nums[right] == target else -1

    def search(self, nums: List[int], target: int) -> int:
        i = self.findMin(nums)
        if target > nums[-1]:  # target 在第一段
            return self.lower_bound(nums, -1, i, target)  # 开区间 (-1, i)
        # target 在第二段
        return self.lower_bound(nums, i - 1, len(nums), target)  # 开区间 (i-1, n)

思路二：一次bs 这个我还没看懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) // 2
            x = nums[mid]
            if x >= nums[0] and (target > x or target < nums[0]):
                l = mid + 1
            elif x < target < nums[0]:
                l = mid + 1
            else:
                r = mid
        return -1 if nums[r] != target else r

67. 寻找旋转排序数组中的最小值153-20260105

我觉得难点在下标处理

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums)-1
        while left < right :
            mid = (left+right)//2
            if nums[mid] < nums[right] :
                right = mid
            else : left = mid + 1 
        # print(left,right)
        return nums[left]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findMin(self,nums):
        left, right = 0, len(nums)-1
        while left < right :
            mid = (left+right)//2
            if nums[mid] <= nums[right] :
                right = mid
            else : 
                left = mid + 1
            print(left,right)
        return nums[left]

68. 寻找两个正序数组的中位数4-20260105********

这个题目挺重要的 看一下官方题解吧

思路一：按大小依次数 硬找中位数 这个方法不太好

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
class Solution:
    # 双指针 移动 len/2 次 找到
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        l1, l2 = len(nums1), len(nums2)
        if l1 == 1 and l2 == 1 : return (nums1[0] + nums2[0]) /2
        nums1.append(9999)
        nums2.append(9999)
        # mid 在 第几个
        midl = (l1+l2-1)//2 + 1
        midr = (l1+l2)//2 + 1
        count, p1, p2 = 0, -1, -1
        # print(l1,l2,midl,midr)
        ans = 0
        while True :
            if nums1[p1+1] < nums2[p2+1] :
                p1 += 1
                t = nums1[p1]
            else :
                p2 += 1
                t = nums2[p2]
            count += 1
            # print(count,t)
            if count == midl :
                ans += t
            if count == midr :
                ans += t
                break
        return ans/2

思路二：双指针 分组 找到两组

一个 题解 写的挺好的 可以看一下： 这个方法的关键想法在于怎么把两个数组分成两组。我觉得写的特别好。从一个的头和另一个的尾巴开始遍历。找到符合条件的。只到分组成功，一定要再看一下这个题解。这俩时间复杂度都是 m+n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findMedianSortedArrays(self, a: List[int], b: List[int]) -> float:
        if len(a) > len(b):
            a, b = b, a  # 保证下面的 i 可以从 0 开始枚举

        m, n = len(a), len(b)
        a = [-inf] + a + [inf]
        b = [-inf] + b + [inf]

        # 枚举 nums1 有 i 个数在第一组
        # 那么 nums2 有 j = (m + n + 1) // 2 - i 个数在第一组
        i, j = 0, (m + n + 1) // 2
        while True:
            if a[i] <= b[j + 1] and a[i + 1] > b[j]:  # 写 >= 也可以
                max1 = max(a[i], b[j])  # 第一组的最大值
                min2 = min(a[i + 1], b[j + 1])  # 第二组的最小值
                return max1 if (m + n) % 2 else (max1 + min2) / 2
            i += 1  # 继续枚举
            j -= 1

思路三：二分查找*

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
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKthElement(k):
            """
            - 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
            - 这里的 "/" 表示整除
            - nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
            - nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
            - 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
            - 这样 pivot 本身最大也只能是第 k-1 小的元素
            - 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
            - 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
            - 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
            """
            
            index1, index2 = 0, 0
            while True:
                # 特殊情况
                if index1 == m:
                    return nums2[index2 + k - 1]
                if index2 == n:
                    return nums1[index1 + k - 1]
                if k == 1:
                    return min(nums1[index1], nums2[index2])

                # 正常情况
                newIndex1 = min(index1 + k // 2 - 1, m - 1)
                newIndex2 = min(index2 + k // 2 - 1, n - 1)
                pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
                if pivot1 <= pivot2:
                    k -= newIndex1 - index1 + 1
                    index1 = newIndex1 + 1
                else:
                    k -= newIndex2 - index2 + 1
                    index2 = newIndex2 + 1
        
        m, n = len(nums1), len(nums2)
        totalLength = m + n
        if totalLength % 2 == 1:
            return getKthElement((totalLength + 1) // 2)
        else:
            return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2


作者：力扣官方题解
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/258842/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路四：二分发划分数组*

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
class Solution:
    def findMedianSortedArrays(self, a: List[int], b: List[int]) -> float:
        if len(a) > len(b):
            a, b = b, a

        m, n = len(a), len(b)
        # 循环不变量：a[left] <= b[j+1]
        # 循环不变量：a[right] > b[j+1]
        left, right = -1, m
        while left + 1 < right:  # 开区间 (left, right) 不为空
            i = (left + right) // 2
            j = (m + n - 3) // 2 - i
            if a[i] <= b[j + 1]:
                left = i  # 缩小二分区间为 (i, right)
            else:
                right = i  # 缩小二分区间为 (left, i)

        # 此时 left 等于 right-1
        # a[left] <= b[j+1] 且 a[right] > b[j'+1] = b[j]，所以答案是 i=left
        i = left
        j = (m + n - 3) // 2 - i
        ai = a[i] if i >= 0 else -inf
        bj = b[j] if j >= 0 else -inf
        ai1 = a[i + 1] if i + 1 < m else inf
        bj1 = b[j + 1] if j + 1 < n else inf
        max1 = max(ai, bj)
        min2 = min(ai1, bj1)
        return max1 if (m + n) % 2 else (max1 + min2) / 2

作者：灵茶山艾府
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/2950686/tu-jie-xun-xu-jian-jin-cong-shuang-zhi-z-p2gd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

69. 有效的括号20-20260105

用栈即可 比较简单这个

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isValid(self, s: str) -> bool:
        def isPair(c1,c2):
            if c1 == '(' : return c2==')'
            if c1 == '{' : return c2=='}'
            if c1 == '[' : return c2==']'
        stk = ['#']
        for c in s :
            if isPair(stk[-1],c) :
                print(c)
                stk.pop()
            else : stk.append(c)
        return len(stk) == 1

尝试优化 但是好像没效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isValid(self, s: str) -> bool:
        def isPair(c1,c2):
            if c1 == '(' : return c2==')'
            if c1 == '[' : return c2==']'
            if c1 == '{' : return c2=='}'
        def isError(c1,c2):
            if c1 == '(' : return c2==']' or c2=='}'
            if c1 == '[' : return c2==')' or c2=='}'
            if c1 == '{' : return c2==']' or c2==')'
        stk = ['#']
        if len(s)%2 == 1 : return False # 这个 mod2 不要忘掉
        for c in s :
            if isError(stk[-1],c) : return False
            if isPair(stk[-1],c) :
                print(c)
                stk.pop()
            else : stk.append(c)
        return len(stk) == 1

70. 最小栈155-20260105

思路：单调栈

用单调栈试试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MinStack:

    def __init__(self):
        self.stk = []
        self.min_stk = [+inf] # monotonic stack

    def push(self, val: int) -> None:
        self.stk.append(val)
        if val <= self.min_stk[-1] : self.min_stk.append(val)

    def pop(self) -> None:
        v = self.stk.pop()
        if v == self.min_stk[-1] : self.min_stk.pop()

    def top(self) -> int:
        return self.stk[-1]

    def getMin(self) -> int:
        return self.min_stk[-1]

题解写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MinStack:
    def __init__(self):
        # 这里的 0 写成任意数都可以，反正用不到
        self.st = [(0, inf)]  # 栈底哨兵

    def push(self, val: int) -> None:
        self.st.append((val, min(self.st[-1][1], val)))

    def pop(self) -> None:
        self.st.pop()

    def top(self) -> int:
        return self.st[-1][0]

    def getMin(self) -> int:
        return self.st[-1][1]

作者：灵茶山艾府
链接：https://leetcode.cn/problems/min-stack/solutions/2974438/ben-zhi-shi-wei-hu-qian-zhui-zui-xiao-zh-x0g8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思考：最小堆

维护一个栈记录数据，以及一个小顶堆，维护最小值。查看的速度是 O1 ，插入删除的速度是 ：
这个方法比上面的慢

71. 字符串解码394-20260105没写出来********

这个题我没写出来

思路一：辅助栈法

遇到 [ 时候 ：记录 重复次数，处理到当前之前的字符结果，并把这个临时结果 res 置为 空
遇到 ] 时候 ：弹栈 此时 两个括号内的内容 在 res 中，然后括号前的内容在栈顶，拼接即可 得到新的 res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, multi = [], "", 0
        for c in s:
            if c == '[':
                stack.append([multi, res])
                res, multi = "", 0
            elif c == ']':
                cur_multi, last_res = stack.pop()
                res = last_res + cur_multi * res
            elif '0' <= c <= '9':
                multi = multi * 10 + int(c)            
            else:
                res += c
        return res

思路二：递归

递归处理括号内的字符串，遇到括号就dfs 传入的 位置 i 标记了 这个括号内字符串的开始，感觉和上面的本质上没有区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def decodeString(self, s: str) -> str:
        def dfs(s, i):
            res, multi = "", 0
            while i < len(s):
                if '0' <= s[i] <= '9':
                    multi = multi * 10 + int(s[i])
                elif s[i] == '[':
                    i, tmp = dfs(s, i + 1)
                    res += multi * tmp
                    multi = 0
                elif s[i] == ']':
                    return i, res
                else:
                    res += s[i]
                i += 1
            return res
        return dfs(s,0)

72. 每日温度739-20260105

思路一：单调栈

这个题目 和 单调递减栈 接雨水那个好像啊 ，先试试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    # 用这个例子想一下
    # 4 5 6 2 0 3 7 4
    # 1 1 4 2 1 1 0 0
    def dailyTemperatures(self, t: List[int]) -> List[int]:
        # 单调递减栈,记录index，被弹走时计算 index差值 最后留在stk中的就是 0 用 0 初始化
        stk = [0]
        ans = [0] * len(t)
        for i in range(1,len(t)) :
            while stk and t[i] > t[stk[-1]] :
                index = stk.pop()
                ans[index] = i - index
            stk.append(i)
        return ans

思路二：别的写的另一种方法 暂时没仔细看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        hottest = 0
        answer = [0] * n
        
        for curr_day in range(n - 1, -1, -1):
            current_temp = temperatures[curr_day]
            if current_temp >= hottest:
                hottest = current_temp
                continue
                   # [73,74,75,71,69,72,76,73]    
            days = 1
            while temperatures[curr_day + days] <= current_temp:
                # Use information from answer to search for the next warmer day
                days += answer[curr_day + days]
            answer[curr_day] = days

        return answer

73. 柱状图中最大的矩形84-20260106**

思路一：单调栈

关键在于 对每个高度遍历的想法 我觉得，之后的就比较简单了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 单调栈 对每根柱子h找到 第一个 小于h 的 前一个就是边界
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 类似温度的方法 记录 下一个小于他的位置
        def nextLess(nums):
            stk = []
            res = [ 0 ] * len(nums)
            for i in range(len(nums)):
                while stk and nums[stk[-1]] > nums[i] :
                    top = stk.pop()
                    res[top] = i-top
                stk.append(i)
            return res
        ans = 0
        right = nextLess(heights)
        left = nextLess(heights[::-1])[::-1]
        for i in range(len(heights)) :
            r = i+right[i]-1 if right[i] != 0 else len(heights)-1
            l = i-left[i]+1 if left[i] != 0 else 0
            ans = max( (r-l+1)*heights[i] , ans )
        return ans

下面这个代码是 找 每个元素 左边 第一个小于他的，维护 单调递增栈 出站不更新，入栈之前更新。 上面的写法是找右边第一个小/大于他的，是在 pop 时候更新。

1
2
3
4
5
6
7
for i,n in enumerate(heights) :
    top = 0
    while stk and heights[stk[-1]] > n :
        top = stk.pop()
    res[i] = i - stk[-1] if stk else 0
    stk.append(i)
print(res)

但是这个算法的复杂度虽然是 但是 速度还是比较慢 遍历了三次数组 ，下面用一次遍历解决问题

思路二：单调栈+优化 （最优

既然入栈确定左边界 出栈确定右边界 能不能一次确定h的两个边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
        # 对一个 H
        #   找到 右边 第一个比他小的 （pop后更新）      单调递增栈
        #   找到 左边 第一个比他小的  (append前更新)   单调递增栈
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 维护单调递增栈 保证每个元素都能出入栈
        heights = [0]+heights+[0]
        stk = []
        left, right = [0]*len(heights),[0]*len(heights)
        for i,n in enumerate(heights) :
            while stk and n <= heights[stk[-1]] :
                top = stk.pop()
                right[top] = i
            left[i] = stk[-1] if stk else 0
            stk.append(i)
        return max((right[i]-left[i]-1)*heights[i] for i in range(len(heights)))

这个优化 还是要遍历两次，遍历一次的是：（*********这个没自己写过）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # heights前面补上零，原因是单个柱子也可以拿出来计算
        # 同时在末尾也加上零，否则无法触发剩余在栈中元素的计算
        heights.insert(0, 0)
        heights.append(0)
        stack = [0]
        res = 0
        for i in range(1, len(heights)):
            h = heights[i]
            if stack and h == heights[stack[-1]]:
                stack.pop()
            else:
                while stack and h < heights[stack[-1]]:
                    mid = stack.pop()
                    l, r = stack[-1], i
                    res = max(res, heights[mid] * (r - l - 1))
            stack.append(i)
        return res

超时

  1. 遍历index
1
2
3
4
5
6
7
8
9
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ans = 0
        l = len(heights)
        for i in range(l):
            for j in range(i,l):
                S = min(heights[i:j+1])*(j-i+1)
                ans = max(ans,S)
        return ans
  1. 遍历高度：遍历高度 h 为什么能找到最优解？是因为这种方法找到了 最小值为 h，也就是高度为 h 能组成的最大矩形。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 遍历高
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ans = 0
        l = len(heights)
        for i in range(l):
            h = heights[i]
            left, right = i, i
            while left > 0 and heights[left-1] >= h :
                left -= 1
            while right < l-1 and heights[right+1] >= h :
                right += 1
            S = h*(right-left+1)
            print(left,right,h,S)
            ans = max(S,ans)
        return ans

74. 数组中的第K个最大元素215-20260109

这个题解写的很好 这个题的思路就是用快速排序 的思想，把一个数放入正确的位置，如果放进去的位置刚好是k 那就 return。难得地方在于快速排序怎么写。

这个思路最简单的实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_select(nums,k):
            pivot = random.choice(nums)
            le, gt, eq = [],[],[]
            for n in nums :
                if n < pivot : le.append(n)
                elif n > pivot : gt.append(n)
                elif n == pivot : eq.append(n)
            if len(gt) >= k : 
                return quick_select(gt,k)
            if len(gt+eq) >= k :
                return pivot
            return quick_select(le,k-len(gt+eq))
        return quick_select(nums,k)

这个会超时，因为这个每次选择的pivot都是 第一个 如果数组有序的话， 会导致 时间复杂度到 ，那么怎么改呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 闭闭
        def quick_select(i,j):
            l,r = i,j
            pivot = nums[i]
            while i < j :
                while i < j and pivot >= nums[j] :
                    j -= 1
                nums[i] = nums[j]
                while i < j and nums[i] >= pivot :
                    i += 1 
                nums[j] = nums[i]
            nums[i] = pivot
            # print(l,r,nums,i,j)
            if i+1 == k : return pivot
            if i+1 < k : return quick_select(i+1,r)
            if i+1 > k : return quick_select(l,i-1)

        return quick_select(0,len(nums)-1)

这样还是超时 超时的关键在于 while 中的两个 大于等于号，之后想办法优化一下。
另外 内层第一个while后的交换 其实可以写到后面 一起交换。但是交换后要移动一下ij ，通过这种方式可能可以把 等号去掉

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 findKthLargest(self, nums: List[int], k: int) -> int:
        # 闭闭
        def quick_select(i,j):
            l,r = i,j
            # pivot_index = random.randint(i,j)
            # nums[i], nums[pivot_index] = nums[pivot_index], nums[i]
            pivot = nums[i]
            while i < j :
                while i < j and pivot >= nums[j] :
                    j -= 1
                nums[i] = nums[j]
                while i < j and nums[i] >= pivot :
                    i += 1 
                nums[j] = nums[i]
            nums[i] = pivot
            # print(l,r,nums,i,j)
            if i+1 == k : return pivot
            if i+1 < k : return quick_select(i+1,r)
            if i+1 > k : return quick_select(l,i-1)

        return quick_select(0,len(nums)-1)

看一下别人的：

邪修： 桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        bound = int(1e4)
        max_size = 2 * bound + 1
        print(max_size)
        num_cnt = [0] * max_size
        for num in nums:
            num_cnt[num + bound] += 1
        for i in range(max_size-1, -1, -1):
            if k <= num_cnt[i]:
                return i - bound
            else:
                k -= num_cnt[i]

快速排序笔记

首先 需要明确的是 快速排序的本质是 找到一个数组中 一个基准数的位置。这个基准数 一般取 第一个位置 。然后各放两个指针，左边的指向基准数，右边的指向末尾。算法流程就是，逐个向前检查后面的元素是不是比 这个 pivot 大，大就继续检查 直到 右指针 的数 小于 pivot 那么就和 pivot 交换位置。现在pivot 在 右边，就一次检查左边的。交换位置。 下面例子是降序

  • 交换的写法
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
        # 闭闭
        def quick_select(i,j):
            pivot = nums[i]
            print(nums,pivot)
            while i < j :
                while i < j and nums[i] >= nums[j] :
                    j -= 1
                    print(i,j)
                nums[j], nums[i] = nums[i], nums[j]
                print(nums)
                while i < j and nums[i] >= nums[j] :
                    i += 1 
                    print(i,j)
                nums[j], nums[i] = nums[i], nums[j]
                print(nums)
            print(nums,i,j,pivot)
            nums[i] = pivot
# 因为要交换 下面的写法更好
        def quick_select(i,j):
            pivot = nums[i]
            print(nums,pivot)
            while i < j :
                while i < j and pivot >= nums[j] :
                    j -= 1
                    print(i,j)
                nums[j], nums[i] = nums[i], nums[j]
                print(nums)
                while i < j and nums[i] >= pivot :
                    i += 1 
                    print(i,j)
                nums[j], nums[i] = nums[i], nums[j]
                print(nums)
            print(nums,i,j,pivot)
            nums[i] = pivot
  • 不交换的写法，上面的 流程中 找到 j 比 pivot大，那么只需要把 说明这个 j 应该在前面。（而不是这个j 应该变小，因为我们还不知道i对不对）所以就把i变成j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 闭闭
def quick_select(i,j):
    pivot = nums[i]
    print(nums,pivot,i,j)
    while i < j :
        while i < j and pivot >= nums[j] :
            j -= 1
            print(i,j)
        nums[i] = nums[j]
        print(nums)
        while i < j and nums[i] >= pivot :
            i += 1 
            print(i,j)
        nums[j] = nums[i]
        print(nums)
    nums[i] = pivot
    print(nums,i,j,pivot)

75. 前 K 个高频元素347-20260110

思路一：优先队列

简单的想法 统计格式 然后优先队列

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        KK = k
        cnt = defaultdict(int)
        for n in nums :
            cnt[n] += 1
        p = []
        for k,v in cnt.items() :   
            p.append((k,v))
        p = sorted(p,key=lambda x: x[1],reverse=True)
        return [ p[i][0] for i in range(KK) ]

思路二：堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from typing import List
from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)
        heap = []  # (count, num)

        for num, c in freq.items():
            if len(heap) < k:
                heapq.heappush(heap, (c, num))
            else:
                if c > heap[0][0]:
                    heapq.heapreplace(heap, (c, num))

        return [num for c, num in heap]

76. 数据流的中位数295-20260110

思路一：用堆维护中位数

维护一个 大堆 一个 小堆 两边数量均衡 且满足 大堆顶 小于 小堆顶 那么中位数就很好找了。那么怎么维护这样一个结构呢？
不妨先想 怎么维护两个 堆顶 元素的大小。 不妨这样想： 每次都往大堆（升序数组左半部分）中加 然后 把堆顶 冒到 小顶堆（升序数组后半部分），这样 小顶恒大于大顶。
但是这样有个问题，每次这样的话会导致，大顶为空。那么就加一个判断：如果小顶的元素数量超过了大顶，那么久：小顶吐出来一个给大顶，因为是小顶吐出来的，依然满足这个顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MedianFinder:
    def __init__(self):
        # 前半个的最大 和 后半个的最小
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        # 每次都往 max 中 添加 然后 平衡两边的 min 中push的元素都是从max中来的
        heapq.heappush(self.max_heap,-num)
        heapq.heappush(self.min_heap,-heapq.heappop(self.max_heap))
        if len(self.max_heap) < len(self.min_heap) :
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
        return 

    def findMedian(self) -> float:
        if len(self.max_heap) - len(self.min_heap) == 0 :
            return (self.min_heap[0] - self.max_heap[0])/2
        else: return -self.max_heap[0]

下面这个是比较快的写法。上面的写法 每次都要把元素加入到大堆 然后再做处理，有咩有简单点的方法呢？ 这个的关键是 push pop ：我们首先明确 两个堆 必须是 大顶的数量 不少于小顶 且最多多一个 才是合理的。而且我们明确，为了保持一致性，两个堆的数据有序性，需要靠堆之间传递元素来满足。
那么如果两个数量相等，那么就往小顶堆塞一个 然后小顶堆再吐一个给大。反之反之。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from heapq import *

class MedianFinder:
    def __init__(self):
        self.A = [] # 小顶堆，保存较大的一半
        self.B = [] # 大顶堆，保存较小的一半

    def addNum(self, num: int) -> None:
        if len(self.A) != len(self.B):
            heappush(self.B, -heappushpop(self.A, num))
        else:
            heappush(self.A, -heappushpop(self.B, -num))

    def findMedian(self) -> float:
        if len(self.A) != len(self.B) :
            return self.A[0] 
        else:
            return (self.A[0] - self.B[0]) / 2.0

Trash 二分查找找位置 然后插入

时间复杂度是 ，因为有个insert操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MedianFinder:
    def __init__(self):
        self.nums = []

    def addNum(self, num: int) -> None:
        l,r = 0, len(self.nums)-1
        while l<=r :
            mid = (l+r)//2
            #找 第一个大于他的位置
            if self.nums[mid] > num :
                r = mid-1
            else :
                l = mid+1
        self.nums.insert(l,num)

    def findMedian(self) -> float:
        l = len(self.nums)
        return (self.nums[l//2] + self.nums[(l-1)//2])/2

77. 买卖股票的最佳时机121-20260112

思路一：记录每个位置后面的最大值

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 记录每个位置后面的最大值
        t_max = prices[-1]
        ans = 0
        for i in range(len(prices)) :
            index = len(prices)-i-1
            t_max = max(t_max,prices[index])
            ans = max(t_max-prices[index],ans)
        return ans

不用max 只用 一次len 会加速速度 如果更新了最低价 就不需要 更新ans了

1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 记录每个位置之前的最小值
        past_min, ans = +inf, 0
        for p in prices :
            past_min = p if p < past_min else past_min
            ans = p-past_min if (p-past_min) > ans else ans
        return ans

78. 跳跃游戏55-20260112

记录能跳到的最远位置 为什么这个贪心是正确的呢？这个题目中 能到的位置 是连续的 也就是 确定了最远到的位置之后，之前的位置一定都是可以访问的。 nums到farest 之间一定是连续的。

1
2
3
4
5
6
7
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farest_index, l = 0, len(nums)
        for i in range(l) :
            if i > farest_index : break
            farest_index = max(farest_index,i + nums[i])
        return farest_index >= l-1
1
2
3
4
5
6
7
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farest_index, l = 0, len(nums)
        for i in range(l) :
            if i > farest_index : return False
            farest_index = max(farest_index,i + nums[i])
        return True

79. 跳跃游戏 II45-20260112

思路一：贪心 - UES

每次跳的时候 维护一个边界 边界变的时候 step +1 mlgb 这个贪心太难想了，其实本质是记录了一个 几步最远可以跳到哪里。贪心 有意思

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def jump(self, nums: List[int]) -> int:
        # 维护 跳到一个位置时候 能到的最大位置是多少 还是贪心
        step, farest, end, l = 0, 0, 0, len(nums)
		if l == 1 :return 0
        for i in range(l) :
            farest = max(nums[i] + i, farest)
            if i == end :
                end = farest
                step += 1
                # print(step,end) # 几步最远可以跳到哪
                if end >= l-1 : return step

Trash - 动态规划 但是不好

时间复杂度很高

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def jump(self, nums: List[int]) -> int:
        # 记录到达每个位置的 最小步数
        l = len(nums)
        dp = [+inf] * l
        dp[0] = 0
        for i in range(l):
            for j in range(1,nums[i]+1) :
                if i+j == l : break
                dp[i+j] = min(dp[i+j],dp[i]+1)
        return dp[-1]

有时间可以再做一下这两个 跳跃游戏 III 跳跃游戏 VII

80. 划分字母区间763-20260112

首先 写在外面
!important: 什么时候用贪心通俗理解：“只顾眼前最优，就能得到最终最优”，无后效性。 这个题目就是很无后效性

思路一：贪心

这个就是把start end 排成这样的：然后找分割位置就行

1
2
3
4
5
6
7
8
9
---
 --
  ----
   -
    ---
	 --
	  -
	   ---
	    --
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 partitionLabels(self, s: str) -> List[int]:
        start,end,l = {},{},len(s)
        for i in range(l) :
            cf = s[i]
            cl = s[l-1-i]
            if cf not in start.keys() :
                start[cf] = i
            if cl not in end.keys() :
                end[cl] = l-i-1
        # print(start,end)
        mp = [(start[c],end[c]) for c in start.keys() ]
        mp = sorted(mp,key= lambda x: x[0])
        # print(mp)
        ans,nans ,split_index = [],0,0
        for item in mp :
            if split_index < item[0] :
                ans.append(split_index+1-nans)
                nans = split_index+1
            split_index = max(item[1],split_index)
        ans.append(l-nans)
        return ans

思路二：另一种贪心

其实我觉得本质是差不多的 可以好好看看别人的代码，这个是别人写的 上面是我自己写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_occ = {}
        for i in range(len(s)):
            last_occ[s[i]] = i

        start = 0
        end = 0
        ans = []
        for i in range(len(s)):
            end = max(end,last_occ[s[i]])
            if i == end:
                ans.append(end -start + 1)
                start = i + 1
                
        return ans

81. 爬楼梯70-20260112

我觉得这个是很经典的动态规划 像分硬币一样 很简单

1
2
3
4
5
6
class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [1] * (n+1)
        for i in range(2,n+1) :
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

虽然这个题目很简单，但是题解里面的两个解法很牛逼 可以看看 一个是斐波那契的通项公式 还有一个是矩阵的快速幂

82. 杨辉三角118-20260112

1
2
3
4
5
6
7
8
9
10
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans,last = [[1]],[1]
        for i in range(2,numRows+1) :
            temp = [1]*i
            for j in range(1,i-1) :
                temp[j] = last[j-1]+last[j]
            last = temp
            ans.append(temp)
        return ans

下面是题解：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ret = list()
        for i in range(numRows):
            row = list()
            for j in range(0, i + 1):
                if j == 0 or j == i:
                    row.append(1)
                else:
                    row.append(ret[i - 1][j] + ret[i - 1][j - 1])
            ret.append(row)
        return ret

83. 打家劫舍198-20260112

这个就是零一背包感觉 也很简单 注意这里的dp是处理到 i ，i 偷或不偷 跟dp没关系

1
2
3
4
5
6
7
8
9
class Solution:
    def rob(self, nums: List[int]) -> int:
        # 处理完（偷或者不偷）第i个房子后的 最大值
        dp,l = nums[:],len(nums)
        if l == 1 : return nums[0]
        dp[1] = max(nums[0:2])
        for i in range(2,l) :
            dp[i] = max(dp[i-2]+nums[i],dp[i-1])
        return dp[-1]

而且只需要看前两个，所以不用开一块内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0

        size = len(nums)
        if size == 1:
            return nums[0]
        
        first, second = nums[0], max(nums[0], nums[1])
        for i in range(2, size):
            first, second = second, max(first + nums[i], second)
        
        return second

84. 完全平方数279-20260112

这个也很简单

1
2
3
4
5
6
7
8
9
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [+inf] * (n+1)
        dp[0],dp[1] = 0,1
        for i in range(n+1):
            for j in range(1,int(sqrt(i))+1) :
                dp[i] = min(dp[i],dp[i-j**2]+1)
        return dp[n]

85. 零钱兑换322-20260112（位运算**）

这个也很简答，coins 排序一下 可以break掉一部分。

1
2
3
4
5
6
7
8
9
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [+inf] * amount
        coins = sorted(coins)
        for i in range(1,amount+1) :
            for c in coins :
                if i-c < 0 : break
                dp[i] = min(dp[i], dp[i-c]+1 )
        return dp[amount] if dp[amount] != inf else -1

思路？位运算 NB

还没看懂 感觉有点牛逼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        mask = (1 << (amount + 1)) - 1
        dp = 1
        count = 0
        coins = set(coin for coin in coins if coin <= amount)
        while not dp >> amount:
            count += 1
            new = dp
            for coin in coins:
                shifted = (dp & (mask >> coin)) << coin
                new |= shifted
            if new == dp:
                return -1
            dp = new
        return count

86. 单词拆分139-20260112

思路一： 动态规划

其实最开始的尝试 也就是下面的 dp 设置 是正确的 但是用了 BFS做而不是动态规划
自己又写了一遍 对了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 到index 为止（包括） 能不能被组成
        dp = [False] * (len(s)+1)
        dp[0] = True
        wordDict = set(wordDict)
        wordLenList = set()
        for w in wordDict:
            wordLenList.add(len(w))
        wordLenList = sorted(list(wordLenList))
        for i in range(len(s)+1):
            for l in wordLenList :
                if i-l < 0: break
                dp[i] = dp[i-l] and s[i-l:i] in wordDict
                if dp[i] : break
                print(i,l,i-l,dp[i-l],s[i-l:i],dp[i])
        print(dp)
        return dp[-1]

Trash-BFS

BFS 但是不对

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
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        #如果就不存在的字母直接 False
        WW = ''
        for w in wordDict :
            WW+=w
        charSet = set(WW)
        for c in s:
            if c not in charSet : return False

        # 到index 为止（包括） 能不能被组成
        dp = [False] * (len(s)+1)
        dp[0] = True
        wordDict = set(wordDict)
        wordlenlist = set()
        for w in wordDict :
            wordlenlist.add(len(w))
        wordlenlist = sorted(list(wordlenlist))
        print(wordlenlist)
        lastTrue = [0]
        que = deque([0])
        while que :
            index = que.popleft()
            for l in wordlenlist :
                if index+l > len(s) : break
                if s[index:index+l] in wordDict :
                    dp[index+l] = True
                    que.append(index+l)
        print(dp)
        return dp[-1]

思路二：BFS 题解的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len = max(map(len, wordDict))  # 用于限制下面 j 的循环次数
        words = set(wordDict)  # 便于快速判断 s[j:i] in words

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int) -> bool:
            if i == 0:  # 成功拆分！
                return True
            for j in range(i - 1, max(i - max_len - 1, -1), -1):
                if s[j:i] in words and dfs(j):
                    return True
            return False

        return dfs(len(s))

87. 最长递增子序列300-20260112

思路一： 动态规划

dp 数组是 以i为结尾的 子序列 最大长度，这个方法的复杂度是 ，怎么优化呢我觉得在找的时候用别的办法。维护一个单调递增栈？下面试一下。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        ans = 1
        # 以第i个数为结尾的子序列 （必选i）
        dp = [1] * len(nums)
        for i in range(len(nums)) :
            # 得往前找比他小的
            for j in range(i) :
                if nums[j] < nums[i] :
                    dp[i] = max(dp[i],dp[j]+1)
                    ans = max(ans,dp[i])
        return ans

ERROR

这个是错误的，来个0把前面的弹飞完了 \尴尬

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 加上单调栈
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        ans = 1
        # 以第i个数为结尾的子序列 （必选i）
        dp = [1] * len(nums)
        # 维护一个单调栈 简化内层循环
        stk = []
        for i in range(len(nums)) :
            while stk and nums[stk[-1]] >= nums[i] :
                stk.pop()
            stk.append(i)
            print(i,stk)
            # 得往前找比他小的
            for j in stk :
                if nums[j] < nums[i] :
                    dp[i] = max(dp[i],dp[j]+1)
                    ans = max(ans,dp[i])
        print(dp)
        return ans

思路二：贪心+二分

这个太帅了 贪心都太帅了

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 lengthOfLIS(self, nums: List[int]) -> int:
        # 用 dp 维护一个 dp[i] 表示 **长度为 i 的最长上升子序列的末尾元素的最小值** dp 并不直接是一个子序列注意定义
        d = []
        for n in nums:
            # 如果这个数能构成上升序列就加进来
            if not d or n > d[-1]:
                d.append(n)
            # 若构成不了，也要把这个数换进来，用二分查找 找该换到的位置。（为了保证数组尽量上升的慢）更新的是len为 mid 结尾的最小元素
            else:
                l, r = 0, len(d) - 1
                loc = r
                while l <= r:
                    mid = (l + r) // 2
                    if d[mid] >= n:
                        loc = mid
                        r = mid - 1
                    else:
                        l = mid + 1
                d[loc] = n
            print(n,d)
        return len(d)

88. 乘积最大子数组152-20260112*

这个题目的题解写的很好，看题解吧。重点是维护一个max 一个min

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # dp 以j为结尾的成绩的最大值
        dp_max = nums[:]
        dp_min = nums[:]
        for i in range(1,len(nums)):
            dp_max[i] = max(dp_max[i-1]*nums[i],nums[i],dp_min[i-1]*nums[i])
            dp_min[i] = min(dp_min[i-1]*nums[i],nums[i],dp_max[i-1]*nums[i])
        return max(dp_max)

89. 分割等和子集416-20260115

写了一个 的方法 不是最好的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)/2
        if target%1!=0 : return False
        mp = defaultdict(int)
        mp[int(target)] = 1
        for n in nums:
            ks = list(mp.keys())
            for k in ks:
                if k==n : return True
                if k-n > 0 : mp[k-n]+=1
            mp[target-n]+=1
        return False

思路一：递归

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
from functools import lru_cache

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        #sumV = sum(nums)
        # can I find a subset of integers which can 
        # summ to sumV/2
        
        s = sum(nums)
        if s % 2 == 1:
            return False
        
        half = s//2
        
        def subSum(currSum,i):
            if i < 0:
                return False
            if currSum + nums[i] == half:
                return True
            if currSum + nums[i] < half:
                if subSum(currSum+ nums[i],i-1):
                    return True
                else:
                    return subSum(currSum,i-1)
        return subSum(0,len(nums)-1)

思路二：位运算

看不懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s%2:return False
        bit = 1
        target = s //2
        for x in nums:
            bit |= (bit << x)
        return (bit >> target) & 1 == 1

        # @cache
        # def dfs(i, cur):
        #     if i < 0:
        #         return False
        #     #这项选还是不选
        #     if cur == target:
        #         return True
        #     else:
        #         return dfs(i-1, cur + nums[i]) or dfs(i-1, cur)
        return dfs(n-1, 0)

90. 最长有效括号32-20260115*****

思路一：栈**********

注意每次存下（ 的位置 ，然后 遇到 ）就pop 如果空了就把这个）的位置记录为新的开始 否则 更新答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 滑动窗口对应一个栈,start end 是闭开
        ans,stk = 0,[-1]
        for i in range(len(s)) :
            if s[i] == '(' : stk.append(i)
            else :
                stk.pop()
                if not stk :
                    stk.append(i)
                else :
                    ans = max(ans,i-stk[-1])
        return ans

思路二：动态规划 没看懂

记录以i位置结尾的最大子串

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 以i位置为结尾的最大子串
        if not s : return 0
        if s=='()' : return 2
        dp = [0] * len(s)
        for i in range(1,len(s)) :
            if s[i] == '(' : dp[i] = 0
            else :
                if s[i-1] == '(' : dp[i] = 2 + (dp[i-2] if i-2 >= 0 else 0)
                elif i-dp[i-1]>0 and s[i-dp[i-1]-1]=='(': 
                    dp[i] = dp[i-1]+ (dp[i-dp[i-1]-2] if i-dp[i-1]-2 >=0 else 0) + 2
        return max(dp)

91. 不同路径62-20260115

思路一：排列组合

这个不就是排列组合么

1
2
3
4
5
6
7
8
A = [1] * 200
for i in range(1,200) :
    A[i] = A[i-1] * i

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # A(m+n-2)/(A(n-1)*A(m-1))
        return int(A[m+n-2]/(A[n-1]*A[m-1]))

思路二：动态规划

1
2
3
4
5
6
7
8
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
        print(f)
        for i in range(1, m):
            for j in range(1, n):
                f[i][j] = f[i - 1][j] + f[i][j - 1]
        return f[m - 1][n - 1]

92. 最小路径和64-20260115

经典动态规划 应该挺简单的

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # dp到达某个点的最短距离
        for r in range(1,len(grid)):
            grid[r][0] += grid[r-1][0]
        for c in range(1,len(grid[0])):
            grid[0][c] += grid[0][c-1]
        for r in range(1,len(grid)) :
            for c in range(1,len(grid[0])) :
                grid[r][c] += min(grid[r-1][c],grid[r][c-1])
        return grid[-1][-1]

93. 最长回文子串5-20260115

很慢

dp 用 判断 i,j 是不是 用 前一个判断就行 但是是 的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # dp 以 i 为结尾的最长子序列 这个难以实现 试试 i,j 是否构成 回文串
        l = len(s)
        isPal = set()
        for i in range(l) :
            isPal.add((i,i))
            isPal.add((i+1,i)) # cbbd 这种
        ans = s[0]
        # ij 是不是 依赖 i+1 j-1 画个i*j图 确定遍历顺序
        for j in range(l) :
            for i in range(j,-1,-1):
                if (i+1,j-1) in isPal and s[i]==s[j] : 
                    isPal.add((i,j))
                    ans = s[i:j+1] if j-i+1 > len(ans) else ans
        return ans

思路一： 中心拓展算法

在上面的基础上 ，遍历每个回文中心和 长度

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
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:  # 处理空字符串边界case
            return ""
        
        l = len(s)
        isPal = set()
        # 初始化：单个字符是回文（i,i），空区间（i+1,i）表示偶数长度回文的初始状态
        for i in range(l):
            isPal.add((i, i))
            isPal.add((i+1, i))  # 对应偶数长度回文的初始（如cbbd中bb的初始）
        ans = s[0]  # 初始最长回文为第一个字符

        # 中心扩展：遍历每个可能的中心（奇数长度中心为i，偶数长度中心为i和i+1）
        for i in range(l):
            # -------- 处理奇数长度回文（中心为i） --------
            lenPal = 0  # 扩展半径，初始0（仅包含中心i）
            # 扩展条件：左右边界不越界，且扩展后的字符相等
            while i - lenPal - 1 >= 0 and i + lenPal + 1 < l:
                # 核心：只要左右字符相等，就构成新的回文，无需依赖之前的isPal（简化逻辑）
                if s[i - lenPal - 1] == s[i + lenPal + 1]:
                    new_left = i - lenPal - 1
                    new_right = i + lenPal + 1
                    isPal.add((new_left, new_right))
                    # 更新最长回文
                    if new_right - new_left + 1 > len(ans):
                        ans = s[new_left:new_right + 1]
                    lenPal += 1
                else:
                    break  # 无法扩展，终止当前中心的奇数扩展
            
            # -------- 处理偶数长度回文（中心为i和i+1） --------
            lenPal_even = 0  # 偶数扩展半径，初始0
            while i - lenPal_even >= 0 and i + lenPal_even + 1 < l:
                # 核心：偶数回文需要i-lenPal_even 和 i+lenPal_even+1 字符相等
                if s[i - lenPal_even] == s[i + lenPal_even + 1]:
                    new_left = i - lenPal_even
                    new_right = i + lenPal_even + 1
                    isPal.add((new_left, new_right))
                    # 更新最长回文
                    if new_right - new_left + 1 > len(ans):
                        ans = s[new_left:new_right + 1]
                    lenPal_even += 1
                else:
                    break  # 无法扩展，终止当前中心的偶数扩展
        
        return ans

思路二：马拉车算法 Manacher （一般不作为面试内容

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
class Solution:
    def expand(self, s, left, right):
        """中心扩展算法,计算当前节点的臂长"""
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return (right - left - 2) // 2

    def longestPalindrome(self, s: str) -> str:
        # 马拉车算法
        
        # 1.初始化
        # 初始化输出结果的指针位置
        start, end = 0, -1
        # 初始化字符串
        s = '#' + '#'.join(list(s)) + '#'
        # 记录每个中心的回文臂长
        arm_len = []
        # 历史到达的最远的右指针位置
        right = -1
        # 历史到达最远右指针位置对应的回文中心
        j = -1
        # 当前节点为中心的回文臂长

        # 2.遍历回文中心
        for i in range(len(s)):
            # 3.如果此时遍历的中心点已经超过了最远的有边界位置
            if i > right:
                cur_arm_len = self.expand(s, i, i)
            # 4.如果还没超过
            else:
                # 4.1计算对称点
                i_sym = 2*j - i
                # 4.2计算开始遍历的臂长
                min_arm_len = min(arm_len[i_sym], right - i)
                # 4.3更新臂长
                cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
            # 5.记录当前位置的臂长
            arm_len.append(cur_arm_len)
            # 6.如果当前臂长超过了最长记录,更新状态
            if i + cur_arm_len > right:
                right = i + cur_arm_len
                j = i
            # 7.如果长度大于输出的结果
            if 2 * cur_arm_len + 1> end - start:
                start = i - cur_arm_len
                end = i + cur_arm_len
        
        # 8.切片输出跳过#
        return s[start + 1: end + 1 : 2]

最好*：别人写的中心拓展

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        ans_left = ans_right = 0
        #奇数长度回文的中心：n 个,偶数中心：n-1个；总共：n + (n-1) = 2n - 1 个中心
        for i in range(2*n-1):      
            l,r = i//2, (i+1)//2  #通过整数除法处理奇偶中心
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 1 > ans_right - ans_left:
                ans_left,ans_right = l+1, r
        return s[ans_left : ans_right]

94. 最长公共子序列1143-20260116

动态规划 注意DP数组的定义

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # dp i,j 表示 t1 [0:i] t2[0,j] 的最长公共序列长度 闭
        dp = [[0]*(len(text2)+1) for _ in range((len(text1)+1))]
        for i in range(1,len(text1)+1):
            for j in range(1,len(text2)+1):
                if text1[i-1] == text2[j-1] :
                    dp[i][j] = dp[i-1][j-1]+1
                else :
                    dp[i][j] = max( dp[i-1][j], dp[i][j-1] )
        return dp[-1][-1]

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # Step 1: Record positions of each character in text1
        char_masks = {}
        for i, char in enumerate(text1):
            char_masks[char] = char_masks.get(char, 0) | (1 << i)
        
        # v stores the "increment" bits (1 if dp[j] > dp[j-1])
        v = 0
        for char in text2:
            # x marks all possible match positions OR existing increments
            x = char_masks.get(char, 0) | v
            
            # (v << 1) | 1 creates a "borrow" bit to start the chain reaction
            # x - (...) performs bit-parallel search for the first available '1'
            # x ^ (...) identifies which bits were affected by the subtraction
            # x & (...) picks the bits that actually contribute to the LCS increment
            v = x & (x ^ (x - ((v << 1) | 1)))
            
        return v.bit_count() # count_set_bits(v)

95. 编辑距离72-20260116（没做）

这两个题好难啊

96. 只出现一次的数字136-20260116

技巧：位运算

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for n in nums :
            ans^=n
        return ans

97. 多数元素169-20260116

用on的空间

1
2
3
4
5
6
7
8
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        mp = defaultdict(int)
        for n in nums :
            mp[n]+=1
        for k,v in mp.items() :
            if v > len(nums)/2 :
                return k
1
2
3
4
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[(len(nums) - 1) // 2]

用o1的空间 随机找

1
2
3
4
5
6
7
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majority_count = len(nums) // 2
        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate

Boyer-Moore 投票算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

作者：力扣官方题解
链接：https://leetcode.cn/problems/majority-element/solutions/146074/duo-shu-yuan-su-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

98. 颜色分类75-20260116（没做）

99. 下一个排列31-20260116