【四火】 关于RESTful不足的思考

Related image在Amazon的时候,公司内有大量的组来维护不计其数的service,而service之间的通用通讯方式是公司内部的一个框架,协议是自定的,客户端也是内部的;现在到了Oracle,我看到这个变成了RESTful,也就是说,协议本身变成了最常见和适用的一种。我看到有太多论述RESTful优点的文章了,而实际工作中也确实有所体会,比如接口和报文的可读性好,不需要特制的客户端,上手和调试都比较容易等等。但是,如果看到某个东西被冠以过多正面的评价,就要当心了。我也慢慢地体会到了一些问题。不过,在谈谈我的思考之前,我想先明确一下我对REST的认识,而这点,鉴于历史原因,也是我不太愿意花时间争辩的内容。我认为REST是一种设计和架构的方式,体现了系统响应请求交互的风格,而非接口规约,更不是什么报文协议。

对于RESTful的四种HTTP/HTTPS的方法,我看到不同的工程师有着不同的理解,而这点,是缺少足够明确的约束的。

  • 第一个例子,GET、POST、PUT、DELETE分别表示对资源的获取、创建、修改和删除。但是实际操作中,我看到一些不一致的东西。比如修改,我见过有使用PUT的,使用POST的,也有使用PATCH的,很难讲孰对孰错,欠缺的是规约。
  • 第二个例子,使用GET来做查询,清晰简便,但是也有着自己的局限性,其中一个就是参数的携带。明文参数的方法并不适合传递吧比较多的参数,而且如果参数值不是普通字符串或者数值,而是数组等集合,它缺少清晰而友好的传递方式。于是我看到有一些工程师会使用POST来解决这样的问题,这无疑从某种程度上破坏了RESTful的一些规约。
  • 第三个例子——版本的指定:我以前所了解到的,版本是可以再请求头部的Accept头中指定的,但是我看到了一些把版本号放到URL中的解决方案。考虑到REST本来也只是一种方式和风格,不能说这样的做法就是错误的,但我觉得还是缺少一个在REST之上更为细致的协议或者规约。
  • 第四个例子,参数的指定方式,放到问号前面的URI里面去还是放到问号后面的参数键值对里面去,我看到了不一致的处理方式。
  • ……

对于资源名称的定义,也就是RESTful的核心,也不适用于许多问题的解决。我用过SOAP,也用过一些其他的XML协议,REST是更加简洁的一个。如果是针对简单实体的增删改查,RESTful无疑是有效的。换言之,它擅长通用性问题的解决,但是孱弱于特应性问题的处理。但是如果是一个复杂业务的封装,RESTful显得力不从心。这样的封装,之所以不任其发展为通用接口,就是考虑到某些业务的特殊性,而通用接口对于特定场景的优化是不足的。就像一个简单的二维表,一个简单的select-from语句可能就可以解决,但是当业务复杂到多数请求都需要join、filter、map,这就似乎很难用擅长通用性的REST来解决问题了,否则就要创造一大堆不易理解的、不易重用的名词在作为resource了。

前面提到过缺少REST之上更为细致的协议或者规约,这个可以进一步展开说。对于某些基于请求和响应的通用操作,和内部框架+协议的方式比较起来,不太容易统一。比如说鉴权,比如说流控,比如说性能监控,这些东西都是很常用的,但是我看到使用一个专有的内部框架会更方便地嵌入和推广这样的组件,而RESTful的结果就是各个项目组五花八门,对于具体字段的理解也是分歧不少。

最后一个,我想到的是客户端的生成,以前用到的内部框架,可以方便地生成客户端,而客户端的功能也比较强大。但是RESTful了以后,以往的一些客户端丰富的特性都要重头自己实现过,比如说复杂的参数校验,比如一些自动装包解包到业务对象的代码生成等等。事实上,这些工作是不可能省略掉的,没法借助框架完成,就要自己想办法做。我记得以往获知一个service,为了使用客户端,想了解一下schema,很容易就可以得到自动生成的文档,但是现在则完全不能。

基于这些种种的原因,如果从头来过,依然使用RESTful风格的service,为了保持各个service之间的一致性,兴许一个统一的API框架是值得的。我理解速度在如今软件企业中的地位,但是我们总得在和可维护性的博弈中取得一个平衡。

确实软件开发没有银弹,而我自认为对于RESTful不足的思考还是不够深刻,如果你有很好的认识,不妨告诉我。:)

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

via 四火的唠叨 https://ift.tt/2ssvB2q

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 推荐最近玩的几款独立游戏

如今各种平台上的大作满天飞,可是不知道有多少人和我一样,很难对这些大作燃起热情。可是凭着怀旧的心态,去回味一下老游戏,或者所谓的“经典”的时候,却又发现时过境迁,物是人非,一样缺少玩下去的动力。平时工作生活就很忙了,留下属于自己的时间不太多,也不太愿意沉迷太多的时间给或新或老的游戏,再加上随着年龄的增长,似乎对越来越多的事情失去了兴趣。直到某些“独立游戏”出现,由于资金、人力的关系,它们大多没有绚烂的画面,繁冗的剧情,以及漫长的游戏时间,但是由于开发者可以决定它们的走向,始终围绕核心想法构建,于是它们或精致或别样,总能把某一游戏性发挥到极致,让我重新找到许多游戏的快乐。我不算什么资深玩家,在这里稍微推荐几款我非常喜欢的独立游戏。

