剑指offer_Part5

友情提示: 代码在这里
本文参照该仓库学习,大家可以star

40 最小的 K 个数

40-2 大小为 K 的最小堆

复杂度:O(NlogK) + O(K)
特别适合处理海量数据
应该使用大顶堆来维护最小堆,而不能直接创建一个小顶堆并设置一个大小,企图让小顶堆中的元素都是最小元素。

维护一个大小为 K 的最小堆过程如下:在添加一个元素之后,如果大顶堆的大小大于 K,那么需要将大顶堆的堆顶元素去除。

return o2.compareTo(o1);这个是降序

特殊记忆:使用compare o2->o1 前面大 后面小 降序 反之就是升序

40-3 快速选择

复杂度:O(N) + O(1)
只有当允许修改数组元素时才可以使用
快速排序的 partition() 方法,会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j],且 a[j+1..h] 大于等于 a[j],此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元素,这种找第 K 个元素的算法称为快速选择算法。

41 数据流中的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

PriorityQueue<>((o1,o2)->o2-o1);//从小到大

42 字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符 “go” 时,第一个只出现一次的字符是 “g”。当从该字符流中读出前六个字符“google” 时,第一个只出现一次的字符是 “l”。

42 连续子数组的最大和

{6, -3, -2, 7, -15, 1, 2, 2},连续子数组的最大和为 8(从第 0 个开始,到第 3 个为止)。

43 从 1 到 n 整数中 1 出现的次数

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

链接:https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
来源:牛客网

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
//主要思路:设定整数点(如1、10、100等等)作为位置点i(对应n的各位、十位、百位等等),分别对每个数位上有多少包含1的点进行分析
//根据设定的整数位置,对n进行分割,分为两部分,高位n/i,低位n%i
//当i表示百位,且百位对应的数>=2,如n=31456,i=100,则a=314,b=56,此时百位为1的次数有a/10+1=32(最高两位0~31),每一次都包含100个连续的点,即共有(a/10+1)* 100个点的百位为1
//当i表示百位,且百位对应的数为1,如n=31156,i=100,则a=311,b=56,此时百位对应的就是1,则共有a/10(最高两位0-30)次是包含100个连续点,当最高两位为31(即a=311),本次只对应局部点00~56,共b+1次,所有点加起来共有(a/10*100)+(b+1),这些点百位对应为1
//当i表示百位,且百位对应的数为0,如n=31056,i=100,则a=310,b=56,此时百位为1的次数有a/10=31(最高两位0~30)
//综合以上三种情况,当百位对应0或>=2时,有(a+8)/10次包含所有100个点,还有当百位为1(a/10==1),需要增加局部点b+1
//之所以补8,是因为当百位为0,则a/10==(a+8)/10,当百位>=2,补8会产生进位位,效果等同于(a/10+1)

int count=0;
long long i=1;
for(i=1;i<=n;i*=10)
{
//i表示当前分析的是哪一个数位
int a = n/i,b = n%i;
count=count+(a+8)/10*i+(a%10==1)* (b+1);
}
return count;
}
};

44 数字序列中的某一位数字

数字以 0123456789101112131415… 的格式序列化到一个字符串中,求这个字符串的第 index 位

45 把数组排成最小的数

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组 {3,32,321},则打印出这三个数字能排成的最小数字为 321323。

可以看成是一个排序问题,在比较两个字符串 S1 和 S2 的大小时,应该比较的是 S1+S2 和 S2+S1 的大小,如果 S1+S2 < S2+S1,那么应该把 S1 排在前面,否则应该把 S2 排在前面。

46 把数字翻译成字符串

给定一个数字,按照如下规则翻译成字符串:1 翻译成“a”,2 翻译成“b”… 26 翻译成“z”。一个数字有多种翻译可能,例如 12258 一共有 5 种,分别是 abbeh,lbeh,aveh,abyh,lyh。实现一个函数,用来计算一个数字有多少种不同的翻译方法。’

47 礼物的最大价值

在一个 m*n 的棋盘的每一个格都放有一个礼物,每个礼物都有一定价值(大于 0)。从左上角开始拿礼物,每次向右或向下移动一格,直到右下角结束。给定一个棋盘,求拿到礼物的最大价值。例如,对于如下棋盘

1
2
3
4
1    10   3    8
12 2 9 6
5 7 4 11
3 7 16 5

礼物的最大价值为 1+12+5+7+7+16+5=53。

应该用动态规划求解,而不是深度优先搜索,深度优先搜索过于复杂,不是最优解。(厉害!)

48 最长不含重复字符的子字符串

输入一个字符串(只包含 a~z 的字符),求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr,最长不含重复字符的子字符串为 acfr,长度为 4。

49 丑数

把只包含因子 2、3 和 5 的数称作丑数(Ugly Number)。例如 6、8 都是丑数,但 14 不是,因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。

作者:HelloHello233
链接:https://www.nowcoder.com/questionTerminal/6aa9e04fc3794f68acf8778237ba065b
来源:牛客网

丑数的定义是1或者因子只有2 3 5,可推出丑数=丑数丑数,假定丑数有序序列为:a1,a2,a3…….an
所以可以将以上序列(a1除外)可以分成3类,必定满足:
包含2的有序丑数序列:2
a1, 2a2, 2a3 …..
包含3的有序丑数序列:3a1, 3a2, 3a3 …..
包含5的有序丑数序列:5
a1, 5a2, 5a3 …..
以上3个序列的个数总数和为n个,而且已知a1 = 1了,将以上三个序列合并成一个有序序列即可
程序中t2,t3,t5实际就是合并过程中三个序列中带排序的字段索引

(歪日) 太强了