每日一题---OJ题: 旋转数组
片头
嗨! 小伙伴们,咱们又见面啦,今天我们一起来学习一道OJ题---旋转数组
emmm,看上去好像没有那么难,我们一起来分析分析
比如: 数组里面有7个元素,分别为 1, 2, 3, 4, 5, 6, 7 , 现在我们将数组中的元素向右轮转3个位置
第一次轮转:将最后一个元素"7"放在第一个位置,后面的元素依次往后移动,变成 7, 1, 2, 3, 4, 5, 6
第二次轮转:将最后一个元素"6"放在第一个位置,后面的元素依次往后移动,变成 6, 7, 1, 2, 3, 4, 5
第三次轮转:将最后一个元素"5"放在第一个位置,后面的元素依次往后移动,变成 5, 6, 7, 1, 2, 3, 4
针对这道题,我们提供3种思路:
思路1: 右旋k次, 每次挪动旋转一位
定义一个变量temp,用来保存最后一个元素,将最后一个元素放到第一个位置,同时将后面的元素依次往右移动
代码如下:
void Reverse(int arr[], int time, int size) {time = time % size; //求具体的旋转次数for (int i = 0; i < time; i++) {//将最后一个元素保存在temp变量中int temp = arr[size - 1];for (int j = size-2; j >=0 ; j--) {//从下标为size-2的元素开始,一直到下标为0的元素,依次往后移动一位arr[j + 1] = arr[j];}//将最后一个元素放入第一个位置(还原)arr[0] = temp;}
}
int main() {int time = 3;int arr[] = { 1,2,3,4,5,6,7 };int sz = sizeof(arr) / sizeof(arr[0]);Reverse(arr, time,sz);for (int i = 0; i < sz; i++) {printf("%d ", arr[i]);}return 0;
}
运行结果为:
5 6 7 1 2 3 4
But,当我们把代码放到leetcode上面显示不通过
哈哈哈哈,说明这道OJ题限制了时间复杂度,我们这种思路的时间复杂度为 O(n^2) ,题目不通过
那我们就换一种思路呗!
思路2: 我们把数组分成3个部分逆置,假设数组里面有7个元素,分别为 1, 2, 3, 4, 5, 6, 7 , 现在我们将数组中的元素向右轮转3个位置
第一个部分: 前n-k个逆置,这里的 n 为 7, k 为 3,也就是前4个逆置,变成 4, 3, 2, 1, 5, 6, 7
第二个部分: 后k个逆置, 这里的 k 为 3,也就是后3个逆置, 变成 4, 3, 2, 1, 7, 6, 5
第三个部分: 整体逆置,变成了 5, 6, 7, 1, 2, 3, 4
代码如下:
void Reverse1(int arr[], int start, int end) {int left = start; //将start赋给left变量int right = end; //将end赋给right变量while (left < right) { //当left小于right的时候,进入循环//用临时变量temp实现逆置(左右元素交换)int temp = arr[left]; arr[left] = arr[right];arr[right] = temp;left++; //每交换完一次,left向右移动right--; //每交换完一次,right向左移动,直到两个变量相遇}
}int main() {int time = 3;int arr[] = { 1,2,3,4,5,6,7 };int sz = sizeof(arr) / sizeof(arr[0]);Reverse1(arr, 0, sz - time - 1); //前n-k个逆置Reverse1(arr, sz - time, sz - 1); //后k个逆置Reverse1(arr, 0, sz - 1); //整体逆置for (int i = 0; i < sz; i++) {printf("%d ", arr[i]);}return 0;
}
运行结果为:
5 6 7 1 2 3 4
同时,我们将代码放到leetcode当中,显示通过
嗯,这种方法好是好,但是好像我如果第一次做这种题,肯定想不出来,那有木有第3种思路呢?
有的! 接下来我就来介绍第三种思路
思路3: 我们可以定义一个新的数组,用memcpy函数将原数组的内容拷贝到新数组中去,拷贝元素的同时,也就完成了逆置
代码如下:
void Reverse2(int arr[], int size, int time) {time = time % size; //求出最终旋转次数int temp[20] = { 0 }; //定义一个临时数组temp,初始化数组为0//将原数组的后time个数拷贝到临时数组temp的前面位置中memcpy(temp, arr + size - time, sizeof(int) * time); //将原数组的前size-time个数拷贝到临时数组temp的后面位置中 memcpy(temp + time, arr, sizeof(int) * (size - time)); //将临时数组temp的所有元素拷贝回原数组memcpy(arr, temp, sizeof(int) * size);
}int main() {int nums[] = { 1,2,3,4,5,6,7 };int time = 3;int size = sizeof(nums) / sizeof(nums[0]);Reverse2(nums, size, time);for (int i = 0; i < size; i++) {printf("%d ", nums[i]);}return 0;
}
运行结果为:
5 6 7 1 2 3 4
我们把代码提交到leetcode上去,显示通过
片尾
今天我们学习了轮转数组这道OJ题,希望看完这篇文章能对友友们有所帮助 ! ! !
求点赞收藏加关注 ! ! !
谢谢大家 ! ! !
相关文章:
每日一题---OJ题: 旋转数组
片头 嗨! 小伙伴们,咱们又见面啦,今天我们一起来学习一道OJ题---旋转数组 emmm,看上去好像没有那么难,我们一起来分析分析 比如: 数组里面有7个元素,分别为 1, 2, 3, 4, 5, 6, 7 , 现在我们将数组中的元素向右轮转3个位置 第一次轮转:将最后一个元素"7"放在第一个…...
基于单链表的通讯录C语言实现
关于单链表的详细了解请见博主的另一篇博客,本文旨在对单链表进行应用,采用C语言编写。 http://t.csdnimg.cn/iBpFa 一、驱动层 1.1 SList.h #pragma once#include<stdio.h> #include<stdlib.h> #include<assert.h> #include"…...
【深度学习】YOLO-World: Real-Time Open-Vocabulary Object Detection,目标检测
介绍一个酷炫的目标检测方式: 论文:https://arxiv.org/abs/2401.17270 代码:https://github.com/AILab-CVC/YOLO-World 文章目录 摘要Introduction第2章 相关工作2.1 传统目标检测2.2 开放词汇目标检测 第3章 方法3.1 预训练公式:…...
debian安装和基本使用
🐇明明跟你说过:个人主页 🏅个人专栏:《Kubernetes航线图:从船长到K8s掌舵者》 🏅 🔖行路有良友,便是天堂🔖 目录 一、引言 1、Debian系统简介 2、Debian与其他Lin…...
nvm安装详细教程(安装nvm、node、npm、cnpm、yarn及环境变量配置)
一、安装nvm 1. 下载nvm 点击 网盘下载 进行下载 2、双击下载好的 nvm-1.1.12-setup.zip 文件 3.双击 nvm-setup.exe 开始安装 4. 选择我接受,然后点击next 5.选择nvm安装路径,路径名称不要有空格,然后点击next 6.node.js安装路径&#…...
优优嗨聚集团:如何优雅地解决个人债务问题,一步步走向财务自由
在快节奏的现代生活中,个人债务问题似乎已成为许多人不得不面对的挑战。正确处理个人债务,不仅关系到个人信用和财务状况,更是实现财务自由的重要一步。本文将为您提供一些实用的建议,帮助您优雅地解决个人债务问题,走…...
SpringCloud实用篇(四)——Nacos
Nacos nacos官方网站:https://nacos.io/ nacos是阿里巴巴的产品,现在是springcloud的一个组件,相比于eureka的功能更加丰富,在国内备受欢迎 nacos的安装 下载地址:https://github.com/alibaba/nacos/releases/ 启动…...
【嵌入式基础知识学习】AD/DA—数模/模数转换
AD/DA—数模/模数转换概念 数字电路只能处理二进制数字信号,而声音、温度、速度和光线等都是模拟量,利用相应的传感器(如声音用话筒)可以将它们转换成模拟信号,然后由A/D转换器将它们转换成二进制数字信号,…...
Swift中的结构体
Swift中的结构体是一种自定义的数据类型,可用于存储多个相关的值。结构体可以包含属性和方法,从而使其具有特定的功能。 结构体与类相似,但有一些重要的区别。最重要的区别是,结构体是值类型,而类是引用类型。这意味着…...
Selenium - java - 屏幕截图
文档地址 Selenium 浏览器自动化项目 | Selenium 安装 <dependency><groupId>org.seleniumhq.selenium</groupId><artifactId>selenium-java</artifactId><version>4.19.1</version></dependency>使用 创建WebDriver实例 …...
【论文阅读——SplitFed: When Federated Learning Meets Split Learning】
级别CCFA 1.摘要 联邦学习(FL)和分割学习(SL)是两种流行的分布式机器学习方法。两者都采用了模型对数据的场景;客户端在不共享原始数据的情况下训练和测试机器学习模型。由于机器学习模型的架构在客户端和服务器之间…...
Python使用方式介绍
1.安装与版本和IDE 1.1 python2.x和python3.x区别 python2在2020已经不再维护,目前主流开发使用python3. 二者语法上略有区别:输入输出、数据处理、异常和默认编码等,如:python3中字符串为Unicode字符串,使用UTF-8编码ÿ…...
浅述python中NumPy包
NumPy(Numerical Python)是Python的一种开源的数值计算扩展,提供了多维数组对象ndarray,是一个快速、灵活的大数据容器,可以用来存储和处理大型矩阵,支持大量的维度数组与矩阵运算,并针对数组运…...
jvm的面试回答
1、jvm由本地方法栈、虚拟机栈、方法区、程序计数器、堆组成,其中堆和方法区是线程间共享的,程序计数器、虚拟机栈和本地方法栈是线程私有的。 2、虚拟机栈: 保存每个java方法的调用、保存局部变量表、等 栈可能出现内存溢出,如果…...
打不动的蓝桥杯
打不动的蓝桥杯 2024-4-13 今天的蓝桥杯打得很烂,8题写了4题,100分可能有20来分吧。我写了的题好像都很简单,没什么竞争力。又觉得我知道的东西不止这么点,没能发挥。 这次比赛,首先,有强烈的陌生感。pytho…...
学习笔记——C语言基本概念文件——(13)
1、文件操作 1.1、文件概念 文件:实现数据存储的载体 1.2、文件的分类 按照数据的组织形式分类: 1.字符文件/文本文件 2.二进制文件 按照用途分类: 1.系统文件 2.库文件--标准库文件/非标准库文件(第三方库) 3.用…...
【MySQL】事务篇
SueWakeup 个人主页:SueWakeup 系列专栏:学习技术栈 个性签名:保留赤子之心也许是种幸运吧 目录 本系列专栏 1. 什么是事务 2. 事务的特征 原子性(Atomicity) 一致性(Consistency) 隔离性&…...
tsconfig.json文件常用配置
最近在学ts,因为tsconfig的配置实在太多啦,所以写此文章用作记录,也作分享 作用? tsconfig.jsono是ts编译器的配置文件,ts编译器可以根据它的信息来对代码进行编译 初始化一个tsconfig文件 tsc -init配置参数解释 …...
【Linux】tcpdump P1 - 网络过滤选项
文章目录 选项 -D选项 -c X选项 -n选项 -s端口捕获 port选项 -w总结 tcpdump 实用程序用于捕获和分析网络流量。系统管理员可以使用它来查看实时流量或将输出保存到文件中稍后分析。本文将演示在日常使用 tcpdump时可能想要使用的几种常见选项。 选项 -D 使用-D 选项的 tcpdu…...
网络篇04 | 应用层 mqtt(物联网)
网络篇04 | 应用层 mqtt(物联网) 1. MQTT协议介绍1.1 MQTT简介1.2 MQTT协议设计规范1.3 MQTT协议主要特性 2 MQTT协议原理2.1 MQTT协议实现方式2.2 发布/订阅、主题、会话2.3 MQTT协议中的方法 3. MQTT协议数据包结构3.1 固定头(Fixed header…...
Transformer模型-decoder解码器,target mask目标掩码的简明介绍
今天介绍transformer模型的decoder解码器,target mask目标掩码 背景 解码器层是对前面文章中提到的子层的包装器。它接受位置嵌入的目标序列,并将它们通过带掩码的多头注意力机制传递。使用掩码是为了防止解码器查看序列中的下一个标记。它迫使模型仅使用…...
All in One:Prometheus 多实例数据统一管理最佳实践
作者:淡唯(啃唯)、阳其凯(逸陵) 引言 Prometheus 作为目前最主流的可观测开源项目之一,已经成为云原生监控的事实标准,被众多企业广泛应用。在使用 Prometheus 的时候,我们经常会遇…...
mysql报错-mysql服务启动停止后,某些服务在未由其他服务或程序使用时将自动停止和数据恢复
启动mysql服务时出现该错误: 本地计算机上的mysql服务启动停止后,某些服务在未由其他服务或程序使用时将自动停止。 我的mysql版本是8.0.18 系统:win10 如何安装mysql,可以看我这一篇文章:mysql的安装 ---必会 - bigbigbrid - 博客园 (cn…...
Java开发从入门到精通(二十):Java的面向对象编程OOP:File文件操作的增删改查
Java大数据开发和安全开发 (一)Java的文件操作1.1 Java的File和IO流概念1.2 File类的使用1.2.1 创建File类的对象1.2.2 常用方法1:判断文件类型、获取文件信息1.2.3 常用方法2:创建文件、删除文件1.2.4 常用方法3:遍历文件夹 1.3 java File的方法递归1.3…...
10.list的模拟实现(普通迭代器和const迭代器的类模板)
1. list的介绍及使用 1.1 list的介绍 list的文档介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过…...
【电控笔记5】电流环速度环三环参数整定
旋转坐标系下的电压方程,由id和iq计算出ud和uq Lq:q轴电感 Ld:d轴电感 输入是电流,输出是电压? 内嵌式pmsm(ipmsm)模型建立: 其中: λf是转子磁场在定子绕组所产生的磁通链,为一常数,在psms中转子磁场非常稳定几乎不变。 ipmsm转矩方程式: 对永磁同步马达而言,使…...
AI克隆语音(基于GPT-SoVITS)
概述 使用GPT-SoVITS训练声音模型,实现文本转语音功能。可以模拟出语气,语速。如果数据质量足够高,可以达到非常相似的结果。相比于So-VITS-SVC需要的显卡配置更低,数据集更小(我的笔记本NVIDIA GeForce RTX 4050 Lap…...
小蚕爬树问题
小蚕爬树问题 问题描述: 编写一个函数 int day(int k,int m,int n),其功能是:返回小蚕需要多少天才能爬到树顶(树高 k 厘米,小蚕每天白天向上爬 m 厘米,每天晚上下滑 n 厘米,爬到树顶后不再下滑࿰…...
科研学习|科研软件——如何使用SmartPLS软件进行结构方程建模
SmartPLS是一种用于结构方程建模(SEM)的软件,它可以用于定量研究,尤其是在商业和社会科学领域中,如市场研究、管理研究、心理学研究等。 一、准备数据 在使用SmartPLS之前,您需要准备一个符合要求的数据集。…...
实用工具系列-ADB使用方式
作者持续关注 WPS二次开发专题系列,持续为大家带来更多有价值的WPS开发技术细节,如果能够帮助到您,请帮忙来个一键三连,更多问题请联系我(WPS二次开发QQ群:250325397),摸鱼吹牛嗨起来࿰…...
网站建设及优化 赣icp/如何快速推广网上国网
一,需求 迭代1 1,实现一个长度(Length)计算系统 用户既可以使用Mile为单位来记录一个长度,也可以用Yard为单位来记录 2,用户可以对比两个用不同单位表示的长度的相等关系 1 Mile 1760 Yard …...
深圳网站搜索优化/外链网盘
2019独角兽企业重金招聘Python工程师标准>>> 1.直接从apk上获取 将apk后缀改为zip,用WinRAR打开,将META-INF/CERT.RSA解压出来,比如说解压到D:\CERT.RSA 命令行底下用 D:\android\project>keytool -printcert -file "D:\C…...
织梦系统如何做网站地图/软文发稿公司
在数组中就地移除value的元素,并且不用管移除后的顺序稳定性。 大致思路: 如果要前移来删除数组元素的话要O(n^2)。 这里的方法是——两个指针(发现两个指针在“就地处决”真的很重要诶...),一个一直指向最后一个元…...
如何接单做网站/大二网络营销实训报告
一、依赖属性基本介绍 本篇开始学习WPF的另一个重要内容依赖属性。 大家都知道WPF带来了很多新的特性,其中一个就是引入了一种新的属性机制——依赖属性。依赖属性出现的目的是用来实现WPF中的样式、自动绑定及实现动画等特性。依赖属性的出现是WPF这种特殊的呈现原…...
保定官网seo分析/seo站点是什么意思
试验网站#1搜索引擎优化收录情况记录(断续运行)日期Yahoogooglebaidusogou每日收录每日收录增量每日收录每日收录增量每日收录每日收录增量每日收录每日收录增量2007-6-24288 333 1060 4813 2007-6-25164013523330108020481302007-6-26空间超过6月流量限制……,…...
网站扁平化结构和树形结构/网络服务有哪些
一、修改文件所有者 chown newowner 文件/目录 改变所有者 chown newowner:newgroup文件/目录改变所有者和所在组 -R 如果是目录则使其下所有子文件或目录递归生效 案列1:请将/home/aa.txt文件的所有者修改成yaya 案列2:请将/home/zhangsan目录…...