《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道普通数组篇中的六道题 第三道:轮转数组(中等) 第四道:除自身以外数组的乘积(中等) 第三道:轮转数组(中等) 方法一:使用额外的数…...
【面试题】【C语言】寻找两个正序数组的中位数
寻找两个正序数组的中位数 仅供学习 题目 算法时间复杂度 二分查找算法,时间复杂度为 O(log(min(m, n))),其中 m 和 n 分别是两个数组的长度。 子函数 查找两个数字的最大值 int max(int a, int b) {return a > b ? a : b; }查找两个数字的最小…...
原始的原型链是怎样玩的
带着问题看代码: 1、原始的继承是怎样实现继承的? A类的prototype 属性 B类的实例 2、实现继承后,连B类的中实例的属性(放在了A类的prototype中)和原型链的上的东西都可以用 3、A.prototype.constructor实际上已经指向…...
RabbitMQ高级篇(如何保证消息的可靠性、如何确保业务的幂等性、延迟消息的概念、延迟消息的应用)
文章目录 1. 消息丢失的情况2. 生产者的可靠性2.1 生产者重连2.2 生产者确认2.3 生产者确认机制的代码实现2.4 如何看待和处理生产者的确认信息 3. 消息代理(RabbitMQ)的可靠性3.1 数据持久化3.2 LazyQueue( 3.12 版本后所有队列都是 Lazy Qu…...
正点原子imx6ull-mini-Linux驱动之platform设备驱动实验(14)
我们在前面几章编写的设备驱动都非常的简单,都是对IO进行最简单的读写操作像I2C、 SPI、LCD 等这些复杂外设的驱动就不能这么去写了,Linux 系统要考虑到驱动的可重用性,因此提出了驱动的分离与分层这样的软件思路,在这个思路下诞生…...
z3基础学习
z3基础学习 z3是一个微软出品的开源约束求解器,能够解决很多种情况下的给定部分约束条件寻求一组满足条件的解的问题。 安装:pip install z3-solver 1. 简单使用 from z3 import * x Int(x) #创建名为x的int类型变量 y Int(y) solve(x y10,2*x…...
开发助手专业版,有反编译等多种功能
软件介绍 开发助手能够用来快速调试应用以及查看手机软硬件相关信息,包括:快速打开或关闭开发者选项中的选项。 将原来几十秒的操作缩短为一次点击。包括显示布局边界,显示 GPU 过度绘制。显示布局更新。强制 GPU 渲染 显示 GPU 视图更新&a…...
嵌入式初学-C语言-十一
#接嵌入式初学-C语言-十,以及部分例题# 循环结构 break和continue break 功能: 1. 用在switch中,用来跳出switch的case语句;如果case没有break,可能会产生case穿透。 2. 用在循环中(while、do..while、for..&#…...
浅谈几个常用OJ的注册方式
众所周知,好的OJ是成功的一半,但是有些英文OJ的注册很让人伤脑筋。 CodeForces 点进官网 戳这里 然后就会进入这个页面 在这一页里面里填写好信息即可 最后,一个邮件就会发到你的邮箱上,点击其中的链接即可激活账号 AtCoder …...
Html实现全国省市区三级联动
目录 前言 1.全国省市区的Json数据 2.找到Json数据文件(在此博文绑定资源)之后,放到resource目录下。 3.通过类加载器加载资源文件,读取Json文件 3.1 创建JsonLoader类 3.2 注入JsonLoader实体,解析Json文件 4.构建前端Html页面 5.通过…...
前端构建工具Webpack 与 Vite 大对比
在现代前端开发领域,构建工具扮演着至关重要的角色。它们不仅可以帮助我们管理项目依赖关系,还可以优化我们的代码,使其在生产环境中运行得更快更高效。其中两个最受欢迎的构建工具就是 Webpack 和 Vite。在这篇文章中,我们将深入…...
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⽂件(注…...
嵌入式学习---DAY17:共用体与位运算
链表剩余的一些内容 一、共用体 union 共用体名 名称首字母大写 { 成员表列; }; 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总结
可参考: https://zhuanlan.zhihu.com/p/695144946 蓝牙网关 参考: https://www.bilibili.com/read/cv28872282/ 蓝牙网关是一种特殊的网络设备,它能够实现蓝牙设备与互联网或其他类型网络之间的数据传输和通信。通过蓝牙网关,用户…...
了解关于标准化的知识
1.标准化组织 1.1国家标准化管理委员会(Standardization Administration of the Peoples Republic of China,简称SAC) TC--(Technical Committee) 技术委员会. SAC/TC,就是“国家标准化管理委员会”下属的一个专项或一个行业的“技术委员会或技术小组”&a…...
【云原生】数据库忘记密码怎么办?
相信很多人都会遇到在虚拟机中忘记数据库密码的情况,想必大家都很苦恼,所以今天给大家来讲讲数据库忘记密码了如何修改密码再登录数据库!!! 1、关闭数据库服务 systemctl stop mariadb 2、执行MySQL 服务器在启动时跳…...
Postman 接口测试详解
Postman 接口测试详解 Postman 接口测试详解1. Postman 基础知识1.1 什么是 Postman?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.等待状态(WAITING) 4.超时等待(TIMED_WAITING) 5.阻塞状态(BLOCKED) 6.终止状态(TERMINATED) 三.线程状态间的转换 四.总结 前言 线程状态及其状态转换…...
C++笔记之编译过程和面向对象
回顾: “abcd”//数据类型 字符串常量 const char *p"abc"; new STU const char *//8 指针的内存空间 int float 指针的内存空间 p 指针指向的内存空间 "abc" 取决于字符串长度 指针变量的内容一级指针 指针变量的地址二级指针 …...
ModuleNotFoundError: No module named ‘tqdm‘
报错信息: tqdm是一个快速、可扩展的Python进度条库,用于展示迭代器的长循环执行进度。 解决:通过以下命令安装 使用conda命令安装 conda install tqdm使用pip安装: pip install tqdm...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
