当前位置: 首页 > 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…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...