《贪婪之枪》(Greedy Guns

应该说算横版过关游戏的一种,但是简单的打击、动作和解谜,加上收集各种武器的乐趣,足以让我把这个游戏流程研究来研究去的了。画面精致,风趣幽默,有一点点像合金弹头,但是又很不一样。整个过程路线很清晰,也没有过多的啰嗦的解谜、事件或者收集的要素。(我忽然想到一个反例——《保卫萝卜》,最开始的核心游戏性是无比清晰的,我也曾是铁粉,但是一代不如一代,到第三代的时候,腾讯把他收购了,系统越来越复杂,越来越慢,界面越来越繁杂,什么乱七八糟的公告、活动一股脑儿都出现了,而平衡性则走了下坡路——这游戏也就玩完了。为此我还写过一点点东西。)

360_shooting_256_nodither

《城堡毁灭者》(Castle Crashers

不同的搞笑角色和各种招式,耐玩的连招系统,颇有挑战性的游戏进程。场景丰富而统一,但是关卡适应性可以说很容易。和《贪婪之枪》比起来,最初的游戏画面并没有那么吸引我,但是玩起来真是非常引人入胜,打击做得也比较出色。一样具有规则比较简单,但是要达成多数甚至全部的动物球收集要素,非常具有挑战性,毕竟隐藏元素颇多。遗憾的是我没有和朋友一起玩,这个游戏是支持多玩家的。

cc2

《神圣土豆的武器店》(Holy Potatoes! A Weapon Shop?!

如果说前面的还具有诸多动作成分的话,这款游戏则完完全全是经营养成加策略的风格了。应该说刚上手,其中的规则需要花一些时间去熟悉和掌握,但是之后就可以把主要的精力放到经营和策略的思考上面去了。故事本身很简单,要给各路英雄打造最适合它们的武器,并且卖出高价,以升级设备,聘请更优秀的匠人。对话幽默,而且角色设计都很有喜感。话说回来,游戏制作上也有遗憾,比如难度曲线的不合理——开始的时候难度有一定挑战性,很吸引人,但是到游戏后期,特别是技巧掌握以后,制造武器的效率太高,角色能力太过强大,于是损失了游戏性。但是总体来看,依然是一款非常吸引我的作品。

manage-agency

《史诗经理》(Epic Manager

非常棒的经营、策略和战棋型游戏。故事主要是讲,要带领一支(以及到后来的2、3支)冒险团队,在一个混乱危险的世界里面接纳任务,招募各类角色,完成任务赚取钱财和经营团队。这个游戏吸引我之处在于,把经营、策略和战棋RPG结合得非常出色。需要动脑,并且需要非常努力地开动脑筋,想方设法把这个团队维持下去,发展下去。要说遗憾我觉得有二,一个是对于热衷于培养一个高潜力角色的玩家来说并不友好,游戏本身的思路要求玩家舍得替换掉那些成长起来但薪资代价过高的角色;另一个是在几个年度后游戏落入尾声,对于喜爱长时间经营培养团队的玩家来说,觉得意犹未尽但是游戏必须在那个时间点结束。

SteamPage_ScreenShots_v2_04_Negotiate

就说这四款吧,这些独立游戏我非常推荐,也都放了官方链接,尤其是第一款和第四款。现在,回过头来想想,我发现这样优秀吸引人的独立游戏,都具备这样的几条特点:

  1. 极佳的游戏性。游戏的核心就是玩,不是什么画面也不是什么声音。举例来具体说,如果是打击动作为核心,那么打击感和角色响应玩家操作的动作必须非常自然流畅;如果追求策略,那么要让玩家得以在忍受范围的时间内上手,并且能够通过合理的难度曲线留住玩家。而这一点,并非有资金有人力就可以做到。为什么独立游戏更可能做到这一点?因为做决策的团队就可以是开发团队,最小化沟通损耗,敏捷、简单,但是高效,而且始终可以围绕在核心点子上面,避免被太多琐事耽误。
  2. 画面精致。游戏性是必要条件,但非充分条件。画面“精致”并不意味着画面“华丽”。为什么这些都是2D游戏?如果要做3D,独立游戏的资金和技术往往很难做到。但是2D游戏,画面风格的统一、配色和界面设计的清晰,这些都是可能做到的,也未必需要很大的开发成本。
  3. 简洁。简洁即包括界面、操作简单,容易入手(挖掘游戏潜在元素可以复杂,但是玩家上手不能复杂);还包括整个游戏世界中,玩家需要达成和追求的目标清晰简单——这两条都非常重要,任一条的违背将使得玩家难以在一定时间内获取足够的游戏乐趣,或者分散玩家游戏的核心乐趣。

最后,必须夸一下Steam平台,实在做得太棒了。现在独立游戏我基本都从Steam上找。有一些互联网服务我可以说是好多年的忠实用户,这样的数量很少,而Steam就是其中之一。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

via 四火的唠叨 https://ift.tt/2HuGfPJ

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 关于国内程序员肉身翻墙

Image result for 翻墙本来是没有倾向谈论这个话题的,但是最近邮件或者微信问我这个问题的国内程序员朋友很多,我在这里一并介绍一下,也算作简单的解答。同样的问题就直接参阅即可。事实上,我很乐意收到这样或者那样的问题,也包括肉身翻墙这样的话题,但是也请大家注意一点礼貌,有好几次有程序员没头没脑地微信上跳出来问问题,然而话都说不清楚,或者连个招呼也不会打,更有甚者二话不说直接把log贴过来让我看问题,实在是让人觉得很不舒服。有些我回复了,有些我实在是不想回复了。另外,具体的问题我比较好解答,像有不少人问我,“你觉得美国怎么样?”,我都不知道从何说起。具体问题还是邮件沟通更合适,我答复起来也更舒服,微信更适合有一句没一句的扯淡。另外,要说明的是,因为我是14年搬到西雅图的,并不算待了很久,我也有一些其它国家的程序员朋友,但是我只谈论美国,因为我也没有其它的经历。

首先,我觉得需要问自己一个问题,为什么要出国工作?是一时脑热么?别人的饭碗里的饭,闻起来总是香的;别人的生活,看起来总是美的。但轮到自己的时候,却不一定如此。如果你想去哪个国家工作,那么至少办理旅游签证去玩一玩、看一看吧?签证有时候会很麻烦,这没错,可是连这样的事情都不做的,下了决心立了志愿又有多少可信度呢?现在旅行那么方便,旅游签证又已经是10年签了,出行应该说不能算什么问题。不同人生活上的追求千千万,找到自己最喜欢的,或许才是最合适的。而怎么才能认定喜欢,肯定是去看看最保险了。当明确了目的和原因,那么才往后思考才有足够的意义。

接着,我想泼一点冷水,谈谈我觉得在海外工作令我失去的东西。

1. 朋友和亲人。这不必细谈了。会认识新朋友,但是绝大多数的交际圈和亲人都会远去,而对于远行后父母养老的顾虑,也是很常见的。

2. 便捷的生活。我记得几年前住在北京的时候,下楼就是一条便利街,从吃饭剪头到购物遛狗,日常服务都有了,踢个球打个篮球,边上就是球场和gym,每天可以步行上班,怎一个方便了得……现在呢,不开车出门就相当于残疾一样,最近的公交车站要走很远,更何况公交系统远没有国内发达,经常一小时一班车,还得倒车才能去市区(西雅图)。

3. 职业生涯的某些可能。你可以认为是职业生涯的瓶颈。语言问题和文化问题是夹杂在一起的,本质上是一类问题,无法分开。程序员这样靠技术吃饭的职业,依然需要语言文化这样强力结合的软能力,而这一点,从我观察来看,中国人普遍有短板,基本上能够奋斗到很高职位的母文化为中国文化的程序员,凤毛麟角。

还有很多其他的方面,但主要是以上。知道这些很重要,是帮助冷静下来做trade off的。

至于好的一面,已经有太多的文字了,我只说一点:

体验。不止是生活上。能在世界软件大国中的top 2都当过工程师工作过,实在是一个非常难得的经历。

接着我才说肉身翻墙的方式。据我所知,有这样三种,难度依次增加:

1. 海外读书,现在留学不同于20年前,学校的选择余地也很大。我身边的大多数华人朋友就是在国内读的大学,然后跑出来读研究生。这种方式的好处在于来到美国在语言方面的压力会小一点,并且在学校里右足够的机会得到语言的强化和锻炼。毕业前可以实习,这也是很好的留下工作的机会,比社招面试成功率要高很多。学生签证到期可以申请18个月的opt,因此有若干次机会进行H1B的抽签,如果是美国硕士会有两次不同概率的机会,总体抽中的概率还是比较高的。

2. 在一些大型跨国企业工作,然后藉由L1签证transfer到国外去。这种方式的选择余地没有第一种大,但是适合那些已经走出学校的程序员,先要面试进入外企,然后根据这些外企的内部转岗政策,至少在国内干满一年后,获得海外职位(这很可能需要经过面试、推荐、商谈等不同的阶段)。这种方式的好处在于可以带家属,而且家属在冗长的流程申请到L2的EAD后可以工作。在L1期间如果公司支持,每年都可以申请H1B签证,但是如果没有美国本土的硕士经历,抽中的概率不大,这两年中每年抽中的概率大概不到三成。如果身份没有变化,L签证在5年后到期,必须离境。

3. 直接投海外简历。这种方式最难,并不只是美国直接招聘的公司凤毛麟角,不只是候选人考察bar高,还包括这种方式无法办理L签证,只能走H1B这一条路,这也就意味着能否抽中签证并非自己能够控制,概率见上。如果面试通过,但是H签证没抽到,有的公司会把你送到别的英语国家去等一年继续抽。对于那些拖家带口的程序员来说,这无疑增加了许多不确定性。

当然,无论是哪一种,都会面临大量的签证等等材料的准备,甚至年年如此。身份问题一直是一个比较烦人的问题,通常公司会联系律师代理帮助,但依然会花费很多的心思和时间,但如果对那些文件材料准备看了就头大,恨之入骨的程序员,这显然是件很不好的事情。

最后,回答两个常见的关于海外求职方面的问题。

英语有多重要?就面试而言,英语很重要,但是远没有专业能力重要。能够沟通交流这是必须,否则一定会影响能力的打分。特别是对于投海外简历有兴趣的程序员,电话面试中能够沟通交流是一个必须要做到的事情。在语言层面耽搁的时间越少,留给自己花在问题本身上的思考和沟通交流的时间就越多。现在英语可以不那么好,但是职业的发展来说,英语机会是一个必要条件。我见过不少中文说起来头头是道的程序员,讲英文却要命一样。

适应异地他乡的生活有多难?这要看怎么定义“适应”这个词。直接来工作的话,前三个月会特别困难一点。几年后绝大多数事情都没有太大问题。但是长远看,最大的困难还是在文化上,文化背景的关系,主流的文化圈子还是很难进入,当然我们自己也有自己熟悉的圈子。而这个困难,基本是终生的。这个问题要看你怎么看了,有的人在乎,有的人不在乎。

就说这些吧。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

via 四火的唠叨 https://ift.tt/2J7gUI5

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 评审的艺术——谈谈现实中的代码评审

曾经写过一点关于代码评审(code review)的文章,比如这篇这篇,现在觉得关于它的认识又有了不少更新。软件工程的技术和实践分成两部分,一部分是和书本知识一致的,大约占一半,这部分基本上在大学里就可以学,自学只要方法得当、刻苦努力也可是途径;但是第二部分来自于实际团队、经验,内容通常无法从书本当中获得,而且难说对错,不同的人和不同的经历造就了不同的认识。代码评审就是第二部分颇具槽点,可以大加讨论的典型。

代码评审是展现个性和性格的途径

我本人特别反对一种颇为常见的观点,就是“一个良好运作的项目,不同的人,应该写出一样的代码”。我非常理解这种观点的初衷,一个良好规范约束的团队中,不同的人写出来的代码应当一致。但实际上,能真正这样做的团队,我还根本没有见到过。所谓的一致代码,仔细品味,发现不同的工程师写出来就是不一致。因此“一致”这个词一定是在一定程度内的大体描述而已,并非越一致约好。其实,代码的创造本就是具备个性的。毫无疑问我们应当遵从规约,应当符合习惯,但是一旦试图过度使用它们去约束代码,不但难以落实,而且容易产生无趣、低效和矛盾的氛围。

再回到代码评审上。代码评审本身,以及基于评审意见的来回沟通,和代码本身比起来,要更难以,也更不应该要求一致。我见过许多代码评审的风格,有人喜欢挑小毛病,有人喜欢展开观点夸夸其谈,有人喜欢给实际例子来证明自己的看法……无论哪一种风格,我都不觉得有什么大的问题。但是,就我个人而言,我可以谈谈我自己的代码评审风格:

我会关注三种问题,需求和业务上的问题、代码结构的问题、代码风格格式的问题。

前两种可能存在阻碍我ship代码的“严重”问题(说“ship”就意味着认可代码具备了push到主线分支的条件了)。我已经记不清多少次和代码作者因为这样的问题争论了。争论是个艺术,有时候并不一定能够达成一致,有的人比较容易被说服,有的人则更坚持己见。我不想说哪一种更好,但是确实这是代码评审中展现风格的事实——都是就事论事,但有人害怕或者不喜欢得罪人,就会显得push over一点;有人则不在乎那么多,坚信自己的想法更合适,就会显得defensive一点。我可能属于后者,似乎在职业生涯的各种阶段都会有和我出现代码评审冲突的事例,但是在某些情况下我也会选择disagree and commit(不同意但是执行团队达成的意见)。我相信有些团队会喜欢我的backbone,也会有团队讨厌我的这种风格。下面的内容,也多为基于自己风格的表述。

坚定自己的意见,但是委婉地表达

关于这一点,我也在努力地改进。可以提及的点很多,技巧也很多,但是老实说,冲突还是不可避免。在我经历的几乎所有的团队中,有时候会有老好人,但是基本上所有的老好人都缺少对于原则的坚持。沟通是门艺术,在代码评审中也一样体现。

  • 最重要的一条,只针对代码,不针对人。这条很简单,都知道对事不对人的重要性,但是要非常小心不能违背。
  • 对于大多数代码风格格式上的问题,我都会标注这个问题是一个picky或者nit的问题(“挑剔的问题”,这是我在Amazon的时候学到的方式)。这样的好处在于,明确告知对方,我虽然提出了这个问题,但是它没有什么大不了的,如果你坚持不改,我也不打算说服你。或者说,我对这个问题持有不同的看法,但是我也并不坚信我的提议更好。
  • 使用也许、或许、可能、似乎这样表示不确定的语气词(包括使用虚拟语气)。这样的好处是,缓和自己观点表达的语气。比如:“这个地方重构一下,去掉这个循环,也许会更好”。
  • 间接地表达质疑。比如说,看到对方用了一个参数3,但是你觉得不对,但又不很确定,可以这样说:“我有一个疑问,为什么这里要使用3而不是其他值?”对方可能会反应过来这个值选取得不够恰当。
  • 放上例子、讨论的链接,以及其它一些辅助材料证明自己的观点,但是不要直接表述观点,让对方来确认这个观点。比如:“下面的讨论是关于这个逻辑的另一种实现方式,不知你觉得是否会稍简洁一些?”
  • 先肯定,再否定。这个我想很多人一直都在用,先摆事实诚恳地说一些同意和正面的话,然后用however一转,说出相反的情况,这样也就在言论中比较了pros和cons,意味着这是经过trade-off得出的结论。
  • ……

一些很常见的可以在代码评审中提及的问题

这样的问题其实有不少,多数和实现的技术无关,但是又很容易不小心略过。它们多数时候是问题,当然也有时候不是。

  • 比如说,我最痛恨的之一,职责过于宽泛或者职责不清的类或模块。我无数次见过这样的类:Helper,或者Utils(注意,它们都没有模型或者模块前缀)。考虑项目的规模,大多数情况下,这样的类很容易变成一个越吹越大的气球,似乎什么东西都可以往里搁,是个十足的违反单一职责原则的糟糕设计。
  • 比如说,在线程使用,容器使用,连接管理……中,缺乏上限控制的设计,在一些情况下导致资源使用过度膨胀。生产者和消费者的队列设计,一旦消费者挂掉或者跟不上,队列里越堆越多,没有拒绝机制。
  • 再比如说,缺少分包、分层,所有的东西都叠在一起,十几个,甚至几十个类文件并列在同一个文件夹下面。
  • 再再比如说,代码缺乏设计,流水账结构,面条型代码,或者简单铺陈几个过程式的方法,这种修改往往代价还不小,自然修改的落实率低,因而令提出问题的人也颇为头疼。
  • ……

避免一次评审提及过多的问题

少数情况下,手里拿到一份实在是问题多到令人发指的代码,这时候需要扼制自己想骂人的冲动。先抓问题的主干,不要去挑那些细枝末节的毛病,因为很有可能,这些代码会被改得面目全非,或者重写。写一大堆评审意见,反而容易淹没最重要的问题。

说说容易,但是这个度有时候并不好掌握。我的习惯是,在明确代码要解决的问题以后,先快速走读一遍代码,判断我是应该粗略地抓主要矛盾呢,还是应该严格地挑刺呢。我也见过一些别的方式。

不一样的评审要求

我始终觉得,代码评审的要求不应该完全一致。不要过度追求公平。对于新项目代码,以及新员工写的代码,要适当严格一些。

新项目的代码是形成后续风格和质量的模板。我们也许都听说过“破窗户原理”,在一块干干净净的代码田地里,新耕种的代码才容易保持一致,也可以避免一些“为了和现有代码风格保持一致”而导致质量妥协的情况出现。

新员工代码的高质量要求则更多地在于对他们良好习惯养成的负责。软件工程师良好职业习惯的养成,代码可以说是最重要一环,而前三个月的影响举足轻重。

还不如不做的评审

有些情况下,代码评审是非常耗时费力的工作。特别是对业务背景不熟悉,对实现技术不熟悉,或者干脆是对方提交上来一大堆修改,阅读非常费力。我不知道哪一种是最难的,但是如果因为这些原因很难做到良好的评审,我会在评审中说明,或者放弃一些评审的工作,保证评审的质量。

代码评审是建立在团队中影响的好方式。一方面是业务逻辑,一方面是代码结构,我反对在两方面都难以给出足够清晰的评审意见的时候,提一堆风格方面的次要问题。否则很容易达成负面影响。

先谈到这里,我想还有不少可以涉及的内容,而它们都难以在课堂和书本上学到。争论才有意思,实践出真知大抵如此吧。你有什么一致的看法,或者反驳,欢迎和我讨论。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

via 四火的唠叨 https://ift.tt/2Evl6P2

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 接触Python后的一点感受记录

python最近因为工作的关系开始学习Python了。以前从不曾正儿八经地学过,如果说工作学习经验带来改变的话,那么编程语言的学习就是个很好的例子。如果在十年前,我要学习Python的话大概会买本系统介绍的Python教程,然后一页一页慢慢看,估计能够啃完大半本,跳过一些自认为次要的特性。等到在项目中使用已经得是一两个月之后了吧。但是如今我显然不太会做一样的事情,我现在会拿着我那些熟悉的编程语言来比较,不同的特性上面,Python是怎样的,是先进还是落后,适合解决什么问题,在哪些领域可以大行其道,但在遇到哪些问题的时候事倍功半。

想起以前接触过的编程语言里,事实上有一半都不能算系统地学过,大致上只是零散地入了门,就开始在项目中使用了。自然,也不可能花很多时间琢磨透了再使用,靠的是时间和经历一点点地积累。这个世界变化太快,已经没有时间把每一步都踩扎实。这就是现实,有时候未必也不是件坏事。很多人觉得大学里对编程语言的学习不值一提,因为象牙塔和工业界完全是不同的概念。但是我倒觉得,如果只考虑同等长度的时间范畴,大学里的学习经历,才是更有影响力的那一个。工作快十年了,变化的东西太多,不变的也不少——看到一群程序员聚在一起进行语言的圣战,在几年前我可能会表达“不同的工具有不同的应用场景”这样看起来中立而不带无脑倾向的废话。不过现在我可能什么都不会说,但是饶有兴致地驻足观看这样的圣战,有时候是骂战。

首先,拿Python和以前学过的语言比较来看。我觉得和Groovy比较接近,特别是语言的动态性。我确信它的学习曲线也是比较简单的。在Linux平台上作为脚本语言很容易使用,往往不需要准备什么预装什么,这和其他脚本语言比起来,便有着不可替代的优势。单纯就语言层面上,Python和Bash比起来它的代码组织性更好,和Perl比起来则没有那么多啰嗦的语法,代码更容易理解。仅由目前所掌握的这一点点知识来看,特别喜欢其中yield关键字的设计,让一些本来需要反复在不同方法上下文中切换的面条代码变得清晰和优雅,这也是我在其它语言中没有见过的。

下面的内容是作为一个初学者的一点点记录,觉得Python中有趣的几点,以及项目中使用的一些感受。

首先,关于缩进。这大概是第一个缩进具备实际意义的编程语言了,缩进不仅仅是用于帮助理解和美观需要了。对于痛恨满天遍地括号的程序员来说,似乎是一种解脱。

Tuple。Tuple的最直接好处是不可变,它时常也被作为容器不同格式之间转换和过渡的媒介,再一个,正因为有了Tuple,让函数“看起来”具备多个返回值也就变成了可能,以前在Scala中也使用过。印象中传统语言里面没有这样原生的东西,比如Java的final关键字除了不可变以外并不具备Tuple其它的特性。

可变参数:在Java中可变参数其实就是一个数组的语法糖,二者本质上没有什么区别。所以可以传一个数组给变参方法,数组会被准确解析成变参;反过来转换也一样——在变参方法中,变参一拿到手就已经是一个数组了,Python为了变参更舒服地调用而设计了展开符号——*。**则是关键字参数,和*被解析成[]不同的是,**被解析成{},这个我在别的语言里面似乎没有见到类似的。如果不是说方法定义,而是说方法调用,那么它似乎和JavaScript ECMA 6中的…类似,可以传递若干键值对(命名参数)。

尾递归优化(Tail Recursion Elimination, TRE)。这其实可以作为语言分类上的一个重要特性,Python不支持尾递归优化,后续有机会再单写一篇来详细谈谈。

List Comprehension。我第一次接触它是在Haskell里(曾经写过一点点东西涉及到它)。它让代码的简洁程度到达一个新的级别,比如下面这样的两个例子:

[x * x for x in range(1, 100) if x % 2 == 1]
[m + n for m in ‘123' for n in 'abc']

从yield到generator。yield这个关键字不仅仅可以让函数多次返回,虽说这已经是一个颇为有趣的事情了,我在其他语言中我没有见到过。它还可以让函数变成generator——其中一种简单的定义方法是,如果函数定义中包含yield,那么它就成为了一个generator,用于不断生成结果并返回。函数是顺序执行,遇到return语句或者最后一行函数语句就返回。而变成generator的函数,在每次调用next()的时候执行,遇到yield语句返回,再次执行时从上次返回的yield语句处继续执行。看这个例子:

def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n

def m_of_three():
    iter = _odd_iter()
    while True:
        n = next(iter)
        if n%3 == 0:
            yield n

for n in m_of_three():
    if n < 100:
        print(n)
    else:
        break

例子中第一个generator _odd_iter用来返回从1开始的所有奇数,而m_of_three生成器用来过滤并返回其中3的倍数,最后一部分则是打印逻辑,打印100以内的结果。这个例子体现了generator的使用,也体现了它对无限序列的支持。

模块的灵活性和自解释能力。这也是我相当喜欢的一个特性。在Python中有这样的规约,一个下划线开头表示私有变量,两个下划线开头表示Python自身预定义的一些变量,这样的规约即保留了违背规约访问和使用这些变量的灵活性,也提供了很多预定义变量的可能。其中一个是模块的__init__.py,类似于Java的package.java,但是提供了更多的特性,用以模块的自解释,比如标准注释、依赖、编码、文档注释和立即执行的main方法等等。

而实际开发的时候,借助pip和virtualenv,可以说依赖和环境准备比多数语言都简单多了。

最后是decorator,这个其实最早我实在Groovy中见到的,现在很多语言都支持注解,但是原生来看似乎Python是使用它支持特性最丰富的,这里不展开了。

在新的团队中,我们的项目比较特别,大部分的服务端代码都是用Python写的。我可以看到Python在开发效率上和环境搭建上的优势,从开发、测试、部署到调试,Python都很易于使用,Linux和命令行亲和力高,不需要很多额外的工具。总体来说,这一点在快速开发的场景下很吸引人。另一方面,Python灵活和强调规约的特性,以及提供的元编程上丰富的支持,我以及好多次感到,在写代码的时候,可以用很简洁的代码,写出看起来有点复杂的特性。现在我接触的Python开源库还不多,随着学习的深入后续再慢慢研究和记录,但是有了pip等等通用的统一的包管理工具,这一切看起来似乎要比传统的Java和C++要简单很多。

不过,Python代码容易产生的问题不可谓不少。老实说,随着代码规模的增加,我更倾向于一个约束更强,类型系统严谨并且代码代码模板清楚统一的编程语言。Python有些“太过灵活”,无论是易读性还是分层/模块化,我都看到代码中有很多需要改善的地方。最常见的一个模式是,用Python写一堆有关联的类和方法,放在一个py文件里面,在开始的时候很不错,也避免了过度臃肿的类文件,但是很快,随着代码规模的增加,这个文件需要不断被拆分和重构,但是重构这件事情却不是那么容易推动的。程序员都知道,当我们说“未来再扩展”或者“以后再改进”的时候,这件事情多半是不会发生了——于是代码过度耦合就变成了一个问题。以往使用Java写代码的时候,项目组仿佛有约定俗成的理念,无论是分层还是类文件设计,往往在开始的时候都显得有些“过度”,多层次的包、类设计,看起来似乎有些臃肿,但是随着代码规模的增加,好处就体现出来了,代码的单一职责这一要求维护得明显更好,在做某些修改的时候,需要评估的调查范围就小,代码修改也更清楚和易于评审者理解,修改者心里也更有谱。

显然这不能说孰好孰坏的问题,但是我对Python在中大规模项目(50万行+)上的使用是有疑虑的。当然也许随着经验的积累我会有不同的看法。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

via 四火的唠叨 https://ift.tt/2pBadqn

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 写在Oracle入职一个月之时(兼招人帖)

OCI加入Oracle的OCI(Oracle Cloud Infrastructure)团队一个月了,感触颇多。事实上每一次团队的更换都是一次体验记录和整理的好机会。技术方面的东西有很多,在允许的范围内,我会在以后慢慢再谈,但是其他方面,现在我想稍微谈一谈,特别是和我的老东家Amazon比较地看。以下的文字更像一篇帖子,而不是文章。

先说工作中的生活。Amazon的总部在西雅图,整个SLU满大街走着大亚麻的人,但是OCI目前只有downtown两栋楼的几层,人数要少得多。对我来说,每天上班从van pool改成了bus,commute的时间代价略高,但由于车次很多,因此也能够接受。Downtown的环境比较复杂,比SLU复杂得多,据我观察白天治安还是不错的。午饭那堆各式各样总在变化的餐车(food truck)没有了,取而代之的各种小饭馆。没看到楼里有自动售货机,不过有免费的水果、零食、咖啡、饮料,都称不上有很多选项,但也聊胜于无。午饭后我经常走过两个block去派克(Pike)市场附近逛逛小商铺晒晒太阳。

说回工作。从各式工具,特别是基础设施上看,Amazon显然更加完备,Oracle则有时显得缺乏,有时具备但是略显过时。在Amazon,如果需要一个合适的kv store,有很多AWS上面的选择可以考虑。但是在Oracle,选项就非常少了,需要更依赖于开源的资源,或者开发团队就需要做更多的工作,甚至干脆从头做一个,于是,这方面看机会也就更多。其实,在软件行业里,这才是常态,毕竟像Amazon、Microsoft、Google这样的互联网大公司工作,才有接触到那么多现成的基础设施的机会,在绝大多数公司中,都需要自力更生一点。我无法评判哪一种一定更好,有现成的选择当然使得技术选型和研发过程显得更加顺利,但是另一方面,时间久了就会忘记了这些东西本来该有的样子,和实际是怎么实现的,就好比总是吃现成饭的人,哪一天S给他一堆食材调料,让他自己下厨,就很难适应了。

毫无疑问,在云这块领域里,Amazon绝对是业界标杆,而它和M、G并称三驾马车,其它公司都和它们有着或多或少的差距。无论从基建、招聘、硬件、设计各方面等等来看,Oracle的野心着实很大,挑战无疑也显而易见。但是无论如何,这样一家“古老”的公司,如此之狠下心去参与云计算的变革,这样的勇气让人觉得真是感慨。当然,传统关系数据库的成功之老本,无论怎么成功,总有一天要吃完,这样的变革,也可以说是早晚必行的事情,那个时间点出现,都会引发争议。和Amazon这样火爆的形势比起来,身在Oracle其中,我保持谨慎乐观,但是这样能够在云计算的浪潮中扮演更大角色的机会,实在让人很难拒绝。

团队可以简单谈一谈,但是项目上面,我能说的不多。我所在的是整座从IaaS、PaaS到SaaS的金字塔中很底层的一层,代码用的Python居多。我们团队气氛和Amazon的很像,目前在迅猛的扩张中,招聘任务很艰巨,也很令人期待。目前全部都是有经验的程序员,包括非常资深的程序员,没有刚毕业的新手程序员。背景上面情况各异,但是多数人都有或多或少的云开发经验,比如从AWS团队来的,从Azure团队来的,也有少数人有和硬件打交道的丰富经验。我本人大概是一个例外,这二者都没有,这也给我带来了一些意料之中的压力。当然,毕竟已经工作快十年了,这些事情也算不上什么大问题。

我经历的每个团队都有不同的风格,有极其充满激情的,有团队成员之间关系走得特别近的,而我如今这个团队,最大的特点,用两个字来概括,就是“成熟”,不仅是专业技能上的成熟,也包括业务领域知识上的成熟;不只是工程师沟通方面,由于成熟的背景,使得沟通显得尤其简洁,还包括研发经理的管理方式——主动的工程师+松散的管理。总体来看,身边的工程师都在努力工作,这方面要比我几年前待过的某些团队显得更加务实。没有人吹牛,很少人在打酱油,这让我看到了一点创业的氛围。

薪酬待遇方面,我无法透露太多,但是如果你优秀,我想它会是非常有竞争力的。如果你也对Oracle有兴趣,想在cloud这个领域体验一把创造者的乐趣,真正做一个弄潮儿(也许已经不算“潮”了,但还是很有趣),而不只是一个云服务的使用者,欢迎和我联系。另外,如果你对大牌的公司的传统团队失去了兴趣,又不想冒太大的风险去一家小公司,那么OCI这样的大公司的全新团队也许会适合你。页面的右上角有我的邮箱链接,以及微信链接。工作地点主要是西雅图。当然,如果你感兴趣的是Amazon,我也可以帮你联系Amazon的朋友来推荐,但是这方面我会很谨慎,毕竟我已经离开了,找朋友推荐是要背负更多责任的。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

via 四火的唠叨 http://ift.tt/2IAPLxN

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 开发环境上的代码同步

最近在搭建开发环境,大致的布局是这样的:一个专门的数据库VM,一个用于编译和代码执行的VM(dev virt,装的RedHat),还有用来写代码和运行这两个虚拟环境的Mac(local)。这里我需要一个工具,可以满这样的需求:

  • 能够把Mac上写的代码同步到dev virt上去。
  • 不需要手动触发,每当有修改,应该能够自动同步。

我把我的解决办法简单记录在这里。在接下去记录之前,需要回答这样两个问题:

  • 为什么需要把编译和执行环境放到VM里面去?因为尽量使得代码的编译执行环境接近于生产线。
  • 为什么要在Mac上写代码,而不在dev virt那个VM上写代码?因为在Mac上使用第三方的工具,做一些操作系统上面的改变,编码环境的改变都比较方便,而且虚拟机中写代码有时候明显感到IDE不流畅。

下面一步一步来解决这个问题。

第一步,配置VM在NAT下的端口映射,允许从Mac上可以SSH(默认是22号端口)到dev virt上:

开发环境上的代码同步

为什么上面选择了2222号端口,主要是考虑避免和常规的SSH冲突。这样配置以后,连接localhost的2222端口,就可以映射到VM上的22号端口去了。

第二步,创建SSH keys。Mac上运行ssh-keygen,创建公钥和私钥。把公钥从~/.ssh/id_rsa.pub拷贝到dev virt,放在~/.ssh下面,并重命名成authorized_keys。注意.ssh权限必须是700,而authorized_keys必须是600。

第三步,配置dev virt上面的/etc/ssh/sshd_config,具体参数根据情况调整,完成以后需要重启SSH服务:service sshd restart。

第四步,尝试连接,在Mac上执行SSH命令,比如ssh ray@127.0.0.1 -p 2222,如果不能访问,考虑修改/etc/ssh/sshd_config,把日志改成verbose:LogLevel VERBOSE,再重启SSH服务,这样就可以通过tail -f /var/log/secure查看无法连接的错误信息。

第五步,创建一个同步脚本,比如叫做rsync.sh,里面就只有一行rsync的命令,比如:rsync -avz -e “ssh -p 2222″ ~/Projects ray@127.0.0.1:~,其中的~/Projects是Mac上的代码环境,要同步到dev virt的~上去。

第六步,安装fswatch,它可以监视文件夹下面的变动。brew install fswatch。

第六步,把fswatch和rsync串起来,比如:fswatch -v -0 ~/Projects/ | xargs -0 -n1 ~/rsync.sh,第一次执行比较慢,花了几分钟。但之后有修改的时候,因为是增量同步,几秒钟就自动同步过去了。rsync因为支持压缩,所以性能还不错。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2Cmugfy

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 再见,亚马逊时光

再见,亚马逊时光新入职Oracle已经超过一周了,但是一直没敢下笔,写一点东西纪念将近6年的亚马逊时光,总有惶恐的感觉。现在觉得不能再拖了,文字不在多寡,仿佛一种仪式,把整个亚马逊的经历画上句号。离开老东家的时候,往往是喜忧参半的,并且难免对前任颇有微词。在我离开华为的时候,便是如此,多为感怀和想念,但是诚实地说,也有一些厌烦的情绪,于是有释放之后的舒坦。这其中的缘由,我在以前的文中写到过。但是离开亚马逊,我却仿佛不再有这些负面的情绪,除了感伤和怀念,便是感激。要说明的是,如今亚马逊的股票直往上蹿,它却远非完美,也有诸多令人遗憾的风言风语。我觉得它在某些方面可以被称为“美国的华为”,做企业的成就自不必说,但是总有许多声音在抱怨对员工施仁不够。我相信这些声音大部分都是真实的,都是客观的,但是公司太大,团队独立性太强,就我的经历而言,并没有体味到这些问题。

时光回到六年前,在我对互联网的概念还迷迷糊糊的时候,在云计算之类概念才兴起不久的时候,我仍然享受着和同事开心的工作氛围,但实在决定受够了在华为的做事风格,于是下决心离开,也想离开传统电信行业,到别的行业去过过瘾,探探险。决定做得有点唐突和冒失,而且早早告诉了我的团队经理,看起来是一个一时冲动的想法而已,不过迷迷糊糊就把那些陆陆续续的挽留给拒绝了。现在我依然觉得,其实当时根本没有把问题想清楚,有时候做起决定来真是没头没脑得吓人。几个月时间里,借着周末和请假的空隙,从南京,到上海、杭州,再到北京,面试了好几家企业,我把这些和不同的公司接触的经历深深地印在脑海里,在权衡几份机会的时候,陈皓凭借他描述的做事的氛围和方式,或者说奇特的工程师文化打动了我,我决定从南京远上北京,加入他的团队,加入亚马逊。老实说,在当时我对亚马逊知之甚少,可能不比“卖书的”这三个字多多少,并不能算非常理智的决定,但是回过头来看,无疑是幸运和正确的选择,为此我也很感谢他和我的这些对话。2012年的2月份,正式加入亚马逊,GFBA项目组,开始和全球开店和商品配送打交道。

从一家民营电信巨头,跑到互联网外企,实在是一个巨大的改变,其中的“鸿沟”,对当时的我来说,确实有点艰难。我记得第一个月的时候,我和老板说,我觉得大家每一个人都比我强。不过,相较于看起来似乎更“平易近人”的技术,英文才是我最大的问题。读那些英文文档几乎是每天上班最痛苦的事情,不只是心里的痛苦,而且还胃痛,是真的胃痛,此处没有修辞手法。看到英文就胃痛,这也是蛮有趣的。我记得当时坐在边上的同事,用半问半嘲讽的语气跟我说,“你英文不适应怎么行啊”。我没有回答,觉得有些难受,似乎觉得不公平,但又没什么机会反驳。其实我自己并不确定,而且读书的时候英文就不好,也就谈不上什么信心。

接下来,你可能会以为我要灌鸡汤,写发愤图强的事情了。错了,我既没有发奋,也没有拿那什么“涂墙”。住在公司附近,交通上时间开销很小。每天下班以后,觉得时间很多,想起在华为动辄9、10点钟回家的生活,忽然觉得很幸福。有时候看看其它书,有时候就干脆打暗黑III,总之就是坚决不看在上班的时候已经苦不堪言的那堆似乎看不完的英文材料。好在老板不给我很大压力,工作时间比较自由,我们学习各种互联网技术,或者亚马逊的技术,然后在团队里分享。工作效率不能说有多高,但是可以在一个相对轻松的环境里面接触这些以前从没见到过的技术和方法,特别是有时候可以琢磨琢磨那些在外企更有经验的程序员的态度和工作方法,实在是令我收获颇丰。

在度过了漫长的适应期以后,组织上变化的关系,GFBA这个组要解散,面前有一些别的组可以选择。于是加入了Demand Forecasting,和商品销量的预测打交道。相对而言,这个组做的事情似乎会更有趣一点。接着的时间我得以有机会去接触一些机器学习的内容,也就是从那个时候开始,我逐渐觉得,学历在这一行的很多方面可能和能力并不挂钩,但是在某些领域却不是,例如机器学习的内容,人工智能的内容,数学基础好的,高校里面研究过这方面的,就是有更专业的方法。而我这样的很多东西都是半路出家自己学习的,既称不上系统,又难说深入,在这些方面的差距很难弥补。随着年岁的增长,不再心比天高,越来越能够正视自己的不足和局限,也越来越能够理解自己在哪些方面更容易遇到天花板,自然也更清楚自己什么部分更有优势。

我觉得当时我们团队在Forecasting这个新领域发展得非常不错。在2013年下半年的时候,在promote之后,我开始不安和躁动起来,开始酝酿野心,想尝试一些别的体验。我曾经说过,我生活过的每一个地方都像是一个奇妙的盒子,我会在未来“寻找其它颜色和风格的盒子”。而下一个盒子,就可能是硅谷,或者西雅图,来到更远处的一个“软件之乡”。在我开始尝试寻找和接洽在美国的团队的时候,正好,有一个机会可以来到西雅图,而且保持这个组不变。我就和我老婆商量,一切都是未知数,心里也发毛,这似乎是一个看起来挺不错的机会,不换组的话工作上的变动可以尽量小一点,压力就会小一点,我们应该抓住。于是我们两人就开始准备,专门正儿八经地学习英文,这似乎是在读书之后都没有的经历了。

2014年5月的时候,我们搬到了西雅图。接下去的时间,最初的三个月内,遇到的困难实在不少,我老婆在生活上给了很大的帮助,于是过渡这个既新鲜又痛苦的过程变得相对顺利。无论如何,能够在世界上最大的两个软件国度拥有居住和工作的体验,作为工程师来说,真是宝贵的经历。

在L签证的前提下,没有跳槽的可能,可是由于组内人事变动,躁动的心又开始作祟,想去一个更加“国际化”的环境工作,也想把自己在数据处理方面的短板补一补,于是考虑换组。和一些经理谈过之后,面了5个觉得感兴趣的组,2015年11月,加入了Contribution Profit这个组,计算成本和利润。从做的事情上看,算是真真正正天天都得和名副其实的“大数据”打交道了。很高兴学到不少有趣的东西,Scala,Spark,distributed workflow等等。

2016年算是因为各种原因,老实了一年,当然,拿到了H签证,这意味着跳槽成为了可能。

2017年下半年,面了一堆公司,最终决定加入Oracle,而整个冗长的手续,一直拖到2018年初才办好。一周前离开的时候,回想起在亚马逊的时光,恍如昨日。我在亚马逊学到了各种各样的技术,但是这些并不是我最引以为傲的。我见识到了大型互联网企业是怎样运作的,在云计算的巨头工作“是怎样一种体验”(知乎体)。工作上我认识了一群伙伴,来自世界各地,五花八门的风格,其中不少还有挺不错的私交。我学到了一个工程师应该具备怎样的严谨,怎样争论问题,怎样铺陈事实,怎样做trade-off……美好的体验太多,6年了,仿佛只是惊鸿一瞥的时间。

贴一张在本来发在朋友圈的,我写给给同事们留念的贺卡。并且非常负责任地说,所有的头像都丑爆了……

再见,亚马逊时光

还有这张用了6年的已经快要磨烂的工牌:

再见,亚马逊时光

就这样吧。谨以此文,纪念无限回味的亚马逊时光。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2BqxrWY

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 《Person of Interest》剧评

《Person of Interest》剧评

看完美剧Person of Interest(POI,疑犯追踪,下同),心有波澜,写一点点文字,零零散散,算是剧评。

我不觉得我是一个美剧狂热的爱好者,但是确实也看了好几部美剧。读书的时候开始看Friends(六人行),后来顺着相同的风格,看Two and a Half Men(好汉两个半),以及How I Met Your Mother(老爸老妈浪漫史)等等,都是很欢快的风格;另一条线看一些悬疑、枪战、罪犯之类的片子,比如最早看Prison Break(越狱),看24(反恐24小时),后来看Breaking Bad(绝命毒师),看Crime Scene Investigation(犯罪现场调查),而如今的POI也是这条路数。别的类型也有涉猎,但是类型都比较随机,比如Grey’s Anatomy(实习医生格蕾)。

我很偶尔才写影评剧评,哪怕实习医生格蕾都看完13季了,那也没有一份写一点感受的冲动。我看的多数美剧,无论能不能追到底,大致上吸引人的程度也是呈下坡趋势。但是POI不一样,结尾很华丽,气氛烘托做得非常棒——背景音乐对悲伤情绪的烘托令我我印象深刻,不只是悲伤,还有悲壮,我专门去查了那首钢琴曲,叫做Metamorphosis One(YouTube的链接)。

去掉那些纯科幻的分类,现在有很多美剧都带一点点“科幻”,POI对于人工智能的超现实拔高便是如此——特工的枪械武器还尚且属于常规,但是当今的人工智能却远远没有发展到如此强大而令人畏惧的地步。作为从事计算机工作的人来说,认为这里很多逻辑确有硬伤,比如对个体的编程能力的追捧,比如对代码片段效用的神话。但无论如何,印象中仿佛是第一次看深入涉及人工智能的美剧,而且无疑它是具有一定启迪意义的。这让我想起罗振宇打过这样比个比方,人工智能就仿佛是远处高速驶来的列车,而且越开越快,越开越快。我们在讨论的时候仿佛它还很远,看不到什么东西,但是等真正瞥见列车的轮廓的时候,速度已经快到来不及做出反应了,于是瞬间就这样从眼前开过去了。

就在去年Alpha Go在围棋方面全面战胜人类的背景下,人类与人工智能关系的未来到底是怎样的?我们在剧中看到一个过度强大的人工智能,准确地说是两个,互相斗争着,而且位于一个其它事物无法比拟的层次上。Samaritan被击败了,但是谁能说未来还会有那个具备如此力量的人工智能出现呢?如果“the machine”战胜了Samaritan且幸存下来,又如何保证它能在约束下帮助人类呢?毕竟它过于强大而将没有约束。就在我思考这将如何收场的时候,剧中给了一个玉石俱焚的走向,这可能也是最好的结果(但是,结尾还有一个伏笔,我似乎是看到在列车上从卫星上重新下载了好像是“the machine”的拷贝,一个它实际未“死”的伏笔,于是未来如果哪天又想另起炉灶换班人马重新翻,拍剧情也不至于僵硬)。当人工智能具备如此的力量,正义还是邪恶似乎已经无法被分辨清楚了。该剧想传达这样一个概念,“拯救生命”是人工智能清晰的初衷,但是如果遇到遇到需要扼杀某些生命来拯救另一些生命的时候,这个概念却变得如此模糊不堪。

当人工智能变得如此强大,当我们的世界都被计算机统治,“确保它做正确的事”将变得不可能。不仅因为“正确”永远只是个相对概念,还因为它没有对手,似乎要阻止这一切发生的办法,只能是遏制它的诞生?但是又如何保证在“the machine”和Samaritan之后,不会有第三个人工智能跳出来统治这个世界?正义还是邪恶,永远是相对的,唯有制衡是永恒的,任何单个非生命体如此独大的时候,人类的未来将充满疑虑。

如果只有上述这样的思考,只能算立意加分,但对于多数人来说,它不会有多吸引人。但POI对人物情感的刻画无疑是第二点我想说的,带来深刻印象的部分。

英雄常见吗,太常见了,英雄人物大概是影剧中最烂大街的主角形象了。POI也不能免俗,但是,要把英雄塑造得有血有肉,有风格,有难论是非的挣扎,而且有致命的缺陷。几位主角出生入死,不只是救助别人,也互相支撑和救助。

宅总Harold Finch是一个不折不扣的nerd,这样的人物总是不讨人喜欢,除了The Big Bang Theory(生活大爆炸)以外,似乎也不是很常见的主角,他们更多地以剧情需要,用一些变态计算机或者其它高科技技术来解决一些不合常理的问题的时候出现,而且多为帮手和一个纯粹“干活的”角色,但只有在POI这样的角色真正成为了头号主角,让人惊呼nerd可是能够拯救世界的啊。既要挖掘问题,又要分配资源(包括其他三个角色都是他的资源,也包括外部的资源,比如警局的Lionel Fusco),还要处理他的团队中的人员关系。

John Reese或许是刚看这个剧会被吐槽最多的主角。一派装到底的风格,头可断、血可流,西装发型不能乱,连这张脸,都好像是肉毒杆菌打多了的长期面瘫,警局的人都叫他“the man in suit”,说话永远是貌似耍酷一样低沉的嗓音,连拿枪,都不举过胸口的高度。外在形象在POI秉承一种过度追求的风格,我已经记不清主角们有多少套衣服,男男女女,西装永远是笔挺的,长裙永远是亮眼的。卖腐也好,滥拽也好,无论你喜欢还是讨厌,这已经形成了POI自己的风格。

Root,或者说Grace小姐,我已经不记得她的原名是什么了,Root就是她的名,从第一季末惊艳出场开始,她逐步逐步把自己变成了the machine的化身,最后在逝去之后,声音依然活在机器里。永远保持坏笑,对Shaw无尽牵挂,对机器向往、追求和沉浸。但她总体来说还是一个非常悲情的人物,失去了一只耳朵的听力(当然这也让她在安装了助听电子设备后和机器更近了一步),再好不容易逃脱之后为了开车躲避对Harold的狙击,中弹身亡。导演还为了煽情地戏剧性地将她的声音通过机器留存下来,仿佛Root并未逝去。

大锤Sameen Shaw,一个解决问题永远只有暴力一条思路主角,也是剧片大量幽默的来源,甚至是黑色幽默。我记不清有多少次这样的镜头,主角们讨论解决问题的办法,Shaw给的办法永远是用武力搞定。她似乎是最没有情绪的角色,甚至比John更不懂得暴露情绪,但是在末尾思念Root的时候情感触动的瞬间,还是揭示了她并非如此,刻画有力而且恰如其分。

警局的两位重要角色,Joss Carter和Lionel Fusco,也个性鲜明,尤其是后者。Lionel是Shaw之外的另一个幽默的来源,而不同之处在于他的幽默大多来自于语言。说话永远都喜欢用各种隐喻、暗喻、指代,我忘记了他给片中的各种主角们取了多少乱七八糟但是总令人会心一笑的别称,比如神奇小子什么的。

当然还有其他角色,但是总体来说其他人物,特别是反面人物的塑造并没有这几位主角这样成功,这样个性鲜明。

总的来说,观看和理解这部剧还是需要费脑筋的,铺垫非常多,总的路线可能容易把握,但是来来回回的反转和呼应,还有许多充满悬疑的问题,很难厘清,也注定这不是一部单纯而轻松幽默的剧。但是优秀的人物塑造,加上和我自身的程序员工程师身份有着千丝万缕关系的故事构造,情节悬念设置,让我大呼过瘾。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2E1f223

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 折腾的快乐

折腾的快乐

先讲个故事

公司里有这么一个小小的差事,某一个月,每天都要把Excel的某一列的数据根据某种规则换算以后拷贝到另一列去。

DA(数据分析师)看了以后说,就手工完成吧。反正只有一个月,这件事情每天做3分钟,也没有多耽误时间。

TPM看了以后说,这事情每天做做很简单啊,写一张便签贴在屏幕上,每天就不会忘记了。

Dev Manager看了以后说,衡量一下这个很小的时间成本,用其它的方式来解决是不划算的,还是手工搞定吧。

……

不过地球上还有一种特殊的物种不同意。它门叫做程序员——这么重复性的劳动难道不能用脚本完成吗?

就是,这还用问?

于是写脚本,调试,测试,整合,两个钟头花掉了。没关系,这是一次性的工作。值得。

用了两天发现bug,某些数据格式没有cover到,修复bug,一个钟头花掉了。没关系,修bug是软件的一部分。

又用了两天,发现数据精度的问题,再修,又一个钟头。呃,没事,看来我需要完善一下UT。

UT一写才发现,看似简简单单的功能,原来需要考虑的case那么多,面条代码看起来很难受,维护起来又费劲,迫切地需要重构代码啊……这一重构,就是一个半天。

接着发现脚本触发的这个行为,或者说是每天用鼠标双击的那一下,其实也应该自动化,要不然忘记了怎么办?于是写cron task。

搞定以后,忽然想起来,脚本的执行不能保证成功啊,执行是可以idempotent的,应该要有一个机制确保每天都执行到。于是开始写一个简单的任务执行系统。

等等,如果一定时间内没有执行,需要告警啊,这个简单的功能怎么能够没有。于是加入告警系统。

单机状况谁也不能保证执行的成功率,如果机器挂掉了,不管是任务执行还是告警都歇菜怎么办,必须要提高可用性。必须要做集群。

好吧,集群的情况需要考虑中心节点的问题,是有带有master节点的设计(Master-Slave?Master-Master?),还是完全去中心化的设计(2PC?Paxos?)呢?

…… (此处省略一万行)

越来越荒唐啊。

一个月过去了,Excel数据拷贝的活也不用干了,折腾以后,手里多了一堆名叫“脚本”和“软件”的烂摊子。

看起来是个相当讽刺的负面例子呢。

有程序员跳出来说,看起来是花了好多倍的时间,但是只要写一次,以后再有Excel的列拷贝问题,不就直接解决了吗?

可问题是,以后会再有这样的问题吗?这似乎是一个很难发生重复的问题,即便有重复,场景可能也千差万别了吧。

所以程序员傻里吧唧地做了一堆无用功,对吗?

……

我觉得未必。

没有折腾的意愿,哪能有那么多有趣的点子,哪能有那么多便捷的软件?提高效率的东西在最开始总是从降低效率开始的,这是一个烟斗模型。

更重要的是,如此的折腾完全源自自愿,折腾是快乐的源泉!

生命不息,折腾不止。

……

好像有点牵强 +_+

在跟自己说“管他呢”之前,忽然想起自己身上发生的两个事情:

局域网备份和私有云

老早就想干这个事情了。家里好几台电脑,照片那么多,如果能够从一台机器上备份到另一台该多好啊。硬盘哪天坏掉的时候,也不会丢东西。

最开始我的做法是手动完成,low爆了对吧,我都不好意思告诉别人;

后来进步一点,写了一点点bat脚本,至少强一点了,证明我还不是废物 ✧(≖ ◡ ≖✿);

再后来更进步一点,用一些稍微方便一点的工具,比如微软的SyncToy。但是无法自动化这一点始终让我很不开心。难道为了实现它,我真要变成上面那个越折腾成本规模越大写脚本的讽刺故事的主人公吗?

好吧,应该别的有办法,研究研究……

一种方式是备份到云上。可是我不是很愿意把私有的照片放到公网上去。

另一种是搭建家庭私有云,为此花很多钱买硬件设备来解决就没意思了。

还有别的办法吗?

应该有,研究研究……

最后发现了一个软件,Plex可以很舒服地解决这个问题,手机上的客户端可以自动同步照片到家里的服务器上。

但是光备份多没意思啊,要是能更好地利用局域网的特点,在电脑上的图片和电影,能够流畅地放到电视上播放观看多好啊。

于是开始折腾下面的部分。

闲置的笔记本

我老婆的旧笔记本不用了,闲置也是浪费。我就把它装到电视柜下面,专门买了HDMI的线,再准备了无线鼠标和无线键盘,想的是可以坐在远处操作,可以看电影和YouTube视频。电影下载,播放,看起来似乎终于把笔记本变成了视频播放器。

可是三分钟热度以后就不用了。

发现用上面提到的Plex可以更有趣地解决这个问题。台式机上面下载电影,存放照片备份,Plex支持以流媒体的方式在远程的客户端观看视频或者图像。于是在FireTV这个小盒子里面下载Plex客户端,搞定原来旧笔记本的功能了。而且,不只是盒子,在手机上也可以装客户端。

不过,依旧是三分钟热度。o(╯□╰)o

实际上,还是FireTV安装的YouTube功能最实用(Google和Amazon因为它图标一类的问题争吵以后,YouTube app已经不能直接在FireTV上使用了,现在需要通过一个中间媒介app,FireFox,再来使用),或者别的视频软件。

我对自己还是有认知的。

而且,似乎平时只有吃饭的时间会坐在电视前看电视,看电影这样长时间的活动,要么电影院,要么电脑,就是没有端坐在电视机前的习惯……

于是折腾一圈之后,忽然意识到,旧笔记本又闲置下来了。

这回怎么办呢?

好吧,研究了一下,可以把它改装成ChromeBook一样的上网本,下载Chrome OS,拷贝到U盘里面,备份数据以后安装到就笔记本上……

太聪明啦!

正高兴呢,兴致勃勃地准备动手。我老婆忽然问我,听起来不错,可是装好以后你会经常去用吗?

呃…… O__O “…

老实说,不会。家里有一个iPad上网都很少用,上网的事情还是笔记本或者台式机最实用了……

不过,话说回来……

谁在乎呢?

享受折腾的快乐就好,不是么?

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2CVDwfe

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 2017年总结

2017年总结

一周前才家人送上飞机回国过年,这两个月要一个人安安静静呆着了,就从写一点东西回顾这个过去的2017开始吧。

健康

我总是把健康放在首位。就像我之前写的,健康是一个拥有它的时候不会注意到它的东西。Crohn’s Disease时不时回来找我,但是总的来说,仅仅急性地比较严重地犯了一次,其它都还可控,比2016年好;抑郁症的问题也基本得到控制,虽然有时候还会头晕,特别是天气不好的时候,这也比2016年好。除了药物以外,时间越长我越能够理解自己的身体,总的来说我已经很满意了。当然,要是没有一个比较好的状态,我也没有办法完成面试求职这些事情。

孩子出生以后,爬山的次数明显不如从前,但是还是能够断断续续进行类似的有氧运动。我并不是一个对健身房特别感冒的人,户外的锻炼往往利于身心二者,而健身房往往只能改善其中的一个方面。我需要更花心思的筹划在远足和爬山这样的事情上面,生活就像跷跷板,我想赴美以后,某些多彩热闹的生活失去了,但是也得到了很多过往不能享受的福利,比如丰富的远足选项,还有各种美好的自然风光。

孩子

记得年初的时候说,2016年是内容丰富的一年,比如我家孩子出生了等等。但是孩子出生以后,生活就显得拥挤很多,忙碌很多。

今年脑海中的有几件重大事情,仿佛最显眼的一件就是,和孩子一起玩的体验。可能说“玩”并不太适合,他太小,似乎主要的交互,除了他喷口水很做鬼脸,在身边爬来爬去,抱着的时候哼哼唧唧或者嘻嘻哈哈以外,也没有什么了。好的一方面是他身体健康,没生什么病,成长就比较顺利。这可能和我们的理念有关系,一位朋友孩子出生以后亲戚朋友各路人马都来看望,保姆就换了几个,结果感染了疾病。

我在孩子出生的时候就明确了对他的期望——健康、独立、快乐,现在也没有什么变化,无论是内容还是优先级顺序上。

旅行

每年我都有旅行计划,基本上是要跑两趟,一趟远途的,一趟或远途或自驾的。显然今年超额完成任务了,远途跑了拉斯维加斯(四天),还去了佛罗里达(五天),自驾俄勒冈(四天)。

每次旅行都有不同的感受。我总是说,人的寿命大致就那么长,年轻的时候有条件就多跑跑,免得老了后悔。眼界这个东西似乎没有什么便捷的开阔途径。当然,我要平衡工作、生活等等,无论大事还是琐事。我想我还是更喜欢温暖一点的地方,在未来某个时间,我很希望全家能搬到南方去。从2018年末到2019年初,争取去一趟欧洲,在当前visa stamping的问题解决之后。

求职

这显然是一件很大的事情。事实上,计划下一次换工作最好的时间是,这一次新入职以前。换工作最大的好处是,了解行情,了解市场,也了解自己。有了求职体验引领的导向,就可以更好地安排日常的工作,也知道自己努力的方向在哪里。

在这过程中,我逐渐深刻地认识到,在拿到的offer中,无论我选择谁,我都将面临很大的压力。而每一次跳槽,往往都意味着更多的责任和挑战(如果职业生涯一直是走上坡路的话),这也是无法回避的一个事实。我很想在正式入职前多做准备,但无论怎样,我当前能够持有的最好心态,也只能是小心翼翼,谨慎乐观。

技术

我对自己在2017年技术方面的进步是不够满意的。可能是其他事情分散了太多精力的缘故,我花在技术上的时间,基本上从2016年开始就不足够。

有一点认识我想提一提,关于技术领域的眼界,这也是这两年我一个比较大的体会。已经工作快要10年了,聚焦的眼光已经逐渐脱离一些特别细小和具体的技术细节,更多的专注到大的方向和领域上面。比如刚工作的时候,一个Spring配置文件我能学习和仔细琢磨三天。现在自然不可能这样了。这不能说一定好或者一定不好,但是我觉得这是一个必然的变化。

立足于数据结构和算法的基础,还有一个重要的方向我正在努力的是,我要更多的涉及cloud的工作,是建设它,而不只是使用它。云早就不是一个新概念了,但是我一直没有机会成为一个建设者。现在借着换工作的契机,我想抓住它,我不知道最终是好是坏,但是我很想去尝试一把。

其它

剩下的部分不想费太多笔墨。想在这里提及的内容,我都简单罗列。

柯南剧场版。每年不能错过的大戏,不过经历了2016年零推理的失望之后,可以预料在推理的戏份上,2017年会有一个巨大的反弹。不过推理依然没有那么足,当然,也可能是我期望太高了……无论如何,柯南剧场版就像过节一样,每年都不会错过的节日。

有一些小游戏值得回味。其中Greedy Guns通关了,很喜欢的轻量级2D横版过关游戏,不需要话很多精力,但是风格又很吸引我。我集齐了所有的武器。

足球经理2018和实况2017,这两个系列似乎是我每年不变的主题,不过年复一年新意似乎越来越少。

曼联的比赛始终让人觉得半死不活,范加尔时代是阵型铺得很开,长眠昏昏欲睡,穆里尼奥时代则是的进攻缺少章法,打强队基本就是不住挨打的基础上偶尔回踹一脚……

看了一些美剧。曾经是越狱的粉丝,当然没有错过最新的一季,但是实在是非常失望。最近迷上了Person of Interest,我看不少人说演得太做作,演得太假,不过我却看得很开心,尤其喜欢里面不少幽默的小细节。

杂七杂八写了一点(似乎我向来写不好这样的东西,看看以前写的,似乎更糟,我就释然了),权做2017年的总结,也做2018年的计划。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2A88USj

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 时间投入上的权衡

时间投入上的权衡

时间管理被很多人忽略了。被忽略的一个原因是,我们被洗脑洗得太久,读到的鸡汤文太多,觉得一个人的主观努力程度扮演了过度重要的作用。事实上,这里有两个问题,一个是如何评价目标的达成,特别是人一生这个大的范围内的评价,鸡汤文中总把一个人在事业上的“成功”列为最大的目标,但实际我觉得这只对一部分人成立;另一个是,即便这个目标成立,主观努力依然被高估了——或者说,主观努力当然重要,而且对于大多数人来说,天赋并无法起到决定性作用,但是,许多人的主观能动力是类似的,结果却大相径庭。这里面,除了主观努力和先天天赋以外,明显还有别的因素在起作用,而时间管理就是其中之一。

几年前写过一点关于时间的文字,不过都是关于工作的,如今随着工作的年头越来越久,大到价值观小到每天的各种小目标都在不断变化。在几年前似乎我的生活中除了工作学习就是玩,剩下的大致都被自己归为“杂事”。现在显然不再如此了,更多的内容和不断的权衡被放了进来。

1. 陪孩子玩还是自己专注做事。这当然是一个权衡,很明显有两个极端,一种人过度地忙于自己的事情,把家庭和孩子晾在一边,如果是冠冕堂皇地称之为“事业”甚至还能得到畸形舆论的吹捧;另一种人则是为了孩子操心费力,牺牲了无数自己的生活工作。我的看法是,这两种模式都不健康。不可否认一个家庭中会有人更花时间在孩子身上,但是凡事便有利弊,倒向任何一头的不平衡都会导致另一头的损失。孩子的养育责任固然重要,生活终究是自己的。

2. 工作的张弛有度。在刚工作的时候我也会羡慕那些绩效特别好的员工,后来慢慢发现其实他们中的大部分似乎都被洗脑过了。我在以前的文章中也说过,“为自己工作。不是为父母,不是为同事,不是为公司,不是为项目,不是为绩效”,看起来很简单的道理,为了理解这一点我花了好久的时间。我记得在华为的时候,加班最疯狂的时间,有一位同事总是能够顶着压力在别人忙碌的时候自己到点下班。显然他的绩效不可能好,但是他得到了更平衡的生活。如今的我已经可以逐渐地坦然面对工作上的压力,我会自己安排休假,我也可以对那些为了公司或者项目而奋斗的话一笑置之,同时,我已经成为了”work hard, play hard”的支持者,也再不会尝试让所有人都满意。

3. 工作的张弛有度也包括在工作时间合理地规划专注的任务。我觉得我还是当个工程师,和manager比起来,工程师需要专注的事情要少得多。专注度的保持举足轻重,注意力总被打散是不利于手头的工作顺利完成的。就像操作系统的上下文切换会消耗CPU一样,如果能够连贯地做一件事,既省精力,又有效率。以前我们谈到在家办公总是提及需要自己在家处理其他事情的缘由,但是现在我也常常因为需要专注工作、避免打扰而在家办公。有很多问题的思考需要安静地不被打扰地进行,有时候中午吃饭去散个步晒个太阳的时间,就足以把问题想清楚,但是窝在办公室里却不能。

4. 关于事业和工作的权衡。事业和工作还要权衡,这不是一条路上的么?我好几年前也是那么认为的。但是后来发现,这二者常常差别大得很。举个最简单的例子,过度忙于工作会让自己只知低头干活,忘记抬头看路,辛苦干了一年却发现自己没有太多可以说出来、总结下来的东西。我给自己的安排是,如同健康饮食一样,每天的工作七成满,剩下的时间需要好好总结学到了什么,有什么经验教训,思考有哪些可以改进的,这些更多的是为了自己的未来,而非项目和团队自身,然后余下的时间可以做一些额外学习充电的事情。这些事情要至少和工作一样重要,通常要更加重要,因为它们会对职业生涯真正产生很大助益,而专注在每天改掉多少bug却不能。当然我也遇到过要求我百分百投入到工作上的非常push的经理,他们和我的观念显然是激烈冲突的,不过好在这样的情况很少见。

(这篇文章好些个月前就开了头,一直想写而没有落实,今天终于可以把它完成)

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2hLknA8

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 Blog安全问题小记

Blog安全问题小记

最近Blog遭遇了几个安全问题,折腾了几个钟头,在此记录一下。

最大的问题是blog访问时不时地出现“502 bad gateway”,即便不出现,latency也能达到接近三十秒。

于是登上vps去看原因,top命令发现CPU都用完了。靠,十个php-fpm居然都在满功率工作。研究了一下,通常php-fpm在没有请求的时候是不应该占用那么多CPU资源的,而且mysql也高,似乎有人在访问网站,但是去access log里面却没找到东西:

top - 02:08:12 up 56 min,  1 user,  load average: 10.18, 9.41, 8.68
Tasks: 115 total,  11 running, 104 sleeping,   0 stopped,   0 zombie
Cpu(s): 36.6%us, 10.4%sy,  0.0%ni,  0.0%id,  0.0%wa,  0.0%hi,  0.1%si, 53.0%st
Mem:    766112k total,   682116k used,    83996k free,   239696k buffers
Swap:  1572860k total,     2664k used,  1570196k free,   125412k cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
23854 www       20   0 59952  30m 4688 R 44.5  4.1   3:56.99 php-fpm
24337 www       20   0 60204  32m 4520 R 44.2  4.3   3:53.83 php-fpm
24300 www       20   0 52004  23m 4448 R 42.9  3.2   3:48.47 php-fpm
24287 www       20   0 54324  27m 5140 R 37.6  3.7   3:54.34 php-fpm
23855 www       20   0 54824  26m 4504 R 35.6  3.5   3:57.25 php-fpm
24323 www       20   0 46108  19m 4856 R 35.6  2.6   3:57.73 php-fpm
24274 www       20   0 56356  28m 4548 R 35.2  3.9   3:56.55 php-fpm
24374 www       20   0 55080  26m 4524 R 33.9  3.5   3:52.03 php-fpm
24385 www       20   0 63820  33m 4428 R 33.2  4.5   3:51.53 php-fpm
24394 www       20   0 57900  29m 4444 R 30.6  3.9   3:50.09 php-fpm
24250 mysql     20   0  214m  29m 5860 S 23.9  3.9   1:35.21 mysqld
    6 root      RT   0     0    0    0 S  1.7  0.0   0:01.31 watchdog/0
  216 root      20   0     0    0    0 S  1.0  0.0   0:02.96 kjournald
23850 www       20   0 18624  11m  868 S  0.3  1.6   0:01.89 nginx
23851 www       20   0 18812  12m  876 S  0.3  1.6   0:03.61 nginx
27889 root      20   0  2712 1136  880 R  0.3  0.1   0:00.81 top

在没有太多线索的时候,有位朋友说PHP有一个slow log可以查看。不过在准备为之动手之前,我忽然想到,如果怀疑是外部请求引起的,至少可以先关掉Nginx,来确认这一点——如果是外部请求引起的,关掉Nginx以后CPU应该能够回落。果然,关闭Nginx以后CPU马上回落。

于是修改Nginx来查看日志,日志级别从Critical改成Info:

error_log  /home/wwwlogs/nginx_error.log  info;

于是发现许许多多这样的日志:

2017/11/20 09:48:09 [info] 14444#0: *27 epoll_wait() reported that client prematurely closed connection, so upstream connection is closed too while sending request to upstream, client: $actual_ip_address, server: www.raychase.net, request: "POST /xmlrpc.php HTTP/1.0", upstream: "fastcgi://unix:/tmp/php-cgi.sock:", host: "raychase.net"

这就清楚许多,似乎这是XML-RPC Attack。这里有介绍:链接

基本上xmlrpc.php是WordPress里面暴露的一个远程调用服务,一些写日志的工具就是基于这个建立起来的(比如介绍过的这个),通过不断调用这个API可以耗尽系统资源,让网站停止正常服务,是一种普通的DDos攻击方式。

我检查了一下源IP地址,各个地址都有,可见来自于请求来自于肉鸡,或者是某个攻击的集群。我看到这里不觉笑了一下,我的blog就写写技术小文章,发发温和的观点,影响力那么小,居然都有人想要黑我?是不是搞错了……

无论如何,原因清楚就好了。通常解决方法是,在Nginx配置文件的server部分配置:

location = /xmlrpc.php {
	allow $xxx;
	deny all;
	access_log off;
}

其中这个allow部分是配置允许的rpc call的地址,其他都拒绝掉。第一次配置没有生效,原来是后文还有关于location的配置,把这个配置给覆盖掉了,处理好这个问题就好。当然,为了省事,也可以把xmlrpc.php改名,改成一个预料不到的名字。

其它的问题:

1. 发现有人尝试登陆主机,在/var/log/secure里面可以找得到很多尝试的记录。一般情况下把个别几个可疑的IP过滤掉就好:

iptables -I INPUT -s $actual_ip_address -p tcp --dport ssh -j REJECT

2. 发现有人尝试从web后台登陆管理员账号,默认的path是wp-login.php,之前使用过验证码,但是最终我还是把这个path改掉了,避免居心叵测的人反复尝试。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2B5tft0

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 LeetCode付费题目(一)

LeetCode 300题以内需要付费才能查看的所有题目解答。

156
157
158
159
161
163
170
186
243
244
245
246
247
248
249
250
251
252
253
254
255
256
259
261
265
266
267
269
270
271
272
276
277
280
281
285
286
288
291
293
294
296
298

Binary Tree Upside Down

【题目】Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example: Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1

【解答】把题目中的树拆成好多个小三角形来分别看,比如2-4-5这个三角形,调整的三部曲:

  1. 把2->4的路径反向,
  2. 2->5的路径切断,
  3. 然后建立4->5的路径。

把这个过程看清楚以后,题目就不难了,代码写法上整体看很像中序遍历。

class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode head = null;
        TreeNode cur = root;

        // reach to the most left node
        while (cur!=null && cur.left!=null) {
            stack.push(cur);
            cur = cur.left;
        }

        while (cur!=null && !stack.isEmpty()) {
            TreeNode parent = stack.pop();
            TreeNode right = parent.right;

            if (head==null) {
                head = cur;
            }

            cur.left = right;
            cur.right = parent;

            if (right!=null) {
                right.left = null;
                right.right = null;
            }

            cur = parent;
        }

        if (cur!=null) {
            cur.left = null;
            cur.right = null;
        }

        if (head==null)
            head = cur;

        return head;
    }
}

Read N Characters Given Read4

【题目】The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function will only be called once for each test case.

【解答】用一个循环来往buf里面写数据,注意三种case:

  1. n先达到
  2. buf.length先达到
  3. read4单次读到的数据小于4个字符

这三种情况都表示需要结束本次读取过程。

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        char[] b = new char[4];
        int pos = 0;
        while (true) {
            int rest = n-pos;
            if (rest==0) // case 1
                return pos;

            int s = read4(b);
            if (s==0) // case 2
                return pos;

            int copySize = s;
            if (pos+s>n)
                copySize = n - pos;

            System.arraycopy(b, 0, buf, pos, copySize);
            pos = pos+copySize;

            if (copySize<4) // case 3
                break;
        }

        return pos;
    }
}

Read N Characters Given Read4 II – Call multiple times

【题目】The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function may be called multiple times.

【解答】这道题的关键在于怎么样给条件归类从而简化逻辑。看起来似乎不复杂,但是有很多需要考虑的要素:

  1. read方法的buf长度决定了该方法读取数据的量不可能超过它;
  2. read方法的参数n也决定了该方法读取数据的量不可能超过它;
  3. read4方法可能读不到足够的数据,这种情况下读取数据的量不可能超过它;
  4. 需要考虑前一次读取完毕之后,可能会有剩余,那么在这次读取的时候,需要优先消费这个剩余量。

上面这几点里面,#1和#2可以合并成一个复合条件;对于#3,在读取不到足够数据的时候,跳出读取循环;而对于#4,考虑引入一个queue,任何情况下数据都从这个queue中取,而如果这个queue为空,就考虑调用read4方法来补充数据,之后再从这个queue中取数据——这样逻辑就得到简化了。

public class Solution extends Reader4 {
    private Queue<Character> queue = new LinkedList<>();
    private char[] buffer = new char[4];

    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        int pos = 0;
        while (n>0 && pos<buf.length) {
            if (!queue.isEmpty()) {
                buf[pos++] = queue.poll();
                n--;
                continue;
            }

            int count = read4(buffer);
            if (count==0) break;
            for (int i=0; i<count; i++) {
                queue.add(buffer[i]);
            }
        }

        return pos;
    }
}

