当前位置: 首页 > news >正文

Leetcode刷题-(41~45)-Java

算法是码农的基本功,也是各个大厂必考察的重点,让我们一起坚持写题吧。

遇事不决,可问春风,春风不语,即是本心。

我们在我们能力范围内,做好我们该做的事,然后相信一切都事最好的安排就可以啦,慢慢来,会很快,向前走,别回头。

目录

1.缺失的第一个正数

2.接雨水

3.字符串相乘

4.通配符匹配

5.跳跃游戏II


1.缺失的第一个正数

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/first-missing-positive/description/

思路1:如果不考虑空间复杂度的情况下,用哈希表存入元素,然后从1开始枚举判断元素是否在哈希表中即可,时间复杂度和空间复杂度都是O(n) 。

思路2:通过修改数组本身模拟:先将小于0的数字都变换成n+1,接下来将小于等于n的元素索引替换成负数,然后🏪找出第一个大于0的数字即是结果。

Java版:

哈希表法:

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length ;Map<Integer, Integer> map = new HashMap<>() ;for(int i=0; i<n; i++){map.put(nums[i], i) ;}int j = 1 ;for(j=1;j<=n; j++){if(!map.keySet().contains(j)){return j ;}}return j ;}
}

方法2:模拟:先将小于等于0的都变为n+1,然后将小于等于n的都变为负数,最后找出第一个大于0的元素所对应的索引,若未找到则返回n+1。

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length ;for(int i=0; i<n; i++){if(nums[i] <= 0){nums[i] = n + 1 ;}}for(int i=0; i<n; i++){int num = Math.abs(nums[i]) ;if(num <= n){nums[num-1] = - Math.abs(nums[num-1]) ;}}for(int i=0; i<n; i++){if(nums[i] > 0){return i + 1 ;}}return n + 1 ;}
}

2.接雨水

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/trapping-rain-water/solutions/

思路:利用双指针模拟,计算可以接到的雨水,维护左右指针以及左右侧柱子高度的最值,由两侧向中间遍历,每次更新左侧或者右侧柱子高度的最值,并计算可以接水的情况。

时间复杂度O(n)、空间复杂度O(1)

Java版:

class Solution {public int trap(int[] height) {int left = 0, right = height.length - 1 ;int leftMax = 0, rightMax = 0 ;int ans = 0 ;while(left < right){leftMax = Math.max(leftMax, height[left]) ;rightMax = Math.max(rightMax, height[right]) ;if(height[left] < height[right]){ans += leftMax - height[left] ;left ++ ;}else{ans += rightMax - height[right] ;right -- ;}}return ans ;}
}

3.字符串相乘

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/multiply-strings/

思路1:直接用BigInteger进行大数的相乘,最后将乘积转换成字符串。

Java版:

import java.math.* ;
class Solution {public String multiply(String num1, String num2) {BigInteger b1 = new BigInteger(num1) ;BigInteger b2 = new BigInteger(num2) ;return b1.multiply(b2).toString() ;}
}

4.通配符匹配

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/wildcard-matching/description/

思路:动态规划的思想,dp[n][m]表示长度为n的字符串s与长度为m的字符串p是否能匹配成功,

需要初始化dp[0][j],然后根据递推式更新dp[i][j].

Java版:

