了解时间复杂度和空间复杂度
在学习数据结构前,我们需要了解时间复杂度和空间复杂度的概念,这能够帮助我们了解数据结构。
算法效率分为时间效率和空间效率
时间复杂度
一个算法的复杂度与其执行的次数成正比。算法中执行基础操作的次数,为算法的时间复杂度。
我们采用大O的渐进表示法。
推导大O阶方法:
1用常数1取代运行时间中的所有加法常数
2在修改后的运行次数函数中,保留最高阶项。
3如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
有些算法的时间复杂度存在最好、平均和最坏情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)
在实际中一般情况关注的是算法的最坏运行情况
举例:
冒泡排序的时间复杂度
从这个例子我们知道了,不是一层循环时间复杂度就是N,两层就是N^2要看具体算法实现。
二分法时间复杂度分析:
阶乘递归的时间复杂度
空间复杂度
对临时储存空间占用大小的量度。计算的是变量的个数。
首先来看冒泡排序的时间复杂度
循环走了N次,重复利用的是一个空间。
斐波那契数列的空间复杂度:
阶乘的时间复杂度:
算法题
消失的数字
面试题 17.04. 消失的数字 - 力扣(LeetCode)
思路1:
排序,如果后一个数字不等于前一个数字加1,那么前一个数字加1,就是要寻找的消失的数字。
这种方法的时间复杂度是N*lgN
思路2:
把0到N加起来,再减去各个数字,得到的数字就是消失的数字。这里的时间复杂度是O(N)。如果先累加,时间复杂度是0(N),依次遍历一遍为O(N)。
int missingNumber(int* nums, int numsSize){int N=numsSize;int ret=(0+N)*(N+1)/2;for(int i=0;i<numsSize;++i){ret-=nums[i];}return ret;}
思路3:
把数组中的所有数字跟0到N异或,剩下的数字就是消失的数字。(我们知道,x^x=0,0^x=x)
int missingNumber(int* nums, int numsSize){int N=numsSize;int x=0;for(int i=0;i<numsSize;i++){x^=nums[i];//x将包含数组nums中所有元素的异或结果}for(int j=0;j<=N;j++){x^=j;}return x;}
189. 轮转数组 - 力扣(LeetCode)
思路1:旋转k次
void rotate(int* nums, int numsSize, int k) {//首先把最后一个数储存起来for(int i=0;i<k;i++){int tmp=nums[numsSize-1];for(int i=numsSize-2;i>=0;i--){nums[i+1]=nums[i];}nums[0]=tmp;}
}
思路2:三段逆置
前k个逆置
后k个逆置
再整体逆置
void Reverse(int*nums,int left,int right)
{while(left<right){int tmp=nums[left];nums[left]=nums[right];nums[right]=tmp;left++;right--;}
}
void rotate(int* nums, int numsSize, int k)
{if(k>=numsSize){k%=numsSize;}Reverse(nums,numsSize-k,numsSize-1);Reverse(nums,0,numsSize-k-1);Reverse(nums,0,numsSize-1);
}
思路3:
以空间换时间
void _rotate(int*nums,int numsSize,int k,int*tmp)
{k%=numsSize;int n=numsSize;memcpy(tmp,nums+n-k,sizeof(int)*k);//将数组最后 k 个元素复制到 tmp 数组的前 k 个位置memcpy(tmp+k,nums,sizeof(int)*(n-k));//将数组的前 (n-k) 个元素复制到 tmp 数组的剩余位置 memcpy(nums,tmp,sizeof(int)*(n));// // 将 tmp 数组的内容复制回 nums 数组
}
void rotate(int* nums, int numsSize, int k)
{int tmp[numsSize];_rotate(nums,numsSize,k,tmp);
}
相关文章:
了解时间复杂度和空间复杂度
在学习数据结构前,我们需要了解时间复杂度和空间复杂度的概念,这能够帮助我们了解数据结构。 算法效率分为时间效率和空间效率 时间复杂度 一个算法的复杂度与其执行的次数成正比。算法中执行基础操作的次数,为算法的时间复杂度。 我们采…...
[笔试强训]day2
1.牛牛的快递 题目链接:牛牛的快递_牛客题霸_牛客网 思路:分小于1.0kg和大于1.0kg,其中大于1.0kg的要“向上取整” ,eg:1.7->2,2.0->2。注意一个点:第二个输入的参数是字符,要…...
android脱壳第二发:grpc-dumpdex加修复
上一篇我写的dex脱壳,写到银行类型的app的dex修复问题,因为dex中被抽取出来的函数的code_item_off 的偏移所在的内存,不在dex文件范围内,所以需要进行一定的修复,然后就停止了。本来不打算接着搞得,但是写了…...
在 TypeScript 中declare module 关键字用法
在 TypeScript 中,declare module 关键字用于声明模块的类型信息,这种声明通常出现在声明文件(通常是 .d.ts 文件)中。这对于当你需要为现有的 JavaScript 库或模块提供类型信息时非常有用,尤其是对于没有提供自己的类…...
NLP step by step -- 了解Transformer
Transformer模型 Transformer相关历史 首先我们先看一下有关Transformer模型的发展历史,下面的图是基于Transformer架构的一些关键模型节点: 图片来源于Hugging Face 图片来源于Hugging Face Transformer 架构 于 2017 年 6 月推出。原本研究的重点是…...
【Leetcode】vector刷题
🔥个人主页:Quitecoder 🔥专栏:Leetcode刷题 目录 1.只出现一次的数字2.杨辉三角3.删除有序数组中的重复项4.只出现一次的数字II5.只出现一次的数字III6.电话号码的字母组合 1.只出现一次的数字 题目链接:136.只出现一…...
【图解计算机网络】从浏览器地址输入到网页显示的整个过程
从浏览器地址输入到网页显示的整个过程 整体流程DHCPhttp协议报文组装DNSTCP协议封装与TCP三次握手IP协议封装与路由表MAC地址与ARP协议交换机路由器 整体流程 从往浏览器输入一个地址到网页的显示,要经过很长的一个流程,中间涉及到计算机网络的许多知识…...
liqo学习及安装,k8s,kubernetes多集群互联
先按照官方的教程在虚拟机安装学习 在开始以下教程之前,您应该确保您的系统上安装了以下软件: Docker,容器运行时。Kubectl,Kubernetes 的命令行工具。 curl -LO "https://dl.k8s.io/release/$(curl -L -s https://dl.k8s.…...
五种主流数据库:集合运算
关系型数据库中的表与集合理论中的集合类似,表是由行(记录)组成的集合。因此,SQL 支持基于数据行的各种集合运算,包括并集运算(Union)、交集运算(Intersect)和差集运算&a…...
java-springmvc 01
springmvc也是在spring framework中的,不是一个单独的项目 MVC就是和Tomcat有关。 01.MVC启动的第一步,启动Tomcat(这个和springboot的run方法启动Tomcat有关) 02.SpringMVC中,最为核心的就是DispatcherServlet&…...
SecuPress Pro 专业级WordPress网站安全防护插件优化版
下载地址:SecuPress Pro 专业版.zip SecuPress Pro:专业的WordPress安全解决方案 如果您没有时间进行每周扫描,SecuPress Pro将是您的理想选择。SecuPress Pro提供了所有SecuPress Free的功能,同时还增加了一些高级选项ÿ…...
linux 查看nginx日志
在 Linux 系统中,查看 Nginx 日志通常涉及以下几个步骤: 确定日志文件位置:Nginx 的日志文件通常位于 /etc/nginx/logs 或 /var/log/nginx。具体位置取决于您在安装 Nginx 时的配置。 查看访问日志:Nginx 的访问日志默认命名为 a…...
iOS - 多线程-GCD-队列组
文章目录 iOS - 多线程-GCD-队列组1. 队列组1.1 基本使用步骤 iOS - 多线程-GCD-队列组 开发过程中,有时候想实现这样的效果 多个任务并发执行所有任务执行完成后,进行下一步处理(比如回到主线程刷新UI) 1. 队列组 可以使用GC…...
1052. 【NOIP2016备赛】方阵操作(square)
1052. 【NOIP2016备赛】方阵操作(square) (Input: square.in, Output: square.out) 时间限制: 1 s 空间限制: 256 MB 题目描述 小 Z 给你一个 n n 的方阵,要求你完成 Q 次操作: 1. 1 i j k,将 ai,j 修改为 k。 2. 2 i j,交…...
Python打怪升级(4)
在计算机领域常常有说"合法"和"非法"指的是:是否合理,是否有效,并不是指触犯了法律。 random.randint(begin,end) 详细讲解一下这个random是指模板,也就是别人写好的代码直接来用,在Python当中,…...
2024年【危险化学品生产单位安全生产管理人员】考试题库及危险化学品生产单位安全生产管理人员考试报名
题库来源:安全生产模拟考试一点通公众号小程序 危险化学品生产单位安全生产管理人员考试题库参考答案及危险化学品生产单位安全生产管理人员考试试题解析是安全生产模拟考试一点通题库老师及危险化学品生产单位安全生产管理人员操作证已考过的学员汇总,…...
动态IP与静态IP的区别,你选对了吗?
在互联网世界中,IP地址是每台设备在网络上的唯一标识。这些地址可以是动态的,也可以是静态的。对于非专业人士来说,理解这两者之间的区别可能会有些困难。本文旨在深入探讨动态IP和静态IP的主要差异,帮助读者根据自己的需求做出明…...
jasypt组件死锁bug案例分享
事故描述 1、上午9.55发布了一个Apollo动态配置参数; 2、片刻后,服务器接口开始出现大量的超时告警,似乎是某资源被耗尽不足分配; 3、正值业务请求高峰的上午十点(平台上午10点会有一些活动会拉一波用户流量&#x…...
golang上传文件到ftp服务器
之前有个业务需要把文件上传到ftp服务器,写了一个上传ftp的功能 package ftpimport "context"type Client interface {// UploadFile 上传文件UploadFile(ctx context.Context, opt *UploadFileOpt) error }type UploadFileOpt struct {Data […...
数据治理和数据管理 傻傻分不清楚?
互联网时代,数据,这一无形资产,已成为现代企业的核心竞争力。如何高效地管理和利用数据,成为企业关注的焦点。在这个过程中,数据治理(Data Governance)和数据管理(Data Management&a…...
linux磁盘原理
在linux系统中,对磁盘进行管理与windows系统类似,都要先分区,格式化,创建文件系统,挂载目录,数据写入...
react 使用WEB3.0控件开发包 V3.0接入海康威视摄像头
1、下载官方安装包: 2、安装官方插件 3、引入文件 在public/index 中引入监控依赖,这三个文件可以在下载的官方demo中找到 4、react 中使用 useEffect(() > { const ipInfo :[192.168.xxxx];//初始化摄像头const WebVideoCtrl window.WebVideoCtrl…...
数据可视化———Tableau
基本认识: 维度:定性—字符串文本,日期和日期时间等等 度量:定量—连续值,一般属于数值 数据类型: 数值 日期/日期时间 字符串 布尔值 地理值 运算符 算数运算符:加减乘除,%取余,…...
【黑马头条】-day12项目部署和发布-jenkins
文章目录 1 持续集成2 软件开发模式2.1 瀑布模式2.2 敏捷开发2.2.1 迭代开发2.2.2 增量开发 3 Jenkins3.1 Jenkins安装3.1.1 导入镜像3.1.2 配置3.1.3 初始化设置 3.2 插件安装3.3 服务器环境准备3.3.1 Docker安装配置3.3.2 Git安装配置3.3.3 Maven安装配置 3.4 Jenkins工具配置…...
学习操作系统路线
操作系统 简介 本课程为计算机专业学生量身定制,补足计算机操作系统相关知识,查漏补缺,也可用于考研复习。内容包括:操作统概述、进程管理、内存管理、文件管理、输入/输出管理等章节。内容力求精炼、重点突出、条理清晰、深入浅…...
uniapp微信小程序(商城项目)
最近,闲来无事,打算学一下uniapp小程序 于是在跟着某站上学着做了一个小程序,主要是为了学uniapp和vue。某站黑马优购 完成的功能主要有:首页、搜索、分类和购物车。 有人问了为什么没有登录、和添加订单呢?问的很好…...
Linux的自动化脚本:使用crul命令下载文件,实现断点续传
目录 一、要求 二、解决思路 (一)curl工具可以进行文件传输,可以实现手动断点续传 1、使用 --range 选项: 2. 使用 --continue-at 选项: (二)编写shell脚本调用curl命令,实现自…...
Golang | Leetcode Golang题解之第46题全排列
题目: 题解: func permute(nums []int) [][]int {var (n len(nums)dfs func(vals []int) // 已选择数 排列为vals 后续回溯继续选择 直至选完ans [][]int)dfs func(vals []int) {//边界if len(vals) n {ans append(ans, vals)}//转移 枚举选哪个f…...
MySQL数据表记录删操作
删除操作 作用删除表里的记录行(都是整行整行的删除的) 1.单表的删除 语法: delete from 表名 where 要删除的记录筛选条件; 案例:删除员工编号大于203的员工信息 delete from employees where employee_id>203; 2.多表…...
Python浅谈清朝秋海棠叶版图
1、清朝疆域概述: 清朝是我国最后一个封建王朝,其始于1616年建州女真部努尔哈赤建立后金,此后统一女真各部、东北地区。后又降服漠南蒙古,1644年入关打败农民起义军、灭南明,削三藩,复台湾。后又收外蒙&am…...
Linux之线程管理
目录 第1关:创建线程 任务描述 相关知识 使用pthread_create函数创建线程 编程要求 答案: 第2关:线程挂起 任务描述 相关知识 使用pthread_join挂起线程 编程要求 答案: 第3关:线程终止 任务描述 相关知识 使用pthread…...
.net反射(Reflection)
文章目录 一.概念:二.反射的作用:三.代码案例:四.运行结果: 一.概念: .NET 反射(Reflection)是指在运行时动态地检查、访问和修改程序集中的类型、成员和对象的能力。通过反射,你可…...
白平衡简介
文章目录 白平衡的概念白平衡的调节常见的白平衡模式 白平衡的概念 白平衡是指摄影、摄像和显示技术中的一项重要概念,用于调节图像中的白色或中性灰色的色彩,使其看起来在不同光源条件下都是准确的白色或灰色。白平衡的主要目的是确保图像的色彩准确性…...
centos7.9下安装SVN服务
一、安装subversion yum install -y subversion #安装svn mkdir -p /data/svnrepos/java #自定义svn仓库位置/data/svnrepos,自定义一个项目叫svn(这里新建目录) svnadmin create /data/svnrepos/java #创建一…...
iStat Menus for Mac:强大的系统监控工具
iStat Menus for Mac是一款功能强大的系统监控工具,专为Mac用户设计,旨在帮助用户全面了解电脑的运行状态,提高电脑的性能和稳定性。 iStat Menus for Mac v6.73 (1239)中文版下载 该软件可以实时监测CPU使用率、内存占用、网络速度、硬盘活动…...
NumPy 1.26 中文官方指南(四)
附加文件 术语表 原文:numpy.org/doc/1.26/glossary.html (n,) 括号中跟着逗号的数字表示一个具有一个元素的元组。尾随逗号将一个元素元组与括号n区分开。 -1 在维度入口中,指示 NumPy 选择长度,以保持数组元素总数不变。 >>> n…...
Python flask
Flask 是一个用 Python 编写的轻量级 Web 应用框架。它被设计为易于使用和扩展,使其成为构建简单网站到复杂的、动态的 web 应用程序的理想选择。以下是 Flask 的一些基本组件和概念: 主要组件 Flask:框架本身,提供基本的功能来处…...
2-token生成
Token是密码学中的一个概念,可以用作身份验证凭证。在计算机领域中,token可以是一个字符串,用于标识用户的身份和权限。当用户进行身份验证时,他们通常会收到一个token,以便在将来的请求中用作凭证。 在互联网应用程序…...
Flutter 上架如何解决 ITMS-91053 问题
最近,我的 Flutter App 发布到 TestFlight 后,就会收到一封邮件:The uploaded build for YOUR APP has one or more issues. 上面的邮件主要是说,我的 App 缺少了调用 API 的声明,以前从来没看到过,上网一查…...
PgSQL的登录相关(Ubuntu22.04)
一 将用户设为密码登录方式 1 修改用户的密码 sudo -u postgres psql -c "ALTER USER yuhui WITH PASSWORD xinmima;" 2 修改配置,指定用户yuhui使用密码登录 sudo vi /etc/postgresql/16/main/pg_hba.conf local all postgres …...
ThingsBoard处理设备上报的属性并转换为可读属性
一、前言 二、案例 1、AI生成JSON数据体 2、将json数据体直接通过遥测topic发送查看效果 3、可查看目前整个数据都在一起 编辑 4、配置附规则链路 5、对msg的消息值,进行数据的转换,并从新进行赋值。 6、规则链路关联关系 7、再次通过MQTT发送遥…...
03-JAVA设计模式
设计模式GOF23 GOF23是指由设计模式经典名著《Design Patterns: Elements of Reusable Object-Oriented Software》(中译本名为《设计模式——可复用面向对象软件的基础》)的四位作者Erich Gamma、Richard Helm、Ralph Johnson、以及John Vlissides提出…...
Aws Nat Gateway
要点 NAT网关要能访问外网,所以需要部署在有互联网网关的Public子网中。 关键: NAT网关创建是选择子网,一定要选择公有子网(有互联网网关子网) 特别注意: 新建nat网关的时候,选择的子网一定…...
SLICEM是如何将查找表配置为分布式RAM/移位寄存器的
1.首先说SliceM和SliceL如何配置为ROM的 一个SLICE包含4个六输入查找表,因此每个查找表就能存储64bit的数据,要实现128bit的ROM,只需要通过两个LUT就可实现,具体如下表: 2.如何配置成为分布式RAM SLICEM中的LUT如下图ÿ…...
Echarts-知识图谱
Echarts-知识图谱 demo地址 打开CodePen 效果 思路 1. 生成根节点 2. 根据子节点距离与根节点的角度关系,生成子节点坐标,进而生成子节点 3. 从子节点上按角度生成对应的子节点 4. 递归将根节点与每一层级子节点连线核心代码 定义节点配置 functio…...
Scala 05 —— 函数式编程底层逻辑
Scala 05 —— 函数式编程底层逻辑 该文章来自2023/1/14的清华大学交叉信息学院助理教授——袁洋演讲。 文章目录 Scala 05 —— 函数式编程底层逻辑函数式编程假如...副作用是必须的?函数的定义函数是数据的函数,不是数字的函数如何把业务逻辑做成纯函…...
在 Node.js 中配置代理 IP 采集文章
不说废话,直接上代码: const http require(http); const https require(https);// 之后可以使用 http 或 https 模块发起请求,它们将自动使用配置的代理 // 代理ip:https://www.kuaidaili.com/?refrg3jlsko0ymg const proxy …...
ESLlint重大更新后,使用旧版ESLint搭配Prettier的配置方式
概要 就在前几天,ESLint迎来了一次重大更新,9.0.0版本,根据官方文档介绍,使用新版的先决条件是Node.js版本必须是18.18.0、20.9.0,或者是>21.1.0的版本,新版ESLint将不再直接支持以下旧版配置(非扁平化…...
springcloud Ribbon的详解
1、Ribbon是什么 Ribbon是Netflix发布的开源项目,Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端负载均衡的框架。 2、Ribbon能干什么 LB负载均衡(Load Balance)是什么?简单的说就是将用户的请求平摊的分配到多个服务上,从而达…...
超级好用的C++实用库之Des加解密
概述 DES(Data Encryption Standard,数据加密标准)是一种历史悠久的对称密钥加密算法,由IBM公司在1970年代设计,并于1977年被美国国家标准局选作联邦资料处理标准。DES使用56位密钥对64位的数据块进行操作,…...
数据结构:线性表(详解)
线性表 线性表的知识框架: 线性表的定义: 线性表是具有相同数据类型的n(n > 0)个数据元素的有限序列,当n 0时线性表为一个空表。 若用L命名为线性表,则数据集合为L {a1,a2,…,an},其中a1称为表头元素,…...
2024年第七届可再生能源与环境工程国际会议(REEE 2024)即将召开!
2024年第七届可再生能源与环境工程国际会议(REEE 2024)将于2024 年8月28-30日在法国南特举行。共绘绿色未来,全球同频共振!REEE 2024将汇聚全球可再生能源与环境工程领域的专家学者和业界精英,共同探讨行业发展的前沿技…...
八股spring+springboot+springMVC+Mybatis(一)
目录 1、面试官:Spring框架中的单例bean是线程安全的吗? 2、面试官:什么是AOP 3、面试官:你们项目中有没有使用到AOP 4、面试官:Spring中的事务是如何实现的 5、面试官:Spring中事务失效的场景有哪些 6、面…...
Ansible的安装与基础命令的使用
Ansible Ansible 是一个开源的自动化工具,用于配置管理、应用部署和任务自动化。它由 Michael DeHaan 于 2012 年创建,后来被 Red Hat 收购。Ansible 的设计理念是简单易用,不需要在受管节点上安装任何代理软件,它通过 SSH&#…...
Content-Type详解
...
snRNA-seq vs scRNA-seq谁更nice,用数据说话
snRNA、scRNA傻傻分不清的时候,人家已经开始择优了,如今的单细胞有当年高通量测序之势,势不可挡,不得不用~小编就带大家看一下这篇2023年发表于《Plant Science》的文章。 植物单细胞RNA测序(scRNA-seq)技术…...
“40法则”视角下的海外网络安全公司
2015 年知名投资人Brad Feld在他的博客中分享一篇名为《The Rule of 40% For a Healthy SaaS Company》的文章,提出了在评价海外企业软件和互联网公司财务状况时广泛使用的“Rule of 40”。“40法则”仅仅包含两个简单的参数:收入增长率和净利润率&#…...
JAVA入门2
前言: 不一样的编程——基于两个大前提,语言随便选一个,作者选java和c,在后续的内容会有c和java的共同使用 第一大前提:编程语言起源于语言 第二大前提:计算机理解不了语言的含义 这两大前提构成了不一样的…...
一键自动化博客发布工具,用过的人都说好(oschina篇)
oschina和segmentfault一样,界面非常的清爽。 界面上除了必须的标题,内容之外,还有文章专辑和推广专区这几个选项。 一起来看看在blog-auto-publishing-tools中,是如何实现自动发布到oschina的吧。 前提条件 前提条件当然是先下载 blog-a…...
搭建Docker私有镜像仓库
大家好,今天给大家分享一下如何搭建私有镜像仓库,私有镜像仓库可以更好地管理和控制镜像的访问和使用,确保只有授权的人员能够获取和使用特定的镜像,而且方便团队内部共享定制化的镜像,提高开发和部署效率,…...
geoserver-OSGEarth-GIS
linux安装geoserver 如何利用GeoServer发布卫星地图服务_geoserver发布卫星图服务-CSDN博客 GeoServer的安装(Windows)与初步使用 - 知乎 Geoserver简介-CSDN博客 GeoServer的安装(Windows)与初步使用 - 知乎 https://www.cnblog…...
Moby简介:openEuler 中的开源docker引擎
Moby 是一个开源的容器化引擎,它提供了创建和管理容器所需的核心功能。在 openEuler 系统中,Moby 作为容器技术的实现之一,它允许用户利用容器化技术来部署、运行和移植应用程序。 Moby 的功能和作用: 1. **容器创建**ÿ…...