凑零钱问题 状态转移方程 $dp(n)= \begin{cases} -1, & \text {n < 0} \ 0, & \text {n = 0} \ min{dp(n-coin)+1|coin \in coins}, &\text {n > 0 } \end{cases}$
# 凑零钱问题
coins = [1,2,5]
def coinChange(coins: List, amount: int):
dp = list()
for i in range(amount+1):
dp.append(amount+1)
dp[0] = 0
for i in range(len(dp)):
for coin in coins:
if i - coin < 0:
continue
dp[i] = min(dp[i], dp[i-coin] + 1)
return dp[amount] if dp[amount] != amount + 1 else -1
print(coinChange(coins,15))
DFS算法(深度优先搜索) 要点: 路径、选择列表、结束条件
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点:这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
/* 划重点:更新步数在这里 */
step++;
}
}
def binarySearch(nums: list, target: int):
left = 0
right = len(nums) - 1
while(left <= right):
mid = left + (right - left)//2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
# 直接返回
return mid
# 返回-1
return -1
def leftBinarySearch(nums:list, target:int):
left = 0
right = len(nums) - 1
while(left <= right):
mid = left + (right - left)/2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
# 锁定左侧边界
right = mid - 1
# 最后要检查 left 越界的情况
if (left >= len(nums) or nums[left] != target):
return -1
# 因为left == right, right = mid - 1
# return mid - 1
return left
def rightBinarySearch(nums:list, target:int):
left = 0
right = len(nums) - 1
while(left <= right):
mid = left + (right - left)//2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
# 锁定右侧侧边界
left = mid + 1
# 最后要检查 left 越界的情况
if (right < 0 or nums[right] != target):
return -1
# 因为left == right, right = mid - 1
# return mid - 1
return right
#滑动窗口算法框架
def slidingWindow(s:str, t:str):
need = dict()
window = dict()
[need.update({c:0}) for c in t]
left = 0
right = 0
valid = 0
while (right < len(s)):
# c 是将移入窗口的字符
c = s[right]
# 右移窗口
right += 1
# 进行窗口内数据的一系列更新
pass
while( window needs shrink):
# d 是将移出窗口的字符
d = s[left]
left += 1
# 进行窗口内数据的一系列更新
pass
重点在于
- 区分节点终止条件
- 区分处理逻辑应该放在前序、中序、后序中的哪个位置
/* 二叉树遍历框架 */
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
# 通用的遍历框架
def bst(root:TreeNode, target:int):
if root.val == target:
# 处理过程
pass
elif root.val < target:
bst(root.left, target)
elif root.val > target:
bst(root.right, target)
def isValidBST(root: TreeNode):
return _isValidBST(root, null, null)
def _isValidBST(root: TreeNode, min:TreeNode, max:TreeNode):
if root == None:
return True
if min == None && root.val <= min.val:
return False
if max == None && root.val >= max.val:s
return False
return _isValidBST(root.left, min, root) && _isValidBST(root.right, root, max)
def isInBST(root: TreeNode, target: int):
if root == None:
return False
if root.val == target:
return True
elif root.val < target:
return isInBST(root.left, target)
elif root.val > target:
return isInBST(root.right, target)
def insertIntoBST(root: TreeNode, target: int):
if root == None:
return new TreeNode(target)
# if root.val == target:
# # 不会插入已经存在的节点
# pass
if root.val < target:
root.right = insertIntoBST(root.right, target)
elif root.val > target:
root.left = insertIntoBST(root.left, target)
def _getMin(node:TreeNode):
while node.left:
node = node.left
return node
def deleteNode(root:TreeNode, key:int):
if not root:
return None
if root.val = key:
if not root.left:
return root.right
if not root.right:
return root.left
minNode = _getMin(root.right)
# 使用替换值的方式,交换节点
root.val = minNode.val
root.right = deleteNode(root.right, minNode.va2020l)
elif root.val < key:
root.left = deleteNode(root.left, key)
elif root.val > key:
root.right = deleteNode(root.right, key)
return root