黄骅市住房和城乡建设局网站,网速,屏显的企业网站应该怎么做,网站设计 线框图Leetcode随机抽题检测 160 相交链表未看解答自己编写的青春版重点题解的代码206 反转链表 一段用于复制的标题未看解答自己编写的青春版重点题解的代码日后再次复习重新写 234 回文链表未看解答自己编写的青春版重点综上#xff0c;利用快慢指针找寻链表中间#xff0c;就按加… Leetcode随机抽题检测 160 相交链表未看解答自己编写的青春版重点题解的代码206 反转链表 一段用于复制的标题未看解答自己编写的青春版重点题解的代码日后再次复习重新写 234 回文链表未看解答自己编写的青春版重点综上利用快慢指针找寻链表中间就按加入虚拟头的方法写。 题解的代码日后再次复习重新写 141 环形链表未看解答自己编写的青春版重点题解的代码日后再次复习重新写 142 环形链表 II未看解答自己编写的青春版重点题解的代码日后再次复习重新写 21 合并两个有序链表未看解答自己编写的青春版重点题解的代码日后再次复习重新写 2 两数相加未看解答自己编写的青春版重点题解的代码日后再次复习重新写 19 删除链表的倒数第 N 个结点未看解答自己编写的青春版重点上面的代码其实有些冗余了这道题只要能想到加入虚拟头上面说的两种特殊情况都能迎刃而解用一般的示例来考虑就能通过。卡哥的代码中是先让 fast 移动 n1 步我的是先移动 n 步都可以不同的对用体现在while判断条件上。 题解的代码日后再次复习重新写 24 两两交换链表中的节点未看解答自己编写的青春版重点题解的代码日后再次复习重新写 25 K 个一组翻转链表未看解答自己编写的青春版重点上面那个评论的方法真厉害我悟了第一次接触这种方式来翻转链表的但是出人意料的很适合这道题之前做的反转链表的方法不能直接用到本题上想使用就要像我那样去写去谨慎的赋值。这种翻转的思想是一次交换两个节点且保持 pre 不变。例如0--1--2--3--4pre在0处不参与翻转cur在1处。那么第一次操作是0--2--1--3--4此时pre还在0cur也还在1继续0--3--2--1--4继续0--4--3--2--1它是每次都将后面的一个值插入到pre的后面pre不移动cur也不移动但是cur的相对位置会随着链表的更改而移动。 题解的代码日后再次复习重新写 138 复制带随机指针的链表未看解答自己编写的青春版重点通过对上面两种方法的学习发现了这道题的本质就是在利用next建立新链表的时候利用一个map保存好原节点和新节点的对应关系就好了本质上是考哈希另一种非常牛的方法随机指针复制拆分这题太牛了一定要着重复习后面这种思想第一次接触。 题解的代码日后再次复习重新写 148 排序链表未看解答自己编写的青春版重点这道题太重要了太重要了一定要多次复习。归并排序是对链表排序最好的方法一定要好好学习归并排序这是可以作为模板代码来学习的本质上就是两个操作,merge 和 cut 。从网上搜到的很多归并排序都是用递归写的不过本题使用循环来写觉得这种写法很值得学习归并排序的递归和循环写法都值得学习快速排序版本是交换节点的并非只交换数值。暂时没看 题解的代码日后再次复习重新写 23 合并 K 个升序链表未看解答自己编写的青春版重点题解的代码日后再次复习重新写 146 LRU 缓存未看解答自己编写的青春版重点这道双向链表的题目真的学习了后面一定要多复习多重写这道题 题解的代码日后再次复习重新写 94 二叉树的中序遍历未看解答自己编写的青春版重点题解的代码日后再次复习重新写 104 二叉树的最大深度未看解答自己编写的青春版重点题解的代码日后再次复习重新写 226 翻转二叉树未看解答自己编写的青春版重点题解的代码日后再次复习重新写 101 对称二叉树未看解答自己编写的青春版重点题解的代码日后再次复习重新写 543 二叉树的直径未看解答自己编写的青春版重点题解的代码日后再次复习重新写 102 二叉树的层序遍历未看解答自己编写的青春版重点题解的代码日后再次复习重新写 108 将有序数组转换为二叉搜索树未看解答自己编写的青春版重点题解的代码日后再次复习重新写 98 验证二叉搜索树未看解答自己编写的青春版重点题解的代码日后再次复习重新写 230 二叉搜索树中第K小的元素未看解答自己编写的青春版重点题解的代码日后再次复习重新写 199 二叉树的右视图未看解答自己编写的青春版重点题解的代码日后再次复习重新写 一段用于复制的标题未看解答自己编写的青春版重点额外空间复杂度为O(1)的思想这道题我被题目骗了题目说顺序应该是前序遍历我就想着递归必须用前序遍历但是前序遍历的问题是会提前修改掉后面要进入递归的值。那么链表从上到下连接可以我从下到上反向连接也可以啊而这一点利用递归的回溯特性可以很自然地做到。假如 last 承载了下一层递归的返回值而本层递归的root为last的上一个只需要赋值root.rightlast就可以了所以后序遍历后序遍历也就不会有还未进入递归值就被修改的问题这题的思路太妙了思路很妙可以多写多复习。 题解的代码日后再次复习重新写 105 从前序与中序遍历序列构造二叉树未看解答自己编写的青春版厉害第一次自己尝试写出了传入左右索引版的代码在空间占用上要比上面的代码低不少。 重点题解的代码日后再次复习重新写 437 路径总和 III未看解答自己编写的青春版重点没来得及体会日后再看重点学习这道题。 题解的代码日后再次复习重新写 236 二叉树的最近公共祖先未看解答自己编写的青春版重点题解的代码日后再次复习重新写 124 二叉树中的最大路径和未看解答自己编写的青春版重点题解的代码日后再次复习重新写 160 相交链表
未看解答自己编写的青春版
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]:curA headAcurB headBcountA 0countB 0while curA :countA 1curA curA.nextwhile curB :countB 1curB curB.nextif countA countB :countA,countB countB,countAheadA,headB headB,headAdiff countA - countBwhile diff 0 :headA headA.nextdiff - 1while headA :if headA headB :return headBelse :headA headA.nextheadB headB.nextreturn None
重点
过。
题解的代码
206 反转链表
一段用于复制的标题
未看解答自己编写的青春版
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:pre Nonecur headwhile cur :temp cur.nextcur.next prepre curcur tempreturn pre重点
过。
题解的代码
日后再次复习重新写
234 回文链表
未看解答自己编写的青春版
class Solution:def isPalindrome(self, head: Optional[ListNode]) - bool:dummy_head ListNode(0,head)slow fast dummy_head# 这里要注意快慢指针找中间要加虚拟头才是对的不加虚拟头不对# 自己举例一下就发现了。while fast and fast.next :slow slow.nextfast fast.next.nextcur slow.nextslow.next Nonepre Nonewhile cur :temp cur.nextcur.next prepre curcur tempwhile pre and head :if pre.val ! head.val :return Falsepre pre.nexthead head.nextreturn True
重点
通过编写这道题的代码发现了一个很重要的点如果要用快慢指针法寻找链表中点最严格的方式是要加入虚拟头
加入虚拟头的代码 dummy_head ListNode(0,head)slow fast dummy_headwhile fast and fast.next :slow slow.nextfast fast.next.nextcur slow.nextslow.next None # 切断操作不加入虚拟头的代码 slow fast headwhile fast and fast.next :slow slow.nextfast fast.next.nextcur slow.nextslow.next None # 切断操作下面用A代表慢指针B代表快指针。
比如1-2-3-4 不加入虚拟头时一开始AB均在 1 移动一步A在2B在3此时还要继续移动while不退出继续移动A在3B为Nonewhile退出此时让A.next None做切断操作这明显是错误的应该是从 2 切断加入虚拟头后就是正确的结果。
加入虚拟头可以让偶数个数的链表切割正确奇数个数的链表切割结果不变因为奇数个数的链表正确切割结果就是左边要包括中间节点然后中间节点的next为None。
那么之前有一道题143 重排链表为什么卡哥的代码也是快慢指针找中间却没有加入虚拟头 143 重排链表 卡哥的代码
class Solution:def reorderList(self, head: Optional[ListNode]) - None:Do not return anything, modify head in-place instead.fast slow head# find mid point which including (first) mid point into the first half linked listwhile fast and fast.next:fast fast.next.nextslow slow.next# 下面两句代码别忘了一个是取右半边这样取的右半边一定是短的那一方# 这样连接也符合题目要求right slow.next # 获取后半边的头slow.next None # 切断这句话很重要不然就成环了node Nonewhile right:temp right.nextright.next nodenode rightright temphead2 nodehead1 headwhile head1 and head2:temp1 head1.nexttemp2 head2.nexthead1.next head2head2.next temp1head1 temp1head2 temp2 因为这道题目的特殊性可以看出从2处切割本题的节点串联逻辑是1 – 4 – 2 – 3 。从3处切割本题的节点串联逻辑是1 – 4 – ( 2 3 ) ( 2 3 ) 本来就在左子串中无需改变位置这是这道题的特殊性对于偶数个数的链表中间两个点切不切割都一样因为这两个点的顺序不需要颠倒。
综上利用快慢指针找寻链表中间就按加入虚拟头的方法写。
题解的代码
日后再次复习重新写
141 环形链表
未看解答自己编写的青春版
class Solution:def hasCycle(self, head: Optional[ListNode]) - bool:if head None or head.next None :return Falseslow fast headwhile fast and fast.next : slow slow.nextfast fast.next.next# 注意判断的位置先移动再判断不然因为初始化都是头结点会立刻返回Trueif slow fast :return Truereturn False重点
在使用快慢指针时注意 if 逻辑判断的位置。
注意注意警告警告上面代码中的提前判断不是必须的。可以不加。
class Solution:def hasCycle(self, head: Optional[ListNode]) - bool:slow fast headwhile fast and fast.next : slow slow.nextfast fast.next.next# 注意判断的位置先移动再判断不然因为初始化都是头结点会立刻返回Trueif slow fast :return Truereturn False题解的代码
日后再次复习重新写
142 环形链表 II
未看解答自己编写的青春版
class Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:slow headfast headwhile fast and fast.next :slow slow.nextfast fast.next.nextif slow fast :cur headwhile True :if cur slow :return curcur cur.nextslow slow.nextreturn None重点
过这道题的理论基础去复习卡哥的解答。
环形链表 II
题解的代码
日后再次复习重新写
21 合并两个有序链表
未看解答自己编写的青春版
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) - Optional[ListNode]:newhead ListNode()res newheadwhile list1 and list2 :if list1.val list2.val :newhead.next list2list2 list2.next else :newhead.next list1list1 list1.nextnewhead newhead.nextif list1 None and list2 ! None :newhead.next list2elif list1 ! None and list2 None :newhead.next list1return res.next重点
过。
题解的代码
日后再次复习重新写
2 两数相加
未看解答自己编写的青春版
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:reshead ListNode()cur resheadpre 0while l1 or l2 :if l1 None :temp prel2.valif temp 9 :pre 1temp temp % 10else :pre 0node ListNode(temp)l2 l2.nextelif l2 None :temp prel1.valif temp 9 :pre 1temp temp % 10else :pre 0node ListNode(temp)l1 l1.nextelse :temp prel2.vall1.valif temp 9 :pre 1temp temp % 10else :pre 0node ListNode(temp)l1 l1.nextl2 l2.nextcur.next nodecur cur.nextif pre 1 :node ListNode(1)cur.next nodereturn reshead.next重点
过。
题解的代码
日后再次复习重新写
19 删除链表的倒数第 N 个结点
未看解答自己编写的青春版
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:dummy_head ListNode(0,head)slow fast dummy_headwhile n 0 :fast fast.nextn - 1while fast and fast.next :fast fast.nextslow slow.nextslow.next slow.next.nextreturn dummy_head.next重点
这道题就明确两点
1、加入虚拟头。
2、模拟特殊情况检验代码是否正确删除的是最后一个节点删除的是第一个节点。
上面的代码其实有些冗余了这道题只要能想到加入虚拟头上面说的两种特殊情况都能迎刃而解用一般的示例来考虑就能通过。卡哥的代码中是先让 fast 移动 n1 步我的是先移动 n 步都可以不同的对用体现在while判断条件上。
移动 n1 步
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:dummy_head ListNode(0,head)slow fast dummy_headwhile n -1 :fast fast.nextn - 1while fast :fast fast.nextslow slow.nextslow.next slow.next.nextreturn dummy_head.next移动 n 步
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:dummy_head ListNode(0,head)slow fast dummy_headwhile n 0 :fast fast.nextn - 1while fast.next :fast fast.nextslow slow.nextslow.next slow.next.nextreturn dummy_head.next题解的代码
日后再次复习重新写
24 两两交换链表中的节点
未看解答自己编写的青春版
class Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:if head None or head.next None :return headdummy_head ListNode(0,head)pre dummy_headcur headwhile cur and cur.next :temp1 cur.nexttemp2 cur.next.nextpre.next temp1temp1.next curcur.next temp2pre curcur cur.nextreturn dummy_head.next重点
理清楚while循环中的交换逻辑就好逻辑弄不清楚就多搞一个临时变量嘛两个temp逻辑不就非常清晰。
这道题为了交换方便同样也需要用虚拟头。
题解的代码
日后再次复习重新写
25 K 个一组翻转链表
未看解答自己编写的青春版
哈哈哈独立完成 hard 题 不过看评论很多人也做出来了看来这道题很简单也就是中等的实际难度。
耗时上也还行40% 左右。
class Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]:dummy_head ListNode(0,head)pre dummy_headbegin end dummy_head.nextcount 1while end :if count k :end end.nextcount 1else :temp end.nexta,b self.reverse(begin,end)pre.next bpre aa.next tempbegin end tempcount 1return dummy_head.nextdef reverse(self,head,end):end.next Nonepre Nonecur headwhile cur :temp cur.nextcur.next prepre curcur tempreturn head,end重点
评论中的一个解答
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy new ListNode(0), prev dummy, curr head, temp;dummy.next head;int length 0;while(head ! null) {length;head head.next;}head dummy.next;for(int i 0; i length / k; i) {for(int j 0; j k - 1; j) {temp curr.next;curr.next temp.next;temp.next prev.next;prev.next temp;}prev curr;curr prev.next;}return dummy.next;}
}上面那个评论的方法真厉害我悟了第一次接触这种方式来翻转链表的但是出人意料的很适合这道题之前做的反转链表的方法不能直接用到本题上想使用就要像我那样去写去谨慎的赋值。这种翻转的思想是一次交换两个节点且保持 pre 不变。例如0–1–2–3–4pre在0处不参与翻转cur在1处。那么第一次操作是0–2–1–3–4此时pre还在0cur也还在1继续0–3–2–1–4继续0–4–3–2–1它是每次都将后面的一个值插入到pre的后面pre不移动cur也不移动但是cur的相对位置会随着链表的更改而移动。
想清楚节点的移动逻辑再谨慎地编写每次循环中的逻辑就可以了。
class Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]:dummy_head ListNode(0,head)pre dummy_headcur dummy_head.nextaa dummy_head.nextcount 0while aa :count 1aa aa.nextfor i in range(count//k):for j in range(k-1):# 这里的四个赋值顺序非常有讲究temp cur.nextcur.next temp.nexttemp.next pre.nextpre.next temppre curcur cur.nextreturn dummy_head.next题解的代码
日后再次复习重新写
138 复制带随机指针的链表
未看解答自己编写的青春版
思想很朴素每次都从头搜索random节点所以耗时也只打败了6%。去学习一下评论区。
class Solution:def copyRandomList(self, head: Optional[Node]) - Optional[Node]:reshead Node(0)copycur resheadcur headwhile cur :node Node(cur.val)copycur.next nodecopycur copycur.nextcur cur.nextcopycur reshead.nextcur headwhile cur :if cur.random None :copycur.random None else :temp_org headtemp_copy reshead.nextwhile temp_org ! cur.random :temp_org temp_org.nexttemp_copy temp_copy.nextcopycur.random temp_copycur cur.nextcopycur copycur.nextreturn reshead.next重点
评论中的一个递归的解法很有意思。当然这种方法相当于记录了该链表的所有节点空间复杂度是O(n)虽然是递归但是这道题的时间复杂度也是O(n)。
class Solution:def copyRandomList(self, head):def copyNode(node, res):if not node: return Noneif node in res: return res[node]copy Node(node.val, None, None)res[node] copycopy.next copyNode(node.next, res)copy.random copyNode(node.random, res)return copyreturn copyNode(head, {})
另一种解法哈希利用字典去记录原节点和新节点的映射关系。使用hash存储原结点和克隆结点的映射关系通过映射关系处理克隆结点的random指针。
时间复杂度和空间复杂度均为O(n)
class Solution {public Node copyRandomList(Node head) {if(head null){return head;}// map方法空间复杂度O(n)Node node head;// 使用hash表存储旧结点和新结点的映射MapNode,Node map new HashMap();while(node ! null){Node clone new Node(node.val,null,null);map.put(node,clone);node node.next;}node head;while(node ! null){map.get(node).next map.get(node.next);map.get(node).random map.get(node.random);node node.next;}return map.get(head);}
}通过对上面两种方法的学习发现了这道题的本质就是在利用next建立新链表的时候利用一个map保存好原节点和新节点的对应关系就好了本质上是考哈希
另一种非常牛的方法随机指针复制拆分
原地处理将克隆结点放在原结点后面在原链表上处理克隆结点的random指针最后分离两个链表空间复杂度O(1)。
class Solution {public Node copyRandomList(Node head) {if(head null){return head;}// 空间复杂度O(1)将克隆结点放在原结点后面Node node head;// 1-2-3 1-1-2-2-3-3while(node ! null){Node clone new Node(node.val,node.next,null);Node temp node.next;node.next clone;node temp;}// 处理random指针node head;while(node ! null){// node.next.random node.random null ? null : node.random.next;node node.next.next;}// 还原原始链表即分离原链表和克隆链表node head;Node cloneHead head.next;while(node.next ! null){Node temp node.next;node.next node.next.next;node temp;}return cloneHead;}
}一篇有助于理解的题解链接
清楚的题解
这题太牛了一定要着重复习后面这种思想第一次接触。
题解的代码
日后再次复习重新写
哈希方法复写
class Solution:def copyRandomList(self, head):reshead Node(0)copycur resheadcur headtable {}while cur :node Node(cur.val)copycur.next nodecopycur copycur.nexttable[cur] copycurcur cur.nextcopycur reshead.nextcur headwhile cur :if cur.random None :copycur.random None else :copycur.random table[cur.random]cur cur.nextcopycur copycur.nextreturn reshead.next
148 排序链表
未看解答自己编写的青春版
先遍历得到数组再排序用一个字典存储数组排序后的下标(key)和链表中的节点(value)的映射然后按照key从小到大去索引原节点来构造新链表。这是时间复杂度为O(n logn)空间复杂度为O(n)的做法。
速度很快打败95%但是空间上只打败了6%
class Solution:def sortList(self, head: Optional[ListNode]) - Optional[ListNode]:table {}nums []cur headwhile cur :# 处理值相同的情况if cur.val in table :# 这里要直接 append, 不能采用赋值操作table[cur.val] table[cur.val].append(cur)# 因为 table[cur.val].append(cur) 的返回值是None# 下面的 pop 操作同理table[cur.val].append(cur)else :table[cur.val] [cur]nums.append(cur.val)cur cur.nextnums.sort()reshead ListNode()cur resheadfor i in nums:# 注意这里要从最末尾开始取因为pop就是丢掉末尾的node table[i][-1] table[i].pop()cur.next nodecur cur.nextcur.next Nonereturn reshead.next要使用O(1)的空间复杂度必然是对链表直接进行排序操作对链表的排序还从来没写过采用哪种方式好也不清楚冒泡肯定不行是O(n^2)看题解说是归并排序归并排序是最适合链表这种数据结构的排序方式。快速排序也可以。
重点这道题太重要了太重要了一定要多次复习。
归并排序是对链表排序最好的方法 伪代码
current dummy.next;
tail dummy;
for (step 1; step length; step * 2) {while (current) {// left-------nullleft current;// left---null right-----nullright cut(current, step); // 将 current 切掉前 step 个头切下来。// left---null right---null current---nullcurrent cut(right, step); // 将 right 切掉前 step 个头切下来。// dummy.next - ----null最后一个节点是 tail始终记录// ^// tailtail.next merge(left, right);while (tail-next) tail tail-next; // 保持 tail 为尾部}
}正式代码好像是C
class Solution {
public:ListNode* sortList(ListNode* head) {ListNode dummyHead(0);dummyHead.next head;auto p head;int length 0;while (p) {length;p p-next;}for (int size 1; size length; size 1) {auto cur dummyHead.next;auto tail dummyHead;while (cur) {auto left cur;auto right cut(left, size); // left-- right---...cur cut(right, size); // left-- right-- cur--...tail-next merge(left, right);while (tail-next) {tail tail-next;}}}return dummyHead.next;}ListNode* cut(ListNode* head, int n) {auto p head;while (--n p) {p p-next;}if (!p) return nullptr;auto next p-next;p-next nullptr;return next;}ListNode* merge(ListNode* l1, ListNode* l2) {ListNode dummyHead(0);auto p dummyHead;while (l1 l2) {if (l1-val l2-val) {p-next l1;p l1;l1 l1-next; } else {p-next l2;p l2;l2 l2-next;}}p-next l1 ? l1 : l2;return dummyHead.next;}
};一定要好好学习归并排序这是可以作为模板代码来学习的本质上就是两个操作,merge 和 cut 。从网上搜到的很多归并排序都是用递归写的不过本题使用循环来写觉得这种写法很值得学习
归并排序的递归和循环写法都值得学习
快速排序版本是交换节点的并非只交换数值。暂时没看
class Solution {
public ListNode sortList(ListNode head) {if(headnull||head.nextnull) return head;// 没有条件创造条件。自己添加头节点最后返回时去掉即可。ListNode newHeadnew ListNode(-1);newHead.nexthead;return quickSort(newHead,null);}// 带头结点的链表快速排序private ListNode quickSort(ListNode head,ListNode end){if (headend||head.nextend||head.next.nextend) return head;// 将小于划分点的值存储在临时链表中ListNode tmpHeadnew ListNode(-1);// partition为划分点p为链表指针tp为临时链表指针ListNode partitionhead.next,ppartition,tptmpHead;// 将小于划分点的结点放到临时链表中while (p.next!end){if (p.next.valpartition.val){tp.nextp.next;tptp.next;p.nextp.next.next;}else {pp.next;}}// 合并临时链表和原链表将原链表接到临时链表后面即可tp.nexthead.next;// 将临时链表插回原链表注意是插回不做这一步在对右半部分处理时就断链了head.nexttmpHead.next;quickSort(head,partition);quickSort(partition,end);// 题目要求不带头节点返回结果时去除return head.next;}
}题解的代码
日后再次复习重新写
自己复写的归并排序好好理解
class Solution:def sortList(self, head: Optional[ListNode]) - Optional[ListNode]:dummy_head ListNode(0,head)cur headcount 0while cur :count 1cur cur.nextstep 1while step count :# 这里cur从头结点head开始也是必须的而不能从虚拟头开始cur dummy_head.nextpre dummy_headwhile cur :left curright self.cut(left,step)cur self.cut(right,step)pre.next self.merge(left,right)while pre.next :pre pre.nextstep step 1return dummy_head.nextdef merge(self,head1,head2):dummy_head ListNode()cur dummy_headwhile head1 and head2 :if head1.val head2.val :cur.next head2head2 head2.nextcur cur.nextelse :cur.next head1head1 head1.nextcur cur.nextif head1 None :cur.next head2else :cur.next head1return dummy_head.next# 注意cut操作是返回切断后后半部分的链表头def cut(self,head,n):cur head# 注意这里一定是n1 ,因为left是从头结点head开始的# 那么如果step是1的话指针应该不移动这样才能仅cut掉当前节点while n 1 and cur ! None :cur cur.nextn - 1if cur None :return Noneres cur.next# cut 操作要在最后结尾处截断赋值为 Nonecur.next Nonereturn res
23 合并 K 个升序链表
未看解答自己编写的青春版
有了上一题的铺垫这道题就显得较为简单了但是效率高不高就不清楚了。倒序归并排序执行 n-1 次因为是每次合并两个然后 pop 出这两个然后将结果 append 进去。
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]:n len(lists) if lists []:return Nonetemp lists[0]while len(lists) 1 :head1 lists[-1]head2 lists[-2]temp self.merge(head1,head2)lists.pop()lists.pop()lists.append(temp)return tempdef merge(self,head1,head2):dummy_head ListNode()cur dummy_headwhile head1 and head2 :if head1.val head2.val :cur.next head2head2 head2.nextcur cur.nextelse :cur.next head1head1 head1.nextcur cur.nextif head1 None :cur.next head2else :cur.next head1return dummy_head.next重点
这题的评论区里一堆妖魔鬼怪的方法作为初学者的我就找一个最朴素的思路吧分治法。
可以学习一下直接没怎么接触过
其实就是递归只不过之前的递归在获得 L1 和 L2 处要收获结果了都是一个类似于加和append的操作本题变成了一个两个链表的merge函数。
class Solution:def mergeKLists(self, lists: List[ListNode]) - ListNode:n len(lists)def merge(left, right):if left right:returnif left right:return lists[left]mid (left right) // 2l1 merge(left, mid)l2 merge(mid 1, right)return mergeTwoLists(l1, l2)def mergeTwoLists(l1, l2):if not l1 or not l2:return l1 or l2if l1.val l2.val:l1.next mergeTwoLists(l1.next, l2)return l1else:l2.next mergeTwoLists(l1, l2.next)return l2return merge(0, n - 1)题解的代码
日后再次复习重新写
分治法复写将原本代码中归并两个有序链表的 mergeTwoLists 函数的递归写法改为了一般的循环写法这样看上去就更好理解一些了本质上就是递归
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]:n len(lists)def merge(left, right):if left right:returnif left right:return lists[left]mid (left right) // 2l1 merge(left, mid)l2 merge(mid 1, right)return self.mergeTwoLists(l1, l2)return merge(0, n - 1)def mergeTwoLists(self,head1,head2):dummy_head ListNode()cur dummy_headwhile head1 and head2 :if head1.val head2.val :cur.next head2head2 head2.nextcur cur.nextelse :cur.next head1head1 head1.nextcur cur.nextif head1 None :cur.next head2else :cur.next head1return dummy_head.next146 LRU 缓存
未看解答自己编写的青春版
没见过这种类型的题也不知道应该用什么数据结构。
重点
首先要明确本题的两个要点。
1、LRU 的功能可以使用双向链表实现访问到的节点移动到头部超出容量的从尾部删除。
2、要实现O(1)得使用HaspMap里面储存 key 与 链表节点即可这样可以快速定位节点然后删除它将它移动到链表头部。
这道双向链表的题目真的学习了后面一定要多复习多重写这道题
题解的代码
class ListNode:def __init__(self, keyNone, valueNone):self.key keyself.value valueself.prev Noneself.next Noneclass LRUCache:def __init__(self, capacity: int):self.capacity capacityself.hashmap {}# 新建两个节点 head 和 tailself.head ListNode()self.tail ListNode()# 初始化链表为 head - tailself.head.next self.tailself.tail.prev self.head# 因为get与put操作都可能需要将双向链表中的某个节点移到末尾所以定义一个方法def move_node_to_tail(self, key):# 先将哈希表key指向的节点拎出来为了简洁起名node# hashmap[key] hashmap[key]# | |# V -- V# prev - node - next pre - next ... nodenode self.hashmap[key]node.prev.next node.nextnode.next.prev node.prev# 之后将node插入到尾节点前# hashmap[key] hashmap[key]# | |# V -- V# prev - tail ... node prev - node - tailnode.prev self.tail.prevnode.next self.tailself.tail.prev.next nodeself.tail.prev nodedef get(self, key: int) - int:if key in self.hashmap:# 如果已经在链表中了久把它移到末尾变成最新访问的self.move_node_to_tail(key)res self.hashmap.get(key, -1)if res -1:return reselse:return res.valuedef put(self, key: int, value: int) - None:if key in self.hashmap:# 如果key本身已经在哈希表中了就不需要在链表中加入新的节点# 但是需要更新字典该值对应节点的valueself.hashmap[key].value value# 之后将该节点移到末尾self.move_node_to_tail(key)else:if len(self.hashmap) self.capacity:# 去掉哈希表对应项self.hashmap.pop(self.head.next.key)# 去掉最久没有被访问过的节点即头节点之后的节点self.head.next self.head.next.nextself.head.next.prev self.head# 如果不在的话就插入到尾节点前new ListNode(key, value)self.hashmap[key] newnew.prev self.tail.prevnew.next self.tailself.tail.prev.next newself.tail.prev new
日后再次复习重新写
94 二叉树的中序遍历
未看解答自己编写的青春版
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:if root None :return []left self.inorderTraversal(root.left)middle root.valright self.inorderTraversal(root.right)return left[middle]right
重点
过。本次刷题旨在把题做出来不考虑递归法怎么写迭代法怎么写其他方法有没有这种事情了。
题解的代码
日后再次复习重新写
104 二叉树的最大深度
未看解答自己编写的青春版
class Solution:def maxDepth(self, root: Optional[TreeNode]) - int:if root None :return 0left self.maxDepth(root.left)right self.maxDepth(root.right)return 1 max(left,right)重点
最大深度 根节点的最大高度直接用高度的定义去递归简单
题解的代码
日后再次复习重新写
226 翻转二叉树
未看解答自己编写的青春版
正确可以AC的代码
class Solution:def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]:if root None :return Noneleft self.invertTree(root.left)right self.invertTree(root.right)root.left , root.right right,leftreturn root要引以为戒的错误代码错误原因在未完全递归完成之前就改变了当前正在递归节点的左右子树。
class Solution:def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]:if root None :return Noneroot.left self.invertTree(root.right)# 上一行代码的赋值操作导致改变了root.left下面的递归就不对了root.right self.invertTree(root.left)return root重点
题解的代码
日后再次复习重新写
101 对称二叉树
未看解答自己编写的青春版
这道题没法在原函数上进行递归判断了必须新建一个函数因为对称的判断需要左右两棵子树的头结点。
class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool:if root None :return Truereturn self.judge_symmetric(root.left,root.right)def judge_symmetric(self,left,right):if left None and right None :return Trueelif left None and right ! None :return Falseelif left ! None and right None :return Falseelse :flag1 self.judge_symmetric(left.left,right.right)flag2 self.judge_symmetric(left.right,right.left)if left.val right.val :flag3 Trueelse :flag3 Falsereturn flag1 and flag2 and flag3怎么感觉我这次写的这个代码有点复杂呢。
重点
之前的代码也差不多可以通过更改顺序稍微优化一下。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool:if root None :return Truereturn self.digui(root.left,root.right)def digui(self,p,q):if p None and q None :return Trueelif p None and q ! None :return Falseelif p ! None and q None :return Falseelse :if p.val ! q.val :return Falseelse :left self.digui(p.left,q.right)if left :right self.digui(p.right,q.left)return left and right
题解的代码
日后再次复习重新写
543 二叉树的直径
未看解答自己编写的青春版
嘿嘿无敌。虽然这道题是简单题但是我觉得这道题如何保存最长的路径以及怎么处理每个节点的返回值还蛮需要考虑清楚的。
class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int:if root None :return 0self.res 0self.track_road(root)return self.resdef track_road(self,root):if root None :return 0left self.track_road(root.left)right self.track_road(root.right)self.res max(self.res,leftright)return 1 max(left,right)
重点
我自认为重点有两个
1、最长路径不一定经过根节点比如根节点的左子树很深而且是完全二叉树而根节点的右子树只有一个节点那么最长路径一定出现在左子树中。
2、本题要处理的值和节点的返回值不一致不是像之前做过的题目所求结果就是根节点的返回值在当前节点最长路径是左右子树加起来但是如果要返回到上一层只能选一个max的返回
题解的代码
日后再次复习重新写
102 二叉树的层序遍历
未看解答自己编写的青春版
from collections import deque
class Solution:def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]:if root None :return []dq deque()dq.append(root)res []while dq :size len(dq)level []for i in range(size):node dq.popleft()level.append(node.val)if node.left :dq.append(node.left)if node.right :dq.append(node.right)res.append(level)return res
重点
层序遍历模板题。
题解的代码
日后再次复习重新写
108 将有序数组转换为二叉搜索树
未看解答自己编写的青春版
递归构造就行了。
class Solution:def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]:if nums [] :return Nonen len(nums)mid n // 2node TreeNode(nums[mid])node.left self.sortedArrayToBST(nums[0:mid])node.right self.sortedArrayToBST(nums[mid1:])return node重点
题解的代码
日后再次复习重新写
98 验证二叉搜索树
未看解答自己编写的青春版
中序遍历左中右所有的中间节点处理逻辑都要放在中间。
class Solution:def __init__(self):self.pre Nonedef isValidBST(self, root: Optional[TreeNode]) - bool:if root None :return Trueleft self.isValidBST(root.left)# 中序遍历左中右所有的中间节点处理逻辑都要放在中间if self.pre :if self.pre.val root.val :return False# 这句话一定要放在中间self.pre rootright self.isValidBST(root.right) return left and right赋值语句 ( self.pre root ) 位置错误导致的错误代码
class Solution:def __init__(self):self.pre Nonedef isValidBST(self, root: Optional[TreeNode]) - bool:if root None :return Trueleft self.isValidBST(root.left)# 中序遍历左中右所有的中间节点处理逻辑都要放在中间if self.pre :if self.pre.val root.val :return Falseright self.isValidBST(root.right) self.pre rootreturn left and right中序遍历迭代法
class Solution:def isValidBST(self, root: Optional[TreeNode]) - bool:stack []cur rootpre Nonewhile stack or cur :if cur :stack.append(cur)cur cur.leftelse :node stack.pop()if pre :if pre.val node.val :return Falsepre nodecur node.rightreturn True上面从stack里 pop 出来的值可以直接用 cur 承接更顺眼一些。
class Solution:def isValidBST(self, root: Optional[TreeNode]) - bool:stack []cur rootpre Nonewhile stack or cur :if cur :stack.append(cur)cur cur.leftelse :cur stack.pop()if pre :if pre.val cur.val :return Falsepre curcur cur.rightreturn True重点
题解的代码
日后再次复习重新写
230 二叉搜索树中第K小的元素
未看解答自己编写的青春版
中序遍历的迭代法模板直接秒了但是时间上只打败了7% ?
class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) - int:count 0stack []cur rootwhile stack or cur :if cur :stack.append(cur)cur cur.leftelse :cur stack.pop()count 1if count k:return cur.valcur cur.rightreturn 0重点
从网上看了一些评论也基本上和我的方法一致。
另一种思路通过计算节点个数来找寻第K个数查找左子树节点个数为 leftN , 如果 KleftN ,则所查找节点在左子树上若 KleftN1 , 则所查找节点为根节点若 KleftN1 , 则所查找节点在右子树上, 按照同样方法查找右子树第 K-leftN 个节点。
但是在时间上还是打败 7% 其他解法怎么这么快的
class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) - int:left self.count(root.left)if left 1 k:return root.valelif left k :return self.kthSmallest(root.left,k)else :return self.kthSmallest(root.right,k-left-1)def count(self,root):if root None :return 0return self.count(root.left)self.count(root.right)1题解的代码
力扣的示例代码
class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) - int: res []def dfs(node):if not node:returnif len(res)k:returndfs(node.left)res.append(node.val)dfs(node.right)dfs(root)return res[k-1]原来就是递归储存所有遍历过的节点当结果列表长度大于等于 k 时返回。
看起来因为使用的是递归所以应该是比我的中序遍历迭代法要少遍历一些节点。不过这个代码有时候90%有时候也是7%不纠结这道题的耗时统计了
日后再次复习重新写
199 二叉树的右视图
未看解答自己编写的青春版
又是层序遍历模板题。
from collections import deque
class Solution:def rightSideView(self, root: Optional[TreeNode]) - List[int]:if root None :return []dq deque()dq.append(root)res []while dq :size len(dq)for i in range(size):node dq.popleft()if node.left :dq.append(node.left)if node.right:dq.append(node.right)res.append(node.val)return res
重点
题解的代码
日后再次复习重新写
一段用于复制的标题
未看解答自己编写的青春版
一开始总想着用递归做但是发现在递归中无法时刻保存当前需要赋值的节点因为本题要求不能返回任意值也就是要操作原节点所以递归函数返回值赋值这些操作都是无效的所以应该用前序遍历的迭代法。
class Solution:def flatten(self, root: Optional[TreeNode]) - None:Do not return anything, modify root in-place instead.if root None :return Nonestack [root]cur rootwhile stack :node stack.pop()if node root :passelse :cur.right nodecur.left Nonecur nodeif node.right :stack.append(node.right)if node.left :stack.append(node.left)但是上述是额外空间复杂度为O(n)因为额外申请了一个堆栈。
重点
额外空间复杂度为O(1)的思想这道题我被题目骗了题目说顺序应该是前序遍历我就想着递归必须用前序遍历但是前序遍历的问题是会提前修改掉后面要进入递归的值。那么链表从上到下连接可以我从下到上反向连接也可以啊而这一点利用递归的回溯特性可以很自然地做到。假如 last 承载了下一层递归的返回值而本层递归的root为last的上一个只需要赋值root.rightlast就可以了
所以后序遍历后序遍历也就不会有还未进入递归值就被修改的问题这题的思路太妙了
class Solution:def __init__(self):self.last Nonedef flatten(self, root: Optional[TreeNode]) - None:Do not return anything, modify root in-place instead.if root None :return Noneself.flatten(root.right)self.flatten(root.left)root.right self.lastroot.left Noneself.last root思路很妙可以多写多复习。
题解的代码
日后再次复习重新写
105 从前序与中序遍历序列构造二叉树
未看解答自己编写的青春版
递归数组切片方法
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]:if preorder []:return Nonemiddle preorder[0]index inorder.index(middle)node TreeNode(middle)node.left self.buildTree(preorder[1:index1],inorder[:index])node.right self.buildTree(preorder[index1:],inorder[index1:])return node厉害第一次自己尝试写出了传入左右索引版的代码在空间占用上要比上面的代码低不少。
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]:def build(pleft,pright,ileft,iright):# 左闭右开不包括right所以才能有等于号if pleft pright :return Nonemiddle preorder[pleft]index inorder.index(middle)node TreeNode(middle)# 举例: ileft 3 , middle 4 , 意味着左子树只有一个节点# 那么对于前序数组起始位置 pleft1 , 要想让左子树有一个点区间应该为# [pleft1,pleft2) 注意循环不变量左闭右开node.left build(pleft1,pleft1index-ileft,ileft,index)node.right build(pleft1index-ileft,pright,index1,iright)return noden len(preorder)return build(0,n,0,n)
重点
过。可以体会下传入左右区间的参数的版本怎样能把每个区间都写对。
题解的代码
日后再次复习重新写
437 路径总和 III
未看解答自己编写的青春版
没做出来。
重点
主要是两种方法双重递归 前缀和。
力扣官方题解
没来得及体会日后再看重点学习这道题。
题解的代码
双重递归
class Solution:def pathSum(self, root: TreeNode, targetSum: int) - int:def rootSum(root, targetSum):if root is None:return 0ret 0if root.val targetSum:ret 1ret rootSum(root.left, targetSum - root.val)ret rootSum(root.right, targetSum - root.val)return retif root is None:return 0ret rootSum(root, targetSum)ret self.pathSum(root.left, targetSum)ret self.pathSum(root.right, targetSum)return ret前缀和
class Solution:def pathSum(self, root: TreeNode, targetSum: int) - int:prefix collections.defaultdict(int)prefix[0] 1def dfs(root, curr):if not root:return 0ret 0curr root.valret prefix[curr - targetSum]prefix[curr] 1ret dfs(root.left, curr)ret dfs(root.right, curr)prefix[curr] - 1return retreturn dfs(root, 0)
日后再次复习重新写
236 二叉树的最近公共祖先
未看解答自己编写的青春版
搞懂左右公共祖先怎么从后序遍历中层层回溯到根节点的。
class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode:self.res Noneself.digui(root,p,q)return self.resdef digui(self,root,p,q):if root None :return Falseif root.val p.val or root.val q.val :self.res rootreturn True left self.digui(root.left,p,q)right self.digui(root.right,p,q)if left and right :self.res rootreturn left or right重点
参考卡哥的解答。
二叉树的最近公共祖先
题目拓展如果树是一个二叉搜索树呢前序遍历树中节点的值就可以了当节点值第一次出现在在区间 [ p.val , q.val ] 时这个节点就是最近公共祖先可以用反证法证明再走一步就不符合条件了。
题解的代码
日后再次复习重新写
124 二叉树中的最大路径和
未看解答自己编写的青春版
小小 hard 。
本题只需要考虑清楚对于在当前节点收获结果的逻辑左和右分别都有两个状态取或不取一共四种情况就好了递归函数在返回时同前面做过的一道题返回的时候没有左右都考虑的情况。
class Solution:def maxPathSum(self, root: Optional[TreeNode]) - int:self.res -infself.digui(root)return self.resdef digui(self,root):if root None :return 0if root.left None and root.right None :self.res max(self.res,root.val)return root.valleft self.digui(root.left)right self.digui(root.right)# 只要想明白这里左和右分别都有两个状态取或不取一共四种情况就好了self.res max(self.res,leftrightroot.val,root.val,rightroot.val,leftroot.val)# 同前面做过的一道题返回的时候没有左右都考虑的情况return max(left,right,0)root.val重点
题解的代码
日后再次复习重新写
