LeetCode 题目解答—— 第 416 到 460 题

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

LeetCode 题目解答—— 第 372 到 415 题

372 到 415 题,同级别的题目反正是越来越难。老规矩,跳过了那些付费题目。

372

35.5%
Medium

373

33.3%
Medium

374

38.9%
Easy

375

37.3%
Medium

376

37.0%
Medium[……] 阅读全文

LeetCode 付费题目(一)

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

156

157

158

159

161

163

[……]阅读全文

求第 K 个数的问题

一道经典的题目。给一堆乱序的数,如果它们从小到大排好,求第 k 个是多少。假设排列的下标从 1 开始,而非 0 开始。

这个问题如此之简单而熟悉,可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少,而且还可以不断演进,成为不同复杂程度的问题。

关于这个问题的分析和演进,我们不妨从一左一右两条分支——堆排序或者快排,来分别进行。在不断演化问题的时候,会这两个分支之间跳来跳去,为了尽量清晰的考虑,我采用一种新方法——使用 【分支:堆排序】【分支:快排】 来标注。

Java 中快排用 Arrays.sort 就可以了,如果是堆排序需要用到 PriorityQueue。 用 Array[……]阅读全文

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

几道抛硬币问题

coin toss

只是记录一下遇到的几道抛硬币的概率问题。

 

1、平均需要抛掷多少次硬币,才会首次出现连续的两个正面?

假设连续两个正面的期望是 E,那么,先看第一次抛硬币:

  1. 如果抛到反面,那么还期望抛 E 次,因为抛到反面完全没用,总数就期望抛 E+1
  2. 如果抛到正面,那么要看下一次,如果下一次也是正面,那抛硬币就结束了,总数是 2;如果下一次是反面,那么相当于重头来过,总数就期望抛 E+2

于是可以得到如下关系式:

E = 0.5(E+1) + 0.25*2 + 0.25(E+2)

得到所求期望 E=6

现在把题目拓展,不是说“连续两个正面”,而是“连续 n 个正面”呢?

这个问题 Matrix67 有非常有趣的解

[……]阅读全文

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] 如今回头看来,里面很多 [……]阅读全文

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 树中的每一个节点都确定了一个自动机的状态;
  • ② 给定一个属于该自动机字母表的字符,在图中可以看到根据不同的字符形成的分支;

[……]阅读全文

back to top