首页 > 其他分享 >《LeetCode热题100》---<5.②普通数组篇五道>

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

时间:2024-08-06 21:53:58浏览次数:17  
标签:nums int 元素 --- length 数组 answer 100 热题

本篇博客讲解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] = 1
        L[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] = 1
        R[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] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素,所以 R = 1
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i,左边的乘积为 answer[i],右边的乘积为 R
            answer[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),输出数组不算进空间复杂度中,因此我们只需要常数的空间存放变量。

标签:nums,int,元素,---,length,数组,answer,100,热题
From: https://blog.csdn.net/m0_73456341/article/details/140881538

相关文章

  • python爬虫预备知识三-多进程
    python实现多进程的方法:fork、multiprocessing模块创建多进程。os.fork方法os.fork方法只适合于unix/linux系统,不支持windows系统。fork方法调用一次会返回两次,原因在于操作系统将当前进程(父进程)复制出一份进程(子进程),这两个进程几乎完全相同,fork方法分别在父进程和子进程中......
  • Python-记录一次迭代求和
    importitertoolsdefget_result(hope,list_input):""":paramhope:#期望相加所得参数:paramlist_input:#所有数值:return:"""defgenerate_combination(items,length):forcombinationinitertools.co......
  • xlsx-js-style 如何配置表格样式
    xlsx-js-style是一个用于处理Excel文件的JavaScript库,基于xlsx库并添加了对样式的支持。通过xlsx-js-style,你可以设置单元格的字体、背景、边框等样式。下面是如何使用xlsx-js-style库配置表格样式的步骤。1.安装库首先,确保你已经安装了xlsx-js-style库:npminstal......
  • 【Material-UI】按钮组件中的实验性API:Loading按钮详解
    文章目录一、LoadingButton组件概述1.组件介绍2.基本用法二、LoadingButton组件的高级用法1.自定义加载指示器2.图标与加载位置三、已知问题与解决方法1.Chrome翻译工具与LoadingButton的兼容性问题四、实用性与未来展望1.应用场景2.未来展望五、总结......
  • dc-2靶机
    下载靶机dc-2先找靶机nmap-sV10.204.11.0/24先广泛的找一下再细查一下nmap-A-p-10.204.11.3开了个80端口又有一个ssh登陆端口我们先查看一下端口服务发现无法访问解析失败我们可以配置/etc/hosts文件再主机配置C:\Windows\System32\drivers\etc没有权限的话右键更......
  • 【论文笔记】Cross-Domain WiFi Sensing with Channel State Information: A Survey
    Cross-DomainWiFiSensingwithChannelStateInformation:ASurveyIntroduction检测领域:检测领域里,大部分用的阈值检测或者简单的学习算法,例如SVM。fallsRT-Fall:Areal-timeandcontactlessfalldetectionsystemwithcommodityWiFidevicesWiFall:Device-fr......
  • ARM Cortex-M3中断简介
    目录中断优先级分组三个系统中断优先级配置寄存器SHPR1SHPR2SHPR3三个中断屏蔽寄存器PRIMASKFAULTMASKBASEPRI中断优先级分组ARMCortex-M内核的MCU具有一个用于中断管理的嵌套向量中断控制器(NVIC,全称:Nestedvectoredinterruptcontroller)。ARMCortex-M的NVIC最大可支持......
  • Docker-Compose单机容器集群编排工具
    目录容器编排管理与传统的容器管理的区别什么Docker-Compose?Docker-Compose的简介Docker-Compose的作用Docker-compose的三大概念什么YAML文件?YAML文件介绍使用YAML时的注意事项YAML文件的基本数据结构Docker-Compose配置常用字段Docker-Compose常用命令我们知道......
  • 【多线程-从零开始-肆】线程安全、加锁和死锁
    进程状态进程状态:就绪:正在CPU上执行,或者随时可以去CPU上执行阻塞:暂时不能参与CPU的执行Java的线程,对应状态做了更详细的区分,不仅仅是就绪和阻塞了六种状态:NEW当前Thread对象虽然有了,但是内核的线程还没有(还没调用过start)TERMINATE当前Thread对......
  • 【多线程-从零开始-伍】volatile关键字和内存可见性问题
    volatile关键字importjava.util.Scanner;publicclassDemo2{privatestaticintn=0;publicstaticvoidmain(String[]args){Threadt1=newThread(()->{while(n==0){//啥都不写......