LeetCode-hot100题解—Day5

原题链接:力扣热题-HOT100
我把刷题的顺序调整了一下,所以可以根据题号进行参考,题号和力扣上时对应的,那么接下来就开始刷题之旅吧~
1-8题见LeetCode-hot100题解—Day1
9-16题见LeetCode-hot100题解—Day2
17-24题见LeetCode-hot100题解—Day3
25-34题见LeetCode-hot100题解—Day4
注:需要补充的是,如果对于每题的思路不是很理解,可以点击链接查看视频讲解,是我在B站发现的一个宝藏UP主,视频讲解很清晰(UP主用的是C++),可以结合视频参考本文的java代码。

力扣hot100题解 32-40

    • 39.组合总和
    • 46.全排列
    • 48.旋转图像
    • 49.字母异位词分组
    • 50.Pow(x,n)
    • 53.最大子数组和
    • 55.跳跃游戏
    • 56.合并区间

39.组合总和

思路
本题是典型的深度优先搜索,需要注意的一点是,每个数字是可以重复选择的,所以在深度优先搜索的时候索引值idx不用改变,具体的思路可以参考视频讲解-组合总和。
时间复杂度
时间复杂度分析:

  • 在最坏情况下,DFS会遍历所有可能的组合。
  • 对于每个数字,都有两种选择:选择或者不选择。
    因此,时间复杂度为 O(2^N),其中 N 是候选数字的数量。
    代码实现
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> com = new ArrayList<>();
        dfs(candidates,target,0,ans,com);
        return ans;
    }

    private void dfs(int[] candidates,int target,int idx,List<List<Integer>> ans, List<Integer> com){
        if(target == 0){
            ans.add(new ArrayList<>(com));
            return ;
        }
        if(idx == candidates.length) return ;

        dfs(candidates,target,idx + 1,ans,com);
        if(target >= candidates[idx]){
            com.add(candidates[idx]);
            dfs(candidates,target - candidates[idx],idx,ans,com);
            com.remove(com.size() - 1);
        }
    }
}

46.全排列

思路
本题是一个典型的dfs问题,和39题很相似,以[1,2,3]为例模拟dfs的过程如下,需要注意的是选择数字进行组合的依据是对应的数字在之前没有被使用,所以需要一个used布尔数组来记录数组元素的使用情况,视频讲解点击视频讲解-全排列。
在这里插入图片描述

时间复杂度
在每个位置上,都有n种选择,因此总共有 n! 种排列,故时间复杂度为O(n^n)
代码实现

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> combine = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        dfs(nums,0,used);
        return ans;
    }

    private void dfs(int[] nums,int idx,boolean[] used){
        if(idx == nums.length){
            ans.add(new ArrayList<>(combine));
            return ;
        }
        for(int i = 0;i < nums.length;i++){
            if(!used[i]){
                combine.add(nums[i]);
                used[i] = true;
                dfs(nums,idx+1,used);
                used[i] = false;
                combine.remove(combine.size() - 1);
            }
        }
    }
}

48.旋转图像

思路:
对二维数组进行顺时针90°的旋转,可以拆分成先将数组按照主对角线进行翻转,然后再将得到的数组左右翻转,模拟的过程如图所示,所以只需要对数组进行两次循环先进行主对角线翻转,然后进行左右翻转即可,详细的讲解点击视频讲解-旋转图像。
在这里插入图片描述

时间复杂度:
用到了两层for循环,故时间复杂度为O(n^2)
代码实现:

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        //按主对角线翻转
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        //左右翻转
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n / 2; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
    }
}

49.字母异位词分组

思路
本题需要将字母异位词分组,然后返回,可以发现字母异位词的在按照字母序排序后结果都是一样的,例如[abc,bca,cba]按照字母序排序后得到的结果都是abc,所以我们可以使用哈希表以字母序的字符串为key,将所有重新排列的单词作为value,在处理结束整个字符串数组后输出map的所有value值即可。详细的视频点击视频讲解-字母异位词分组。
时间复杂度
这段代码的时间复杂度为O(NKlogK),其中N表示字符串数组的长度,K表示字符串的最大长度。
代码中的循环遍历了字符串数组,所以它的时间复杂度是O(N)
在每次循环中,将字符串转换为字符数组需要O(K)的时间复杂度。然后对字符数组进行排序需要O(KlogK)的时间复杂度。因此,每次循环的总时间复杂度是O(KlogK)
最后,将排序后的字符串作为键值,将原始字符串添加到对应的列表中,这个操作的时间复杂度是O(1)
因此,整个代码的时间复杂度为O(NKlogK)
代码实现

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> record = new HashMap<>();
        for(String str : strs){
            char[] chars = str.toCharArray();
            Arrays.sort(chars);`在这里插入代码片`
            String key = new String(chars);
            if(!record.containsKey(key)){
                record.put(key,new ArrayList<>());
            }
            record.get(key).add(str);
        }
        return new ArrayList<>(record.values());
    }
}

