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

《LeetCode热题100》---<5.②普通数组篇五道>

本篇博客讲解LeetCode热题100道普通数组篇中的六道题

第三道:轮转数组(中等)

第四道:除自身以外数组的乘积(中等)

第三道:轮转数组(中等)

 方法一:使用额外的数组

class Solution {public void rotate(int[] nums, int k) {int len = nums.length;int[] newArr = new int[len];for (int i = 0; i < len; ++i) {newArr[(i + k) % len] = nums[i];}System.arraycopy(newArr, 0, nums, 0, len);}
}

 1.新建一个nums数组长度的数组。

2.轮转k次。因此我们将从(i + k) % len开始,将nums数组中的值依次赋值给新数组。

3.最终将新数组中的值拷贝回原来的数组。

时间复杂度: O(n),其中 n 为数组的长度。

空间复杂度: O(n)。

方法二:数组翻转

​​​​​​class Solution {public void rotate(int[] nums, int k) {k %= nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}public void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start += 1;end -= 1;}}
}

翻转的思想:轮转k个位置,那么也就相当于先将数组翻转。之后再翻转(0,k-1)这个位置的元素。再翻转(k,n-1)这个位置的元素。下如图演示。

第四道:除自身以外数组的乘积(中等)

 方法一:前缀之积乘以后缀之积

class Solution {public int[] productExceptSelf(int[] nums) {int length = nums.length;// L 和 R 分别表示左右两侧的乘积列表int[] L = new int[length];int[] R = new int[length];int[] answer = new int[length];// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 '0' 的元素,因为左侧没有元素,所以 L[0] = 1L[0] = 1;for (int i = 1; i < length; i++) {L[i] = nums[i - 1] * L[i - 1];}// R[i] 为索引 i 右侧所有元素的乘积// 对于索引为 'length-1' 的元素,因为右侧没有元素,所以 R[length-1] = 1R[length - 1] = 1;for (int i = length - 2; i >= 0; i--) {R[i] = nums[i + 1] * R[i + 1];}// 对于索引 i,除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for (int i = 0; i < length; i++) {answer[i] = L[i] * R[i];}return answer;}
}

1.新建一两个数组长度为nums的长度。一个L存前缀之积,一个R存后缀之积

2.L[i] 表示索引 i 左侧所有元素的乘积,因为索引为 '0' 的元素左侧没有元素, 所以 L[0] = 1

3.for循环从1开始,计算每个元素的前缀之积 L[i] = nums[i - 1] * L[i - 1];

4.再从后往前遍历计算后缀之积。R[length - 1] = 1;。R[i] = nums[i + 1] * R[i + 1];得到后缀之积。

5.     for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }

6.最终返回answer。

时间复杂度:O(N),其中 N 指的是数组 nums 的大小。预处理 L 和 R 数组以及最后的遍历计算都是 O(N) 的时间复杂度。
空间复杂度:O(N),其中 N 指的是数组 nums 的大小。使用了 L 和 R 数组去构造答案,L 和 R 数组的长度为数组 nums 的大小 

方法二:方法一的进阶,空间复杂度 O(1) 的方法 

