字符串比较

网上看到有人也说是他遇到的一道笔试题,那我想这道题目其实还考过很多人。只不过当时是给我笔让我写出来,一下子懵住了,没缓过神来。写的算法时间复杂度为O(n*m),而出题的要求是时间复杂度控制在O(n+m),而且内存和CPU要控制的很小。

已经快一年了,只记得题目的大意是:两个很多的字符串A、B(全部小写字母),请找出A中有,而B中没有的?

如果是用纸写出来,我想思考后也能写出来,而如果只是说(一般最多说一次,实在不理解最多再重复一次,还不能理解,别人可能会认为你理解和沟通上有障碍了)其实还挺考一个人的理解能力和反应能力。

记得我当时是提笔就写,得到的回答是问:是说还能不能继续优化?然后又改了改,同样又问,能不能继续优化。其实这道题并不难,重点是要理解出题的本意,找到最高效的方法,后来要想好后手机(最多140个字符)发给他。

题目有两个信息已经透露出来了:

1、对于比较字符串,尽量避免二次或以上的循环(消耗时间),出这道题希望给出的代码只有一次循环;

2、全部都是小定字母,而小写字母最多只有26个(a-z);

当时直接在手机上写的,代码也不见了,刚自己又写了一遍:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
 <head>
  <title> new document </title>
  <meta name="generator" content="editplus" />
  <meta name="author" content="" />
  <meta name="keywords" content="" />
  <meta name="description" content="" />
  <meta http-equiv='content-type' content='text/html;charset=utf-8' />
 </head>

 <body>
  
<script type="text/javascript">
var s1 = new Array(60999*10).join('abcdefghijklmnopqrstuvwxyz'),
    s2 = '';

!(function() {
    var arr = [], i = 0, s = '';
    
    while (i < 26) {
        i++;
        s = String.fromCharCode(Math.random()*26 + 97);
        arr.push(s);
    }

    s2 = new Array(10000*10).join(arr.join(''));
})();

function getChar(str1, str2) {
    var arr = [],
        s = '';

    for (var i = 97;i < 123 ;i++ ) {
        s = String.fromCharCode(i);
        if (str1.indexOf(s) > -1 && str2.indexOf(s) == -1) {
            arr.push(s);
        }
    }

    return arr.join("");
}

var date1 = +new Date();
var rstStr = getChar(s1, s2);
var date2 = +new Date();

alert('Total Date:' + (date2 - date1) + '\n string is : ' + rstStr);
</script>

 </body>
</html>

在线运行代码:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title> new document </title> </head> <body> </body> </html> 预览代码

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏达摩兵的技术空间

建造者模式解读

732
来自专栏Dawnzhang的开发者手册

开发中我们需要遵循的几个设计原则!(转)

在软件开发中,前人对软件系统的设计和开发总结了一些原则和模式, 不管用什么语言做开发,都将对我们系统设计和开发提供指导意义。本文主要将总结这些常见的原则和具体阐...

1352
来自专栏大数据和云计算技术

算法系列 图数据结构探索(无向图搜索)

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第10篇《无向图搜索》,非常赞!希望对大家有帮助,大家会喜欢!

2164
来自专栏编程

写好Java代码的30条经验总结

无可厚非你是一名程序员,但你真的是一个优秀的程序员吗?答案可不一定了。想要成为一个优秀的程序员,有着良好的代码编写习惯是必不可少的。下面就让我们来看看Java代...

2245
来自专栏一个会写诗的程序员的博客

第1章 JVM语言家族概览

所谓编程语言只是一个抽象的规范,而编译器是这个规范的实现,它是在这个规范的严格定义下被实现的.

2063
来自专栏玄魂工作室

CTF实战30 CTF题目练习和讲解五(讲解部分)

该培训中提及的技术只适用于合法CTF比赛和有合法授权的渗透测试,请勿用于其他非法用途,如用作其他非法用途与本文作者无关

2093
来自专栏微信公众号:Java团长

开发中我们需要遵循的几个设计原则!

在软件开发中,前人对软件系统的设计和开发总结了一些原则和模式, 不管用什么语言做开发,都将对我们系统设计和开发提供指导意义。本文主要将总结这些常见的原则和具体阐...

1021
来自专栏Java面试通关手册

一份送给Java初学者的指南

我自己总结的Java学习的系统知识点以及面试问题,目前已经开源,会一直完善下去,欢迎建议和指导欢迎Star: https://github.com/Snailc...

1593
来自专栏tkokof 的技术,小趣及杂念

Coroutine,你究竟干了什么?

  使用Unity已经有一段时间了,对于Component、GameObject之类的概念也算是有所了解,而脚本方面从一开始就选定了C#,目前来看还是挺明智的:...

561
来自专栏申龙斌的程序人生

零基础学编程009:只显示2位小数

我们仍要继续解决这个问题:如何用Python打印这篇枯燥的《复利数据表》? (1+0.01) ^ 1 = 1.01 (1+0.01) ^ 2 = 1.02 (...

3027

扫码关注云+社区

领取腾讯云代金券