当前位置: 首页 > news >正文

Python算法题集_排序链表

 Python算法题集_排序链表

  • 题148:排序链表
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【冒泡大法】
    • 2) 改进版一【列表排序】
    • 3) 改进版二【数值归并排序】
    • 4) 改进版三【快慢指针归并排序】
  • 4. 最优算法

本文为Python算法题集之一的代码示例

题148:排序链表

1. 示例说明

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

    示例 1:

    img

    输入:head = [4,2,1,3]
    输出:[1,2,3,4]
    

    示例 2:

    img

    输入:head = [-1,5,3,4,0]
    输出:[-1,0,3,4,5]
    

    示例 3:

    输入:head = []
    输出:[]
    

    提示:

    • 链表中节点的数目在范围 [0, 5 * 104]
    • -105 <= Node.val <= 105

    **进阶:**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?


2. 题目解析

- 题意分解

  1. 本题为对链表进行排序
  2. 基本的解法是双层循环冒泡法,所以基本的时间算法复杂度为O(n^2)

- 优化思路

  1. 通常优化:减少循环层次

  2. 通常优化:增加分支,减少计算集

  3. 通常优化:采用内置算法来提升计算速度

  4. 分析题目特点,分析最优解

    1. 链表的排序算法极为耗时

    2. 可以采用归并法对链表进行拆分然后合并

    3. 可以用列表排序法进行简单排序


- 测量工具

  • 本地化测试说明:LeetCode网站测试运行时数据波动很大,因此需要本地化测试解决这个问题
  • CheckFuncPerf(本地化函数用时和内存占用测试模块)已上传到CSDN,地址:Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成,详见【最优算法章节】

3. 代码展开

1) 标准求解【冒泡大法】

链表双层,每次循环将一个最大值移到尾部,毫无意外的超时

无法通关,果然超时在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_base(head):if not head:return headif not head.next:return headbexchange = Truetmphead = ListNode(-1)tmphead.next = headtmpNode = tmpheadwhile bexchange and tmpNode:bexchange = FalsestartNode = tmpNodewhile startNode:if startNode.next:nextnode = startNode.nextif startNode.next.next:nextnode2 = nextnode.nextif nextnode.val > nextnode2.val:tmpNext = nextnode2.nextstartNode.next = nextnode2nextnode2.next = nextnodenextnode.next = tmpNextbexchange = TruestartNode = startNode.nextreturn tmphead.nextresult = cfp.getTimeMemoryStr(Solution.sortList_base, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果【链表长度1W】
函数 sortList_base 的运行时间为 20534.61 ms;内存使用量为 4.00 KB 执行结果 = 1

2) 改进版一【列表排序】

将链表存入列表结构,通过列表排序,最后再连接起来,性能优异,内存O(n)

性能卓越,超越96%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_ext1(head):if not head:return headif not head.next:return headlist_node = []while head:list_node.append([head.val, head])head = head.nextsort_list = sorted(list_node, key=lambda x: x[0])for iIdx in range(len(sort_list)-1):sort_list[iIdx][1].next = sort_list[iIdx+1][1]sort_list[-1][1].next = Nonereturn sort_list[0][1]result = cfp.getTimeMemoryStr(Solution.sortList_ext1, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果【链表长度1W】
函数 sortList_ext1 的运行时间为 2.99 ms;内存使用量为 16.00 KB 执行结果 = 1

3) 改进版二【数值归并排序】

使用递归设计,用值定位将链表拆分排序;递归的最大层次为990,因此链表长度在2^990次方内都不会溢出

不值一提,超过06%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_ext2(head):if not head:return headmin_val = max_val = head.valcurnode = headwhile curnode:min_val = min(min_val, curnode.val)max_val = max(max_val, curnode.val)curnode = curnode.nextif min_val == max_val:return headmid_val = (min_val + max_val) // 2head1 = ListNode(0) last1 = head1 head2 = ListNode(0) last2 = head2 curnode = headwhile curnode:if curnode.val <= mid_val:last1.next = curnodelast1 = last1.next else:last2.next = curnodelast2 = last2.nextcurnode = curnode.next last1.next = Nonelast2.next = None head1 = Solution.sortList_ext2(head1.next) head2 = Solution.sortList_ext2(head2.next)curnode = head1while curnode.next:curnode = curnode.nextcurnode.next = head2return head1result = cfp.getTimeMemoryStr(Solution.sortList_ext2, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 sortList_ext2 的运行时间为 71.03 ms;内存使用量为 0.00 KB 执行结果 = 1

4) 改进版三【快慢指针归并排序】

使用递归设计,用快慢指针将链表拆分排序;递归的最大层次为990,因此链表长度在2^990次方内都不会溢出

