JavaScript 确定一个字符串的所有字符均不同
上次去Google Girls送了我一本面试金典,前天无聊就看了起来,看到的部分目前还是比较基础也有些意思的,在我看到第一堆算法题的时候我说了一句,这个题看着有点简单啊……然后秒被打脸,可以说,所有的题都是想简单就简单,想难就难,主要看你考虑了多少。
今天就拿其中一道题来说说上面的观点。
实现一个算法,确定一个字符串的所有字符是否不同,假设不允许使用额外的数据结构,又该如何处理。
上次去Google Girls送了我一本面试金典,前天无聊就看了起来,看到的部分目前还是比较基础也有些意思的,在我看到第一堆算法题的时候我说了一句,这个题看着有点简单啊……然后秒被打脸,可以说,所有的题都是想简单就简单,想难就难,主要看你考虑了多少。
今天就拿其中一道题来说说上面的观点。
实现一个算法,确定一个字符串的所有字符是否不同,假设不允许使用额外的数据结构,又该如何处理。
标题不知道怎么拟定比较好,总之是讲Promise的吧,基本上算是第一次讲Promise,以前Rails+Angular的时候曾经说过,不过那个时候对于callback hell和Promise解决的东西理解的并不深刻,所以解释的也很肤浅(不明明这次依旧是肤浅的解释)。
首先……V8的Promise性能实在不靠谱,都没有第三方的快,bluebird有一篇性能比较(反正大致是想说自己快吧):http://bluebirdjs.com/docs/benchmarks.html
慢归慢,基本上一些对于性能需求不太迫切的项目还是可以用自带的Promise的,Node6对于ES6的支持已经相当全面了,这一点可以用npm install es-checker
检查一下。(毕竟回调地狱恶心到吐血)。
关于HTTP,从啃完图解HTTP之后,觉得信息量还是有一些的,自然不可能完全都记得清楚,只能记得大概,而自己实现一个似乎能够更好地理解。
本文使用Python,因为原文就是用的Python,也挺好理解的:http://www.codeceo.com/article/make-web-server-1.html
结巴分词是一个跨语言的中文分词器,整体效果还算不错,功能也够用,这里直接用Python了,其他主流语言版本均有提供。
Word2Vec,起源于谷歌的一个项目,在我刚开始接触的时候就关注到了他的神奇,大致是通过深度神经网络把词映射到N维空间,处理成向量之后我们终于可以在自然语言处理上方便的使用它进行一些后续处理。(具体的方法忘了)
Python的gensim
库中有word2vec
包,我们使用这个就可以了,接下来我们就对维基百科进行处理,作为训练集去训练。(包地址:http://radimrehurek.com/gensim/models/word2vec.html)
接下来,我们不可避免的会遇到线程同步问题,这是因为我们涉及到了共享数据的问题(也就是一个数组)。
我们来看看Python的锁:
threadLock = threading.Lock()
在同步的地方,用:
接下来我们差不多能聊起来了,剩下的就是解决上一篇中我们遗留的登出移除问题以及做一个界面,那样我们就能给更多的人用啦。
选择Tkinter,主要是,作为一个没有其他语言GUI基础的人,入门最简单粗暴的方法可能就是这个了。
关于Tkinter,网上的资源其实说不上太多,还是比较难找的,尤其是对于一个写惯了HTML/CSS的,其实是挺痛苦的。
Tkinter的布局教程可以看这里:http://effbot.org/tkinterbook/grid.htm
完成了上一个版本,我们会发现,根本聊不起来啊!
问题的关键在于,我们现在的程序,一次只能干一个事情,你让我等待输入了,我就不能好好输出了。
所以我们需要在此引入多线程的概念,多线程的概念,简单的来说,就是,我因为只有一个人,你让我去干一件事还可以,两件事我不行,那多加一个人,总可以干了。
那么阻塞呢,意思就是说:由于我干了这个,不能干那个,我们把这个现象叫做阻塞。
概念都理解了之后,我们知道了,只要多加一个线程就行了!
实现多线程有几种方法,具体来说,我们可以看一下这篇:
http://www.cnblogs.com/tqsummer/archive/2011/01/25/1944771.html
接下来我们首先略过了Python的基础,这一部分,随便找一本Python的书看看就行了,习惯了没有;
的人生之后,在必须的语句里记得加:
,基本上你就进入了Python模式。
当然,由于赶时间,这里很多可能不是最优写法,大家可以去GitHub提出=v=。
官网Demo有云:
# Echo server program
import socket
HOST = '' # Symbolic name meaning all available interfaces
PORT = 50007 # Arbitrary non-privileged port
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind((HOST, PORT))
s.listen(1)
conn, addr = s.accept()
print 'Connected by', addr
while 1:
data = conn.recv(1024)
if not data: break
conn.sendall(data)
conn.close()
依旧还是面试题,比较麻烦的是,这个排序的关键在于,我们需要时间复杂度为O(n),空间复杂度为O(1)。
题目大概是这样的,看了输入输出基本就会明白了:
input: arr = ['', 'a', 'b', '', 'a', 'c', '*', 'm']
output: [ '', '', '*', 'a', 'a', 'b', 'c', 'm' ]
问题描述:将数组中的字母与星号分开
这里其实主要没做出来是因为我没有很好地理解怎么计算复杂度,尤其是空间复杂度,时间复杂度我勉强记忆成for循环的嵌套还是可以的,但是空间复杂度呢?
面试时还被问到多维数组如何转换成一维数组的问题,这个问题比较灵活,其实也有很多种解法,当然,考虑到面试时候比较紧张,还是踏踏实实的用传统的方法来,和深拷贝一样,依旧是使用递归。
由于没有额外需要考虑的东西,因此这题实际上比起深拷贝来说要简单许多:
var convert = function(arr) {
var newArr = [];
arr.forEach(function(val) {
if (val instanceof Array) {
Array.prototype.push.apply(newArr, convert(val));
} else {
newArr.push(val);
}
});
return newArr;
};