《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),输出数组不算进空间复杂度中,因此我们只需要常数的空间存放变量。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/389758.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vscode+cmake+msys2工具链配置

1、msys2下载编译器和cmake工具 pacman -S mingw-w64-x86_64-toolchain pacman -S mingw-w64-x86_64-cmaketoolchain包中包含很多不必要的工具包&#xff0c;应该可以指定具体的工具g&#xff0c;gcc&#xff0c;mingw32-make的下载&#xff0c;详细命令请自行搜索。 2、将 m…

QT 应用程序输出中文乱码

一 &#xff0c;选择文本编码 1. 点击编辑再点击Select Encoding选择编码 2 .在弹出的窗口&#xff0c;选择UTF-8再点击按编码保存即可 3. 重新编译&#xff0c;可以发现中文乱码问题解决

思维+dfs,CF 269C - Flawed Flow

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 269C - Flawed Flow 二、解题报告 1、思路分析 考虑源点相连的边的方向是确定的&#xff0c;因为流量是从源点往外流的 我们设cap[u] 为 和u相连边的容量和&#xff0c;显然入边容量要和出边容量相等&…

jvm调优参数

JVM调优是指调整JVM的参数&#xff0c;以优化Java程序的性能。以下是一些常用的JVM调优方法&#xff1a; 1.堆内存大小&#xff1a;通过-Xms和-Xmx参数设置JVM的初始堆内存和最大堆内存。堆内存太小会导致频繁GC&#xff0c;太大则可能导致内存利用率不高。 2.新生代与老年…

OS_操作系统的运行环境

2024.06.11:操作系统的运行环境学习笔记 第3节 操作系统的运行环境 3.1 操作系统引导3.2 操作系统内核3.2.1 内核资源管理3.2.2 内核基本功能 3.3 CPU的双重工作模式3.3.1 CPU处于用户态&#xff08;目态&#xff09;3.3.2 CPU处于内核态&#xff08;管态&#xff09; 3.4 特权…

鸿蒙Scroll布局,横向与纵向

注意&#xff0c;当横向scroll时&#xff0c;直接子元素的宽&#xff0c;不能100%&#xff0c; 当纵向scroll时&#xff0c;直接子元素的高&#xff0c;不能100%​​​​​​​ 1、纵向代码&#xff1a; 方法1&#xff1a;用数值计算&#xff0c;来设置中间的高度&#xff1a; …

nginx负载均衡、java、tomcat装包

一、nginx 七层负载均衡 1、七层负载均衡基础配置 2、负载均衡状态 [rootserver]# vim /usr/local/nginx/conf/nginx.confworker_processes 1;event {worker_connections 1024&#xff1b;}http { # 七层负载均衡支持http、ftp协议include mime.types;default_type app…

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

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

ModuleNotFoundError: No module named ‘tqdm‘

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

【JVM】垃圾回收机制、算法和垃圾回收器

什么是垃圾回收机制 为了让程序员更加专注于代码的实现&#xff0c;而不用过多的考虑内存释放的问题&#xff0c;所以在Java语言中&#xff0c;有了自动的垃圾回收机制&#xff0c;也是我们常常提及的GC(Garbage Collection) 有了这个垃圾回收机制之后&#xff0c;程序员只需…

Spring学习笔记1

今天内容:配置maven 搭建了springboot项目 约定大于配置&#xff08;它默认的框架优先级比配置的要高&#xff0c;基本全都用它所默认的框架只有特殊需求的时候才会修改一小部分。&#xff09; IOC Spring IOC 管理项目中java bean的生命周期 在项目运行阶段&#xff0c;…

操作系统与进程简单介绍

操作系统与进程 操作系统进程 操作系统 上一篇博客中介绍了操作系统到底层硬件它们之间的一个关系&#xff0c;那么还是这张图 操作系统到用户它们之间的关系又是如何的呢&#xff1f; 又回到了最根本的问题上&#xff1a;为什么要有操作系统呢&#xff1f; 1、向下管理好软…

敦煌文化主题页面 HTML,CSS,Javascript 源码分享

使用技术&#xff1a;HTML&#xff0c;CSS&#xff0c;JavaScript 项目亮点&#xff1a;加入了大量的CSS动画效果&#xff0c;以及JS交互效果&#xff0c;水平适合初学者以及大学生&#xff0c;包含登录注册页 需要的可以dd&#xff0c; 绿泡泡&#xff1a;ColdDayOne

为面试准备的一些内容

开发中使用了什么技术&#xff1f; mvvm、compose、livedata、单例模式、工厂模式、弱引用、线程池、Handler。 对于项目一开始我们打算使用aosp原生的管控方式&#xff0c;如UsageStatManager获取每个app的使用时长&#xff0c;和使用PackageManager的setPackagesSuspended方…

一文弄清Java的四大引用及其两大传递

开场白 Hello大家好呀&#xff0c;我是CodeCodeBond✊最近在复习很多很多的基础知识&#xff0c;有了很多新的感悟~ 话不多说&#xff0c;直接发车✈ 四大引用 问题切入点 在学习 Thread线程利用ThreadLocalMap实现线程的本地内存&#xff08;变量副本&#xff09;的时候&…

mac配置git的sshkey

在MAC中配置Git的SSH Key&#xff1a; 1.打开终端 2.生成SSH密钥&#xff0c;输入以下命令&#xff1a; ssh-keygen -t rsa -b 4096 -C “你自己的账号电子邮件地址” 按回车键后&#xff0c;系统会提示你输入文件保存路径&#xff0c;默认为~/.ssh/id_rsa直接按回车键使用默…

Mybatis实战:#{} 和 ${}的使用区别和数据库连接池

一.#{} 和 ${} #{} 和 ${} 在MyBatis框架中都是用于SQL语句中参数替换的标记&#xff0c;但它们在使用方式和处理参数值上存在一些显著的区别。 #{}的作用&#xff1a; #{} 是MyBatis中用于预编译SQL语句的参数占位符。它会将参数值放入一个预编译的PreparedStatement中&am…

Java语言程序设计——篇十一(2)

&#x1f33f;&#x1f33f;&#x1f33f;跟随博主脚步&#xff0c;从这里开始→博主主页&#x1f33f;&#x1f33f;&#x1f33f; 欢迎大家&#xff1a;这里是我的学习笔记、总结知识的地方&#xff0c;喜欢的话请三连&#xff0c;有问题可以私信&#x1f333;&#x1f333;&…

MySQL(8.0)数据库安装和初始化以及管理

1.MySQL下载安装和初始化 1.下载安装包 下载地址&#xff1a;https://downloads.mysql.com/archives/get/p/23/file/mysql-8.0.33-1.el7.x86_64.rpm-bundle.tar wget https://downloads.mysql.com/archives/get/p/23/file/mysql-8.0.33-1.el7.x86_64.rpm-bundle.tar 2.解压…

数据同步策略概览

数据同步在业务开发中比较普遍&#xff0c;例如 订阅MySQL的binlog将数据同步至异构数据库。数据同步方案需要考虑一下几点&#xff1a; 数据实时性要求数据量级是否有数据转换逻辑 可分为两种模式 发布订阅模式&#xff1a;分为订阅数据库log还是订阅应用层发的消息点对点模…