class Solution {public int[] productExceptSelf(int[] nums) {int length = nums.length;int[] answer = new int[length];// answer[i] 表示索引 i 左侧所有元素的乘积// 因为索引为 '0' 的元素左侧没有元素, 所以 answer[0] = 1answer[0] = 1;for (int i = 1; i < length; i++) {answer[i] = nums[i - 1] * answer[i - 1];}// R 为右侧所有元素的乘积// 刚开始右边没有元素,所以 R = 1int R = 1;for (int i = length - 1; i >= 0; i--) {// 对于索引 i,左边的乘积为 answer[i],右边的乘积为 Ranswer[i] = answer[i] * R;// R 需要包含右边所有的乘积,所以计算下一个结果时需要将当前值乘到 R 上R *= nums[i];}return answer;}
}

1.新建一个answer数组长度为nums的长度。

2.answer[i] 表示索引 i 左侧所有元素的乘积,因为索引为 '0' 的元素左侧没有元素, 所以 answer[0] = 1

3.for循环从1开始,计算每个元素的前缀之积answer[i] = nums[i - 1] * answer[i - 1];

4.再从后往前遍历计算后缀之积。R 为右侧所有元素的乘积。开始R=1。从n-1开始遍历。令

answer[i] = answer[i] * R;得到最终答案。R *= nums[i];得到后缀之积。

5.最终返回answer。

时间复杂度:O(N),其中 N 指的是数组 nums 的大小。分析与方法一相同。
空间复杂度:O(1),输出数组不算进空间复杂度中,因此我们只需要常数的空间存放变量。

相关文章:

《LeetCode热题100》---<5.②普通数组篇五道>

本篇博客讲解LeetCode热题100道普通数组篇中的六道题 第三道&#xff1a;轮转数组&#xff08;中等&#xff09; 第四道&#xff1a;除自身以外数组的乘积&#xff08;中等&#xff09; 第三道&#xff1a;轮转数组&#xff08;中等&#xff09; 方法一&#xff1a;使用额外的数…...

【面试题】【C语言】寻找两个正序数组的中位数

寻找两个正序数组的中位数 仅供学习 题目 算法时间复杂度 二分查找算法&#xff0c;时间复杂度为 O(log(min(m, n)))&#xff0c;其中 m 和 n 分别是两个数组的长度。 子函数 查找两个数字的最大值 int max(int a, int b) {return a > b ? a : b; }查找两个数字的最小…...

原始的原型链是怎样玩的

带着问题看代码&#xff1a; 1、原始的继承是怎样实现继承的&#xff1f; A类的prototype 属性 B类的实例 2、实现继承后&#xff0c;连B类的中实例的属性&#xff08;放在了A类的prototype中&#xff09;和原型链的上的东西都可以用 3、A.prototype.constructor实际上已经指向…...

RabbitMQ高级篇(如何保证消息的可靠性、如何确保业务的幂等性、延迟消息的概念、延迟消息的应用)

文章目录 1. 消息丢失的情况2. 生产者的可靠性2.1 生产者重连2.2 生产者确认2.3 生产者确认机制的代码实现2.4 如何看待和处理生产者的确认信息 3. 消息代理&#xff08;RabbitMQ&#xff09;的可靠性3.1 数据持久化3.2 LazyQueue&#xff08; 3.12 版本后所有队列都是 Lazy Qu…...

正点原子imx6ull-mini-Linux驱动之platform设备驱动实验(14)

我们在前面几章编写的设备驱动都非常的简单&#xff0c;都是对IO进行最简单的读写操作像I2C、 SPI、LCD 等这些复杂外设的驱动就不能这么去写了&#xff0c;Linux 系统要考虑到驱动的可重用性&#xff0c;因此提出了驱动的分离与分层这样的软件思路&#xff0c;在这个思路下诞生…...

z3基础学习

z3基础学习 ​ z3是一个微软出品的开源约束求解器&#xff0c;能够解决很多种情况下的给定部分约束条件寻求一组满足条件的解的问题。 安装&#xff1a;pip install z3-solver 1. 简单使用 from z3 import * x Int(x) #创建名为x的int类型变量 y Int(y) solve(x y10,2*x…...

开发助手专业版,有反编译等多种功能

软件介绍 开发助手能够用来快速调试应用以及查看手机软硬件相关信息&#xff0c;包括&#xff1a;快速打开或关闭开发者选项中的选项。 将原来几十秒的操作缩短为一次点击。包括显示布局边界&#xff0c;显示 GPU 过度绘制。显示布局更新。强制 GPU 渲染 显示 GPU 视图更新&a…...

嵌入式初学-C语言-十一

#接嵌入式初学-C语言-十,以及部分例题# 循环结构 break和continue break 功能&#xff1a; 1. 用在switch中&#xff0c;用来跳出switch的case语句&#xff1b;如果case没有break&#xff0c;可能会产生case穿透。 2. 用在循环中&#xff08;while、do..while、for..&#…...

浅谈几个常用OJ的注册方式

众所周知&#xff0c;好的OJ是成功的一半&#xff0c;但是有些英文OJ的注册很让人伤脑筋。 CodeForces 点进官网 戳这里 然后就会进入这个页面 在这一页里面里填写好信息即可 最后&#xff0c;一个邮件就会发到你的邮箱上&#xff0c;点击其中的链接即可激活账号 AtCoder …...

Html实现全国省市区三级联动

目录 前言 1.全国省市区的Json数据 2.找到Json数据文件(在此博文绑定资源)之后&#xff0c;放到resource目录下。 3.通过类加载器加载资源文件&#xff0c;读取Json文件 3.1 创建JsonLoader类 3.2 注入JsonLoader实体&#xff0c;解析Json文件 4.构建前端Html页面 5.通过…...

前端构建工具Webpack 与 Vite 大对比

在现代前端开发领域&#xff0c;构建工具扮演着至关重要的角色。它们不仅可以帮助我们管理项目依赖关系&#xff0c;还可以优化我们的代码&#xff0c;使其在生产环境中运行得更快更高效。其中两个最受欢迎的构建工具就是 Webpack 和 Vite。在这篇文章中&#xff0c;我们将深入…...

Ubuntu-22.04环境搭建

安装wget(一般ubuntu会自带) sudo apt-get install wget 更换国内软件源 先备份原来的/etc/apt/source.list⽂件 sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak 防止修改错误 导致无可挽回 将下列国内镜像源 写入原来的/etc/apt/source.list⽂件&#xff08;注…...

嵌入式学习---DAY17:共用体与位运算

链表剩余的一些内容 一、共用体 union 共用体名 名称首字母大写 { 成员表列&#xff1b; }&#xff1b; union Demo {int i;short s;char c; }; int main(void) {union Demo d;d.i 10;d.s 100;d.c 200;printf("%d\n", sizeof(d)); /…...

蓝牙网关和蓝牙MESH总结

可参考&#xff1a; https://zhuanlan.zhihu.com/p/695144946 蓝牙网关 参考&#xff1a; https://www.bilibili.com/read/cv28872282/ 蓝牙网关是一种特殊的网络设备&#xff0c;它能够实现蓝牙设备与互联网或其他类型网络之间的数据传输和通信。通过蓝牙网关&#xff0c;用户…...

了解关于标准化的知识

1.标准化组织 1.1国家标准化管理委员会(Standardization Administration of the Peoples Republic of China&#xff0c;简称SAC) TC--(Technical Committee) 技术委员会. SAC/TC,就是“国家标准化管理委员会”下属的一个专项或一个行业的“技术委员会或技术小组”&a…...

【云原生】数据库忘记密码怎么办?

相信很多人都会遇到在虚拟机中忘记数据库密码的情况&#xff0c;想必大家都很苦恼&#xff0c;所以今天给大家来讲讲数据库忘记密码了如何修改密码再登录数据库&#xff01;&#xff01;&#xff01; 1、关闭数据库服务 systemctl stop mariadb 2、执行MySQL 服务器在启动时跳…...

Postman 接口测试详解

Postman 接口测试详解 Postman 接口测试详解1. Postman 基础知识1.1 什么是 Postman&#xff1f;1.2 Postman 的主要功能 2. 安装与设置2.1 安装 Postman2.2 创建 Postman 账户 3. Postman 的基本操作3.1 创建和发送请求3.2 解析响应数据3.3 使用环境和变量 4. 进阶功能4.1 编写…...

【JavaEE】线程状态

目录 前言 一.线程状态图 二.线程状态 1.初始状态(NEW) 2.运行状态(RUNNING) 3.等待状态&#xff08;WAITING) 4.超时等待&#xff08;TIMED_WAITING) 5.阻塞状态&#xff08;BLOCKED) 6.终止状态(TERMINATED) 三.线程状态间的转换 四.总结 前言 线程状态及其状态转换…...

C++笔记之编译过程和面向对象

回顾&#xff1a; “abcd”//数据类型 字符串常量 const char *p"abc"; new STU const char *//8 指针的内存空间 int float 指针的内存空间 p 指针指向的内存空间 "abc" 取决于字符串长度 指针变量的内容一级指针 指针变量的地址二级指针 …...

ModuleNotFoundError: No module named ‘tqdm‘

报错信息&#xff1a; tqdm是一个快速、可扩展的Python进度条库&#xff0c;用于展示迭代器的长循环执行进度。 解决&#xff1a;通过以下命令安装 使用conda命令安装 conda install tqdm使用pip安装&#xff1a; pip install tqdm...

东京电影节公布2024年竞赛片评审团成员并对其业绩分别进行评介 没什么含金量

第37届东京国际电影节竞赛单元评审团名单正式公布。 周五&#xff0c;电影节组织者宣布&#xff0c;香港电影制片人杜琪峰、匈牙利电影制片人伊尔迪科恩耶迪、日本女演员桥本爱和法国女演员基娅拉马斯楚安尼将与之前宣布的评审团主席梁朝伟一起担任 2024 年主竞赛评审团成员。 …...

智能景区垃圾识别系统:基于YOLO的深度学习实现

基于深度学习的景区垃圾识别系统&#xff08;UI界面YOLOv8/v7/v6/v5代码训练数据集&#xff09; 1. 引言 景区垃圾识别是环保管理的重要任务之一。传统的人工清理方式效率低、成本高&#xff0c;而借助深度学习技术可以实现自动化的垃圾检测与识别&#xff0c;提高景区的清洁…...

ventoy和微pe可以共存吗?ventoy和pe共存使用教程

Ventoy新一代多系统启动U盘解决方案。国产开源U盘启动制作工具&#xff0c;支持Legacy BIOS和UEFI模式&#xff0c;理论上几乎支持任何ISO镜像文件&#xff0c;支持加载多个不同类型的ISO文件启动&#xff0c;无需反复地格式化U盘&#xff0c;插入U盘安装写入就能制作成可引导的…...

如何获取和安装SSL证书

SSL&#xff08;Secure Sockets Layer&#xff09;证书是用于加密网站服务器和客户端之间通信的一种数字证书。它通过HTTPS协议保护数据传输的安全性&#xff0c;防止数据被窃听或篡改。本文将指导您如何为您的网站获取并安装SSL证书。 步骤1&#xff1a;选择SSL证书提供商 首…...

makefile在IC设计中的使用笔记

1 makefile在IC设计中的地位 关于makefile的详细介绍可以参考第一个连接&#xff0c;里面的内容很多也很详细。但在数字IC设计中&#xff0c;并不会把所有的用法都用到&#xff0c;下面记录一下主要用到的规则。 2 IC设计涉及到的主要用法 2.1 变量的定义和使用 在makefile…...

Suno声称在受版权保护的音乐上训练模型属于“合理使用“

继美国唱片业协会&#xff08;RIAA&#xff09; 最近对音乐生成初创公司 Udio 和 Suno 提起诉讼之后&#xff0c;Suno 在周四提交的一份法庭文件中承认&#xff0c;该公司确实使用了受版权保护的歌曲来训练其人工智能模型。但它声称&#xff0c;根据合理使用原则&#xff0c;这…...

Java | Leetcode Java题解之第316题去除重复字母

题目&#xff1a; 题解&#xff1a; class Solution {public String removeDuplicateLetters(String s) {boolean[] vis new boolean[26];int[] num new int[26];for (int i 0; i < s.length(); i) {num[s.charAt(i) - a];}StringBuffer sb new StringBuffer();for (in…...

Taro学习记录

一、安装taro-cli 二、项目文件 三、项目搭建 1、Eslint配置 在项目生成的 .eslintrc 中进行配置 {"extends": ["taro/react"], //一个配置文件&#xff0c;可以被基础配置中的已启用的规则继承"parser": "babel/eslint-parser…...

Spring Cache框架详解

Spring Cache框架详解 Spring Cache是Spring框架提供的一个强大的缓存抽象层&#xff0c;旨在简化缓存技术的集成和使用。自Spring 3.1版本开始&#xff0c;Spring Cache就被引入以支持在Spring应用程序中添加缓存功能。随着Spring版本的迭代&#xff0c;Spring Cache的功能日…...

解决Html iframe 内嵌video标签导致视频无法全屏展示的问题

原因&#xff1a; 由于浏览器的安全策略所限制的。为了防止恶意网站利用全屏播放功能进行滥用或欺骗用户&#xff0c;浏览器对iframe中的视频播放做了限制。 在iframe标签中播放视频时&#xff0c;浏览器会根据安全策略阻止视频全屏播放。这是因为iframe标签中的内容被认为是第…...