文档章节

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

大数据之路
 大数据之路
发布于 2012/09/16 00:33
字数 411
阅读 597
收藏 7
点赞 0
评论 2

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

 

© 著作权归作者所有

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

评论(2)

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

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

chambai ⋅ 2012/08/05 ⋅ 0

2018 前端面试准备

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

掘金官方 ⋅ 2017/12/14 ⋅ 0

数据结构与算法面试题80道

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

_子墨 ⋅ 2014/10/22 ⋅ 0

算法面试题总结

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

笨笨熊 ⋅ 2011/03/13 ⋅ 0

一道ISCC题引申的PHP正则复习

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

日生三金 ⋅ 05/15 ⋅ 0

各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

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

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

工作面试

2016 年末,腾讯,百度,华为,搜狗和滴滴面试题汇总 2016 年未,腾讯,百度,华为,搜狗和滴滴面试题汇总 杭州找Android工作的点点滴滴 写在前面的话 我从14年毕业到现在一直待一个三线城市...

掘金官方 ⋅ 01/04 ⋅ 0

九月十月百度,迅雷,华为,阿里巴巴最新校招笔试面试二十题(10.12)

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

mickelfeng ⋅ 2013/10/12 ⋅ 0

前端相关整理

整理一下最近在网上收集的前端面试相关资料,包括预备知识、书籍、面试考点、面经等。前端方面资料其实太多太多,就光从知乎、前端乱炖、w3cplus 等网站就能找到很多,所以针对细节不发散,仅...

Seas0n_ ⋅ 2016/03/01 ⋅ 0

十道腾讯软件开发工程师面试题

  本来在一家杭州软件测试公司工作,三月初的时候无意中收到深圳腾讯云的电话(对方表明身份后,说看到我的简历,想和我聊聊。当时没有电面经验再加上也没有进来也没有投简历,爽快的答应聊...

程序员客栈 ⋅ 2016/06/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

知乎Java数据结构

作者:匿名用户 链接:https://www.zhihu.com/question/35947829/answer/66113038 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 感觉知乎上嘲讽题主简...

颖伙虫 ⋅ 今天 ⋅ 0

Confluence 6 恢复一个站点有关使用站点导出为备份的说明

推荐使用生产备份策略。我们推荐你针对你的生产环境中使用的 Confluence 参考 Production Backup Strategy 页面中的内容进行备份和恢复(这个需要你备份你的数据库和 home 目录)。XML 导出备...

honeymose ⋅ 今天 ⋅ 0

JavaScript零基础入门——(九)JavaScript的函数

JavaScript零基础入门——(九)JavaScript的函数 欢迎回到我们的JavaScript零基础入门,上一节课我们了解了有关JS中数组的相关知识点,不知道大家有没有自己去敲一敲,消化一下?这一节课,...

JandenMa ⋅ 今天 ⋅ 0

火狐浏览器各版本下载及插件httprequest

各版本下载地址:http://ftp.mozilla.org/pub/mozilla.org//firefox/releases/ httprequest插件截至57版本可用

xiaoge2016 ⋅ 今天 ⋅ 0

Docker系列教程28-实战:使用Docker Compose运行ELK

原文:http://www.itmuch.com/docker/28-docker-compose-in-action-elk/,转载请说明出处。 ElasticSearch【存储】 Logtash【日志聚合器】 Kibana【界面】 答案: version: '2'services: ...

周立_ITMuch ⋅ 今天 ⋅ 0

使用快嘉sdkg极速搭建接口模拟系统

在具体项目研发过程中,一旦前后端双方约定好接口,前端和app同事就会希望后台同事可以尽快提供可供对接的接口方便调试,而对后台同事来说定好接口还仅是个开始、设计流程,实现业务逻辑,编...

fastjrun ⋅ 今天 ⋅ 0

PXE/KickStart 无人值守安装

导言 作为中小公司的运维,经常会遇到一些机械式的重复工作,例如:有时公司同时上线几十甚至上百台服务器,而且需要我们在短时间内完成系统安装。 常规的办法有什么? 光盘安装系统 ===> 一...

kangvcar ⋅ 昨天 ⋅ 0

使用Puppeteer撸一个爬虫

Puppeteer是什么 puppeteer是谷歌chrome团队官方开发的一个无界面(Headless)chrome工具。Chrome Headless将成为web应用自动化测试的行业标杆。所以我们很有必要来了解一下它。所谓的无头浏...

小草先森 ⋅ 昨天 ⋅ 0

Java Done Right

* 表示难度较大或理论性较强。 ** 表示难度更大或理论性更强。 【Java语言本身】 基础语法,面向对象,顺序编程,并发编程,网络编程,泛型,注解,lambda(Java8),module(Java9),var(...

风华神使 ⋅ 昨天 ⋅ 0

Linux系统日志

linux 系统日志 /var/log/messages /etc/logrotate.conf 日志切割配置文件 https://my.oschina.net/u/2000675/blog/908189 logrotate 使用详解 dmesg 命令 /var/log/dmesg 日志 last命令,调......

Linux学习笔记 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部