121、Best Time to Buy and Sell Stock
"""
买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
卖出的价格大于买入的价格
"""
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res=0
for i in range(len(prices)):
for j in range(i+1,len(prices)):
if (prices[j]-prices[i])>res:
res=prices[j]-prices[i]
return res
122、Best Time to Buy and Sell Stock II
"""
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
"""
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res=0
for i in range(1,len(prices)):
if prices[i]>prices[i-1]:
res += (prices[i]-prices[i-1])
return res
123、Best Time to Buy and Sell Stock III
"""
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
动态规划
第i天经过k次交易得到的最大利益
dp[k][i] = max(dp[k][i], dp[k-1][j-1] + prices[i] - prices[j]) 0 <=j <= i
"""
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices)==0:
return 0
n=len(prices)
dp=[[0]*n for _ in range(3)]
for k in range(1,3):
for i in range(1,n):
dp[k][i]=max(prices[i]-prices[0],dp[k][i-1])
for j in range(1,i+1):
dp[k][i]=max(dp[k][i],dp[k-1][j-1]+prices[i]-prices[j])
return dp[-1][-1]
124 、Binary Tree Maximum Path Sum
image.png
"""
二叉树最大路径和
global关键字修饰变量后标识该变量是全局变量，对该变量进行修改就是修改全局变量，
nonlocal关键字修饰变量后标识该变量是上一级函数中的局部变量，如果上一级函数中不存在该局部变量，nonlocal位置会发生错误。
给定一个非空二叉树，返回其最大路径和。
路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
递归
自底向上
"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.max=float('-inf')
self.max_path(root)
return self.max
def max_path(self,root):
if not root:
return 0
left=self.max_path(root.left)
right=self.max_path(root.right)
self.max=max(left+right+root.val,self.max)
tmp=max(left,right)+root.val
return tmp if tmp>0 else 0
125、Valid Palindrome
"""
回文串验证
验证一个字符串是否是回文串
忽略符号和大小写
"""
class Solution:
def isPalindrome(self, s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
while i < len(s) and not s[i].isalnum():
i += 1
while j > -1 and not s[j].isalnum():
j -= 1
if i > j:
return True
if s[i].upper() != s[j].upper():
return False
else:
i += 1
j -= 1
return True
126、Word Ladder II
"""
单词接龙
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
"""
#BFS + 层次遍历
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
def backtrack(res,routine,path,endWord):
if len(routine[endWord]) == 0:
res.append([endWord] + path)
else:
for pre in routine[endWord]:
backtrack(res,routine,[endWord] + path,pre)
lookup = set(wordList) | set([beginWord])
res,cur,routine = [],set([beginWord]),{word:[] for word in lookup}
while cur and endWord not in cur:
next_queue = set()
for word in cur:
lookup.remove(word)
for word in cur:
for i in range(len(word)):
for j in range(97,123):
tmp = word[:i] + chr(j) + word[i+1:]
if tmp in lookup:
next_queue.add(tmp)
routine[tmp].append(word)
cur = next_queue
if cur:
backtrack(res,routine,[],endWord)
return res
# DFS+BFS
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
from collections import defaultdict
wordList=set(wordList)
res=[]
next_word_dict=defaultdict(list)
distance={}
distance[beginWord]=0
def next_word(word):
ans=[]
for i in range(len(word)):
for j in range(97,123):
tmp=word[:i]+chr(j)+word[i+1:]
if tmp!=word and tmp in wordList:
ans.append(tmp)
return ans
def bfs():
cur=[beginWord]
step=0
flag=False
while cur:
step+=1
next_time=[]
for word in cur:
for nw in next_word[word]:
next_word_dict[word].append(nw)
if nw==endWord:
flag=True
if nw not in distince:
distince[nw]=step
next_time.append(nw)
if flag:
break
cur=next_time
def dfs(tmp,step):
127、word ladder
"""
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
双向广度优先搜索
双向搜索的结束条件是找到一个单词被两边搜索都访问过了。
"""
from collections import defaultdict
class Solution:
def __init__(self):
self.length=0
self.all_combo_dict=defaultdict(list)
def visitWordNode(self, queue, visited, others_visited):
current_word,level=queue.pop(0)
for i in range(self.length):
intermediate_word=current_word[:i]+"*"+current_word[i+1:]
for word in self.all_combo_dict[intermediate_word]:
if word in others_visited:
return level+others_visited[word]
if word not in others_visited:
visited[word]=level+1
queue.append((word,level+1))
return None
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0
self.length=len(beginWord)
for word in wordList:
for i in range(self.length):
self.all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)
queue_begin=[(beginWord,1)]
queue_end=[(endWord,1)]
visited_begin={beginWord:1}
visited_end={endWord:1}
ans=None
while queue_begin and queue_end:
ans=self.visitWordNode(queue_begin,visited_begin,visited_end)
if ans:
return ans
ans=self.visitWordNode(queue_end,visited_end,visited_begin)
if ans:
return ans
return 0
128、Longest Consecutive Sequence
"""
最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。
input:[100, 4, 200, 1, 3, 2]
output:4
"""
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
hash_dict = dict()
max_length = 0
for num in nums:
if num not in hash_dict:
left = hash_dict.get(num - 1, 0)
right = hash_dict.get(num + 1, 0)
cur_length = 1 + left + right
if cur_length > max_length:
max_length = cur_length
hash_dict[num] = cur_length
hash_dict[num - left] = cur_length
hash_dict[num + right] = cur_length
return max_length
#排序，判断
class Solution:
def longestConsecutive(self, nums):
if not nums:
return 0
nums.sort()
longest_streak = 1
current_streak = 1
for i in range(1, len(nums)):
if nums[i] != nums[i-1]:
if nums[i] == nums[i-1]+1:
current_streak += 1
else:
longest_streak = max(longest_streak, current_streak)
current_streak = 1
return max(longest_streak, current_streak)
129、Sum Root to Leaf Numbers
"""
求根到叶子节点数字之和
从根节点到叶子节点转换为字符串直接连接
连接完后转化为整数相加
"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
self.res = 0
def helper(root, tmp):
if not root:
return
if not root.left and not root.right:
self.res += int(tmp + str(root.val))
return
helper(root.left, tmp + str(root.val))
helper(root.right, tmp + str(root.val))
helper(root, "")
return self.res
130、Surrounded Regions
"""
被围绕的区域
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
"""
#DFS
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
row = len(board)
col = len(board[0])
def dfs(i, j):
board[i][j] = "B"
for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
tmp_i = i + x
tmp_j = j + y
if 1 <= tmp_i < row and 1 <= tmp_j < col and board[tmp_i][tmp_j] == "O":
dfs(tmp_i, tmp_j)
for j in range(col):
# 第一行
if board[0][j] == "O":
dfs(0, j)
# 最后一行
if board[row - 1][j] == "O":
dfs(row - 1, j)
for i in range(row):
# 第一列
if board[i][0] == "O":
dfs(i, 0)
# 最后一列
if board[i][col-1] == "O":
dfs(i, col - 1)
for i in range(row):
for j in range(col):
# O 变成 X
if board[i][j] == "O":
board[i][j] = "X"
# B 变成 O
if board[i][j] == "B":
board[i][j] = "O"
#BFS
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
row = len(board)
col = len(board[0])
def bfs(i, j):
from collections import deque
queue = deque()
queue.appendleft((i, j))
while queue:
i, j = queue.pop()
if 0 <= i < row and 0 <= j < col and board[i][j] == "O":
board[i][j] = "B"
for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
queue.appendleft((i + x, j + y))
for j in range(col):
# 第一行
if board[0][j] == "O":
bfs(0, j)
# 最后一行
if board[row - 1][j] == "O":
bfs(row - 1, j)
for i in range(row):
if board[i][0] == "O":
bfs(i, 0)
if board[i][col - 1] == "O":
bfs(i, col - 1)
for i in range(row):
for j in range(col):
if board[i][j] == "O":
board[i][j] = "X"
if board[i][j] == "B":
board[i][j] = "O"
#并查集
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
f = {}
def find(x):
f.setdefault(x, x)
if f[x] != x:
f[x] = find(f[x])
return f[x]
def union(x, y):
f[find(y)] = find(x)
if not board or not board[0]:
return
row = len(board)
col = len(board[0])
dummy = row * col
for i in range(row):
for j in range(col):
if board[i][j] == "O":
if i == 0 or i == row - 1 or j == 0 or j == col - 1:
union(i * col + j, dummy)
else:
for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if board[i + x][j + y] == "O":
union(i * col + j, (i + x) * col + (j + y))
for i in range(row):
for j in range(col):
if find(dummy) == find(i * col + j):
board[i][j] = "O"
else:
board[i][j] = "X"
网友评论