阳泉市网站建设_网站建设公司_留言板_seo优化

问题1：

问题链接：

141. 环形链表

问题描述：

给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从0开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。

实例：

代码：

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defhasCycle(self,head:Optional[ListNode])->bool:#快慢指针，再有环的情况下，这俩指针终会相遇，没有环，fast走到头就结束了slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextiffastisslow:returnTruereturnFalse#访问到了链表末尾，没有环

问题2：

问题链接：

142. 环形链表 II

问题描述：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从0开始）。如果 pos 是-1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。

实例：

代码：

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defdetectCycle(self,head:Optional[ListNode])->Optional[ListNode]:slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextiffastisslow:whileslowisnothead:#再走a步,到达入环扣，此时正确位置，因为利用快慢指针，相遇的地方不是入环扣。slow=slow.nexthead=head.nextreturnslowreturnNone

问题3：

问题链接：

143. 重排链表

问题描述：

给定一个单链表 L 的头节点 head ，单链表 L 表示为： L0 → L1 → … → Ln-1→ Ln 请将其重新排列后变为： L0 → Ln → L1 → Ln-1→ L2 → Ln-2→ … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

实例：

代码：

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defreorderList(self,head:Optional[ListNode])->None:# 快慢指针找到链表中点fast=slow=headwhilefast.nextandfast.next.next:slow=slow.nextfast=fast.next.next# cur 指向右半部分链表cur=slow.nextslow.next=None# 反转右半部分链表pre=Nonewhilecur:t=cur.nextcur.next=pre pre,cur=cur,t cur=head# 此时 cur, pre 分别指向链表左右两半的第一个节点# 合并whilepre:t=pre.nextpre.next=cur.nextcur.next=pre cur,pre=pre.next,t

问题4：

问题链接：

144. 二叉树的前序遍历

问题描述：

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

实例：

代码：

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:#2.迭代ans=[]st=[]cur=rootwhilecurorst:whilecur:ans.append(cur.val)st.append(cur)cur=cur.left cur=st.pop()cur=cur.rightreturnans

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:#1.递归ans=[]defdfs(root):ifrootisNone:returnans.append(root.val)dfs(root.left)dfs(root.right)dfs(root)returnans

问题5：

问题链接：

145. 二叉树的后序遍历

问题描述：

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

实例：

代码：

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defpostorderTraversal(self,root:Optional[TreeNode])->List[int]:#1.递归ans=[]defdfs(root):ifrootisNone:returndfs(root.left)dfs(root.right)ans.append(root.val)dfs(root)returnans

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defpostorderTraversal(self,root:TreeNode)->List[int]:# 注意：根节点为空，直接返回空列表ifnotroot:return[]stack=[]res=[]whilerootorstack:whileroot:# 当前节点入栈stack.append(root)# 如果当前节点有左子树，继续向左子树找ifroot.left:root=root.left# 如果当前节点无左子树，在右子树继续找else:root=root.right# 跳出循环的条件是 root 为空，那当前栈顶元素为叶子节点。# 弹出栈顶元素，并加入结果数组cur=stack.pop()res.append(cur.val)# 如果栈不为空，且当前栈顶元素的左节点是刚刚跳出的栈顶元素 cur# 则转向遍历右子树当前栈顶元素的右子树ifstackandstack[-1].left==cur:root=stack[-1].right# 否则证明当前栈顶元素无左右子树，那当前的栈顶元素弹出。else:root=Nonereturnres

问题6：

问题链接：

146. LRU 缓存

问题描述：

请你设计并实现一个满足LRU(最近最少使用)缓存 约束的数据结构。 实现 LRUCache 类：LRUCache(int capacity)以 正整数 作为容量 capacity 初始化 LRU 缓存 intget(int key)如果关键字 key 存在于缓存中，则返回关键字的值，否则返回-1。 voidput(int key,int value)如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以O(1)的平均时间复杂度运行。

实例：