知识点总结
关于java中的哈希表的用法
Map在解决一些算法问题时经常会用到,所以在这里对MapAPI总结一下,方便后续刷题的时候来查看使用,参考博客java map使用(这个博客里面包含了其他哈希结构的API,很赞,推荐去看,这里我只是摘抄出来Map的常用API)。
void clear() :删除Map中的所有键值对
boolean containsKey(key) :查询Map中是否包含指定的key,如果包含则返回true
boolean containsValue(value) :查询Map中是否包含指定的value,如果包含则返回true
Set entrySet() :返回Map中所包含的键值对所组成的Set集合 ,每个集合元素都是Map.Entry的对象,EntryMap的内部类
Object get(key):返回key对应的value,如果没有key则返回null
boolean isEmpty():查询Map是否为空,为空返回true
Set keySet():返回该Map中所有key所组成的set集合
Object put(key,value):添加一个键值对,如果已有一个相同的key值则新的键值对覆盖旧的键值对
void putAll(Map m):将指定Map中的键值对复制到Map
Object remove(key) :删除指定key所对应的键值对,返回key所关联的value,如果key不存在则返回null
int size():返回该Map里的键值对的个数
Collection values():返回该Map中所有value组成的Collection
Map中包含一个内部类:Entry,该类封装了一个键值对,它包含了三个方法:
Object getKey():返回该Entry里包含的key值
Object getValue():返回该Entry里包含的value
Object setValue(value) :设置该Entry中包含的value值,并返回新设置的value值。

50.Pow(x,n)

思路
本题暴力的解法是直接循环累成x,但是这样做时间复杂度会很高,导致超时,这里我们用快速幂来解决,快速幂在算法题中也较为常见,其思想是我们将n转换成二进制,可以使得我们累乘的次数变少,如下图的过程所示。第一步我们需要先得到x的各二次幂的值,然后根据n的二进制来决定需要将哪些二次幂累乘(如果没有理解的请看下图),如果不是很明白可以点击观看视频讲解视频讲解-Pow(x,n)。
在这里插入图片描述

时间复杂度
该代码的时间复杂度为O(logN)。循环的次数取决于n的二进制表示中1的个数,而n的二进制表示最多有logN位。所以,循环的次数最多为logN次,因此时间复杂度为O(logN)
代码实现

class Solution {
    public double myPow(double x, int n) {
        //防止溢出重新定义为long long类型
        long N = n;
        //如果n是负数,先处理成整数,在最后得到结果后处理成1/ans即可
        if(n < 0) N = -N;
        double ans = 1.0;
        while(N > 0){
            if( (N & 1) == 1) ans *= x;
            x *= x;
            N >>= 1;
        }
        return n < 0 ? 1 / ans :ans;
    }
}

53.最大子数组和

思路
本题采用动态规划来求解,动态规划最重要的是得到动态规划方程,在本题中我们要得到数组中和最大的连续子数组,用f(i)来表示到下标为i时子数组的和,那么f(i-1)就是指到下标为i-1的子数组的和,如果f(i-1)<0,所以要得到最大的和,f(i)就是nums[i],如果f(i-1)>0,那么f(i)的最大和为f(i-1)+nums[i],需要注意的题目中要求是连续的子数组,如果不是连续子数组,那么就不能用该方法求解,可以使用dfs。如果没有理解上面的讲解可以点击观看视频讲解视频讲解-最大子数组和。
时间复杂度
由于只对数组进行了一次遍历,所以时间复杂度为O(n)
代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = nums[0];
        int ans = nums[0];
        for(int i = 1; i < nums.length;i++){
            pre = pre > 0 ? pre + nums[i] : nums[i];
            ans = Math.max(ans,pre);
        }
        return ans;
    }
}