class Solution {public boolean isMatch(String s, String p) {// dp[n][m]: 字符串s的前n字符与字符串p的前m个字符是否匹配int n = s.length(), m = p.length() ;boolean [][] dp = new boolean[n+1][m+1] ;// 初始化s为空与p是否能够匹配,空的s只能与p的*匹配dp[0][0] = true ;for(int j=1; j<=m; j++){if(p.charAt(j-1) == '*'){dp[0][j] = true ;}else{break;}}// 遍历更新dp数组for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(p.charAt(j-1) == '*'){// 匹配任意字符或者空字符dp[i][j] = dp[i-1][j] || dp[i][j-1] ;}else if(p.charAt(j-1) == '?' || s.charAt(i-1) == p.charAt(j-1)){// 匹配一个字符dp[i][j] = dp[i-1][j-1] ;}}}return dp[n][m] ;}
}

5.跳跃游戏II

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/jump-game-ii/description/

思路:动态规划思想,dp[n]表示走到第n个位置所需要的最小步数。判断从第j位置是否可以走到i位置,如果可以则更新dp[i]的最小值。

Java版:

class Solution {public int jump(int[] nums) {int n = nums.length ;int [] dp = new int [n] ;dp[0] = 0 ;for(int i=1; i<n; i++){dp[i] = Integer.MAX_VALUE ;for(int j=0; j<i; j++){if(nums[j] >= i-j){dp[i] = Math.min(dp[j]+1, dp[i]) ;}}}return dp[n-1] ;}
}

相关文章:

Leetcode刷题-(41~45)-Java

算法是码农的基本功&#xff0c;也是各个大厂必考察的重点&#xff0c;让我们一起坚持写题吧。 遇事不决&#xff0c;可问春风&#xff0c;春风不语&#xff0c;即是本心。 我们在我们能力范围内&#xff0c;做好我们该做的事&#xff0c;然后相信一切都事最好的安排就可以啦…...

【Android】源码解析Activity的结构分析

源码解析Activity的结构分析 目录 1、Activity、View、Window有什么关联&#xff1f;2、Activity的结构构建流程3 源码解析Activity的构成 3.1 Activity的Attach方法3.2 Activity的OnCreate 4、WindowManager与View的关系总结 1、一个Activity对应几个WindowManage&#xff0…...

小猪APP分发:重塑应用分发市场的创新力量

在移动互联网蓬勃发展的今天&#xff0c;应用分发平台作为连接开发者与用户的桥梁&#xff0c;扮演着至关重要的角色。然而&#xff0c;随着市场的饱和&#xff0c;如何在众多平台中脱颖而出&#xff0c;为开发者提供更宽广的舞台&#xff0c;同时确保用户能够便捷、安全地获取…...

区块链 | IPFS 工作原理入门

&#x1f98a;原文&#xff1a;What is the InterPlanetary File System (IPFS), and how does it work? &#x1f98a;写在前面&#xff1a;本文属于搬运博客&#xff0c;自己留存学习。 1 去中心化互联网 尽管万维网是一个全球性的网络&#xff0c;但在数据存储方面&#…...

减速机齿数速算

1.齿轮相关参数 1.1 模数 &#xff0c; 因为 齿数*齿距 Pi*直径 所以&#xff1a;直径/齿数 齿距/PI 模数 国标现行标准&#xff08;截止2024/5&#xff09;是&#xff1a; GB/ 1357-2008 / ISO 54-1996 模数有国标的一个序列标准&#xff1a; 1.2.轴径 轴径的国标是&a…...

2万字长文:海豚调度器(DolphinScheduler)面试题深入了解

目录 海豚调度器的主要功能和特点 海豚调度器与Oozie、Azkaban等调度器相比的优势...

全双工音频对讲模块-支持空中升级、多级无线中继

SA618F30是一款高集成的大功率全双工无线音频模块&#xff0c;发射功率高达32dBm。该音频模块简化接口&#xff0c;只需外接音频功放或麦克风即可作为一个小型对讲机&#xff0c;方便快捷嵌入到各类手持设备中。支持多级无线中继&#xff0c;支持OTA空中升级。 SA618F30配备1W…...

Spring扩展点(二)Spring事务生命周期

Spring事务生命周期 Spring事务事务生命周期 接口 TransactionSynchronizationTransactionalEventListener&#xff08;另一种监听事务周期的方式&#xff09; Spring事务 Spring对JDBC事务做了封装&#xff0c;使其易于使用。主要分为声明式事务和编程式事务。 Transactiona…...

foobar2000 for Mac:卓越音乐播放器

当您在寻找一款音质卓越、功能丰富的音频播放器时&#xff0c;foobar2000 for Mac无疑是您的首选。它拥有简洁明了的界面设计&#xff0c;易于上手&#xff0c;同时支持多种音频格式&#xff0c;让您无需担心兼容性问题。 foobar2000 for Mac v2.6.4免激活版下载 foobar2000 fo…...

【自动驾驶|毫米波雷达】初识毫米波雷达射频前端硬件

第一次更新&#xff1a;2024/5/4 目录 整体概述 混频器&#xff08;MIXER&#xff09; 低通滤波器&#xff08;LPF&#xff1a;Low-Pass filter&#xff09; 数模转换器&#xff08;ADC&#xff1a;Analog to Digital Converter&#xff09; 毫米波雷达功能框图 整体概述 完…...

实战BACnet/IP标准通信网关在楼宇自动化中的应用

智慧楼宇建设实现不同设备间的互联互通是一项巨大挑战&#xff0c;尤其是在那些历史悠久的建筑中&#xff0c;新旧系统并存的情况尤为普遍。某大型商业综合体就面临着这样的困境&#xff1a;老旧的暖通空调系统采用Modbus RTU协议&#xff0c;而新部署的能源管理系统却要求BACn…...

设计模式的原则与分类

一、设计模式的原则 1、单一职责原则 一个类只需要负责一种职责即可&#xff0c;一个类发生变化的原因&#xff0c;必然是所负责的职责发生变化 2、接口隔离原则 单一职责原则是接口隔离原则的基础&#xff0c;单一职责原则注重职责的划分&#xff0c;从职责角度进行类和接口…...

在ubuntu虚拟机中手动安装VMware Tools(VMware Workstation 17 player)

可参考官方文档&#xff1a;在 Linux 虚拟机中手动安装 VMware Tools 以下列出我在安装过程中遇见的问题&#xff1a; 1、“安装VMware Tools”选项为灰&#xff0c;无法选中 原因是VMware Tools的安装包镜像在Player的安装目录下&#xff0c;需要在虚拟机启动的时候加载这个…...

十个数据安全最佳实践:保护数据的简单方法

在德迅云安全将介绍数据安全的主要原则&#xff0c;并了解适用于大多数行业的 10 种数据安全最佳实践&#xff0c;以及云端安全检测的重要性。 数据威胁和维护数据安全的好处 什么是数据安全&#xff1f; 数据安全是旨在保护组织敏感资产的流程和工具的组合。有价值的数据在…...

【leetcode】二分搜索题目总结

704. 二分查找 class Solution { public:int search(vector<int>& nums, int target) {int left 0, right nums.size() - 1;while (left < right) {int mid left (right - left) / 2;if (nums[mid] target) {return mid;} else if (nums[mid] < target) …...

六西格玛项目的核心要素:理论学习、实践应用与项目经验

许多朋友担心&#xff0c;没有项目经验是否就意味着无法考取六西格玛证书。针对这一疑问&#xff0c;张驰咨询为大家详细解答。 首先&#xff0c;需要明确的是&#xff0c;六西格玛项目不仅仅是一种管理工具或方法&#xff0c;更是一种追求卓越、持续改进的思维方式。它强调通…...

21-ESP32-S3实时时钟(RTC)

ESP32-S3实时时钟&#xff08;RTC&#xff09;的使用 ESP32-S3是一款高性能的Wi-Fi和蓝牙集成的系统级芯片&#xff08;SoC&#xff09;&#xff0c;它包含一个实时时钟&#xff08;RTC&#xff09;模块&#xff0c;可以在系统的其他部分关闭时继续运行&#xff0c;以节省电能…...

17.接口自动化学习-日志

1.日志输出渠道 &#xff08;1&#xff09;文件格式 xx.log &#xff08;2&#xff09;控制台输出 2.日志级别 debug<info<warnning<error<critical 3.代码实现 from utils.handle_path import log_path import logging import datetime def logger(fileLogTr…...

python直接发布到网站wordpress之二发布图片

在我的上一篇文章中已经给出了python操作wordpress的环境和发布文字的教程&#xff1a; python直接发布到网站wordpress之一只发布文字-CSDN博客 本篇实现发布带图片的内容&#xff0c;无图无真相嘛。 直接上代码&#xff1a; from wordpress_xmlrpc.methods.media import …...

Messari 报告摘要 :Covalent Network(CQT)2024 年第一季度表现

摘要&#xff1a; 尽管 CQT 代币流通供应量增加了 20%&#xff08;新增 1.04 亿枚 CQT&#xff09;&#xff0c;但 CQT 的质押百分比仅从 2023 年第一季度的 22% 增长到了 2024 年第一季度的 29%。 CQT 的市值季度环比增长了 28%&#xff0c;多次达到 2.75 亿美元&#xff0c…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...