网站怎么做导航条,企业邮箱注册哪个好,昆明网站建设手机版,家居公司网站建设方案pptPython算法题集_两两交换链表中的节点 题24#xff1a;两两交换链表中的节点1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【四节点法】2) 改进版一【列表操作】3) 改进版二【三指针法】4) 改进版三【递归大法】 4. 最优算法 本文为Python算法… Python算法题集_两两交换链表中的节点 题24两两交换链表中的节点1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【四节点法】2) 改进版一【列表操作】3) 改进版二【三指针法】4) 改进版三【递归大法】 4. 最优算法 本文为Python算法题集之一的代码示例
题24两两交换链表中的节点
1. 示例说明 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 示例 1 输入head [1,2,3,4]
输出[2,1,4,3]示例 2 输入head []
输出[]示例 3 输入head [1]
输出[1]提示 链表中节点的数目在范围 [0, 100] 内0 Node.val 100 2. 题目解析
- 题意分解
本题为两两交换链表中间的节点本题的主要计算是2块1是链表遍历2是节点链接调整基本的解法是单层循环链表1读一遍过程中执行节点链接调整所以基本的时间算法复杂度为O(m
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 标准方法是一次循环4个节点中第2个节点链接第1个第1个节点连接第3个或者第4个【如果第4个存在】 可以用列表结构进行节点调整列表结构简单方便维护 可以用三指针方式一次循环完成 此问题可以用嵌套思路使用递归法 - 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大因此需要本地化测试解决这个问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题很难超时本地化超时测试用例自己生成详见【最优算法章节】 3. 代码展开
1) 标准求解【四节点法】
一次遍历检查4个节点完成节点链接调整
出类拔萃超过85%
import CheckFuncPerf as cfpclass Solution:staticmethoddef swapPairs_base(head):if not head:return headif not head.next:return headtmpNode1, tmpNode2 head, head.nexthead tmpNode2while tmpNode1 and tmpNode2:tmpNode11 tmpNode2.nexttmpNode12 NonetmpNode1.next tmpNode2.nexttmpNode2.next tmpNode1if tmpNode11:tmpNode12 tmpNode11.nextif tmpNode12:tmpNode1.next tmpNode12tmpNode1 tmpNode11tmpNode2 tmpNode12return headresult cfp.getTimeMemoryStr(Solution.swapPairs_base, ahead)
print(result[msg], 执行结果 {}.format(result[result].val))# 运行结果
函数 swapPairs_base 的运行时间为 18.01 ms内存使用量为 4.00 KB 执行结果 12) 改进版一【列表操作】
将链表转换为数组再完成节点链接调整
马马虎虎超过69%
import CheckFuncPerf as cfpclass Solution:staticmethoddef swapPairs_ext1(head):if not head:return headif not head.next:return headlist_node []while head:list_node.append(head)head head.nextiLen len(list_node)for iIdx in range(len(list_node) // 2):if iIdx * 2 2 iLen:continuelist_node[iIdx*21].next list_node[iIdx*2]if iIdx * 2 3 iLen:list_node[iIdx * 2].next Noneelif iIdx * 2 4 iLen:list_node[iIdx * 2].next list_node[iIdx * 2 2]else:list_node[iIdx * 2].next list_node[iIdx * 2 3]return list_node[1]result cfp.getTimeMemoryStr(Solution.swapPairs_ext1, ahead)
print(result[msg], 执行结果 {}.format(result[result].val))# 运行结果
函数 swapPairs_ext1 的运行时间为 109.04 ms内存使用量为 76.00 KB 执行结果 13) 改进版二【三指针法】
使用三指针结构遍历链表完成节点链接调整
出类拔萃超过85%
import CheckFuncPerf as cfpclass Solution:staticmethoddef swapPairs_ext2(head):dummyhead ListNode(0)dummyhead.next headnodepre dummyheadnodeslow dummyhead.nextif not nodeslow:return dummyhead.nextnodefast nodeslow.nextwhile nodefast:nodeslow.next nodefast.nextnodefast.next nodeslownodepre.next nodefastnodepre nodeslownodeslow nodeslow.nextif not nodeslow:breaknodefast nodeslow.nextreturn dummyhead.nextresult cfp.getTimeMemoryStr(Solution.swapPairs_ext2, ahead)
print(result[msg], 执行结果 {}.format(result[result].val))# 运行结果
函数 swapPairs_ext2 的运行时间为 17.00 ms内存使用量为 0.00 KB 执行结果 14) 改进版三【递归大法】
采用递归方式遍历链表完成节点链接调整
出神入化超过96%
import CheckFuncPerf as cfpclass Solution:staticmethoddef swapPairs_ext3(head):def swapnodepair(head):nodeleft headif not nodeleft:return headnoderight nodeleft.nextif not noderight:return headnodeleft.next swapnodepair(noderight.next)noderight.next nodeleftreturn noderightreturn swapnodepair(head)result cfp.getTimeMemoryStr(Solution.swapPairs_ext3, ahead)
print(result[msg], 执行结果 {}.format(result[result].val))# 运行结果
Traceback (most recent call last):......
[Previous line repeated 991 more times]
RecursionError: maximum recursion depth exceeded4. 最优算法
根据本地日志分析最优算法为第3种swapPairs_ext2
nums [ x for x in range(200000)]
def generateOneLinkedList(data):head ListNode()current_node headfor num in data:new_node ListNode(num)current_node.next new_nodecurrent_node new_nodereturn head.next
ahead generateOneLinkedList(nums)
result cfp.getTimeMemoryStr(Solution.swapPairs_base, ahead)
print(result[msg], 执行结果 {}.format(result[result].val))# 算法本地速度实测比较
函数 swapPairs_base 的运行时间为 18.01 ms内存使用量为 4.00 KB 执行结果 1
函数 swapPairs_ext1 的运行时间为 109.04 ms内存使用量为 76.00 KB 执行结果 1
函数 swapPairs_ext2 的运行时间为 17.00 ms内存使用量为 0.00 KB 执行结果 1
Traceback (most recent call last): # 递归法swapPairs_ext3超时......[Previous line repeated 991 more times]
RecursionError: maximum recursion depth exceeded一日练一日功一日不练十日空
may the odds be ever in your favor ~
