文档章节

关于腾讯的一道字符串匹配的面试题

大数据之路
 大数据之路
发布于 2012/09/16 00:33
字数 411
阅读 600
收藏 7

Question:

 假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,

 比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,

 所以这两个字符串是匹配的。要求高效!

 

Answer:

假定字符串中都是ASCII字符。如下用一个数组来计数,前者加,后者减,全部为0则匹配。

static bool IsMatch(string s1, string s2)
        {
            if (s1 == null && s2 == null) return true;
            if (s1 == null || s2 == null) return false;

            if (s1.Length != s2.Length) return false;

            int[] check = new int[128];

            foreach (char c in s1)
            {
                check[(int)c]++;
            }
            foreach (char c in s2)
            {
                check[(int)c]--;
            }
            foreach (int i in check)
            {
                if (i != 0) return false;
            }

            return true;
        }

 

如果使用python的话,就更简单了:

  1. >>> sorted('abcda') == sorted('adabc')
  2. True

复制代码Geek的玩法很多,除了有人先提到的上面做法,我还想到以下方法也挺Geek:

  1. >>> from collections import Counter
  2. >>> Counter('abcda') == Counter('adabc')
  3. True

复制代码 (Counter类在Python 2.7里被新增进来)

看看结果,是一样的:

  1. >>> Counter('abcda')
  2. Counter({'a': 2, 'c': 1, 'b': 1, 'd': 1})
  3. >>> Counter('adabc')
  4. Counter({'a': 2, 'c': 1, 'b': 1, 'd': 1})

复制代码 另外,可以稍微格式化输出结果看看,用到了Counter类的elements()方法:

  1. >>> list(Counter('abcda').elements())
  2. ['a', 'a', 'c', 'b', 'd']
  3. >>> list(Counter('adabc').elements())
  4. ['a', 'a', 'c', 'b', 'd']

复制代码

 

REF:

 http://blog.sina.com.cn/s/blog_5fe9373101011pj0.html

http://bbs.chinaunix.net/thread-3770641-1-1.html

http://topic.csdn.net/u/20120908/21/F8BE391F-E4F1-46E9-949D-D9A640E4EE32.html

最新九月百度人搜,阿里巴巴,腾讯华为京东小米笔试面试二十题

http://blog.csdn.net/v_july_v/article/details/7974418 

精选30道Java笔试题解答

http://www.cnblogs.com/lanxuezaipiao/p/3371224.html

 

© 著作权归作者所有

共有 人打赏支持
大数据之路
粉丝 1510
博文 516
码字总数 342856
作品 0
武汉
架构师
加载中

评论(2)

刘毕维
代码是简洁,但需要是高效,应当分析执行时间。
江斌
江斌
这题ascii就每没啥好说了
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
2018 前端面试准备

前端面试常见问题按知识点分类整理 前端面试常考问题整理,按模块知识点分类,持续完善中... Front-end-Developer-Questions by Modules and knowledge 前端面试经典问题:CSS 中居中的几种方...

掘金官方
2017/12/14
0
0
一道ISCC题引申的PHP正则复习

iscc中的一道web题“试试看”,描述为随意开火 起初看url,以为是一道常规的文件包含题,后面试了很多方法都出不来 最后受到其他师傅的启发才得到payload 这里有两种payload都可以 (PHP 4, ...

日生三金
05/15
0
0
九月十月百度,迅雷,华为,阿里巴巴最新校招笔试面试二十题(10.12)

九月十月百度,迅雷,华为,阿里巴巴,最新校招笔试面试二十题 题记 本博客自2010年10月11日开通以来,已经帮助了一大批人找到工作,特别是连续三年在每一年的9、10月份陪伴了至少三届毕业生...

mickelfeng
2013/10/12
0
0
各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 1...

云栖希望。
2017/12/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

00.编译OpenJDK-8u40的整个过程

前言 历经2天的折腾总算把OpenJDK给编译成功了,要说为啥搞这个,还得从面试说起,最近出去面试经常被问到JVM的相关东西,总感觉自己以前学的太浅薄,所以回来就打算深入学习,目标把《深入理...

凌晨一点
25分钟前
0
0
python: 一些关于元组的碎碎念

初始化元组的时候,尤其是元组里面只有一个元素的时候,会出现一些很蛋疼的情况: def checkContentAndType(obj): print(obj) print(type(obj))if __name__=="__main__": tu...

Oh_really
昨天
1
2
jvm crash分析工具

介绍一款非常好用的jvm crash分析工具,当jvm挂掉时,会产生hs_err_pid.log。里面记录了jvm当时的运行状态以及错误信息,但是内容量比较庞大,不好分析。所以我们要借助工具来帮我们。 Cras...

xpbob
昨天
65
0
Qt编写自定义控件属性设计器

以前做.NET开发中,.NET直接就集成了属性设计器,VS不愧是宇宙第一IDE,你能够想到的都给你封装好了,用起来不要太爽!因为项目需要自从全面转Qt开发已经6年有余,在工业控制领域,有一些应用...

飞扬青云
昨天
1
0
我为什么用GO语言来做区块链?

Go语言现在常常被用来做去中心化系统(decentralised system)。其他类型的公司也都把Go用在产品的核心模块中,并且它在网站开发中也占据了一席之地。 我们在决定做Karachain的时候,考量(b...

HiBlock
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部