2020.06.15牛客网中级班第二章算法

题目一

一个数的因子仅仅包括2，3，5的数称为丑数。数字1特别对待也看作是丑数，所以从1开始的10个丑 数分别为1、2、3、4、5、6、8、9、 10、12返回第n个丑数

暴力解:

a = 1 :

return true

a != 1 时:

先把所有2的因子消掉,得到b. 再把c所有3的因子消掉,得到d. 再把d所有5的因子消掉,得到e. e!=1 False e=1 True 时间复杂度log(a)

理解时间复杂度: 假设a中有K个2 Y个3 Z个5, 时间复杂度是O(K+Y+Z)

如果从头开始试,缺点特别慢.

思想:假设第i个丑数为a,则a = ? * 2 / ? * 3 / ? * 5

开头几个数不成立.

第一个丑数是1, 三个指针i2,i3,i5,初始情况下都指向1,由i2指针指向的数,只乘2, i3,i5同理

1x2=2, 1x3=3, 1x5=5

i2右移指向2: 2x2=4

3 4 5比较,最小的为下一个丑数,i3指向2: 2 x 3 = 6

4 5 6 比较,最小的为 4,i2右移,指向3: 2 x 3 = 6

5 6 6 比较,最小的为5,i5右移指向2: 5 x 2 = 10

6 6 10比较,最小的为6, i2, i3 右移, i2指向4, i3 指向3, 2 x 4 = 8, 3 x 3 =9

8 9 10 比较…

题目二

无序数组,对其中额子数组排序,让整体数组有序,求需要排序的最短子数组长度.

arr = [1, 5, 3, 4, 2, 6, 7] 返回4 [5, 3, 4, 2]

时间复杂度希望做到O(n),且不用额外空间. 如果排序,复杂度为O(NlogN)

从左往右遍历:

只关注一个点:当前数和左侧划过的数的关系.

当前数cur, 左侧划过的数最大为cur_max.

两种情况: cur >= cur_max(对) cur <= cur_max(错)

cur = 1 cur_max = null 对

cur = 5 cur_max = 1 对

cur = 3 cur_max = 5 错

cur = 4 cur_max = 5 错

cur = 2 cur_max = 5 错

cur = 6 cur_max = 5 对 (调整cur_max = 6)

cur = 7 cur_max = 6 对

记录错最右边的位置

从右侧往左遍历:

关注当前数和右侧划过数最小值的关系

cur < cur_min 对

cur > cur_min 错

cur_min = none cur = 7 默认为对

cur_min = 7 cur = 6 对

cur_min = 6 cur = 2 对

cur_min = 2 cur = 4 错

cur_min = 2 cur = 3 错

cur_min = 2 cur = 5 错

cur_min = 2 cur = 1 对

记录错最左的地方

需要排序的是两个最位置中间的数字.

解释:为什么这样做的原因是,当前数来到cur,左侧有一个数为cur_max,如果此时cur<cur_max排序,位置调换.我们记录最后一个不达标的位置,意味着右边的数字都达标.从右向左遍历,同样.

题目三

原问题是背包,构建出背包的表.

正数数组,累加和,即为最大值.

构建一张表

[3, 2, 5] max = 10

表的规格是 length * (sum + 1) 值为bool

dp[i][j] = arr[0…i] 所有数字自由组合,能否组成j

最后一个行从左往右,第一个为False的值即为组不成的数.

i01234567891030FFTFFFFFFF21FTTFTFFFFF52FTTFTFTTFT

表中每个元素得到是O(1)的时间复杂度,但是得构建表格,O(1) * SUM , sum很大,时间复杂度就很大

状态转移:

dp[i][j] =

1.dp[i-1][j] 如果此位置为T, dp[i][j]也肯定为T,此时用不到i位置上的数字

2.dp[i][j] 如果用到的话, dp[i-1][j-arr[i]] 为T, dp[i][j]也为T

1 || 2 只要有一个为T, dp[i][j]就为T.

如果arr[i] == j, 那么dp[i][j]为T

不用当前数的情况下,能否搞出来,直接看dp[i-1][j]用当前数,去找dp[i-1][j-arr[i]]

[进阶]

如果已知正数数组arr中肯定有1这个数,是否能更快得到最小不可组成和.

第一步,先排序,最小位置为1,其他位置不知. 承担时间复杂度o(nlogn)的代价

申请变量range = 1, range表示1-range(1)范围上所有的数都能被累加和得到

cur > range + 1

关注点:当前数有没有大于range + 1,如果有,返回range + 1, 如果没有,最后的range + 1即为答案, 包括所有的逻辑.

步骤:从1位置开始遍历

min(arr) = 1

range = 1

如果: arr[2] > 1 + range return arr[2]

否则: range = 1 + arr[2]

重点思路:如果数组中含有1, 用数组后面的的任何一个数,就可以连续的往下推.

题目五

random()方法是在[0, 1)方法随机返回一个数.

那么返回[0, x) (0<x<=1) 区间内的一个数的概率为x,因为它必返回[0,1)之间的数

