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

LeetCode题练习与总结:赎金信--383

一、题目描述

给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以,返回 true ;否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1:

输入:ransomNote = "a", magazine = "b"
输出:false

示例 2:

输入:ransomNote = "aa", magazine = "ab"
输出:false

示例 3:

输入:ransomNote = "aa", magazine = "aab"
输出:true

提示:

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote 和 magazine 由小写英文字母组成

二、解题思路

  1. 首先,我们需要统计 magazine 中每个字符出现的次数。
  2. 然后,遍历 ransomNote 中的每个字符,并检查 magazine 中是否有足够的该字符来构成 ransomNote
  3. 如果在 ransomNote 中发现一个字符,而 magazine 中没有足够的该字符,那么返回 false
  4. 如果 ransomNote 中的所有字符都能在 magazine 中找到足够的数量,返回 true

三、具体代码

class Solution {public boolean canConstruct(String ransomNote, String magazine) {// 使用一个数组来统计magazine中每个字符的出现次数int[] count = new int[26]; // 因为只有小写字母,所以大小为26// 遍历magazine,统计每个字符的出现次数for (char c : magazine.toCharArray()) {count[c - 'a']++;}// 遍历ransomNote,检查是否有足够的字符for (char c : ransomNote.toCharArray()) {// 如果magazine中没有足够的字符c,返回falseif (--count[c - 'a'] < 0) {return false;}}// 如果所有字符都检查通过,返回truereturn true;}
}

在这段代码中,我们使用了一个长度为26的数组 count 来存储每个字符出现的次数,因为英文字母一共有26个。数组中的索引 i 对应字符 'a' + i。通过这种方式,我们可以快速定位并更新字符的出现次数。当遍历 ransomNote 时,我们只需要检查对应的计数是否大于0,如果是,则表示可以构成,否则返回 false

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 遍历 magazine 字符串统计字符出现次数:这个操作的时间复杂度是 O(n),其中 n 是 magazine 字符串的长度。
  • 遍历 ransomNote 字符串检查字符是否足够:这个操作的时间复杂度是 O(m),其中 m 是 ransomNote 字符串的长度。

因为这两个操作是顺序执行的,所以总的时间复杂度是两个操作的和,即 O(n + m)。

2. 空间复杂度
  • 使用了一个固定大小的数组 count 来存储每个字符的出现次数,该数组的大小为26,不随输入字符串的长度变化。因此,这个操作的空间复杂度是 O(1)。

综上所述,该算法的时间复杂度是 O(n + m),空间复杂度是 O(1)。其中 n 是 magazine 的长度,m 是 ransomNote 的长度。

五、总结知识点

  1. 数组的声明与初始化:使用 int[] count = new int[26]; 声明并初始化了一个长度为26的整型数组,用于存储每个小写字母出现的次数。

  2. 字符与整型的转换:通过表达式 c - 'a' 将字符转换为对应的整型索引。这是因为字符在Java中是以整数形式存储的,且小写字母 ‘a’ 到 ‘z’ 在ASCII表中的值是连续的。

  3. 增强型for循环:使用增强型for循环 for (char c : magazine.toCharArray()) 来遍历字符串中的每个字符。

  4. 数组的索引访问:使用数组索引 count[c - 'a'] 来访问和更新数组中对应字符的计数。

  5. 前缀自增和自减操作:使用 ++ 和 -- 操作符来增加和减少数组中字符的计数。

  6. 条件判断:使用 if 语句来检查数组中字符的计数是否小于0,以确定是否可以由 magazine 中的字符构成 ransomNote

  7. 返回值:使用 return 语句来返回布尔值 true 或 false,表示 ransomNote 是否可以由 magazine 中的字符构成。