Longest Substring with At Most Two Distinct Characters

【题目】Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is “ece” which its length is 3.

【解答】最多两个distinct字符的最长子串。这道是经典的双指针问题,一快一慢,快指针来探路,用一个map来记录当前的所有字符,只要map的大小小于等于2就走快指针;慢指针用来处理当map大小大于2的情况下,不断右移动并吐出字符,直到map大小恢复到2。

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s==null || s.length()==0)
            return 0;

        Map<Character, Integer> map = new HashMap<>();
        int slow = 0, fast = 0;
        int longest = 0;
        while(fast<s.length()) {
            char cf = s.charAt(fast);
            if (!map.containsKey(cf))
                map.put(cf, 0);
            map.put(cf, map.get(cf)+1);

            while (map.size()>2) {
                char cs = s.charAt(slow);
                map.put(cs, map.get(cs)-1);
                if (map.get(cs)==0)
                    map.remove(cs);
                slow++;
            }

            longest = Math.max(longest, fast-slow+1);
            fast++;
        }

        return longest;
    }
}

 

class TwoSum {
    private List<Integer> nums = new ArrayList<>();
    
    /** Initialize your data structure here. */
    public TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (nums.isEmpty()) {
            nums.add(number);
            return;
        }
        
        int l=0, r=nums.size()-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (nums.get(mid)==number) {
                nums.add(mid, number);
                return;
            } else if (nums.get(mid)<number) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        
        if (l<nums.size())
            nums.add(l, number);
        else
            nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        int l=0, r=nums.size()-1;
        while (l<r) {
            int sum = nums.get(l) + nums.get(r);
            if (sum==value)
                return true;
            else if (sum<value)
                l++;
            else
                r--;
        }
        
