学习目标：
- 刷完面试经典150题
- 链接: 面试经典150题
学习内容：
-
- 串联所有单词的子串（困难）→滑动窗口
-
- 组合（中等）→回溯
-
- 最大子数组和（中等）→Kadane 算法
-
- 将二叉搜索树变平衡（中等）→平衡二叉树
-
- 数组中的第K个最大元素（中等）→堆
-
- 搜索插入位置（简单）→二分查找
-
- 搜索二维矩阵（中等）→二分查找
-
- 打家劫舍（中等）→一维动态规划
学习时间：
2024.4.2
知识点
- 回溯算法
- 滑动窗口
- 动态规划
- 回溯
- 堆
- 二分查找
- Kadane 算法
学习内容：
30. 串联所有单词的子串（困难）→滑动窗口
复仇！我来啦！
有了昨天438.求异构词的经验，这道题写起来顺手多了。
思路：
定义一个滑动窗口大小和子串总大小相当
在主串中遍历滑动窗口，判断是否子串的单词全在主串中
（避免子串有重复的单词，用visit标记是否这个单词已经匹配过了）
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
str_w=''.join(words)
ans=[]
l_w=len(str_w) #子串和窗口的大小
l_s=len(s) #字符串大小
if l_w>l_s: #排除不合规的情况
return []
l_word=len(words[0]) #子串每个字符串的大小
n_word=len(words) #子串字符个数
visit = [0] * n_word # 记录子串字符是否匹配过
def isTrue(str, words):
for i in range(len(words)):
if str==words[i] and not visit[i]:
visit[i]=1
return True
for time in range(l_s-l_w+1): #time记录开始索引和循环次数
flag=True #标记是否有不匹配的状况
for i in range(n_word):
visit[i]=0
for i in range(n_word):
if not isTrue(s[time+i*l_word:time+(i+1)*l_word],words):
flag=False
break
if flag:
ans.append(time)
return ans
BUT! 我以为大功告成的时候，不出意料地出了岔子，超时了
不得不说，这个测试用例真恶心。
改正：
这次我尝试使用字典
s_dict记录滑动窗口字符情况
p_dict记录子串字符情况
代码：
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
str_w=''.join(words)
ans=[] #存输出
l_w=len(str_w) #子串和窗口的大小
l_s=len(s) #字符串大小
if l_w>l_s: #排除不合规的情况
return []
l_word=len(words[0]) #子串每个字符串的大小
n_word=len(words) #子串字符个数
p_dict={} #子串字符情况
for i in words:
if i not in p_dict:
p_dict[i]=1
else:
p_dict[i]+=1
for time in range(l_s-l_w+1): #time记录开始索引和循环次数
s_dict = {} # 滑动窗口字符情况
for i in range(n_word):
if s[time+i*l_word:time+(i+1)*l_word] not in s_dict:
s_dict[s[time+i*l_word:time+(i+1)*l_word]] = 1
else:
s_dict[s[time+i*l_word:time+(i+1)*l_word]] += 1
if s_dict==p_dict:
ans.append(time)
return ans
77. 组合（中等）→回溯
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
复习昨天学的回溯算法
用昨天的方法，果不其然，超时了
回溯太难了，我又看了答案，我发誓，明天在做一道，一定不看答案了
class Solution(object):
def combine(self, n, k):
"""
:type n: int [1,n]
:type k: int k个数组合
k<=n
:rtype: List[List[int]]
"""
if n==1 and k==1:
return [[1]]
if k==1:
return [[i+1] for i in range(n)]
ans=[] #记录排列组合
path=[] #记录单词的组合
def dfs(i):
d=k-len(path)
if d==0:
ans.append(list(path))
return
if i >d:
dfs(i-1)
path.append(i)
dfs(i-1)
path.pop()
dfs(n)
return ans
我拷贝了，晚上睡觉的时候偷学，一定要学会！！！！
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
简单题，秒了
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left=0
right=len(nums)-1
mid=(left+right)//2
while left<=right:
if nums[mid]==target:
return mid
elif nums[mid]>target:
right=mid-1
mid=(left+right)//2
else:
left = mid + 1
mid = (left + right) // 2
nums.append(target)
nums.sort()
return left
-74. 搜索二维矩阵（中等）→二分查找
简单题，秒了
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
row=len(matrix)
column=len(matrix[0])
left=0
right=row-1
mid=(left+right)//2
while left <= right:
if matrix[mid][0] == target:
return True
elif matrix[mid][0] > target:
right = mid - 1
mid = (left + right) // 2
else:
left = mid + 1
mid = (left + right) // 2
a=left-1 #执行到这里，应该是每行的首个元素大小不匹配的情况，
#因为没有找到的终止条件是left>right,
#所以right才是最后没有找到元素的位置，故a=right
left = 0
right = column - 1
mid = (left + right) // 2
while left <= right:
if matrix[a][mid] == target:
return True
elif matrix[a][mid] > target:
right = mid - 1
mid = (left + right) // 2
else:
left = mid + 1
mid = (left + right) // 2
return False
1382. 将二叉搜索树变平衡（中等）→平衡二叉树
还以为是构造平衡二叉树呢，仔细一看题发现直接把原来的树中序遍历之后得一个有序数组
然后递归地选取中间节点作为根就ok了
class Solution(object):
def balanceBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
nums=[]
def visited(root):
if root.left:
visited(root.left)
nums.append(root.val)
if root.right:
visited(root.right)
def ave_tree(root,nums,left,right):
mid=(left+right)//2
root.val=nums[mid]
if left<mid:
root.left=TreeNode()
ave_tree(root.left, nums, left, mid - 1)
if right > mid:
root.right = TreeNode()
ave_tree(root.right, nums, mid + 1, right)
if root.left:
visited(root.left)
nums.append(root.val)
if root.right:
visited(root.right)
left=0
right=len(nums)-1
mid=(left+right)//2
root1=TreeNode(nums[mid]) #新的平衡树，中间节点是数组中位数
if left < mid:
root1.left = TreeNode()
ave_tree(root1.left, nums, left, mid - 1)
if right > mid:
root1.right = TreeNode()
ave_tree(root1.right, nums, mid + 1, right)
return root1
53. 最大子数组和（中等）→Kadane 算法
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
又是一个没听说过得算法，甚至怎么读都不知道
必须百度之！
Kadane 算法知识点：
Kadane 算法知识点：
1、用于解决最大子数组和问题（在给定整数数组中找到一个连续的子数组，使其元素之和最大（数组可能含有负数））
2、核心思想是通过迭代数组的每个元素，维护两个变量来跟踪局部最优解和全局最优解
算法步骤:
1、设置两个变量，max_cur(在当前位置结束的最大子数组和)和max_global(全局最大子数组和)。都初始化为第一个变量的值
2、迭代：从数组第二个元素开始遍历。在每一步中，更新这两个变量，
更新max_cur=max(a[i],max_cur+a[i])
>这表示要么继续当前的子数组（如果加上当前元素后和更大），要么重新开始一个新的子数组（如果当前元素本身比之前的子数组和大）
更新max_global=max(max_global,max_cur)
3、返回max_global
时间复杂度： O(n)
我去！好神奇！一把过!!!
代码：
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==1:
return nums[0]
max_cur=nums[0]
max_global=nums[0]
for i in range(1,len(nums)):
max_cur=max(max_cur+nums[i],nums[i])
max_global=max(max_global,max_cur)
return max_global
215. 数组中的第K个最大元素（中等）→堆
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
这道题是关于堆的题，所以第一印象就是建堆，然后依次输入最大值。开干!
两种建堆手法：
库函数建堆：
因为python的建堆函数，默认建立小根堆，所以取相反数建堆，可以建立大根堆
需要引入模块 import heapq
import heapq
for i in range(len(nums)):
nums[i]=-nums[i]
heapq.heapify(nums)
for i in range(len(nums)):
nums[i]=-nums[i]
print(nums)
手动建堆：
if len(nums)==1 and k==1:
return nums[0]
#手撸法
def big_heap(nums):
n=len(nums)
for i in range(n//2-1,-1,-1): #从最后一个非叶子节点开始向上调整
temp=nums[i]
j=2*i+1 #左孩子索引
while j<n:
#如果右孩子存在且右孩子更大
if j + 1 < n and nums[j + 1] > nums[j]:
j = j + 1
if temp>=nums[j]:
break
else: #孩子节点更大
nums[i]=nums[j]
i=j #这两行的作用是递归的向下迭代
j=2*i+1 #当前节点循环过后，i和j开始控制该节点的孩子节点和孙子节点
nums[i]=temp #直到完全遵循大根堆的条件，把开始保存的最初节点放在他该放在的位置上
当我意气风发写完了之后，
气煞老夫!!!为什么超时了！！！我明明写的是大根堆啊
哎可能是我堆的调整有问题吧
看了一眼题解：
import heapq
class Solution(object):
def findKthLargest(self,nums, k):
heap = []
for num in nums: #因为是小根堆，所以每次弹入相反数
heapq.heappush(heap, -num)
for _ in range(k-1):
heapq.heappop(heap)
return -heapq.heappop(heap)
题解中用到了python的内置函数，heapq
我查了查他的功能
功能是建立小根堆
创建堆：两种方式
nums = [4,2,53,12,5,1]
#第一种逐个元素建堆
heap = []
for num in nums:
heapq.heappush(heap, -num)
print(nums)
#[1, 4, 2, 12, 5, 53]
# 第二种：原地建堆
nums = [4,2,53,12,5,1]
heapq.heapify(nums)
print(nums)
#[1, 2, 4, 12, 5, 53])
弹出根元素：
heappop(heap)，返回最小值。
当堆为空，报错indexerror
压入元素：
heappush(heap,item)
最后。。。。。。。。。。。。。。。。。。。。。。。。
呵呵。。
我真的无语！！！！！这都行！！！！我费了好久好久的力气才把堆写好。看一眼题解，发现这个也行阿阿阿阿阿阿阿，我疯了！！！！
最后成果
- 30. 串联所有单词的子串（困难）→滑动窗口
- 53. 最大子数组和（中等）→Kadane 算法
- 1382. 将二叉搜索树变平衡（中等）→平衡二叉树
- 215. 数组中的第K个最大元素（中等）→堆
- 35. 搜索插入位置（简单）→二分查找
- 74. 搜索二维矩阵（中等）→二分查找
- 77. 组合（中等）→回溯
-
- 打家劫舍（中等）→一维动态规划
结论
堆的那道题我直接裂开了，动态规划不写了，留给明天把，我心死
今日精神极其不稳地