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

leetcode 面试经典 150 题:轮转数组

链接轮转数组
题序号189
题型数组
解法1. 额外数组法,2. 原数组翻转法(三次翻转法)
难度中等
熟练度✅✅✅✅

题目

给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

  • 示例 1:
    输入: nums = [1,2,3,4,5,6,7], k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右轮转 1 步: [7,1,2,3,4,5,6]
    向右轮转 2 步: [6,7,1,2,3,4,5]
    向右轮转 3 步: [5,6,7,1,2,3,4]

  • 示例 2:
    输入:nums = [-1,-100,3,99], k = 2
    输出:[3,99,-1,-100]
    解释:
    向右轮转 1 步: [99,-1,-100,3]
    向右轮转 2 步: [3,99,-1,-100]

  • 提示:
    1 <= nums.length <= 105
    -231 <= nums[i] <= 231 - 1
    0 <= k <= 105

  • 进阶:
    尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
    你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

题解

额外数组法

  1. 核心要点:遍历原数组,将原数组下标为 i 的元素放至新数组下标为 (i+k) mod n 的位置,最后将新数组拷贝至原数组即可。
  2. 复杂度:时间复杂度O(n),空间复杂度O(n)。
  3. c++ 实现算法
class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();vector <int> newarr(n);for(int i = 0; i < n; i++ ) {newarr[(i+k)%n] = nums[i];}nums.assign(newarr.begin(), newarr.end());  }
};
  1. 算法推演

n=7,k=3
(0+3)%7=3 newarr[3] = nums[0] 1
(1+3)%7=4 newarr[4] = nums[1] 2
(2+3)%7=5 newarr[5] = nums[2] 3
(3+3)%7=6 newarr[6] = nums[3] 4
(4+3)%7=0 newarr[0] = nums[4] 5
(5+3)%7=1 newarr[1] = nums[5] 6
(6+3)%7=2 newarr[2] = nums[6] 7

原数组翻转法(三次翻转法)

  1. 核心要点:现将整个数组翻转,再将前 k 个数翻转,最后将剩下元素翻转。
  2. 复杂度:时间复杂度O(n),其中 n 为数组的长度。每个元素被翻转两次,一共 n 个元素,因此总时间复杂度为 O(2n)=O(n);空间复杂度O(1)。
  3. c++ 实现算法:翻转可以利用swap函数数组首尾交换实现。
