一道经典的题目。给一堆乱序的数，如果它们从小到大排好，求第k个是多少。假设排列的下标从1开始，而非0开始。
这个问题如此之简单而熟悉，可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少，而且还可以不断演进，成为不同复杂程度的问题。
看到这个问题，脑海里的第一反应是一左一右红蓝两条分支——堆排序或者快排。Java中快排用Arrays.sort就可以了，如果是堆排序需[......]阅读全文
Archive for Algorithm & Data Structure
19
一 2017
LeetCode题目解答——第311到371题
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
老规矩，跳过需要付费的题目。题目是越来越不好做，我尽量把自己的思路写下来。
371
51.9%
Easy
36[......]阅读全文
四火 |
2 comments
| Tags: LeetCode
16
十二 2015
LeetCode题目解答——第227到310题
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
LeetCode的题目是不断在更新。还是老规矩，跳过了那些需要付费才能做的题目。下面的解法可能不是最好的，具体问题我们可以讨论。截至目前我解答的全部的LeetCode放在了这里。[......]阅读全文
四火 |
One comment
| Tags: LeetCode
18
六 2015
LeetCode题目解答——155~226题
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
LeetCode上面的题目更新很快，而且题目是越来越不好做了。我把最新的155到226题目的思考和解答过程放在下面，解法有好有坏，有问题我们可以讨论。老规矩，有一些题目是要买一个特定的[......]阅读全文
四火 |
One comment
| Tags: LeetCode
01
六 2015
建立动态规划状态转移方程的练习
大学里面算法课老师教导过动态规划，但是就像看书要把书看厚再看薄一样，要把动态规划彻底理解，还是需要一些时间的锻炼。解动态规划问题，每个人都有自己的习惯的套路，我的理解是最核心的过程有两部，一个是找出问题的一个一个子“状态”，再一个就是建立“状态转移方程”（就是所谓的“递推关系式”）。把这个过程搞定，基本上动态规划的题目就解
[......]阅读全文
四火 |
No comments
| Tags: 动态规划
13
三 2015
一道随机数题目的求解
有这样一道算法题：
给定一个能够生成均匀1~5随机枚举数的函数，请设计一个能够生成均匀1~7随机枚举数的函数。
就是说，有一个生成随机数的函数rand5，可能返回1、2、3、4、5这5个枚举值，其中每个值被返回的概率都是严格的1/5，现在需要设计一个类似的随机数函数rand7，可能返回1、2、3、4、5、6、7这几个枚举值，每个值被返回的概率都是严格的1/7。
先掩卷思考，脑海中
[......]阅读全文
14
二 2015
Java容器类型复习笔记
19
一 2015
LeetCode算法题目解答汇总
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。请读者知道这一点。
只要不是特别忙或者特别不方便，最近一直保持着每天做几道算法题的规律，到后来随着难度的增加，每天做的题目越来越少。我的初衷就是练习，因为一方面我本身算法基础并不[......]阅读全文
四火 |
One comment
| Tags: LeetCode
18
一 2015
LeetCode题目解答——Hard部分
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
以下是LeetCode题目解答的最后一部分：Hard部分。
Text Justification
14.0%
Hard
Search in Rotated[......]阅读全文
四火 |
3 comments
| Tags: LeetCode
23
十二 2014
LeetCode题目解答——Medium部分（下）
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
这是LeetCode题目Medium难度部分中的下半部分，表格中的Acceptance是LeetCode网上拷贝下来的的数据。这些完成以后，就只剩Hard部分了。欢迎讨论。[......]阅读全文
四火 |
No comments
| Tags: LeetCode
21
十一 2014
LeetCode题目解答——Medium部分（上）
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
以下是LeetCode题目中Medium部分的上半部分，点击表格中的名称进入题目和解答。我计划把LeetCode我的解答分成四个部分发上来，这是第二部分。做这些题目收获还是挺大的。[......]阅读全文
四火 |
3 comments
| Tags: LeetCode
03
十一 2014
LeetCode题目解答——Easy部分
[Updated on 9/22/2017] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于tricky的方法。我没有为了这个再更新，就让它们去吧。
LeetCode最近很火，我以前不太知道有这么一个很方便练习算法的网站，直到大概数周前同事和我说起，正好我老婆要找工作，而根据同事的理论，LeetCode的题目是必须攻破的第一道关卡[......]阅读全文
四火 |
9 comments
| Tags: LeetCode
01
十 2014
一道位运算的算法题
最近遇到这样一道算法题：
Given an array of integers, every element appears three times except for one. Find that single one.
一组整数，除了一个只出现一次以外，其他每个整数都恰好出现三次，要寻找那个特殊的整数。
似曾相识
首先，它让我想起了另外一道类似的题目，如果把上面的&ld
[......]阅读全文
四火 |
6 comments
| Tags: 位运算
22
十二 2013
排序算法一览（下）：归并类、分布类和混合类排序
上半部分请参见《排序算法一览（上）：交换类、选择类和插入类排序》。
归并类排序
归并排序（Merge Sort）
归并排序是一种分治法，它反复将两个已经排序的序列合并成一个序列（平均时间复杂度O(nlogn)，最好时间复杂度O(n)）：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，
[......]阅读全文
四火 |
No comments
| Tags: 排序
15
十二 2013
排序算法一览（上）：交换类、选择类和插入类排序
最近在复习常用排序算法发现了下面这个罪恶的排序方法列表页面，我被那些有趣的排序方法诱惑了，就把上面介绍的各种排序方法都整理了一遍（我觉得维基百科比其它我看过的算法书都要易懂一些），前半部分可以说还乐在其中，后半部分就有些厌烦了，不过最后总算是坚持看完了。以下是第一部分，包括交换类排序、选择类排序和插入类排序。
- 交换类排序 - 冒泡排序 鸡尾酒排序 奇偶排序 梳子排序 侏儒排序 快速排序 臭皮匠
[......]阅读全文
四火 |
No comments
| Tags: 排序
10
十二 2013
Trie树和其它数据结构的比较
28
十一 2013
给我一把榔头，满世界都是钉子
一篇文章存成一个巨大的文件，总共大约有一亿个单词，要找出里面重复次数最多的。怎么做？
Hadoop是一把威力巨大的榔头，在使用过Hadoop之后，看着任何东西都想把它给map reduce了。有一个关于Jeff Dean的小笑话，说在睡不着觉的时候，一般人是数羊，Jeff Dean是map reduce他的羊群。所以，我的办法是，把这个文件拆分成若干个小文件，在map过程用hash算法保证相同的
[......]阅读全文
03
十 2013
换个角度思考问题
19
五 2013
再谈大楼扔鸡蛋的问题
这道题是说，100层楼，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论过这个问题的解法，因为只想记录一下思路和讨论过程，写得很简略。现在，我想重新整理一下这个问题，再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述，把这个问题的前后说清楚。
现在只有两个鸡蛋，而算法必须在各种合法输入下都是可行的，就是说要能找出这一层来，你得假设你的运
[......]阅读全文
17
二 2012
