力扣大厂热门面试算法题 43-45

43. 字符串相乘,44. 通配符匹配,45. 跳跃游戏 II,每题做详细思路梳理,配套Python&Java双语代码, 2024.03.18 可通过leetcode所有测试用例。

目录

43. 字符串相乘

解题思路

完整代码

Python

Java

44. 通配符匹配

解题思路

完整代码

Python

Java

45. 跳跃游戏 II

解题思路

完整代码

Python

Java


43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示:

  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只能由数字组成。
  • num1 和 num2 都不包含任何前导零,除了数字0本身。

解题思路

        可以使用一个被称为“竖式乘法”的方法,这是一种我们在小学学过的乘法手算方法。由于题目要求不能直接将字符串转换为整数进行计算,我们需要模拟这个过程。整体思路如下:

  1. 初始化结果字符串:最开始,我们可以将结果初始化为"0",因为任何数与0相乘都是0。
  2. 逐位相乘:从num2的最低位开始,每一位与num1相乘,得到一个临时的乘积。注意,我们需要处理乘积中的进位问题。
  3. 处理进位:将每一步的乘积加到最终的结果上时,同样需要处理进位问题。
  4. 结果累加:将每次乘法的结果累加到最终结果中,注意,由于是逐位相乘,我们需要在结果的右侧添加相应数量的0(这模拟了竖式乘法中的位移)。
  5. 去除前导零:最终,我们可能会得到一个有前导零的字符串,需要去掉这些前导零。

完整代码

Python
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":  # 如果有一个数为0,直接返回0
            return "0"
        
        result = [0] * (len(num1) + len(num2))  # 初始化结果数组,最大长度为两个字符串长度之和
        
        # 逐位相乘
        for i in range(len(num1) - 1, -1, -1):
            for j in range(len(num2) - 1, -1, -1):
                mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))  # 计算每一位的乘积
                sum = mul + result[i + j + 1]  # 加上之前的结果
                result[i + j + 1] = sum % 10  # 更新当前位
                result[i + j] += sum // 10  # 处理进位
        
        # 将结果数组转换为字符串,同时去除前导零
        result_str = ''.join(map(str, result))
        return result_str.lstrip('0')
Java
public class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {  // 如果有一个数为0,直接返回0
            return "0";
        }
        
        int[] result = new int[num1.length() + num2.length()];  // 初始化结果数组
        
        // 逐位相乘
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int sum = mul + result[i + j + 1];  // 加上之前的结果
                result[i + j + 1] = sum % 10;  // 更新当前位
                result[i + j] += sum / 10;  // 处理进位
            }
        }
        
        // 将结果数组转换为字符串,同时去除前导零
        StringBuilder resultStr = new StringBuilder();
        for (int num : result) {
            if (!(resultStr.length() == 0 && num == 0)) {  // 跳过前导零
                resultStr.append(num);
            }
        }
        
        return resultStr.length() == 0 ? "0" : resultStr.toString();
    }
}

44. 通配符匹配

给你一个输入字符串 (s) 和一个字符模式 (p) ,请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配:

  • '?' 可以匹配任何单个字符。
  • '*' 可以匹配任意字符序列(包括空字符序列)。

判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。

 

示例 1:

输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:s = "aa", p = "*"
输出:true
解释:'*' 可以匹配任意字符串。

示例 3:

输入:s = "cb", p = "?a"
输出:false
解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

提示:

  • 0 <= s.length, p.length <= 2000
  • s 仅由小写英文字母组成
  • p 仅由小写英文字母、'?' 或 '*' 组成

解题思路

        通配符匹配是一个经典问题,我们可以通过动态规划(DP)来解决这个问题。动态规划的基本思想是用一个二维数组dp[i][j]来表示字符串s的前i个字符和模式p的前j个字符是否匹配。下面是解决这个问题的步骤:

  1. 初始化:首先,我们初始化dp[0][0]true,因为两个空字符串是匹配的。对于dp[0][j],如果p的前j个字符都是*,那么它们可以匹配空字符串,因此dp[0][j]也为true
  2. 填充DP表:接下来,我们按行填充这个DP表。对于每一对(i, j),我们需要根据s[i-1]p[j-1]的关系来更新dp[i][j]
    • 如果s[i-1] == p[j-1]或者p[j-1] == '?',则dp[i][j] = dp[i-1][j-1]
    • 如果p[j-1] == '*',则dp[i][j] = dp[i][j-1](不使用*字符匹配)或dp[i-1][j](使用*字符匹配s[i-1]以及它之前的字符)。
  3. 返回结果:最后,dp[s.length()][p.length()]就是整个问题的答案,表示sp是否完全匹配。

完整代码

Python
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        dp[0][0] = True

        for j in range(1, len(p) + 1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-1]

        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j-1] == '*':
                    dp[i][j] = dp[i][j-1] or dp[i-1][j]
                elif p[j-1] == '?' or s[i-1] == p[j-1]:
                    dp[i][j] = dp[i-1][j-1]

        return dp[len(s)][len(p)]
