前端算法题目解析（二）

小皮咖

发布于 2020-02-24 12:28:22

7880

发布于 2020-02-24 12:28:22

文章被收录于专栏：小皮咖

前言

虽然疫情还是严峻，但总会过去。在此居家办公之际，应该趁这个时机好好提升下自我，多读书多看报，少吃零食多运动哈哈。

最近看一些文章和题目有接触一些算法题，我整理了一下收录daily-question 的 algorithm 文件夹中，后续会继续增加，本文分享我整理的十个算法题目。

11-计算矩阵中的岛个数

问题描述：

一个矩阵中只有 0 和 1 两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片 1 连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？

举例：下面这个矩阵中有4个岛。

let arrIsland = [
	[0,0,1,0,1,0],
	[1,1,1,0,1,0],
	[1,0,0,1,0,0],
	[0,0,0,0,0,1]
]
// 四个岛分别是 【(0,2)(1,0)(1,1)(1,2)(2,0)】 【(0,5),(1,5)】 【(2,3)】【(3,5)】

思路：

用递归与双循环实现，循环中递归找到一个岛（即找出 1 及其上下左右的 1），将此岛标记（我标记为2），然后重复依次找出剩下的岛
注意边界情况及不等于1的情况，此时应结束递归。

参考答案：

function islandCount(arr){
	if (!arr || arr.length === 0) {
		return;
	};
	let N = arr.length, M = arr[0].length, res = 0;
	for(let i = 0; i < N; i++){
		for(let j = 0; j < M; j++){
			if (arr[i][j] === 1) {
				++res;
				infect(arr,i,j,N,M);
			}
		}
	}
	return res;
}
// 递归函数，传入 数组arr, x坐标 i, y坐标j 数组长度N及数组内元素长度M
function infect(arr,i,j,N,M){
  // 处理边界情况及不为1的情况，此时结束递归
	if (i < 0 || j < 0 || i >= N || j >= M || arr[i][j] !== 1) {
		return;
	};
	arr[i][j] = 2; // 将找到的岛元素标记，避免重复
	infect(arr,i,j-1,N,M); // 向左寻找
	infect(arr,i+1,j,N,M); // 向右寻找
	infect(arr,i,j+1,N,M); // 向下寻找
	infect(arr,i-1,j,N,M); // 向上寻找
}
let arrIsland = [
	[0,0,1,0,1,0],
	[1,1,1,0,1,0],
	[1,0,0,1,0,0],
	[0,0,0,0,0,1]
];
console.log(islandCount(arrIsland));  // 4
复制代码

12-汉诺塔问题

关于汉诺塔：

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

思路：

递归解决：把问题转化为规模缩小了的同类问题的子问题；
明确递归结束的条件(base case)：n == 1
其他过程：from：来源地；to：目的地；help：辅助。

参考答案：

function hanoiProcess(n,from,to,help){
	if (n < 1) {
		return;
	}
	if (n == 1) {  // 最后一个从from移到to
		console.log("Move 1 from " + from + " to " + to);
	} else{
		hanoiProcess(n-1, from, help, to);  // 前n-1个从from移到help上，可以借助to
		console.log("Move "+ n +" from " + from + " to " + to);
		hanoiProcess(n-1, help, to, from);  // 再把n-1个从help移到to，可以借助from
	}
}
hanoiProcess(3, "左", "右", "中");
// Move 1 from 左 to 右
// Move 2 from 左 to 中
// Move 1 from 右 to 中
// Move 3 from 左 to 右
// Move 1 from 中 to 左
// Move 2 from 中 to 右
// Move 1 from 左 to 右
复制代码

13-母牛生母牛

问题描述：

母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设不会死。求 N 年后，母牛的数量。

思路：

因为新生的母牛，只有等到第四年才能生小母牛。所以前 4 年，只有原来的一头母牛每年生一头。
第一年：原始牛共 1 头
第二年：原始牛生了牛 A 共两头
第三年：原始牛生了牛 A , 牛 B 共三头
第四年：原始牛生了牛 A , 牛 B, 牛 C ，共四头
第五年：原始牛生了牛 A , 牛 B, 牛 C，牛 D 共五头，牛 A 生了牛 A1 共两头，其中牛 A 多算了一次。我们将牛 A 视为一头新的原始牛抽离出去，则原来的原始牛生了牛 B, 牛 C，牛 D 共四头，新原始牛生了牛 A1 共两头，从这里你会发现，第五年剩的数量 = 第四年生的的数量 + 第二年生的数量
接着算第六年：原始牛生了牛 A , 牛 B, 牛 C，牛 D，牛 F 共六头，牛 A 生了牛 A1,牛 A2 共三头, 牛 B 生了牛 B1 共两头

