贰.1.7 实战:阿里巴巴前端面试题

贰.1.7.1 求数组子数组之和的最大值

这道题源自微软面试题,后来被阿里巴巴用上了,据说只有20%的人能给出时间复杂度为 O(N3)O(N^3) 的答案,给出 O(N)O(N) 解的人极少。题目如下:

一个有N个整数项的一维数组,这个数组有很连续多子数组,那么子数组之和的最大值是多少?

举例:

  • [ 1,-3, 3, 4, 5,-3]返回12;

  • [-1,-2,-3,-4,-9,-8]返回-1;

解法一

问题其实是求从下标为ij之间的连续数组项之和的最大值。

function fn(arr) {
let maxSum=-Infinity, len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = i; j < len; j++) {
let sum=0;
for (let k = i; k <= j; k++) {
sum += arr[k];
}
if (sum > maxSum){
maxSum = sum;
}
}
}
console.log(maxSum);
}
fn([ 1, -3, 3, 4, 5, -3]);//>> 12
fn([-1, -2, -3, -4, -9, -8]);//>> -1

上面代码有3个for循环,因此时间复杂度是 O(N3)O(N^3)

解法二

如果注意到 Ai+...+Aj=Ai+...Aj1+AjA_i+...+A_j=A_i+...A_j-_1+A_j ,那么可以将解法一精简如下:

function fn(arr) {
let maxSum=-Infinity, len = arr.length;
for (let i = 0; i < len; i++) {
let sum = 0;
for (let j = i; j < len; j++) {
sum += arr[j];
if (sum > maxSum){
maxSum = sum;
}
}
}
console.log(maxSum);
}
fn([ 1, -3, 3, 4, 5, -3]);//>> 12
fn([-1, -2, -3, -4, -9, -8]);//>> -1

上面代码第6行就体现了 Ai+...+AjA_i+...+A_j ,与解法一的第三个for循环其实是等效的。因此可以精简掉一个for循环,精简之后的算法时间复杂度为 O(N2)O(N^2) 。能做到这样,其实已经不错的,但是还不够,有没有更低时间复杂度的解法呢?有!

解法三

若用动态规划法,应该先有一个“看起来更加毫无规律”的样本数据,这里选[ 1, -3, 3, 4, 5, -3],然后做下面表格分析规律得出状态转移方程

步骤

操作

累加的子数组之和

最大子数组和

1

加1

1

1

2

-3

-2

-2

3

之前的和<0,舍弃,直接从3开始,+3

3

3

4

+4

7

7

5

+5

12

12

6

-3

9

12

用数学归纳法得出状态转移方程如下:

//todo

function fn(array) {
if (array == null && array.length <= 0) {
return 0;
}
let Maxsum = Integer.MIN_VALUE;
let currentSum = 0;
for (let i = 0; i < array.length; i++) {
currentSum += array[i];
if (currentSum < array[i]) {
currentSum = array[i];
}
if (currentSum > Maxsum) {
Maxsum = currentSum;
}
}
return Maxsum;
}

时间复杂度为 O(N)O(N)

贰.1.7.2 硬币找零

题目为:

从面值为 1,2,5,10 的硬币中找零 36 块钱,最少要 几 枚硬币?

解法一:动态规划

这是典型的动态规划问题。所谓动态规划,也即问题分成多个步骤,每一步的选择是可以动态调整的,所有步骤完成之后,最后求最优解。比如求两点之间的最优路径,多种组合方案的最优方案。这类问题,可以分解成对每一步求最优解,然后将每步的最优解组合,即为最终最优解。

本题求最少硬币数,也可以用动态规划法求解。首先要归纳出一个状态转移方程。给定的金额i,最少硬币数为f(i),硬币面值为j,它们之间的关系可以用方程表达如下(该方程即为状态转移方程):

f(i)=f(ij)+1f(i)=f(i-j)+1

有了上面这个状态转移方程,可以看出是一个递归求解过程,所以,此类问题就很好解了,代码如下:

/**
* 硬币找零 之 动态规划法。
* 状态转移方程 DP(i)=DP(i-j)+1,其中i是金额,j是硬币面值。
* @param {array} coins 硬币面额的数组
* @param {number} amount 给定的金额数
*/
(function (coins, amount) {
//优化,缓存递归过程中已经计算过的金额数
let cache = new Map();
//如果金额和面值恰好相等,1枚硬币就能完成
coins.forEach(coin => {
cache.set(coin, 1);
});
console.time("coffe1891");
let DP = function (amount) {
if (amount <= 0)
return 0;
else if (cache.has(amount))
return cache.get(amount);
else {
//缓存方案
let tmpArr = [];
for (let i = 0; i < coins.length; i++) {
let coin = coins[i];
if (amount - coin > 0) {//非法钱数不计算
//递归
let v = DP(amount - coin) + 1;
tmpArr.push(v);
}
}
//从方案中选最优的
tmpArr.sort((a, b) => a - b);
cache.set(amount, tmpArr[0]);
return tmpArr[0];
}
}
console.log("从面值为 " + coins + " 的硬币中找零 " + amount + " 块钱,最少要 " + DP(amount) + " 枚硬币");
console.timeEnd('coffe1891');
})([1, 2, 5, 10], 36);

因此我们发现一个规律:可用动态规划法解题的关键,在于找到状态转移方程,通过观察该方程,可以更快知道解题的具体算法思路

解法二:贪心算法

每次我们都优先取最大的硬币面额,直到剩余金额不足最大面额时,我们会取第二大的面额,以此类推,从而实现总硬币数最小的目的。其思想非常简单,我们直接上代码:

/**
* 硬币找零 之 贪心算法
*/
(function (coins, amount) {
let s = new Date().getTime();
let greedy = function (amount) {
let total = 0;//已找金额
let change = [];//放硬币的罐子
for (let i = coins.length-1; i >= 0; i--) {
let coin = coins[i];
while (total + coin <= amount) {
change.push(coin);
total += coin;
}
}
return change.length;
}
console.log("从面值为 " + coins + " 的硬币中找零 " + amount + " 块钱,最少要 " + greedy(amount) + " 枚硬币");
let e = new Date().getTime();
console.log("耗时 " + (e - s) + " ms");
})([1, 2, 5, 10], 36);