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

2024.1.7力扣每日一题——赎金信

2024.1.7

      • 题目来源
      • 我的题解
        • 方法一 哈希表
        • 方法二 数组

题目来源

力扣每日一题;题序:383

我的题解

方法一 哈希表

使用哈希表记录ransomNote中所需字符的数量,然后遍历magazine并将哈希表中存在的对应的数量减一

时间复杂度:O(n+m)。n表示ransomNote的长度,m表示magazine的长度
空间复杂度:O(n)。

public boolean canConstruct(String ransomNote, String magazine) {Map<Character,Integer> need=new HashMap<>();for(Character ch:ransomNote.toCharArray()){need.put(ch,need.getOrDefault(ch,0)+1);}for(Character ch:magazine.toCharArray()){if(need.containsKey(ch))need.put(ch,need.get(ch)-1);}for(Character key:need.keySet()){if(need.get(key)>0)return false;}return true;
}
方法二 数组

由于都是小写字母,所以可以使用数组代替哈希表
这里采用先求magazine中的各个字母的数量,然后去匹配ransomNote,这样可以在匹配的过程中判断magazine某个字符不存在或者该字符的数量不足以组成ransomNote,可以提前结束后续的计算。

时间复杂度:O(n+m)
空间复杂度:O(|S|)。|S|=26

public boolean canConstruct(String ransomNote, String magazine) {int[] rans=new int[26];for(int i=0;i<magazine.length();i++){char ch=magazine.charAt(i);rans[ch-'a']++;}for(int i=0;i<ransomNote.length();i++){char ch=ransomNote.charAt(i);rans[ch-'a']--;if(rans[ch-'a']<0)return false;}return true;}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

http://www.lryc.cn/news/275647.html

相关文章:

  • C#中List<T>底层原理剖析
  • Leetcode 3003. Maximize the Number of Partitions After Operations
  • MySQL第一讲:MySQL知识体系详解(P6精通)
  • 逻辑回归简单案例分析--鸢尾花数据集
  • Python print 高阶玩法
  • Wpf 使用 Prism 实战开发Day09
  • 网络端口(包括TCP端口和UDP端口)的作用、定义、分类,以及在视频监控和流媒体通信中的定义
  • flink如何写入es
  • Java、Python、C++和C#的界面开发框架和工具的重新介绍
  • Java二叉树的遍历以及最大深度问题
  • Apollo 9.0搭建问题记录
  • 【心得】PHP文件包含高级利用攻击面个人笔记
  • [scala] 列表常见用法
  • python 使用urllib3发起post请求,携带json参数
  • 深入理解堆(Heap):一个强大的数据结构
  • 抖音在线查权重系统源码,附带查询接口
  • Spring Framework和SpringBoot的区别
  • 2024--Django平台开发-Django知识点(三)
  • Github 2024-01-08开源项目周报 Top14
  • vue3 的内置组件汇总
  • ARM工控机Node-red使用教程
  • Visual Studio 发布程序自动更新 ClickOnce和AutoUpdater测试
  • Codeforces Round 761 (Div. 2) E. Christmas Chocolates(思维题 树的直径 二进制性质 lca)
  • 知识图谱之汽车实战案例综述与前瞻分析
  • 网关Gateway
  • java 生成一个当前时间的时间搓
  • 金融中IC和IR的定义
  • Git(2):Git环境的安装
  • Pytest单元测试系列[v1.0.0][pytest插件常用技巧]
  • 嵌入式培训机构四个月实训课程笔记(完整版)-Linux系统编程第五天-Linux消息共享内存练习题(物联技术666)