        return false;
    }
}

One Edit Distance

【题目】Given two strings S and T, determine if they are both one edit distance apart.

【解答】抓住题目的关键,有且只有一个edit distance,所以,总共就两种可能,一种是S和T相同的长度,那么与其内部只有一个字符不同;另一个是S和T长度差别只有1,为了便于简化代码逻辑,当T长度小于S的时候交换S和T的位置再计算。

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s==null || t==null)
            return false;
        
        if (t.length()>s.length())
            return isOneEditDistance(t, s);
        
        if (s.length()-t.length()>1)
            return false;
        
        int p=0, q=0;
        boolean mismatch = false;
        while(p<s.length()) {
            if (q==t.length())
                return !mismatch;
            
            char cp = s.charAt(p);
            char cq = t.charAt(q);
            
            if (cp!=cq) {
                if (mismatch)
                    return false;
                
                mismatch = true;
                
                if (s.length()>t.length()) {
                    p++;
                    continue;
                }
            }
            
            p++;
            q++;
        }
        
        return mismatch;
    }
}

Missing Ranges

【题目】Given a sorted integer array where the range of elements are in the inclusive range [lowerupper], return its missing ranges.

For example, given [0, 1, 3, 50, 75]lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

【解答】处理好首尾的情况,因为首尾的点可能在给定的数组范围内,也可能在范围外。

class Solution {
    public List<String> findMissingRanges(int[] nums, int lo, int up) {
        long lower = (long) lo;
        long upper = (long) up;
        
        if (upper<lower || nums==null)
            throw new IllegalArgumentException();
        
        List<String> result = new ArrayList<>();
        if (nums.length==0) {
            String empty = gen(lower-1, upper+1);
            result.add(empty);
            return result;
        }
        
        for (int i=0; i<nums.length; i++) {
            long num = (long) nums[i];
            
            if (i==0) {
                String first = gen(lower-1, Math.min(num, upper+1));
                if (first != null)
                    result.add(first);
            } else {
                String item = gen(Math.max(lower-1, (long)nums[i-1]), Math.min(num, upper+1));
                if (item != null)
                    result.add(item);
            }
            
            if (i==nums.length-1) {
                String last = gen(Math.max(lower-1, num), upper+1);
                if (last != null)
                    result.add(last);
            }
        }
        
        return result;
    }
    
    private String gen(long l, long r) {
        if (l>=r-1)
            return null;
        
        if (l==r-2) {
            return "" + (r-1);
        } else {
            return (l+1) + "->" + (r-1);
        }
    }
}

Two Sum III – Data structure design

【题目】Design and implement a TwoSum class. It should support the following operations: add and find.

add – Add the number to an internal data structure.
find – Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

【解答】数据结构的设计,这里有一个权衡,而具体需求题目并未说清楚。

  • 要么牺牲add方法,即让find方法获得O(1)的时间复杂度,但是add方法时间复杂度会相对较高;
  • 要么牺牲find方法,即让add方法获得O(1)的时间复杂度,但是find方法时间复杂度会相对较高。

我把这两种方法都放在下面,但是只有后一种方法能够跑通性能测试用例。

方法一,find方法时间复杂度为O(1):

class TwoSum2 {
    private Set<Integer> nums = new HashSet<>();
    private Set<Integer> results = new HashSet<>();
    
    /** Initialize your data structure here. */
    public TwoSum2() {
        
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        for (int num : nums) {
            results.add(number + num);
        }
        
        nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        return results.contains(value);
    }
}

方法二,add方法时间复杂度为O(1):

class TwoSum {
    private List<Integer> nums = new ArrayList<>();
    
    /** Initialize your data structure here. */
    public TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (nums.isEmpty()) {
            nums.add(number);
            return;
        }
        
        int l=0, r=nums.size()-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (nums.get(mid)==number) {
                nums.add(mid, number);
                return;
            } else if (nums.get(mid)<number) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        
        if (l<nums.size())
            nums.add(l, number);
        else
            nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        int l=0, r=nums.size()-1;
        while (l<r) {
            int sum = nums.get(l) + nums.get(r);
            if (sum==value)
                return true;
            else if (sum<value)
                l++;
            else
                r--;
        }
        
        return false;
    }
}

Reverse Words in a String II

【题目】Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Could you do it in-place without allocating extra space?

【解答】这个题目很常规,先尝试字符串整体反转,然后再给每个单词单独反转:

class Solution {
    public void reverseWords(char[] str) {
        if (str==null || str.length==0)
            return;
        
        int p=0, q=str.length-1;
        reverse(str, p, q);
        
        p=0; q=0;
        while(q<=str.length) {
            if (q==str.length-1 || str[q+1]==' ') {
                reverse(str, p, q);
                q = q+2;
                p = q;
                continue;
            }
            
            q++;
        }
    }
    
    private void reverse(char[] str, int p, int q) {
        while(p<q) {
            swap(str, p, q);
            p++;
            q--;
        }
    }
    
    private void swap(char[] str, int p, int q) {
        char temp = str[p];
        str[p] = str[q];
        str[q] = temp;
    }
}

Shortest Word Distance

【题目】Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”word2 = “practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

【解答】找两个单词的最近距离,用一个map存储单词的位置,key为单词本身,value可以用TreeSet,也可以用Heap来存放位置集合,这样value的元素是有序的,比较容易找最近距离:

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        Map<String, TreeSet<Integer>> map = new HashMap<>();
        for (int i=0; i<words.length; i++) {
            TreeSet<Integer> ts = map.getOrDefault(words[i], new TreeSet<>());
            ts.add(i);
            map.put(words[i], ts);
        }
        
        TreeSet<Integer> ts1 = map.get(word1);
        TreeSet<Integer> ts2 = map.get(word2);
        
        Iterator<Integer> it1 = ts1.iterator();
        Iterator<Integer> it2 = ts2.iterator();
        int v1 = it1.next();
        int v2 = it2.next();
        int min = Math.abs(v1-v2);
        
        while(it1.hasNext() || it2.hasNext()) {
            if (min==0)
                return 0;
            
            if (v1<v2) {
                if (!it1.hasNext()) {
                    return min;
                } else {
                    v1 = it1.next();
                    min = Math.min(min, Math.abs(v1-v2));
                }
            } else {
                if (!it2.hasNext()) {
                    return min;
                } else {
                    v2 = it2.next();
                    min = Math.min(min, Math.abs(v1-v2));
                }
            }
        }
        
        return min;
    }
}

Shortest Word Distance II

【题目】This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”word2 = “practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

【解答】解法和上面那道一样,略。

Shortest Word Distance III

【题目】This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”word2 = “coding”, return 1.
Given word1 = "makes"word2 = "makes", return 3.

Note:
You may assume word1 and word2 are both in the list.

【解答】其实解法还是可以基本一样,只需要单独处理word1和word2相同的情况而已。不过上面说了,这个map的value可以是TreeSet,也可以是堆,既然上面用了TreeSet,下面用堆来做一下吧(堆的实现在Java中是优先级队列):

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        Map<String, PriorityQueue<Integer>> map = new HashMap<>();
        for (int i=0; i<words.length; i++) {
            String word = words[i];
            PriorityQueue<Integer> pq = map.getOrDefault(word, new PriorityQueue<>());
            pq.add(i);
            map.put(word, pq);
        }
        
        PriorityQueue<Integer> pq1 = map.get(word1);
        PriorityQueue<Integer> pq2 = map.get(word2);
        
        int min = Integer.MAX_VALUE;
        if (word1.equals(word2)) {
            Integer last = null;
            for (int v : pq1) {
                if (last==null) {
                    last = v;
                } else {
                    min = Math.min(min, v-last);
                    last = v;
                }
            }
            
            return min;
        }
        
        Integer l1 = pq1.poll();
        Integer l2 = pq2.poll();
        while(!pq1.isEmpty() || !pq2.isEmpty()) {
            if (l2>l1) {
                min = Math.min(l2-l1, min);
                if (!pq1.isEmpty())
                    l1 = pq1.poll();
                else
                    return min;
            } else {
                min = Math.min(l1-l2, min);
                if (!pq2.isEmpty())
                    l2 = pq2.poll();
                else
                    return min;
            }
        }
        
        return Math.min(min, Math.abs(l2-l1));
    }
}

Strobogrammatic Number

【题目】A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers “69″, “88″, and “818″ are all strobogrammatic.

【解答】这个题目的关键在于找strobogrammatic这种数可能的组合,仔细思考以后,发现就这么几种:11,88, 00, 69,96。

class Solution {
    public boolean isStrobogrammatic(String num) {
        if (num==null || num.length()==0)
            return false;
        
        int l=0, r=num.length()-1;
        while(l<=r) {
            int lnum = num.charAt(l)-'0';
            int rnum = num.charAt(r)-'0';
            
            if (!isStrobogrammatic(lnum, rnum))
                return false;
            
            l++;
            r--;
        }
        
        return true;
    }
    
    private boolean isStrobogrammatic(int l, int r) {
        if (l==1 && r==1)
            return true;
        if (l==8 && r==8)
            return true;
        if (l==6 && r==9 || l==9 && r==6)
            return true;
        if (l==0 && r==0)
            return true;
        
        return false;
    }
}

Strobogrammatic Number II

【题目】A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return ["11","69","88","96"].

【解答】有了前面题目的积累,这个题目可以考虑构造法而不是采用搜索法。即我们已经知道n位的数怎样构造才能组成满足题目的数。通常能构造的时候,可以不要使用搜索,因为搜索的复杂度比构造高

class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<>();
        if (n<=0) return result;
        
        fs("", n, result);
        
        return result;
    }
    
    private void fs(String x, int n, List<String> result) {
        if (n==0) {
            if (x.length()!=0) {
                if (x.startsWith("0") && !x.equals("0"))
                    return;
                
                result.add(x);
            }
            
            return;
        }
        
        if (n%2==1) {
            fs("1", n-1, result);
            fs("8", n-1, result);
            fs("0", n-1, result);
        } else {
            fs("1"+x+"1", n-2, result);
            fs("8"+x+"8", n-2, result);
            fs("0"+x+"0", n-2, result);
            
            fs("6"+x+"9", n-2, result);
            fs("9"+x+"6", n-2, result);
        }
        
    }
}

Strobogrammatic Number III

【题目】A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = “50″, high = “100″, return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

【解答】和上题相比更进一步,现在要找一个范围内所有的strobogrammatic数。我们可以继续使用构造法,但是需要判断数是不是在要求的范围内。

class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int sl = low.length();
        int sh = high.length();
        
        int count = 0;
        for (int i=sl; i<=sh; i++) {
            count += sr(low, high, "", i);
        }
        
        return count;
    }
    
    private int sr(String low, String high, String str, int i) {
        int ll = low.length();
        int hl = high.length();
        
        if (i==0) {
            if (str.length()==ll && str.compareTo(low)<0)
                return 0;
            if (str.length()==hl && str.compareTo(high)>0)
                return 0;
            
            if (str.startsWith("0") && !str.equals("0"))
                return 0;
            
            return 1;
        }
        
        int count = 0;
        if (i%2==1) {
            count += sr(low, high, "0", i-1);
            count += sr(low, high, "1", i-1);
            count += sr(low, high, "8", i-1);
        } else {
            count += sr(low, high, "0"+str+"0", i-2);
            count += sr(low, high, "1"+str+"1", i-2);
            count += sr(low, high, "8"+str+"8", i-2);
            
            count += sr(low, high, "9"+str+"6", i-2);
            count += sr(low, high, "6"+str+"9", i-2);
        }
        
        return count;
    }
}

Group Shifted Strings

【题目】Given a string, we can “shift” each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep “shifting” which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
A solution is:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

【解答】关键是处理好ba这种后面的字符字母序小于前面字符的情况。用一个map来给他们归类,key为相邻两个字符间的距离。

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<List<Integer>, List<String>> map = new HashMap<>();
        for (String str : strings) {
            List<Integer> list = new ArrayList<>(str.length()-1);
            Character last = null;
            for (int i=0; i<str.length(); i++) {
                Character ch = str.charAt(i);
                if (last==null) {
                    last = ch;
                } else {
                    int diff = ch - last;
                    if (ch<last) {
                        diff = ('z'-last) + (ch-'a') + 1;
                    }
                    
                    list.add(diff);
                    last = ch;
                }
            }
            
            List<String> strs = map.getOrDefault(list, new ArrayList<>());
            strs.add(str);
            map.put(list, strs);
        }
        
        return new ArrayList<>(map.values());
    }
}

Count Univalue Subtrees

【题目】Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

 

return 4.

【解答】定义一个类Res,用来存放两个信息,一个是树是否是univalue的,一个是该树往下包含的univalue的树有多少个。这样就可以用递归来解了:

class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        if (root==null) return 0;
        
        return count(root).count;
    }
    
    private Res count(TreeNode root) {
        int count = 0;
        boolean isUS = true;
        if (root.left!=null) {
            Res left = count(root.left);
            if (!left.isUS || root.val!=root.left.val)
                isUS = false;
            
            count += left.count;
        }
        if (root.right!=null) {
            Res right = count(root.right);
            if (!right.isUS || root.val!=root.right.val)
                isUS = false;
            
            count += right.count;
        }
        
        if (isUS)
            count++;
        
        return new Res(count, isUS);
    }
}

class Res {
    int count;
    boolean isUS;
    
    public Res(int count, boolean isUS) {
        this.count = count;
        this.isUS = isUS;
    }
}

Flatten 2D Vector

【题目】Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

【解答】只有二维,那问题就不麻烦,用两个指针,一个p,一个q,分别指向第一维的位置和第二维的位置。定一个一个check方法,用来保持指针指向的位置是有意义的。

public class Vector2D implements Iterator<Integer> {
    private List<List<Integer>> lists = null;
    private Integer p = null;
    private Integer q = null;
    
    public Vector2D(List<List<Integer>> vec2d) {
        this.lists = vec2d;
    }

    @Override
    public Integer next() {
        int toReturn = lists.get(p).get(q);
        q++;
        check();
        
        return toReturn;
    }

    @Override
    public boolean hasNext() {
        if (p==null) {
            if (lists==null || lists.isEmpty())
                return false;
            p = 0;
        }
        
        if (q==null) {
            q = 0;
            check();
        }
        
        return p!=lists.size();
    }
    
    private void check() {
        while (p!=lists.size()) {
            List list = lists.get(p);
            if (list==null || q>=list.size()) {
                p++;
                q=0;
            } else {
                return;
            }
        }
        
        return;
    }
}

Meeting Rooms

【题目】Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

【解答】先根据start时间排序,然后从小到大遍历,如果发现重叠的情况,就返回false。

class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval l, Interval r) {
                return l.start - r.start;
            }
        });
        
        Integer lastEnd = null;
        for (Interval it : intervals) {
            if (lastEnd==null) {
                lastEnd = it.end;
            } else {
                if (it.start<lastEnd)
                    return false;
                
                lastEnd = it.end;
            }
        }
        
        return true;
    }
}

Meeting Rooms II

【题目】Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

【解答】把每个时间段拆成两个点,分别为开始点和结束点。然后把所有的点排序,要求时间点早的放在前,如果时间点一样,把表示结束的点放在前。接着就可以遍历并计数了:

class Iter {
    int val;
    boolean start;
    public Iter(int val, boolean start) {
        this.val = val;
        this.start = start;
    }
}
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        List<Iter> list = new ArrayList<>(intervals.length * 2);
        for (Interval inter : intervals) {
            Iter start = new Iter(inter.start, true);
            Iter end = new Iter(inter.end, false);
            list.add(start);
            list.add(end);
        }
        
        Collections.sort(list, new Comparator<Iter>() {
            @Override
            public int compare(Iter l, Iter r) {
                if (l.val==r.val) {
                    if ((l.start && r.start) || (!l.start && !r.start))
                        return 0;
                    else if (l.start)
                        return 1;
                    else
                        return -1;
                } else {
                    return l.val - r.val;
                }
            }
        });
        
        int count = 0;
        int max = 0;
        for (Iter it : list) {
            if (it.start) {
                count++;
                max = Math.max(max, count);
            } else {
                count--;
            }
        }
        
        return max;
    }
}

Factor Combinations

【题目】Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

  1. You may assume that n is always positive.
  2. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

【解答】这类找所有组合的题目,通常可以优先考虑(1)排列组合方法能不能解,(2)其它构造法能不能解,不能的话可以用回溯法,那样的话就是一个常规问题了。回溯法的时候这里用一个list来记录走到某状态的时候,之前生成的路径,可以不断维护这个状态list,这样就避免了一大堆“new ArrayList”的代码。有些题目用回溯法解的时候,我们使用一个“visited”数组,原理是类似的。

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        cal(n, new ArrayList<>(), result);
        return result;
    }
    
    private void cal(int n, List<Integer> list, List<List<Integer>> result) {
        if (n==1) {
            if (list.size()>1) {
                List<Integer> copy = new ArrayList<>(list);
                result.add(copy);
            }
            
            return;
        }
        
        int last = 2;
        if (!list.isEmpty())
            last = list.get(list.size()-1);
        for (int i=last; i<=n; i++) {
            if (n%i==0) {
                list.add(i);
                cal(n/i, list, result);
                list.remove(list.get(list.size()-1));
            }
        }
    }
}

Verify Preorder Sequence in Binary Search Tree

【题目】Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:
Could you do it using only constant space complexity?

【解答】首先我考虑用递归来解,要求常数空间复杂度,就定义一个start和end的组合来表示区间,在区间内满足如下条件的数列为合法的二叉搜索树:

  • 第一个数是根,接着往后遍历,前半段的数必须小于它(左子树),一旦发现某个数大于它了,表示后半段开始了(右子树),但是在后半段里面发现又有数小于根,就是非法了,否则为合法。
  • 对左子树和右子树继续如上检查。

代码不复杂:

class Solution2 {
    public boolean verifyPreorder(int[] preorder) {
        return verify(preorder, 0, preorder.length-1);
    }
    
    private boolean verify(int[] preorder, int start, int end) {
        if (start>=end) return true;
        
        int root = preorder[start];
        Integer firstRight = null;
        for (int i=start+1; i<=end; i++) {
            if (firstRight==null) {
                if (preorder[i]>root)
                    firstRight = i;
            } else {
                if (preorder[i]<root)
                    return false;
            }
        }
        
        if (firstRight==null)
            return verify(preorder, start+1, end);
        else
            return verify(preorder, start+1, firstRight-1) && verify(preorder, firstRight, end);
    }
}

运行出现了StackOverflowError,递归的工作栈太深,因此需要变个思路,不能这样递归了。那就写成循环吧。可以BFS,也可以DFS。我这里用BFS,判断逻辑和上面的递归比并无二致,使用一个queue来存放当前需要检查的所有子树。

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Queue<Range> queue = new LinkedList<>();
        Range r = new Range(0, preorder.length-1);
        queue.add(r);
        
        while (!queue.isEmpty()) {
            Queue<Range> nq = new LinkedList<>();
            for (Range range : queue) {
                int start = range.start;
                int end = range.end;
                
                if (start>=end) continue;
                
                int root = preorder[start];
                Integer firstRight = null;
                for (int i=start+1; i<=end; i++) {
                    if (firstRight==null) {
                        if (preorder[i]>root)
                            firstRight = i;
                    } else {
                        if (preorder[i]<root)
                            return false;
                    }
                }

                if (firstRight==null) {
                    nq.add(new Range(start+1, end));
                } else {
                    nq.add(new Range(start+1, firstRight-1));
                    nq.add(new Range(firstRight, end));
                }
            }
            
            queue = nq;
        }
        
        return true;
    }
}

class Range {
    int start;
    int end;
    
    public Range(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

Paint House

【题目】There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

【解答】思路基本上是DP,任意一个柱子 i 涂上颜色 x 的最小花费都和它前一个柱子涂上的其他两种颜色的最小花费相关。我可以建立三个滚动变量来存放当前柱子分别涂上这三种颜色的花费,也可以直接利用costs变量来存放,就连滚动变量都省了。

class Solution {
    public int minCost(int[][] costs) {
        // red blue green
        if (costs==null || (costs.length>0 && costs[0].length!=3))
            throw new IllegalArgumentException();
        
        if (costs.length==0)
            return 0;
        
        for (int i=0; i<costs.length; i++) {
            if (i==0) continue;
            
            costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2]);
            costs[i][1] += Math.min(costs[i-1][0], costs[i-1][2]);
            costs[i][2] += Math.min(costs[i-1][0], costs[i-1][1]);
        }
        
        int last = costs.length-1;
        return Math.min(Math.min(costs[last][0], costs[last][1]), costs[last][2]);
    }
}

3Sum Smaller

【题目】Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

【解答】先排序是不会错的。之后锁定nums[i]的情况下考虑采用经典的双指针方法来寻找可行解,需要注意的是,每当双指针中的left固定,right直接找到可行解的范围,可以减小单纯遍历造成的时间复杂度。

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        
        int count = 0;
        for (int i=0; i<nums.length-2; i++) {
            int l=i+1, r=nums.length-1;
            while (l<r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum>=target) {
                    r--;
                } else {
                    count += r-l; // fix the l, move r, get all possibilities
                    l++;
                }
            }
        }
        
        return count;
    }
}

Graph Valid Tree

【题目】Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0]and thus will not appear together in edges.

【解答】无向图。要成为一棵树,意味着不能形成环。因此这道题是属于图里面的常规题。两种思路:

  1. 可以用基于搜索的BFS或者DFS来解,需要引入一个visited数组,一旦在遍历的过程中发现命中了之前遍历过的节点,说明形成环了;而如果一次遍历完毕后,发现还有节点没有覆盖到,说明存在不止一棵“树”。
  2. 当然,也可以使用并查集来求解,思路是,在构造并查集的过程中,需要union X和Y,如果发现X和Y已经是union的,说明这里存在环了;而如果在遍历完毕之后,发现并查集中存在不止一个null(null在一棵树中意味着root节点),说明这图中不止一棵树。这道题题目不难,但是非常有代表性。
