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

【初阶数据结构】复杂度算法题篇

旋转数组

力扣原题
在这里插入图片描述


方案一

循环K次将数组所有元素向后移动⼀位(代码不通过)

时间复杂度O(n2)
空间复杂度O(1)

void rotate(int* nums, int numsSize, int k) {while (k--) {int end = nums[numsSize - 1];for (int i = numsSize - 1; i > 0; i--) {nums[i] = nums[i - 1];}nums[0] = end;}
}

在这里插入图片描述

  • 时间复杂度过高,需要优化

方案二

申请新数组空间,先将后k个数据放到新数组中,再将剩下的数据挪到新数组中

时间复杂度O(n)
空间复杂度O(n)

void rotate(int* nums, int numsSize, int k) {int newArr[numsSize];for (int i = 0; i < numsSize; ++i) {newArr[(i + k) % numsSize] = nums[i];}for (int i = 0; i < numsSize; ++i) {nums[i] = newArr[i];}
}
  • 记得最后要把新数组数据复制到原数组
  • 时间复杂度降低了,可以通过
  • 空间复杂度提升,仍可以优化

方案三

数组翻转

该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 kmodn 个元素会移动至数组头部,其余元素向后移动 kmodn 个位置。

我们可以先将所有元素翻转,这样尾部的 kmodn 个元素就被移至数组头部,然后我们再翻转 [0,kmodn−1] 区间的元素和 [kmodn,n−1] 区间的元素即能得到最后的答案

时间复杂度:O(n)
空间复杂度:O(1)

在这里插入图片描述

void reverse(int* nums, int begin, int end) {while (begin < end) {int tmp = nums[begin];nums[begin] = nums[end];nums[end] = tmp;begin++;end--;}
}
void rotate(int* nums, int numsSize, int k) {k = k % numsSize;reverse(nums, 0, numsSize - k - 1);reverse(nums, numsSize - k, numsSize - 1);reverse(nums, 0, numsSize - 1);
}

相关文章:

【初阶数据结构】复杂度算法题篇

旋转数组 力扣原题 方案一 循环K次将数组所有元素向后移动⼀位&#xff08;代码不通过) 时间复杂度O(n2) 空间复杂度O(1) void rotate(int* nums, int numsSize, int k) {while (k--) {int end nums[numsSize - 1];for (int i numsSize - 1; i > 0; i--) {nums[i] num…...

20240725项目的maven环境报红-重新配置maven

1.在编辑器里面打开项目&#xff0c;导入源码 &#xff08;1&#xff09;找到项目的地址C:\Users\zzz\IdeaProjects\datasys&#xff0c;然后右击用idea编辑器打开。 &#xff08;2&#xff09;idea中上菜单栏打开open&#xff0c;然后输入file&#xff0c;选择源代码文件 2.…...

若依 ruoyi poi Excel合并行的导入

本文仅针对文字相关的合并做了处理 &#xff0c;图片合并及保存需要另做处理&#xff01;&#xff01; 目标&#xff1a;Excel合并行内容的导入 结果&#xff1a; 1. ExcelUtil.java 类&#xff0c;新增方法&#xff1a;判断是否是合并行 /*** 新增 合并行相关代码&#xff1a;…...

优化算法:1.遗传算法(GA)及Python实现

一、定义 遗传算法就像是在模拟“优胜劣汰”的进化过程&#xff0c;通过选择最优秀的个体&#xff0c;交配产生下一代&#xff0c;并引入一定的变异&#xff0c;逐步优化解决问题。 二、具体步骤 初始化种群(Initialization)&#xff1a; 假设你要找到一个迷宫的最佳出口路径。…...

企业化运维(8)Docker容器技术

###1.Docker介绍### 什么是Docker Docker 是一个开源的应用容器引擎&#xff0c;让开发者可以打包他们的应用以及依赖包到一个可移植的镜像中&#xff0c;然后发布到任何流行的 Linux或Windows 机器上&#xff0c;也可以实现虚拟化。容器是完全使用沙箱机制&#xff0c;相互之间…...

Unity C#底层原理(二)

委托 方法的容器&#xff1a;委托可以存储一个或多个方法的引用。可以使用委托对象来调用这些方法。函数/方法的变量类型&#xff1a;委托类型可以像变量一样声明和使用&#xff0c;存储方法的引用。存储、传递方法&#xff1a;委托可以作为参数传递给方法&#xff0c;也可以作…...

计算机网络-配置路由器ACL(访问控制列表)

配置访问控制列表ACL 拓扑结构 拓扑结构如下&#xff1a; 要配置一个ACL&#xff0c;禁止PC0访问PC3&#xff0c;禁止PC4访问PC0&#xff0c;其它正常。 配置Router0 配置接口IP地址&#xff1a; interface fastethernet 0/0 ip address 192.168.1.1 255.255.255.0 no shu…...

51单片机嵌入式开发:20、STC89C52R基于C51嵌入式点阵广告屏的设计

