LeetCode 300题以内需要付费才能查看的所有题目解答。
156
157
158
159
161
163
[……]阅读全文
分类：Algorithm & Data Structure
求第K个数的问题
一道经典的题目。给一堆乱序的数，如果它们从小到大排好，求第k个是多少。假设排列的下标从1开始，而非0开始。
这个问题如此之简单而熟悉，可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少，而且还可以不断演进，成为不同复杂程度的问题。
看到这个问题，脑海里的第一反应是一左一右红蓝两条分支——堆排序或者快排。Java中快排用Arrays.sort就可以了，如果是堆排序需要用到PriorityQueue。 用Arrays.sort写起来最简单（这里的参数校验都省掉了）：
public int getKth(int[] nums, int k) {
int[
[……]阅读全文
LeetCode题目解答——第311到371题
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
老规矩，跳过需要付费的题目。题目是越来越不好做，我尽量把自己的思路写下来。
371
51.9%
Easy
368
31.9%
Medium
367
36.9%
Medium
36[……]阅读全文
LeetCode题目解答——第227到310题
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
LeetCode的题目是不断在更新。还是老规矩，跳过了那些需要付费才能做的题目。下面的解法可能不是最好的，具体问题我们可以讨论。截至目前我解答的全部的LeetCode放在了这里。
310
Minimum Height Trees
24.0%
Medium[……]阅读全文
LeetCode题目解答——155~226题
[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。
先掩卷思考，脑海中浮现的思路包括：
- 调用rand5的结果除以5，再乘以7，这样的结果范围为7/5~7，并非所希望的结果；
- 反复调用rand5函数7次，结果再除以5，这样的结果范围为也为7/5 ~ 7，并非所
[……]阅读全文
Java容器类型复习笔记
最近抽空把java.lang下面常用的那些容器类型（数据结构）复习了一下，这些东西是基础，平时使用的时候也可以很容易查得到，有些方法大概知道，但是总是弄混，如果可以记住那些重要方法，并且能够熟练使用的话，还是可以让编码过程变得容易很多。另外一个是实现机制，对于常用数据结构的实现机制，应该说是必须要熟知的。
另外，并发容器我之前整理过，放在这篇文章里。
Queue
- add和offer的区别在于达到上限时add抛出异常，offer返回false；
- remove和poll的区别在于，队列为空时前者抛出异常，后者返回空；
- element和peek都返回队列头部元素，但是前者失败不抛出异常，后者返回
[……]阅读全文
LeetCode算法题目解答汇总
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。请读者知道这一点。
只要不是特别忙或者特别不方便，最近一直保持着每天做几道算法题的规律，到后来随着难度的增加，每天做的题目越来越少。我的初衷就是练习，因为一方面我本身算法基础并不好，再一方面是因为工作以后传统意义上所谓算法的东西接触还是太少。为了题目查找方便起见，我把之前几篇陆陆续续贴出来的我对LeetCode上面算法题的解答汇总在下面，CTRL+F就可以比较方便地找到。由于[……]阅读全文
LeetCode题目解答——Hard部分
[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
LeetCode题目解答——Medium部分（下）
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
这是LeetCode题目Medium难度部分中的下半部分，表格中的Acceptance是LeetCode网上拷贝下来的的数据。这些完成以后，就只剩Hard部分了。欢迎讨论。
Multiply Strings
20.5%
Medium
LeetCode题目解答——Medium部分（上）
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
以下是LeetCode题目中Medium部分的上半部分，点击表格中的名称进入题目和解答。我计划把LeetCode我的解答分成四个部分发上来，这是第二部分。做这些题目收获还是挺大的。
Divide Two Integers
16.6%
Medium
LeetCode题目解答——Easy部分
[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
[……]阅读全文
排序算法一览（上）：交换类、选择类和插入类排序
最近在复习常用排序算法发现了下面这个罪恶的排序方法列表页面，我被那些有趣的排序方法诱惑了，就把上面介绍的各种排序方法都整理了一遍（我觉得维基百科比其它我看过的算法书都要易懂一些），前半部分可以说还乐在其中，后半部分就有些厌烦了，不过最后总算是坚持看完了。以下是第一部分，包括交换类排序、选择类排序和插入类排序。
- 交换类排序 – 冒泡排序 鸡尾酒排序 奇偶排序 梳子排序 侏儒排序 快速排序 臭皮匠排序 Bogo排序
- 选择类排序 – 选择排序 堆排序 Smooth排序 笛卡尔树排序 锦标赛排序 圈排序
- 插入类排序 – 插入排序 希尔排序 二叉查找树排序 图书馆排序 耐心排序
- 归并类排序 – 归并
[……]阅读全文
Trie树和其它数据结构的比较
Trie树，又叫做前缀树或者是字典树，是一种有序的树。从空字符串的根开始，往下遍历到某个节点，确定了对应的字符串，也就是说，任意一个节点的所有子孙都具备相同的前缀。每一棵Trie树都可以被看做是一个简单版的确定有限状态的自动机（DFA，deterministic finite automaton），也就是说，对于一个任意给定的属于该自动机的状态(①)和一个属于该自动机字母表的字符(②)，都可以根据给定的转移函数(③)转到下一个状态去。其中：
- ① 对于Trie树中的每一个节点都确定了一个自动机的状态；
- ② 给定一个属于该自动机字母表的字符，在图中可以看到根据不同的字符形成的分支；
[……]阅读全文
给我一把榔头，满世界都是钉子
一篇文章存成一个巨大的文件，总共大约有一亿个单词，要找出里面重复次数最多的。怎么做？
Hadoop是一把威力巨大的榔头，在使用过Hadoop之后，看着任何东西都想把它给map reduce了。有一个关于Jeff Dean的小笑话，说在睡不着觉的时候，一般人是数羊，Jeff Dean是map reduce他的羊群。所以，我的办法是，把这个文件拆分成若干个小文件，在map过程用hash算法保证相同的单词落入一个文件（这点很重要），计算单词出现次数，在reduce过程取得重复次数最多的单词来。
但是，真有必要这样啰嗦吗？
只有一亿个单词，简单估算一下，一个字母占据两个字节，假设单词平均长度5，即便
[……]阅读全文
换个角度思考问题
最近在看一本书，叫做《思考的乐趣》，第26节“我最爱的证明”，里面介绍了这样一则有趣的问题（文章链接在此）：
设想一个平面上布满间距为1的横纵直线，形成由一个个1×1正方形组成的网格。任意给一个面积小于1个单位的图形，证明这个图形总能放在网格中而不包含任何一个格点。
初看这个论断，觉得似乎是正确的，但又不知从何下手。文中指出证明的思路很巧妙，让人感到数学的美妙。我的感触是，文中的证明大大地换了个角度，很有峰回路转的感觉。正在读这篇文章的你，不妨先思考一下，别急着往下看答案。
如果陷入了拼命去构造各种各样的图形类别，去思考不同类别图形的情况下，怎么去摆放这样的图形，使得图形不覆
[……]阅读全文
再谈大楼扔鸡蛋的问题
这道题是说，100层楼，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论过这个问题的解法，因为只想记录一下思路和讨论过程，写得很简略。现在，我想重新整理一下这个问题，再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述，把这个问题的前后说清楚。
现在只有两个鸡蛋，而算法必须在各种合法输入下都是可行的，就是说要能找出这一层来，你得假设你的运气最差，这就意味着，我求解的是在每种扔鸡蛋的策略下都有一个需要扔的次数的最大值，而现在需要求解的是这些最大值中的最小值的问题。如果我只有一枚鸡蛋，这就意味着，我只能从第一层开始老老实实地一层一层往上试
[……]阅读全文
