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_profit

3.二分查找：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 False

4.二叉树：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