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

消失的数字,旋转数组(leetcode 一题多解)

目录

一、消失的数字

思路一(暴力求解)代码实现:

思路二(数列的思想)代码实现:

思路三(异或的运用)代码实现:

 二、轮转数组

思路一(暴力求解)代码实现:

思路二使用额外的空间(以空间换时间)代码实现:

思路三(三步逆置)


一、消失的数字

思路如下图:

思路一(暴力求解)代码实现:

排序好后一一查找。

此处不建议使用该方法,因为时间复杂度过大。


int missingNumber(int* nums, int numsSize)
{int i = 0;int j = 0;int flag = -1;//利用冒泡排序思想进行排序for (i = 0; i < numsSize - 1; i++){for (j = 0; j < numsSize - 1 - i; j++){if (nums[j] > nums[j + 1]){int tmp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tmp;}}}//一个个查找for (i = 0; i < numsSize; i++){if (i != nums[i]){flag = i;break;}}return i;
}

思路二(数列的思想)代码实现:

此处代码就开始简化了:时间复杂度为O(N),先用上等差数列的公式求前num个数字之和,再一一减去nums数组中的元素,最后得到的就是消失的数字!

int missingNumber(int* nums, int numsSize)
{int i=0;int sum=0;//前numsSize个数字相加,等差数列求和sum = (numsSize+1)*numsSize/2;//减去nums数组中的所有值的和for(i=0;i<numsSize;i++){sum-=nums[i];}return sum;
}

思路三(异或的运用)代码实现:

利用了异或操作符
首先讲解一下这个操作符(^):
  这个操作符是对二进制来用的,相同为零相异为一
这个操作符有几个特点
  1.n^0 = n
  2.n^n = 0
  3.满足交换律,如:(a^b) ^ c =a^(b^c)

如果想知道更多操作符的使用请移步到:操作符(笔记)-CSDN博客

思路:用0先跟0~numsSize中数据异或,再跟nums数组中所有元素异或,最后的值就是所要找的值 

效果如下:

0^1^2^...中间有消失的数...^n ^1^2^...中间消失的数不在这里...^n = 0^中间有消失的数 =

中间有消失的数

