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

【数据结构OJ题】轮转数组

原题链接:https://leetcode.cn/problems/rotate-array/

目录

1. 题目描述

2. 思路分析

3. 代码实现


1. 题目描述

2. 思路分析

1. 方法一暴力求解,将数组的第一个元素用临时变量tmp存起来,再将数组其他元素往右挪动一步,挪动k次。

时间复杂度:O(N^2)

空间复杂度:O(1)

2. 方法二空间换时间,用malloc()函数额外开辟一个空间表示tmp[ ]数组。将原数组nums[ ]中的后k个元素拷贝到tmp[ ]数组,作为tmp[ ]数组前k个元素。将原数组的前n-k个元素拷贝到tmp[ ]数组,作为tmp[ ]数组的后n-k个元素。最后再将tmp[ ]数组拷贝回去给原数组nums[ ]。(拷贝的操作我们要使用memcpy()函数)

时间复杂度:O(N)

空间复杂度:O(N)

3. 方法三三次逆置首先将前n-k个元素逆置,将后k个元素逆置,最后将数组整体逆置。

(也可以先将数组整体逆置,然后将数组前k个元素逆置,将后n-k个元素逆置)。

时间复杂度:O(N)

空间复杂度:O(1)

3. 代码实现

因为方法一的时间复杂度太高了,这里就不写出来了。我们在这里实现方法二和方法三的代码。

这里都要注意一个问题,就是k的值有可能大于等于数组长度n,所以我们要做取余操作k%=n来防止越界。

这里先介绍下方法二要用到的内存相关的函数:

malloc函数是用于动态分配内存的函数。malloc函数的作用是在运行时从堆中分配指定大小的内存块,并返回一个指向该内存块的指针。

函数参数size表示需要分配的内存块的大小,以字节为单位。malloc函数返回一个void*类型的指针,指向分配的内存块的起始位置。如果内存分配失败,则返回一个空指针NULL

使用malloc函数可以动态地在程序运行期间申请所需的内存空间来存储数据,而不需要在编译时确定内存大小。分配的内存块可以用于存储各种类型的数据(如整数、字符、数组等)。

 memcpy函数用于在内存之间复制一段数据。memcpy函数将指定大小的数据从源内存区域复制到目标内存区域。memcpy函数返回一个指向目标内存区域的指针。

函数参数:

dest:指向目标内存区域起始位置的指针。

src:指向源内存区域起始位置的指针。

num:需要复制的字节数。

方法二:

void rotate(int* nums, int numsSize, int k) {int n = numsSize;int* tmp = malloc(sizeof(int) * n);  //用malloc()函数开辟一块空间k %= n; //防越界memcpy(tmp, nums + n - k, sizeof(int) * k);  //将nums[]数组的后k个拷贝到tmpmemcpy(tmp + k, nums, sizeof(int) * (n - k));  //将nums[]数组的前n-k个拷贝到tmpmemcpy(nums, tmp, sizeof(int) * n);  //将tmp[]数组拷贝给nums[]free(tmp);tmp = NULL;
}

方法三:

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) {int n = numsSize;k %= n;  //防越界reverse(nums, 0, n - k - 1);  //逆置前n-k个reverse(nums, n - k, n - 1);  //逆置后k个reverse(nums, 0, n - 1); //整体逆置
}

相关文章:

【数据结构OJ题】轮转数组

原题链接&#xff1a;https://leetcode.cn/problems/rotate-array/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 1. 方法一&#xff1a;暴力求解&#xff0c;将数组的第一个元素用临时变量tmp存起来&#xff0c;再将数组其他元素往右挪动一步&…...

现代C++中的从头开始深度学习:【4/8】梯度下降

一、说明 在本系列中&#xff0c;我们将学习如何仅使用普通和现代C编写必须知道的深度学习算法&#xff0c;例如卷积、反向传播、激活函数、优化器、深度神经网络等。 在这个故事中&#xff0c;我们将通过引入梯度下降算法来介绍数据中 2D 卷积核的拟合。我们将使用卷积和上一个…...

Yolov5缺陷检测/目标检测 Jetson nx部署Triton server

使用AI目标检测进行缺陷检测时&#xff0c;部署到Jetson上即小巧算力还高&#xff0c;将训练好的模型转为tensorRT再部署到Jetson 上供http或GRPC调用。1 Jetson nx 刷机 找个ubuntu 系统NVIDIA官网下载安装Jetson 的sdkmanager一步步刷机即可。 本文刷的是JetPack 5.1, 其中包…...

MobaXterm 中文乱码, 及pojie

中文解决方法&#xff1a; 把“连字”去掉&#xff01; MobaXterm网页&#xff0c;可以生成一个授权文件Custom.mxtpro。放在安装目录就可以了 MobaXterm Keygen (husbin.top)http://b70.husbin.top:5000/...

java: 程序包sun.misc不存在

启动失败&#xff0c;rebuild时也报错&#xff1a;java: 程序包sun.misc不存在 问题出在JDK版本上&#xff0c;这个包在JDK9的时候已经被弃用了&#xff0c;这里改回JDK8即可 步骤如下&#xff1a;...

WSL2Linux 子系统(五)