单独把牛 A 拿出来做原始牛，你会发现剩下的 原始牛生了牛B, 牛C，牛D，牛F，牛B生了牛B1共两头 与第五年的情况 原始牛生了牛A , 牛B, 牛C，牛D 共五头，牛A生了牛A1共两头及其相似，数量规则一致只是名字不一样而已，那么第六年的数量 = 第五年的数量 + 第三年的数量，以此类推可以得出 f(n) = f(n-1) + f(n-3), 当 n <= 4 时， f(n) = n, 是不是有点斐波那契数列的感觉？？可以用递归实现！！

参考答案：

function cow(n) {
  if (n < 1) {
    return;
  }
  let count = 0;
  if (n > 4) {
    count = cow(n - 1) + cow(n - 3);
  } else {
    count = n;
  }
  return count;
}
let n = 7;
console.log(n + ' 年后，牛的数量是： ' + cow(n));
// 7 年后，牛的数量是： 13
复制代码

14-找出字符串中出现最多的字母

例如字符串： （ababccdeajxac）

最先想到的解法是用 map 纪录每个字符的次数，然后找出最多的即可：

function getMaxNumberOfChar(str) {
  return (str + '').split('').reduce(
    function(pre, cur, index, arr) {
      cur in pre ? pre[cur]++ : (pre[cur] = 1);
      pre[cur] > pre.value && ((pre.char = cur), (pre.value = pre[cur]));
      return pre;
    },
    { value: 0 }
  );
}
getMaxNumberOfChar('ababccdeajxac'); // Object {value: 4, a: 4, char: "a", b: 2, c: 3…}
复制代码

此外，可以考虑用正则来辅助处理：

function getMaxNumberOfChar(str) {
  return (str + '')
    .split('')
    .sort()
    .join('')
    .match(/(\w)\1*/g) // \1表示\w匹配到的字母  \1是匹配第一个分组匹配到的内容
    .reduce(
      function(pre, cur) {
        return cur.length > pre.value
          ? { value: cur.length, char: cur[0] }
          : pre;
      },
      { value: 0 }
    );
}
getMaxNumberOfChar('ababccdeajxac'); // Object {value: 4, char: "a"}
复制代码

这里拓展一下 reduce 函数的用法

// reduce 函数
// array.reduce(function(accumulator, currentValue, currentIndex, arr), initialValue)
// reducer回调函数本身接受几个参数，第一个参数是 accumulator 累加器，第二个是数组中的 item，第三个参数是该项的索引，最后一个参数是原始数组的引用。
// initialValue 为reduce初始值，否则视数组第一个值为初始值，选填
const array1 = [1, 2, 3, 4];

// 1 + 2 + 3 + 4
console.log(
  array1.reduce((accumulator, currentValue) => {
    console.log(accumulator, currentValue);
    return accumulator + currentValue;
  })
);
复制代码

15-解析 URL 参数为对象

尽可能的全面正确的解析一个任意 url 的所有参数为 Object，注意边界条件的处理

let url =
  'http://www.suporka.com/?user=suporka&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled';
parseParam(url);
/* 结果
{ user: 'suporka',
  id: [ 123, 456 ], // 重复出现的 key 要组装成数组，能被转成数字的就转成数字类型
  city: '北京', // 中文需解码
  enabled: true, // 未指定值得 key 约定为 true
}
*/

解法

function parseParam(url) {
  const paramsStr = /.+\?(.+)$/.exec(url)[1]; // 将 ? 后面的字符串取出来
  const paramsArr = paramsStr.split('&'); // 将字符串以 & 分割后存到数组中
  let paramsObj = {};
  // 将 params 存到对象中
  paramsArr.forEach(param => {
    if (/=/.test(param)) {
      // 处理有 value 的参数
      let [key, val] = param.split('='); // 分割 key 和 value
      val = decodeURIComponent(val); // 解码
      val = /^\d+$/.test(val) ? parseFloat(val) : val; // 判断是否转为数字

      if (paramsObj.hasOwnProperty(key)) {
        // 如果对象有 key，则添加一个值
        paramsObj[key] = [].concat(paramsObj[key], val);
      } else {
        // 如果对象没有这个 key，创建 key 并设置值
        paramsObj[key] = val;
      }
    } else {
      // 处理没有 value 的参数
      paramsObj[param] = true;
    }
  });

  return paramsObj;
}
复制代码

