LeetCode 付费题目(一)

LeetCode 300 题以内需要付费才能查看的所有题目解答。

156

157

158

159

161

163

[……]阅读全文

求第 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[……]阅读全文

建立动态规划状态转移方程的练习

algorithm

大学里面算法课老师教导过动态规划,但是就像看书要把书看厚再看薄一样,要把动态规划彻底理解,还是需要一些时间的锻炼。解动态规划问题,每个人都有自己的习惯的套路,我的理解是最核心的过程有两部,一个是找出问题的一个一个子“ 状态”,再一个就是建立“ 状态转移方程”(就是所谓的“ 递推关系式”)。把这个过程搞定,基本上动态规划的题目就解了一半了,剩下那些代码层面的事情,是把思路和数学方程实现而已了。

在实现的过程中,可能会用到一些技巧,比如“ 循环还是递归”,这只是实现的办法而已,不是动态规划的本质;再比如空

[……]阅读全文

一道随机数题目的求解

random 有这样一道算法题:

给定一个能够生成均匀 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 容器类型复习笔记

data_structures 最近抽空把 java.lang 下面常用的那些容器类型(数据结构)复习了一下,这些东西是基础,平时使用的时候也可以很容易查得到,有些方法大概知道,但是总是弄混,如果可以记住那些重要方法,并且能够熟练使用的话,还是可以让编码过程变得容易很多。另外一个是实现机制,对于常用数据结构的实现机制,应该说是必须要熟知的。

另外,并发容器我之前整理过,放在 这篇文章 里。

Queue

  1. add 和 offer 的区别在于达到上限时 add 抛出异常,offer 返回 false;
  2. remove 和 poll 的区别在于,队列为空时前者抛出异常,后者返回空;
  3. element 和 peek 都返回队列头部元素,但是前者失败不抛出异常,后者返回

[……]阅读全文

LeetCode 算法题目解答汇总

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

Reverse Nodes in k-Gro[……]阅读全文

LeetCode 题目解答——Medium 部分(下)

[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。

这是 LeetCode 题目 Medium 难度部分中的下半部分,表格中的 Acceptance 是 LeetCode 网上拷贝下来的的数据。这些完成以后,就只剩 Hard 部分了。欢迎讨论。

Multiply Strings
20.5%
Medium

Sum Root to Leaf[……]阅读全文

LeetCode 题目解答——Medium 部分(上)

[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。

以下是 LeetCode 题目中 Medium 部分的上半部分,点击表格中的名称进入题目和解答。我计划把 LeetCode 我的解答分成四个部分发上来,这是第二部分。做这些题目收获还是挺大的。

Divide Two Integers
16.6%
Medium

3Sum
16.[……] 阅读全文

LeetCode 题目解答——Easy 部分

alg [Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。

LeetCode 最近很火,我以前不太知道有这么一个很方便练习算法的网站,直到大概数周前同事和我说起,正好我老婆要找工作,而根据同事的理论,LeetCode 的题目是必须攻破的第一道关卡。我虽说又不找工作,但是纯粹拿来练手和学习,觉得很多题目都挺有趣的。现在已经做了三分之一,我会把我的解答分几次放上来。这里是第一部分,难度为 easy 的题目。

我觉得做这样的题目很有帮助,但也要有 [……] 阅读全文

一道位运算的算法题

programmer

最近遇到这样一道算法题:

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

[……]阅读全文

排序算法一览(上):交换类、选择类和插入类排序

sort

最近在复习常用排序算法发现了下面这个罪恶的排序方法列表页面,我被那些有趣的排序方法诱惑了,就把上面介绍的各种排序方法都整理了一遍(我觉得维基百科比其它我看过的算法书都要易懂一些),前半部分可以说还乐在其中,后半部分就有些厌烦了,不过最后总算是坚持看完了。以下是第一部分,包括交换类排序、选择类排序和插入类排序。
  • 交换类排序 –  冒泡排序  鸡尾酒排序 奇偶排序 梳子排序 侏儒排序  快速排序  臭皮匠排序 Bogo 排序
  • 选择类排序 –  选择排序   堆排序  Smooth 排序 笛卡尔树排序 锦标赛排序 圈排序
  • 插入类排序 –  插入排序   希尔排序  二叉查找树排序 图书馆排序 耐心排序
  • 归并类排序 –  归并

[……]阅读全文

Trie 树和其它数据结构的比较

trie

Trie 树 ,又叫做前缀树或者是字典树,是一种有序的树。从空字符串的根开始,往下遍历到某个节点,确定了对应的字符串,也就是说,任意一个节点的所有子孙都具备相同的前缀。每一棵 Trie 树都可以被看做是一个简单版的确定有限状态的自动机(DFA,deterministic finite automaton),也就是说,对于一个任意给定的属于该自动机的状态 (①) 和一个属于该自动机字母表的字符 (②),都可以根据给定的转移函数 (③) 转到下一个状态去。其中:

  • ① 对于 Trie 树中的每一个节点都确定了一个自动机的状态;
  • ② 给定一个属于该自动机字母表的字符,在图中可以看到根据不同的字符形成的分支;

[……]阅读全文

给我一把榔头,满世界都是钉子

hammer 一篇文章存成一个巨大的文件,总共大约有一亿个单词,要找出里面重复次数最多的。怎么做?

Hadoop 是一把威力巨大的榔头,在使用过 Hadoop 之后,看着任何东西都想把它给 map reduce 了。有一个关于 Jeff Dean 的小笑话,说在睡不着觉的时候,一般人是数羊,Jeff Dean 是 map reduce 他的羊群。所以,我的办法是,把这个文件拆分成若干个小文件,在 map 过程用 hash 算法保证相同的单词落入一个文件(这点很重要),计算单词出现次数,在 reduce 过程取得重复次数最多的单词来。

但是,真有必要这样啰嗦吗?

只有一亿个单词,简单估算一下,一个字母占据两个字节,假设单词平均长度 5,即便

[……]阅读全文

换个角度思考问题

think最近在看一本书,叫做 《思考的乐趣》,第 26 节“我最爱的证明”,里面介绍了这样一则有趣的问题(文章 链接在此):

设想一个平面上布满间距为 1 的横纵直线,形成由一个个 1×1 正方形组成的网格。任意给一个面积小于 1 个单位的图形,证明这个图形总能放在网格中而不包含任何一个格点。

example

初看这个论断,觉得似乎是正确的,但又不知从何下手。文中指出证明的思路很巧妙,让人感到数学的美妙。我的感触是,文中的证明大大地换了个角度,很有峰回路转的感觉。正在读这篇文章的你,不妨先思考一下,别急着往下看答案。

如果陷入了拼命去构造各种各样的图形类别,去思考不同类别图形的情况下,怎么去摆放这样的图形,使得图形不覆

[……]阅读全文

再谈大楼扔鸡蛋的问题

egg 这道题是说,100 层楼,两个一模一样的鸡蛋,某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在 去年初的这篇文章里面讨论过这个问题的解法 ,因为只想记录一下思路和讨论过程,写得很简略。现在,我想重新整理一下这个问题,再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述,把这个问题的前后说清楚。

现在只有两个鸡蛋,而算法必须在各种合法输入下都是可行的,就是说要能找出这一层来,你得假设你的运气最差,这就意味着,我求解的是在每种扔鸡蛋的策略下都有一个需要扔的次数的最大值,而现在需要求解的是这些最大值中的最小值的问题。如果我只有一枚鸡蛋,这就意味着,我只能从第一层开始老老实实地一层一层往上试

[……]阅读全文

back to top