class Solution2 {
public:void reverse(vector<int>& nums, int start, int end) {while (start < end) {swap(nums[start], nums[end]);start += 1;end -= 1;}}void rotate(vector<int>& nums, int k) {k %= nums.size(); //k=3%7=3,为了旋转不超过数组长度reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}
};
  1. 推演算法

推演:
输入数组:1 2 3 4 5 6 7
第一次翻转:7 6 5 4 3 2 1
第二次翻转:5 6 7 4 3 2 1
第三次翻转:5 6 7 1 2 3 4

c++ 完整demo

#include <iostream>
#include <vector>using namespace std;class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();vector <int> newarr(n);for(int i = 0; i < n; i++ ) {newarr[(i+k)%n] = nums[i];}nums.assign(newarr.begin(), newarr.end());  }
};
class Solution2 {
public:void reverse(vector<int>& nums, int start, int end) {while (start < end) {swap(nums[start], nums[end]);start += 1;end -= 1;}}void rotate(vector<int>& nums, int k) {k %= nums.size(); //k=3%7=3,为了旋转不超过数组长度reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}
};
int main() {vector <int> nums = {1, 2, 3, 4, 5, 6, 7};int k = 3;//Solution solution;Solution2 solution;solution.rotate(nums, k);for(int i = 0; i < nums.size(); i++) {cout << "nums[" << i << "]: " << nums[i] << endl;}return 0;
}

相关文章:

leetcode 面试经典 150 题:轮转数组

链接轮转数组题序号189题型数组解法1. 额外数组法&#xff0c;2. 原数组翻转法&#xff08;三次翻转法&#xff09;难度中等熟练度✅✅✅✅ 题目 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1: 输入: nums [1,2,…...

Elasticsearch:探索 Elastic 向量数据库的深度应用

Elasticsearch&#xff1a;探索 Elastic 向量数据库的深度应用 一、Elasticsearch 向量数据库简介 1. Elasticsearch 向量数据库的概念 Elasticsearch 本身是一个基于 Lucene 的搜索引擎&#xff0c;提供了全文搜索和分析的功能。随着技术的发展&#xff0c;Elasticsearch 也…...

From matplotl1b.path 1mport failed to import ImportError:numpy.core.multiarray

问题&#xff1a;From matplotl1b.path 1mport failed to import ImportError:numpy.core.multiarray 安装labelme的时候说numpy与环境不兼容&#xff0c;调不了labelme 解决1&#xff1a;安装虚拟环境 &#xff08;这里安装labelmede 虚拟环境&#xff09; #查看python版本 …...

Docker- Unable to find image “hello-world“locally

Docker- Unable to find image “hello-world“locally 文章目录 Docker- Unable to find image “hello-world“locally问题描述一. 切换镜像1. 编辑镜像源2. 切换镜像内容 二、 检查设置1、 重启dockers2、 检查配置是否生效3. Docker镜像源检查4. Dokcer执行测试 三、自定义…...

linux定时执行脚本的方法

使用 cron 服务(推荐) 简介: Cron 是一个基于时间的任务调度程序,它允许用户在指定的时间间隔自动运行命令或脚本。它使用crontab(cron table 的缩写)文件来存储定时任务的配置信息。操作步骤: 编辑用户的 crontab 文件:在终端中输入crontab -e命令。这将打开一个文本编…...

Docker 中启动 Nacos

要在 Docker 中启动 Nacos&#xff0c;你可以使用以下步骤来启动 Nacos 服务。我已经有了 swr.cn-north-4.myhuaweicloud.com/ddn-k8s/docker.io/nacos/nacos-server:v2.4.2.1 这个镜像。 1. 创建并启动 MySQL 容器&#xff08;Nacos 依赖 MySQL&#xff09; Nacos 默认使用 …...

【计算机网络】课程 实验三 跨交换机实现 VLAN 间路由

实验 3 跨交换机实现 VLAN 间路由 一、实验目的 1&#xff0e;理解跨交换机之间VLAN的特点。 2&#xff0e;掌握如何在交换机上划分基于端口的VLAN&#xff0c;给VLAN内添加端口。 3&#xff0e;利用三层交换机跨交换机实现 VLAN 间路由。 二、实验分析与设计 【背景描述…...

【74CH192D+4511减法30进制2022年7月7日】

缘由30秒定时器错误帮我看看-大数据-CSDN问答 电路图用到S1倒计时信号控制&#xff0c;S2置数30。从演示可以看到置数&#xff0c;开始&#xff0c;暂停&#xff0c;继续&#xff0c;等于0时清零&#xff0c;并且灯亮&#xff0c;最后断开信号输入完成所有功能。看题主有自己动…...

基于ESP32的桌面小屏幕实战[5]:PCB下单

1. 焊接调试前准备 PCB下单 点击“PCB下单” 检查一下DRC 确认无错误之后&#xff0c;确认下单 然后就会跳转到下面的网页 基本上保持默认选项即可。可以看到“焊盘喷镀”有3个选项。 在选择表面处理工艺时&#xff0c;应综合考虑产品的具体需求、环保法规以及成本等因素。例…...

孤独症儿童寄宿:温馨寄宿,陪伴成长

在社会的各个角落&#xff0c;有一群特殊的孩子&#xff0c;他们生活在自己的世界里&#xff0c;对外界的感知和反应与众不同。他们&#xff0c;就是孤独症&#xff08;自闭症&#xff09;儿童。孤独症&#xff0c;这个看似遥远的名词&#xff0c;却真实地影响着无数家庭&#…...

云备份项目--服务端编写

文章目录 7. 数据管理模块7.1 如何设计7.2 完整的类 8. 热点管理8.1 如何设计8.2 完整的类 9. 业务处理模块9.1 如何设计9.2 完整的类9.3 测试9.3.1 测试展示功能 完整的代码–gitee链接 7. 数据管理模块 TODO: 读写锁&#xff1f;普通锁&#xff1f; 7.1 如何设计 需要管理…...

CSS——2.书写格式一

<!DOCTYPE html> <html><head><meta charset"UTF-8"><title></title></head><body><!--css书写中&#xff1a;--><!--1.css 由属性名:属性值构成--><!--style"color: red;font-size: 20px;&quo…...

【保姆级】sql注入之堆叠注入

一、堆叠注入的原理 mysql数据库sql语句的默认结束符是以";"号结尾&#xff0c;在执行多条sql语句时就要使用结束符隔 开,而堆叠注入其实就是通过结束符来执行多条sql语句 比如我们在mysql的命令行界面执行一条查询语句,这时语句的结尾必须加上分号结束 select * fr…...

大模型推理加速调研(框架、方法)

大模型推理加速调研&#xff08;框架、方法&#xff09; 大模型推理框架调研总结推理框架TensorRT-LLMllama.cppmnn-llmfastllmmlc-llm 环境搭建&部署推理环境llama.cppfastllmmnn-llmvllm vllm_openai_completions.pylmdeployTensorRT-LLM 大模型加速技术总结模型压缩量化…...

js -音频变音(听不出说话的人是谁)

学习参考来源&#xff1a; https://zhuanlan.zhihu.com/p/634848804 https://developer.mozilla.org/zh-CN/docs/Web/API/Web_Audio_API 实际效果&#xff1a; http://www.qingkong.zone/laboratory?typeaudio-confusion 前言 本文内容可结合上面学习参考来源&#xff0c;结合…...

3D Object Detection和6D Pose Estimation有什么异同?

知乎讨论&#xff1a; (99 封私信 / 95 条消息) 3D Object Detection和6D Pose Estimation有什么异同&#xff1f; - 知乎 GPT回答&#xff1a; 3D Object Detection 和 6D Pose Estimation 都是计算机视觉领域的重要任务&#xff0c;广泛应用于机器人、自动驾驶和增强现实…...

NRF24L01模块STM32通信-通信初始化

目录 前言 一、IO口初始化 二、模拟SPI的基础代码 1.一些代码的宏定义 2.起始信号 3.CS,SCK,MOSI操作 4.MISO,IRQ操作 三.中间层代码 1.字节的输入和读取 2.写操作 3.读操作 四.应用层代码 1.24L01的检测 2.在main函数进行简单验证 3.24L01宏定义的代码 总结 前…...

vue Element Ui Upload 上传 点击一个按钮,选择多个文件后直接上传,使用防抖解决多次上传的问题。

问题&#xff1a; 在使用Element Ui Upload 上传文件时&#xff0c;选择多个文件上传时&#xff0c;on-change事件会一个一个返回上传的文件&#xff0c;导致前端不知道什么时候可以拿到全部上传的文件&#xff0c;再一起调后台接口。 解决方法&#xff1a; 上传文件后&…...

算法题(26):最后一个单词的长度

审题&#xff1a; 需要我们返回最后一个单词的长度&#xff0c;并且字符串内只有空格来分割单词 思路&#xff1a; 找到最后一个单词的方法就是从后开始遍历找到第一个非空格的元素&#xff0c;称为pos&#xff08;第一个出现单词的位置&#xff09; 然后再从pos位置开始反向寻…...

Ungoogled Chromium127 编译指南 MacOS 篇(二)- 项目要求

1. 引言 在开始编译 Ungoogled Chromium 之前&#xff0c;我们需要确保系统满足所有必要的硬件和软件要求。由于浏览器编译是一个资源密集型的任务&#xff0c;合适的硬件配置和完整的软件环境至关重要。本文将详细介绍编译 Ungoogled Chromium 所需的各项要求。 2. 硬件要求…...

nginx配置-其他配置

nginx配置-其他配置 server_tokens server_tokens server_token on/off 是 Nginx 配置文件中的一个指令&#xff0c;用于控制 Nginx 服务器在响应 HTTP 请求时是否显示服务器的版本信息。 默认情况下&#xff0c;Nginx 会在响应头中包含服务器的版本号&#xff0c;例如 Serve…...

Springboot使用RabbitMQ实现关闭超时订单的一个简单示例

1.maven中引入rabbitmq的依赖&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId></dependency> 2.application.yml中进行rabbitmq相关配置&#xff1a; # rabbit…...

QT-------------对话框和多窗口程序设计

一、标准对话框 1. QFileDialog 对话框 功能&#xff1a;提供文件选择对话框&#xff0c;方便用户选择文件或目录。 #include <QApplication> #include <QFileDialog> #include <QMessageBox>int main(int argc, char *argv[]) {QApplication app(argc, a…...

信息科技伦理与道德2:研究方法

1 问题描述 1.1 讨论&#xff1f; 请挑一项信息技术&#xff0c;谈一谈为什么认为他是道德的/不道德的&#xff0c;或者根据使用场景才能判断是否道德。判断的依据是什么&#xff08;自身的道德准则&#xff09;&#xff1f;为什么你觉得你的道德准则是合理的&#xff0c;其他…...

Linux(Centos 7.6)命令详解:ls

1.命令作用 列出目录内容(list directory contents) 2.命令语法 Usage: ls [OPTION]... [FILE]... 3.参数详解 OPTION: -l&#xff0c;long list 使用长列表格式-a&#xff0c;all 不忽略.开头的条目&#xff08;打印所有条目&#xff0c;包括.开头的隐藏条目&#xff09…...

深入理解 WebSocket:实时通信的基础

随着互联网技术的不断发展&#xff0c;实时通信逐渐成为现代应用程序中不可或缺的一部分。无论是即时通讯应用、在线游戏、社交平台还是股票交易系统&#xff0c;都需要能够在客户端与服务器之间快速、高效地传输数据。传统的 HTTP 协议虽然简单且广泛应用&#xff0c;但它并不…...

【网络协议】开放式最短路径优先协议OSPF详解(一)

OSPF 是为取代 RIP 而开发的一种无类别的链路状态路由协议&#xff0c;它通过使用区域划分以实现更好的可扩展性。 文章目录 链路状态路由协议OSPF 的工作原理OSPF 数据包类型Dijkstra算法、管理距离与度量值OSPF的管理距离OSPF的度量值 链路状态路由协议的优势拓扑结构路由器O…...

2000-2020年各省地区生产总值数据/各省gdp数据

2000-2020年各省地区生产总值数据/各省gdp数据 1、时间&#xff1a;2000-2020年 2、来源&#xff1a;国家统计局 3、指标&#xff1a;行政区划代码、地区、年份、地区生产总值 4、范围&#xff1a;31省 指标解释&#xff1a;地区生产总值&#xff08;Regional GDP&#xf…...

消息转换器在SpringMVC执行流程

消息转换器的工作机制 内部工作流程 读取&#xff08;Read&#xff09;操作 当接收到一个包含实体内容的HTTP请求时&#xff0c;Spring MVC会根据请求头中的Content-Type属性来确定应该使用哪个HttpMessageConverter来解析请求体。DispatcherServlet会遍历已注册的HttpMessage…...

7. C语言 运算符详解

本章目录: 前言C语言运算符的分类1. 算术运算符2. 关系运算符3. 逻辑运算符4. 位运算符5. 赋值运算符6. 杂项运算符 运算符优先级 前言 在C语言中&#xff0c;运算符是程序中执行各种操作的核心工具&#xff0c;涉及算术运算、逻辑判断、位操作等多个方面。掌握C语言中的各种运…...

一、准备工作(2):部署TensorFlow和Keras

目录 一、确保已安装 Python 和 pip 二、打开命令行界面并执行安装命令 Windows macOS 和 Linux 三、安装过程中的注意事项 创建虚拟环境 激活虚拟环境 在虚拟环境中安装包 四、验证安装 五、常见问题排查 六、下一步 pip install tensorflow keras 是一个用于在计算…...

Rabbitmq Fanout如何保证不重复消费及应用场景

rabbitmq fanout业务场景&#xff0c;一个交换机对应多个队列&#xff0c;不会重复消费吗 在 RabbitMQ 中&#xff0c;使用 Fanout 类型的交换机时&#xff0c;确实可以将一个交换机绑定到多个队列。每当有消息发布到这个交换机时&#xff0c;交换机会把消息广播到所有绑定的队…...

【Linux系列】使用 `nohup` 命令运行 Python 脚本并保存输出日志的详细解析

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

基于Python的考研学习系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…...

多模态大模型文生图和图生文的主要技术

1 图生文 CLIP 该模型架构由图像编码器和文本编码器组成。图像编码器将图像转换为嵌入&#xff08;数字列表&#xff09;&#xff0c;文本编码器将文本转换为嵌入。 这两个编码器在成批的图像-文本对上进行训练&#xff0c;其中文本描述图像。编码器的训练方式如下&#xff1…...

云架构:考量与框架

云架构&#xff1a;考量与框架 引言 在当今的数字化环境中&#xff0c;云计算已成为现代商业运营的基石。一个设计良好的云架构框架为可扩展、安全和弹性的系统奠定了基础。本文将深入探讨云架构的核心要素&#xff0c;讨论重要的考量因素、设计指南&#xff0c;以及最佳实践…...

用uniapp写一个播放视频首页页面代码

效果如下图所示 首页有导航栏&#xff0c;搜索框&#xff0c;和视频列表&#xff0c; 导航栏如下图 搜索框如下图 视频列表如下图 文件目录 视频首页页面代码如下 <template> <view class"video-home"> <!-- 搜索栏 --> <view class…...

开发培训-慧集通(iPaaS)集成平台脚本开发Groovy基础培训视频

‌Groovy‌是一种基于Java虚拟机&#xff08;JVM&#xff09;的敏捷开发语言&#xff0c;结合了Python、Ruby和Smalltalk的许多强大特性。它旨在提高开发者的生产力&#xff0c;通过简洁、熟悉且易于学习的语法&#xff0c;Groovy能够与Java代码无缝集成&#xff0c;并提供强大…...

供需平台信息发布付费查看小程序系统开发方案

供需平台信息发布付费查看小程序系统主要是为了满足个人及企业用户的供需信息发布与匹配需求。 一、目标用户群体 个人用户&#xff1a;寻找兼职工作、二手物品交换、本地服务&#xff08;如家政、维修&#xff09;等。 小微企业&#xff1a;推广产品和服务&#xff0c;寻找合…...

【Qt】如何保证线程安全(以日志写入为例)

前言 在近日学习中发现&#xff0c;如果开发一个单例模式的日志系统&#xff0c;难免会出现多个线程记录日志的情况&#xff0c;这个时候线程可能导致竞争&#xff0c;或者始料未及的情况发生。 通过学习&#xff0c;如果要保证线程安全&#xff0c;要使用互斥锁QMutex&#xf…...

k8s基础(3)—Kubernetes-Deployment

一、 Deployment概述 ‌ Kubernetes Deployment‌是Kubernetes中的一个核心概念&#xff0c;它是一种高级别的控制器&#xff0c;用于管理Pod和ReplicaSet&#xff0c;确保应用程序的高可用性和稳定性。Deployment通过声明式配置来创建和更新Pod和ReplicaSet&#xff0c;从而…...

信息系统管理师试题-人力资源

下列&#xff08; &#xff09;不属于人力资源管理的主要工作内容。 A根据各工作岗位任务的特点和工作要求&#xff0c;预测组织的人力需求 B根据工作需要&#xff0c;选拔出符合组织需要的员工 C对新员工进行工作指导和培训 D为项目团队争取和募集更多资金 答案D 解析&#xf…...

【情感】程序人生之情感关系中的平等意识(如何经营一段长期稳定的关系 沸羊羊舔狗自查表)

【情感】程序人生之情感关系中的平等意识&#xff08;如何经营一段长期稳定的关系 & 沸羊羊舔狗自查表&#xff09; 文章目录 1、情感关系中的平等意识2、如何经营一段长期稳定的关系&#xff08;避免左倾 | 敬畏与担当&#xff09;3、沸羊羊/舔狗自查表&#xff08;避免右…...

pyspark执行group by操作

前情提要 在处理亿级别数据时&#xff0c;常常输入是hive表&#xff0c;因此需要在pypark流程中引入一些场景sql操作&#xff0c;其中group by就是比较常见的操作。 基础步骤 创建SparkSession&#xff1a;通过enableHiveSupport()方法启用Hive支持&#xff0c;确保能够访问…...

小寒时处在二三九,天寒地冻北风吼

今&#xff08;1月5日上午10时33分&#xff09;天迎来了小寒节气&#xff0c;本“人民体验官”推广人民日报官方微博文化产品《小寒来了&#xff01;最冷的时候如何养生防病》&#xff0c;同时科普小寒相关知识。 截图&#xff1a;来源本“人民体验官”推广平台 人民微博告诉我…...

微信小程序校园自助点餐系统实战:从设计到实现

随着移动互联网的发展&#xff0c;越来越多的校园场景开始智能化、自助化。微信小程序凭借其轻量化、便捷性和强大的生态支持&#xff0c;成为了各类校园应用的首选工具之一。今天&#xff0c;我们将通过实际开发一个微信小程序“校园自助点餐系统”来展示如何设计和实现这样一…...

java基础之代理

代理模式&#xff08;Proxy Pattern&#xff09; 简介 是一种结构型设计模式&#xff0c;主要用于为某对象提供一个代理对象&#xff0c;以控制对该对象的访问。通过引入一个代理对象来控制对原对象的访问。代理对象在客户端和目标对象之间充当中介&#xff0c;负责将客户端的…...

uniapp - 基于uniapp+vue3实现自定义增强版table表格组件体验「兼容H5+小程序+App端」

本文提供增强版table表格组件体验,打造跨端表格的新标杆. uv3-table&#xff1a;一款基于uniappvue3跨端自定义手机端增强版表格组件。支持固定表头/列、边框、斑马纹、单选/多选&#xff0c;自定义表头/表体插槽、左右固定列阴影高亮显示。支持编译兼容H5小程序端App端。 提供…...

【Obsidian插件开发】新建窗口时出现多余的空白窗口

问题描述 在打开Edit Task的Modal的时候&#xff0c;有一个多余的空白modal同时也被打开了&#xff0c;并且点右上角的叉号可以把Edit Task窗口也关上。最开始没有这个问题&#xff0c;我给edit task窗口加了css&#xff0c;移动位置之后问题就出现了。 解决方法 我最开始看到…...

springmvc--请求参数的绑定

目录 一、创建项目&#xff0c;pom文件 二、web.xml 三、spring-mvc.xml 四、index.jsp 五、实体类 Address类 User类 六、UserController类 七、请求参数解决中文乱码 八、配置tomcat,然后启动tomcat 1. 2. 3. 4. 九、接收Map类型 1.直接接收Map类型 &#x…...