LeetCode hot 100 每日一题(11)——189. 轮转数组
这是一道难度为中等的题目,让我们来看看题目描述:
给定一个整数数组
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 <= 1 0 5 10^5 105
- − 2 31 -2^{31} −231 <= nums[i] <= 2 31 2^{31} 231 - 1
- 0 <= k <= 1 0 5 10^5 105
题解
class Solution {public void rotate(int[] nums, int k) {int n = nums.length; // 获取数组的长度k %= n; // 取模运算,防止 k 超过数组长度(若 k == n,则轮转后数组不变)// 1. 先整体翻转数组reverse(nums, 0, n - 1);// 2. 翻转前 k 个元素,使其恢复正确顺序reverse(nums, 0, k - 1);// 3. 翻转剩余的 n-k 个元素,使其恢复正确顺序reverse(nums, k, n - 1);}// 反转数组的辅助方法private void reverse(int[] nums, int i, int j) {while (i < j) { // 采用双指针法,交换 i 和 j 位置的元素int temp = nums[i];nums[i++] = nums[j]; // i 向右移动nums[j--] = temp; // j 向左移动}}
}
算法思路
使用 三次翻转 解决数组的右移问题:
- 整体翻转数组(第一次翻转):把数组
[1,2,3,4,5,6,7]
变成[7,6,5,4,3,2,1]
。 - 翻转前
k
个元素(第二次翻转):将[7,6,5]
翻转后变为[5,6,7]
,其余部分[4,3,2,1]
保持不变。 - 翻转剩余部分(第三次翻转):将
[4,3,2,1]
翻转后变为[1,2,3,4]
。
最终得到正确的 右移 k
次后的数组。
示例演示
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
执行 rotate(nums, 3)
:
- 整体翻转:
[7,6,5,4,3,2,1]
- 翻转前 3 个元素:
[5,6,7,4,3,2,1]
- 翻转剩余部分:
[5,6,7,1,2,3,4]
最终输出:[5,6,7,1,2,3,4]
时间复杂度分析
- 数组翻转的时间复杂度:
- 第一次翻转:
O(n)
- 第二次翻转:
O(k)
- 第三次翻转:
O(n-k)
- 第一次翻转:
总时间复杂度为 O(n),相比于暴力解法(O(n × k))更高效。
空间复杂度分析
- 只使用了 常数级额外空间(
int temp
变量),因此 空间复杂度为 O(1)。
问题与解答
[NOTE] 问题1
k %= n; // 取模运算,防止 k 超过数组长度(若 k == n,则轮转后数组不变)
这一句中,假如k超过数组长度会怎么样?假如k为n+1呢?
解答:
情况分析
如果k
直接超过数组长度n
,那么我们实际上只关心k % n
的结果,而不是k
的实际值。
示例 1假设数组
nums = [1,2,3,4,5]
,n = 5
:
- 若
k = 5
,k % 5 = 0
,意味着数组轮转 5 次后回到原始状态。- 若
k = 6
,k % 5 = 1
,意味着 轮转 6 次 = 轮转 1 次,即[5,1,2,3,4]
。- 若
k = 10
,k % 5 = 0
,数组轮转 10 次后仍然保持不变。- 若
k = n + 1 = 6
,k % 5 = 1
,等效于k = 1
的情况。一般规律
- 由于数组是 循环结构,当
k
大于等于n
时,多出来的n
轮转不会改变最终结果,因此k % n
取余数是关键。- 代码中的
k %= n;
保证 k 永远在[0, n-1]
范围内,不会导致重复计算,使算法更高效。
[NOTE] 问题2
while (i < j) { // 采用双指针法,交换 i 和 j 位置的元素int temp = nums[i];nums[i++] = nums[j]; // i 向右移动nums[j--] = temp; // j 向左移动}
这段双指针法交换位置是否可以作为模板使用?
解答:
双指针法(Two Pointers)详解
概念
- 双指针法 是一种 高效的 处理 数组翻转(或者部分翻转)的方式。
- 采用 左右两端同时交换 的方式,可以 一次遍历 完成数组反转。
- 时间复杂度:O(n),空间复杂度:O(1)。
示例演示
假设:
nums = [1, 2, 3, 4, 5]
执行
reverse(nums, 0, 4);
,即反转整个数组。迭代过程
迭代次数 i j nums[i] nums[j] 交换后数组 初始状态 0 4 1 5 [5,2,3,4,1]
第 1 次迭代 1 3 2 4 [5,4,3,2,1]
第 2 次迭代 2 2 3 3 [5,4,3,2,1]
(中点,不变)
- 终止条件:
i >= j
时停止,即遍历到数组中心即可完成反转。
作为模板使用该方法可用于以下场景
- 翻转整个数组
reverse(nums, 0, nums.length - 1);
适用于 数组翻转、字符串翻转 等。- 翻转子数组
reverse(nums, left, right);
适用于 局部翻转、K 轮转 等问题,如 字符串中的单词反转。- 检查是否为回文
boolean isPalindrome(String s) {int i = 0, j = s.length() - 1;while (i < j) {if (s.charAt(i++) != s.charAt(j--)) return false;}return true; }
适用于 判断字符串或数组是否对称。
相关文章:
LeetCode hot 100 每日一题(11)——189. 轮转数组
这是一道难度为中等的题目,让我们来看看题目描述: 给定一个整数数组 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…...
VLAN综合实验
一、实验拓扑 二、实验要求 1、PC1/3处于同一个网段,所在接口为access,属于VLAN 2。 2、PC2/4/5/6处于同一网段。 3、PC2可以访问PC4/5/6。 4、PC4可以访问PC5,但不能访问PC6。 5、PC5不能访问PC6。 6、所有PC通过DHCP获取IP地址&#…...
杨辉三角(js实现,LeetCode118)
看到这道题我的第一反应是找规律,核心突破点是numRows这个参数,杨辉三角的第numRows行拥有的元素数量为numRows个,并且头尾都是1,由此我们可以通过双层for循环,先生成每一行的数组,然后将每一行的数组push进…...
C语言复习笔记--数组
今天继续来浅浅推进一下C语言的复习,这次是数组的复习,话不多说,正文开始. 数组的概念 数组是⼀组相同类型元素的集合,一种自定义类型.数组中元素个数不能为0.数组分为⼀维数组和多维数组,多维数组⼀般⽐较多⻅的是⼆维数组. 下面从一维数组说起. 一维数组的创建和…...
Linux操作系统实验报告单(3)文本编辑器vi/vim
一、实验目的 掌握vi/vim编辑器的进入和退出方式了解vi/vim的三种模式熟练vi/vim的操作命令 二、实验内容 1.在家目录下新建一个名为“vitest_name”(“name”为学生姓名拼音)的目录。 ●创建用户目录命令:sudo mkdir /home/vitest_lw3613 …...
docker linux 常用操作命令
以下是 Docker 的常见操作命令及其简单介绍,帮助你快速上手 Docker 的基本使用: 1. 镜像操作 拉取镜像 docker pull 镜像名称:标签示例: docker pull ubuntu:20.04从 Docker Hub 拉取 Ubuntu 20.04 镜像。 拉取镜像 docker build -t"…...
除自身以外数组的乘积——面试经典150题(力扣)
题目 给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时…...
打破煤矿通信屏障,无线系统赋能生产安全与智能进阶
项目背景 在煤矿行业智能化转型的浪潮中,七台河矿业局积极回应国家煤矿智能化建设的号召,采取了具有前瞻性的战略举措——在七台河地区的煤矿部署了“井上井下”无线覆盖与广播一体化系统。此举旨在消除井上与井下之间的通信障碍,加强矿业局与…...
DeepSeek + Kimi 自动生成 PPT
可以先用deepseek生成ppt大纲,再把这个大纲复制到Kimi的ppt助手里: https://kimi.moonshot.cn/kimiplus/conpg18t7lagbbsfqksg 选择ppt模板: 点击生成ppt就制作好了。...
Blender标注工具
按住键盘D键 鼠标左键绘制 / 右键擦除 也可以在上方选择删除...
鸿蒙开发:远场通信服务rcp拦截器问题
前言 本文基于Api13。 上篇文章,简单的对rcp中的会话问题做了概述,本篇文章,我们聊一聊rcp中的拦截器问题,按照正常开发,其实拦截器中也不存在问题的,毕竟都是很官方的开发方式,但是在结合了创建…...
调研报告:Hadoop 3.x Ozone 全景解析
Ozone 是 Hadoop 的分布式对象存储系统,具有易扩展和冗余存储的特点。 Ozone 不仅能存储数十亿个不同大小的对象,还支持在容器化环境(比如 Kubernetes)中运行。 Apache Spark、Hive 和 YARN 等应用无需任何修改即可使用 Ozone。Ozone 提供了 Java API、S3 接口和命令行接口…...
Thinkphp 多文件压缩
控制器 <?phpnamespace app\api\controller; use think\Controller; use think\facade\Db; use think\facade\Request;use ZipArchive;class DrugTestResult {public function download(){if(Request::isPost()){$data Request::post();$idnumber Request::param(idnumb…...
NGINX中的反向代理实践
以下是一个全面和优化的配置示例,包括了错误处理、超时设置、头部信息调整等: server {listen 80;server_name your.domain.name; # 替换为你的实际域名或IP地址# 前端应用的静态资源处理location / {root /path/to/vue/dist; # Vue 应用的dist目录try_…...
redis分布式锁实现Redisson+redlock中watch dog是如何判断当前线程是否持有锁进行续租的呢?
在 Redis 中,Watch Dog(看门狗)机制主要用于实现分布式锁的自动续期(如 Redisson 的 RedLock 实现)。其核心目的是确保当业务逻辑执行时间超过锁的初始过期时间(leaseTime)时,锁不会…...
[spring] Spring JPA - Hibernate 多表联查 1
[spring] Spring JPA - Hibernate 多表联查 1 之前在 [spring] spring jpa - hibernate 名词解释&配置 和 [spring] spring jpa - hibernate CRUD 简单的学习了一下怎么使用 Hibernate 实现 CRUD 操作,不过涉及到的部分都是逻辑上比较简单的实现——只在一张表…...
在 Elasticsearch 中探索基于 NVIDIA 的 GPU 加速向量搜索
作者:来自 Elastic Chris Hegarty 及 Hemant Malik 由 NVIDIA cuVS 提供支持,此次合作旨在为开发者在 Elasticsearch 中的向量搜索提供 GPU 加速。 在 Elastic Engineering 组织内,我们一直致力于优化向量数据库的性能。我们的使命是让 Lucen…...
2025年图生视频模型技术全景解析
一、开源图生视频模型 阿里通义万象Wan2.1系列 I2V-14B-480P: 14B参数基础模型支持480P分辨率图生视频显存需求16GB以上 I2V-14B-720P: 高清增强版模型采用分帧渲染技术,输出分辨率达1280720 技术特性: 支持中文提示词自动解析内置…...
Docker build 会在本地产生巨大的文件
Docker build 会在本地产生巨大的文件, 比如 用 这个命令列出本地镜像 docker images 可见size都是很大的, 到docker目录下,看到ext4.vhdx的大小 80多G 那只能用这个命令把不用的镜像删掉了: (rmi后面是镜像id&a…...
使用LLaMA Factory微调导出模型,并用ollama运行,用open webui使用该模型
本篇记录学习使用llama factory微调模型的过程,使用ollama运行微调好的模型,使用open webui前端调用ollama的模型; 测试机信息: 系统:Ubuntu 24.04.2 LTS(桌面版) cpu:i9-14900KF …...
Git远程拉取和推送配置
Git进行远程代码拉取和推送时候提示配置user.name 和 user.email 背景:换新电脑后使用Git进行代码拉取和推送过程中,提示“Make sure you configure your “user.name” and “user.email” in git.”。这个配置针对git的正常使用仅需要配置一次…...
正则魔法:解码 return /^\d+$/.test(text) ? text : ‘0‘ 的秘密
🚀 正则魔法:解码 return /^\d$/.test(text) ? text : 0 的秘密 🌟 嘿,技术探险家们!👋 今天我们要破解一段看似简单的代码:return /^\d$/.test(text) ? text : 0。它藏在一个 Vue 前端组件中…...
[023-01-47].第47节:组件应用 - GetWay与 Sentinel 集成实现服务限流
SpringCloud学习大纲 一、需求说明: 实现网关cloudalibaba-sentinel-gateway9528模块保护cloudalibaba-provider-payment9001 二、编码实现: 2.1.建module: 新建模块,名称是:cloudalibaba-sentinel-gateway9528 2.2.改pom &l…...
【自用】NLP算法面经(5)
一、L1、L2正则化 正则化是机器学习中用于防止过拟合并提高模型泛化能力的技术。当模型过拟合时,它已经很好地学习了训练数据,甚至是训练数据中的噪声,所以可能无法在新的、未见过的数据上表现良好。 比如: 其中,x1和…...
AI视频生成产品体验分享(第2趴):Vidu、Hailuo、Runway、Pika谁更胜一筹?
hi,大家,继上次体验完可灵、即梦和pixverse,今天打算从产品经理的角度再研究下Vidu、Hailuo、Runway、Pika这几款产品!欢迎加入讨论! 一、产品简介 1. Vidu:国产自研的「一致性标杆」 📌官网…...
火绒终端安全管理系统V2.0——行为管理(软件禁用+违规外联)
火绒终端安全管理系统V2.0:行为管理策略分为软件禁用和违规外联两部分,能够管理终端用户软件的使用,以及终端用户违规连接外部网络的问题。 l 软件禁用 软件禁用策略可以选择软件名单的属性、添加软件名单以及设置发现终端使用禁用软件时的…...
台式机电脑组装---电脑机箱与主板接线
台式机电脑组装—电脑机箱与主板接线 1、机箱连接主板的跳线一般主要有USB 2.0、USB 3.0、前置音频接口(HD_AUDIO)以及POWER SW、RESET SW、POWER LED、HDD LED四个主板跳线,这些跳线分别的含义如下。 RESET SW:机箱重启按键;注:…...
【总结】常用API架构类型
引言 在现代软件开发中,API(应用程序编程接口)已经成为各类系统之间交互的核心。不同的 API 架构类型适用于不同的业务需求和技术场景,选择合适的架构可以提高系统的性能、可维护性和扩展性。本文将介绍几种常见的 API 架构类型,并分析它们的…...
ffmpeg库视频硬解码使用流程
FFmpeg 的硬解码(Hardware Decoding)通过调用 GPU 或专用硬件的编解码能力实现,能显著降低 CPU 占用率。 一、FFmpeg 支持的硬件解码类型 FFmpeg 原生支持多种硬件加速类型,具体由 AVHWDeviceType 定义,包括&…...
两个常用的用于读写和操作DXF文件C#库:netDxf 和 DXF.NET
netDxf 和 DXF.NET 是两个常用的C#库,用于读取、写入和操作DXF文件。以下是它们的详细介绍和用法示例。 1. netDxf 简介 netDxf 是一个开源的DXF文件读写库,支持AutoCAD DXF格式的读取和写入。它支持大多数DXF实体和对象,并且易于使用。 Gi…...
jmeter吞吐量控制器-Throughput Controller
jmeter吞吐量控制器-Throughput Controller 新增吞吐量控制器名词解释测试场景场景1:场景2:场景3场景4场景5场景6场景7场景8 测试结论 根据百分比执行不同的接口测试场景测试结果 新增吞吐量控制器 名词解释 Based on: Total Executions(总执行数)/Perc…...
windows 平台编译openssl
文章目录 准备环境安装perl安装NASM获取源码 源码编译配置编译 准备环境 安装perl 下载Perl 5.40.0.1 Portable zip strawberryperl 解压后设置系统环境变量 测试安装是否成功 perl --versionThis is perl 5, version 40, subversion 0 (v5.40.0) built for MSWin32-x64-m…...
【Linux】Makefile秘籍
> 🍃 本系列为Linux的内容,如果感兴趣,欢迎订阅🚩 > 🎊个人主页:【小编的个人主页】 >小编将在这里分享学习Linux的心路历程✨和知识分享🔍 >如果本篇文章有问题,还请多多包涵&a…...
Python散点图(Scatter Plot):数据探索的“第一张图表”
在数据可视化领域,散点图是一种强大而灵活的工具,它能够帮助我们直观地理解和探索数据集中变量之间的关系。本文将深入探讨散点图的核心原理、应用场景以及如何使用Python进行高效绘制。 后续几篇将介绍高级技巧、复杂应用场景。 Python散点图(Scatter Plot):高阶分析、散点…...
Spring AI Alibaba快速使用
AI 时代,Java 程序员也需要与时俱进,这两个框架必须掌握。 一个是 Spring AI一个是 Spring Alibaba AI。 Spring AI 是一个AI工程领域的应用程序框架,它的目标是将 Spring生态系统的设计原则应用于人工智能领域。 但是, Spring…...
Redis 跳表原理详解
一、引言 在 Redis 中,有序集合(Sorted Set)是一种非常重要的数据结构,它可以实现元素的有序存储和高效查找。而实现有序集合的底层数据结构之一就是跳表(Skip List)。跳表是一种随机化的数据结构ÿ…...
安全地自动重新启动 Windows 资源管理器Bat脚本
安全地自动重新启动 Windows 资源管理器脚本 可以直接运行的 Windows 批处理脚本,用于安全地自动重新启动 Windows 资源管理器。该脚本会在杀死资源管理器之前检查是否有其他进程正在使用资源管理器相关的文件。 Bat脚本 echo off title 资源管理器安全重启工具 co…...
【C++模板】
模板初阶 前言1.定义模板2.函数模板2.1定义2.2实例化函数模板2.3模板参数的匹配原则 3.类模板3.1类模板实例化 前言 模板是C中泛型编程的基础,一个模板就是一个创建类和函数的蓝图或公式。 1.定义模板 假定我们希望编写一个函数来比较两个值,并指出第…...
基于Debian搭建FTP服务器
操作系统 Debian-9.6.0-amd64,图形化安装 基础操作 1.软件安装管理 命令方式: 在线安装 sudo apt-get install vim/ifconfig 查看安装软件 dpkg -l 图形化桌面方式 : 通过“软件管理”工具管理 2.网络管理 /etc/network/interfaces 3.文本…...
如果我的项目是用ts写的,那么如何使用webpack的动态导入功能呢?
在 TypeScript 项目中使用 Webpack 的动态导入(Dynamic Imports)功能,需要结合 TypeScript 的语法和 Webpack 的配置。以下是具体实现方法和注意事项: 一、基础配置 1. 修改 tsconfig.json 确保 TypeScript 支持动态导入语法&am…...
构建高效的LinkedIn图像爬取工具
一. 项目背景与目标 LinkedIn上的用户头像数据可以用于多种场景,例如: 人才招聘:通过分析目标职位候选人的头像,了解其职业形象。市场调研:收集特定行业从业者的头像,用于分析职业群体的特征。学术研究&a…...
在windows下安装windows+Ubuntu16.04双系统(下)
这篇文章的内容主要来源于这篇文章,为正式安装windowsUbuntu16.04双系统部分。在正式安装前,若还没有进行前期准备工作(1.分区2.制作启动u盘),见《在windows下安装windowsUbuntu16.04双系统(上)》 二、正式安装Ubuntu …...
浅分析 PE3R 感知高效的三维重建
"近期,二维到三维感知技术的进步显著提升了对二维图像中三维场景的理解能力。然而,现有方法面临诸多关键挑战,包括跨场景泛化能力有限、感知精度欠佳以及重建速度缓慢。为克服这些局限,我们提出了感知高效三维重建框架&#…...
调和Django与Sql server2019的关系
数据库升级成sqlserver2019后,用户发现一些APP不能用了,检查发现是Django连接sqlserver的APP全部不能用了,页面打开都是500错误,进入Pycharm调试发现: 1.遇到错误1:django.db.backends.XXX错误 File "…...
【canvas】一键自动布局:如何让流程图节点自动找到最佳位置
一键自动布局:如何让流程图节点自动找到最佳位置 引言 在流程图、拓扑图和系统架构图设计中,节点布局往往是最令人头疼的问题。如果手动调整每个节点位置,不仅耗时费力,还难以保证美观性和一致性。本文将深入解析如何实现自动布…...
Flutter 学习之旅 之 flutter 使用 SQLite(sqflite) 实现简单的数据本地化 保存/获取/移除/判断是否存在 的简单封装
Flutter 学习之旅 之 flutter 使用 SQLite(sqflite) 实现简单的数据本地化 保存/获取/移除/判断是否存在 的简单封装 目录 Flutter 学习之旅 之 flutter 使用 SQLite(sqflite) 实现简单的数据本地化 保存/获取/移除/判断是否存在…...
[unity 组件] Content Size Fitter 横向填充不满解决办法
可以看到,当只有3个或者4个元素的时候,布局组件并没有将横向宽度占满来布局。之所以有此困惑的原因是我以为他的布局策略是,从左到右,从上至下,尽量占满空间,不够了再换行,其实不然。 5到6个元…...
Dify 项目开源大模型应用开发平台
Dify 是一款开源的大语言模型(LLM)应用开发平台,旨在简化生成式 AI 应用的创建、部署和持续优化流程。以下从多个维度对该项目进行详细介绍: 一、项目定义与核心功能 Dify 的核心定位是结合 后端即服务(BaaSÿ…...
使用 `pytest` 框架时,可以通过极限封装将 YAML 文件的读取、解析
在使用 pytest 框架时,可以通过极限封装将 YAML 文件的读取、解析和测试用例的通用逻辑封装成共享的方法或 fixture,从而减少重复代码。以下是详细的实现步骤和示例。 1. 封装 YAML 文件读取和解析 将 YAML 文件的读取和解析逻辑封装到一个工具函数中,供所有测试用例调用。…...
算法刷题记录——LeetCode篇(2) [第101~200题](持续更新)
(优先整理热门100及面试150,不定期持续更新,欢迎关注) 101. 对称二叉树 给你一个二叉树的根节点 root , 检查它是否轴对称。 示例 1: 输入:root [1,2,2,3,4,4,3] 输出:true示例 2: 输入&am…...