LeetCode -Hot100 - 56. 合并区间

server/2025/1/1 15:30:08/

前言

本专栏主要通过“LeetCode 热题100”,来捡起自己本科阶段的算法知识与技巧。语言主要使用c++/java。如果同样正在练习LeetCode 热题100的朋友欢迎关注或订阅本专栏。有疑问欢迎留言交流~

题目描述

题目链接

给定一个整数数组 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
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 105

思路

解法一: 第一个思路想到的是直接利用现成的vector方法去实现,关键就是删除最后一个元素,然后插入到第一个元素中。代码如下:

class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();k = k % n; // 防止k大于n的情况,这样可以避免不必要的旋转for (int i = 0; i < k; ++i) {int temp = nums.back(); // 获取最后一个元素nums.pop_back(); // 删除最后一个元素nums.insert(nums.begin(), temp); // 在第一个位置插入该元素}}
};

提交,超出时间限制(看来还是不能投机取巧,不是)。原因很简单vector本质上还就是一个普通的动态数组,数据结构第一节将数组与链表的时候就讲过,list和数组的区别(一个方便插入,一个方便检索)。

解法二: 那第二个解法就是使用现成的list做法。但是既然改作list了,就不要去像上面一样,一个一个去删除,增加元素了.我们可以直接选取后面那一截链表,直接插到前面去。c++ 提供现成的双向链表list类。这边我也整理了 一些常用的list方法。有兴趣的朋友可以查看。list方法代码如下:

class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();if (n == 0) return;k = k % n; // 防止k大于n的情况,这样可以避免不必要的旋转// 将数组转换为链表list<int> linkedList(nums.begin(), nums.end());// 将链表的后k个元素移动到前面auto it = linkedList.end();advance(it, -k);  // 定位到倒数第k个元素linkedList.splice(linkedList.begin(), linkedList, it, linkedList.end());// 将链表转换回数组nums.assign(linkedList.begin(), linkedList.end());}
};

解法三:开辟一个新数组,去找其中的对应关系。直接复制一个数组。然后找出其中的一一对应关系即可。代码如下:

class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();k = k % n; // 防止k大于n的情况vector<int> copynums(nums);for (int i=0; i<n; ++i){nums[i] = copynums[(n-k+i)%n];}}
};

http://www.ppmy.cn/server/154378.html

相关文章

WPF编程excel表格操作

WPF编程excel表格操作 摘要NPOI安装封装代码测试代码 摘要 Excel操作几种方式 使用开源库NPOI(常用&#xff0c;操作丰富)使用Microsoft.Office.Interop.Excel COM组件(兼容性问题)使用OpenXml(效率高)使用OleDb(过时) NPOI安装 封装代码 using System; using System.IO; u…

关键客户转化为会员的重要性及 “开源 AI 智能名片 2 + 1 链动模式商城小程序” 在其中的应用剖析

摘要&#xff1a; 本文聚焦于商业运营中把关键客户转化为会员的重要意义&#xff0c;深入探讨在此过程中新兴技术与模式的作用。以 “开源 AI 智能名片 2 1 链动模式商城小程序” 为例&#xff0c;阐述其如何助力企业精准识别、转化关键客户为会员&#xff0c;实现营销的精准化…

指针学习-

指针基础 &#xff08;1&#xff09;p (int *) 1732——p指向地址为1732的int变量 &#xff08;2&#xff09;指针声明符不是指针的组成部分&#xff0c;p是指针变量而不是*p &#xff08;3&#xff09;不同类型的指针变量之间不能相互赋值 &#xff08;4&#xff09;指针初始…

【Rust自学】7.4. use关键字 Pt.2 :重导入与换国内镜像源教程

喜欢的话别忘了点赞、收藏加关注哦&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 7.4.1. 使用pub use重新导入名称 使用use将路径导入作用域内后。该名称在词作用域内是私有的。 以上一篇文章的代码为例&#xff1a; m…

嵌入式学习-QT-Day08

嵌入式学习-QT-Day08 八、数据库 1、准备工作 2、连接数据库 3、创建表 4、增删改 5、查询 5.1 全查 5.2 模糊查询 八、数据库 1、准备工作 Qt本身并没有数据库的功能&#xff0c;但是Qt支持调用其他主流的数据库产品&#xff0c;并且这些数据库产品指定了统一的Qt接口&#xf…

uniapp下拉选择组件

目录 背景 实现思路 代码实现 配置项 使用 尾巴 背景 最近遇到一个这样的需求&#xff0c;在输入框中输入关键字&#xff0c;通过接口查询到结果之后&#xff0c;以下拉框列表形式展现供用户选择。查询了下uni-app官网和项目中使用的uv-ui库&#xff0c;没找到符合条件的…

如何设置Edge浏览器访问软件

使用Edge浏览器访问分销ERP A\V系列软件时会出现各种报错&#xff0c;如何设置Edge浏览器使其正常访问&#xff0c;请看下面的具体操作。 一、打开Edge浏览器&#xff0c;点击右上角的 设置及其他&#xff0c;如图&#xff1a; 二、在弹出界面中&#xff0c;点击 扩展&#xff…

腾讯音乐:说说Redis脑裂问题?

Redis 脑裂问题是指&#xff0c;在 Redis 哨兵模式或集群模式中&#xff0c;由于网络原因&#xff0c;导致主节点&#xff08;Master&#xff09;与哨兵&#xff08;Sentinel&#xff09;和从节点&#xff08;Slave&#xff09;的通讯中断&#xff0c;此时哨兵就会误以为主节点…