剑指offer03-数组占用重复的数字
创建一个哈希表，遍历数组，如果数组中没有这个元素，就将元素加入进去，如果
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
# 创建一个哈希表，用来存储遍历到的数字
dic = []
n = len(nums)
for i in range(n):
# 如果在哈希表中没有这个数字，就把该数字的下标加进来
if nums[i] in dic:
return nums[i]
else:
dic.append(nums[i])
剑指offer04-二维数组中的查找
从左下角开始查找
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
# 如果数组为空，返回false
if not matrix:
return False
n= len(matrix)
m = len(matrix[0])
# 整体思路从左下角开始遍历
i = n-1
j = 0
while(i>=0 and j <m):
if target< matrix[i][j]:
i -=1
# 如果正好找到，返回true
elif target==matrix[i][j]:
return True
# 如果目标值大于遍历的值，需要在下一列去寻找
else:
j +=1
return False
反思为什么用for循环反而会出错的原因：
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
# 如果数组为空，返回false
if not matrix:
return False
n= len(matrix)
m = len(matrix[0])
# 当数组只有一行的时候
if n==1:
for j in range(m):
if target==matrix[0][j]:
return True
return False
# 当数组只有一列的时候
if m==1:
for j in range(n):
if target==matrix[j][0]:
return True
return False
# 整体思路从左下角开始遍历
for i in range(n-1,0,-1):
for j in range(m):
# 如果目标值小于此时遍历的值，需要到上一行去寻找
if target< matrix[i][j]:
i -=1
# 如果正好找到，返回true
elif target==matrix[i][j]:
return True
# 如果目标值大于遍历的值，需要在下一列去寻找
else:
j +=1
return False
剑指offer05-替换空格
方式一：采用python中内置的replace()函数可以直接将’ ‘ 替换为%20
class Solution:
def replaceSpace(self, s: str) -> str:
# 直接用replce函数进行替换
return s.replace(" ","%20")
方式二：空数组不断加入以及组成新的数组的形式
class Solution:
def replaceSpace(self, s: str) -> str:
res = []
# 在字符串中遍历，当遍历到空格的时候，加入%20，当遍历到字符串的时候，加入进去
for c in s:
if c == ' ':
res.append("%20")
else:
res.append(c)
# 返回用"."连接的字符串
return "".join(res)
剑指offer09-用两个栈实现队列
这里重在理解相应的题意，以及理解栈与队列的性质
class CQueue:
def __init__(self):
# 写一个方法，定义两个栈，其中栈A作为主栈，栈B作为辅助栈
# 栈A实现入队功能，栈B实现出队功能
self.A,self.B=[],[]
#定义在队列尾部插入整数的函数，插入操作是有参数，没有返回值的
# 直接在A中插入元素就可以
def appendTail(self, value: int) -> None:
self.A.append(value)
# 定义在头部删除整数的函数，删除操作没有参数，有返回值
def deleteHead(self) -> int:
# 如果栈B有值的话，就弹出返回即可
if self.B:
return self.B.pop()
# 如果栈A中没有值，表明此时构造的队列是空的，deleteHead操作返回-1
if not self.A:
return -1
# 如果栈A中有元素，将栈A中的元素弹出添加到栈B中（栈B元素实现栈A元素的倒序）
while self.A:
self.B.append(self.A.pop())
# 栈B执行出栈，相当于删除A的栈底元素，实现队首元素的删除
return self.B.pop()
最后的一个函数也可以做适当的变化
def deleteHead(self) -> int:
# 如果栈A为空,直接返回-1
if not self.A and not self.B:
return -1
# 如果栈B为空
if not self.B:
while self.A:
self.B.append(self.A.pop())
# 栈B执行出栈，相当于删除A的栈底元素，实现队首元素的删除
return self.B.pop()
同时联系之前的一道题，基本上同样的思维模式，其中的pop()函数和empty()函数在上一道题目中包含在deleteHead()函数中了。
leetcoad232-用栈实现队列
class MyQueue:
def __init__(self):
# 定义两个栈
self.A,self.B=[],[]
# 将元素推到队列的末尾
def push(self, x: int) -> None:
self.A.append(x)
# 移除队首元素
def pop(self) -> int:
# 如果栈B为空
if not self.B:
while self.A:
self.B.append(self.A.pop())
return self.B.pop()
# 返回队列开头的元素(pop和peek的区别，一个是删除，一个是返回)
def peek(self) -> int:
if not self.B:
while self.A:
self.B.append(self.A.pop())
return self.B[-1]
# 定义一个empy函数，如果为空返回true，如果不为空就返回false
def empty(self) -> bool:
# 判断是否两个栈都为空
if not self.A and not self.B:
return True
else:
return False
剑指offer 06-从尾到头打印链表
备注：此题与反转链表之间的区别与联系
写法一：采用栈的写法
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
# 构建一个栈（也是一个数组）
stack = []
while head:
# 把链表的头节点加入栈中
stack.append(head.val)
# 不断的把头节点的值指向下一个结点，类似一个遍历的过程（不断的进行入栈的操作，直到头节点为空的时候跳出循环）
head = head.next
# 直接返回倒序数组
return stack[::-1]
# 真正运用栈的思想的，只是从概念上去理解，实际没必要，因为多用了一个res数组
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
# 构建一个栈
stack = []
while head:
# 把链表的头节点加入栈中（push：入栈）
stack.append(head.val)
head = head.next
res=[]
while stack:
# pop：出栈
res.append(stack.pop())
return res
写法二：采用递归的方式
# 另外写了一个DFS的函数
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
def dfs(head):
# 递归终止条件
if not head:
return []
# 每次返回当前的list +当前的节点值，实现节点的倒序输出
return dfs(head.next) + [head.val]
return dfs(head)
或者采用这样的递归形式，利用已有的函数一步到位
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
# 递归终止条件
if not head:
return []
else:
return self.reversePrint(head.next) + [head.val]
剑指offer 11-旋转数组中的最小数字
- 原来的数组是递增有序
- 左边元素大于右边元素
- 首先肯定是要用二分法的（排序数组的查找优先使用二分），目的是看中间元素是在哪个排序数组中
- 在采用的基础上，要用中间的值和右边的值进行比较才能知道旋转的数到底在哪个区间范围内（如果与左边的值进行比较的话，无法选定区间）
- 为什么要单独区分中间值与右边值相等的情况:先记住
class Solution:
def minArray(self, numbers: List[int]) -> int:
n = len(numbers)
if n ==1:
return numbers[0]
# 采用二分查找的思路解题
left=0
right=n-1
while left < right:
mid = left +(right-left)//2
# 如果中间的值大于右边的值，mid在左排序数组中，所以旋转的元素在右边区间：[mid+1,right]之间，left=mid+1
if numbers[mid]>numbers[right]:
left = mid+1
# 如果中间的值小于右边的值，这是一个正常的排序，mid在右排序数组中，所以旋转的元素在[left,mid]之间，right=mid（mid也可能是一个旋转元素，不能排除mid比左边的元素更小）
elif numbers[mid] <numbers[right]:
right = mid
# 如果中间的值等于右边的值，无法判断到底在哪个区间
else:
# 一个一个的往前去遍历，找到那个最小值
return self.findMin(numbers,left,right)
return numbers[left]
# 从头到尾遍历numbers获取最小值
def findMin(self,numbers,left,right):
res=numbers[left]
for i in range(left,right+1):
# 一旦发现遍历的值还小于左边这个值，就更新这个最小值
if numbers[i]< res:
res=numbers[i]
return res
剑指offer12-矩阵中的路径
题目描述：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
加上自己的一点理解：回溯，在每一层的搜索里面，不管有没有找到，都需要往回走
还有要把DFS想象成为一个多叉树，每个下面都是有多种选择的，如果不对就回退，接着进行选择
要解决什么叫搜索过的问题
需要将字符串进行拆分，一个一个元素进行匹配
通过两层嵌套覆盖所有的情况
写入dfs函数：
终止条件：
- 边界情况的判断:行越界、列越界、以及网格中的任何一个元素都没有与word中的字母匹配，返回False
- 当访问到最后一个字符的时候，说明成功匹配到了最后一个元素，直接返回True(网格中存在这个单词)
递推工作：
- 标记当前矩阵元素，将其修改为特殊字符，代表元素已经访问，防止之后的搜索重复访问
- 搜索元素的四个方向，匹配下一个目标元素，使用或来连接（只需找到一条可行的路径就直接返回，不再做后续的DFS）,并记录结果至res
- 还原当前矩阵：一趟结束后，把原来设置的’#’改成匹配好的字符，以免影响后面dfs的遍历。将board[i][j]还原至初始值:work[k] 这里是自己在学习算法的时候最难立即的一点
返回值：
返回布尔量res,代表是否搜索到目标的字符串
# 要加上自己的本地调试过程（必须要做到），同时还要结合岛屿数量的那一道题或者思路再整理一遍
# 深度优先搜索+剪枝
# 深度优先搜索：暴力遍历矩阵中所有字符串可能性，DFS通过递归，先朝一个反向搜搜索到底，再回溯到上一个节点，沿着另外的一个方向搜索，以此类推。
# 剪枝：在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况，（例如：此矩阵元素和目标字符不同、此元素已被访问[后面处理的方式也是一个亮点]），则应立即返回，称之为 可行性剪枝
from typing import List
# 根据输入的条件，预计需要输出的是true,相当于作为一个理解题目的过程
"""
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
"""
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
# 二维网格的行数与列数
m,n = len(board),len(board[0])
# 遍历网格,通过两层嵌套覆盖所有的情况，一个字母一个字母的尝试
for i in range(m):
for j in range(n):
# 以左上角第一个元素为起点进行相应的dfs搜索，如果能够查到，直接返回true,所有的情况都没没有找到，返回False（是一个查找字符的过程）
if self.dfs(board,word,i,j,0):
return True
return False
# dfs作用：查看在给定的网格中是否存在word这个路径
# x 和y分别表示行和列数
# k 表示访问到word中的字母的下标（递归参数有三个）
def dfs(self,board: List[List[str]],word,x,y,k):
# 对各种边界条件进行判断,两个终止条件
# 终止条件一：行或列索引越界或当前矩阵元素与目标字符不同
if x <0 or x>=len(board) or y<0 or y >=len(board[0]) or board[x][y]!=word[k]:
return False
# 当程序跑到word的最后一个字母的时候，不需要搜索，直接返回True
if k==len(word)-1:
return True
# 把访问过的字母标记为"#"，代表已经遍历了，以免影响后面dfs的遍历使用
# 只会保证当前的匹配方案中不要走回头路，一旦看到这个符号，说明不能走回头路，但是于此同时也只是影响当前的匹配方案，因为如果匹配成功与不成功，要回溯返回，此时需要取消标记（也就是后面的操作）
board[x][y]="#"
# 进行剪枝,按照上下左右的顺序进行搜索去匹配word中下一个字母，用res进行记录
# 也即朝四个方向递归，看是否有能够匹配下一个字母的元素存在，只需要找到一条可行的路径就直接返回，不再做后续的dfs（一条不行就另外换一条路径）
res = self.dfs(board,word,x-1,y,k+1) or self.dfs(board,word,x+1,y,k+1) or self.dfs(board,word,x,y-1,k+1) or self.dfs(board,word,x,y+1,k+1)
# 一趟结束后，把原来设置的'#'改成匹配好的字符，以免影响后面dfs的遍历,因为一旦没有找到还需要回退到上一层或上上层去寻找
board[x][y]=word[k]
# 如果能够找到就返回res
return res
# 头文件（本地调试的时候需要）
if __name__ == '__main__':
# 输入一个特定的需要求解的数组
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word="BFCE"
res = Solution().exist(board,word)
print(res)
# print(" 输出 => " ,res)
提供另外的一种解决思路
# 另外的一种思路：按照岛屿数量的思路来写，借鉴黑眼圈的写法
# 之前不算正真的理解，所以在调试之后发现还是很有新的收获的
# 主函数退出递归的条件：要么已经找到了一条完整的路径，要么网格已经遍历完全了（刚开始是自己一直疑惑的点）
# 但是这里的解法还是有问题，没有体现回溯的过程，还是不太建议采用
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m,n = len(board),len(board[0])
for i in range(m):
for j in range(n):
if self.dfs(board,word,i,j,0):
return True
return False
def dfs(self,board: List[List[str]],word,x,y,k):
# 如果board[x][y]元素与words的第k个元素不相等，直接返回结果
if board[x][y]!=word[k]:
return False
# 当程序跑到word的最后一个字母的时候，不需要搜索，直接返回
if k==len(word)-1:
return True
# 原来位置的字符串，用临时变量进行存储，在每一个递归里面都会变化
temp = board[x][y]
# 把访问过的字母标记为"#"，代表已经遍历了，以免影响后面dfs的遍历使用
board[x][y]="#"
# 循环遍历当前位置的上、下、左、右四个方向
for dx, dy in ((-1,0),(1,0),(0,-1),(0,1)):
newX = dx + x
newY = dy + y
# 如果新的位置超出了数组边界 或者 已经访问过
if newX <0 or newX>=len(board) or newY<0 or newY >=len(board[0]) or board[newX][newY]=="#":
continue
# 递归搜索新的位置
if self.dfs(board,word,newX,newY,k+1):
return True
# 恢复状态，这里恢复状态的方式也要注意理解：因为已经位于循环的外面，不能用上面的解法：board[x][y]=word[k],用的是变量temp进行存储的
board[x][y]=temp
return False
剑指offer13-机器人的运动范围
再做第二遍的时候，思路及代码必须自己独立实现，不能辅助其他的方法，看懂之后再写。
题目分析：在一个m行n列的方格之中，机器人可以从[0.0]开始向上下左右移动，但是不能出界也不能进入到行坐标与列坐标的数位之和大于k的格子，问机器人最多能够达到多少的格子？
这里自己做了一个excel表格帮助自己去理解，其中m=n=20,k=8,表中红色区域是满足要求的，并且机器人是可以达到的，黄色区域虽然满足数位之和的要求，但是机器人并不能达到，仍然不是题目中符合要求的格子。
有两个关键点记录一下：
- 避免少统计：遍历所有能移动的格子
- 避免重复统计：每次统计完一个格子后将其移除
- 还有一点：符合要求的区域机器人不一定能够到达（重点理解），中间有一些不符合要求的区域机器人无法跨越
- 机器人从一个方向出发，直到达到不可到达的区域才会返回，是深度优先遍历
- 机器人不断的重复从一个格子出发探索、返回携带数量以及清除区域操作，用递归来解决
- 数位之和的计算可以用一个函数来辅助的计算（思维方式吧，实现的过程并不难，但是就是要十分的熟练）
使用图片来辅助理解
移动机器人前进和后退的移动轨迹（也即DFS的递归和回溯过程）
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
# 使用临时变量 visited 记录格子是否被访问过
visited=[[0]*n for _ in range(m)]
# 开始深度优先遍历
return self.dfs(0,0,m,n,k,visited)
# 写一个深度优先遍历函数
def dfs(self,i,j,m,n,k,visited):
# 几种边界条件
# 行列索引越界
if i >=m or j >=n :
return 0
# 数位和超出目标值 k ，即不满足行坐标和列坐标的数位之和小于 k 的格子（剪枝1）
if self.sum(i,j)>k:
return 0
# 已经被访问过的格子（剪枝2）
if visited[i][j]:
return 0
# 机器人进入了一个新格子，标注这个格子被访问过
visited[i][j]= True
# 沿着当前格子的右边和下边继续访问
# 回溯返回值：返回1+下方搜索可达的解总数+右方搜索的可达解总数
return 1+ self.dfs(i+1,j,m,n,k,visited) +self.dfs(i,j+1,m,n,k,visited)
# 写一个计算两个坐标之和的函数sum
def sum(self,i,j):
# 通过求余与取整的方式来计算
ia,ib=i//10,i%10
ja,jb=j//10,j%10
s = ia +ib +ja +jb
return s
# 把计算数位之和的函数优化一下
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
# 使用临时变量 visited 记录格子是否被访问过
visited=[[0]*n for _ in range(m)]
# 开始深度优先遍历
return self.dfs(0,0,m,n,k,visited)
# 写一个深度优先遍历函数
def dfs(self,i,j,m,n,k,visited):
if i >=m or j >=n or:
return 0
if self.sum(i)+self.sum(j)>k: return 0
if visited[i][j]:
return 0
visited[i][j]= True
return 1+ self.dfs(i+1,j,m,n,k,visited) +self.dfs(i,j+1,m,n,k,visited)
def sum(self,i):
s = 0
while i!=0:
# 计算数位之和
s+=i +i%10
# 计算十位数
i = i//10
return s
剑指offer 18 删除链表的节点
需要定义两个指针，不断的向右移动
当cur指针访问到需要删除的元素的受，将pre指针指向cur的下一个指针（此时需要删除的节点，没有任何一个指针指向它）
最后返回链表的头节点就是删除后的链表
特殊情况的处理：当删除的节点就是头节点的时候，直接返回头节点的下一个节点
循环的终止条件：cur指针指向空或是cur指针指向的节点值就是要删除的值
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
# 特殊的情况处理
if head.val==val:
return head.next
# 遍历整个链表,要用指针来做,实质是一种二叉树的遍历框架
# 定义两个指针pre,cur
pre,cur= head,head.next
# 当cur的节点值等于val的时候跳出循环
while cur and cur.val != val:
# while cur.val != val:
pre= cur
cur = cur.next
pre.next= cur.next
return head
剑指offer 21调整数组顺序使奇数位于偶数前面
采用双指针的做法：让left左边都是奇数，让right右边都属偶数
如果left指针指向的元素值是奇数，说明该元素在左侧，让left向右移动
如果right指针指向的元素是偶数，那么元素在右侧，让right向左移动
否则，要么left指向的为偶数，right指向的为奇数，交换两个位置的元素（空变量），题目不难，主要是找对思路就可以了。
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
# 采用双指针的写法
left ,right = 0,len(nums)-1
# 采用二分查找的思路
while left < right:
# 如果left指针指向的元素是奇数，说明该元素应该再左侧，让left向右移动
if nums[left]%2==1:
left +=1
# 如果right指针指向的元素是偶数，那么元素在右侧，让right向左移动
elif nums[right]%2==0:
right-=1
else:
temp = nums[left]
nums[left]= nums[right]
nums[right]=temp
return nums
剑指offer22 链表中倒数第k个节点
仍然是采用双指针，同时让其中的一个节点先走k步(这里实现的过程也是一个考察点，需要自己注意)
然后两个指针同时向右移动，直到先行的指针指向为空此时后面的那个指针指向的就是要求的链表（理解这里的思想很重要）
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
# 定义两个指针
pre,cur=head,head
# 让cur指针提前向右移动k步
for i in range(0,k):
cur=cur.next
# 让两个指针同时向向移动，跳出循环的条件是cur指针指向为空
while cur:
pre=pre.next
cur = cur.next
return pre
剑指offer 26 树的子结构
利用二叉树递归的代码（做的时候，这几种情况记得再判断一下 ）
边界的判断：
空树不是任意一个树的子结构
查看几种情况：
- A的根节点与B的根节点相同，依次比较他们的子节点
- A的根节点与B的根节点不同，A的左子树与B的根节点比较
- A的根节点与B的根节点不同，A的右子树与B的根节点比较
用两张图来辅助理解：
要判断B是否是A的子结构，要么一开始就从A和B的根节点开始
如果根节点不相同，就需要判断B是否为A的左子树或右子树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
# 先从两个根节点出发进行判断
# 如果一开始A或者B为空，直接返回False（特例情况：空树不是任何一个树的子结构）
if not A or not B:
return False
# 判单B是否是A的左子树含有右子树的结构：实际上是有以下的三种情况，都可以通过函数的递归抵用来解决
# 接下来主要比较的点：A与B的根节点的比较（A的左右子树的节点与B的根节点的比较）,本质是对A进行一个先序遍历
# 情况一：如果找到相同的节点值，判断它们各自的左右子节点是否相同（以节点A为根节点的子树包含树B,直接用dfs）
# 情况二：如果A根节点与B的根节点不同，比较A的左子树与B的根节点（树B是树A左子树的子结构,用isSubStructure(A.left,B)）
# 情况三：如果A根节点与B的根节点不同，比较A的右子树与B的根节点 (树B是树A右子树的子结构,用isSubStructure(A.right,B)）
return self.dfs(A, B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)
# 写一个函数，作用是：从上一个函数得到的根节点开始递归比较是否右子树
def dfs(self,A,B):
# 一开始去找A和B完全匹配的情况
# 递归的终止条件：
# 终止条件一：# 对B不断的进行遍历，直到为空（B已经递归到叶子节点了），说明B的全部节点都和A的子结构能够匹配
if not B:
return True
# 终止条件二：如果A中的节点为空，B中的节点不为空，不能匹配
if not A:
return False
# 终止条件三：如果A和B都不为空，但是数值又不同，也是不匹配的（理解）
if A.val != B.val:
return False
# 返回值：当前的这个点是匹配的（A.val= B.val），继续的递归判断左子树和右子树是否分别匹配（需要同时递归）
return self.dfs(A.left,B.left) and self.dfs(A.right,B.right)
剑指offer 27-二叉树的镜像
总体的思路：
- 把根节点的左子树先抽离出来进行保存
- 把当前节点的右子树镜像到镜像的二叉树中
- 把原左子树放到镜像二叉树的右子树中
- 在整个的过程中都是递归的进行操作的
# 递归的写法：类似于交换两个数的写法
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
# 当节点为空时，直接返回
# 递归的出口
if not root:
return None
# 设置一个临时的节点 tmp 用来存储当前节点的左子树（避免覆盖后找到左右子节点）
temp = root.left
# 以下两个操作是在交换当前节点的左右子树
# 当前节点的左子树为节点的右子树
# 同时递归下去，不停的交换子树中的节点
root.left=self.mirrorTree(root.right)
# 当前节点的右子树为节点的左子树
# 同时递归下去，不停的交互子树中的节点
root.right=self.mirrorTree(temp)
# 最后返回根节点
return root
看到题解的时候发现还有很多其他的解法在里面，如果自己右精力的话可以去考虑一下。
剑指offer28-对称的二叉树
题目本身是一个定义题，自己之前也是做过的，二叉树的本质都是递归的做法
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
# 边界情况
if not root:
return True
return self.isSymmetricalTree(root.left,root.right)
# 定义一个判断两个二叉树是否对称的函数isSymmetricalTree
def isSymmetricalTree(self,left, right):
# 如果根子树的左右两个节点同时为空，肯定是对称的，直接的返回true
if not left and not right:
return True
# 如果根子树的左右子树有一个为空，一个有值，不对称，返回false
elif not left or not right:
return False
# 左右子树都是有值的
else:
# 如果左子树与右子树的值不相等，不对称，返回fasle
if left.val !=right.val:
return False
# 递归的对比当前节点的左子树的左子树与右子树的右子树、左子树的右子树与右子树的左子树是否对称
return self.isSymmetricalTree(left.left,right.right) and self.isSymmetricalTree(left.right,right.left)
# 把代码做一点简化操作
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
return self.isSymmetricalTree(root.left,root.right)
def isSymmetricalTree(self,left, right):
if not left and not right:
return True
# 上面的几种判断的情况，由于返回值是相同的，可以进行合并
if not left or not right or left.val !=right.val:
return False
# 递归的对比当前节点的左子树的左子树与右子树的右子树、左子树的右子树与右子树的左子树是否对称
return self.isSymmetricalTree(left.left,right.right) and self.isSymmetricalTree(left.right,right.left)
剑指offer32-I从上到下打印二叉树II(树的按层打印，打印到一个数组中)
后面的连续的三道题要求理解并加深相应的印象，对于理解层序遍历(BFS)概念十分有帮助！！！！
要点如下：
- 边界条件的判断：当根节点为空的时候，返回空数组
- 需要借助一个队列，先将二叉树的根节点入队，然后出队，访问出队节点
- 如果有左子树，则将左子树的根节点入队，若有右子树，将右子树的根节点入队
- 然后出队，访问根节点，如此反复直到队列为空
这里贴一段伪代码，加强学习与记忆：
void LevelOrder(BiTree T){
InitQueue(Q) ; //初始化辅助队列
BiTree p;
EnQueue(Q,T); //将根节点入队
while (!IsEmpty(o)){ //队列不空则循环
DeQueue(Q,P) //队头节点出队
visit(p) //访问出队节点
if (p->left!=NULL)
EnQueue(Q,P->left); //左子树不空，则左子树根节点入队
if (p->right!=NULL)
EnQueue(Q,P->right); //右子树不空，则左子树根节点入队
}
}
以下为本题的python的实现代码：
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
# 根节点为空的情况返回空数组
if not root:
return []
# 生成一个队列，用来保存节点
# queue=collections.deque()
queue=[]
# 生成一个 res，用来保存输出的节点
res = []
# 首先让根节点入队
queue.append(root)
# 遍历队列，直到队列为空
while queue:
# 获取队列的头部元素(把队列的队头元素进行推出)
# curNode=queue.popleft()
curNode=queue.pop(0)
# 把推出的结点值存放到 res 中
res.append(curNode.val)
# 判断该节点是否有左右子节点
# 如果左子节点有值，则把左子节点加入到队列中
if curNode.left:
queue.append(curNode.left)
# 如果右子节点有值，则把右子节点加入到队列中
if curNode.right:
queue.append(curNode.right)
return res
剑指offer32-II从上到下打印二叉树II(层序遍历)
在上一题的基础上加入了需要每一层打印到一行，也是层序遍历的精髓所在。
主要是要通过图深刻的将层序遍历的思想彻底弄清楚，有几个要点：
- 在大的循环下面（只要队列不为空就一直循环），打印的时候需要加入一个循环将队列中的元素不断加入到数组中，其中循环的次数与队列的长度（也即每层的节点的个数有关）
- 每一层的循环结束后，把层的结果添加到最后的结果中
- 出队
- 打印
- 添加子节点
# 第二次写了，当成模板来记忆就行
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
# 根节点为空的情况返回空数组
if not root:
return []
# 生成一个队列，用来保存节点
queue=[]
# 生成temp和res，分别用来保存每一层的节点和全部层的结果
res = []
# 首先让根节点入队
queue.append(root)
# 遍历队列，直到队列为空
while queue:
# 记录queue的长度，即每层节点的个数
n= len(queue)
temp=[]
# 用for循环将队列中的元素添加到temp数组中
# temp =[num for num in queue]
for i in range(n):
# 把队列的头部元素弹出
curNode=queue.pop(0)
# 用temp数组保存当前层的元素
temp.append(curNode.val)
# print(temp)
# 判断该节点是否有左右子节点
# 如果左子节点有值，则把左子节点加入到队列中
if curNode.left:
queue.append(curNode.left)
# 如果右子节点有值，则把右子节点加入到队列中
if curNode.right:
queue.append(curNode.right)
# 把每一层的元素加入到res数组中
res.append(temp)
print(res)
return res
剑指offer32-III从上到下打印二叉树III(打印顺序按照层的奇偶性交替变化)
同时在打印的时候，创建的打印数组必须是双端队列，满足可以从队头或者队尾插入元素的要求：奇数层添加至尾部，偶数层添加至头部
需要用到python中的：from collections import deque
值得学习别人的一些比较好的做法，后面有时间再细细的研究
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er--3/
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
# 根节点为空的情况返回空数组
if not root:
return []
# 生成一个队列，用来保存节点
queue=[]
# 生成temp和res，分别用来保存每一层的节点和全部层的结果
res = []
# 首先让根节点入队
queue.append(root)
# 写一个函数用来判断当前的层数是否为奇数层，最开始是为奇数层的
isOddNnumber = False
# 遍历队列，直到队列为空
while queue:
# 记录queue的长度，即每层节点的个数,用于后面将每一层队列的元素加入到temp中
n= len(queue)
# 奇数与偶数层交替出现
# 通过取反操作，判断当前的层数是否为奇数层
# 由于isOddNnumber初始化为False，第一次进来这个while循环取反之后为true
isOddNnumber=~ isOddNnumber
# 生成一个双端队列,只有双端队列才可以从尾部加入到队列中
temp=collections.deque()
# 用for循环将队列中的元素添加到temp数组中
# temp =[num for num in queue]
for i in range(n):
# 把队列的头部元素弹出
curNode=queue.pop(0)
# 用temp数组保存当前层的元素
# 如果发现是奇数层，需要从头加入到尾部
if isOddNnumber:
temp.append(curNode.val)
# 如果发现是偶数层，需要从尾部加到头部
else:
temp.appendleft(curNode.val)
# 判断该节点是否有左右子节点
# 如果左子节点有值，则把左子节点加入到队列中
if curNode.left:
queue.append(curNode.left)
# 如果右子节点有值，则把右子节点加入到队列中
if curNode.right:
queue.append(curNode.right)
# 把每一层的元素加入到res数组中
res.append(list(temp))
return res
剑指offer33-二叉搜索树的后序遍历
剑指offer35-复杂链表的复制
剑指offer36-二叉搜索树与双向链表
剑指offer39-数组中出现次数超过一半的
剑指offer41-数据流中的中位数
如果是奇数个数值，中位数是数值排序后中间的数值
如果是偶数个数值，中位数是数值排序后中间两个数的平均值
有几个注意点：
- 数据在不断的变
- 求中位数的方法也在不断的变
- 对于动态的数据，借助堆来帮忙解决
- 大顶堆：用来存储数据流中较小的一半（递增，堆顶为最大值）
- 小顶堆：存储数据流中较大的一半（递增，堆顶为最小值）
- 保持大顶堆与小顶堆的元素个数相同（两个堆顶元素平均数）或者至多相差一个，更多的元素出现在小顶堆中（直接将小顶堆的堆顶元素弹出就行）
- 重要的是：维护大小顶堆的过程：
- 想要添加一个元素到小顶堆，先到大顶堆中排序一番，将大顶堆的堆顶元素弹出来加入到小顶堆中
剑指offer43-1~n中整数中1出现的次数
剑指offer44数字序列中某一位的数字
剑指offer45-把数组排列成最小的数
剑指offer46-把数字翻译成字符串
剑指offer47-礼物的最大价值
剑指 Offer48-最长不含重复字符的子字符串
剑指offer49-丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
理解题目的意思：
假设已知的丑数序列：1，2，3，4，5，6，8，9，
- nums2数组中存储这个序列中所有丑数与2相乘的结果,nums={ 1 * 2 ， 2 * 2 ，3 * 2 ， 4 * 2 ，5 * 2 ，6 * 2 ，8 * 2，。。。}
- nums3 数组存储了这个序列中所有丑数与 3 相乘的结果，nums3 = { 1 * 3 ， 2 * 3 ，3 * 3 ， 4 * 3 ，5 * 3 ，6 * 3 ，8 * 3，。。。}
- nums5 数组存储了这个序列中所有丑数与 5 相乘的结果，nums5 = { 1 * 5 ， 2 * 5 ，3 * 5 ， 4 * 5 ，5 * 5 ，6 * 5 ，8 * 5，。。。}
也就是说，每次寻找丑数的过程是在 nums2 、nums3、nums5 这三个数组中寻找最小值的过程。
- 在寻找过程中，因为丑数的序列在不断的扩充，nums2 、nums3、nums5 这三个数组也在不断的扩充。
- 每次找到那个最小值之后，接下来的寻找过程应该忽略它了。