55.跳跃游戏

思路
通过题意可以得出,当数组的下标大于此下标之前所有下标可以跳转的最大位置,则说明无法到达最后一个下标,因为这时该下标是无法到达的,所以也无法到达最后一个图标。如果没有理解的话,可以点击观看视频讲解视频讲解-跳跃游戏,里面有具体的过程模拟。
时间复杂度
由于只对数组进行了一次遍历,所以时间复杂度为O(n)
代码实现

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

56.合并区间

思路
本题使用扫描线法来解决,首先要对二维数组进行排序,根据其中数组元素的第一个数字进行升序排列(这里代码里用了一种正则表达式的排序方法,会在知识点总结进行介绍),在排序完成之后进行扫描,有三种情况,我们将最前面的数组区间设置为[start,end],向后扫描:

  1. 后面的区间的starti大于end,那么直接将前一个区间加入结果集中

  2. 后面的区间的starti小于end,这里又会分出两种情况:

    (1)后面的区间完全包含在前面的区间
    (2)后面的区间的endi大于前面区间的end
    以上两种情况我们都需要将end更新为最大的end值,所以可以归结为一类

如果还是不太理解的话可以点击视频讲解-合并区间。
时间复杂度
首先将区间按照起始时间排序,这需要O(nlogn)的时间复杂度,然后遍历排序后的区间,维护一个当前区间的起始时间和结束时间。如果遇到与当前区间重叠的新区间,就更新当前区间的结束时间。如果遇到与当前区间不重叠的新区间,就把当前区间加入到结果列表中,然后更新当前区间的起始时间和结束时间,这个遍历过程需要O(n)的时间复杂度。所以总的时间复杂度是O(nlogn) + O(n) = O(nlogn)
代码实现

class Solution {
    public int[][] merge(int[][] intervals) {
        //将ntervals按照数组元素的第一个数排序
        Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
        List<int[]> ans = new ArrayList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        for(int[] interval : intervals){
            if(interval[0] > end){
                ans.add(new int[]{start,end});
                start = interval[0];
                end = interval[1];
            }else{
                end = Math.max(end,interval[1]);
            }
        }
        ans.add(new int[]{start,end});
        return ans.toArray(new int[ans.size()][]);
    }
}

知识总结
1.List的常见使用

//向List中添加元素
List.add(e)
//根据索引获取元素
List.get(index)
//按照索引删除
List.remove(index)
//按照元素内容删除
List.remove(Object o)
//判断List中是否包含某个元素,返回true或false
List.contains(Object o)
//使用element替换该索引处的值
List.set(index,element)
//在该索引位置插入一个值
List.add(index,element)
//返回该值的第一个索引
List.indexOf(Object o)
//返回该值的最后一个索引
List.lastIndexOf(Object o)
//截取List的部分元素,
//注意这里时左闭右开,即fromIndex的值要包括,但是toIndex的值不包括,索引从0开始
List.subList(fromIndex, toIndex)
//返回该List中的元素数
List.size()
//对比两个List的所有元素是否相同
//两个相等对象的equals方法一定为true, 但两个hashcode相等的对象不一定是相等的对象
List1.equals(List2)
//判断List是否为空
List.isEmpty()
//返回Iterator集合对象
List.iterator()
//将List转换为字符串
List.toString()
//将List转换为数组
List.toArray()

2.二维数组的排序

Arrays.sort(intervals,(a,b) -> a[0] - b[0]);

intervals是一个二维数组,每个元素都是一个包含两个整数的数组,表示一个时间区间的开始和结束时间。(a, b) -> a[0] - b[0]是一个lambda表达式,用作排序的比较函数。它比较两个数组ab的第一个元素,如果a[0]小于b[0],则返回一个负数,表示a应该排在b前面。经过排序,intervals数组中的时间区间会按照开始时间的升序排列。
为什么不能直接使用Arrays.sort(intervals)呢?
由于 intervals 数组中的元素是 int[] 类型的数组。在这种情况下,直接使用 Arrays.sort(intervals) 是不正确的,因为 Java 默认使用数组元素的比较顺序进行排序,对于 int[] 类型来说,比较的是数组的引用,而不是数组中的元素。
对于一维数组,比如 int[] 类型,Arrays.sort() 方法可以直接使用,它会按照数组元素的自然顺序进行排序。
但是对于二维数组 int[][] 类型,情况就不太一样了。因为二维数组的元素是一维数组,所以 Arrays.sort() 默认是按照一维数组的引用进行排序的,而不是按照一维数组中的元素进行排序。
为了按照二维数组中的特定元素进行排序,需要提供一个自定义的比较器,例如 (a, b) -> a[0] - b[0] ,这样可以告诉 Arrays.sort() 方法按照二维数组中的第一个元素进行排序。
待续…

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

