【解题报告】【lintcode81】Data Stream Median

题意

给出一组数字,逐一输入,每输入一个数字,就输出已经输入数字排序后的中位数,即中间那个数字

解答

直接暴力很简单,但是时间复杂度很高,不符合性能要求。
时间复杂度要求是nlogn,可以想到的是快速排序和堆排序两种排序,再结合题目,我们选择堆

维护两个堆,一个堆比中位数小,一个比中位数大,我们称之为大堆,小堆

大堆是一个比中位数大的小根堆,堆顶是刚刚比中位数大的数

小堆是一个比中位数小的大根堆,堆顶是刚刚比中位数小的数

每次获得一个数的时候,先与目前的中位数比较,大就加入大堆,小就加入小堆,如果加入完毕之后两个堆的大小不一致了,就应该重新查找中位数了
1.如果大根堆比小根堆大,[……]

Read more

【解题报告】【lintcode192】Wildcard Matching

题意

判断两个可能包含通配符“?”和“”的字符串是否匹配。匹配规则如下:
‘?’ 可以匹配任何单个字符。
‘ 可以匹配任意字符串(包括空字符串)。
两个串完全匹配才算匹配成功。
一些例子:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, ““) → true
isMatch(“aa”, “a
“) → true
isMatch(“ab”, “?“) → true
isMatch(“aab”, “c
a*b”) → false

解答

对于’?’的匹配很简[……]

Read more

【解题报告】【lintcode54】String to Integer II

题意

一个字符串中间含有一个整数数字,找出他,并转为数字返回

解答

主要分为三步来求解
1.使用正则表达式匹配字符串,看是否有符合条件的子串
2.根据匹配结果,再根据符号,小数点的位置确定执行操作串的长度和开始位置
3.对于每一个操作子串的字符进行处理,并加到结果上,最后处理边界和符号

代码

[……]

Read more

【解题报告】【lintcode88】Lowest Common Ancestor

题意

给出一颗二叉树中的两个节点,寻找它们的最小公共祖先

解法

分为两个部分
1.寻找给出节点的路径
2.比较这两个路径,寻找最小公共祖先

代码

[……]

Read more

【解题报告】【lintcode1】A + B Problem

题意

不适用任何数学运算实现A+B

解答

使用位运算
异或运算可以当作加法,但是无法处理进位
需要使用按位与和左移来进行进位处理

代码

[……]

Read more

【解题报告】【lintcode61】 Search for a Range

题意

在一个有序数组中,找到给出的范围值的开始和结束点下标
nlogn的复杂度

解答

看到nlogn和有序数组,那么就能想象到二分查找,但是需要对二分查找做一些改动
当找到目标时不停止,而是继续对左右区间进行二分,并维护找到区间边缘的最小/最大下标
那么,一次二分进行完毕之后,我们就可以得到最大最小的范围了。

代码

[……]

Read more

【解题报告】lintcode82落单的数

题意

数组里所有数都出现了两次,但是其中有一个只出现了一次,找出它
时间复杂度O(n)

解答

使用位运算,异或运算
由于其结合律
结合律:A^(B^C)=(A^B)^C
且如果两个数字相同,异或结果为0,0与仍和数字的异或为这个数字本身
我们把所有数字异或起来,就是我们要找的结果了

代码

[……]

Read more

【解题报告】lintcode4求第n个丑数

题意

设计一个算法,找出只含素因子2,3,5 的第 n 大的数。
符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12…

解答

既然只有素数因子2,3,5,那么我们可以得知,第n个丑数肯定是前面某一个丑数乘以2,3,5的结果
那么,我们可以以此生成一个丑数表
但是,第n个丑数是多少呢,可以得知,是比前一个数大的最小丑数
我们设置三个计数器,记录乘2,3,5比当前最大的丑数还要大的下标
每次添加就从这三个下标的数乘2,3,5的结果中选最小的一个
如此循环,得到第n个

代码

[……]

Read more

【解题报告】lintcode3统计数字

题意

给出一个n和k,统计0-n的数字中,k出现了多少次

解题

首先通过log运算来得出n有多少位,创建数组,每次给数组最低位加1
然后计算进位
在计算过程中,计算数字出现次数

代码

[……]

Read more

【解题报告】lintcode5寻找第k大数

题意

寻找给定无序数组中第k大的数

解法

设置一个标记数组,扫描给出的数组,在标记数组对应下标的数字上加一
然后遍历标记数组,当综合等于给出数组长度-k时,就找到了第k大数(此时标记数组的下标就是这个数字)

代码

[……]

Read more