Java
public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;

        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j-1) == '*') {
                dp[0][j] = dp[0][j-1];
            }
        }

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                } else if (p.charAt(j-1) == '?' || s.charAt(i-1) == p.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }

        return dp[s.length()][p.length()];
    }
}

45. 跳跃游戏 II

给定一个长度为 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

解题思路

        可以使用贪心算法。基本思想是,在每一步中都尽可能地跳得更远,但同时保留当前能达到的最远距离内的下一步跳跃能达到的最远距离。具体步骤如下:

  1. 初始化变量:创建几个变量,steps用于记录跳跃次数,maxReach用于记录当前步骤内能到达的最远距离,end用于记录这一跳能到达的最远位置。
  2. 遍历数组:从数组的第一个元素开始遍历,直到倒数第二个元素(因为最后一个元素是我们的目的地,不需要再跳跃)。
  3. 更新最远距离:在遍历的每一步中,更新能达到的最远距离maxReach = max(maxReach, i + nums[i]),其中i是当前位置,nums[i]是从当前位置能跳跃的最大长度。
  4. 到达跳跃点:当我们到达上一次跳跃确定的最远位置end时,意味着需要进行下一次跳跃,此时更新end为当前能达到的最远距离maxReach,并增加跳跃次数steps++
  5. 返回结果:当遍历完成时,steps即为到达数组末尾的最小跳跃次数。

完整代码

Python
class Solution:
    def jump(self, nums: List[int]) -> int:
        steps = 0
        maxReach = 0
        end = 0

        for i in range(len(nums) - 1):  # 不需要遍历到最后一个元素
            maxReach = max(maxReach, i + nums[i])
            if i == end:
                end = maxReach
                steps += 1

        return steps
Java
public class Solution {
    public int jump(int[] nums) {
        int steps = 0;
        int maxReach = 0;
        int end = 0;

        for (int i = 0; i < nums.length - 1; i++) {  // 不需要遍历到最后一个元素
            maxReach = Math.max(maxReach, i + nums[i]);
            if (i == end) {
                end = maxReach;
                steps++;
            }
        }

        return steps;
    }
}

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

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

相关文章

【Redis知识点总结】(五)——Redis实现分布式锁

Redis知识点总结&#xff08;五&#xff09;——Redis实现分布式锁 setnxsetnx expiresetnx expire lua脚本set nx exset nx ex 随机值set nx ex 随机值 lua脚本set ex nx 随机值 lua脚本 锁续期RedissonRedLock 在Redis的众多应用场景中&#xff0c;分布式锁是Redis比…

FDA: 用于语义分割的傅里叶域自适应

论文链接&#xff1a;https://arxiv.org/abs/2004.05498 代码链接&#xff1a;GitHub - YanchaoYang/FDA: Fourier Domain Adaptation for Semantic Segmentation 机构&#xff1a;UCLA 发表于2020CVPR 这篇文章别的地方略读了&#xff0c;主要看看方法&#xff0c;感兴趣自…

淘宝商品详情API接口采集商品上货

使用淘宝商品详情API接口采集商品信息以进行上货是一个常见的需求&#xff0c;但需要注意的是&#xff0c;淘宝的API接口使用受到严格的限制和规定&#xff0c;需要遵循淘宝的开放平台政策。以下是一般性的步骤和建议&#xff0c;但请确保在实际操作中遵循淘宝的官方文档和规定…

极智芯 | 解读移动端芯片荟萃篇 主流移动芯片性能对比

欢迎关注我的公众号「极智视界」,获取我的更多技术分享 大家好,我是极智视界,本文分享一下 解读移动端芯片荟萃篇 主流移动芯片性能对比。 要说芯片的应用场景一般都会说云边端、云边端的,这里的移动端芯片当然是会属于云边端中的端场景了,主要是面向手机、平板等应用。下…

springboot实战笔记

用户模块开发 用户登录接口实现 根据token获取用户信息 检查账号是否可用 用户注册接口实现

【每日算法】理论:常见AIGC模型; 刷题:力扣单调栈

上期文章 【每日算法】理论&#xff1a;生成模型基础&#xff1b; 刷题&#xff1a;力扣单调栈 文章目录 上期文章一、上期问题二、理论问题1、stable diffusion模型的网络架构2、T5的网络架构&#xff08;Text-To-Text Transfer Transformer模型&#xff09;3、SDXL模型4、DA…

【网络安全】 MSF生成木马教程

本文章仅用于信息安全学习&#xff0c;请遵守相关法律法规&#xff0c;严禁用于非法途径。若读者因此作出任何危害网络安全的行为&#xff0c;后果自负&#xff0c;与作者无关。 环境准备&#xff1a; 名称系统位数IP攻击机Kali Linux6410.3.0.231客户端Windows 76410.3.0.234…

二叉搜索树、B-树、B+树

