当前位置: 首页 > 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;…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...