STC89C52R基于C51嵌入式点阵广告屏的设计 1 概述2 LED点阵介绍2.1 特点和优势2.2 工作原理&#xff1a;2.3 使用方法&#xff1a; 3 LED点阵原理3.1 Led点阵内部电路3.2 原理图电路3.3 74HC595 4 软件实现点阵图案的滑动4.1 软件工程代码4.2 Protues仿真 5 总结 配套示例程序 1…...

VLC输出NDI媒体流

目录 1. 下载安装VLC Play 2. 首先在电脑上安装NDI Tools 3. 运行VLC进行输出配置 4. 播放视频 5. 验证 (1)用Studio Monitor验证 (2)用OBS验证 NDI(Network Device Interface)即网络设备接口,是由美国 NewTek 公司开发的免费标准,它可使兼容的视频产品以高质量…...

WiFi 局域网通信 - 发现服务和解析

1. nsdManager nsdManager requireContext().getSystemService(Context.NSD_SERVICE) as NsdManager2. NsdManager.DiscoveryListener 注意&#xff1a;在onStartDiscoveryFailed 和 onStopDiscoveryFailed里不要调用nsdManager.stopServiceDiscovery(this) 方法&#xff0…...

ChatGPT建议前端学习计划

HTML&CSS基础 - 学习HTML标签、CSS属性、页面布局等基础知识 JavaScript基础 - 学习变量、数据类型、控制流、函数等基础知识 jQuery - 学习如何使用jQuery处理文档对象模型&#xff08;DOM&#xff09;、事件、动画等 Ajax - 全称为 Asynchronous JavaScript and XML&…...

YOLO5项目目录最强解析

YOLO5项目目录解析 YOLOv5 项目目录下的文件和目录的结构&#xff0c;以下是对每个目录和文件的解释&#xff1a; 目录 &#x1f4c1; .github: 存放 GitHub 相关配置和文件&#xff0c;如 GitHub Actions 工作流文件、Issue 模板等&#xff0c;用于自动化构建和持续集成等功…...

【python】sklearn基础教程及示例

【python】sklearn基础教程及示例 Scikit-learn&#xff08;简称sklearn&#xff09;是一个非常流行的Python机器学习库&#xff0c;提供了许多常用的机器学习算法和工具。以下是一个基础教程的概述&#xff1a; 1. 安装scikit-learn 首先&#xff0c;确保你已经安装了Python和…...

Linux:传输层(2) -- TCP协议(2)

目录 1. 流量控制 2. 滑动窗口 3. 拥塞控制 4. 延迟应答 5. 捎带应答 6. 面向字节流 7. 粘包问题 8. TCP异常情况 1. 流量控制 接收端处理数据的速度是有限的. 如果发送端发的太快 , 导致接收端的缓冲区被打满 , 这个时候如果发送端继续发送 , 就会造成丢包, 继而引…...

AcWing 802. 区间和

var说明add存储了插入操作&#xff0c;在指定 x x x下标所在位置 a [ x ] c a[x]c a[x]cquery是求 [ L , R ] [L,R] [L,R]区间和用到的数组,最后才用到alls 是存储离散化之后的值 , 对于会访问到的每个下标&#xff0c;统统丢到 a l l s 里面 &#xff0c;会把 x 和 [ L , R …...

实验2-2-1 温度转换

#include<stdio.h> #include <math.h> int main(){int c,f150;c5*(f-32)/9;printf("fahr 150, celsius %d",c); }...

Spark实时(六):Output Sinks案例演示

文章目录 Output Sinks案例演示 一、​​​​​​​File sink 二、​​​​​​​​​​​​​​Memory Sink 三、​​​​​​​​​​​​​​Foreach Sink 1、​​​​​​​foreachBatch 2、​​​​​​​​​​​​​​foreach Output Sinks案例演示 当我们对流式…...

在SQL编程中DROP、DELETE和TRUNCATE的区别

在SQL编程中&#xff0c;DROP、DELETE和TRUNCATE都是用于删除数据的命令&#xff0c;但它们之间有着显著的区别&#xff0c;主要体现在它们删除数据的范围、操作的不可逆性、对表结构的影响、性能以及事务日志的影响上。 DROP: 作用&#xff1a;DROP命令用于删除整个表及其所有…...

【AI大模型】Prompt 提示词工程使用详解

目录 一、前言 二、Prompt 提示词工程介绍 2.1 Prompt提示词工程是什么 2.1.1 Prompt 构成要素 2.2 Prompt 提示词工程有什么作用 2.2.1 Prompt 提示词工程使用场景 2.3 为什么要学习Prompt 提示词工程 三、Prompt 提示词工程元素构成与操作实践 3.1 前置准备 3.2 Pro…...

学习记录day18——数据结构 算法

算法的相关概念 程序 数据结构 算法 算法是程序设计的灵魂&#xff0c;结构式程序设计的肉体 算法&#xff1a;计算机解决问题的方法护额步骤 算法的特性 1、确定性&#xff1a;算法中每一条语句都有确定的含义&#xff0c;不能模棱两可 2、有穷性&#xff1a;程序执行一…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...