class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges==null || n<0)
            return false;
        
        Integer[] map = new Integer[n];
        for (int[] edge : edges) {
            int x = find(edge[0], map);
            int y = find(edge[1], map);
            
            if (x==y) {
                // the two points are already in the map so a new edge will make a cycle
                return false;
            }
            
            // union
            map[x] = y;
        }
        
        boolean flag = false;
        for (Integer point : map) {
            if (point==null) {
                if (!flag)
                    flag = true;
                else
                    return false;
            }
        }
        
        return true;
    }
    
    private int find(int num, Integer[] map) {
        if (map[num] == null)
            return num;
        else
            return find(map[num], map);
    }
}

Paint House II

【题目】There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

【解答】这道题直接拿出来的话需要好好想想,但是已经有了前面Paint House的经验,这道题的解法可以说换汤不换药。之前只有三种颜色,现在有k种颜色而已。

class Solution {
    public int minCostII(int[][] costs) {
        if (costs.length==0)
            return 0;
        
        for (int i=0; i<costs.length; i++) {
            if (i==0) continue;
            
            for (int j=0; j<costs[0].length; j++) {
                costs[i][j] += min(costs, i-1, j);
            }
        }
        
        return min(costs, costs.length-1, null);
    }
    
    private int min(int[][] costs, int i, Integer excludeJ) {
        Integer min = Integer.MAX_VALUE;
        for (int j=0; j<costs[0].length; j++) {
            if (excludeJ!=null && excludeJ.intValue()==j)
                continue;
            
            min = Math.min(min, costs[i][j]);
        }
        
        return min;
    }
}

Palindrome Permutation

【题目】Given a string, determine if a permutation of the string could form a palindrome.

For example,
"code" -> False, "aab" -> True, "carerac" -> True.

【解答】一个字符串的排列要能成为回文,这个字符串可以全部为成对的字符,或者只有一个字符不成对。因此引入一个HashSet,为每个字符调用add方法,根据结果来判断,如果set中已经存在,说明成对了,直接从这个set中删掉。遍历完毕后,看这个set的大小,超过1就返回false。

class Solution {
    public boolean canPermutePalindrome(String s) {
        Set<Character> set = new HashSet<>();
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (!set.add(ch))
                set.remove(ch);
        }
        
        return set.size()<=1;
    }
}

Palindrome Permutation II

【题目】Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

【解答】要找出所有的回文排列。首先找到每个字符可能出现的次数,存在一个数组中。然后检查这个数组,只能出现最多一次的单数,否则返回空集合,即无法形成回文。接着深度优先搜索,遍历所有可能性,这个数组正好用于遍历过程中记录状态。

class Solution {
    public List<String> generatePalindromes(String s) {
        int[] arr = new int[128];
        for (int i=0; i<s.length(); i++) {
            int idx = (int)s.charAt(i);
            arr[idx]++;
        }
        
        Integer odd = null;
        for (int i=0; i<arr.length; i++) {
            if (arr[i]%2==1) {
                if (odd!=null)
                    return new ArrayList<>();
                else
                    odd = i;
            }
        }
        
        List<String> result = new ArrayList<>();
        if (odd!=null) {
            arr[odd]--;
            travel((char)(odd.intValue()) + "", arr, result);
        } else {
            travel("", arr, result);
        }
        
        return result;
    }
    
    private void travel(String str, int[] arr, List<String> result) {
        boolean hasData = false;
        for (int i=0; i<arr.length; i++) {
            if (arr[i]==0) continue;
            
            hasData = true;
            arr[i] -= 2;
            
            travel((char)i + str + (char)i, arr, result);
            
            arr[i] += 2;
        }
        
        if (!hasData) result.add(str);
    }
}

Alien Dictionary

【题目】There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is: "zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return "".

Note:

  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.

【解答】本质上是一道图的问题。图问题的解法通常需要的并不多,下面这种基于入度(in degree)的解法很常见。

  • Step 1,建立两个数据结构,一个是表示先后顺序关系map<Character, Set<Character>>,表示key的字符必须先与任何value set的字符;另一个是indegrees<Character, Integer>,表示字符的入度,即入度为0的话表示当前没有任何字符必须先于它。
  • Step 2,每次从入度indegrees中找一个入度为0的节点作为输出的元素,然后去顺序关系map中找到它的直接后继,并将这些直接后继的入度全部减一,相当于删掉了当前节点和它的所有后继之间的路径,接着循环继续找入度为0的节点。
思路如上,不过代码写得有点啰嗦:
class Solution {
    public String alienOrder(String[] words) {
        if (words.length == 0) return "";
        if (words.length == 1) return words[0];
        
        Map<Character, Set<Character>> map = new HashMap<>();
        Map<Character, Integer> indegrees = new HashMap<>();
        
        // Step 1
        String last = null;
        for (String word : words) {
            if (last==null) {
                last = word;
                continue;
            }
            
            boolean found = false;
            for (int i=0; i<word.length() || i<last.length(); i++) {
                char cw = 0;
                if (i<word.length()) {
                    cw = word.charAt(i);
                    if (!indegrees.containsKey(cw)) {
                        indegrees.put(cw, 0);
                        map.put(cw, new HashSet<>());
                    }
                }
                
                char cl = 0;
                if (i<last.length()) {
                    cl = last.charAt(i);
                    if (!indegrees.containsKey(cl)) {
                        indegrees.put(cl, 0);
                        map.put(cl, new HashSet<>());
                    }
                }
                
                if (i>=last.length() || i>=word.length() || cw==cl)
                    continue;

                if (!found) {
                    found = true;
                    Set<Character> set = map.get(cl);
                    if (set.add(cw))
                        indegrees.put(cw, indegrees.get(cw)+1);
                }
            }
            
            last = word;
        }
        
        // Step 2
        Character c = null;
        for (Map.Entry<Character, Integer> entry : indegrees.entrySet()) {
            if (entry.getValue()==0) {
                c = entry.getKey();
                break;
            }
        }
        if (c!=null)
            indegrees.remove(c);
        
        String result = "";
        while (c!=null) {
            result = result + c;
            
            Set<Character> set = map.get(c);
            if (set!=null) {
                for (Character ch : set) {
                    indegrees.put(ch, indegrees.get(ch)-1);
                }
            }
            
            c = null;
            for (Map.Entry<Character, Integer> entry : indegrees.entrySet()) {
                if (entry.getValue()==0) {
                    c = entry.getKey();
                    break;
                }
            }
            if (c!=null)
                indegrees.remove(c);
        }
        
        if (!indegrees.isEmpty())
            return "";
        
        return result;
    }
}

Closest Binary Search Tree Value

【题目】Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

  • Given target value is a floating point.
  • You are guaranteed to have only one unique value in the BST that is closest to the target.

【解答】二叉搜索树找最接近的点。如果target大于root.val,检查root.val,与右子树递归找到的最接近的点,这二者哪个更接近;如果target小于root.val,则检查root.val,与左子树递归找到的最接近的点,这二者哪个更接近。

class Solution {
    public int closestValue(TreeNode root, double target) {
        if (target==root.val) return root.val;
        
        if (target>root.val) {
            if (root.right==null) {
                return root.val;
            } else {
                int r = closestValue(root.right, target);
                if (target-root.val > Math.abs(r-target))
                    return r;
                else
                    return root.val;
            }
        } else {
            if (root.left==null) {
                return root.val;
            } else {
                int l = closestValue(root.left, target);
                if (root.val-target > Math.abs(l-target))
                    return l;
                else
                    return root.val;
            }
        }
    }
}

Encode and Decode Strings

【题目】Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

  • The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
  • Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
  • Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

【解答】要加密和解密一个字符串数组,如果要尝试去引入一个特殊的符号来分隔这几个string,就走上一条不归路了。因为无论选用什么分隔符,这个分隔符都可能在这个string list里面出现过。我采用的办法是类似于某些协议的设计,使用第一个换行符”\n”来分隔加密后报文的头部和实体。头部存放所有string的长度列表,实体则是所有string的简单拼接。

注意两个edge cases:空list,这种情况下头部为空;list中包含空字符串””,这种情况下该字符串的长度为0,因此头部不可能为空。

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        String lengths = "";
        for (String str : strs) {
            lengths += str.length() + ",";
            sb.append(str);
        }
        
        if (lengths.length()>0)
            lengths = lengths.substring(0, lengths.length()-1);
        
        return lengths + '\n' + sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        int idx = s.indexOf('\n');
        String lens = s.substring(0, idx);
        if (idx==0) return new ArrayList<>();

        String[] ls = lens.split("\\,");

        List<String> list = new ArrayList<>(ls.length);
        int p=idx+1;
        for (String l : ls) {
            int strl = Integer.parseInt(l);
            if (strl==0) {
                list.add("");
                continue;
            }
            list.add(s.substring(p, p+strl));
            p = p + strl;
        }
        
        return list;
    }
}

Closest Binary Search Tree Value II

【题目】Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

【解答】在BST中,需要返回k个和target最接近的节点。我的做法是:

  • Step 1: 先先序遍历BST得到一个有序的double linked list,同时也记录下了最接近的节点;
  • Step 2: 然后双指针一个往前,一个往后,寻找下一个最接近的点,直到找到k个为止。
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Item c = null;
        Item min = null;
        
        // Step 1
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur!=null || !stack.isEmpty()) {
            if (cur!=null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode tn = stack.pop();
                
                if (c==null) {
                    c = new Item(tn.val);
                    min = c;
                } else {
                    c.next = new Item(tn.val);
                    c.next.prev = c;
                    
                    c = c.next;
                    if (Math.abs(c.val-target) < Math.abs(min.val-target))
                        min = c;
                }
                
                cur = tn.right;
            }
        }
        
        // Step 2
        Item l=min.prev, r=min.next;
        List<Integer> result = new ArrayList<>();
        result.add(min.val);
        while (result.size()<k) {
            double leftDiff = Double.MAX_VALUE;
            if (l!=null) {
                leftDiff = Math.abs(l.val-target);
            }
            
            double rightDiff = Double.MAX_VALUE;
            if (r!=null) {
                rightDiff = Math.abs(r.val-target);
            }
            
            if (leftDiff<rightDiff) {
                result.add(l.val);
                l = l.prev;
            } else {
                result.add(r.val);
                r = r.next;
            }
        }
        
        return result;
    }
}

class Item {
    int val;
    Item prev;
    Item next;
    
    public Item(int val) {
        this.val = val;
    }
}

虽然AC了,不过我觉得应该有更优的解法,因为我遍历了BST所有的节点,事实上,如果只要找K个,以某种方法我应该只需要遍历K个,或者接近K个节点即可。

Paint Fence

【题目】There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

【解答】首先要理解题意。题目说得不太清楚,有人在评论区里面说,一种更清晰的描述方式应该是“no 3 adjacent posts have the same color”,就是说不能连续三个post都涂上同一种颜色。现在考虑任意的连续两根柱子A和B,存在两种可能,一种是A和B同色,这种情况下的种类数设为same;另一种是A和B不同色,种类数设为diff。现在要给下一根柱子C涂色:

  • 如果C和相邻的B同色,那么很显然共有diff种涂法,因为如果A和B同色时,是不能允许C和B继续同色的;
  • 如果C和B不同色,那么有两种情况,一种是A和B同色,这种情况下要避免B和C同色,共有same*(k-1)种涂法;另一种是A和B不同色,而又要求B和C不同色,共有diff*(k-1)种涂法。
class Solution {
    public int numWays(int n, int k) {
        if (n==0 || k==0)
            return 0;
        
        if (n==1)
            return k;
        else if (n==2)
            return k*k;
        
        int same = k;
        int diff = k*(k-1);
        
        for (int i=3; i<=n; i++) {
            int newSame = diff;
            int newDiff = (same+diff) * (k-1);
            
            same = newSame;
            diff = newDiff;
        }
        
        return same + diff;
    }
}

Find the Celebrity

【题目】Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

【解答】找名人问题。n个人里面,存在至多一位名人。名人不认识其余任何一个人,而其余任何一人都认识名人。

  • 用一个变量last记录疑似名人的那个人,对于其他人i,调用knows(last, i),如果返回true,说明last不可能是名人,于是更新last为i;
  • 接着再反过来第二遍循环中调用kowns(i, last),如果返回false,说明这个last有人不认识,那么这个last就不是名人,如果所有的i都认识last,last就是名人。
public class Solution extends Relation {
    public int findCelebrity(int n) {
        if (n<=1)
            return -1;
        
        Integer last = null;
        for (int i=0; i<n; i++) {
            if (last==null) {
                last = i;
                continue;
            }
            
            boolean know = knows(last, i);
            if (know) {
                last = i;
            }
        }

        for (int i=0; i<n; i++) {
            if (last!=i) {
                boolean know = knows(i, last);
                if (!know)
                    return -1;

                know = knows(last, i);
                if (know)
                    return -1;
            }
        }
        
        return last;
    }
}
 

Wiggle Sort

【题目】Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

【解答】先排序,然后从头、尾依次取数。

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums==null || nums.length==0)
            return;
        
        int[] numsCopy = new int[nums.length];
        System.arraycopy(nums, 0, numsCopy, 0, nums.length);
        Arrays.sort(numsCopy);
        
        int left=0, right=numsCopy.length-1;
        int i=0;
        boolean flag = true;
        while(i<nums.length) {
            if (flag) {
                nums[i++] = numsCopy[left];
                left++;
                flag = !flag;
            } else {
                nums[i++] = numsCopy[right];
                right--;
                flag = !flag;
            }
        }
    }
}

Zigzag Iterator

【题目】Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question – Update (2015-09-18):
The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:

[1,2,3]
[4,5,6,7]
[8,9]

It should return [1,4,8,2,5,9,3,6,7].

【解答】用一个boolean变量记录下一个访问的节点是在v1还是v2;用一个int变量col用来记录节点下标。建立一个adjust方法用来针对一些不合法的情况调整节点的位置,比如v1或者v2已经穷尽时。保证每次方法调用以后内部总是能够准备好下一个需要返回的节点。

public class ZigzagIterator {
    private List<Integer> v1 = null;
    private List<Integer> v2 = null;
    
    private boolean row = true;
    private int col = 0;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.v1 = v1;
        this.v2 = v2;
        adjust();
    }

    private void adjust() {
        if (row) {
            if (v1.size()<=col) {
                row = false;
            }
        } else {
            if (v2.size()<=col) {
                row = true;
                col++;
            }
        }
    }
    
    public int next() {
        List<Integer> v = row ? v1 : v2;
        if (col>=v.size()) throw new RuntimeException();
        
        int res = v.get(col);
        if (row) {
            row = false;
        } else {
            row = true;
            col++;
        }
        adjust();
        
        return res;
    }

    public boolean hasNext() {
        List<Integer> v = row ? v1 : v2;
        return col<v.size();
    }
}

Inorder Successor in BST

【题目】Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

【解答】用一个boolean变量记录是否已经找到p了。剩下的和普通的二叉树的中序遍历没有区别。

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        boolean matched = false;
        while (cur!=null || !stack.isEmpty()) {
            if (cur!=null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode tn = stack.pop();
                if (matched) {
                    return tn;
                } else {
                    if (p==tn) matched = true;
                    cur = tn.right;
                }
            }
        }
        
        return null;
    }
}

Walls and Gates

【题目】You are given a m x n 2D grid initialized with these three possible values.

  1. -1 – A wall or an obstacle.
  2. 0 – A gate.
  3. INF – Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

【解答】我一开始的思路是DFS,从任何一点出发,为了防止循环探索,先标记自己为障碍(-1),然后探索上下左右四个方向,以找到里gate最近的步数。可是这样的方法有一个问题,在标记自己(比如为A)为障碍的时候,如果探索的位置正好需要通过A才可达呢?这样得出的结果是有问题的。另外一个麻烦的地方是,有些地方是不可达的,因此需要标记为INF,可是怎样区分是原始的INF还是我希望标记的INF呢?这个问题又需要额外的逻辑来处理。

于是,换个思路。一个相对简单的办法是,找所有gate(0)的位置,然后从gate开始往周围蔓延,寻找所有通过这个门可达的点,并且记录和更新最小步数。其中,在寻找的过程中,如果发现在该位置上已经出现了更小的值,这个值可能是障碍(-1),也可能是更小的步数,就直接返回,以减小计算量。代码简单很多。我觉得这道题在迷宫类问题中是有一定代表性的。

class Solution {
    public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; i++) {
            for (int j = 0; j < rooms[0].length; j++) {
                if (rooms[i][j] == 0)
                    mark(rooms, i, j, 0);
            }
        }
    }

    private void mark(int[][] rooms, int i, int j, int step) {
        if (i < 0 || j < 0 || j >= rooms[0].length || i >= rooms.length || rooms[i][j] < step)
            return;
        
        rooms[i][j] = step;
        
        mark(rooms, i - 1, j, step + 1);
        mark(rooms, i + 1, j, step + 1);
        mark(rooms, i, j - 1, step + 1);
        mark(rooms, i, j + 1, step + 1);
    }
}

Unique Word Abbreviation

【题目】An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word’s abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example: 

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

【解答】写一个方法来得到一个词语的缩略形式,然后把缩略形式作为key,放到map里面去。这样查询的时候就可以看给定的缩略形式是不是可以找到唯一的对应词语。

class ValidWordAbbr {
    private Map<String, Set<String>> map = new HashMap<>();
    public ValidWordAbbr(String[] dictionary) {
        for (String s : dictionary) {
            String key = getKey(s);
            Set<String> set = map.get(key);
            if (set == null)
                set = new HashSet<>();
            
            set.add(s);
            
            map.put(key, set);
        }
    }
    
    private String getKey(String s) {
        String key = null;
        if (s.length()<3)
            key = s;
        else
            key = "" + s.charAt(0) + (s.length()-2) + s.charAt(s.length()-1);
        
        return key;
    }
    
    public boolean isUnique(String word) {
        String key = getKey(word);
        if (!this.map.containsKey(key))
            return true;
        else {
            Set<String> set = this.map.get(key);
            if (set.size() == 1 && set.contains(word))
                return true;
        }
        
        return false;
    }
}

Word Pattern II

【题目】Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Examples:

  1. pattern = "abab", str = "redblueredblue" should return true.
  2. pattern = "aaaa", str = "asdasdasdasd" should return true.
  3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:

You may assume both pattern and str contains only lowercase letters.

【解答】判断字符串是否匹配这个pattern。我的思路是回溯法,使用两个map,一个是pattern的字符对应到str中的substring的map;另一个是反过来,substring对应到字符。

  • 如果发现某个字符在map中出现过,必须要同时检查另一个map,看这个substring是否也出现过且对应到相同的字符去,然后才递归调用余下的部分。
  • 如果发现字符没有出现过,也要类似的操作,确保选取的substring也是没有出现过的。再递归调用余下的部分,只要有一种substring选取的解返回true,这个方法就返回true。
class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        return match(pattern, 0, str, 0, new HashMap<>(), new HashMap<>());
    }
    
    private boolean match(String pattern, int p, String str, int s, Map<Character, String> map, Map<String, Character> map2) {
        if (p==pattern.length() && s==str.length()) return true;
        if (p==pattern.length() || s==str.length()) return false;
        
        char cp = pattern.charAt(p);
        if (map.containsKey(cp)) {
            String token = map.get(cp);
            if (token.length()>=str.length()-s+1)
                return false;
            
            String sub = str.substring(s, s+token.length());
            if (!sub.equals(token))
                return false;
            
            Character ch = map2.get(sub);
            if (ch.charValue()!=cp)
                return false;
            
            return match(pattern, p+1, str, s+token.length(), map, map2);
        } else {
            for (int i=1; i<=str.length()-s; i++) {
                String sub = str.substring(s, s+i);
                if (map2.containsKey(sub))
                    continue;
                
                map.put(cp, sub);
                map2.put(sub, cp);
                
                boolean res = match(pattern, p+1, str, s+i, map, map2);
                if (res) return true;
                
                map.remove(cp);
                map2.remove(sub);
            }
            
            return false;
        }
    }
}

Flip Game

【题目】You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.

For example, given s = "++++", after one move, it may become one of the following states:

[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list [].

【解答】转成char array然后替换相应的字符。

class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> result = new ArrayList<>();
        for (int i=1; i<s.length(); i++) {
            if (s.charAt(i)=='+' && s.charAt(i-1)=='+') {
                char[] chs = s.toCharArray();
                chs[i] = '-';
                chs[i-1] = '-';
                result.add(new String(chs));
            }
        }
        return result;
    }
}

Flip Game II

【题目】You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm’s runtime complexity.

【解答】本质上还是回溯法。自己当前可以选择一步走,如果走了哪一步,接下去如果对手无法赢,那么自己就赢了。

class Solution {
    public boolean canWin(String s) {
        return canWin(s.toCharArray());
    }
    
    private boolean canWin(char[] chs) {
        for (int i=1; i<chs.length; i++) {
            if (chs[i]=='+' && chs[i-1]=='+') {
                
                chs[i]='-';
                chs[i-1]='-';
                
                boolean res = canWin(chs);
                
                chs[i]='+';
                chs[i-1]='+';
                
                if (!res)
                    return true;
            }
        }
        
        return false;
    }
}

Best Meeting Point

【题目】A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0)(0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

【解答】显然,把图上的每个点取出来去计算和所有人所在的点距离之和是一个办法,但是复杂度太高了。考虑优化的办法。这里的距离用的是曼哈顿距离,因此可以看到,行和列的距离计算是完全独立的。也就是说,从行这个维度上去取点的逻辑,和从列这个维度上去取点的逻辑,是互不影响的。这一点非常重要,因为有了这一个理论基础,就可以把这个二维的问题降为一维来解决。

如果这个图只有一维,那么这些人的位置的中位数是最佳的位置(不是平均数)。有了这个发现以后,问题就变成了求中位数的过程,也就迎刃而解了。

class Solution {
    public int minTotalDistance(int[][] grid) {
        List<Integer> rows = new ArrayList<>();
        List<Integer> cols = new ArrayList<>();
        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[0].length; j++) {
                if (grid[i][j]==1) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        
        Collections.sort(rows);
        Collections.sort(cols);
        
        int i = rows.get(rows.size() / 2);
        int j = cols.get(cols.size() / 2);
        
        int total = 0;
        for (int p : rows) {
            total += Math.abs(p-i);
        }
        for (int q : cols) {
            total += Math.abs(q-j);
        }
        
        return total;
    }
}

Binary Tree Longest Consecutive Sequence

【题目】Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    /
   2
  /
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

【解答】建立一个Result对象,用来在递归遍历这棵树的时候传递子树的结果,包含两个值,一个是发现的最长递增串,一个是以该子树root为起点的最长递增串。

class Solution {
    public int longestConsecutive(TreeNode root) {
        return travel(root).longest;
    }
    
    private Result travel(TreeNode root) {
        if (root==null)
            return new Result();
        
        int longest = 1;
        int increasing = 1;
        
        Result left = travel(root.left);
        longest = Math.max(left.longest, longest);
        if (root.left!=null && root.val+1==root.left.val) {
            increasing = Math.max(left.increasing+1, increasing);
        }
        
        Result right = travel(root.right);
        longest = Math.max(right.longest, longest);
        if (root.right!=null && root.val+1==root.right.val) {
            increasing = Math.max(right.increasing+1, increasing);
        }
        
        longest = Math.max(longest, increasing);
        
        Result res = new Result();
        res.longest = longest;
        res.increasing = increasing;
        
        return res;
    }
}

class Result {
    int longest;
    int increasing;
}

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2zAkCcu

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 LeetCode付费题目(一)

LeetCode 300题以内需要付费才能查看的所有题目解答。

156
157
158
159
161
163
170
186
243
244
245
246
247
248
249
250
251
252
253
254
255
256
259
261
265
266
267
269
270
271
272
276
277
280
281
285
286
288
291
293
294
296
298

Binary Tree Upside Down

【题目】Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example: Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1

【解答】把题目中的树拆成好多个小三角形来分别看,比如2-4-5这个三角形,调整的三部曲:

  1. 把2->4的路径反向,
  2. 2->5的路径切断,
  3. 然后建立4->5的路径。

把这个过程看清楚以后,题目就不难了,代码写法上整体看很像中序遍历。

class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode head = null;
        TreeNode cur = root;

        // reach to the most left node
        while (cur!=null && cur.left!=null) {
            stack.push(cur);
            cur = cur.left;
        }

        while (cur!=null && !stack.isEmpty()) {
            TreeNode parent = stack.pop();
            TreeNode right = parent.right;

            if (head==null) {
                head = cur;
            }

            cur.left = right;
            cur.right = parent;

            if (right!=null) {
                right.left = null;
                right.right = null;
            }

            cur = parent;
        }

        if (cur!=null) {
            cur.left = null;
            cur.right = null;
        }

        if (head==null)
            head = cur;

        return head;
    }
}

Read N Characters Given Read4

【题目】The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function will only be called once for each test case.

【解答】用一个循环来往buf里面写数据,注意三种case:

  1. n先达到
  2. buf.length先达到
  3. read4单次读到的数据小于4个字符

这三种情况都表示需要结束本次读取过程。

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        char[] b = new char[4];
        int pos = 0;
        while (true) {
            int rest = n-pos;
            if (rest==0) // case 1
                return pos;

            int s = read4(b);
            if (s==0) // case 2
                return pos;

            int copySize = s;
            if (pos+s>n)
                copySize = n - pos;

            System.arraycopy(b, 0, buf, pos, copySize);
            pos = pos+copySize;

            if (copySize<4) // case 3
                break;
        }

        return pos;
    }
}

Read N Characters Given Read4 II – Call multiple times

【题目】The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function may be called multiple times.