int missingNumber(int* nums, int numsSize)
{int x = 0;int i = 0;//先跟0-numsSize中数据异或for (i = 1; i <= numsSize; i++){x = x ^ i;}//跟nums数组中数据异或for (i = 0; i < numsSize; i++){x = x ^ nums[i];}return x;}

 二、轮转数组

思路如下图所示

思路一(暴力求解)代码实现:

void rotate(int* nums, int numsSize, int k) {//如果k>=numsSize,则k=k%numsSize,减少循环次数if (k >= numsSize){k %= numsSize;}//轮转的次数for (int j = 1; j <= k; s++){//记录数组最后一个元素的值int tmp = nums[numsSize-1];//每一次的轮转数组的变化for (int i = numsSize - 1; i > 0; i--){nums[i] = nums[i - 1];	}//把记录下来的值赋给数组首元素nums[0] = tmp;}
}

思路二使用额外的空间(以空间换时间)代码实现:

牺牲存储空间为代价,直接在栈上开辟一块新的存储空间

void rotate(int* nums, int sz, int k)
{//开辟与nums数组一样大小的空间int* tmp = (int*)malloc(sizeof(int) * sz);int i = 0;//如果k>=size,则k=k%size,减少循环次数if (k >= sz){k %= sz;}//先把后sz-k-1个元素拷贝到tmp中去for (i = 0; i < k; i++){tmp[i] = nums[sz - k + i];}//再把前k-1个元素拷贝到tmp中去for (i = 0; i < sz-k; i++){tmp[k+i] = nums[i];}//最后,把tmp的内容拷贝到nums中去for (i = 0; i < sz; i++){nums[i] = tmp[i];}
}

思路三(三步逆置)

如果k>=numsSize时,取余数

因为,逆置8次和逆置1次效果是相同的

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) {if(k>=numsSize){k %= numsSize; // 如果k大于等于数组长度,先对k取余}reverse(nums, 0, numsSize - k - 1);//注意控制下标reverse(nums, numsSize - k, numsSize - 1);reverse(nums, 0, numsSize - 1);
}

相关文章:

消失的数字,旋转数组(leetcode 一题多解)

目录 一、消失的数字 思路一&#xff08;暴力求解&#xff09;代码实现&#xff1a; 思路二&#xff08;数列的思想&#xff09;代码实现&#xff1a; 思路三&#xff08;异或的运用&#xff09;代码实现&#xff1a; 二、轮转数组 思路一&#xff08;暴力求解&#xff09…...

肠道菌群16s检测粪便采样工具包 粪便采样套装

肠道菌群16s检测是一种常见的分子生物学技术&#xff0c;用于研究人体肠道中的微生物群落。该技术通过分析16s rRNA基因序列&#xff0c;可以快速、准确地鉴定并定量不同种类的肠道微生物。 肠道菌群16s检测通常通过采集粪便样本进行分析。在实验室中&#xff0c;通过提取微生物…...

实现领域驱动设计-07-领域服务

领域中的服务表示一个无状态的操作&#xff0c;它用于实现特定于某个领域的任务。当某个操作不适合放在聚合和值对象上时&#xff0c;为了避免过程式的编程方式&#xff0c;最好的方式便是使用领域服务来实现该操作。 什么是领域服务? 当领域中的某个操作过程或转换过程不是实…...

井盖位移传感器厂家批发,守护井盖安全

窨井盖广泛分布于城市街道&#xff0c;其管理效果直接反映了城市治理的现代化程度。根据住房和城乡建设部发布的《关于进一步加强城市窨井盖安全管理的通知》&#xff0c;全国各地需加强窨井盖的安全管理。作为市政基础设施的一个重要的组成部分&#xff0c;井盖的管理工作不仅…...

python命令行交互 引导用户选择宠物

字多不看&#xff0c;直接体验 代码 以下代码将在命令行中&#xff0c;引导用户选择一个或者多个宠物&#xff0c;并反馈用户选择的宠物 # -*- coding:UTF-8 -*- """ author: dyy contact: douyaoyuan126.com time: 2023/11/22 15:19 file: 在命令行中引导用户…...

Leetcode—167.两数之和 II - 输入有序数组【中等】

2023每日刷题&#xff08;四十一&#xff09; Leetcode—167.两数之和 II - 输入有序数组 实现代码 /*** Note: The returned array must be malloced, assume caller calls free().*/ int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {*returnSiz…...

MybatisPlus改造逻辑删除有多方便

MybatisPlus的逻辑删除可以有效保留历史数据。之前没有用逻辑删除的项目&#xff0c;想改造成逻辑删除总共需要几步&#xff1f; 答案&#xff1a;4步搞定 一、修改pom.xml的MybatisPlus版本&#xff08;注意版本兼容性&#xff09; <properties>...<!--<mybatis-…...

希尔伯特变换-matlab仿真

希尔伯特变换(hilbert transform)简介 在信号处理中我们常见的有傅里叶变换,用来分析频域信息,还有拉普拉斯变换和z变换,用于系统分析系统响应。短时傅里叶分析和小波分析用于时频分析。希尔伯特变换似乎听到的比较少。我因为最近在做信号幅度提取的时候看到可以用希尔伯…...

python字典的基本操作详解

Python字典是一种数据结构&#xff0c;它存储的是键值对&#xff08;key-value pair&#xff09;。在Python中&#xff0c;字典用于存储和组织数据&#xff0c;并且提供了快速查找和访问数据的方法。 以下是一些Python字典的基本操作&#xff1a; 创建字典&#xff1a; # 创…...

[ CSS ] 内容超出容器后 以...省略

内容超出容器后 以…省略 当前效果 代码 <template><div class"box">有志者&#xff0c;事竟成&#xff0c;破釜沉舟&#xff0c;百二秦关终属楚; 有心人&#xff0c;天不负&#xff0c;卧薪尝胆&#xff0c;三千越甲可吞吴</div> </templa…...

Java远程连接本地开源分布式搜索引擎ElasticSearch

文章目录 前言1. Windows 安装 Cpolar2. 创建Elasticsearch公网连接地址3. 远程连接Elasticsearch4. 设置固定二级子域名 前言 简单几步,结合Cpolar内网穿透工具实现Java远程连接操作本地Elasticsearch。 什么是elasticsearch&#xff1f;一个开源的分布式搜索引擎&#xff0…...

递归回溯剪枝-子集

LCR 079. 子集 - 力扣&#xff08;LeetCode&#xff09; 方法一 1. 决策树&#xff1a;对于决策树&#xff0c;思考的角度不同&#xff0c;画出的决策树也会不同&#xff0c;这道题可以从两个角度来画决策树。 2. 考虑全局变量的使用&#xff1a; 使用全局变量 List<List&…...

VC++、MFC中操作excel时,Rang和Rangs的区别是什么?

Rang 参考微软说明 作用 表示一个单元格、一行、一列、一个包含单个或若干连续单元格区域的选定单元格范围&#xff0c;或者一个三维区域。 说明 Range 的默认成员将不包含参数的调用转发至 Value 属性 如&#xff0c;someRange someOtherRange 等效于 someRange.Value …...

使用Rust开发小游戏

本文是对 使用 Rust 开发一个微型游戏【已完结】[1]的学习与记录. cargo new flappy 在Cargo.toml的[dependencies]下方增加: bracket-lib "~0.8.7" main.rs中: use bracket_lib::prelude::*;struct State {}impl GameState for State { fn tick(&mut self,…...

笔记二十一、使用路由search进行传递参数

21.1 父组件设置路由参数 <NavLink to{classify?param_A${this.state.name}&param_B${this.state.age}} className{this.activeStyle}>classify</NavLink> import React from "react"; import {NavLink, Outlet} from "react-router-dom"…...

python多线程和多进程

1.多线程 线程是程序执行的最小单位&#xff0c;一个进程至少有一个线程。 提高并发性。通过线程可方便有效地实现并发性。进程可创建多个线程来执行同一程序的不同部分。 进程之间不能共享内存&#xff0c;但线程之间共享内存非常容易。 Python 常用的多线程库有threading 和…...

VMware虚拟机网络配置详解

vmware为我们提供了三种网络工作模式&#xff0c;它们分别是&#xff1a;Bridged&#xff08;桥接模式&#xff09;、NAT&#xff08;网络地址转换模式&#xff09;、Host-Only&#xff08;仅主机模式&#xff09; 打开vmware虚拟机&#xff0c;我们可以在选项栏的“编辑”下的…...

VUE语法--img图片不显示/img的src动态赋值图片显示

1、问题概述 常见情景1&#xff1a;在VUE中使用img显示图片的时候&#xff0c;通过传参的方式传入图片的路径和名称&#xff0c;VUE不加载本地资源而是通过http://localhost:8080/...的地址去加载网络资源&#xff0c;从而出现了图片无法显示的情况。 常见情景2&#xff1a;针…...

springboot+vue智能企业设备管理系统05k50

智能设备管理系统主要是为了提高工作人员的工作效率和更方便快捷的满足用户&#xff0c;更好存储所有数据信息及快速方便的检索功能&#xff0c;对系统的各个模块是通过许多今天的发达系统做出合理的分析来确定考虑用户的可操作性&#xff0c;遵循开发的系统优化的原则&#xf…...

C++中的new、operator new与placement new

new operator new operator是我们常用的new。 new 和 delete 是用来在 堆上申请和释放空间的 &#xff0c;是 C 定义的 关键字&#xff0c;和 sizeof 一样。 实际 new / delete 和 malloc / free 最大的区别是&#xff0c;前者对于 自定义类型 除了可以开辟空间&#xff0c;…...

SITS2026多模态评测集深度解析(业界首份全栈评估框架白皮书)

第一章&#xff1a;SITS2026发布&#xff1a;多模态大模型评测集 2026奇点智能技术大会(https://ml-summit.org) SITS2026&#xff08;Singularity Intelligence Test Suite 2026&#xff09;是面向下一代多模态大模型的综合性基准评测集&#xff0c;由全球32家研究机构联合构…...

Harness CD + GitOps 架构师级实践:Canary 部署与多云交付

本文深入解析企业级 Harness CD(持续交付)与 GitOps 的高级架构设计原则与实践。作为 Harness 平台工程系列文章的第三篇,本文聚焦于服务/环境抽象模型、Canary + Progressive Delivery 策略、多云交付架构以及 GitOps at Scale 的设计考量,帮助架构师构建生产级的软件交付…...

Harness 安全左移 + CCM + AI 增强:企业级交付平台终极指南

本文深入解析 Harness 在安全左移、云成本管理以及 AI 增强交付领域的核心能力。作为 Harness 平台工程系列文章的第五篇,本文聚焦于 Security Testing Orchestration(STO)、Cloud Cost Management(CCM)FinOps 优化以及 AI 原生化的 DevOps 能力,帮助企业构建安全、成本可…...

Java 代码质量与静态分析最佳实践 2027:构建高质量软件

Java 代码质量与静态分析最佳实践 2027&#xff1a;构建高质量软件别叫我大神&#xff0c;叫我 Alex 就好。今天我们来聊聊 Java 代码质量与静态分析的最佳实践 2027&#xff0c;这些实践可以帮助我们构建更可靠、更可维护的软件。一、引言 代码质量是软件开发的核心要素之一&a…...

从‘滋滋’声到静音运行:A4988微步细分设置全解(附STM32/Arduino代码示例)

从‘滋滋’声到静音运行&#xff1a;A4988微步细分设置全解&#xff08;附STM32/Arduino代码示例&#xff09; 当你的3D打印机突然发出刺耳的啸叫&#xff0c;或是写字机器人在精细作画时出现恼人的抖动&#xff0c;背后往往隐藏着步进电机驱动器的配置玄机。A4988作为开源硬件…...

天气的所有状态

这个问题其实没有一个**全球统一“固定数量”**的天气状态标准&#xff0c;不同气象机构&#xff08;比如中国气象局、WMO、METAR航空天气&#xff09;分类都不一样。 但在嵌入式/APP开发里&#xff0c;一般会用一个**“工程上够用 覆盖常见情况”**的分类&#xff0c;大概 20…...

5分钟精通Waifu2x-Extension-GUI:便携版与安装版部署全攻略

5分钟精通Waifu2x-Extension-GUI&#xff1a;便携版与安装版部署全攻略 【免费下载链接】Waifu2x-Extension-GUI Video, Image and GIF upscale/enlarge(Super-Resolution) and Video frame interpolation. Achieved with Waifu2x, Real-ESRGAN, Real-CUGAN, RTX Video Super R…...

遗传算法与免疫算法求解物流配送中心选址问题,附详细注释与源码(Matlab编写

遗传算法 求解物流配送中心选址问题 源码详细注释(Matlab编写) 有两种解决选址问题代码&#xff0c;说明如下&#xff1a; 代码一&#xff1a;免疫算法物流配送中心选址 模型应用场景&#xff1a; 1.配送中心能够配送的总量≥各揽收站需求之和 2.一个配送中心可为多个揽收站配送…...

[具身智能-372]:具身智能大脑、小脑、肢体各自的功能分工、各自的技术栈、各自的难点

具身智能的“大脑-小脑-肢体”架构是工程界借鉴人类神经运动系统提出的分层解耦设计范式。该架构并非严格生物学复刻&#xff0c;而是为了在复杂系统中实现“认知-控制-执行”的模块化管理与协同优化。以下从功能分工、技术栈与核心难点三个维度进行系统拆解&#xff1a;&#…...

告别wlan0乱码!Cubieboard2+RTL8188ETV无线网卡完整配置与网络优化指南

Cubieboard2无线网络终极优化&#xff1a;从随机命名到稳定高速的RTL8188ETV实战指南 当你兴奋地将RTL8188ETV无线网卡插入Cubieboard2的USB接口&#xff0c;却发现系统生成的网卡名称像wlxe0b2f14aba0d这样的随机字符串时&#xff0c;是否感到脚本编写和网络管理变得异常麻烦&…...