目录
- 152. 乘积最大子数组
- 83. 删除排序链表中的重复元素
- 695. 岛屿的最大面积
- 198. 打家劫舍
- 139. 单词拆分
- 堆排序
- 24. 两两交换链表中的节点
- 560. 和为 K 的子数组
- 209. 长度最小的子数组
- 297. 二叉树的序列化与反序列化
152. 乘积最大子数组
题目链接
Python
class Solution:
def maxProduct(self, nums: List[int]) -> int:
pre_max=pre_min=res=nums[0]
for i in range(1,len(nums)):
cur_max=max(pre_max*nums[i],nums[i],pre_min*nums[i])
cur_min=min(pre_max*nums[i],nums[i],pre_min*nums[i])
pre_max=cur_max
pre_min=cur_min
res=max(pre_max,res)
return res
83. 删除排序链表中的重复元素
题目链接
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
cur=head
while cur.next:
if cur.val==cur.next.val:
cur.next=cur.next.next
else:
cur=cur.next
return head
695. 岛屿的最大面积
题目链接
Python
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
def dfs(x, y):
area = grid[x][y] # 计算与其连接的陆地的面积
used[x][y] = True # 将与其连接的陆地都标记为True（已经访问过）
for d in dirs:
nx, ny = x + d[0], y + d[1]
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1 and used[nx][ny] == False:
area += dfs(nx, ny)
return area
m,n=len(grid),len(grid[0])
used = [[False] * n for _ in range(m)]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
res = 0
for i in range(m):
for j in range(n):
if used[i][j] == False and grid[i][j] == 1:
area = dfs(i, j)
res = max(res, area)
return res
哔哩哔哩暑期实习考过这题。在做该题之前建议先做 200. 岛屿数量
198. 打家劫舍
题目链接
Python
class Solution:
def rob(self, nums: List[int]) -> int:
# dp[i]表示到nums[i]（含）所能偷的最大金额
n=len(nums)
if n==1:
return nums[0]
dp=[0]*len(nums)
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
for i in range(2,n):
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
return dp[-1]
139. 单词拆分
题目链接
Python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n=len(s)
dp=[False]*(n+1)
dp[0]=True # dp[i]的i表示字符串的长度
# 背包
for i in range(n): # i是指字符串的开始索引，0~n-1
# 物品
for j in range(i+1,n+1): # j是指字符串的结束索引，i+1~n（字符串截取不包括结束索引）
if dp[i] and s[i:j] in wordDict:
dp[j]=True
return dp[n]
该题属于 完全背包 问题，完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。核心代码中两层for循环是可以完全颠倒的，先遍历背包后遍历物品，先遍历物品再遍历背包都是可以的。
- 求组合数：先遍历物品再遍历背包。
- 求排列数：先遍历背包后遍历物品。
堆排序
题目链接
Python
class Solution:
def adjust(self,nums,parent,length):
"""
nums：待排序数组
parent：父结点的索引
length：参与调整的数组长度（结点个数）
"""
child=parent*2+1
while child<length:
if child+1<length and nums[child+1]>nums[child]:
child+=1
if nums[parent]<nums[child]:
nums[parent],nums[child]=nums[child],nums[parent]
parent=child
child=2*parent+1
else:
break
def sortArray(self, nums: List[int]) -> List[int]:
# 建立堆结构
for i in range(len(nums)//2-1,-1,-1):
self.adjust(nums,i,len(nums))
for i in range(len(nums)-1,0,-1):
nums[0],nums[i]=nums[i],nums[0]
self.adjust(nums,0,i)
return nums
24. 两两交换链表中的节点
题目链接
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy=ListNode(next=head)
cur=dummy
while cur.next and cur.next.next:
node1=cur.next
node3=cur.next.next.next
cur.next=cur.next.next # node2
cur.next.next=node1
# 两个两个地交换
node1.next=node3
cur=cur.next.next
return dummy.next
560. 和为 K 的子数组
题目链接
Python
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
from collections import defaultdict
presums=defaultdict(int)
presums[0]=1
count=0
presum=0
for i in range(len(nums)):
presum+=nums[i]
# 下面两行不能交换顺序
count+=presums[presum-k] # 利用defaultdict的特性，当【presum-k不存在】时，返回的是0。这样避免了判断，如果交换了顺序会导致presum-k可能存在，如输入：[1] 0
presums[presum]+=1
return count
209. 长度最小的子数组
题目链接
Python
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
s=0
i=0
inf=float("inf")
res=inf
n=len(nums)
for j in range(n):
s+=nums[j]
while s>=target:
res=min(res,j-i+1)
s-=nums[i]
i+=1
return 0 if res==inf else res
297. 二叉树的序列化与反序列化
题目链接
Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Codec:
# BFS解法
def serialize(self, root):
"""Encodes a tree to a single string.
序列化二叉树:二叉树->字符串
:type root: TreeNode
:rtype: str
"""
if not root:
return "[]"
q=deque([root])
res=[]
while q:
node=q.popleft()
if node:
res.append(str(node.val))
q.append(node.left)
q.append(node.right)
else:
res.append("null")
return "["+",".join(res)+"]"
def deserialize(self, data):
"""Decodes your encoded data to tree.
反序列化二叉树:字符串->二叉树
:type data: str
:rtype: TreeNode
"""
# data是字符串，不能像下面这样写
# if not data:
# return
if data=="[]":
return
vals, i = data[1:-1].split(','), 1
root = TreeNode(int(vals[0]))
q=deque([root])
while q:
node = q.popleft()
if vals[i] != "null":
node.left = TreeNode(int(vals[i]))
q.append(node.left)
i += 1
if vals[i] != "null":
node.right = TreeNode(int(vals[i]))
q.append(node.right)
i += 1
return root