16. 走楼梯的动态规划

题目：

楼梯台阶有 12 阶，一步只能走 1 阶或者 2 阶，那么，请问走完楼梯有多少走法？

这里涉及到动态规划，所谓动态规划，意思就是说，大事化小，小事化了。术语的话，包含三个，最优子结构，边界，状态转移公式

再来分析这道题目——

走到最后一个台阶的前一个情况，只能有两种，就是从第 11 台阶走一步上来，或者从 10 台阶走两步上来，那么不管有多少走法走到了 11 阶假设是 X 种走法吧，假设是 Y 种走法走到了 10 阶，那么，走到 12 阶的走法一定是 X+Y，这个是成立的吧。这就是最优子结构
那什么是边界呢？本例子中，走到第一个台阶，就一种走法吧，没有台阶，那就 0 种走法吧，走到第二个台阶，也就 2 种走法，其实这就是边界了。
那么状态转移公式就水到渠成了, F(n) = F(n-1) + F(n-2)，看起来是不是有点像斐波那契数列？？

代码如下：

function fun(n) {
  if (n < 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  return fun(n - 1) + fun(n - 2);
}
console.log('12台阶的走法 ：' + fun(12));
复制代码

我们之前在斐波那契数列里面讲过，这种递归有性能问题，根据斐波那契数列的优化，改写代码如下：

function fun(n) {
  if (n < 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  var a = 1;
  var b = 2;
  var temp = 0;
  for (var i = 3; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }
  return temp;
}
console.log('12台阶的走法 ：' + fun(12));
复制代码

17-数组中找出和为 M 的 N 个数

先来道简单的题目：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们组成的数组。 你不能重复利用这个数组中同样的元素。

比较容易想到的方法是用两层循环，不断遍历找出和为目标值的两个元素，然后存进数组。

var nums = [8, 9, 2, 15, 7, 1];
var target = 9;
var twoSum = function(nums, target) {
  var result = [];
  for (var i = 0; i < nums.length; i++) {
    for (var j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        result.push([nums[i], nums[j]]);
      }
    }
  }
  return result;
};
console.log(twoSum(nums, target)); //[ [ 8, 1 ], [ 2, 7 ] ]
复制代码

如果要求我们使用递归，该如何实现呢？

这个和我上一个算法《走楼梯的动态规划》有些相似，我们也来动态规划下：

假设数组和目标值如下

var nums = [8, 9, 2, 15, 7, 1];
var target = 9;

首先我们拿出第一个元素 8 ，再从后面剩下的[9, 2, 15, 7 ,1]找 9-8 (即1), 找到与目标值差值（这里是 1）则返回这个组合，找不到返回空数组
然后再从剩下的[9, 2, 15, 7 ,1]找出组合值等于目标值的数组，即重复 1 步骤
将 1，2 步骤合并就是我们所求的组合
状态转移公式为 f(n) = f(n 首项与目标值差值组合).concat(f(n - 1))
边界。当数组长度小于取出元素个数时，返回空数组。当取出元素为 1 时，返回目标值数组。

// 以下是代码
var nums = [8, 9, 2, 15, 7, 1];
var target = 10;

function search(arr, m, n = 2) {
  if (arr.length < n) return [];

  if (n === 1) return arr.filter(i => i === m);
  return search(arr.slice(1), m - arr[0], 1)
    .map(item => [arr[0], item])
    .concat(search(arr.slice(1), m));
}
console.log(search(nums, target));
复制代码

升级版

从一个数组中找出 N 个数，其和为 M 的所有可能

从上面得知，如果使用循环，取出 2 个数就是两层循环，3 个数就是三层循环，以此类推，n 越大循环越多，显然不可取。所以选择第二种方法，也就是递归。

上面已经为我们写好了递归的雏形，现在对其进行改造

上面边界 n === 1 其实还可以降为 0, 因为当 n === 0 && m === 0 时，上一步的 arr[0] 就是我们要找的最后一个数,而且在 map 函数中，我们已经将 arr[0] 置为首位，此时只要返回一个长度为 1 且首项为空的数组（[[]]），并且在 map 函数中将其 item([]) 展开即可

注：这里要花点时间好好理解下，比较绕

// 代码如下
function search(arr, m, n) {
  if (n === 0) return m === 0 ? [[]] : [];
  if (arr.length < n) return [];
  return search(arr.slice(1), m - arr[0], n - 1)
    .map(item => [arr[0], ...item])
    .concat(search(arr.slice(1), m, n));
}

// 测试一下
var nums = [8, 9, 2, 15, 7, 1];
var target = 10;

console.log(search(nums, target, 3)); // [[2,7,1]]
复制代码

18-数组中找出和为 M 的 N 个数(番外篇)

还是同样的问题：

从一个数组中找出 N 个数，其和为 M 的所有可能

数组中选取不固定数值 N ，我们可以尝试着使用标记的方式，我们把 1 表示成选取状态，把 0 表示成未选取状态。

假设数组 const arr=[1,2,3,4] ，对应着每个元素都有标记 0 或者 1 。如果 N=4 ，也就是在这个数组中，需要选择 4 个元素，那么对应的标记就只有一种可能 1111 ，如果 N=3 ，那就有 4 种可能，分别是 1110 、 1101 、1011 以及 0111 (也就是 C4 取 3->4 ) 种可能。

标记中有几个 1 就是代表选取了几个数，然后再去遍历这些 1 所有可能存在的排列方式，最后做一个判断，这个判断就是：每一种排列方式，都代表着数组中不同位置的被选中的数的组合，所以这里就是将选中的这些数字，进行求和运算，然后判断求出的和是不是等于 M 。

如何将数组和标记关联

0101 明显就是二进制嘛

对于 arr 来说，有 4 个元素，对应的选择方式就是从 0000（ N = 0 ）到 1111( N = 4 )的所有可能。

而 1111 就是 15 的二进制，也就是说这所有的可能其实对应的就是 0 - 15 中所有数对应的二进制。

这里的问题最终变成了如何从数组长度 4 推导出 0 - 15

这里采用了位运算--左移运算， 1 << 4 的结果是 16 。所以我们可以建立这样一个迭代：

const arr = [1, 2, 3, 4];
let len = arr.length,
  bit = 1 << len;

// 这里忽略了 0 的情况(N = 0)，取值就是 1 - 15
for (let i = 1; i < bit; i++) {
  // ...
}

如何从 1110 标记中取出 1 的个数

最简单的方式：

const n = num => num.toString(2).replace(/0/g, '').length;
复制代码

这其实也是一道算法常考题，因为位运算是不需要编译的，肯定速度最快。

PS: 如果不理解位运算为何会提高性能的同学，可以自行搜索一下位运算。简单点说就是：位运算直接用二进制进行表示，省去了中间过程的各种复杂转换，提高了速度。

我们尝试使用 & 运算来解决这个问题

首先我们肯定知道 1 & 1 = 1; 1 & 0 = 0 这些结论的。所以我们从 15 & 14 => 14 可以推导出 1111 & 1110 => 1110 ，为什么可以这样推导呢，因为 15 的二进制就是 1111 ，14 同理。

我们可以看到，通过上面的操作消掉了最后的 1。

所以我们可以建立一个迭代，通过统计消除的次数，就能确定最终有几个 1 了。代码如下：

const n = num => {
  let count = 0;
  while (num) {
    num &= num - 1;
    count++;
  }
  return count;
};
复制代码

计算和等于 M

现在我们已经可以把所有的选取可能转变为遍历一个数组，然后通过迭代数组中的每个数对应的二进制，有几个 1 来确定选取元素的个数。

那么，现在需要的最后一层判断就是选取的这些数字和必须等于 M

这里其实就是建立一个映射：

1110 到 [1, 2, 3, 4] 的映射，就代表选取了 2, 3, 4，然后判断 2 + 3 + 4 与 M 。

这里可以这样看：1110 中的左边第一个 1 对应着数组 [1, 2, 3, 4] 中的 1 。

现在有一个问题，该如何建立这个映射关系呢？

我们知道前者 1110 其实就是对应的外层遍历中的 i = 14 的情况。

再看看数组[1, 2, 3, 4] ，我们可以将元素及其位置分别映射为 1000 0100 0010 0001。

实现方式也是通过位运算--左位移来实现：

1 << inx ，inx 为数组的下标。

位掩码介绍

对 位掩码 不熟悉的童鞋会有点晕，这里简单科普下：

实质上，这里的 1 << j ，是指使用 1 的移位来生成其中仅设置第 j 位的位掩码。

比如：14 的二进制表示为 1110，其代表（从右往左）选取了第 2 , 3 , 4 位。

那么(下面故意写成上下对应的方式)：

// demo1
1110 & 0001 = 0000;

// demo2
1110 & 0010 = 0010;

PS: 通过上面代码，我们可以看到上下对应的 0 和 1 在进行 & 运算以后，得出的结果和在 js 中进行相同条件下 & 运算的结果相同。

所以：

1 << 0 // 1 -> 0001
1 << 1 // 2 -> 0010
1 << 2 // 4 -> 0100
1 << 3 // 8 -> 1000

// 说白了，就是把左边的值变成二进制形式，然后左移或者右移，超出补 0

// 所以， 1110 对应着 第一位没有选取，那么 1110 & 0001(设置为第一位的位掩码) = 0，如果 i & (1 << inx) !== 0 代表该位被选取了
for(let j = 0; j < arr.length; j++){
    if((i & (1 << j) !== 0) {
    // 代表这个数被选取了，我们做累加求和就行
    }
}

复制代码所以综上所述，最终代码实现如下：

// 参数依次为目标数组、选取元素数目、目标和
const search = (arr, count, sum) => {
  // 计算某选择情况下有几个 `1`，也就是选择元素的个数
  const n = num => {
    let count = 0;
    while (num) {
      num &= num - 1;
      count++;
    }
    return count;
  };

  let len = arr.length,
    bit = 1 << len,
    res = [];

  // 遍历所有的选择情况
  for (let i = 1; i < bit; i++) {
    // 满足选择的元素个数 === count
    if (n(i) === count) {
      let s = 0,
        temp = [];

      // 每一种满足个数为 N 的选择情况下，继续判断是否满足 和为 M
      for (let j = 0; j < len; j++) {
        // 建立映射，找出选择位上的元素
        if ((i & (1 << j)) !== 0) {
          s += arr[j];
          temp.push(arr[j]);
        }
      }

      // 如果这种选择情况满足和为 M
      if (s === sum) {
        res.push(temp);
      }
    }
  }

  return res;
};
复制代码

总结

这里位操作思路和代码都很棒。但是 bit 位移有溢出问题。当数组长度大于 30 的时候，位操作已经溢出不精准。因此仅供参考其思想，不能作为其标准答案。

原文地址: 从一个数组中找出 N 个数，其和为 M 的所有可能--最 nice 的解法

19-TOP-k 问题

问题: 输入 n 个整数，找出其中最大的 K 个数。例如输入 4,5,1,6,2,7,3,8 这 8 个数字，则最大的 4 个数字是 8,7,6,5,。

比较简单的是将这些数字组合成一个数组，然后进行从大到小进行排序，取前 K 个即可。

选择算法

对整个数组进行排序有点浪费，我们只是取前 K 个，后面剩下的不进行排序也行。因此，对此数组使用选择算法获取前 K 个数即可。

function getLargeNumber(array, k) {
  if (array == null || k <= 0 || k > array.length) {
    return [];
  }
  let length = array.length,
    i,
    j,
    maxIndex,
    maxValue,
    temp;
  for (i = 0; i < k; i++) {
    maxIndex = i;
    maxValue = array[maxIndex];
    for (j = i + 1; j < length; j++) {
      //通过循环选出最小的
      if (array[j] > maxValue) {
        maxIndex = j;
        maxValue = array[maxIndex];
      }
    }
    // 交换位置
    temp = array[i];
    array[i] = maxValue;
    array[maxIndex] = temp;
  }
  return array.slice(0, k);
}
// 测试一下
var nums = [8, 9, 2, 15, 7, 1];
console.log(getLargeNumber(nums, 3)); // [15,9,8]
复制代码

快排算法

我们可以利用快排中 partion 函数的思想来做做题。

因为 partion 可以使得序列分为 2 部分：左边的值都小于哨兵，右边的值都大于哨兵。所以我们只要找到处于第 k 位置的哨兵即可，也就是说找到第 k 大的值所在的位置即可，那么它的左边的 k-1 值都小于等于第 k 大值。显然，前 k 个值即为我们所求的最小 k 个数。在我们的划分过程有 3 种情况：

哨兵的位置大于 k，说明第 k 大的数在左边，继续递归处理左部分即可。
哨兵的位置小于 k，说明第 K 大的数在右边，继续递归处理有部分即可。
哨兵的位置等于 k，说明该哨兵即为第 K 大的值，其左边 k-1 个数都小于等于它，因此输出前 k 个即为所求的结果。

var nums = [8, 9, 2, 15, 7, 1, 13, 35, 24];

function getLargeNumber(array, k) {
  if (array == null || k <= 0 || k > array.length) {
    return [];
  }

  partition(array, 0, array.length - 1, k - 1);
  return array.slice(0, k);
}
function partition(array, low, high, k) {
  if (low < high) {
    // 获取 low 至 high 之间一个随机数
    let pivot = Math.floor(Math.random() * (high - low + 1)) + low;

    // 此随机数对应的元素与最后一位暂时交换（后面会再交换一次），我们先找到有多少个数大于此随机数，大的话从左到右排列
    swap(array, pivot, high);
    let index = low;
    for (let i = low; i < high; i++) {
      if (array[i] > array[high]) {
        // 这里便是一次选择排序
        swap(array, i, index);
        index++;
      }
    }
    // 交换数组第index个和刚才置于数组末尾的随机数组元素，这样array[index]左边的数都比array[index]大
    swap(array, index, high);

    // 如果index > k，说明我们刚才排的范围过大，应该缩小范围再次递归寻找
    // 如果 index < k，说明我们刚才拍的范围过小，应该扩大范围再次递归寻找
    if (index > k) {
      partition(array, low, index - 1, k);
    } else if (index < k) {
      partition(array, index + 1, high, k);
    }
  }
}

function swap(array, one, two) {
  [array[one], array[two]] = [array[two], array[one]];
}
console.log(getLargeNumber(nums, 3)); // [35,24,15]
复制代码

最小堆

我们知道，最小堆的顶部结点为该堆的最小值，因此我们创建一个具有 K 的节点的最小堆（可以先取该数组的前 K 个元素）调整为最小堆。

之后将第 K + 1 个元素与堆顶对比，如果大于堆顶元素，则说明堆顶元素不是第 K 大的值，因此将堆顶元素替换为第 K + 1 个元素，并调整此最小堆，以此类推至数组的最后一个元素，则最后整个最小堆即为所求答案。

// 建立堆
function buildHeap(nums) {
  // 注意这里的头节点是从0开始的，所以最后一个非叶子结点是 parseInt(nums.length/2)-1
  let start = parseInt(nums.length / 2) - 1;
  let size = nums.length;
  // 从最后一个非叶子结点开始调整，直至堆顶。
  for (let i = start; i >= 0; i--) {
    adjustHeap(nums, i, size);
  }
  return nums;
}
// 调整最小堆，使index的值小于于左右节点
function adjustHeap(nums, index, size) {
  // 交换后可能会破坏堆结构，需要循环使得每一个父节点都大于左右结点
  while (true) {
    let min = index;
    let left = index * 2 + 1; // 左节点
    let right = index * 2 + 2; // 右节点
    if (left < size && nums[min] > nums[left]) min = left;
    if (right < size && nums[min] > nums[right]) min = right;
    // 如果左右结点大于当前的结点则交换，并再循环一遍判断交换后的左右结点位置是否破坏了堆结构（比左右结点小了）
    if (index !== min) {
      [nums[index], nums[min]] = [nums[min], nums[index]];
      index = min;
    } else {
      break;
    }
  }
}
// 获取最大的前K个数
function getLargeNumber(nums, k) {
  // 创建一个具有 K 的节点的最小堆（可以先取该数组的前 K 个元素）调整为最小堆。
  let minHeap = buildHeap(nums.slice(0, k));
  for (let i = k; i < nums.length; i++) {
    // 将第 i 个元素与堆顶对比，如果大于堆顶元素，则说明堆顶元素不是第 K 大的值，因此将堆顶元素替换为第 i 个元素
    if (minHeap[0] < nums[i]) {
      minHeap[0] = nums[i];
      // 替换后调整此最小堆
      adjustHeap(minHeap, 0, k);
    }
  }
  return minHeap;
}
var nums = [8, 9, 2, 15, 7, 1, 13, 35, 24];

console.log(getLargeNumber(nums, 4)); // [13,15,24,35]
复制代码

20-判断一个数是否为丑数

何为丑数？丑数就是只包含质因数 2, 3, 5 的正整数。

试着写出一个函数，判断传入的是否为丑数？

function isUgly (num) {
  if (typeof +num !== 'number') return false
  if (num < 1) return false;
  // 从大往小除，先从5开始
  while(num % 5 === 0) {
      num /= 5;
  }
  while(num % 3 === 0) {
      num /= 3;
  }
  while(num % 2 === 0) {
      num /= 2;
  }
  return num === 1;
}

// 测试一下
isUgly(18) // true
isUgly(7) // false
复制代码

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020年02月14日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度