WLS2Linux 子系统编译 Android 上一篇文章中讲解 《WLS2Linux 子系统迁移/恢复》&#xff0c;从C盘迁移到D盘。既可以防止C盘爆红&#xff0c;又可以释放磁盘空间。有更大存储空间意味大有可为&#xff0c;比如说编译Android系统。本文则以开源 firefly Android10代码为例简单…...

java 企业工程管理系统软件源码 自主研发 工程行业适用 em

​ 工程项目管理软件&#xff08;工程项目管理系统&#xff09;对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营&#xff0c;全过程、全方位的对项目进行综合管理 工程项目各模块及其功能点清单 一、系统管理 1、数据字典&#…...

IPO观察丨困于门店扩张的KK集团,还能讲好增长故事吗?

KK集团发起了其IPO之路上的第三次冲击。 近日&#xff0c;KK集团更新了招股书&#xff0c;继续推进港交所上市进程&#xff0c;此前两次上市搁置后终于有了新动向。从更新内容来看&#xff0c;KK集团招股书披露了公司截至2023年一季度的最新业绩&#xff0c;交出一份不错的“成…...

【iOS】RunLoop

前言-什么是RunLoop&#xff1f; 什么是RunLoop? 跑圈&#xff1f;字面上理解确实是这样的。 Apple官方文档这样解释RunLoop RunLoop是与线程息息相关的基本结构的一部分。RunLoop是一个调度任务和处理任务的事件循环。RunLoop的目的是为了在有工作的时候让线程忙起来&#…...

数据包传输方式:单播、多播、广播、组播、泛播

数据包传输方式 单播、多播、广播、组播、泛播 网络中假设X代表所有的机器&#xff0c;Y代表X中的一部分机器&#xff0c;Z代表一组机器&#xff0c;1代表一台机器&#xff0c;那么 1&#xff1a;1 那就是单播&#xff1b;1&#xff1a;Y 那就是多播&#xff1b;1&#xff1…...

WebRTC基础知识

文章目录 基础概念NAT (Network Address Translation) 打洞STUN&#xff08;Session Traversal Utilities for NAT&#xff09;基于STUN协议的DDoS反射攻击 # TODO TURN&#xff08;Traversal Using Relays around NAT&#xff09;ICE&#xff08;Interactive Connectivity Est…...

积累常见的有针对性的python面试题---python面试题001

1.考点列表的.remove方法的参数是传入的对应的元素的值,而不是下标 然后再看remove这里,注意这个是,删除写的那个值,比如这里写3,就是删除3, 而不是下标. remove不是下标删除,而是内容删除. 2.元组操作,元组不支持修改,某个下标的内容 可以问他如何修改元组的某个元素 3.…...

在springboot使用websocket时mapper无法注入

直接上代码 package cn.ujoined.combined.utils;import org.springframework.beans.BeansException; import org.springframework.context.ApplicationContext; import org.springframework.context.ApplicationContextAware; import org.springframework.stereotype.Componen…...

前端加密与解密的几种方式

1.base64加密方式 1. base64是什么&#xff1f; Base64&#xff0c;顾名思义&#xff0c;就是包括小写字母a-z、大写字母A-Z、数字0-9、符号""、"/"一共64个字符的字符集&#xff0c;&#xff08;另加一个“”&#xff0c;实际是65个字符&#xff0c;至于…...

详解Spring Bean的生命周期

详解Spring Bean的生命周期 Spring Bean的生命周期包括以下阶段&#xff1a; 1. 实例化Bean 对于BeanFactory容器&#xff0c;当客户向容器请求一个尚未初始化的bean时&#xff0c;或初始化bean的时候需要注入另一个尚未初始化的依赖时&#xff0c;容器就会调用createBean进…...

详解Shell 脚本中 “$” 符号的多种用法

通常情况下&#xff0c;在工作中用的最多的有如下几项&#xff1a; $0&#xff1a;Shell 的命令本身 1到9&#xff1a;表示 Shell 的第几个参数 $? &#xff1a;显示最后命令的执行情况 $#&#xff1a;传递到脚本的参数个数 $$&#xff1a;脚本运行的当前进程 ID 号 $*&#…...

Redis如何实现Session存储

在Redis中实现Session存储,主要有两种方式:使用Spring Session和手动存储。 使用Spring Session:Spring Session是Spring框架提供的一个模块,用于简化Session管理,并将Session数据存储到外部数据存储中,如Redis。使用Spring Session,你只需要在Spring Boot项目中添加相应…...

安防视频监控汇聚EasyCVR平台接入Ehome告警,公网快照不显示的原因排查

智能视频监控汇聚平台TSINGSEE青犀视频EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等&#xff0c;视频监控管理平台…...

【Springboot】@ComponentScan 详解

文章目录 ComponentScanComponentScan ANNOTATION 和 REGEXComponentScan CUSTOMComponentScan ASSIGNABLE_TYPE ComponentScan ComponentScan 是 Spring 框架中的一个注解&#xff0c;用于自动扫描和注册容器中的组件。 使用 ComponentScan 注解可以告诉 Spring 在指定的包或…...

flask-----信号

安装&#xff1a; flask中的信号使用的是一个第三方插件&#xff0c;叫做blinker。通过pip list看一下&#xff0c;如果没有安装&#xff0c;通过以下命令即可安装blinker&#xff1a; pip install blinker flask其中有内置的信号 template_rendered _signals.signal(temp…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...