LeetCode100 -- Day1
1.动态规划：118、279、322
（1）118 杨辉三角
可以看做是一个下三角形式的数组.
每一行的第一个和最后一个元素均为1，中间其他元素是自己头顶和左上方元素之和。
class Solution(object):def generate(self, numRows):results=[[1]] ## 第一行只有一个1for i in range(1, numRows):pre_row = results[i-1] ## 获取上一行cur_row = [1] ## 每一行的第一个元素为1for j in range(1,i): ## 中间[1,i-1]的元素为头顶和左上方元素之和cur_row.append(pre_row[j]+ pre_row[j-1])cur_row.append(1) ## 每一行最后一个元素为1results.append(cur_row)return results（2）279 完全平方数
dp[i]：和为 i 时所需的最少完全平方数的数量，目标是计算 dp[n]。
状态更新：对于每个数字i（从 1 到 n），考虑所有可能的完全平方数 j²（ j² ≤ i)，如果使用 j² 作为其中一个平方数，那么剩余部分为 i−j² ，其最少平方数数量为 dp[ i
-j²]，因此，dp[i] 应该是所有可能的 j（ j² ≤ i） 中，dp[ i - j² ] + 1 的最小值。
import math
class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""dp=[float('inf')]*(n+1) ## 初始化为极大值dp[0]=0for i in range(1,n+1):max_j = int(math.sqrt(i))for j in range(1, max_j+1):dp[i]=min(dp[i], dp[i-j*j]+1)return dp[n]（3）322 零钱兑换
dp[i]：和为 i 使用的硬币最少个数
状态更新：
遍历coins数组中的coin，如果coin<=i，则可能会用到这枚coin，那么就要查看剩余金额使用的硬币最小个数 → dp[i-coin]+1
如果用不到这枚coin，则金额不变 → dp[i]
class Solution(object):def coinChange(self, coins, amount):if amount == 0:return 0dp = [float('inf')]*(amount+1)dp[0] = 0for i in range(1, amount+1):for coin in coins:if coin<=i:dp[i] = min(dp[i], dp[i-coin]+1)if dp[amount] == float('inf'):return -1return dp[amount]2.贪心算法：121
在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择
与动规不同之处：动态规划需要保存子问题解并重用，而贪心算法不会回头改变之前的选择
（1）121 买卖股票的最佳时机
本质上：最大利润 = 最高价 - 最低价，同时最高价对应的index必须大于最低价
class Solution(object):def maxProfit(self, prices):max_profit = 0min_price = prices[0]for cur_price in prices:if cur_price < min_price:min_price = cur_priceelif cur_price - min_price > max_profit:max_profit = cur_price - min_pricereturn max_profit3.二分查找：35、74
（1）35 搜索插入位置
class Solution(object):def searchInsert(self, nums, target):n = len(nums)left = 0right = n-1while left<=right:mid = (left+right)//2if target == nums[mid]:return midelif target < nums[mid]:right = mid-1else:left = mid+1return left（2）74 搜索二维矩阵
class Solution(object):def searchMatrix(self, matrix, target):m = len(matrix)n = len(matrix[0])if target < matrix[0][0] or target > matrix[-1][-1]:return Falsetop, bottom = 0, m-1## 先找在哪一行while top <= bottom:row_mid = (top+bottom)//2## target比当前行最小值还小→往上找if matrix[row_mid][0]>target:bottom = row_mid-1## target比当前行最大值还打→往下找 elif matrix[row_mid][-1]<target:top = row_mid+1else: ## 行内查找left, right = 0, n-1while left<=right:col_mid = (left+right)//2if matrix[row_mid][col_mid]==target:return Trueelif matrix[row_mid][col_mid]<target:left = col_mid+1else:right = col_mid-1## 没找到target→不存在return Falsereturn False4.二叉树：94、104、102、226
（1）94 二叉树中序遍历
递归法：
class Solution(object):def inorderTraversal(self, root):results=[]def traverse(node):if not node:returntraverse(node.left)results.append(node.val)traverse(node.right)traverse(root)return results迭代法：
stack=[]results=[]cur_node=rootwhile cur_node or stack:## 找到最左节点while cur_node: stack.append(cur_node)cur_node=cur_node.left## 处理根节点cur_node=stack.pop()results.append(cur_node.val)## 处理右子树cur_node=cur_node.right return results （2）104 二叉树最大深度
class Solution(object):def maxDepth(self, root): if not root:return 0left = maxDepth(root.left)right = maxDepth(root.right) return max(left,right)+1 （3）102 二叉树层序遍历
from collections import deque
class Solution(object):def levelOrder(self, root):""":type root: Optional[TreeNode]:rtype: List[List[int]]"""if not root:return []results=[]quene=deque([root])while quene:cur_level=[]for _ in range(len(quene)):node = quene.popleft()cur_level.append(node.val)if node.left: quene.append(node.left)if node.right: quene.append(node.right)results.append(cur_level)return results（4）226 翻转二叉树
class Solution(object):def invertTree(self, root):""" 后序遍历实现 """if not root:return """ 递归翻转左右子树 """self.invertTree(root.left)self.invertTree(root.right)""" 交换当前节点的左右子树 """root.left, root.right = root.right, root.left return root