【解答】这道题的关键在于怎么样给条件归类从而简化逻辑。看起来似乎不复杂,但是有很多需要考虑的要素:

  1. read方法的buf长度决定了该方法读取数据的量不可能超过它;
  2. read方法的参数n也决定了该方法读取数据的量不可能超过它;
  3. read4方法可能读不到足够的数据,这种情况下读取数据的量不可能超过它;
  4. 需要考虑前一次读取完毕之后,可能会有剩余,那么在这次读取的时候,需要优先消费这个剩余量。

上面这几点里面,#1和#2可以合并成一个复合条件;对于#3,在读取不到足够数据的时候,跳出读取循环;而对于#4,考虑引入一个queue,任何情况下数据都从这个queue中取,而如果这个queue为空,就考虑调用read4方法来补充数据,之后再从这个queue中取数据——这样逻辑就得到简化了。

public class Solution extends Reader4 {
    private Queue<Character> queue = new LinkedList<>();
    private char[] buffer = new char[4];

    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        int pos = 0;
        while (n>0 && pos<buf.length) {
            if (!queue.isEmpty()) {
                buf[pos++] = queue.poll();
                n--;
                continue;
            }

            int count = read4(buffer);
            if (count==0) break;
            for (int i=0; i<count; i++) {
                queue.add(buffer[i]);
            }
        }

        return pos;
    }
}

Longest Substring with At Most Two Distinct Characters

【题目】Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is “ece” which its length is 3.

【解答】最多两个distinct字符的最长子串。这道是经典的双指针问题,一快一慢,快指针来探路,用一个map来记录当前的所有字符,只要map的大小小于等于2就走快指针;慢指针用来处理当map大小大于2的情况下,不断右移动并吐出字符,直到map大小恢复到2。

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s==null || s.length()==0)
            return 0;

        Map<Character, Integer> map = new HashMap<>();
        int slow = 0, fast = 0;
        int longest = 0;
        while(fast<s.length()) {
            char cf = s.charAt(fast);
            if (!map.containsKey(cf))
                map.put(cf, 0);
            map.put(cf, map.get(cf)+1);

            while (map.size()>2) {
                char cs = s.charAt(slow);
                map.put(cs, map.get(cs)-1);
                if (map.get(cs)==0)
                    map.remove(cs);
                slow++;
            }

            longest = Math.max(longest, fast-slow+1);
            fast++;
        }

        return longest;
    }
}

 

class TwoSum {
    private List<Integer> nums = new ArrayList<>();
    
    /** Initialize your data structure here. */
    public TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (nums.isEmpty()) {
            nums.add(number);
            return;
        }
        
        int l=0, r=nums.size()-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (nums.get(mid)==number) {
                nums.add(mid, number);
                return;
            } else if (nums.get(mid)<number) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        
        if (l<nums.size())
            nums.add(l, number);
        else
            nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        int l=0, r=nums.size()-1;
        while (l<r) {
            int sum = nums.get(l) + nums.get(r);
            if (sum==value)
                return true;
            else if (sum<value)
                l++;
            else
                r--;
        }
        
        return false;
    }
}

One Edit Distance

【题目】Given two strings S and T, determine if they are both one edit distance apart.

【解答】抓住题目的关键,有且只有一个edit distance,所以,总共就两种可能,一种是S和T相同的长度,那么与其内部只有一个字符不同;另一个是S和T长度差别只有1,为了便于简化代码逻辑,当T长度小于S的时候交换S和T的位置再计算。

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s==null || t==null)
            return false;
        
        if (t.length()>s.length())
            return isOneEditDistance(t, s);
        
        if (s.length()-t.length()>1)
            return false;
        
        int p=0, q=0;
        boolean mismatch = false;
        while(p<s.length()) {
            if (q==t.length())
                return !mismatch;
            
            char cp = s.charAt(p);
            char cq = t.charAt(q);
            
            if (cp!=cq) {
                if (mismatch)
                    return false;
                
                mismatch = true;
                
                if (s.length()>t.length()) {
                    p++;
                    continue;
                }
            }
            
            p++;
            q++;
        }
        
        return mismatch;
    }
}

Missing Ranges

【题目】Given a sorted integer array where the range of elements are in the inclusive range [lowerupper], return its missing ranges.

For example, given [0, 1, 3, 50, 75]lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

【解答】处理好首尾的情况,因为首尾的点可能在给定的数组范围内,也可能在范围外。

class Solution {
    public List<String> findMissingRanges(int[] nums, int lo, int up) {
        long lower = (long) lo;
        long upper = (long) up;
        
        if (upper<lower || nums==null)
            throw new IllegalArgumentException();
        
        List<String> result = new ArrayList<>();
        if (nums.length==0) {
            String empty = gen(lower-1, upper+1);
            result.add(empty);
            return result;
        }
        
        for (int i=0; i<nums.length; i++) {
            long num = (long) nums[i];
            
            if (i==0) {
                String first = gen(lower-1, Math.min(num, upper+1));
                if (first != null)
                    result.add(first);
            } else {
                String item = gen(Math.max(lower-1, (long)nums[i-1]), Math.min(num, upper+1));
                if (item != null)
                    result.add(item);
            }
            
            if (i==nums.length-1) {
                String last = gen(Math.max(lower-1, num), upper+1);
                if (last != null)
                    result.add(last);
            }
        }
        
        return result;
    }
    
    private String gen(long l, long r) {
        if (l>=r-1)
            return null;
        
        if (l==r-2) {
            return "" + (r-1);
        } else {
            return (l+1) + "->" + (r-1);
        }
    }
}

Two Sum III – Data structure design

【题目】Design and implement a TwoSum class. It should support the following operations: add and find.

add – Add the number to an internal data structure.
find – Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

【解答】数据结构的设计,这里有一个权衡,而具体需求题目并未说清楚。

  • 要么牺牲add方法,即让find方法获得O(1)的时间复杂度,但是add方法时间复杂度会相对较高;
  • 要么牺牲find方法,即让add方法获得O(1)的时间复杂度,但是find方法时间复杂度会相对较高。

我把这两种方法都放在下面,但是只有后一种方法能够跑通性能测试用例。

方法一,find方法时间复杂度为O(1):

class TwoSum2 {
    private Set<Integer> nums = new HashSet<>();
    private Set<Integer> results = new HashSet<>();
    
    /** Initialize your data structure here. */
    public TwoSum2() {
        
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        for (int num : nums) {
            results.add(number + num);
        }
        
        nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        return results.contains(value);
    }
}

方法二,add方法时间复杂度为O(1):

class TwoSum {
    private List<Integer> nums = new ArrayList<>();
    
    /** Initialize your data structure here. */
    public TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (nums.isEmpty()) {
            nums.add(number);
            return;
        }
        
        int l=0, r=nums.size()-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (nums.get(mid)==number) {
                nums.add(mid, number);
                return;
            } else if (nums.get(mid)<number) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        
        if (l<nums.size())
            nums.add(l, number);
        else
            nums.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        int l=0, r=nums.size()-1;
        while (l<r) {
            int sum = nums.get(l) + nums.get(r);
            if (sum==value)
                return true;
            else if (sum<value)
                l++;
            else
                r--;
        }
        
        return false;
    }
}

Reverse Words in a String II

【题目】Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Could you do it in-place without allocating extra space?

【解答】这个题目很常规,先尝试字符串整体反转,然后再给每个单词单独反转:

class Solution {
    public void reverseWords(char[] str) {
        if (str==null || str.length==0)
            return;
        
        int p=0, q=str.length-1;
        reverse(str, p, q);
        
        p=0; q=0;
        while(q<=str.length) {
            if (q==str.length-1 || str[q+1]==' ') {
                reverse(str, p, q);
                q = q+2;
                p = q;
                continue;
            }
            
            q++;
        }
    }
    
    private void reverse(char[] str, int p, int q) {
        while(p<q) {
            swap(str, p, q);
            p++;
            q--;
        }
    }
    
    private void swap(char[] str, int p, int q) {
        char temp = str[p];
        str[p] = str[q];
        str[q] = temp;
    }
}

Shortest Word Distance

【题目】Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”word2 = “practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

【解答】找两个单词的最近距离,用一个map存储单词的位置,key为单词本身,value可以用TreeSet,也可以用Heap来存放位置集合,这样value的元素是有序的,比较容易找最近距离:

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        Map<String, TreeSet<Integer>> map = new HashMap<>();
        for (int i=0; i<words.length; i++) {
            TreeSet<Integer> ts = map.getOrDefault(words[i], new TreeSet<>());
            ts.add(i);
            map.put(words[i], ts);
        }
        
        TreeSet<Integer> ts1 = map.get(word1);
        TreeSet<Integer> ts2 = map.get(word2);
        
        Iterator<Integer> it1 = ts1.iterator();
        Iterator<Integer> it2 = ts2.iterator();
        int v1 = it1.next();
        int v2 = it2.next();
        int min = Math.abs(v1-v2);
        
        while(it1.hasNext() || it2.hasNext()) {
            if (min==0)
                return 0;
            
            if (v1<v2) {
                if (!it1.hasNext()) {
                    return min;
                } else {
                    v1 = it1.next();
                    min = Math.min(min, Math.abs(v1-v2));
                }
            } else {
                if (!it2.hasNext()) {
                    return min;
                } else {
                    v2 = it2.next();
                    min = Math.min(min, Math.abs(v1-v2));
                }
            }
        }
        
        return min;
    }
}

Shortest Word Distance II

【题目】This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”word2 = “practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

【解答】解法和上面那道一样,略。

Shortest Word Distance III

【题目】This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”word2 = “coding”, return 1.
Given word1 = "makes"word2 = "makes", return 3.

Note:
You may assume word1 and word2 are both in the list.

【解答】其实解法还是可以基本一样,只需要单独处理word1和word2相同的情况而已。不过上面说了,这个map的value可以是TreeSet,也可以是堆,既然上面用了TreeSet,下面用堆来做一下吧(堆的实现在Java中是优先级队列):

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        Map<String, PriorityQueue<Integer>> map = new HashMap<>();
        for (int i=0; i<words.length; i++) {
            String word = words[i];
            PriorityQueue<Integer> pq = map.getOrDefault(word, new PriorityQueue<>());
            pq.add(i);
            map.put(word, pq);
        }
        
        PriorityQueue<Integer> pq1 = map.get(word1);
        PriorityQueue<Integer> pq2 = map.get(word2);
        
        int min = Integer.MAX_VALUE;
        if (word1.equals(word2)) {
            Integer last = null;
            for (int v : pq1) {
                if (last==null) {
                    last = v;
                } else {
                    min = Math.min(min, v-last);
                    last = v;
                }
            }
            
            return min;
        }
        
        Integer l1 = pq1.poll();
        Integer l2 = pq2.poll();
        while(!pq1.isEmpty() || !pq2.isEmpty()) {
            if (l2>l1) {
                min = Math.min(l2-l1, min);
                if (!pq1.isEmpty())
                    l1 = pq1.poll();
                else
                    return min;
            } else {
                min = Math.min(l1-l2, min);
                if (!pq2.isEmpty())
                    l2 = pq2.poll();
                else
                    return min;
            }
        }
        
        return Math.min(min, Math.abs(l2-l1));
    }
}

Strobogrammatic Number

【题目】A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers “69″, “88″, and “818″ are all strobogrammatic.

【解答】这个题目的关键在于找strobogrammatic这种数可能的组合,仔细思考以后,发现就这么几种:11,88, 00, 69,96。

class Solution {
    public boolean isStrobogrammatic(String num) {
        if (num==null || num.length()==0)
            return false;
        
        int l=0, r=num.length()-1;
        while(l<=r) {
            int lnum = num.charAt(l)-'0';
            int rnum = num.charAt(r)-'0';
            
            if (!isStrobogrammatic(lnum, rnum))
                return false;
            
            l++;
            r--;
        }
        
        return true;
    }
    
    private boolean isStrobogrammatic(int l, int r) {
        if (l==1 && r==1)
            return true;
        if (l==8 && r==8)
            return true;
        if (l==6 && r==9 || l==9 && r==6)
            return true;
        if (l==0 && r==0)
            return true;
        
        return false;
    }
}

Strobogrammatic Number II

【题目】A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return ["11","69","88","96"].

【解答】有了前面题目的积累,这个题目可以考虑构造法而不是采用搜索法。即我们已经知道n位的数怎样构造才能组成满足题目的数。通常能构造的时候,可以不要使用搜索,因为搜索的复杂度比构造高

class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<>();
        if (n<=0) return result;
        
        fs("", n, result);
        
        return result;
    }
    
    private void fs(String x, int n, List<String> result) {
        if (n==0) {
            if (x.length()!=0) {
                if (x.startsWith("0") && !x.equals("0"))
                    return;
                
                result.add(x);
            }
            
            return;
        }
        
        if (n%2==1) {
            fs("1", n-1, result);
            fs("8", n-1, result);
            fs("0", n-1, result);
        } else {
            fs("1"+x+"1", n-2, result);
            fs("8"+x+"8", n-2, result);
            fs("0"+x+"0", n-2, result);
            
            fs("6"+x+"9", n-2, result);
            fs("9"+x+"6", n-2, result);
        }
        
    }
}

Strobogrammatic Number III

【题目】A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = “50″, high = “100″, return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the low and high numbers are represented as string.

【解答】和上题相比更进一步,现在要找一个范围内所有的strobogrammatic数。我们可以继续使用构造法,但是需要判断数是不是在要求的范围内。

class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int sl = low.length();
        int sh = high.length();
        
        int count = 0;
        for (int i=sl; i<=sh; i++) {
            count += sr(low, high, "", i);
        }
        
        return count;
    }
    
    private int sr(String low, String high, String str, int i) {
        int ll = low.length();
        int hl = high.length();
        
        if (i==0) {
            if (str.length()==ll && str.compareTo(low)<0)
                return 0;
            if (str.length()==hl && str.compareTo(high)>0)
                return 0;
            
            if (str.startsWith("0") && !str.equals("0"))
                return 0;
            
            return 1;
        }
        
        int count = 0;
        if (i%2==1) {
            count += sr(low, high, "0", i-1);
            count += sr(low, high, "1", i-1);
            count += sr(low, high, "8", i-1);
        } else {
            count += sr(low, high, "0"+str+"0", i-2);
            count += sr(low, high, "1"+str+"1", i-2);
            count += sr(low, high, "8"+str+"8", i-2);
            
            count += sr(low, high, "9"+str+"6", i-2);
            count += sr(low, high, "6"+str+"9", i-2);
        }
        
        return count;
    }
}

Group Shifted Strings

【题目】Given a string, we can “shift” each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep “shifting” which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
A solution is:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

【解答】关键是处理好ba这种后面的字符字母序小于前面字符的情况。用一个map来给他们归类,key为相邻两个字符间的距离。

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<List<Integer>, List<String>> map = new HashMap<>();
        for (String str : strings) {
            List<Integer> list = new ArrayList<>(str.length()-1);
            Character last = null;
            for (int i=0; i<str.length(); i++) {
                Character ch = str.charAt(i);
                if (last==null) {
                    last = ch;
                } else {
                    int diff = ch - last;
                    if (ch<last) {
                        diff = ('z'-last) + (ch-'a') + 1;
                    }
                    
                    list.add(diff);
                    last = ch;
                }
            }
            
            List<String> strs = map.getOrDefault(list, new ArrayList<>());
            strs.add(str);
            map.put(list, strs);
        }
        
        return new ArrayList<>(map.values());
    }
}

Count Univalue Subtrees

【题目】Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

 

return 4.

【解答】定义一个类Res,用来存放两个信息,一个是树是否是univalue的,一个是该树往下包含的univalue的树有多少个。这样就可以用递归来解了:

class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        if (root==null) return 0;
        
        return count(root).count;
    }
    
    private Res count(TreeNode root) {
        int count = 0;
        boolean isUS = true;
        if (root.left!=null) {
            Res left = count(root.left);
            if (!left.isUS || root.val!=root.left.val)
                isUS = false;
            
            count += left.count;
        }
        if (root.right!=null) {
            Res right = count(root.right);
            if (!right.isUS || root.val!=root.right.val)
                isUS = false;
            
            count += right.count;
        }
        
        if (isUS)
            count++;
        
        return new Res(count, isUS);
    }
}

class Res {
    int count;
    boolean isUS;
    
    public Res(int count, boolean isUS) {
        this.count = count;
        this.isUS = isUS;
    }
}

Flatten 2D Vector

【题目】Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

【解答】只有二维,那问题就不麻烦,用两个指针,一个p,一个q,分别指向第一维的位置和第二维的位置。定一个一个check方法,用来保持指针指向的位置是有意义的。

public class Vector2D implements Iterator<Integer> {
    private List<List<Integer>> lists = null;
    private Integer p = null;
    private Integer q = null;
    
    public Vector2D(List<List<Integer>> vec2d) {
        this.lists = vec2d;
    }

    @Override
    public Integer next() {
        int toReturn = lists.get(p).get(q);
        q++;
        check();
        
        return toReturn;
    }

    @Override
    public boolean hasNext() {
        if (p==null) {
            if (lists==null || lists.isEmpty())
                return false;
            p = 0;
        }
        
        if (q==null) {
            q = 0;
            check();
        }
        
        return p!=lists.size();
    }
    
    private void check() {
        while (p!=lists.size()) {
            List list = lists.get(p);
            if (list==null || q>=list.size()) {
                p++;
                q=0;
            } else {
                return;
            }
        }
        
        return;
    }
}

Meeting Rooms

【题目】Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

【解答】先根据start时间排序,然后从小到大遍历,如果发现重叠的情况,就返回false。

class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval l, Interval r) {
                return l.start - r.start;
            }
        });
        
        Integer lastEnd = null;
        for (Interval it : intervals) {
            if (lastEnd==null) {
                lastEnd = it.end;
            } else {
                if (it.start<lastEnd)
                    return false;
                
                lastEnd = it.end;
            }
        }
        
        return true;
    }
}

Meeting Rooms II

【题目】Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

【解答】把每个时间段拆成两个点,分别为开始点和结束点。然后把所有的点排序,要求时间点早的放在前,如果时间点一样,把表示结束的点放在前。接着就可以遍历并计数了:

class Iter {
    int val;
    boolean start;
    public Iter(int val, boolean start) {
        this.val = val;
        this.start = start;
    }
}
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        List<Iter> list = new ArrayList<>(intervals.length * 2);
        for (Interval inter : intervals) {
            Iter start = new Iter(inter.start, true);
            Iter end = new Iter(inter.end, false);
            list.add(start);
            list.add(end);
        }
        
        Collections.sort(list, new Comparator<Iter>() {
            @Override
            public int compare(Iter l, Iter r) {
                if (l.val==r.val) {
                    if ((l.start && r.start) || (!l.start && !r.start))
                        return 0;
                    else if (l.start)
                        return 1;
                    else
                        return -1;
                } else {
                    return l.val - r.val;
                }
            }
        });
        
        int count = 0;
        int max = 0;
        for (Iter it : list) {
            if (it.start) {
                count++;
                max = Math.max(max, count);
            } else {
                count--;
            }
        }
        
        return max;
    }
}

Factor Combinations

【题目】Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

  1. You may assume that n is always positive.
  2. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

【解答】这类找所有组合的题目,通常可以优先考虑(1)排列组合方法能不能解,(2)其它构造法能不能解,不能的话可以用回溯法,那样的话就是一个常规问题了。回溯法的时候这里用一个list来记录走到某状态的时候,之前生成的路径,可以不断维护这个状态list,这样就避免了一大堆“new ArrayList”的代码。有些题目用回溯法解的时候,我们使用一个“visited”数组,原理是类似的。

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        cal(n, new ArrayList<>(), result);
        return result;
    }
    
    private void cal(int n, List<Integer> list, List<List<Integer>> result) {
        if (n==1) {
            if (list.size()>1) {
                List<Integer> copy = new ArrayList<>(list);
                result.add(copy);
            }
            
            return;
        }
        
        int last = 2;
        if (!list.isEmpty())
            last = list.get(list.size()-1);
        for (int i=last; i<=n; i++) {
            if (n%i==0) {
                list.add(i);
                cal(n/i, list, result);
                list.remove(list.get(list.size()-1));
            }
        }
    }
}

Verify Preorder Sequence in Binary Search Tree

【题目】Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:
Could you do it using only constant space complexity?

【解答】首先我考虑用递归来解,要求常数空间复杂度,就定义一个start和end的组合来表示区间,在区间内满足如下条件的数列为合法的二叉搜索树:

  • 第一个数是根,接着往后遍历,前半段的数必须小于它(左子树),一旦发现某个数大于它了,表示后半段开始了(右子树),但是在后半段里面发现又有数小于根,就是非法了,否则为合法。
  • 对左子树和右子树继续如上检查。

代码不复杂:

class Solution2 {
    public boolean verifyPreorder(int[] preorder) {
        return verify(preorder, 0, preorder.length-1);
    }
    
    private boolean verify(int[] preorder, int start, int end) {
        if (start>=end) return true;
        
        int root = preorder[start];
        Integer firstRight = null;
        for (int i=start+1; i<=end; i++) {
            if (firstRight==null) {
                if (preorder[i]>root)
                    firstRight = i;
            } else {
                if (preorder[i]<root)
                    return false;
            }
        }
        
        if (firstRight==null)
            return verify(preorder, start+1, end);
        else
            return verify(preorder, start+1, firstRight-1) && verify(preorder, firstRight, end);
    }
}

运行出现了StackOverflowError,递归的工作栈太深,因此需要变个思路,不能这样递归了。那就写成循环吧。可以BFS,也可以DFS。我这里用BFS,判断逻辑和上面的递归比并无二致,使用一个queue来存放当前需要检查的所有子树。

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Queue<Range> queue = new LinkedList<>();
        Range r = new Range(0, preorder.length-1);
        queue.add(r);
        
        while (!queue.isEmpty()) {
            Queue<Range> nq = new LinkedList<>();
            for (Range range : queue) {
                int start = range.start;
                int end = range.end;
                
                if (start>=end) continue;
                
                int root = preorder[start];
                Integer firstRight = null;
                for (int i=start+1; i<=end; i++) {
                    if (firstRight==null) {
                        if (preorder[i]>root)
                            firstRight = i;
                    } else {
                        if (preorder[i]<root)
                            return false;
                    }
                }

                if (firstRight==null) {
                    nq.add(new Range(start+1, end));
                } else {
                    nq.add(new Range(start+1, firstRight-1));
                    nq.add(new Range(firstRight, end));
                }
            }
            
            queue = nq;
        }
        
        return true;
    }
}

class Range {
    int start;
    int end;
    
    public Range(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

Paint House

【题目】There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

【解答】思路基本上是DP,任意一个柱子 i 涂上颜色 x 的最小花费都和它前一个柱子涂上的其他两种颜色的最小花费相关。我可以建立三个滚动变量来存放当前柱子分别涂上这三种颜色的花费,也可以直接利用costs变量来存放,就连滚动变量都省了。

class Solution {
    public int minCost(int[][] costs) {
        // red blue green
        if (costs==null || (costs.length>0 && costs[0].length!=3))
            throw new IllegalArgumentException();
        
        if (costs.length==0)
            return 0;
        
        for (int i=0; i<costs.length; i++) {
            if (i==0) continue;
            
            costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2]);
            costs[i][1] += Math.min(costs[i-1][0], costs[i-1][2]);
            costs[i][2] += Math.min(costs[i-1][0], costs[i-1][1]);
        }
        
        int last = costs.length-1;
        return Math.min(Math.min(costs[last][0], costs[last][1]), costs[last][2]);
    }
}

3Sum Smaller

【题目】Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

【解答】先排序是不会错的。之后锁定nums[i]的情况下考虑采用经典的双指针方法来寻找可行解,需要注意的是,每当双指针中的left固定,right直接找到可行解的范围,可以减小单纯遍历造成的时间复杂度。

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        
        int count = 0;
        for (int i=0; i<nums.length-2; i++) {
            int l=i+1, r=nums.length-1;
            while (l<r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum>=target) {
                    r--;
                } else {
                    count += r-l; // fix the l, move r, get all possibilities
                    l++;
                }
            }
        }
        
        return count;
    }
}

Graph Valid Tree

【题目】Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0]and thus will not appear together in edges.

【解答】无向图。要成为一棵树,意味着不能形成环。因此这道题是属于图里面的常规题。两种思路:

  1. 可以用基于搜索的BFS或者DFS来解,需要引入一个visited数组,一旦在遍历的过程中发现命中了之前遍历过的节点,说明形成环了;而如果一次遍历完毕后,发现还有节点没有覆盖到,说明存在不止一棵“树”。
  2. 当然,也可以使用并查集来求解,思路是,在构造并查集的过程中,需要union X和Y,如果发现X和Y已经是union的,说明这里存在环了;而如果在遍历完毕之后,发现并查集中存在不止一个null(null在一棵树中意味着root节点),说明这图中不止一棵树。这道题题目不难,但是非常有代表性。
class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges==null || n<0)
            return false;
        
        Integer[] map = new Integer[n];
        for (int[] edge : edges) {
            int x = find(edge[0], map);
            int y = find(edge[1], map);
            
            if (x==y) {
                // the two points are already in the map so a new edge will make a cycle
                return false;
            }
            
            // union
            map[x] = y;
        }
        
        boolean flag = false;
        for (Integer point : map) {
            if (point==null) {
                if (!flag)
                    flag = true;
                else
                    return false;
            }
        }
        
        return true;
    }
    
    private int find(int num, Integer[] map) {
        if (map[num] == null)
            return num;
        else
            return find(map[num], map);
    }
}

Paint House II

【题目】There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