马马虎虎,超越72%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:@staticmethoddef sortList_ext3(head):if not head or not head.next:return headslownode, fastnode = head, head.nextwhile fastnode and fastnode.next:fastnode, slownode = fastnode.next.next, slownode.nextmidnode, slownode.next = slownode.next, None leftlink, rightlink = Solution.sortList_ext3(head), Solution.sortList_ext3(midnode)tmpnode = headnode = ListNode(0)while leftlink and rightlink:if leftlink.val < rightlink.val:tmpnode.next, leftlink = leftlink, leftlink.nextelse:tmpnode.next, rightlink = rightlink, rightlink.nexttmpnode = tmpnode.nexttmpnode.next = leftlink if leftlink else rightlinkreturn headnode.nextresult = cfp.getTimeMemoryStr(Solution.sortList_ext3, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 sortList_ext3 的运行时间为 19.02 ms;内存使用量为 0.00 KB 执行结果 = 1

4. 最优算法

根据本地日志分析,最优算法为第2种sortList_ext1,如果内存要O(1)的话,则最优算法为第4种sortList_ext3

iLen = 10000
nums = [iLen - x for x in range(iLen)]
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.sortList_base, ahead)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 算法本地速度实测比较
函数 sortList_base 的运行时间为 20534.61 ms;内存使用量为 4.00 KB 执行结果 = 1
函数 sortList_ext1 的运行时间为 2.99 ms;内存使用量为 16.00 KB 执行结果 = 1
函数 sortList_ext2 的运行时间为 71.03 ms;内存使用量为 0.00 KB 执行结果 = 1
函数 sortList_ext3 的运行时间为 19.02 ms;内存使用量为 0.00 KB 执行结果 = 1

一日练,一日功,一日不练十日空

may the odds be ever in your favor ~

相关文章:

Python算法题集_排序链表

Python算法题集_排序链表 题148&#xff1a;排序链表1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【冒泡大法】2) 改进版一【列表排序】3) 改进版二【数值归并排序】4) 改进版三【快慢指针归并排序】 4. 最优算法 本文为Python算法题集之一的…...

红日靶场2学习

靶场下载来自&#xff1a; http://vulnstack.qiyuanxuetang.net/vuln/detail/3/ 靶场统一登录密码&#xff1a;1qazWSX 按大佬的说法是 环境需要模拟内网和外网两个网段&#xff0c;PC端虚拟机相当于网关服务器&#xff0c;所以需要两张网卡&#xff0c;一个用来向外网提供web…...

将 下载下来的 jar 包 安装到本地的 maven 仓库中

使用管理员权限 打开一个 cmd 窗口输入 mvn -v 查看 maven 版本由于之前 并没有这样的操作所以第一次 执行的时候 提示 命令不存在所以需要将 maven 软件中的 bin 文件的目录 添加到 环境变量中 的 path 变量 中本机路径为:D:\Program Files (x86)\apache-maven-3.5.2\bin C:\…...

Qt初使用(使用Qt创建项目,在创建的项目中添加类,Qt中输出内容到控制台,设置窗口大小和窗口标题,Qt查看说明文档)

目录 一.创建带模板的项目新建项目运行在文件中查看该项目文件 二.在创建好的项目中添加类三.创建空项目&#xff08;不使用自带的模板&#xff09;四.Qt中输出内容到控制台五.设置窗口大小 , 窗口标题 ,固定窗口大小QWidget组件的说明 六.Pro文件帮助文档 按windows键&#xf…...

【黑马程序员】C++运算符重载

文章目录 运算符重载加号运算符重载成员函数实现运算符重载全局函数实现运算符重载全局函数实现函数重载 左移运算符重载递增运算符重载赋值运算符重载关系运算符重载函数调用运算符重载 运算符重载 对已有的运算符重新进行定义&#xff0c;赋予其另一种功能&#xff0c;以适应…...

Java中的乐观锁和悲观锁

使用场景及用法 悲观锁 总是假设最坏的情况&#xff0c;每次去拿数据的时候都认为别人会修改&#xff0c;所以每次在拿数据的时候都会上锁&#xff0c;这样别人想拿这个数据就会阻塞直到它拿到锁&#xff08;共享资源每次只给一个线程使用&#xff0c;其它线程阻塞&#xff0c;…...

从Unity到Three.js(计时器、Transform)

计时器、模型对象平移函数、枚举定义的使用 对应unity中的一些常用功能 import * as THREE from three;const scene new THREE.Scene(); const camera new THREE.PerspectiveCamera(60, window.innerWidth / window.innerHeight, 0.1, 1000);const renderer new THREE.WebG…...

红日靶场(初学)