示例： 输入["LRUCache","put","put","get","put","get","put","get","get","get"][[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]输出[null,null,null,1,null,-1,null,-1,3,4]解释 LRUCache lRUCache=newLRUCache(2);lRUCache.put(1,1);//缓存是{1=1}lRUCache.put(2,2);//缓存是{1=1,2=2}lRUCache.get(1);//返回1lRUCache.put(3,3);//该操作会使得关键字2作废，缓存是{1=1,3=3}lRUCache.get(2);//返回-1(未找到)lRUCache.put(4,4);//该操作会使得关键字1作废，缓存是{4=4,3=3}lRUCache.get(1);//返回-1(未找到)lRUCache.get(3);//返回3lRUCache.get(4);//返回4

代码：

classNode:# 提高访问属性的速度，并节省内存__slots__='prev','next','key','value'def__init__(self,key=0,value=0):self.key=key self.value=valueclassLRUCache:def__init__(self,capacity:int):self.capacity=capacity self.dummy=Node()# 哨兵节点self.dummy.prev=self.dummy self.dummy.next=self.dummy self.key_to_node={}# 获取 key 对应的节点，同时把该节点移到链表头部defget_node(self,key:int)->Optional[Node]:ifkeynotinself.key_to_node:# 没有这本书returnNonenode=self.key_to_node[key]# 有这本书self.remove(node)# 把这本书抽出来self.push_front(node)# 放在最上面returnnodedefget(self,key:int)->int:node=self.get_node(key)# get_node 会把对应节点移到链表头部returnnode.valueifnodeelse-1defput(self,key:int,value:int)->None:node=self.get_node(key)# get_node 会把对应节点移到链表头部ifnode:# 有这本书node.value=value# 更新 valuereturnself.key_to_node[key]=node=Node(key,value)# 新书self.push_front(node)# 放在最上面iflen(self.key_to_node)>self.capacity:# 书太多了back_node=self.dummy.prevdelself.key_to_node[back_node.key]self.remove(back_node)# 去掉最后一本书# 删除一个节点（抽出一本书）defremove(self,x:Node)->None:x.prev.next=x.nextx.next.prev=x.prev# 在链表头添加一个节点（把一本书放在最上面）defpush_front(self,x:Node)->None:x.prev=self.dummy x.next=self.dummy.nextx.prev.next=x x.next.prev=x# Your LRUCache object will be instantiated and called as such:# obj = LRUCache(capacity)# param_1 = obj.get(key)# obj.put(key,value)

问题7：

问题链接：

147. 对链表进行插入排序

问题描述：

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。 插入排序 算法的步骤:插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 重复直到所有输入数据插入完为止。 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。 对链表进行插入排序。

实例：

代码：

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:definsertionSortList(self,head:Optional[ListNode])->Optional[ListNode]:#1.转为列表ifnothead:returnNonenode=head res=[]whilenode:res.append(node.val)node=node.nextres.sort()node=headforiinrange(len(res)):node.val=res[i]node=node.nextreturnhead

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:definsertionSortList(self,head:Optional[ListNode])->Optional[ListNode]:#2.借助虚拟节点dummy=ListNode(0)pre=dummy cur=headwhilecur:#把下一个节点保存下来tmp=cur.nextwhilepre.nextandpre.next.val<cur.val:pre=pre.nextcur.next=pre.nextpre.next=cur pre=dummy cur=tmpreturndummy.next

问题8：

问题链接：

148. 排序链表

问题描述：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

实例：

代码：

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:# 876. 链表的中间结点（快慢指针）defmiddleNode(self,head:Optional[ListNode])->Optional[ListNode]:slow=fast=headwhilefastandfast.next:pre=slow# 记录 slow 的前一个节点slow=slow.nextfast=fast.next.nextpre.next=None# 断开 slow 的前一个节点和 slow 的连接returnslow# 21. 合并两个有序链表（双指针）defmergeTwoLists(self,list1:Optional[ListNode],list2:Optional[ListNode])->Optional[ListNode]:cur=dummy=ListNode()# 用哨兵节点简化代码逻辑whilelist1andlist2:iflist1.val<list2.val:cur.next=list1# 把 list1 加到新链表中list1=list1.nextelse:# 注：相等的情况加哪个节点都是可以的cur.next=list2# 把 list2 加到新链表中list2=list2.nextcur=cur.nextcur.next=list1iflist1elselist2# 拼接剩余链表returndummy.nextdefsortList(self,head:Optional[ListNode])->Optional[ListNode]:# 如果链表为空或者只有一个节点，无需排序ifheadisNoneorhead.nextisNone:returnhead# 找到中间节点 head2，并断开 head2 与其前一个节点的连接# 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]head2=self.middleNode(head)# 分治head=self.sortList(head)head2=self.sortList(head2)# 合并returnself.mergeTwoLists(head,head2)

问题9：

问题链接：

149. 直线上最多的点数

问题描述：

给你一个数组 points ，其中 points[i]=[xi,yi]表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

实例：

代码：

classSolution:defmaxPoints(self,points:List[List[int]])->int:ans=0fori,(x,y)inenumerate(points):# 假设直线一定经过 points[i]cnt=defaultdict(int)forx2,y2inpoints[i+1:]:dx,dy=x2-x,y2-y k=dy/dxifdxelseinf cnt[k]+=1ans=max(ans,cnt[k])# 这里没有算上 (x,y) 这个点，最后再加一returnans+1

问题10：

问题链接：

150. 逆波兰表达式求值

问题描述：

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意： 有效的算符为'+'、'-'、'*'和'/'。 每个操作数（运算对象）都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用32位 整数表示。

实例：

示例1： 输入：tokens=["2","1","+","3","*"]输出：9解释：该算式转化为常见的中缀算术表达式为：((2+1)*3)=9示例2： 输入：tokens=["4","13","5","/","+"]输出：6解释：该算式转化为常见的中缀算术表达式为：(4+(13/5))=6示例3： 输入：tokens=["10","6","9","3","+","-11","*","/","*","17","+","5","+"]输出：22解释：该算式转化为常见的中缀算术表达式为：((10*(6/((9+3)*-11)))+17)+5=((10*(6/(12*-11)))+17)+5=((10*(6/-132))+17)+5=((10*0)+17)+5=(0+17)+5=17+5=22

代码：

classSolution:defevalRPN(self,tokens:List[str])->int:st=[]fortokenintokens:iflen(token)>1ortoken[0].isdigit():# token 是数字st.append(int(token))continuex=st.pop()iftoken=='+':st[-1]+=xeliftoken=='-':st[-1]-=xeliftoken=='*':st[-1]*=xelse:# 题目要求除法向零取整，但 // 是向下取整st[-1]=trunc(st[-1]/x)returnst[0]