LeetCode 300 题以内需要付费才能查看的所有题目解答。
156
157
158
159
161
163
[……]阅读全文
一个纯正程序员的啰嗦
一道经典的题目。给一堆乱序的数,如果它们从小到大排好,求第 k 个是多少。假设排列的下标从 1 开始,而非 0 开始。
这个问题如此之简单而熟悉,可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少,而且还可以不断演进,成为不同复杂程度的问题。
看到这个问题,脑海里的第一反应是一左一右红蓝两条分支——堆排序或者快排。Java 中快排用 Arrays.sort 就可以了,如果是堆排序需要用到 PriorityQueue。 用 Arrays.sort 写起来最简单(这里的参数校验都省掉了):
public int getKth(int[] nums, int k) { int[
[……]阅读全文
[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。
老规矩,跳过需要付费的题目。题目是越来越不好做,我尽量把自己的思路写下来。
371
51.9%
Easy
368
31.9%
Medium
367
36.9%
Medium
36[……]阅读全文
[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。
LeetCode 的题目是不断在更新。还是老规矩,跳过了那些需要付费才能做的题目。下面的解法可能不是最好的,具体问题我们可以讨论。截至目前我解答的全部的 LeetCode 放在了 这里 。
310
Minimum Height Trees
24.0%
Medium[……] 阅读全文
[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。
LeetCode 上面的题目更新很快,而且题目是越来越不好做了。我把最新的 155 到 226 题目的思考和解答过程放在下面,解法有好有坏,有问题我们可以讨论。老规矩,有一些题目是要买一个特定的电子书才可以在线做题的,我就跳过去了。
226
Invert Binary Tree[……]阅读全文
大学里面算法课老师教导过动态规划,但是就像看书要把书看厚再看薄一样,要把动态规划彻底理解,还是需要一些时间的锻炼。解动态规划问题,每个人都有自己的习惯的套路,我的理解是最核心的过程有两部,一个是找出问题的一个一个子“ 状态”,再一个就是建立“ 状态转移方程”(就是所谓的“ 递推关系式”)。把这个过程搞定,基本上动态规划的题目就解了一半了,剩下那些代码层面的事情,是把思路和数学方程实现而已了。
在实现的过程中,可能会用到一些技巧,比如“ 循环还是递归”,这只是实现的办法而已,不是动态规划的本质;再比如空
[……]阅读全文
给定一个能够生成均匀 1~5 随机枚举数的函数,请设计一个能够生成均匀 1~7 随机枚举数的函数。
就是说,有一个生成随机数的函数 rand5,可能返回 1、2、3、4、5 这 5 个枚举值,其中每个值被返回的概率都是严格的 1/5,现在需要设计一个类似的随机数函数 rand7,可能返回 1、2、3、4、5、6、7 这几个枚举值,每个值被返回的概率都是严格的 1/7。
先掩卷思考,脑海中浮现的思路包括:
[……]阅读全文
最近抽空把 java.lang 下面常用的那些容器类型(数据结构)复习了一下,这些东西是基础,平时使用的时候也可以很容易查得到,有些方法大概知道,但是总是弄混,如果可以记住那些重要方法,并且能够熟练使用的话,还是可以让编码过程变得容易很多。另外一个是实现机制,对于常用数据结构的实现机制,应该说是必须要熟知的。
另外,并发容器我之前整理过,放在 这篇文章 里。
Queue
[……]阅读全文
[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,[……]阅读全文
[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。
以下是 LeetCode 题目解答的最后一部分:Hard 部分。
Text Justification
14.0%
Hard
Search in Rotated Sorted Array
28.6%
Hard
Binary Tree Maximum Path Sum
20.2%
Hard
[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。
这是 LeetCode 题目 Medium 难度部分中的下半部分,表格中的 Acceptance 是 LeetCode 网上拷贝下来的的数据。这些完成以后,就只剩 Hard 部分了。欢迎讨论。
Multiply Strings
20.5%
Medium
[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。
以下是 LeetCode 题目中 Medium 部分的上半部分,点击表格中的名称进入题目和解答。我计划把 LeetCode 我的解答分成四个部分发上来,这是第二部分。做这些题目收获还是挺大的。
Divide Two Integers
16.6%
Medium
[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。
LeetCode 最近很火,我以前不太知道有这么一个很方便练习算法的网站,直到大概数周前同事和我说起,正好我老婆要找工作,而根据同事的理论,LeetCode 的题目是必须攻破的第一道关卡。我虽说又不找工作,但是纯粹拿来练手和学习,觉得很多题目都挺有趣的。现在已经做了三分之一,我会把我的解答分几次放上来。这里是第一部分,难度为 easy 的题目。
我觉得做这样的题目很有帮助,但也要有 [……] 阅读全文
最近遇到这样一道算法题:
Given an array of integers, every element appears three times except for one. Find that single one.
一组整数,除了一个只出现一次以外,其他每个整数都恰好出现三次,要寻找那个特殊的整数。
似曾相识
首先,它让我想起了另外一道类似的题目,如果把上面的“ 恰好三次”,改成“ 恰好两次”,寻找那个特殊的整数,又该怎么解?
那样的话,我希望找到一个方法,让两个相同的数进行运算以后,能够泯灭掉,这样所有的数进行运算
[……]阅读全文
上半部分请参见 《排序算法一览(上):交换类、选择类和插入类排序》。
归并类排序
归并排序(Merge Sort)
归并排序是一种分治法,它反复将两个已经排序的序列合并成一个序列(平均时间复杂度 O(nlogn),最好时间复杂度 O(n)):
public class Sort { public s
[……]阅读全文
[……]阅读全文
Trie 树 ,又叫做前缀树或者是字典树,是一种有序的树。从空字符串的根开始,往下遍历到某个节点,确定了对应的字符串,也就是说,任意一个节点的所有子孙都具备相同的前缀。每一棵 Trie 树都可以被看做是一个简单版的确定有限状态的自动机(DFA,deterministic finite automaton),也就是说,对于一个任意给定的属于该自动机的状态 (①) 和一个属于该自动机字母表的字符 (②),都可以根据给定的转移函数 (③) 转到下一个状态去。其中:
[……]阅读全文
一篇文章存成一个巨大的文件,总共大约有一亿个单词,要找出里面重复次数最多的。怎么做?
Hadoop 是一把威力巨大的榔头,在使用过 Hadoop 之后,看着任何东西都想把它给 map reduce 了。有一个关于 Jeff Dean 的小笑话,说在睡不着觉的时候,一般人是数羊,Jeff Dean 是 map reduce 他的羊群。所以,我的办法是,把这个文件拆分成若干个小文件,在 map 过程用 hash 算法保证相同的单词落入一个文件(这点很重要),计算单词出现次数,在 reduce 过程取得重复次数最多的单词来。
但是,真有必要这样啰嗦吗?
只有一亿个单词,简单估算一下,一个字母占据两个字节,假设单词平均长度 5,即便
[……]阅读全文
最近在看一本书,叫做 《思考的乐趣》,第 26 节“我最爱的证明”,里面介绍了这样一则有趣的问题(文章 链接在此):
设想一个平面上布满间距为 1 的横纵直线,形成由一个个 1×1 正方形组成的网格。任意给一个面积小于 1 个单位的图形,证明这个图形总能放在网格中而不包含任何一个格点。
初看这个论断,觉得似乎是正确的,但又不知从何下手。文中指出证明的思路很巧妙,让人感到数学的美妙。我的感触是,文中的证明大大地换了个角度,很有峰回路转的感觉。正在读这篇文章的你,不妨先思考一下,别急着往下看答案。
如果陷入了拼命去构造各种各样的图形类别,去思考不同类别图形的情况下,怎么去摆放这样的图形,使得图形不覆
[……]阅读全文
这道题是说,100 层楼,两个一模一样的鸡蛋,某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在 去年初的这篇文章里面讨论过这个问题的解法 ,因为只想记录一下思路和讨论过程,写得很简略。现在,我想重新整理一下这个问题,再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述,把这个问题的前后说清楚。
现在只有两个鸡蛋,而算法必须在各种合法输入下都是可行的,就是说要能找出这一层来,你得假设你的运气最差,这就意味着,我求解的是在每种扔鸡蛋的策略下都有一个需要扔的次数的最大值,而现在需要求解的是这些最大值中的最小值的问题。如果我只有一枚鸡蛋,这就意味着,我只能从第一层开始老老实实地一层一层往上试
[……]阅读全文