按照以前的来说一般是有两层网络的内网和外网 这个也是这样的 所以需要两张网卡&#xff0c;一个用来向外网提供web服务&#xff0c;一个是通向内网 以下就是配置 以下就是一些相关信息 外网网段是写成了192.168.111.1/24 WEB PC DC kali 开始扫描 nmap -sS -sV -Pn -T4 19…...

【PyTorch】改变张量(Tensor)形状操作

PyTorch深度学习总结 第二章 PyTorch中改变张量(Tensor)形状操作 文章目录 PyTorch深度学习总结一、前言二、改变张量形状 一、前言 上文讲解了张量生成和信息获取的知识&#xff0c;本文将针对张量的操作进行详细讲解。 二、改变张量形状 1、改变张量形状的函数总结&#x…...

《金融人工智能:用python实现ai量化交易》

融合了数学、python、深度学习以及金融知识&#xff0c;是本推荐的好书。请收藏本文&#xff0c;读后再给大学总结。...

位运算+leetcode ( 2 )

题一&#xff1a;只出现一次的数字&#xff08;1&#xff09; 1.链接 136. 只出现一次的数字 - 力扣&#xff08;LeetCode&#xff09; 2.思想 借用位运算中异或操作符的特点&#xff0c;a^a0&#xff0c;0^aa先定义一个sum0就用一个循环来遍历这个数组&#xff0c;每次都进行…...

17 ABCD数码管显示与动态扫描原理

1. 驱动八位数码管循环点亮 1.1 数码管结构图 数码管有两种结构&#xff0c;共阴极和共阳极&#xff0c;ACX720板上的是共阳极数码管&#xff0c;低电平点亮。 1.2 三位数码管等效电路图 为了节约I/O接口&#xff0c;各个数码管的各段发光管被连在一起&#xff0c;通过sel端…...

【Zigbee课程设计系列文章】Zigbee开发环境搭建

【Zigbee课程设计系列文章】Zigbee开发环境搭建 前言IAR 下载安装Z-Stack协议栈安装 &#x1f38a;项目专栏&#xff1a;【Zigbee课程设计系列文章】&#xff08;附详细使用教程完整代码原理图完整课设报告&#xff09; 前言 &#x1f451;由于无线传感器网络&#xff08;也即…...

[Linux开发工具]项目自动化构建工具-make/Makefile

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 目录 1.背景2.依赖关系和依…...

PLC_博图系列☞参数实例

PLC_博图系列☞参数实例 文章目录 PLC_博图系列☞参数实例背景介绍参数实例参数实例的工作原理创建参数实例将实例作为参数传送 关键字&#xff1a; PLC、 西门子、 博图、 Siemens 、 参数实例 背景介绍 这是一篇关于PLC编程的文章&#xff0c;特别是关于西门子的博图软件…...

LLaMA 2 和 QianWen-14B

阿里云通义千问14B模型开源&#xff01;性能超越Llama2等同等尺寸模型 - 科技新闻 - EDA365电子论坛网 LLaMA 2 的硬件要求&#xff1a; LLaMA 2 系列模型有不同的参数量版本&#xff0c;如7B、13B和70B等。对于不同大小的模型&#xff0c;其硬件需求也有所不同。以下是一些硬…...

浅谈Java常见设计模式及实例

前言 Java 中常用的设计模式有很多种&#xff0c;其实平常用到的还比较少&#xff0c;但是还是有必要了解一下&#xff0c;可以按照实际情况运用到我们的代码中。按照类型可以基本分解为&#xff0c;创建型模式、结构型模式和行为型模式。 创建型模式 (Creational Patterns) 1…...

【RISC-V DSP设计】基于CEVA DSP架构的指令集分析(一)-总体介绍

目录 一、引言 二、CEVA-BX1™ DSP Library 概述 三、CEVA-BX1™ DSP Library 功能与特点 四、CEVA-BX1™ DSP Library 优势 今天开始我们继续对CEVA DSP的架构和指令集进行分析&#xff0c;基于对CEVA DSP的分析和了解&#xff0c;后续可以进行基于RISC-V内核架构的DSP指令…...

Rust标量类型详解

在Rust中&#xff0c;数据类型分为标量类型和复合类型。本篇博客将重点介绍Rust的标量类型&#xff0c;其中包括整数类型、浮点类型、布尔类型以及字符类型。 整数类型 Rust提供了多种整数类型&#xff0c;分为带符号整数和无符号整数。带符号整数表示可以为正数、零或负数&a…...

【双指针】【C++算法】1537. 最大得分

作者推荐 【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目 本文涉及知识点 双指针 LeetCoce 1537. 最大得分 你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。 一条 合法路径 定义如下&#xff1a; 选择数组 nums1 或者 nums2 开始遍历&…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...