【解答】这道题直接拿出来的话需要好好想想,但是已经有了前面Paint House的经验,这道题的解法可以说换汤不换药。之前只有三种颜色,现在有k种颜色而已。

class Solution {
    public int minCostII(int[][] costs) {
        if (costs.length==0)
            return 0;
        
        for (int i=0; i<costs.length; i++) {
            if (i==0) continue;
            
            for (int j=0; j<costs[0].length; j++) {
                costs[i][j] += min(costs, i-1, j);
            }
        }
        
        return min(costs, costs.length-1, null);
    }
    
    private int min(int[][] costs, int i, Integer excludeJ) {
        Integer min = Integer.MAX_VALUE;
        for (int j=0; j<costs[0].length; j++) {
            if (excludeJ!=null && excludeJ.intValue()==j)
                continue;
            
            min = Math.min(min, costs[i][j]);
        }
        
        return min;
    }
}

Palindrome Permutation

【题目】Given a string, determine if a permutation of the string could form a palindrome.

For example,
"code" -> False, "aab" -> True, "carerac" -> True.

【解答】一个字符串的排列要能成为回文,这个字符串可以全部为成对的字符,或者只有一个字符不成对。因此引入一个HashSet,为每个字符调用add方法,根据结果来判断,如果set中已经存在,说明成对了,直接从这个set中删掉。遍历完毕后,看这个set的大小,超过1就返回false。

class Solution {
    public boolean canPermutePalindrome(String s) {
        Set<Character> set = new HashSet<>();
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            if (!set.add(ch))
                set.remove(ch);
        }
        
        return set.size()<=1;
    }
}

Palindrome Permutation II

【题目】Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

【解答】要找出所有的回文排列。首先找到每个字符可能出现的次数,存在一个数组中。然后检查这个数组,只能出现最多一次的单数,否则返回空集合,即无法形成回文。接着深度优先搜索,遍历所有可能性,这个数组正好用于遍历过程中记录状态。

class Solution {
    public List<String> generatePalindromes(String s) {
        int[] arr = new int[128];
        for (int i=0; i<s.length(); i++) {
            int idx = (int)s.charAt(i);
            arr[idx]++;
        }
        
        Integer odd = null;
        for (int i=0; i<arr.length; i++) {
            if (arr[i]%2==1) {
                if (odd!=null)
                    return new ArrayList<>();
                else
                    odd = i;
            }
        }
        
        List<String> result = new ArrayList<>();
        if (odd!=null) {
            arr[odd]--;
            travel((char)(odd.intValue()) + "", arr, result);
        } else {
            travel("", arr, result);
        }
        
        return result;
    }
    
    private void travel(String str, int[] arr, List<String> result) {
        boolean hasData = false;
        for (int i=0; i<arr.length; i++) {
            if (arr[i]==0) continue;
            
            hasData = true;
            arr[i] -= 2;
            
            travel((char)i + str + (char)i, arr, result);
            
            arr[i] += 2;
        }
        
        if (!hasData) result.add(str);
    }
}

Alien Dictionary

【题目】There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is: "zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return "".

Note:

  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.

【解答】本质上是一道图的问题。图问题的解法通常需要的并不多,下面这种基于入度(in degree)的解法很常见。

  • Step 1,建立两个数据结构,一个是表示先后顺序关系map<Character, Set<Character>>,表示key的字符必须先与任何value set的字符;另一个是indegrees<Character, Integer>,表示字符的入度,即入度为0的话表示当前没有任何字符必须先于它。
  • Step 2,每次从入度indegrees中找一个入度为0的节点作为输出的元素,然后去顺序关系map中找到它的直接后继,并将这些直接后继的入度全部减一,相当于删掉了当前节点和它的所有后继之间的路径,接着循环继续找入度为0的节点。
思路如上,不过代码写得有点啰嗦:
class Solution {
    public String alienOrder(String[] words) {
        if (words.length == 0) return "";
        if (words.length == 1) return words[0];
        
        Map<Character, Set<Character>> map = new HashMap<>();
        Map<Character, Integer> indegrees = new HashMap<>();
        
        // Step 1
        String last = null;
        for (String word : words) {
            if (last==null) {
                last = word;
                continue;
            }
            
            boolean found = false;
            for (int i=0; i<word.length() || i<last.length(); i++) {
                char cw = 0;
                if (i<word.length()) {
                    cw = word.charAt(i);
                    if (!indegrees.containsKey(cw)) {
                        indegrees.put(cw, 0);
                        map.put(cw, new HashSet<>());
                    }
                }
                
                char cl = 0;
                if (i<last.length()) {
                    cl = last.charAt(i);
                    if (!indegrees.containsKey(cl)) {
                        indegrees.put(cl, 0);
                        map.put(cl, new HashSet<>());
                    }
                }
                
                if (i>=last.length() || i>=word.length() || cw==cl)
                    continue;

                if (!found) {
                    found = true;
                    Set<Character> set = map.get(cl);
                    if (set.add(cw))
                        indegrees.put(cw, indegrees.get(cw)+1);
                }
            }
            
            last = word;
        }
        
        // Step 2
        Character c = null;
        for (Map.Entry<Character, Integer> entry : indegrees.entrySet()) {
            if (entry.getValue()==0) {
                c = entry.getKey();
                break;
            }
        }
        if (c!=null)
            indegrees.remove(c);
        
        String result = "";
        while (c!=null) {
            result = result + c;
            
            Set<Character> set = map.get(c);
            if (set!=null) {
                for (Character ch : set) {
                    indegrees.put(ch, indegrees.get(ch)-1);
                }
            }
            
            c = null;
            for (Map.Entry<Character, Integer> entry : indegrees.entrySet()) {
                if (entry.getValue()==0) {
                    c = entry.getKey();
                    break;
                }
            }
            if (c!=null)
                indegrees.remove(c);
        }
        
        if (!indegrees.isEmpty())
            return "";
        
        return result;
    }
}

Closest Binary Search Tree Value

【题目】Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

  • Given target value is a floating point.
  • You are guaranteed to have only one unique value in the BST that is closest to the target.

【解答】二叉搜索树找最接近的点。如果target大于root.val,检查root.val,与右子树递归找到的最接近的点,这二者哪个更接近;如果target小于root.val,则检查root.val,与左子树递归找到的最接近的点,这二者哪个更接近。

class Solution {
    public int closestValue(TreeNode root, double target) {
        if (target==root.val) return root.val;
        
        if (target>root.val) {
            if (root.right==null) {
                return root.val;
            } else {
                int r = closestValue(root.right, target);
                if (target-root.val > Math.abs(r-target))
                    return r;
                else
                    return root.val;
            }
        } else {
            if (root.left==null) {
                return root.val;
            } else {
                int l = closestValue(root.left, target);
                if (root.val-target > Math.abs(l-target))
                    return l;
                else
                    return root.val;
            }
        }
    }
}

Encode and Decode Strings

【题目】Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

  • The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
  • Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
  • Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

【解答】要加密和解密一个字符串数组,如果要尝试去引入一个特殊的符号来分隔这几个string,就走上一条不归路了。因为无论选用什么分隔符,这个分隔符都可能在这个string list里面出现过。我采用的办法是类似于某些协议的设计,使用第一个换行符”\n”来分隔加密后报文的头部和实体。头部存放所有string的长度列表,实体则是所有string的简单拼接。

注意两个edge cases:空list,这种情况下头部为空;list中包含空字符串””,这种情况下该字符串的长度为0,因此头部不可能为空。

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        String lengths = "";
        for (String str : strs) {
            lengths += str.length() + ",";
            sb.append(str);
        }
        
        if (lengths.length()>0)
            lengths = lengths.substring(0, lengths.length()-1);
        
        return lengths + '\n' + sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        int idx = s.indexOf('\n');
        String lens = s.substring(0, idx);
        if (idx==0) return new ArrayList<>();

        String[] ls = lens.split("\\,");

        List<String> list = new ArrayList<>(ls.length);
        int p=idx+1;
        for (String l : ls) {
            int strl = Integer.parseInt(l);
            if (strl==0) {
                list.add("");
                continue;
            }
            list.add(s.substring(p, p+strl));
            p = p + strl;
        }
        
        return list;
    }
}

Closest Binary Search Tree Value II

【题目】Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

【解答】在BST中,需要返回k个和target最接近的节点。我的做法是:

  • Step 1: 先先序遍历BST得到一个有序的double linked list,同时也记录下了最接近的节点;
  • Step 2: 然后双指针一个往前,一个往后,寻找下一个最接近的点,直到找到k个为止。
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Item c = null;
        Item min = null;
        
        // Step 1
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur!=null || !stack.isEmpty()) {
            if (cur!=null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode tn = stack.pop();
                
                if (c==null) {
                    c = new Item(tn.val);
                    min = c;
                } else {
                    c.next = new Item(tn.val);
                    c.next.prev = c;
                    
                    c = c.next;
                    if (Math.abs(c.val-target) < Math.abs(min.val-target))
                        min = c;
                }
                
                cur = tn.right;
            }
        }
        
        // Step 2
        Item l=min.prev, r=min.next;
        List<Integer> result = new ArrayList<>();
        result.add(min.val);
        while (result.size()<k) {
            double leftDiff = Double.MAX_VALUE;
            if (l!=null) {
                leftDiff = Math.abs(l.val-target);
            }
            
            double rightDiff = Double.MAX_VALUE;
            if (r!=null) {
                rightDiff = Math.abs(r.val-target);
            }
            
            if (leftDiff<rightDiff) {
                result.add(l.val);
                l = l.prev;
            } else {
                result.add(r.val);
                r = r.next;
            }
        }
        
        return result;
    }
}

class Item {
    int val;
    Item prev;
    Item next;
    
    public Item(int val) {
        this.val = val;
    }
}

虽然AC了,不过我觉得应该有更优的解法,因为我遍历了BST所有的节点,事实上,如果只要找K个,以某种方法我应该只需要遍历K个,或者接近K个节点即可。

Paint Fence

【题目】There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

【解答】首先要理解题意。题目说得不太清楚,有人在评论区里面说,一种更清晰的描述方式应该是“no 3 adjacent posts have the same color”,就是说不能连续三个post都涂上同一种颜色。现在考虑任意的连续两根柱子A和B,存在两种可能,一种是A和B同色,这种情况下的种类数设为same;另一种是A和B不同色,种类数设为diff。现在要给下一根柱子C涂色:

  • 如果C和相邻的B同色,那么很显然共有diff种涂法,因为如果A和B同色时,是不能允许C和B继续同色的;
  • 如果C和B不同色,那么有两种情况,一种是A和B同色,这种情况下要避免B和C同色,共有same*(k-1)种涂法;另一种是A和B不同色,而又要求B和C不同色,共有diff*(k-1)种涂法。
class Solution {
    public int numWays(int n, int k) {
        if (n==0 || k==0)
            return 0;
        
        if (n==1)
            return k;
        else if (n==2)
            return k*k;
        
        int same = k;
        int diff = k*(k-1);
        
        for (int i=3; i<=n; i++) {
            int newSame = diff;
            int newDiff = (same+diff) * (k-1);
            
            same = newSame;
            diff = newDiff;
        }
        
        return same + diff;
    }
}

Find the Celebrity

【题目】Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

【解答】找名人问题。n个人里面,存在至多一位名人。名人不认识其余任何一个人,而其余任何一人都认识名人。

  • 用一个变量last记录疑似名人的那个人,对于其他人i,调用knows(last, i),如果返回true,说明last不可能是名人,于是更新last为i;
  • 接着再反过来第二遍循环中调用kowns(i, last),如果返回false,说明这个last有人不认识,那么这个last就不是名人,如果所有的i都认识last,last就是名人。
public class Solution extends Relation {
    public int findCelebrity(int n) {
        if (n<=1)
            return -1;
        
        Integer last = null;
        for (int i=0; i<n; i++) {
            if (last==null) {
                last = i;
                continue;
            }
            
            boolean know = knows(last, i);
            if (know) {
                last = i;
            }
        }

        for (int i=0; i<n; i++) {
            if (last!=i) {
                boolean know = knows(i, last);
                if (!know)
                    return -1;

                know = knows(last, i);
                if (know)
                    return -1;
            }
        }
        
        return last;
    }
}
 

Wiggle Sort

【题目】Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

【解答】先排序,然后从头、尾依次取数。

class Solution {
    public void wiggleSort(int[] nums) {
        if (nums==null || nums.length==0)
            return;
        
        int[] numsCopy = new int[nums.length];
        System.arraycopy(nums, 0, numsCopy, 0, nums.length);
        Arrays.sort(numsCopy);
        
        int left=0, right=numsCopy.length-1;
        int i=0;
        boolean flag = true;
        while(i<nums.length) {
            if (flag) {
                nums[i++] = numsCopy[left];
                left++;
                flag = !flag;
            } else {
                nums[i++] = numsCopy[right];
                right--;
                flag = !flag;
            }
        }
    }
}

Zigzag Iterator

【题目】Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question – Update (2015-09-18):
The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:

[1,2,3]
[4,5,6,7]
[8,9]

It should return [1,4,8,2,5,9,3,6,7].

【解答】用一个boolean变量记录下一个访问的节点是在v1还是v2;用一个int变量col用来记录节点下标。建立一个adjust方法用来针对一些不合法的情况调整节点的位置,比如v1或者v2已经穷尽时。保证每次方法调用以后内部总是能够准备好下一个需要返回的节点。

public class ZigzagIterator {
    private List<Integer> v1 = null;
    private List<Integer> v2 = null;
    
    private boolean row = true;
    private int col = 0;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.v1 = v1;
        this.v2 = v2;
        adjust();
    }

    private void adjust() {
        if (row) {
            if (v1.size()<=col) {
                row = false;
            }
        } else {
            if (v2.size()<=col) {
                row = true;
                col++;
            }
        }
    }
    
    public int next() {
        List<Integer> v = row ? v1 : v2;
        if (col>=v.size()) throw new RuntimeException();
        
        int res = v.get(col);
        if (row) {
            row = false;
        } else {
            row = true;
            col++;
        }
        adjust();
        
        return res;
    }

    public boolean hasNext() {
        List<Integer> v = row ? v1 : v2;
        return col<v.size();
    }
}

Inorder Successor in BST

【题目】Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

【解答】用一个boolean变量记录是否已经找到p了。剩下的和普通的二叉树的中序遍历没有区别。

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        boolean matched = false;
        while (cur!=null || !stack.isEmpty()) {
            if (cur!=null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode tn = stack.pop();
                if (matched) {
                    return tn;
                } else {
                    if (p==tn) matched = true;
                    cur = tn.right;
                }
            }
        }
        
        return null;
    }
}

Walls and Gates

【题目】You are given a m x n 2D grid initialized with these three possible values.

  1. -1 – A wall or an obstacle.
  2. 0 – A gate.
  3. INF – Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

【解答】我一开始的思路是DFS,从任何一点出发,为了防止循环探索,先标记自己为障碍(-1),然后探索上下左右四个方向,以找到里gate最近的步数。可是这样的方法有一个问题,在标记自己(比如为A)为障碍的时候,如果探索的位置正好需要通过A才可达呢?这样得出的结果是有问题的。另外一个麻烦的地方是,有些地方是不可达的,因此需要标记为INF,可是怎样区分是原始的INF还是我希望标记的INF呢?这个问题又需要额外的逻辑来处理。

于是,换个思路。一个相对简单的办法是,找所有gate(0)的位置,然后从gate开始往周围蔓延,寻找所有通过这个门可达的点,并且记录和更新最小步数。其中,在寻找的过程中,如果发现在该位置上已经出现了更小的值,这个值可能是障碍(-1),也可能是更小的步数,就直接返回,以减小计算量。代码简单很多。我觉得这道题在迷宫类问题中是有一定代表性的。

class Solution {
    public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; i++) {
            for (int j = 0; j < rooms[0].length; j++) {
                if (rooms[i][j] == 0)
                    mark(rooms, i, j, 0);
            }
        }
    }

    private void mark(int[][] rooms, int i, int j, int step) {
        if (i < 0 || j < 0 || j >= rooms[0].length || i >= rooms.length || rooms[i][j] < step)
            return;
        
        rooms[i][j] = step;
        
        mark(rooms, i - 1, j, step + 1);
        mark(rooms, i + 1, j, step + 1);
        mark(rooms, i, j - 1, step + 1);
        mark(rooms, i, j + 1, step + 1);
    }
}

Unique Word Abbreviation

【题目】An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word’s abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example: 

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

【解答】写一个方法来得到一个词语的缩略形式,然后把缩略形式作为key,放到map里面去。这样查询的时候就可以看给定的缩略形式是不是可以找到唯一的对应词语。

class ValidWordAbbr {
    private Map<String, Set<String>> map = new HashMap<>();
    public ValidWordAbbr(String[] dictionary) {
        for (String s : dictionary) {
            String key = getKey(s);
            Set<String> set = map.get(key);
            if (set == null)
                set = new HashSet<>();
            
            set.add(s);
            
            map.put(key, set);
        }
    }
    
    private String getKey(String s) {
        String key = null;
        if (s.length()<3)
            key = s;
        else
            key = "" + s.charAt(0) + (s.length()-2) + s.charAt(s.length()-1);
        
        return key;
    }
    
    public boolean isUnique(String word) {
        String key = getKey(word);
        if (!this.map.containsKey(key))
            return true;
        else {
            Set<String> set = this.map.get(key);
            if (set.size() == 1 && set.contains(word))
                return true;
        }
        
        return false;
    }
}

Word Pattern II

【题目】Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Examples:

  1. pattern = "abab", str = "redblueredblue" should return true.
  2. pattern = "aaaa", str = "asdasdasdasd" should return true.
  3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:

You may assume both pattern and str contains only lowercase letters.

【解答】判断字符串是否匹配这个pattern。我的思路是回溯法,使用两个map,一个是pattern的字符对应到str中的substring的map;另一个是反过来,substring对应到字符。

  • 如果发现某个字符在map中出现过,必须要同时检查另一个map,看这个substring是否也出现过且对应到相同的字符去,然后才递归调用余下的部分。
  • 如果发现字符没有出现过,也要类似的操作,确保选取的substring也是没有出现过的。再递归调用余下的部分,只要有一种substring选取的解返回true,这个方法就返回true。
class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        return match(pattern, 0, str, 0, new HashMap<>(), new HashMap<>());
    }
    
    private boolean match(String pattern, int p, String str, int s, Map<Character, String> map, Map<String, Character> map2) {
        if (p==pattern.length() && s==str.length()) return true;
        if (p==pattern.length() || s==str.length()) return false;
        
        char cp = pattern.charAt(p);
        if (map.containsKey(cp)) {
            String token = map.get(cp);
            if (token.length()>=str.length()-s+1)
                return false;
            
            String sub = str.substring(s, s+token.length());
            if (!sub.equals(token))
                return false;
            
            Character ch = map2.get(sub);
            if (ch.charValue()!=cp)
                return false;
            
            return match(pattern, p+1, str, s+token.length(), map, map2);
        } else {
            for (int i=1; i<=str.length()-s; i++) {
                String sub = str.substring(s, s+i);
                if (map2.containsKey(sub))
                    continue;
                
                map.put(cp, sub);
                map2.put(sub, cp);
                
                boolean res = match(pattern, p+1, str, s+i, map, map2);
                if (res) return true;
                
                map.remove(cp);
                map2.remove(sub);
            }
            
            return false;
        }
    }
}

Flip Game

【题目】You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.

For example, given s = "++++", after one move, it may become one of the following states:

[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list [].

【解答】转成char array然后替换相应的字符。

class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> result = new ArrayList<>();
        for (int i=1; i<s.length(); i++) {
            if (s.charAt(i)=='+' && s.charAt(i-1)=='+') {
                char[] chs = s.toCharArray();
                chs[i] = '-';
                chs[i-1] = '-';
                result.add(new String(chs));
            }
        }
        return result;
    }
}

Flip Game II

【题目】You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm’s runtime complexity.

【解答】本质上还是回溯法。自己当前可以选择一步走,如果走了哪一步,接下去如果对手无法赢,那么自己就赢了。

class Solution {
    public boolean canWin(String s) {
        return canWin(s.toCharArray());
    }
    
    private boolean canWin(char[] chs) {
        for (int i=1; i<chs.length; i++) {
            if (chs[i]=='+' && chs[i-1]=='+') {
                
                chs[i]='-';
                chs[i-1]='-';
                
                boolean res = canWin(chs);
                
                chs[i]='+';
                chs[i-1]='+';
                
                if (!res)
                    return true;
            }
        }
        
        return false;
    }
}

Best Meeting Point