现在要求返回概率为x^k(k=2,3,4,5)

在互相独立的情况下,假设x=0.6,k=2

random()返回[0, 0.6)内数的概率为0.6,现在需要返回0.6^2, 相互独立情况下,再次返回[0, 0.6)内的数的概率也为0.6.

第一次返回的概率为0.6,第二次返回的概率也为0.6,那么两次都返回的概率为0.36(互相独立),这时候只要判定两次中返回的最大值小于0.6即可判断两次返回的值都在[0, 0.6)区间内.

run max(random.random(), random.random()) < 0.6

题目四

首先考虑:假设数组为空,range=100,考虑缺多少个数.

缺1, 2, 此时范围推到1~3(3=1+2)

缺4, 范围1~7

缺8,范围1~15

缺16,范围1~31

缺32,范围1~63

缺64,范围1~127

考虑非空的情况.

arr = [3, 17, 21, 78], range=67 考虑1~67

touch = 0 (touch表示1~touch的值都被搞定了.)

arr[0] = 3 1~2未搞定

缺1 touch = 1 1~1搞定

缺2 touch = 2 1~2搞定

同样1~3也搞定 touch=3

此时1~6范围也已经搞定 touch=6

缺7 范围1~13 touch=13

缺14 范围1~27 touch=24

使用17 范围1~44 touch=44

使用21 范围1~65 touch=65

缺66 范围1~131 touch=131

touch > range 停止

另外一种情况:用完数组中的数,还没有到range.

数组完事后,touch = 5000 range=5000万,用数组为空的情况.

编程思路: 先排好序, 定义变量patches = 0, touch = 0

排好序后,从左往右遍历数组,

for i in range(len(arr): while arr[i] > touch + 1 # 说明当前arr元素 touch到达不了 # 比较巧的一个点, touch初始值为0,只要arr[0]不为1, 都会补充1这个元素.

题目六

假设所有元素单独在自己的集合,对外提供两个操作.

所有的集合在一个结构内,每个集合只有一个元素.

方法1) isameset(v 01, v 02) 返回V类型的o1和o2是否是一个集合的.

方法2) union(v o1, v o2) 把o1单样本所在集合和o2单样本所在集合合并成一个.

怎么把单词的时间复杂度搞成O(1).

暴力解法(并查集): 时间复杂度o(n^2)[每次查询合并时都是O(1)]

GCD方法(辗转相除法)判断最大公约数

给定参数中的每个元素首先单独样本,每个元素自己都是一个集合.

第一轮:

判断a,b T 则调用union(a, b)

判断a, c T 则调用union(a, c)

a,d a,e a, f

第二轮:

从b开始…

…

备注:并查集合并是最快的.

o(n^2) n:数组中数的个数

方法2:

{100, 50, 17, 200}

m找其质数因子的代价o(m)

确定一个数是否是质数代价是o(根号下m)

100的质数因子(在1-根下100之间查找):

1, 100

找到2,另外一个则是50

3, F

4, 25

5, 20

6, F

7, F

8, F

9, F

10, 10

建立map.

1010002050040250100

下一个数: 20

根号下20 ≈ 4

建立map

key : 因子 value : 哪个位置的数拥有这个因子

所有1的因子都忽略, 下面看因子20, 表中添加 20 : 1

看因子2,0位置已经有,把下标作为集合元素. 把0所在的集合和 1所在的集合合并.

因子10, 0位置已经有,再次合并

因子4, 0位置已经有,再次合并

因子5, 0位置没有, 5 : 1添加至表中.

最后,形成一张表.

暴力解法是直接数对数, 这种方法是因子对因子.

例子: 6, 2, 3, 102, 17

查6, 根下6 ≈ 2, 向下取整

1, 6 (1不可忽略, 若忽略1, 也会忽略6)

2, 3

map:

6 : 0

2 : 0

3 : 0

来到2 根下2 ≈ 1

因子为1, 2. 忽略因子1

查表,由2:0得知 0位置的数也有2这个因子, 0位置所在集合 和 1 位置所在集合 合并.(合并的时候就用到了前提知识并查集,因为并查集的并查操作时间复杂度为o(1))

来到3,根下3 约等于 1

因子为1, 3. 忽略因子1

查表, 由3:0得知0位置的数也有3这个因子,0所在集合 和 2所在集合 合并

来到102, 根下102 约等于 10

因子为:

1, 102(忽略1)

2, 51

3, 34

6, 17

查表,102 没有, 表里添加102 : 3

2 0位置所在集合 和 3位置所在集合 合并

51 添加 51: 3

3 0位置所在集合 和 3位置所在集合 合并

34 添加 34 : 3

6 0位置所在集合 和 3位置所在集合 合并

17 添加 17 : 3

来到 17,根下17 ≈ 4

因子为:

1, 17 (忽略1)

17 查表, 17: 3, 3位置所在集合 和 4位置所在集合合并.

时间复杂度为O(N * V ^ 1/2)

根据输入用例,猜想要什么方法.

如果N大,V很小,用第二种方法.

如果V都很大,N小,用第一种方法.