Archive for Algorithm & Data Structure

LeetCode题目解答——第227到310题

LeetCode的题目是不断在更新。还是老规矩,跳过了那些需要付费才能做的题目。下面的解法可能不是最好的,具体问题我们可以讨论。截至目前我解答的全部的LeetCode放在了这里

310
Minimum Height Trees
24.0%
Medium

309
Best Time to Buy and Sell[......]阅读全文

分享到:

LeetCode题目解答——155~226题

LeetCode上面的题目更新很快,而且题目是越来越不好做了。我把最新的155到226题目的思考和解答过程放在下面,解法有好有坏,有问题我们可以讨论。老规矩,有一些题目是要买一个特定的电子书才可以在线做题的,我就跳过去了。

226
Invert Binary Tree
37.6%
Easy

225
Implemen[......]阅读全文

分享到:

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

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

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

[......]阅读全文

分享到:

一道随机数题目的求解

一道随机数题目的求解 有这样一道算法题:

给定一个能够生成均匀1~5随机枚举数的函数,请设计一个能够生成均匀1~7随机枚举数的函数。

就是说,有一个生成随机数的函数rand5,可能返回1、2、3、4、5这5个枚举值,其中每个值被返回的概率都是严格的1/5,现在需要设计一个类似的随机数函数rand7,可能返回1、2、3、4、5、6、7这几个枚举值,每个值被返回的概率都是严格的1/7。

先掩卷思考,脑海中

[......]阅读全文

分享到:

Java容器类型复习笔记

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

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

Queue

  1. add和offer的区别在于达

[......]阅读全文

分享到:

LeetCode算法题目解答汇总

LeetCode算法题目解答汇总

只要不是特别忙或者特别不方便,最近一直保持着每天做几道算法题的规律,到后来随着难度的增加,每天做的题目越来越少。我的初衷就是练习,因为一方面我本身算法基础并不好,再一方面是因为工作以后传统意义上所谓算法的东西接触还是太少。为了题目查找方便起见,我把之前几篇陆陆续续贴出来的我对LeetCode上面算法题的解答汇总在下面,CTRL+F就可以比较方便地找到。由于LeetCode上的题在不断更新,因此

[......]阅读全文

分享到:

LeetCode题目解答——Hard部分

以下是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-Group
24.9%
Hard

Binary Tree[......]阅读全文

分享到:

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

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

Multiply Strings
20.5%
Medium

Sum Root to Leaf Numbers[......]阅读全文

分享到:

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

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

Divide Two Integers 16.6% Medium 3Sum 16.7% Medium Evaluate Reverse Pol[......]阅读全文

分享到:

LeetCode题目解答——Easy部分

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

我觉得做这样的题目很有帮助,但也要有正确的目的。有些题是

[......]阅读全文

分享到:

一道位运算的算法题

一道位运算的算法题

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

Given an array of integers, every element appears three times except for one. Find that single one.

一组整数,除了一个只出现一次以外,其他每个整数都恰好出现三次,要寻找那个特殊的整数。

似曾相识

首先,它让我想起了另外一道类似的题目,如果把上面的&ld

[......]阅读全文

分享到:

排序算法一览(下):归并类、分布类和混合类排序

上半部分请参见《排序算法一览(上):交换类、选择类和插入类排序》

 

归并类排序

归并排序(Merge Sort)

归并排序是一种分治法,它反复将两个已经排序的序列合并成一个序列(平均时间复杂度O(nlogn),最好时间复杂度O(n)):

  • 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  • 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  • 比较两个指针所指向的元素,

[......]阅读全文

分享到:

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

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

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

[......]阅读全文

分享到:

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

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

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

[......]阅读全文

分享到:

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

给我一把榔头,满世界都是钉子 一篇文章存成一个巨大的文件,总共大约有一亿个单词,要找出里面重复次数最多的。怎么做?

Hadoop是一把威力巨大的榔头,在使用过Hadoop之后,看着任何东西都想把它给map reduce了。有一个关于Jeff Dean的小笑话,说在睡不着觉的时候,一般人是数羊,Jeff Dean是map reduce他的羊群。所以,我的办法是,把这个文件拆分成若干个小文件,在map过程用hash算法保证相同的

[......]阅读全文

分享到:

换个角度思考问题

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

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

换个角度思考问题

初看这个论断,觉得似乎是正确的,但又不知从何下手。文中指出证明的思路很巧妙,让人感到数学的美妙。我的感触是,文中的证

[......]阅读全文

分享到:

再谈大楼扔鸡蛋的问题

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

现在只有两个鸡蛋,而算法必须在各种合法输入下都是可行的,就是说要能找出这一层来,你得假设你的运

[......]阅读全文

分享到:

寻找组成字母相同的单词

寻找组成字母相同的单词 这篇文章是对这个帖子的汇总,帖子里的答复都很有意思,真希望ITEye多一些这样的帖子,少一些浮躁和毫无意义的争论。

我把帖子汇总贴在下面:

Write a function that takes as input list of words and prints out groups of words with exactly the same letters, one group per l

[......]阅读全文

分享到:

青蛙跳台阶问题的三种解法

青蛙跳台阶问题的三种解法 题目:一只青蛙一次可以跳1级台阶,也可以跳2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

这道题还被ITEye放在了博文视点杯有奖答题活动里面。

我提供三种解法。

1、递归求解:

青蛙每跳一次前,有这样三种情况:

  • (1)只剩1级或0级台阶了,只能跳一步或者无法再跳了,那么这条路也走到了终点,走法的种类数可以加1;
  • (2)可以走2级台阶;
  • (3)可以走1级台阶。

[......]阅读全文

分享到:

大楼扔鸡蛋问题的求解

大楼扔鸡蛋问题的求解 有道经典的算法题,两个一模一样的鸡蛋,某层之上扔鸡蛋就会碎。假如运气最差的话,问要测试多少次才能找出这层楼来。

如果只有一个鸡蛋,我就只能一层一层试验。两个的话关键就是找着第一个鸡蛋试验的位置,第二个鸡蛋还是只能一层一层试验。

这道问题其实可以扩展到任意个鸡蛋,但现在还是只看2个鸡蛋的情况。

2个鸡蛋只有n层的最优解求出来假使为k,那么,n+1层的时候,把第一个鸡蛋在第k层释放,只有两种情

[......]阅读全文

分享到:

Preview on Feedage: