【LeetCode哈希表#1】有效的字母异位词(数组)

有效的字母异位词

力扣题目链接(opens new window)

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

思路

暴力法

两层for循环,逐个比较输入的两字符串的所有字母是否是相同的,如果是,则为字母异位词

class Solution {
    public boolean isAnagram(String s, String t) {
        int count = 0;
        for(int i = 0; i < s.length(); i++){
            for(int j = 0; j < t.length(); j++){
                if(s.charAt(i) == t.charAt(j)){
                    count++;
                }
            }
        }

        if(count == s.length()){
            return true;
        }else{
            return false;
        }
    }
}

问题:没有考虑相同字母多次出现的情况

目前暴力法的复杂度已经是n*n了,加上相同字母的标记肯定更复杂,很可能超时

应该使用后别的更优的方法去解题

哈希法

要用哈希法,那肯定要选择一种哈希结构来储存数据(区别于简介:详见)

  • 数组
  • set
  • map

选哪种呢?

本题给的数据输入是字符串,且条件是字符串只包含小写字母

也就是a-z,一共26个

除此之外,字母a-z的ASCII码是连续的

小规模连续数据,我们可以考虑用数组来存储

先定义一个长度为26的数组hash

遍历字符串s,记录每个字母出现的次数,并在hash的对应位置累加(就是++)

然后遍历字符串t,记录每个字母出现的次数,并在hash对应位置累减(就是--)

当遍历结束,我们去访问数组的所有元素

如果均为0,那么代表着字符串s中的字母也在字符串t中出现了一遍(因此累加累减相互抵消)

如果出现了不是0的数,那么至少有一方的某个字母多出现几次,则不满足条件

这样就可以判断这个字符串是否为字母异位词

代码

思路大致就是上面的,但是代码实现起来依旧有技巧(感觉每道题都差不多是这样,要么代码有坑要么思路有坑)

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] hash = new int[26];

        for(int i = 0; i < s.length(); i++){
            // //获取当前字母所在位置
            // //通过与a作差就能够过ASCII码的差值找到当前之母的对应位置
            // //例如,a和a相减是ASCII值相减,结果为0,a也就位于字母表0~25的第0个
            // int index_s = s.charAt(i) - 'a';
            // //对应字母出现次数计数累加
            // hash[index_s]++;
            //合起来写如下
            hash[s.charAt(i) - 'a']++;
        }

        for(int j = 0; j < t.length(); j++){
            // //同理
            // int index_t = t.charAt(j) - 'a';
            // hash[index_t]--;
            hash[t.charAt(j) - 'a']--;
        }

        //判断hash数组是否全为0
        for(int i = 0; i < 26; i++){
            if(hash[i] != 0){
                return false;
            }
        }
        return true;
    }
}
考察点总结
1、定位字母所在位置

这里使用了ASCII码值相减的方法来确定遍历到的字母具体位于0~25的哪里

实现这种方式的前提是:字母的ASCII码是连续的

2、遍历字符串

Java中:

str = "dayceng" 
for(int j = 0; j < str.length(); j++){
    //使用charAt()来得到字符串中j位置的字母
    System.out.println(str.charAt(j));            
   }

CPP中:

str = "dayceng" 
for(int j = 0; j < str.size(); j++){
    //直接把字符串当成类似Python中的"列表"来操作即可
    cout << str[j] << endl;
}
本文转载于网络 如有侵权请联系删除

相关文章

  • 服务器软件大扫盲

    先说一句哈,自从在B站开始刷视频后,我就觉得要学的内容实在是太多了。这篇“服务器软件大扫盲”就是我看了羊哥的一期视频后有感而发的,比如说Web服务器、HTTP服务器、应用服务器这三个概念,我是见过很多次,但如果你非要我说出它们之间的区别的话,我只好哑口无言。还有,我自己用过的Tomcat、Nginx、Apache、Jetty、Undertow,它们之间有什么优缺点,嗯。。。。。。只好继续哑口无言。可能有很多小伙伴和我一样,用过,但具体的差别还真的说不上来,所以我打算借这个机会来和大家一起学习下。(我就是课代表,我骄傲)先来说Web服务器,它一般指的是网站服务器,可以向浏览器(PC端或者移动端)等Web客户端提供服务,供请求数据或者下载数据。服务器使用HTTP(超文本传输协议)和客户端浏览器进行通信,因此我们也把Web服务器称作为HTTP服务器。再来说应用服务器,它是一种软件框架,提供一个应用程序运行的环境。通常用于为应用程序提供安全、数据、事务支持、负载平衡大型分布式系统管理等服务。在我看来,Web服务器和应用服务器之间的界限已经非常模糊,后者更高级一点,就好像公司与企业这两个名词之间

  • 实战 | 单区域OSPF典型组网配置案例

    组网及说明在实际组网中,经常会遇到OSPF组网的案例,比如单区域OSPF、多区域OSPF、OSPF虚链路、OSPFNSSA、OSPFSTUB等需求,以下是单区域OSPF典型组网的配置案例。网络拓扑图:配置步骤配置loopback0地址配置各互联地址创建OSPF进程1,并将各地址在区域0中发布查看OSPF邻居的状态测试PC之间能互联互通配置关键点R1:<H3C>system-view [H3C]sysnameR1 [R1]intLoopBack0 [R1-LoopBack0]ipadd [R1-LoopBack0]ipaddress1.1.1.132 [R1-LoopBack0]quit [R1]intgi0/0 [R1-GigabitEthernet0/0]ipaddress192.168.1.124 [R1-GigabitEthernet0/0]description<connecttoPC> [R1-GigabitEthernet0/0]quit [R1]intgi0/1 [R1-GigabitEthernet0/1]ipaddress

  • 将Elasticsearch直接连接到Java EE应用程序

    时髦的大数据来自3V:音量,种类和速度。卷是指数据的大小,品种是指不同类型的数据,而速度是指数据处理的速度。为了处理持久性大数据,NoSQL数据库可以更快地写入和读取数据。但由于数量众多,搜索引擎需要查找没有大量计算机能力且耗费太多时间的信息。搜索引擎是一种旨在搜索信息的软件系统;这种机制使用户获得他们想要的信息变得更加直接和清晰。本文将介绍NoSQL,它既是文档类型,也是搜索引擎Elasticsearch。Elasticsearch是NoSQL文档类型和基于Lucene的搜索引擎。它提供了一个分布式,支持多租户的全文搜索引擎,具有HTTPWeb界面和无架构JSON文档。Elasticsearch是用Java开发的,并根据ApacheLicense的条款作为开源发布。Elasticsearch是ApacheSolr最受欢迎的企业搜索引擎,后者也基于Lucene。它是一个近乎实时的搜索平台。这意味着从索引文档到可搜索文档的时间有一点延迟(通常是一秒)。搜索引擎中的步骤在Elasticsearch中,搜索引擎的进度基于分析器,该分析器包含三个较低级别的构建块:字符过滤器,标记器和令牌过滤器

  • Linux常用命令 - nl命令详解

    21篇测试必备的Linux常用命令,每天敲一篇,每次敲三遍,每月一循环,全都可记住!! https://www.cnblogs.com/poloyy/category/1672457.html   显示行号,除了空行 默认就是这个 nltest.txtnl-bttest.txt   无论是否为空行,都显示行号 nl-batest.txt   行号靠最左显示 nl-nlntest.txt     行号靠最右显示 nl-nrntest.txt     行号靠最右显示,不足位数左边补0 nl-nrztest.txt       本文作者:小菠萝测试笔记 本文链接:https://www.cnblogs.com/poloyy/p/12609651.html  

  • 002js第二天总结

    三元运算式:varx=10;vary=20;varresult=x>y;x:y; 执行过程:先判断x>y?如果条件满足则输出x,反之输出y; if 一个分支 ifelse 两个分支 ifelseif  多个分支 while  最少一次循环都没执行 dowhlie  至少执行循环一次 swithcase 多个值时用 for  常用循环体

  • struts2 redirect 配置动态传递参数

    <actionname="actionName"class="com.towerking.TestAction"method="executeMethod"> <resultname="success"type="redirect">login.jsp?flag=success&amp;userType=${userType}</result> <resultname="error"type="redirect">login.jsp?flag=error&amp;userType=${userType}</result> </action>复制 在配置Struts2的时候,有时需要配置多个参数,且其中一个参数是根据实际情况动态变化的,则需要通过上述方法进行配置。 其中在XML文件中,配置&需要使用 &amp;复制 否则Struts2会出现如下错误:struts2thereferencetoentitymustendwiththe';'delimiter。 在配置代码中userT

  • 59、序列化二叉树

    一、题目 请实现两个函数,分别用来序列化和反序列化二叉树 二、解法 1/* 2publicclassTreeNode{ 3intval=0; 4TreeNodeleft=null; 5TreeNoderight=null; 6 7publicTreeNode(intval){ 8this.val=val; 9 10} 11 12} 13*/ 14publicclassSolution{ 15publicintindex=-1; 16StringSerialize(TreeNoderoot){ 17StringBuffersb=newStringBuffer(); 18if(root==null){ 19sb.append("#,"); 20returnsb.toString(); 21} 22sb.append(root.val+","); 23sb.append(Serialize(root.left)); 24sb.append(Serialize(root.right)); 25returnsb.toString(); 26 27} 28TreeNodeDeserialize(

  • vue+element ui中el-tabel组件中 &lt;template scope=&quot;scope&quot;&gt;的理解和使用

    通过 Scopedslot 可以获取到row,column,$index和store(table内部的状态管理)的数据。   这篇文章讲的不错 https://blog.csdn.net/tg928600774/article/details/81945140

  • Failed to enable unit: Unit file chronyd.service does not exist.

    因为执行了  systemctldisablechronyd.service 然后再对它执行操作会提示 Failedtoenableunit:Unitfilechronyd.servicedoesnotexist. 原因是服务被disable了,所以不能用了。 解决办法: 1.  systemctlenablechrony 就可以了 ubuntu不要加d,systemctlstatuschrony d是daemon的意思,有些服务不需要加d,看你配置的unit的文件名

  • TabLayout+ViewPager 标题不显示问题

    第一次用TabLayout+ViewPager组合在布局中写好了三个标题预览没问题而且也设置了 app:tabIndicatorColor="@color/colorAccent"app:tabSelectedTextColor="@color/colorAccent"app:tabTextColor="@color/button_nav_font_default"三个属性都设置,当运行在手机上的时候显示空白刚开始以为是手机问题(华为)换了小米手机也是同样的问题,我开始怀疑主题问题了,因为我的主题颜色是全是白色以下代码复制 <stylename="AppTheme"parent="Theme.AppCompat.Light.NoActionBar"><!--Customizeyourthemehere.--><itemname="colorPrimary">@color/white</item><itemname="colorPrimaryDark">@color/white</item><itemname=

  • 给DBA和IT同行的一些建议

    这篇文章和技术无关,但却是每个程序员都需要关注的问题。无它,主要是国内程序员加班文化盛行,这让程序员原本就不太健康的生活习惯更加不健康,所以转载国外程序员ZedA.Shaw写就的文章,希望能给大家带来健康。我最近在写《深度Python》的最后几节课,我还要加一课:关于程序员在其职业生涯中普遍的健康问题。我发现诸多代码人在敲代码的时候好像不在乎他们的身体状况,很可能是太过于全神贯注。我希望人们可以通过知晓一些与编程者相关的健康问题而获益,并可以避免曾经发生在我身上,而且就我知道也发生在很多人身上的问题。我可能不会把这篇博文全部放进《深》里,因为有点多。但我会写个缩减版。请您惠知喜好,或有我可以引用的附加资源。 我的背景和资历 我以前是一等合格美国士兵,并学习过多种武术。近年来我未像过去学武术一样奋力工作,而是专注于瑜伽,入定和一些简单的活动。我小时候是异常健康的,现在依然如故,这归功于我早已根深蒂固的锻炼习惯。首先先列一下我学过的武术:忍术(Ninjitsu),合气道(Aikido),柔术(Judo),泰拳(MuayThai),咏春(WingTsung),卡波耶拉(Capoeira),阿

  • linux挂在win共享文件

    1.先设置共享文件,再网络中查看,有目录则共享成功 2.yumsamba-client (linux系统和win系统共享协议的包) 3.yuminstallcifs-utils此外还要安装这个包,安装好之后查找确认一下 4 新建挂载点 首先需要到linux系统,新建一个挂载点分区。比如/data 5. 挂载win共享文件夹 输入命令:mount-tcifs-ousername=hui,passwd=admin,uid="root",gid="0"//192.168.1.118//Desktop-4duubgf/各种包/mnt/windata   mount-tcifs-ousername=hui,passwd=admin,uid="9006",gid="9006"//192.168.1.118/data3/databak/data mount-t cifs -0  username=win版本系统账号,passwd=win系统密码,uid=“",gid="”(以linux什么账号身份挂载) 共享文件夹共享路径&nbs

  • python3 100道基础练习题001

    题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 参考答案: list1=[] foriinrange(1,5): forjinrange(1,5): forkinrange(1,5): if(i!=k)and(i!=j)and(j!=k): list1.append(i*100+j*10+k) print("1、2、3、4个数字,能组成%d个互不相同且无重复数字的三位数"%len(list1)) print("所有可能的三位数为",list1)复制  

  • js点击页面其他地方如何隐藏div元素菜单

      web页面常用的一个需求,写下拉菜单是我们往往不是用select_option,而是自定义一个元素列出选项来满足需求,当我们点击按钮出现菜单, 点击按钮或菜单以外页面空白地方隐藏该菜单,这里提供一种简单有效的方法仅供参考: 1document.onclick=function(e){         2$("div").hide(); 3} 4$('button').on("click",function(e){         5if($("#div").css("display")=="none"){           6$("#div").show();         7}else{           8$("#div").hide();         9}         10e=e||event; 11stopFunc(e);       12}); 13       14$('#div').on("click",function(e){         15e=e||event; 16stopFunc(e);       17});     18functio

  • 2020牛客寒假算法训练营第二场题解(持续更新中)

    A做游戏 贪心,最多赢多少场只要保证尽可能赢就行了,即石头对应剪刀,剪刀对应布,布对应石头。 #include<iostream> #include<cmath> usingnamespacestd; intmain() { longlonga,b,c,x,y,z; cin>>a>>b>>c>>x>>y>>z; longlongans=0; ans+=min(a,y); ans+=min(b,z); ans+=min(c,x); cout<<ans<<endl; return0; }复制 ViewCode B排数字 题意为给一串数字可以随意打乱保证616字串的数量最多,那么首先我们统计数串中1和6的个数,其他的数字均没有用,题目就转换成了给定数量的1和6,要组合成子串616最多的字符串。 只需要比较6和1的数量即可,分为1的数量>=6的数量-1和1的数量<=6的数量-1两种情况考虑即可 #include<iostream> #incl

  • Make 与 CMake

    Make与CMake CMake入门实战 Make?CMake 首先先来了解一下gcc,gcc是GNUCompilerCollection(就是GNU编译器套件),也可以简单认为是编译器,它可以编译很多种编程语言(包括C、C++、Objective-C、Fortran、Java等等)。当我们的程序只有一个源文件时,直接就可以用gcc命令编译它。 但是当程序包含很多源文件时,用gcc命令逐个去编译时,就很容易混乱而且工作量大。所以就出现了Make工具,例如GNUMake,QT的qmake,微软的MSnmake,BSDMake(pmake),Makepp,等等。它是一个自动化编译工具,我们可以使用一条命令实现完全编译,但是需要编写一个规则文件,Make工具依据它来批量处理编译,这个文件就是Makefile文件。Makefile在一些简单的工程完全可以人工手写,但是当工程非常大的时候,手写Makefile也是非常麻烦的。而且不同的Make工具遵循着不同的规范和标准,所执行的Makefile格式也千差万别。这样就带来了一个严峻的问题:如果软件想跨平台,必须要保证能够在不同平台编译。而如果使

  • Vue.use源码分析

    我想有过vue开发经验的,对于vue.use并不陌生。当使用vue-resource或vue-router等全局组件时,必须通过Vue.use方法引入,才起作用。那么vue.use在组件引入之前到底做了那些事情呢?让我们一窥究竟。 先上vue.use源码 Vue.use=function(plugin){ /*istanbulignoreif*/ if(plugin.installed){ return } //additionalparameters varargs=toArray(arguments,1); args.unshift(this); if(typeofplugin.install==='function'){ plugin.install.apply(plugin,args); }elseif(typeofplugin==='function'){ plugin.apply(null,args); } plugin.installed=true; returnthis };复制 假设我们通过Vue.use引入一个插件plugin(该插件可以暂时理解为一个变量或参数

  • appium python andiroid自动化文档整理笔记

    from appium import webdriver import time,unittest,HTMLTestRunner class Testlogin(unittest.TestCase):     def setUp(self):         self.desired_caps={}         self.desired_caps['platformName'] = 'Android'         self.desired_caps['deviceName']='a6969'         self.desired_caps['

  • mongodb第二篇:聚合

    db.$collectionName.aggregate(),入参是聚合管道阶段(aggregationpipelinestage)数组,数组是有序的,把数组元素调换位置,输出的结果可能不一样。阶段名有: $addFields、$bucket、$bucketAuto、$changeStream、$collStats、$count、$facet、$geoNear、$graphLookup、$group、$indexStats、$limit、$listSessions、$lookup、$match、$merge、$out、$planCacheStats、$project、$redact、$replaceRoot、$replaceWith、$sample、$search、$set、$setWindowFields、$skip、$sort、$sortByCount、$unionWith、$unset、unwind。 参考https://www.mongodb.com/docs/v5.0/reference/operator/aggregation-pipeline/ 阶段名要用$标注。 1、$

  • 第二模块第一章作业

    知识:以后还要再回顾,到时再写复制 str.find()实际返回的是索引值,如果需对查找字符串作条件判断,第一个字符串刚好是索引0,也就是布尔值False,而找不到返回的是-1或者索引非0,则返回true。     ---》用以下方法可对查找字符串作判断,根据.find找不到字符串返回-1的特点,把返回的索引值+1再判断即可,找不到返回-1,+1后刚好变成0,为false,而找得到就算+1也是True复制 #!/usr/bin/envpython#.-*-coding:utf-8-*-#.__author__.='J"#删除信息和第4题只操作一遍,所以不计数n了deffile_to_D():#把文件内容变成以索引为key的字典,每个索引指向一条个人信息globalDD={}f=open('E:test.txt','r')d=f.readlines()foriind:i=i.split(',')i[0]=int(i[0])D[i[0]]=iprint('总表',D)#print(len(D))defsave_to_file():f=open('E:test.txt','w')foriin

  • text

    1,AlexLi,22,13651054608,IT,2013-04-01 2,JackWang,28,13451024608,HR,2015-01-07 3,RainWang,21,13451054608,IT,2017-04-01 4,MackQiao,44,15653354208,Sales,2016-02-01 5,RachelChen,23,13351024606,IT,2013-03-16 6,EricLiu,19,18531054602,Marketing,2012-12-01 7,ChaoZhang,21,13235324334,Administration,2011-08-08 8,KevinChen,22,13151054603,Sales,2013-04-01 9,ShitWen,20,13351024602,IT,2017-07-03 10,ShanshanDu,26,13698424612,Operation,2017-07-02复制 AlexLi,123 JackWang,1234 RainWang,1235 MackQiao,1236 RachelCh

相关推荐

推荐阅读