LeetCode 整理:按难度和类型分类排序(146 / 152)

Featured

=== 十月十五日更 ===

题已刷完,这篇总结还落下不少进度。这个网站本属于个人博客,以后我不想把刷题这种纯找工作的文章发在这里。另外,我回头审视了以前写的一些题解,发现还有不少提升空间,包括对解法的描述和代码的优化。因此我重新做了一个题解网站,也希望能以更加清晰的分类目录和解法帮助读者提升刷题的效率,早点从刷题中走出来,做些更有意思的事。鉴于我需要重新描述大多数题目的解法,新的网站目前只有十来道题,我准备在完成全部题解后再尝试推广,大约在十一月下旬完成。完成后会把这里的题解全部删除。

本篇至此停更。

===

Degree of difficulty from 1~5, 1 is the simplest, 5 is the most difficult.

shuashua
分类有点散漫,有些是交叉的,目前有 General, String, Linked List (LL), Array, Tree, Recursion, Dynamic Programming (DP), Bit Manipulation (Bit). 分类标签在标题后的括号里,也有些只出现一两次的标签。
我会把值得复习的题发出来,链接在相应标题上,没链接的题一般比较简单,或者是我认为不太有用的题。

有一点需要注意,我刚开始做题时觉得多数题偏难,随着熟练度提升,有些题对我变简单了,但我还是会按照最开始的难度标准来分类。
这里有一篇文章可供参考编程面试的10大算法概念
Continue reading

新老姿势交替时的阵痛

三观之中,最容易改变的是价值观。短短一年前,我还很信奉这些:

  • 一天不能吃超过两个鸡蛋,否则胆固醇会超标;
  • 运动超过40分钟才会开始燃烧脂肪;
  • 热身(主要是)要拉韧带;

现在看来,这些是什么鬼啊,都是假的。

回想一下,有多少自己坚持了很久的事情,到最后发现是错的?用数字表示,如果保持现状是1,那么每天一点进步和每天一点退步的差异是巨大的:1.01^365 = 38,0.99^365 = 0.026,难得数字这么贴近实际,却让每一步显得如此残酷。然而,在质变发生之前,有谁能知道自己坚持的方向是正确的呢?我能做的只有不断自省,接收反馈,调整方向,但仍然无可避免要浪费些时间。鲁迅先生说过,「浪费自己的时间等于慢性自杀」,每每回想起虚度的光阴,都感觉受到了成吨的伤害。这些试错用的时间无法挽回,但只要稍加节制,我还是能避开许多堕落的机会。倘若有段时间比较混吃等死,则只有用胡适先生的话来安慰自己,「成功不必在我,而功力必不唐捐」。

做出有益的改变,才能看到新的风景。

辞旧迎新

闲时怀旧。这两天翻了翻以前的不少照片,有些几年来还是第一次看。照片这种东西果然还是得隔很久再看才有感觉,才能体会到变化之大。然而这几年我哪方面变了,自己也说不清。旧事忘得快。再往前,看看高中时写的东西,发现还挺有意思,也许是因为年少时的感情更加纯粹,也更加鲁莽,更加充沛,也更加脆弱。看着这些史料,好像在看另一个人的故事,还略带点熟悉感。人总是在变的,估计过个两三年,这里的几篇文也会变得陌生起来。

曾经喜欢写充满细节的剧本;现在渐渐地走上「船到桥头自然直」的路去了。

2015年的开头是一个三月长的gap,我一直期望有这么一个gap,现在终于来了。可我变了。以前希望用一整块的时间完成某些事,现在看来,这是不现实也没必要的。但总之还是把主线剧情写一写,毕竟预则立不预则废。两面性很容易被遗忘,永远提醒自己辩证地看待每一件事。大二时写过一句话:「你是害怕改变,还是害怕坚持?我都不怕。」四年后我还是不怕。得之我幸,失之我命。

记不住以往,看不清远方,只知道日子不要过得太荒唐,就是有意义。

