秋招复习计划-算法题2

  |  

前言

旋转数组的最小数字,斐波那契数列,跳台阶,变态跳台阶,矩形覆盖


27



旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。如果一个非递减排序的数组的旋转数组,输出数组的最小元素。例如数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转,该数组的最小值为1。注意:给出的所有元素都大于0,若数组大小为0.请返回0

题目分析

分析旋转数组的特点,我们会发现,旋转数组由两个有序的部分组成,并且存在一个分界点,而这个分界点刚好就是最小的那个数。

除此之外,我们还可以用二分法去逼近这个最小的数。

算法代码

1
2
3
4
5
6
7
function minNumberInRotateArray(rotateArray) {
if(rotateArray.length === 0) return 0;
for(let i = 0, len = rotateArray.length; i < len; i++) {
if(rotateArray[i] > rotateArray[i + 1]) return rotateArray[i + 1];
}
return rotateArray[0];
}

这个方法就是利用了旋转数组分界点的特点,旋转数组两部分都是递增的,只有在分界点处,最小值比它左边的值小。这个方法的时间复杂度是O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
function minNumberInRotateArray2(rotateArray) {
let left = 0,
right = rotateArray.length - 1;
while (right - left > 1) {
let mid = left + (right - left >> 1);
if (rotateArray[mid] > rotateArray[right]) {
left = mid;
} else {
right = mid;
}
}
return Math.min(rotateArray[left], rotateArray[right]);
}

这个方法使用的就是二分法来逼近最小值。它一直将中间的值与右边的值比较,如果中间的值大于右边的值,就将左赋值为中间位置,取有半侧。如果小,则将中间位置赋值给右,取左半侧。并且它计算中间位置的方式也比较特别。它用左的位置去加上范围(右减左)的“一半”,这一的一般并不是真正的一半,而是使用了右移一位的方式。这样也会导致,最后无论右与做的举例是3还是2,最后左和右之间都会差1,这也是为什么最后的返回值是左和右中较小的哪一个,这个1的间隔是无法消去的。

举例说明:[3,4,5,6,7,1,2]

起始的left=0,right=6。mid = 0 + 6(110)右移一位(011) = 3;

rotateArray[3] = 6 > 2 = rotateArray[6],所以left = mid = 3。再次计算mid = 3 + 11的右移一位 = 4

rotateArray[4] = 7 > 2 = rotateArray[6], 所以left = mid = 4。再次计算mid = 4 + 10右移一位 = 5

rotateArray[5] = 1 < 2 = rotateArray[6],所以right = mid = 5。

比较rotateArray[4] ,rotateArray[5],及7和1,返回1.

斐波那契数列

题目描述

斐波那契数列及f(n) = f(n-1) + f(n-2),现在要求输入一个整数n,请你输出斐波那契数列的第n项

题目分析

从斐波那契数列的定义来看,可以使用递归,但是递归的重复计算部分太多了,其实我们只要知道n-1和n-2的值就行了。现在我们来计算一遍,先从0开始。

第0个数为0,第一个数为1

对于第2个数来说 1 = 1 + 0,而它的前一个数,也就是第1个数可以用第2个数减第0个数,及1 - 0 = 1计算得出

对于第3个数来说 2 = 1 + 1,而它的前一个数,也就是第2个数可以用第3个数减第1个数,及2 - 1 = 1计算得出

对于第4个数来说 3 = 2 + 1,而它的前一个数,也就是第3个数可以用第4个数减第2个数,及3 - 1 = 2计算得出

依次类推,我们只要在开始是计算自身和前一个数的和,可以得到下一个数,然后用下一个数去减前一个数,从新得到自身,并保存。在下一次的计算中,自身就变成了前一次的计算结果,而前一个数就是上一次的自身。虽然这样听起来有点绕,但是其核心就是将每一次的数保存下来做下一次计算用。这样就减少重复计算

算法代码

1
2
3
4
5
6
7
8
9
function Fibonacci(n) {
let f = 0,
g = 1;
while(n--) {
g += f;
f = g - f;
}
return f;
}

分析一下它的运行过程

1
2
3
4
5
6
7
8
9
7 13
g = 1; f= 0; //初始化,g为第一个值,f为第0个值,也就是当前值
7 g = 1 + 0 = 1; f = 1 - 0 = 1 //第一次计算,g为第二个值,f为第一个值
6 g = 1 + 1 = 2; f = 2 - 1 = 1
5 g = 2 + 1 = 3; f = 3 - 1 = 2
4 g = 3 + 2 = 5; f = 5 - 2 = 3
3 g = 5 + 3 = 8; f = 8 - 3 = 5
2 g = 8 + 5 = 13; f = 13 - 5 = 8;
1 g = 8 + 13 = 21; f = 21 - 8 = 13

当然,其实递归也是较为简单的一种方式,在n不是很大的情况下,也可以使用递归的方法,这里也给出递归的代码

1
2
3
4
5
6
7
function Fibonacci(n) {
if(n === 2 || n === 1) {
return 1;
} else {
return Fibonacci(n-1) + Fibonacci(n-2)
}
}

跳台阶

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求改青蛙跳上一个n级的台阶总共有几种跳法。

题目分析

看起来这道题很复杂,其实用一下小学的奥数思维分析一下:

  • 假设青蛙第一次跳一个台阶,那么还有n-1个台阶要跳,记作f(n-1)种跳法。
  • 假设青蛙第一次跳两个台阶,那么还有n-2个台阶要跳,基座f(n-2)种跳法。
  • 那么n个台阶,青蛙有f(n) = f(n-1) + f(n-2)种跳法。
  • 那么f(n=1)有一种跳法,f(n=2) 有两种跳法

没错,你没有看错,这就是斐波那契数列

算法代码

1
2
3
4
5
6
7
8
9
function jumpFloor(n) {
let f = 1,
g = 2;
while(--n) {
g += f;
f = g - f;
}
return f
}

变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级….也可以跳上n级,求该青蛙跳上n级台阶有几种跳法

题目分析

数学不好真的写不来算法,这种高中送分的数列规律问题,现在都快忘的差不多了,分析一下:

  • 同之前的跳台阶一样,f(n) = f(n-1) + f(n-2) + …. + f(1)
  • f(n - 1) = f(n-2) + f(n-3) + …. + f(1)
  • 一式减二式可得 f(n) - f(n-1) = f(n-1), f(n) = 2 * f(n-1)

这道题编程没有任何难度,真的是在考数学

算法代码

1
2
3
function jumpFloorII(n) {
return Math.pow(2, n-1);
}

矩形覆盖

题目描述

请问用n个2*1的小举行无重复地覆盖一个2*n的打矩形,一共有多少种方法

题目分析

还是斐波那契:

  • 假设矩形为2*1,那么只有一种摆放方法
  • 假设矩形为2*2,那么有两种摆放方法
  • 假设矩形为2*n,考虑第一次摆放,如果是竖着摆,那么还剩下2*(n-1)的矩形摆放,有f(n-1)种摆法
  • 假设矩形为2*n,考虑第一次摆放,如果是横着摆,那么它下面那一行也只能横着摆,那么还剩下2*(n-2)的矩形摆放,有f(n-2)种摆法
  • 得出f(n) = f(n-1) + f(n-2)

算法代码

1
2
3
4
5
6
7
8
9
function rectCover(number) {
if (number === 0) return 0;
let f = 1,
g = 2;
while(--number) {
g += f;
f = g - f;
}
}
文章目录
  1. 1. 旋转数组的最小数字
  2. 2. 斐波那契数列
  3. 3. 跳台阶
  4. 4. 变态跳台阶
  5. 5. 矩形覆盖
|