【题目】A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0)(0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

【解答】显然,把图上的每个点取出来去计算和所有人所在的点距离之和是一个办法,但是复杂度太高了。考虑优化的办法。这里的距离用的是曼哈顿距离,因此可以看到,行和列的距离计算是完全独立的。也就是说,从行这个维度上去取点的逻辑,和从列这个维度上去取点的逻辑,是互不影响的。这一点非常重要,因为有了这一个理论基础,就可以把这个二维的问题降为一维来解决。

如果这个图只有一维,那么这些人的位置的中位数是最佳的位置(不是平均数)。有了这个发现以后,问题就变成了求中位数的过程,也就迎刃而解了。

class Solution {
    public int minTotalDistance(int[][] grid) {
        List<Integer> rows = new ArrayList<>();
        List<Integer> cols = new ArrayList<>();
        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[0].length; j++) {
                if (grid[i][j]==1) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        
        Collections.sort(rows);
        Collections.sort(cols);
        
        int i = rows.get(rows.size() / 2);
        int j = cols.get(cols.size() / 2);
        
        int total = 0;
        for (int p : rows) {
            total += Math.abs(p-i);
        }
        for (int q : cols) {
            total += Math.abs(q-j);
        }
        
        return total;
    }
}

Binary Tree Longest Consecutive Sequence

【题目】Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    /
   2
  /
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

【解答】建立一个Result对象,用来在递归遍历这棵树的时候传递子树的结果,包含两个值,一个是发现的最长递增串,一个是以该子树root为起点的最长递增串。

class Solution {
    public int longestConsecutive(TreeNode root) {
        return travel(root).longest;
    }
    
    private Result travel(TreeNode root) {
        if (root==null)
            return new Result();
        
        int longest = 1;
        int increasing = 1;
        
        Result left = travel(root.left);
        longest = Math.max(left.longest, longest);
        if (root.left!=null && root.val+1==root.left.val) {
            increasing = Math.max(left.increasing+1, increasing);
        }
        
        Result right = travel(root.right);
        longest = Math.max(right.longest, longest);
        if (root.right!=null && root.val+1==root.right.val) {
            increasing = Math.max(right.increasing+1, increasing);
        }
        
        longest = Math.max(longest, increasing);
        
        Result res = new Result();
        res.longest = longest;
        res.increasing = increasing;
        
        return res;
    }
}

class Result {
    int longest;
    int increasing;
}

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2zAkCcu

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 几个系统设计问题的解决思路

几个系统设计问题的解决思路曾经写过一些系统设计方面的思考(比如这个这个),但是最近准备面试,又接触了更多系统设计方面的问题。这里我想简单记录一些典型系统设计问题的思路。通过学习常见的系统,在心中形成一些问题解决的套路,以在思考和分析新问题的时候提供一些既定思路。很抱歉时间关系写得很简略,主要是提示一些思路和方向。

设计Tweeter
两种常见模型的trade off:

  • Pull on demand: merge x timelines
  • Push on change: async, read once to get them

缓存的设计,cache through
Following table的设计,好友关系存两份,A -> B 和 B -> A

设计Web crawler
分布式queue,用来存放不断更新的需要爬虫完成的任务,典型的N个生产者+M个消费者的模型
key value storage,用来存储已经完成的网页,爬下来的数据放在S3上
Quota的使用:用来避免对某一个网站分配过多的资源

设计Type Ahead
核心在于避免从磁盘中实时查询,所有查询必须最快命中内存中的数据结构,并且查询的效率必须是O(1)的
采用Trie树,并且每个节点都要有指向结果集的链接
这样的数据结构的生成和更新必须在一开始就初始化完成

设计邮件系统
核心在于存储层schema的设计,user id作为range key,email id作为primary key,邮件的时间列索引化,以便查询某人最近的邮件
读写分离,收取邮件和发送邮件的服务分开

设计图片上传和访问系统
核心在于CDN的使用,要把静态资源的读取推送到离用户近的节点去。
处理在用户上传图片后,CDN数据还没有最新数据的情况(数据不一致的问题)

设计图像转换服务
典型异步系统的设计:

  • 一个分布式queue存放异步任务,
  • 另一个key-value storage存放任务状态,用来供另外的系统查询任务状态

两个API设计:上传图像后返回上传成功和任务ID;查询当前任务状态
另外可以考虑Lambda这种serverless的方式

设计分布式文件系统
核心在于怎么存放文件的meta data和实际的data从而分担读写压力,怎么处理文件的更新和删除
比如master上存放粗略的meta data,知道文件的分片在哪个slave服务器上,slave上存放分片具体信息,client读写仅仅通过master定位到slave,余下的工作不通过master完成,以避免master成为瓶颈
chunk和checksum的设计和使用

设计Tiny URL服务
schema的设计,需要解决两个问题:short URL -> long URL(最多被使用)和 long URL -> short URL
short URL的生成,几种方法在分布式系统中生成唯一ID
读基于缓存的优化

设计流量限制系统

  • 思路1:Cache TTL on bucket level
  • 思路2:Leaky Bucket / Token Bucket

设计Metrics系统
Ring Buffer,根据不同的统计粒度,设定不同的bucket size
根据不同的统计粒度,建立不同的表来持久化和供未来查询
读写模型:写多读少,汇总增量数据后再更新的优化

设计打车系统
核心在于司机和乘客怎样更新地理位置信息,系统怎样存储地理位置信息,已经怎样为乘客寻找最近的司机(geo hash)
读写模型:写多读少,怎样优化系统来应付这种状况,一致性的牺牲

设计即时聊天系统
引入Channel Service,socket push的使用
存储:解耦成消息表和会话表,使得用户可以单独设定每个会话的属性引入Channel Service
用户在线状态的维护:heartbeat

设计联机日志服务
持久化问题,日志client和日志service,减少单点故障造成的日志丢失
尽可能不影响现有业务应用,线程必须独立
引入队列,对于大量日志写入的缓冲
在网络不可用时,日志客户端可以写入本地文件,网络恢复后可以上传本地文件

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2A3drX9

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 近期面试求职的经历和感受

近期面试求职的经历和感受好久没有更新了。回来报个到,也向关注和提醒我blog更新的朋友们道个歉。原因在于,最近非常忙,忙于找工作。现在下家还没有定下来,手头有几个offer,还在考虑中,但是很快会决定下来,然后更新更进一步的信息。无论如何,blog的更新已经恢复正轨。
通常人的一生中不会有太多属于自己的求职季节,尤其像我这样的,总觉得在一个地方需要积累,因而并不是频繁跳槽的粉丝。第一份工作在华为,我干了三年半;第二份工作在亚马逊,直到现在,超过了五年半。职业生涯的前方就将是第10个年头。

为什么是现在?

三年半前我通过L签证来到西雅图,而L签证是不能够更换雇主的,因而自然也不用考虑工作变更的可能性。去年10月我正式变更为H1B签证,可以变更雇主了,但是我的孩子很快出生,而且我身体状况也不是很好,就选择等一等,这一等就到如今。人都是有惰性的,这件事情上就是潜意识里害怕变化。但是另一方面,潜在的变化也会让人感到野心勃勃和充满欲望。我对自己说,不管结果怎样,一定要把自己放到这个市场上掂掂分量。在任何一个地方呆太久了,都不利于眼界的扩展

都从哪些角度考虑下一份工作?

工程师,Individual Contributor,技术路线。对管理岗没有什么兴趣。

技术的角度看,我希望能够继续专注于我感兴趣的领域,既包括全栈工程,也包括分布式系统。前者从能力上可能更适具备竞争力,后者则是我近几年的兴趣点。以往我总是说要积累各个领域的知识和体验,但是现在我慢慢在计划,到35~40岁,我需要明确下专注的领域,而不再像以往这样“不挑食”。这几年我会不断接近和过渡到这个目标,慢慢地明确和提炼自己的核心竞争力。

随着经验的增长,往往每一份工作都会比前一份报酬更高,也被寄予更大的期望。换言之,跳槽也会越来越难,这是职业生涯向上发展的一个标志。

非技术的角度看。我当然想拿更高的薪酬,体现我的价值,包括薪水也包括级别。我也希望能继续做一些有影响力的工作,既包括用户层面的影响力,又包括产品层面的影响力,和出色的工程师一起工作。小团队,但是有大野心。这是我的偏好,优先级上先考虑团队和项目,再考虑雇主。工作签证的关系,我不太想考虑特别小的公司。对于中型公司还是巨头,我是有挣扎的。但是无论如何,产品和雇主的前景,是我看中的东西。

北美工作难找吗?

既难,又不难。说它难,是因为它的玩法和国内大不相同,对于工程师的功底,特别是数据结构和算法的考察,比国内大多数公司要严苛得多。几乎所有的面试都要求现场写代码,而且要写可工作的代码,不是伪代码。说它不难,则是因为这里的面试更便于准备,项目、代码和系统设计,几乎涵盖了百分之八十的面试内容。换言之,北美的技术面试更注重工程师的思维,而国内则问很多知识性的内容,各有利弊。我得适应这种不同的玩法。

不过相对于说工作难不难找,我倒是想从recruiter的角度说一声,招一个优秀的工程师,真是太难了,大量的人力成本,电话面试1到2个小时,onsite 4到7个小时,再加上组织沟通的成本,feedback和debrief的成本,有时还需要管酒店机票,等等等等。最后,这个工程师还不一定去了哪家。这也是为什么很多IT公司都已经把“招人”作为第一要务了。几年前在国内的时候有一个recruiter说过两个有趣的二八法则,一个是,软件工程师的20%的岗位由那些80%的工程师去争抢;另一个是,市场上最容易发现的80%的简历都是那些20%的不够优秀的工程师撰写的。

简历重要吗?

我犯过一个错误,觉得简历这个东西,不是很重要,重要的是面试表现。于是“简历拒”就生生打了我脸。简历需要好好打磨,如今的简历并不需要局限在一页纸。如果经历丰富,一页纸是很难说清楚的。

由于工作机会很多,特别是在LinkedIn上,不断有猎头“骚扰”。因此我没有使用像Monster或者Indeed这样的招聘网站,这和我在国内当时离开华为找工作的策略是不同的。我只选择自己感兴趣的公司,或推荐或定向投简历。事实上,这种也帮我过滤了信息,避免了很多不必要的沟通。

怎么准备面试?

关于算法和数据结构。很多人都说要刷题,Leetcode已经到了差不多700道,刷题这种事情是没有止境的,我看“一亩三分地”上有一种很不好的风气,就是试图通过题海战术去“偶遇”面试中刷过的题目。作为骑驴找马的我来说,自然不愿意也不可能去选择这样的方式。我给自己定下的目标是,与其去统计那些做过的题目的数量,不如精致地总结一些常见的套路。套路这个东西数量并不多。事实上我做过一些题目,但是很多题目做得都很差,而且大部分都忘记了,只有少部分能够在面试中遇到,即便遇到了,还是需要我现场去通过思考和交流解决问题。

关于系统设计。因为我已经工作好些年了,系统设计往往会成为一个重点考察对象。除了日常的积累以外,也是有一些套路可寻的。仅仅凭借日常积累,是很难做好面试中的系统设计的。总结常见和经典的系统设计,就成为了非常有助益的一环。以前写过一点点,但是现在看起来还是太浅了,我也许以后为稍微写一点经典的系统设计。

最后,关于自己的项目,说清楚,画清楚,从架构到细节。还有那些烂大街的behavior questions,我想不必提及了。

面试时间规划上有策略吗?

有。我的经验是,把特别想去的公司往后放。电话面试相对宽松,但是最初的两三次电话面试只能用作积攒经验,成功率肯定不如后来进行的高。对于onsite,把想去公司的onsite放到一起,密集一两周完成。越想去的公司越往后放。这里的原因是,雇主一旦给offer,很多只有一周到两周的决定时间,希望offer互相compete,就只能把这些onsite放到一起。几乎所有的公司都愿意在有offer deadline的情况下加快流程前进的速度。

如果可能的话,面试的数量要达到一定才能积累足够的经验。我前前后后总共onsite了15家公司,可以说每5家都是一个阶段,每一个阶段都比前一个阶段总体来说发挥更自如,表现更好。

当然,这可能只适用于我这种短时间内骑驴找马的策略。有朋友喜欢常年在准备,随时可以跳槽的,自然就有不同的策略了。

面试的随机性

有位朋友和我说过,面试的随机性很强,不要太当回事。对于任何一次面试的个体,这是非常有道理的。如果面试挂了,并不代表你不够好,常常也不代表你发挥得不够好。原因是多方面的,有的时候只是在团队文化上不那么契合,有时候只是某一点小的行为表现被错误地放大为一个负面的信号,有时候甚至是被人故意黑了(在北美工作的同学都知道这一点,面试中很难避免)。因此想要在吊死一个选项,非得拿到那家的offer不可,无疑是非常困难而危险的。

另外一点是,特别是在面试的前期,往往没有offer,经验缺乏,甚至面一家挂一家,无疑对自己的心理压力巨大。自我的调整显得举足轻重。但是就像一句老话一样,“道理我都懂,可还是过不好这一生”,有时候尝试去坦然地接纳这些事实,承受这些压力,未见得是件坏事。

最后,我想说的是,坚定地相信,对工程师来说,技术是非常有价值的。尊重自己并且尊重技术,就会有别人尊重你,获得报酬,享受生活,也就能够在职业生涯上继续迈出坚实的步伐。祝愿和我一样近期找工作的朋友们能得到较为理想的结果。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2gN5BJ1

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 经典的第K大问题

经典的第K大问题给一堆数,求第k大的那个。为了避免题意理解方面的歧义,先澄清一下,在这里我们假设和生活中常规的认知一致,有小到大排列,k从1开始,而非0开始,即第一个元素是k=1的元素,第k大就是从小到大排列后排行第k的那个。

这个问题如此之简单而熟悉,可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少,而且还可以不断演进,成为不同复杂程度的问题。

看到这个问题,脑海里的第一反应是一左一右红蓝两条分支——堆排序或者快排。Java中快排用Arrays.sort就可以了,如果是堆排序需要用到PriorityQueue。 用Arrays.sort写起来最简单(这里的参数校验都省掉了):

public int getKth(int[] nums, int k) {
    int[] numsCopy = new int[nums.length];
    System.arraycopy(nums, 0, numsCopy, 0, nums.length);

    Arrays.sort(numsCopy);
    return numsCopy[k - 1];
}

我拷贝了一下数组,以免对原数组做修改。 当然用PriorityQueue写起来不麻烦:

public int getKth(int[] nums, int k) {
    Queue<Integer> heap = new PriorityQueue<>(k);
    for (int i=0; i<nums.length; i++) {
        heap.add(nums[i]);
    }

    int result = 0;
    for (int i=0; i<k; i++)
        result = heap.poll();

    return result;
}

第一个相关问题来了,Arrays.sort是怎么实现的,复杂度到底是多少?

我们可以简单地认为Arrays.sort是n*log(n)的复杂度。事实上Java的实现用的不是普通的快排,而是DualPivotQuicksort,一个优化了的快速排序算法。一般的快排都是使用一个pivot,每个周期把比它小的元素扔左边,比它大的扔右边。但是DualPivotQuicksort使用了两个pivot,这样原来这堆数就分要分成三份了。在当今多数的计算机条件下,CPU计算速度原来越快,而原本被忽略的内存地址访问速度却很难有一样幅度的提高,因而显得越来越举足轻重。因此我们不能只考虑排序过程中单纯的“大小比较”次数,还需要考虑实际“地址访问”(即num[i])的开销。因为CPU的缓存等原因,在不同情形下,实际对地址访问的次数比算法理论上要少。在有意义的实际应用中,DualPivotQuicksort因为能够在多数情况下减少地址访问次数而最终比原始的快速排序更快。

第二个引申问题来了,只从算法的角度考虑,是否还有优化余地呢?

如果我只需要找到第k大,而不关心从1到k-1之间元素的顺序,也不关心从k+1到最大元素之间的顺序,那能不能通过减少这部分的多余比较,来减少一点运算时间开销呢? 其实是可以的。和上面一样,根据堆排序和快排两种思路来梳理优化方法。 先考虑堆排序。我可以修改原来的最小堆实现,由最小堆改为固定堆大小的最大堆。每次放入元素以后检查堆的大小,确保保持在k。

public int getKth(int[] nums, int k) {
    Queue<Integer> heap = new PriorityQueue<>(k);
    for (int i=0; i<nums.length; i++) {
        heap.add(nums[i]);
        if (i > k - 1)
            heap.poll();
    }

    return heap.poll();
}

注意我初始化的时候初始化了一个大小为k的堆,而实际上我维护着的大小是k-1,这其中有一个留了一个大小为1的缓冲,是因为我都是先放进元素,再poll来调整堆的大小。因此引入这个缓冲以避免不必要的堆大小grow。 再考虑快排优化的思路,每个周期内都把比pivot小的往左边扔,比pivot大的往右边扔,而这样操作一次以后,我可以知道pivot在最后序列中的位置。如果正好是k,那皆大欢喜;如果比k大,说明要找的k在这个pivot的左边,那就再k左边继续进行这样的运算;如果比k小,那就再k右边继续这样的运算。简单来说就是包含两步:

  1. search:找pivot的位置,然后根据和k的比较进一步递归pivot的左边或者是右边的子数组;
  2. partition:把小的数扔pivot左边和把大的数扔pivot右边的过程。

细化来说,上述第二步这个和pivot比较并且往左或者往右扔数的逻辑是:

  • 先把当前最左边的那个数选举出来作为pivot(选pivot的办法有很多,这只是最简单的一个办法),这里的pivot变量实际存储的是它的位置(下标),而其值用变量x存储;
  • 然后指针cur往右走,如果发现有比pivot更小的元素,和pivot交换一下,这样操作直到最后;
  • 再把最左边那个数和pivot最终应该呆的位置上的数交换一下,就使得pivot左边的数都小于pivot上的数,pivot右边的数都大于pivot上的数了。
public int getKth(int[] nums, int k) {
    int[] numsCopy = new int[nums.length];
    System.arraycopy(nums, 0, numsCopy, 0, nums.length);

    return search(numsCopy, k - 1, 0, nums.length - 1);
}

private int search(int[] nums, int k, int left, int right) {
    if (left >= right)
        return nums[left];

    int idx = partition(nums, left, right);
    if (idx == k)
        return nums[idx];
    if (idx < k)
        return search(nums, k, idx + 1, right);
    else
        return search(nums, k, left, idx - 1);
}

private int partition(int[] nums, int left, int right) {
    int x = nums[left];
    int pivot = left;
    int cur = left + 1;
    while (cur <= right) {
        if (nums[cur] < x) {
            pivot++;
            swap(nums, pivot, cur);
        }

        cur++;
    }

    swap(nums, left, pivot);

    return pivot;

}

private void swap(int[] nums, int left, int right) {
    if (left == right)
        return;

    nums[left] ^= nums[right];
    nums[right] ^= nums[left];
    nums[left] ^= nums[right];
}

下面再回到最原始的解法,看堆这个分支。如果这堆数很多,但是k很小,那使用堆为了取第k个数,却需要维护一个巨大的堆,多少显得浪费。于是引出了下面这个问题:

能够改进上面堆排序的做法,仅仅维护一个大小为k的堆吗?

上面的做法为什么不行?因为堆,或者说优先级队列,只有一个出口。换言之,这个最小堆只能每次去poll最小值,如果这个堆的大小已经超过了k,我要是想从中去掉一个肯定不需要的最大值,是没有办法做到的。

但是什么队列有两个出口呢?Deque。可是一般的Deque却又不具备堆的特性,那有没有可能将PriorityQueue和Deque结合起来呢?这样我的问题就解决了。如果需要我自己实现,那我可以分别创建一个最大堆和一个最小堆,分别保存堆元素的引用。代码就不贴了,有上面这些基础,这个很容易实现。

不过开源已经有这样的东西了,有不同的实现版本,有的就叫做PriorityDeque;还有一个版本,是大名鼎鼎的Guava实现的,叫做MinMaxPriorityQueue

如果这堆数不是放在一起,而是在若干个数组里呢?

前面说了,如果这堆数只在一个数组里,有两种办法可以排序,如果是在若干个不同的数组里呢?一样可以从快排和堆排序两个思路去分析。

如果利用上面改进后的快排,一种方法是合并成一个大数组快排,另一种方法是给每个数组快排之后都各自取最大的k个,拿出来放到一起继续快排。

但是倘若k相对比较小可以接受而某一个数组太大,而且数组太多(假设下面的nums.length ≥ k),那么堆排序就更有优势,因为不需要合并,堆的大小只和这个k有关,和这些数组本身大小无关。具体做法是,如果每个数组都还无序,就先给每个数组排序,如果数组很大,不需要完全有序,只需要用上面的优化了的方法各自整理出容量为k的最小堆,从而使得每个数组都有一个最小堆相对应,能够不断pull出当时该数组最小的元素。于是这个问题就变成了,如何从若干个size为k的最小堆中,找出第k大的元素:

先定义这样一个元素。其中idx就存放着第几个堆(下标),num为实际存放的数值:

class Item {
    int num;
    int idx;

    public Item(int num, int idx) {
        this.num = num;
        this.idx = idx;
    }
}

再在主方法中,对整体维护一个最小堆heap,每次从这个堆中取出一个元素的时候,要观察这个元素是从哪里来的,如果是从nums[i]来的,就再从nums[i]取一个当时的最小元素补充到这个heap中。

public int getKth(Queue<Integer> nums[], int k) {
    Queue<Item> heap = new PriorityQueue<>(nums.length, (o1, o2) -> o1.num - o2.num);
    for (int i=0; i<k; i++)
        heap.add(new Item(nums[i].poll(), i));

    Item item = null;
    for (int i=0; i<k-1; i++) {
        item = heap.poll();
        heap.add(new Item(nums[item.idx].poll(), item.idx));
    }

    return heap.poll().num;
}

这个方法其实还有一个有趣的推广,就是从一维到二维,甚至更高维。

具体来说,如果拿到若干个数组,从中任意取两个数x和y,要求x+y或者x*y的所有组合里面的第k大。这样的问题还是可以基于堆来解决,当然,首先要给每个数组各自排序。思路是类似的。

继续,如果这些数在不同的机器上(文件里)呢?

我想这也是个经典问题,这个问题都问烂了。数据量如果放在一台机器上不合适,那么很多人都会想到,可以map-reduce啊,每台机器上进行map运算都求出最大的k个,然后汇总到一台机器上去reduce求出最终的第k大(如果机器很多,这个汇总过程可以是多级汇总)。

可是,这个回答无意之中假定了一个条件,让问题变得好处理很多。这个条件就是——k不大。

假如这堆数很多,因此放在若干台机器上,但是如果这个k也非常大呢?即便要想把这k个数放到一台机器上去找也不可行。

这时候问题就有点复杂了,也有不同的处理方法。一种办法是,通过某种排序方法(比如基于不断归并的外排序),给每台机器上的数据都排好序,然后从中找一个(猜一个可能为第k大的数)数作为pivot,并且在每台机器上这些有序数里面都明确这个pivot的位置。假设machine[i]表示第i台机器上,pivot这个数所处的序列,那么把这些machine[i]累加起来,得到的数sum去和k比较:

  • 如果sum==k,那这个第k大的数就找到了;
  • 如果sum<k,说明这个数在每台机器上machine[i]往后,直到结尾的这一段数中;
  • 如果sum>k,说明这个数在每台机器上machine[i]往前,直到开头的这一段数中。

如是递归求解。

当然这个方法依然有许多地方可以改进,比如这个预先进行的外排序,未必要完全进行,是可以通过稳重介绍的理论优化掉或者部分优化掉的。

这个方法改变了思考的角度,原本是从一堆数中去找第k大的数,现在是从中拿出一个数来,去这堆数中找它应该在的位置。

还蛮有趣的。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2ulfFAE

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 分布式系统中唯一ID的生成

分布式系统中唯一ID的生成其实老早就像写一点这个话题。几乎我见过的所有大型系统中,都需要一个唯一ID的生成逻辑。别看小小的ID,需求和场景还挺多:

  • 这个ID多数为数字,但有时候是数字字母的组合;
  • 可能随机,也可能要求随时间严格递增;
  • 有时ID的长度和组成并不重要,有时候却要求它严格遵循规则,或者考虑可读性而要求长度越短越好;
  • 某些系统要求ID可以预期,某些系统却要求ID随机性强,无法猜测(例如避免爬虫等等原因)。

独立的生成服务

比如数据库。最常见的一种,也是应用最多的一种,就是利用数据库的自增长序列。比如Oracle中的sequence的nextVal。有多台application的host,但是只有一个数据库。本质上这是耍了个小赖皮,把某分布式系统唯一ID的生成逻辑寄托到一个特定的数据库上,于是分布式系统存在中心节点了。

这个方法简单,而且可以严格保证单调递增。不过中心化带来的问题众所周知,比如单点故障,比如性能方面的扩展上限。有一种workaround,正如同数据库有主从库一样,可以给不同的数据库设置sequence范围(比如一个是从1~100000000,另一个是从100000001到200000000),或者是设置相同的步长(比如一个是1、3、5、7……另一个是2、4、6、8……),但是互相不重复,从而保证唯一性。不过这样不同sequence生成节点整体内的ID递增性就丢失了。

其它的生成服务也有很多,很多系统中设计的ticket server本质上也就是扮演这样一个角色,特点是这个ID生成服务系统必须独立于现有母系统(客户系统)。但是注意,单点service不代表一定会存在单点故障,单点service一样可以HA。因为这个service也可以是去中心化的。

既然说到这样的service,开源ID生成算法上,最最有名的是Twitter的snowflake,它正是重点考虑到high scale而设计的。64bit长度以下,无需节点间复杂的协作,ID有序。每一条snowflake生成的ID都包含三个部分:timestamp、节点编号,以及一个自增的子序列号。额外地,需要提及其中两个问题的处理:

  • timestamp冲突:timestamp本身是毫秒级的,如果出现冲突,那么其中的自增子序列号会自动+1从而保证生成的ID不会和上一条的冲突。
  • 节点编号的生成:这个其实是从Zookeeper去获取的,也是被诟病说它不够去中心化的原因之一(一个改进方案是Boundary Flake,不需要依赖于这个获取逻辑)。

本地生成器

这个也很常见,局限性也非常明显。通常必须满足这样的要求:在不同的host(分布式节点)之间没有关系保证(比如递增性)。

比如我见过这样的逻辑,用host的唯一编号来作前缀(保证环境中节点编号的唯一性即可),毫秒数来生成ID的主体部分。看似简单,一样可以解决唯一ID的问题。当然它的局限性也很多,如果使用当前毫秒数,无法对于不同host生成的ID进行先后比较(因为无法确保时间是严格一致的);而且只能一个毫秒最多只能生成一个ID,如果要生成两个就会产生冲突。这两个问题当中,对于后者有一个改进方案,就是使用一个AtomicLong来保证冲突情况下的自增序列。

既然提到了AtomicLong,有一些开源项目做到了对AtomicLong的分布式实现。比如Redisson(基于Redis)。但这不属于这里讨论的本地生成器范畴。

还有一种典型是UUID。UUID的全称叫做immutable universally unique identifier,Java中一个UUID代表一个128bit的数。在分布式系统中,它比前面说的方案有更多优势,比如长度一致,比如没有一个毫秒内最多只能生成一个的要求。但是,尽管可以认为它是唯一的,UUID的冲突却是理论上可能存在的。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2s9VEcm

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 React+Redux组合使用之感受

React+Redux组合使用之感受最近完成了一个使用React+Redux组合的项目,以前仅仅是接触了解以及学习,并未正儿八经地使用过,因此这一次可以说是第一次完整地再一个项目当中使用。因而对于认识之浅显请轻拍。

从架构和层次的层面,这个组合给我最好的感受是干净利落的解耦。有不少JavaScript框架尝试解决解耦问题,但是到了落实的层面上很容易出现分层分模块不容易严格控制,缺少清晰标准等问题。但是React+Redux的组合没有这个问题,我们把应用中JavaScript的部分分层为action、client、config、constant、reducer、store、util和view几个部分,其中view又进一步划分成component(不带业务逻辑)和widget(包含业务逻辑)等几个子包。每一个小模块对应有规约路径和命名的scss,在应用中基本上没有出现层次混乱的情况。当然也不尽美,其中一个容易混乱的地方在于传递的数据模型的设计,比如从服务端取回的对象,之后的数据处理可以放在action中,可以放在reducer中,甚至也可以放在view中——这是由(1)“到底想给reducer传递怎样的消息”和(2)“在store中要存储怎样的数据结构”来决定的。这一条标准的理解不同,容易引起不同的代码风格和不同的层次模块划分。

我们有一些新员工初涉JavaScript,我觉得应用React+Redux组合的代码是非常好的“第一个项目”,因为相对来说稍微严格一些的代码控制和清晰的层次模块划分,对于培养良好的设计和代码习惯有着非常大的作用。本来前端的世界里面就是良莠丛生,容易上手但是水又深,相对代码自由度高,而且杂七杂八的风格范型到处都是。培养一个好的习惯在职业生涯中受益无穷。

再吐槽关于view的一切都由store中的状态决定这一点。其实这个初衷非常好,特别利于解耦,view可以划分到很小的模块,只有零零散散几个状态,并且问题定位的时候可以牢牢抓住状态变化这一点。但是凡事有利有弊,在大型项目的时候这一点明显增加了可维护性,但是也明显让项目的代码显得臃肿。基本上每添加一个小小的功能,都要从action->reducer->view等等一层一层写好多代码。如果遇到了一些特殊的情形,比如需要一些动画效果,真可谓杀鸡用牛刀,逻辑繁琐。以前也用过一些其他框架,比如Angular等等,如果从代码量上看,Redux可以说是比较多的,如果你喜欢简洁清晰的代码,不喜欢一大堆js文件,那么你不会喜欢Redux的。

关于JSX。React中JSX可谓是最大的创新了,我本人也非常喜欢这种不同编程范型的融合(命令式代码和声明式代码)。如果有一个好的IDE插件,编码的过程是非常愉悦的。同时,JSX和JS一样,测试非常方便,通常我们把测试用例和源码放在一起,只是每一个测试子包以“_test”命名,这一点非常利于源码和测试代码关联起来阅读。

最后赞一下Redux的devtools,非常好用。结合起一些其他辅助测试的工具,我们现在基本上在开发模式下每当有任何源码的改动,或者UT的改动,改动影响到的UT会在后台自动运行,并且调试页面会自动加载改动的内容,省去了传统模式下build-deploy-refresh的过程。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

via 四火的唠叨 http://ift.tt/2ri1XJY

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share