二叉搜索树 二叉查找树&#xff0c;也称为二叉搜索树、有序二叉树或排序二叉树&#xff0c;是指一棵空树或者具有下列性质的二叉树&#xff1a; 若任意节点的左子树不空&#xff0c;则左子树上所有节点的值均小于它的根节点的值&#xff1b;若任意节点的右子树不空&#xff0…

java入门-基本数据类型

今天开始开贴关注初学java的同学&#xff0c;写些基础内容&#xff0c;希望对大家有所帮助。如果对大家有帮助会一直写下去。 java基本语法-基本数据类型 概述 基本数据类型在程序运行中&#xff0c;需要内存空间来存储数据。数据存储的大小有不同&#xff0c;申请合理的内存空…

POJO简介

文章目录 简介POJO与ELB的区别POJO真正的意思 常见的POJO类DTODAOPOVOEntity 简介 什么是POJO&#xff1f;POJO&#xff08;Plain Ordinary Java Object&#xff09;简单的Java对象&#xff0c;实际就是普通JavaBeans&#xff0c;是为了避免和EJB(EJB是Enterprise Java Beans技…

Docker【docker使用】

文章目录 前言一、概念二、常用方法1.镜像2.容器 三、镜像构建贺管理 前言 上一篇文章讲了docker的安装&#xff0c;本片文章我们来聊聊docker的一些常用操作。以及镜像、容器之间的关系 一、概念 docker三大核心概念&#xff1a;镜像 Image、容器 Container、仓库 Reposito…

Opencv4+稀疏光流算法详解+实现

0. 写在前面 项目需要用到光流法找到图像中的点运动方向&#xff0c;想到光流法刚好适用。原理部分参考&#xff1a; 图像处理算法--光流法-原理-CSDN博客 1. Opencv4.5.4稀疏光流函数说明 1.1 稀疏光流API介绍 prevImg:视频前一帧图像/金字塔&#xff0c;单通道CV_…

获取远程管理软件保存的凭据

点击星标&#xff0c;即时接收最新推文 本文选自《内网安全攻防&#xff1a;红队之路》 扫描二维码五折购书 内网敏感数据的发现 内网的核心敏感数据&#xff0c;不仅包括数据库、电子邮件&#xff0c;还包括个人数据及组织的业务数据、技术数据等。可以说&#xff0c;价值较高…

(零)OpenOFDM接收端整体思路

一旦捕获射频信号并将其下变频至基带&#xff0c;解码管道就会启动&#xff0c;包括&#xff1a; OFDM&#xff0c;多载波调制的一种。通过频分复用实现高速串行数据的并行传输, 它具有较好的抗多径衰落的能力&#xff0c;能够支持多用户接入。 OFDM主要思想是&#xff1a;将信…

(1)fopen,fseek,fread,ftell,rewind作用和使用方法,大端小端

文章目录 1.fopen&#xff0c;fseek&#xff0c;fread&#xff0c;ftell&#xff0c;rewind作用和使用方法2.bin文件里从0x0000到0x0x0007是00 00 DF 00 00 01 00 00&#xff0c;但是用fread读出来前四个字节是DF0000&#xff0c;然后是0x1000&#xff0c;这是为什么&#xff1…

2024蓝桥杯每日一题(回溯)

备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一&#xff1a;木棒 试题二&#xff1a;n皇后问题 试题三&#xff1a;糖果 试题四&#xff1a;飞机降落 试题五&#xff1a;生日蛋糕 试题一&#xff1a;木棒 【问题描述】 乔治拿来一组等长…

steam_api.dll“是什么?打开游戏出现找不到steam_api.dll无法继续执行代码如何解决

"steam_api.dll"是什么&#xff1f;&#xff0c;steam_api.dll它是由windows系统Visual C Redistributable for Visual Studio提供的。当这个文件损坏或丢失时&#xff0c;会导致一些应用程序无法运行&#xff0c;显示找不到"steam_api.dll"缺失错误。本文…

马斯克开源的grok AI大模型

马斯克践行诺言&#xff0c;坚持开源原则&#xff0c;选择开源自家的 AI 大模型——Grok-1 下载链接如下: https://github.com/xai-org/grok-1 Grok-1 开源仅过去了 10 个小时&#xff0c;该项目便获得了 超过16k 的 Star&#xff0c;成为众人关注的焦点所在。 后续继续更新…

Python二级备考(1)考纲+基础操作

考试大纲如下&#xff1a; 基本要求 考试内容 考试方式 比较希望能直接刷题&#xff0c;因为不懂的比较多可能会看视频。 基础操作刷题&#xff1a; 知乎大头计算机1-13题 import jieba txtinput() lsjieba.lcut(txt) print("{:.1f}".format(len(txt)/len(ls)…

springcloud:4.2 GateWay结合JWT实现网关鉴权

概述 概述 简介 JWT是一种用于双方之间传递安全信息的简洁的、URL安全的声明规范。 定义了一种简洁的,自包含的方法用于通信双方之间以Json对象的形式安全的传递信息。 特别适用于分布式站点的单点登录(SSO)场景 传统的session认证的缺点 安全性:CSRF攻击因为基于cookie来…