力扣经典150题第三十九题:赎金信

2024-04-24 20:28

本文主要是介绍力扣经典150题第三十九题:赎金信,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 力扣经典150题第三十九题:赎金信
    • 引言
    • 题目详解
    • 解题思路
    • 代码实现
    • 示例演示
    • 复杂度分析
    • 总结

力扣经典150题第三十九题:赎金信

引言

本篇博客介绍了力扣经典150题中的第三十九题:赎金信。题目要求判断字符串 ransomNote 是否能由字符串 magazine 中的字符构成,且 magazine 中的每个字符只能使用一次。

题目详解

给定两个字符串 ransomNotemagazine,要求判断 ransomNote 是否能由 magazine 中的字符构成。具体要求如下:

  • magazine 中的每个字符只能在 ransomNote 中使用一次。
  • 如果能够构成,则返回 true;否则返回 false
    示例 1:

输入:ransomNote = “a”, magazine = “b”
输出:false
示例 2:

输入:ransomNote = “aa”, magazine = “ab”
输出:false
示例 3:

输入:ransomNote = “aa”, magazine = “aab”
输出:true

解题思路

为了判断 ransomNote 是否能由 magazine 中的字符构成,可以利用哈希表记录 magazine 中每个字符的出现次数,然后逐个检查 ransomNote 中的字符是否可以在哈希表中找到并且次数不超过 magazine 中的剩余次数。

具体步骤如下:

  1. 使用哈希表 magazineCount 统计 magazine 中每个字符出现的次数。
  2. 遍历 ransomNote 中的每个字符,查看是否在 magazineCount 中,并且对应字符的剩余次数大于 0
  3. 如果所有字符都满足条件,则返回 true;否则返回 false

通过上述步骤,可以判断 ransomNote 是否能由 magazine 中的字符构成。

代码实现

import java.util.HashMap;
import java.util.Map;public class RansomNote {public boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() > magazine.length()) {return false;}// 哈希表记录 magazine 中每个字符的出现次数Map<Character, Integer> magazineCount = new HashMap<>();for (char ch : magazine.toCharArray()) {magazineCount.put(ch, magazineCount.getOrDefault(ch, 0) + 1);}// 检查 ransomNote 中的字符是否能够由 magazine 构成for (char ch : ransomNote.toCharArray()) {if (!magazineCount.containsKey(ch) || magazineCount.get(ch) <= 0) {return false;}magazineCount.put(ch, magazineCount.get(ch) - 1);}return true;}public static void main(String[] args) {RansomNote solution = new RansomNote();// 示例测试String ransomNote1 = "a";String magazine1 = "b";System.out.println("ransomNote: " + ransomNote1 + ", magazine: " + magazine1);System.out.println("结果: " + solution.canConstruct(ransomNote1, magazine1));String ransomNote2 = "aa";String magazine2 = "ab";System.out.println("ransomNote: " + ransomNote2 + ", magazine: " + magazine2);System.out.println("结果: " + solution.canConstruct(ransomNote2, magazine2));String ransomNote3 = "aa";String magazine3 = "aab";System.out.println("ransomNote: " + ransomNote3 + ", magazine: " + magazine3);System.out.println("结果: " + solution.canConstruct(ransomNote3, magazine3));}
}

示例演示

展示了三个不同的示例测试,验证了 ransomNote 是否能由 magazine 中的字符构成的功能。

复杂度分析

该解法的时间复杂度为 O(m + n),其中 m 是 ransomNote 的长度,n 是 magazine 的长度。空间复杂度为 O(n),用于存储 magazine 中每个字符的出现次数。

总结

本篇博客介绍了如何判断 ransomNote 是否能由 magazine 中的字符构成。通过使用哈希表记录字符出现次数,并逐个检查 ransomNote 中的字符是否满足条件,最终实现了判断功能。

这篇关于力扣经典150题第三十九题:赎金信的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/932757

相关文章

HotSpot虚拟机的经典垃圾收集器

读《深入理解Java虚拟机》第三版笔记。 关系 Serial、ParNew、Parallel Scavenge、Parallel Old、Serial Old(MSC)、Concurrent Mark Sweep (CMS)、Garbage First(G1)收集器。 如图: 1、Serial 和 Serial Old 收集器 2、ParNew 收集器 3、Parallel Sc

STL经典案例(四)——实验室预约综合管理系统(项目涉及知识点很全面,内容有点多,耐心看完会有收获的!)

项目干货满满,内容有点过多,看起来可能会有点卡。系统提示读完超过俩小时,建议分多篇发布,我觉得分篇就不完整了,失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份:管理员、实验室教师、学生 管理员:给学生和实验室教师创建账号并分发 实验室教师:审核学生的预约申请 学生:申请使用实验室 高校实验室包括:超景深实验室(可容纳10人)、大数据实验室(可容纳20人)、物联网实验

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

嵌入式面试经典30问:二

1. 嵌入式系统中,如何选择合适的微控制器或微处理器? 在嵌入式系统中选择合适的微控制器(MCU)或微处理器(MPU)时,需要考虑多个因素以确保所选组件能够满足项目的具体需求。以下是一些关键步骤和考虑因素: 1.1 确定项目需求 性能要求:根据项目的复杂度、处理速度和数据吞吐量等要求,确定所需的处理器性能。功耗:评估系统的功耗需求,选择低功耗的MCU或MPU以延长电池寿命或减少能源消耗。成本

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的,但是可能代码比较复杂,这回来个简洁版的,这个是递归版本 可以看看之前的版本,两个版本面试用哪个都保过 解法都在代码里,不懂就留言或者私信 class Solution {/**对于之前的解法,我现在提供一共更优的解,但是这种可能会比较难懂一些(思想方面)代码其实是很简洁的,总体思想如下:不需要排序直接把所有数放入map,map的key是当前数字,value是当前数开始的

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1