|
141. 环形链表
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
'''
他让我判断是否有环:
我的想法是:记录,记录,记录,用字典记录(这样查找方便些)
--记录每个变量的内存地址,这样每次遍历的时候查找一遍不挺好?
'''
def fun1(head):
dic={}
while head:
if head in dic:
return True
else:
dic[head]=0
head=head.next
return False
'''
他让我用o(1)的空间复杂度,我应激反应出来了,双指针
因为,只能一个方向所以一定是快慢指针? 嗯应该是这样
那么如果没有环,直到head==None slow和quick都不可能指向同一个节点
如果有环,那么quick和slow是可以指向同一节点的
--因为quick跑的太快又回来了
'''
'''
重点:
如何设计可以使有环的时候,quick一定可以追上slow
这里可以看一下:floyd判环(圈)算法,我没详细看,反正就是一定能追上只要quick比slow快,且有圈
就先理解成套圈吧
'''
p1=ListNode(1)
def fun2(head):
if head == None or head.next == None:
return False
s = head
q = head.next
while q and q.next:
if q == s:
return True
q = q.next.next
s = s.next
return False
print(fun2(p1))
====================================================================================================================================================================================================================================
104. 二叉树的最大深度
'''
'''
哈哈,这个题目我有印象,当时死搞搞了两个多小时,非要尼玛用栈模仿递归
'''
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
'''
广度优先遍历
这种遍历就是,一层一层的遍历树,可以用队列来
'''
def fun1(root):#这个函数的运行结果和这个题目没什么关系,只是从上到下,从左到右进行输出而已
duilie=[]
while duilie or root:#当前节点不为空,或者
if root.left:
duilie.append(root.left)
if root.right:
duilie.append(root.right)
print(root.val)
root=duilie.pop(0)
def fun2(root):#这个的层次更加鲜明,循环里面嵌套循环,嵌套循环用来表示一层,然后顺带着可以算出最大深度
if root==None:
return 0
duilie=[root]
dade=[]
while duilie:#队列不为空进来
size=len(duilie)#获得当前队列长度,相当于一层的个数
ls=[0]*size
for i in range(size):
node=duilie.pop(0)
if node.left:
duilie.append(node.left)
if node.right:
duilie.append(node.right)
ls[i]=node.val
#循环结束
dade.append(ls)
return len(dade)
'''
既然是二叉树,递归就是不可或缺的一部分
那我们来看看递归怎么做?
--1+max(fun3(root.left),fun3(root.right))
你不觉得很好吗?
当前位置是一层+左子树或右子树的最大值,这样不就是最大深度
'''
def fun3(root):
if root==None:
return 0
return 1+max(fun3(root.left),fun3(root.right))
====================================================================================================================================================================================================================================
98. 验证二叉搜索树
'''
二叉搜索树的定义:
--当前节点的左子树只含有小于当前节点的数
--当前节点的右子树只含有大于当前节点的数
--所有的左右子树也为二叉搜索树
二叉搜索树有一个性质:
中序遍历一定是有序的
那么中序遍历有序,可不可以得到该二叉树是二叉搜索树
可以
'''
'''
方法一:
先中序遍历,再判断是否为有序
这个的时间复杂度怎么说呢
中序遍历o(n) 排序o(n*logn)当然这里需要动的并不多,可以达到o(n)不过我不知道python排序的快速排序怎么写的
比较o(n)
时间复杂度:
开了两个列表
'''
'''
这里其实写,非递归的中序遍历更好,因为可以直接在这个过程中比较
'''
class Solution:
def isValidBST(self, root) -> bool:
ls=[]
self.digui(root,ls)
li=ls.copy()
li.sort()
for i in range(len(li)):
if i+1<len(li) and li[i]==li[i+1]:
return False
if li[i]!=ls[i]:
return False
return True
def digui(self,root,ls):
if root==None:
return
self.digui(root.left,ls)
ls.append(root.val)
self.digui(root.right,ls)
'''
我觉得有一种相对上面这样写更好的方法,再遍历的过程中找到左子树的最大值,右子树的最小值,然后与当前节点比较
哈哈哈,这是看答案写的不是很理解
过程有点理不清了
'''
class Solution:
def isValidBST(self, root) -> bool:
return self.bianli(root,float('-inf'),float('inf'))
def bianli(self,root,lower,upper):
if root==None:
return True
val=root.val
if not lower<val<upper:
return False
if not self.bianli(root.left,lower,val):
return False
if not self.bianli(root.right,val,upper):
return False
return True
|