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: # 这里写个q是为了防止当前q是倒数第二个,然后q=q.next.next得到了None这样的话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)