V23 中的新增功能:LEADTOOLS React Medical Web 查看器

LEADTOOLS (Lead Technology)由Moe Daher and Rich Little创建于1990年&#xff0c;其总部设在北卡罗来纳州夏洛特。LEAD的建立是为了使Daher先生在数码图象与压缩技术领域的发明面向市场。在过去超过30年的发展历程中&#xff0c;LEAD以其在全世界主要国家中占有的市场领导地位…

21.Nacos集群搭建

模拟Nacos三个节点&#xff0c;同一个ip,启动三个不同的端口&#xff1a; 节点 nacos1, 端口&#xff1a;8845 节点 nacos2, 端口&#xff1a;8846 节点 nacos3, 端口&#xff1a;8847 1.搭建数据库&#xff0c;初始化数据库表结构 这里我们以单点的数据库为例 首先新建一…

2024年 Java 面试八股文——Redis篇

目录 1、介绍下Redis Redis有哪些数据类型 难度系数&#xff1a;⭐ 2、Redis提供了哪几种持久化方式 难度系数&#xff1a;⭐ 3、Redis为什么快 难度系数&#xff1a;⭐ 4、Redis为什么是单线程的 难度系数&#xff1a;⭐ 5、Redis服务器的的内存是多大…

基于飞腾D2000全国产化高速公路一体化收费站解决方案:站数据服务器、站AI服务器、收费系统、监控系统

高速公路一体化收费站解决方案 行业 交通工程及沿路设施作为公路的一个重要组成部分&#xff0c;对城市互联和城市发展具有重要意义&#xff0c;因此围绕高速公路的专用收费 站设计和建设&#xff0c;将有效促进枢纽集散系统与高速公路连通&#xff0c;显著提升城市高速集散能…

ES的脑裂现象

目录 0 集群结点的职责1 什么是脑裂现象2 造成脑裂现象的原因2.1 网络问题&#xff08;最常见&#xff09;2.2 主节点负载过大&#xff0c;资源耗尽&#xff0c;别的结点ping不到主节点2.3 主节点JVM内存回收时间过长导致 3 脑裂现象的解决方案3.1 局域网部署3.2 角色分离&…

C语言从入门到精通-C静态库的生成及使用

静态库 什么是静态库 C静态库&#xff08;Static Library&#xff09;是C语言编程中常用的一种库文件形式。与动态库&#xff08;Dynamic Library&#xff09;相比&#xff0c;静态库在程序编译时会被完全嵌入到最终的可执行文件中&#xff0c;因此生成的可执行文件不依赖于外…

BiLSTM-KDE的双向长短期记忆神经网络结合核密度估计多变量回归区间预测(Matlab)

BiLSTM-KDE的双向长短期记忆神经网络结合核密度估计多变量回归区间预测&#xff08;Matlab&#xff09; 目录 BiLSTM-KDE的双向长短期记忆神经网络结合核密度估计多变量回归区间预测&#xff08;Matlab&#xff09;效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.BiLS…

后台架构总结

前言 疫情三年&#xff0c;全国各地的健康码成为了每个人的重要生活组成部分。虽然过去一年&#xff0c;但是回想起来任然历历在目。 今天我就通过当时基于小程序的健康码架构&#xff0c;来给大家讲一下如何基于java&#xff0c;springboot等技术来快速搭建一个后台业务系统…

人工智能分割分类model:nnUnet-paddle

文章目录 神经网络nnUnet和paddle都需要在Ubuntu下进行安装PaddleProject 神经网络 开源来自https://github.com/MIC-DKFZ/nnUNet 自建了仓库&#xff0c;但还不会用 来自 mmsegmentation有空去了解 . MICCAI 2020 也是用到这个网络 paddle上的是不是不能用… nnUnet和pad…

Linux基础IO(下)