  8. 字符串到字符数组的转换:使用 toCharArray() 方法将字符串转换为字符数组,以便能够遍历字符串中的每个字符。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

相关文章:

LeetCode题练习与总结:赎金信--383

一、题目描述 给你两个字符串&#xff1a;ransomNote 和 magazine &#xff0c;判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以&#xff0c;返回 true &#xff1b;否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 示例 1&#xff1…...

eval: jdk1.8.0_431/jre/bin/java: Permission denied

当您在启动Tomcat或其他Java应用时遇到“Permission denied”错误&#xff0c;这通常表示当前用户没有执行指定Java可执行文件的权限。以下是解决这个问题的几种方法&#xff1a; 方法一&#xff1a;检查文件权限 查看文件权限&#xff1a; 使用ls -l命令查看Java可执行文件的…...

.Net IOC理解及代码实现

IOC理解 IoC(Inversion of Control)&#xff1a;即控制反转&#xff0c;这是一种设计思想&#xff0c;指将对象的控制权交给IOC容器&#xff0c;由容器来实现对象的创建、管理&#xff0c;程序员只需要从容器获取想要的对象就可以了。DI(Dependency Injection)&#xff0c;即依…...

履带机器人(一、STM32控制部分--标准库)

一、履带机器人整体逻辑框架 通过在PC端搭建上位机,使得在PC端可以给STM32发送控制指令并且接受STM32的状态信息。 通过RS485通信,使得STM32可以和电机进行通信,STM32发送启动、停止、转速、方向等指令,并接受电机返回的状态信息。 二、STM32逻辑框架 整体逻辑: 1、先…...

地理空间-Java实现航迹稀释

Java实现航迹点稀释算法&#xff08;Douglas - Peucker算法&#xff09;的示例代码&#xff0c;该算法可在保证航迹整体形状变化不大的情况下减少航迹点数量&#xff1a; import java.util.ArrayList; import java.util.List; class Point { double x; double y; public Point…...

qt QHttpMultiPart详解

1. 概述 QHttpMultiPart是Qt框架中用于处理HTTP多部分请求的类。它类似于RFC 2046中描述的MIME multipart消息&#xff0c;允许在单个HTTP请求中包含多个数据部分&#xff0c;如文件、文本等。这种多部分请求在上传文件或发送带有附件的邮件等场景中非常有用。QHttpMultiPart类…...

【测试】【Debug】vscode中同一个测试用例出现重复

这种是正常的情况 当下面又出现一个 类似python_test->文件夹名->test_good ->test_pad 同一个测试用例出现两次&#xff0c;名称都相同&#xff0c;显然是重复了。那么如何解决&#xff1f; 这种情况是因为在终端利用“pip install pytest”安装 之后&#xff0c;又…...

Mac上的免费压缩软件-FastZip使用体验实测

FastZip是Mac上的一款免费的压缩软件&#xff0c;分享一下我在日常使用中的体验 压缩格式支持7Z、Zip&#xff0c;解压支持7Z、ZIP、RAR、TAR、GZIP、BZIP2、XZ、LZIP、ACE、ISO、CAB、PAX、JAR、AR、CPIO等所有常见格式的解压 体验使用下来能满足我所有的压缩与解压的需求&a…...

Linux(CentOS)运行 jar 包

1、在本地终端运行&#xff0c;关闭终端&#xff0c;程序就会终止 java -jar tlias-0.0.1-SNAPSHOT.jar 发送请求&#xff0c;成功 关闭终端&#xff08;程序也会终止&#xff09; 发送请求&#xff0c;失败 2、在远程终端运行&#xff0c;关闭终端&#xff0c;程序就会终止 …...

基于YOLOv8 Web的安全帽佩戴识别检测系统的研究和设计,数据集+训练结果+Web源码

摘要 在工地&#xff0c;制造工厂&#xff0c;发电厂等地方&#xff0c;施工人佩戴安全帽能有效降低事故发生概率&#xff0c;在工业制造、发电等领域需要进行施工人员安全帽监测。目前大多数的 YOLO 模型还拘泥于公司、企业开发生产的具体产品中&#xff0c;大多数无编程基础…...

LabVIEW VISA通信常见问题

在工业自动化和测试测量等应用中&#xff0c;使用LabVIEW的VISA函数与设备进行通信时&#xff0c;若发送指令后未能接收数据&#xff0c;以下因素可能是原因&#xff1a; 设备未响应或响应延迟应用示例&#xff1a;例如&#xff0c;在控制测量仪器&#xff08;如电压表&#xf…...

Node.js Stream(流)以及模块系统使用介绍 (基础介绍 五)

Stream(流) Stream 是 Node.js 中非常重要的一个模块&#xff0c;应用广泛。 Stream 是一个抽象接口&#xff0c;Node 中有很多对象实现了这个接口。例如&#xff0c;对http 服务器发起请求的request 对象就是一个 Stream&#xff0c;还有stdout&#xff08;标准输出&#xf…...

嵌入式linux中设备树控制硬件的方法

大家好,今天主要给大家分享一下,如何使用linux系统下的设备树进行硬件控制方法。 第一:linux系统中设备树驱动LED原理 在linux系统中可以使用设备树向Linux内核传递相关的寄存器地址,linux驱动中使用OF函数从设备树中获取所需的属性值,然后使用获取到的属性值来初始化相关…...

定时器入门:Air780E定时器基础与进阶

今天我们学习的是Air780E定时器基础与进阶&#xff0c;让大家更深入的了解定时器。 一、定时器(timer)的概述 在Air780E模组搭载的LuatOS系统中&#xff0c;定时器&#xff08;timer&#xff09;是一项基础且关键的服务。它允许开发者在特定的时间点或周期性地执行代码段&…...

Java LeetCode练习

3216. 交换后字典序最小的字符串 package JavaExercise;public class Exercise {public static void main(String[] args) {String s "45320";Solution solution new Solution();System.out.println(solution.getSmallestString(s));} }class Solution {public St…...

go 集成go-redis 缓存操作

一、什么是Go Redis 这是一个流行的Go语言Redis客户端库&#xff0c;它提供了细化的API&#xff0c;对每个Redis命令的功能进行了封装&#xff0c;使得用户只需记住命令&#xff0c;具体的用法可以直接查看接口的声明&#xff0c;使用成本较低。go-redis对数据类型按照Redis底…...

python数据结构基础(3)

书接上文.要创建一个单链表类,首先是初始化方法: class singlelink:def __init__(self):self.head Noneself.tail Noneself.length0return 判断链表是否为空: def isempty(self):return self.length 0 向链表尾部添加节点: def add_node(self,item):if not isinstance(…...

java-智能识别车牌号_基于spring ai和开源国产大模型_qwen vl

用大模型做车牌号识别&#xff0c;最简单高效 在Java场景中&#xff0c;java识别车牌号的需求非常普遍。过去&#xff0c;我们主要依赖OCR等传统方法来实现java识别车牌号&#xff0c;但这些方法的效果往往不稳定。随着技术的发展&#xff0c;现在有了更先进的解决方案——大模…...

全局池化(Global Pooling)

普通池化操作看这里&#xff1a;最大池化&#xff08;Max Pooling&#xff09;和平均池化&#xff08;Average Pooling&#xff09; 全局池化&#xff08;Global Pooling&#xff09; 是一种特殊的池化方法&#xff0c;主要包括&#xff1a; 全局平均池化&#xff08;Global …...

ubuntu 24.04运行chattts时cuda安装错误原因分析

使用ubuntu 24.04&#xff0c;按照2noise/ChatTTS官方流程安装依赖时报错。ChatTTShttps://github.com/2noise/ChatTTS 这是因为cuda版本不对&#xff0c;ChatTTS目前的版本&#xff0c;要求支持cuda 12.4及以上&#xff0c;但是如果nvidia显卡驱动版本较老&#xff0c;无法支…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

Matlab实现任意伪彩色图像可视化显示

Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中&#xff0c;如何展示好看的实验结果图像非常重要&#xff01;&#xff01;&#xff01; 1、灰度原始图像 灰度图像每个像素点只有一个数值&#xff0c;代表该点的​​亮度&#xff08;或…...

【iOS】 Block再学习

iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...