一个纯正程序员的啰嗦
我觉得去理解数据结构的时候，需要注意到它其实包含两个层面。一个层面是高一级的，从功能、接口的角度去理解，比如说堆，有什么功用，都有怎样的 API；另一个层面是低一级的，从结构和实现的角度去理解，比如堆的实现，可以用数组实现，也可以用单独的节点对象+指针实现。上面一层相同，但是下面一层不同，功能上可能基本一致，但是性能上针对不同的应用场景就可以天差地别。
图就是另外一个典型例子，无向图也好，有向图也好，这是从功能上说的，但它们各自的实现，或者说基于的 “表示方法” 有多种。我记得在学习数据结构早期，基本上没有比较系统地去比较它们，那今天就把这一课补上。
比如上面这个有向图，四个顶点
[……]阅读全文
有这样一个经典的算法题，说是一个单向链表，它内部可能存在环，也可能不存在，用怎样的方法，可以检测出，这个链表是否存在环。下图即是这个形成环的示意，如果单向链表的尾部，指向了链表中的一个节点，而不是指向空，那就构成环了。
接着的一个问题是，怎么检测出这个链表是否有环？
看到这个问题，也许你会觉得，太简单了，但是这个问题只是一个引子。在 《求第 K 个数的问题》一文中，我从简入深，逐步展开，把这 “第 K 个数” 的一系列问题翻了个底朝天。我想关于这个链表成环问题，我也利用类似的思路，看看我是不是也能把这一个问题前前后后讲清楚。
在进一步思考怎样判断这个成环
[……]阅读全文
有时候忽然上下班路上，会去思考一些司空见惯的问题，有一些问题随着思考深入，发现还挺有意思的，就记录在这里。问题之间关联关系不大，有点散。
倒时差的问题
西雅图夏令时和北京时间的时差是 15 个小时，有一个简单的换算方式，就是把当前西雅图时间昼夜颠倒一下（加 12 小时），再加 3 个小时，就得到北京时间了。举例来说，现在是 8 月 16 日晚上的 9 点 37 分，昼夜颠倒一下，就是 8 月 17 日的上午的 9 点 37 分，再加 3 小时，就是 8 月 17 日中午的 12 点 37 分，这就是北京时间。
这几年跑了几次北京和西雅图以后，发现一个规律，就是从北京来到西雅图倒时差非常困难，而从西雅图回到北京倒时差就相对容易得多。我曾经以为是自己心理 [……]阅读全文
从第 416 到第 460 题，跳过了需要付费的题目。付费的题目会单独放在一篇里面。
416
Partition Equal Subset Sum
40.0%
Medium
417
Pacific Atlantic Water Flow
36.9%
Medium
419
Battleships in a Board
65.2%
Medium
420
Strong Password Checker
17.9%
Hard
421
Maximum XOR of Two Numbers in an Array
50.5%
Me[……]阅读全文
372 到 415 题，同级别的题目反正是越来越难。老规矩，跳过了那些付费题目。
372
35.5%
Medium
373
33.3%
Medium
374
38.9%
Easy
375
37.3%
Medium
376
37.0%
Medium[……]阅读全文
一道经典的题目。给一堆乱序的数，如果它们从小到大排好，求第 k 个是多少。假设排列的下标从 1 开始，而非 0 开始。
这个问题如此之简单而熟悉，可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少，而且还可以不断演进，成为不同复杂程度的问题。
关于这个问题的分析和演进，我们不妨从一左一右两条分支——堆排序或者快排，来分别进行。在不断演化问题的时候，会这两个分支之间跳来跳去，为了尽量清晰的考虑，我采用一种新方法——使用 【分支：堆排序】和 【分支：快排】来标注。
Java 中快排用 Arrays.sort 就可以了，如果是堆排序需要用到 PriorityQueue。 用 Array[……]阅读全文
[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[……]阅读全文
只是记录一下遇到的几道抛硬币的概率问题。
1、平均需要抛掷多少次硬币，才会首次出现连续的两个正面？
假设连续两个正面的期望是 E，那么，先看第一次抛硬币：
于是可以得到如下关系式：
E = 0.5(E+1) + 0.25*2 + 0.25(E+2)
得到所求期望 E=6
现在把题目拓展，不是说 “连续两个正面”，而是 “连续 n 个正面” 呢？
这个问题 Matrix67 有非常有趣的解
[……]阅读全文
[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] 如今回头看来，里面很多做法都不是最佳的，有的从复杂度上根本就不是最优解，有的写的太啰嗦，有的则用了一些过于 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.
一组整数，除了一个只出现一次以外，其他每个整数都恰好出现三次，要寻找那个特殊的整数。
似曾相识
首先，它让我想起了另外一道类似的题目，如果把上面的“ 恰好三次”，改成“ 恰好两次”，寻找那个特殊的整数，又该怎么解？
那样的话，我希望找到一个方法，让两个相同的数进行运算以后，能够泯灭掉，这样所有的数进行运算
[……]阅读全文