目录 1. 缓冲区 1.1 定义 1.2 理解缓冲区 1.2.1 为什么要有缓冲区 1.2.2 缓冲区的工作原理 缓冲区什么时候写入&#xff0c;什么时候刷新&#xff1f; 2. 文件系统 2.1 什么是文件系统&#xff1f; 2.2 为什么要有文件系统&#xff1f; 2.3 认识文件的管理结构 2.…

绩效评估与持续反馈

高绩效团队认识到评论和反馈的商业价值&#xff0c;这是两种关键的绩效管理工具。绩效管理是 2023 年受访者最优先考虑的五项人力资源举措之一&#xff0c;学习和发展是另一项举措&#xff0c;绩效评估和持续反馈最近可能会受到人力资源团队的更多关注。 在这里&#xff0c;我…

每天五分钟玩转深度学习PyTorch:创建pytorch中的零维标量tensor

标量是什么? tensor张量是一个多维数组,零维就是一个点(就是本章的标量),一维就是向量,二维就是一般的矩阵,多维就相当于一个多维的数组,这和 numpy理解是一样的,不同的是Tensor不仅可以在CPU上跑,在GPU上也可以跑。 标量(scalar),只具有数值大小,而没有方向,…

python数据可视化:雷达图

【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 python数据可视化&#xff1a; 雷达图 选择题 关于以下代码输出的雷达图中&#xff0c;以下说法正确的是&#xff1f; import numpy as np import matplotlib.pyplot as plt from pylab impor…

深入浅出一文图解Vision Mamba(ViM)

文章目录 引言&#xff1a;Mamba第一章&#xff1a;环境安装1.1安装教程1.2问题总结1.3安装总结 第二章&#xff1a;即插即用模块2.1模块一&#xff1a;Mamba Vision代码&#xff1a;models_mamba.py运行结果 2.2模块二&#xff1a;MambaIR代码&#xff1a;MambaIR运行结果 第三…

IP如何安装SSL证书,实现加密传输

让我们理解一下SSL证书。SSL&#xff08;Secure Sockets Layer&#xff09;证书是一种数字证书&#xff0c;它利用数据加密技术&#xff0c;确保了互联网数据传输的安全。当网站安装了SSL证书后&#xff0c;所有的数据都会经过加密后再传输&#xff0c;这可以防止黑客窃取或篡改…

标贝语音识别技术在金融领域中的应用实例

随着语音识别技术与文本挖掘、自然语言处理等技术的不断融合&#xff0c;智能语音交互技术在金融领域中爆发了出巨大的应用潜力。标贝科技根据自身与金融领域合作的经验为大家梳理出以下几点智能语音识别技术在金融领域中的应用实例。 一、智能柜台服务 语音识别的主要功能就…

如何安全可控的进行跨区域数据交换,提高数据价值?

跨区域数据交换指的是在不同地理位置或不同网络环境下的数据传输和共享。随着数字化转型的加速&#xff0c;企业及组织越来越依赖于数据的流动来优化业务流程、增强决策制定和推动创新。然而&#xff0c;跨区域数据交换也带来了一系列的挑战和风险&#xff0c;主要包括&#xf…

SpringSecurity6配置requestMatchers().permitAll() 无效问题

版本 <spring-boot.version>3.0.2</spring-boot.version> <jjwt.version>0.12.5</jjwt.version>问题描述 题主在写 SpringSecurity6 JWT 做登录认证开发。一路跟着教程叭叭的敲。等到接口验证的时候&#xff0c;发现我的登录接口虽然在SecurityConf…

maven多模块创建-安装配置

1、前提 许久没有写文章了&#xff0c;荒废了2年多的时间&#xff0c;在整理的时候&#xff0c;发现Maven还差一篇安装配置的文章&#xff0c;现在开始提笔完善它&#xff0c;参考&#xff1a;https://blog.csdn.net/m0_72803119/article/details/134634164。 —写于2024年4月…

有什么好用的足球数据分析工具,可以生成可靠的投注策略?

在寻找好用的足球数据分析工具以生成可靠的投注策略时&#xff0c;有几个值得考虑的选项。以下是一些工具和建议&#xff1a; 乐彩数据分析&#xff1a;这款工具以其精准的预测和高达70%以上的准确率而受到赞誉。它利用大数据算法进行预测&#xff0c;相比个人预测更加准确。此…