辞旧迎新,新年快乐。

真实的重构

结束实习后,除了重拾锻炼,什么都不想做,只是在附近和网上游荡。最近无意间看到别人贴伞哥(冰河)的博客,于是点进去看了一下。伞哥又牛逼了很多,他是个奇葩的大牛,编程能力强大的同时,还掌握了跆拳道和各种外语,简直闪闪发光。看到他的经历,我这种小虾米也会更有动力去努力。于是重新订阅了他的博客。

当初不再订阅他的博客,是因为我觉得他这个人很怪,跟公司的关系很差,而且非常自恋。但是看他最近的几篇日志,我觉得之前是自己武断了。伞哥除了智商和意志力异常的高以外,我目前还没发现特别奇怪的地方。他之前表现出的奇怪是被网易的工作氛围衬托出来的,我在了解了一些国内 IT 的工作氛围后,理解了他的选择;至于自恋的问题,我认为这点不影响其他人就可以。加上他养了两只猫,所以这次我回来了,说得准确一点是,我重构了我对他的认识。重构在 IT 行业经常出现,不知道是否广泛被外界使用,这个词的意思是重新构建。

cats

伞哥的猫,点击进入冰河博客原文。

这次态度的转变,让我想到《傲慢与偏见》的一个片段:

pride-and-prejudice-1

pride-and-prejudice-2

pride-and-prejudice-3

pride-and-prejudice-4

女主说「I cannot tease you about that.」其实是充满轻视和戏谑的,因为她不能理解男主的傲慢与偏见,也不愿意去解读他的想法。她有她的傲慢与偏见。她对他的第一印象不好,理所当然地认为这人就是怪胎。当然了,理智的人都知道用第一印象看人属于认知失调,但还是难以控制自己的认知。

第一次看电影时,感觉他们起初是如此的不合拍,最后却走到了一起,其中的转变让我感到困惑。后来又看了一遍,男主角在暴雨时彻底丢掉了他的傲慢,而女主角那时还是充满了偏见。人们不相信你的信念,人们只相信你做的事情,因为你做的事情理应反映出你真实的信念。幸而他还有机会和能力来表现。幸而女主角是个充满魅力的女人。男主角的转变,以及女主角对应的转变,就是整部电影的故事线了,满满的正能量,虽然也充斥着中彩票般的运气。

这种傲慢的态度,其实挺多见,比如贴标签,比如站队,有意或无意不重要,他们表现出来的,都是傲慢与偏见。期望不付出任何努力,就能了解别人或自己是个怎么样的人,即使通过捷径获得的答案 99% 都是错的,他们也不在乎,他们只需要有答案,不关心真实。

从对冰河的评价转变这件事,以及其他很多事情上看,我也曾是一个傲慢的人,相信「My good opinion, once lost, is lost forever」。现在看来,是多么幼稚。我自顾自地认为一个人不可与之交的时候,不知错过了多少美好的东西。这种重构的条件包括放下偏见,沟通,和转变观念,三者都是知易行难,容易被忽视。但有多少重构的机会,我都不愿轻易放过了。

我们都是凡人,成长的道路何其曲折。

[LeetCode] Sqrt(x)

https://oj.leetcode.com/problems/sqrtx/

牛顿法,还是得背下来。。。

 

[LeetCode] Binary Tree Zigzag Level Order Traversal

https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

这题是普通的层次遍历,根据奇偶层数来使用不同顺序输出结果子集,关键是做到代码不啰嗦。

 

[LeetCode] Largest Rectangle in Histogram

这篇写得很好,我就不写了。

http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html

仅作记录于此。本题的关键是在栈中存储单调非递减的高度的下标,如果当前高度比栈中的小,就出栈,更新最大面积,否则压栈。数组最后加一个0,来使代码更简洁。使用 while 循环做。

[LeetCode] Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Continue reading

[LeetCode] Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Continue reading