Day18
Title45.jump(跳跃游戏 II)
解法一：动态规划
依然分三步走：
1.状态方程
2.dp[i]的意义
3.边界条件及初始值
优先思考第二个问题：
dp[i]表示到达i时需要的最少跳数
第一个问题：
dp[i+j]=min(dp[i]+1,dp[i+j])
为什么？我们要保证前面已经确定好为最小步数的情况下，让其从这个节点向下去跳，那么就需要去对比并更新到达该节点的最小距离，j的最远距离为x，即能从外层遍历节点出发所到达的最远距离。
第三个问题：
初始值全部为数组最大长度n，因为最远最远为一步一步跳，那么最远才需要跳n步，第一个值定位0，因为出发点就为索引号为0的地方。
class Solution(object):def jump(self, nums):""":type nums: List[int]:rtype: int"""m=len(nums)dp=[m for _ in range(m)]dp[0]=0for i in range(m):x=nums[i]for j in range(x+1):if i+j<m :dp[i+j]=min(dp[i+j],dp[i]+1)return dp[m-1]解法二：贪心算法
反向思考，如果要到达最后一个位置，那么最远最远从前面哪里起跳，如果可以从这个位置起跳，那么当前索引+x一定会超过position，此时怎么接着思考呢？更新position的位置为当前离最后一个位置最远的索引点，再依次类推，直到position被更新到索引0
class Solution(object):def jump(self, nums):""":type nums: List[int]:rtype: int"""# 反向思考，如果要到达最后一个位置，那么最远最远从前面哪里起跳#如果可以从这个位置起跳，那么当前索引+x一定会超过position#此时怎么接着思考呢？更新position的位置为当前离最后一个位置最远的索引点，再依次类推，直到position被更新到索引0position=len(nums)-1step=0while position!=0:for i in range(len(nums)-1):if nums[i]+i>=position:position=istep+=1breakreturn step解法三：正向检查的贪心
每一次尝试跳最远的距离，在所有当前可调节点当中进行比对，那个可以跳的最远就走那个
Title46.全排列
方法1：回溯法（方法非常好想出来，只是解题代码需要理清楚）
关于回溯法，进行以下步骤的思考
固定步骤
1.设置接受符合规则的结果列表，同时设置每轮迭代的存储列表
2.思考什么情况下向本轮结果集合当中添加新元素，同时思考迭代进行传递的值是什么
3.思考什么情况下将当前论的结果存入最终结果
class Solution(object):def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""n = len(nums)res, path = [], []def dfs(i):if i == n:res.append(path[:])returnfor j in range(0,n):if nums[j] not in path:path.append(nums[j])dfs(i+1)path.pop()dfs(0)return resTitle47.全排列2 permuteUnique
方法1：回溯+剪枝
相较于上一个不可重复，这种可重复的更难
本题提供一种新的思路：当前轮的结果不需要一个新列表来存储，而是直接传递列表作为参数，可以避免回溯操作弹出时的复杂性。
剪枝操作的第二个条件难以理解：
本质上是为了避免同层中出现重复元素
- 初始状态：visited数组全为False，当前路径为空。
- 选择第一个元素：
- 可以选择索引0的1，或者索引1的1，或者索引2的2。
- 但是根据剪枝条件，当i=1时，nums[1] == nums[0]，且visited[0]为False（因为还没有被访问过），所以会跳过i=1，不能选第二个1作为第一个元素。
- 因此，第一个元素只能是索引0的1或者索引2的2。
class Solution(object):def permuteUnique(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort() # 关键：排序使相同元素相邻res = []visited = [False] * len(nums) # 记录元素是否被使用过def backtrack(path):if len(path) == len(nums):res.append(path[:])returnfor i in range(len(nums)):# 剪枝条件：跳过已用元素 或 同一层中与前一个相同且未被使用的元素if visited[i] or (i > 0 and nums[i] == nums[i-1] and not visited[i-1]):continuevisited[i] = Truebacktrack(path + [nums[i]])visited[i] = Falsebacktrack([])return res如果不采用第二个剪枝的条件，可以如下方式去写,但是时间消耗大幅度增加。
class Solution(object):def permuteUnique(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort() # 关键：排序使相同元素相邻res = []visited = [False] * len(nums) # 记录元素是否被使用过def backtrack(path):if len(path) == len(nums) and path[:] not in res:res.append(path[:])returnfor i in range(len(nums)):# 剪枝条件：跳过已用元素 或 同一层中与前一个相同且未被使用的元素if visited[i] :continuevisited[i] = Truebacktrack(path + [nums[i]])visited[i] = Falsebacktrack([])return resTitle48 rotate 旋转图像
方法一：用辅助数组旋转，最后再赋值回去,时空复杂度都挺高的，并且违背了题目不让使用额外数组的条件
class Solution(object):def rotate(self, matrix):""":type matrix: List[List[int]]:rtype: None Do not return anything, modify matrix in-place instead."""n=len(matrix)n_matrix=[[0]*n for _ in range(n)]for i in range(n):for j in range(n):n_matrix[j][n-i-1]=matrix[i][j]matrix[:]=n_matrixreturn matrix方法二：原地翻转
利用方法一的算法思想，如果我们直接原地更改matrix，那么会造成matrix[j][n-i-1]原本的值被覆盖，所以我们需要把该位置原本的值也保存起来去更改到他应该的位置，旋转90读，对应四个元素一次性直接修改到指定位置即可。关于i和j的取值，官方题解给的图非常清晰的解释了为什么
官方题解
class Solution:def rotate(self, matrix: List[List[int]]) -> None:n = len(matrix)for i in range(n // 2):for j in range((n + 1) // 2):matrix[i][j], matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1] \= matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1], matrix[i][j]Title49 字符异位词
方法一：排序（没想出来，下次再碰到肯定可以解决）
sorted后生成对应的字符串如果是异位词是唯一的，那么可以当做键。
class Solution(object):def groupAnagrams(self, strs):""":type strs: List[str]:rtype: List[List[str]]"""mp = {} for st in strs:key = ''.join(sorted(st))# 如果键不存在，手动初始化为空列表if key not in mp:mp[key] = []# 添加当前字符串到对应的列表中mp[key].append(st)return list(mp.values())