小工具      在线工具  汉语词典  css  js  c++  java

在这里插入图片描述

前言

今天开始我将陆续为大家更新面试经典150题中较难理解的题目。今天我为大家分享的是,除自身以外数组的乘积、跳跃游戏| 和 跳跃游戏||。

除自身以外数组的乘积

除自身以外数组的乘积

要求

给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法,且在 O(n) 时间复杂度内完成此题

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

class Solution {
    
    public int[] productExceptSelf(int[] nums) {
    

    }
}

思路

按照一般的思路,我们可能会想:先将数组中所有的元素相乘得到一个sum,然后再遍历一遍数组,answer[i] = sum / nums[i],如果nums[i] = 0,answer[i] = sum。但是这个题目要求我们不使用除法,那么我们该怎么办呢?因为是除自身以外的数组的乘积,自身以外的数组被分为左右两部分,我们只需要将 左边部分数组元素的乘积 x 右边部分数组元素的乘积 就得到除自身以外的数组的乘积。所以我们可以使用两个数组L和R来分别存储数组第 i 个元素左边部分数组元素的乘积和右边部分数组元素的乘积,最后再遍历一遍数组,answer[i] = L[i] * R[i]。

在这里插入图片描述

代码

class Solution {
    
    public int[] productExceptSelf(int[] nums) {
    
        int n = nums.length;
        int[] answer = new int[n];
        int[] L = new int[n];
        int[] R = new int[n];
        L[0] = 1;
        for(int i = 1; i < n; i++) {
    
        //L[i]等于前i-2个数的乘积乘上第i-1个数
            L[i] = L[i-1] * nums[i-1];
        } 
        R[n-1] = 1;
        for(int i = n - 2; i >= 0; i--) {
    
        //R[i]等于后 length-i-2 个数的乘积乘上第 length-i-1个数
            R[i] = R[i+1] * nums[i+1];
        }

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

        return answer;
    }
}

在这里插入图片描述

跳跃游戏|

跳跃游戏|

要求

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1:

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:

输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

class Solution {
    
    public int jump(int[] nums) {
    

    }
}

题解

其实这个题目可以换一种理解方式:在某位置的跳跃范围内时候有某一位置可以跳跃到最后一个下标处。我们可以使用 rightmost 来记录在某位置的跳跃范围内的最大跳跃位置, 最大跳跃位置 = i + nums[i] 如果 rightmost >= length-1,那么说明可以到达最后一个下标处。

在这里插入图片描述

代码

class Solution {
    
    public boolean canJump(int[] nums) {
    
        int n = nums.length;
        int rightmost = 0;
        for(int i = 0; i < n; i++) {
    
            if(i <= rightmost) {
    
                rightmost = Math.max(rightmost,i + nums[i]);
                if(rightmost >= n-1) {
    
                    return true;
                }
            }
        }
        return false;
    }
}

在这里插入图片描述

跳跃游戏||

跳跃游戏||

要求

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

class Solution {
    
    public int jump(int[] nums) {
    

    }
}

题解

因为题目中说生成的测试用例可以到达nums[i-1],求最小的跳跃次数。所以我们每次跳跃的位置就是在跳跃区间中能跳跃最远的位置。并且在遍历数组时,我们不访问最后一个元素,这是因为在访问最后一个元素之前,我们的边界一定大于等于最后一个位置,否则就无法跳到最后一个位置了。如果访问最后一个元素,在边界正好为最后一个位置的情况下,我们会增加一次「不必要的跳跃次数」,因此我们不必访问最后一个元素。
在这里插入图片描述

代码

class Solution {
    
    public int jump(int[] nums) {
    
        int n = nums.length;
        int rightmost = 0;
        //end用来记录跳跃区间
        int end = 0;
        int step = 0;
        for(int i = 0; i < n - 1; i++) {
    
            rightmost = Math.max(rightmost,i + nums[i]);
            if(i == end) {
    
                end = rightmost;
                step++;
            }
        }

        return step;
    }
}

在这里插入图片描述

. . .

相关推荐

额外说明

SpringBoot+@Async注解-异步调用

编程开发里,使用java异步执行方法可以让程序同时处理多个请求业务,提升吞吐量来缩短业务的执行时间,在springboot的程序应用中,提供了@Async注解来实现异步执行方法。 在业务开发中,有些时候是不需要立即返回业务的处理结果,比如物联网设备上报的

额外说明

Unity与 SO 交互 ☀️| 详细讲解 Unity端使用C# 调用so文件的具体方法

本文章是Unity与 SO 交互的内容,该专栏还有多篇优质内容在等待你观看,现在点击右上角点击这个————-订阅专栏- 就可以免费观看多篇相关内容的文章啦! 目录 -前言 -Unity 使用C#调用so文件 -第一步:准备好生成so文件的源文件 -第二步

额外说明

C++程序设计:回文数

【问题描述】 当一个数从前往后写与从后往前写时相等,则该数被称为回文数,所有的个位数都是回文数。 所有非回文数通过一系列的操作都可以匹配一个回文数。首先,将该数写反以后与原数相加,判断结果是否为回文数,如果不是,重复上述过程,直到和为回文数为止。例如:对

额外说明

那些我收藏多年和偷摸使用的工具~~~

作为一个见到好东西,不管有没有用先收藏的我来说,本期活动实在是太有必要写一篇博客了 目录 展示我的收藏癖 生活类收藏 学习类收藏 工具类收藏 谷歌插件类收藏 工具推荐 效率工具 sublime 文件转换工具 text转Markdown Markdown-

额外说明

计算机组成原理--基于Logisim的存储器实验的应用(超详细/设计/实验/作业/练习)

目录 课程名:计算机组成原理 内容/作用:设计/实验/作业/练习 学习:基于Logisim的存储器实验 一、前言 二、环境与设备 三、内容 四、结果与分析 课程名:计算机组成原理 内容/作用:设计/实验/作业/练习 学习:基于Logisim的存储器实验

额外说明

YoloV8改进策略:基于分层注意力的FasterViT,让YoloV8实现性能的飞跃

文章目录 摘要 论文翻译 摘要 1、简介 2、相关工作 3、FasterViT 3.1、设计主体 3.2、架构设计 3.3、FasterViT组件 4、实验 4.1、训练设置 5、结果 5.1、图像分类 5.2、目标检测与实例分割 5.3、语义分割 6、

额外说明

访问swagger文档报错Illegal DefaultValue 1024 for parameter type integer,java.lang.NumberFormatException

后台报错问题日志 2021-12-30 15:41:24.675 WARN [nio-9008-exec-1] [] i.s.m.p.AbstractSerializableParameter [421] : Illegal DefaultVal

额外说明

【Zap】日志重复打印问题

环境:Go1.18.2 windows/amd64 zap:go.uber.org/zap v1.7.0 近期,在做项目案例的时候,发现使用zap作为日志时,相同的日志内容重复输出,这些天,深入分析了一下zap的源码,发现了该问题出现的原因,现在总结一下

额外说明

域名能生成多少二级域名_15个最佳域名生成器,可帮助您选择域名(FAST)

一个域名可以生成多少个二级域名? Are you looking to 建立一个网站, but not sure which domain name to use? Picking the right domain name isn’t easy. Sp

ads via 小工具