首页 > 编程语言 >leedcode【383】. 赎金信——Java解法

leedcode【383】. 赎金信——Java解法

时间:2024-05-28 12:33:34浏览次数:30  
标签:ransomNote false int length leedcode magazine 383 Java data

Problem: 383. 赎金信

  1. 题目
  2. 思路
  3. 解题方法
  4. 复杂度
  5. Code
  6. 性能

题目

给你两个字符串: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 <= 105
ransomNote 和 magazine 由小写英文字母组成

思路

因为题目说只有小写字母,那可以采用空间换取时间的哈希策略,用一个长度为26的数组来记录magazine里字母出现的次数。

然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。

解题方法

数组在哈希法中的应用。

为什么不用map?
在本题的情况下,使用map的空间消耗要比数组大一些的,因为map要维护红黑树或者哈希表,而且还要做哈希函数,是费时的!数据量大的话就能体现出来差别了。 所以数组更加简单直接有效!

复杂度

时间复杂度:

O(n)

空间复杂度:

O(1)

Code

Java

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

性能

image.png

标签:ransomNote,false,int,length,leedcode,magazine,383,Java,data
From: https://blog.csdn.net/qq_42631788/article/details/139259718

相关文章

  • 前端小白必知必会:JavaScript的作用域
    文章导读:AI辅助学习前端,包含入门、进阶、高级部分前端系列内容,当前是JavaScript的部分,瑶琴会持续更新,适合零基础的朋友,已有前端工作经验的可以不看,也可以当作基础知识回顾。这篇文章瑶琴带大家学习 javascript中关于变量作用域的相关知识点。在JavaScript中,变量的作用......
  • Java-生成固定长度的随机字符串、随机字符串开头的ID、写入文件、读取文件
    packagecom.sgcc;importjava.io.*;importjava.text.DecimalFormat;importjava.util.ArrayList;importjava.util.List;importjava.util.Random;publicclassMain{publicstaticStringgenerateMixedString(intlength){Randomrandom=ne......
  • Java多线程与并行计算:深入剖析Java线程,线程池,以及利用Java进行并行计算的策略
    一、Java线程概述线程基础概念: 线程是操作系统调度的最小单元,它是进程的一部分,每个线程都有自己的程序计数器、栈和局部变量。线程之间共享进程的堆和方法区。 Java线程创建和启动: 在Java中主要有两种方式创建线程: 继承Thread类:创建一个新class,继......
  • Java项目-基于springboot+vue的时间管理系统(源码+数据库+文档)​
    如需完整项目,请私信博主基于SpringBoot+Vue的时间管理系统开发语言:Java数据库:MySQL技术:SpringBoot+MyBatis+Vue.js工具:IDEA/Ecilpse、Navicat、Maven在Internet高速发展的今天,我们生活的各个领域都涉及到计算机的应用,其中包括时间管理系统的网络应用,在外国时间管理系统已经......
  • Java项目-基于springboot+vue的社区维修平台(源码+数据库+文档)​
    如需完整项目,请私信博主基于SpringBoot+Vue的社区维修平台开发语言:Java数据库:MySQL技术:SpringBoot+MyBatis+Vue.js工具:IDEA/Ecilpse、Navicat、Maven21世纪的今天,随着社会的不断发展与进步,人们对于信息科学化的认识,已由低层次向高层次发展,由原来的感性认识向理性认识提高,管......
  • 【Java】变量_数据类型
    1、变量1.1简介在JavaSE(JavaPlatform,StandardEdition)中,变量是用于存储数据的容器,每个变量都有一个类型,这个类型决定了变量可以存储的数据种类以及存储这些数据所需的内存空间大小。下面将详细介绍Java中变量的声明和数据类型。1.2变量声明变量必须要先声明,才能使用......
  • Java网络编程
    Java网络编程是Java编程中一个非常重要的领域,它为程序员提供了构建网络应用程序的能力。在当今互联网时代,网络应用程序无处不在,从简单的客户端-服务器通信到复杂的分布式系统,Java网络编程都扮演着关键角色。网络模型在探讨Java网络编程之前,让我们先了解一下计算机网......
  • 滑动窗口-java
    主要通过单调队列来解决滑动窗口问题,得到滑动窗口中元素的最大值和最小值。目录前言一、滑动窗口二、算法思路1.滑动窗口 2.算法思路3.代码详解三、代码如下1.代码如下2.读入数据3.代码运行结果总结前言主要通过单调队列来解决滑动窗口问题,得到滑动窗口中......
  • JAVA------基础篇
    java基础1.JDKJDK:javadevelopmentkitJRE:javaruntimeenvironmentJDK包含JREjava跨平台:因为java程序运行依赖虚拟机,虚拟机需要有对应操作系统的版本,而jre中有虚拟机。当你想要在Linux系统下运行,则需要安装对应的虚拟机,及对应的jdk版本,而对应的jdk版本中的jre有对......
  • 基于Java的高校学生勤工助学优派系统的设计与实现(论文+源码)_kaic
    摘  要高校勤工助学管理系统的出现,让学生的工作更加标准,不仅仅使高校办公室的办公水平以及管理水平大大提高,还优化了勤工助学资金的使用方式方法,完善了资助所需费用的资源配置,可以卓有成效地缩减学校的管理经费。本系统主要采取Java语言以及面向对象的开发模式,进行编码和......