以下是近期遇到的三个计 (算) 算(法)题... 提到这些问题的时候简单理了下思路, 后面又以 JavaScript 代码实现并顺便记个笔记...
问题一: 从无序数组里取出 M 个值, 总和为 N, 得出一个解即可
思路:
递归直到长度为 M 为止, 得出数组子集;
对得出的数组子集进行计算, 如果相加的和等于 N(如果设置容差 T, 则相加的和与 N 的差距小于容差 T), 则将子集数据存入 combArr;
2.1. 默认只取第一个值, 取到后跳出循环;
2.2. 如果设置取所有结果, 则继续循环求之后的子集.
代码如下:
- const arr = [14, 30, 38, 15, 34, 20, 10, 5, 35, 32, 27, 11, 9, 50, 21, 29, 3, 47, 26, 39, 18, 17, 40, 37, 49, 23, 22, 43, 33, 1, 24, 8, 16, 12, 25, 28, 48, 2, 41, 44, 45, 46, 4, 13, 42, 36, 31, 19, 6, 7];
- // 参数 数组 数量 总和 容差 是否取全部结果
- function getCombination(array, count, sum, tolerance, allResult) {
- const combArr = [];
- const $tolerance = isNaN(tolerance) ? 0 : tolerance;
- if (!count || isNaN(count)) {;
- return combArr.push([]), combArr;
- }
- // 是否取所有结果
- let getAllResult = false;
- const generateIdxComb = ($originArray, $count, $array) => {
- if ($count === 0) {
- const $sum = $originArray.reduce((a, b) => a + b);
- if (Math.abs(sum - $sum) <= $tolerance) {
- combArr.push($originArray);
- if (allResult) {
- getAllResult = true;
- }
- }
- return;
- }
- for (let i = 0, len = $array.length; i <= len - $count; i++) {
- if (combArr.length && !getAllResult) {
- break;
- }
- generateIdxComb($originArray.concat($array[i]), $count - 1, $array.slice(i + 1));
- }
- }
- // 递归取子集
- (generateIdxComb)([], count, array);
- return combArr;
- }
- getCombination(arr, 3, 21);
- // output [[14, 5, 2]]
- getCombination(arr, 3, 21, 0, true);
- // output [[14, 5, 2],[14, 3, 4],...] 27 个组合
问题一的扩展, 背包问题: 给定一组物品, 每种物品都有自己的重量和价格, 在限定的总重量内, 我们如何选择, 才能使得物品的总价格最高.
在上面的代码做判断条件的修改:
- const arr = [{weight: 1,price: 15}, {weight: 3,price: 12}, {weight: 5,price: 16}, {weight: 6,price: 9}, {weight: 7,price: 18}, {weight: 9,price: 11}];
- // 数组 数量 限定值
- function getMaxComb(array, count, sum) {
- let combArr = [];
- let totalPrice = 0;
- if (!count || isNaN(count)) {;
- return combArr;
- }
- const generateIdxComb = ($originArray, $count, $array) => {
- if ($count === 0) {
- const $sumWeight = $originArray.reduce((a, b) => a + b.weight, 0);
- if ($sumWeight <= sum) {
- const $totalPrice = $originArray.reduce((a, b) => a + b.price, 0);
- if ($totalPrice> totalPrice) {
- totalPrice = $totalPrice;
- combArr = $originArray;
- }
- };
- return;
- }
- for (let i = 0, len = $array.length; i <= len - $count; i++) {
- generateIdxComb($originArray.concat($array[i]), $count - 1, $array.slice(i + 1));
- }
- }
- // 递归取子集
- (generateIdxComb)([], count, array);
- return combArr;
- }
- getMaxComb(arr, 3, 17);
- // output [{"weight":1,"price":15},{"weight":5,"price":16},{"weight":7,"price":18}]
问题二: 取一串字符串里的最长回文
关于这个问题, 理了 2 种思路, 一种是空间换时间的, 但是在浏览器跑 1W 以上长度的字符串就导致浏览器奔溃; 下面代码中的是另外一种, 在浏览器跑了个 10000 长度字符串的时间为 200ms 不到. 两种方法在 Node.JS 端皆可用, 前者效率是后者的 10 倍, 所以... 就直接贴了效率较佳的代码.
先说思路:
考虑到回文长度奇偶的区别, 预先处理字符串, 中间加_连接;
以字符串做循环, 分别以当前索引的字符为中心将两边的值做比较, 如果是回文, 则返回回文长度的 1/2;
如果回文长度大于当前存的最长回文长度变量的值, 则更新最长回文长度变量和最长回文中心索引值变量;
当字符串长度减去循环中心小于最长回文长度变量, 则说明以右边字符为中心的回文不会比当前获得的最长回文长了, 就不用继续浪费计算资源了.
代码如下:
- function getLongestPalindrome($value) {
- // 考虑到回文长度是偶数的情况
- value = $value.split('').join('_');
- // 存最长回文长度 (其实是长度的 1/2; 从 doCkeck 中可以看出, 返回的仅是循环的值)
- let longestPalindromeLen = 0;
- // 存最长回文的中心索引值
- let palindromeCenter = 0;
- // 数组长度
- const len = value.length;
- // 回文检测
- function doCheck(idx, value) {
- let i = 0;
- for (; i <= idx; i++) {
- if (value[idx - i] !== value[idx + i]) {
- break;
- }
- }
- // 注意这里返回的是 i - 1, 所以其实取到的是回文长度的 1/2
- return i - 1;
- }
- // 遍历数组
- for (let i = 0; i <len; i++) {
- // 省掉后续的一些判断, 因为这时候以右边字符为中心的回文长度已经小于等于最长回文了
- if (len - i < longestPalindromeLen) {
- break;
- }
- const checkResult = doCheck(i, value);
- if (checkResult && checkResult> longestPalindromeLen) {
- longestPalindromeLen = checkResult;
- palindromeCenter = i;
- }
- }
- // 组成结果
- let str = value.slice(palindromeCenter - longestPalindromeLen, palindromeCenter + longestPalindromeLen + 1).replace(/_/g, '');
- return str;
- }
- getLongestPalindrome('aba');
- // output 'aba'
- getLongestPalindrome('adaceebdsdbeecabd');
- // output 'aceebdsdbeeca'
- getLongestPalindrome('abbac');
- // output 'abba'
- getLongestPalindrome('12345678765432');
- // output '2345678765432'
问题三: 下面矩阵中, 从 1 到 10 的路径中取路径值相加最大的路径.
- 1 - 30 - 15 - 34 - 23
- | | | | |
- 20 - 6 - 8 - 27 - 19
- | | | | |
- 35 - 11 - 9 - 21 - 7
- | | | | |
- 29 - 3 - 50 - 18 - 10
思路:
1 . 分别从 右 和 下 出发, 判断两个方向的较大值, 作为到路径节点为止的最大值, 这样便能够得到最大的路径的值. 如下 1-30-6 和 1-20-6 ,37> 27, 则该节点值为 37, 以此类推, 得出:
- 1 - 31 - 46 - 80 - 103
- | | | | |
- 21 - 37 - 54 - 107 - 126
- | | | | |
- 56 - 67 - 76 - 128 - 135
- | | | | |
- 85 - 88 - 138 - 156 - 166
2 . 计算并且输出最优路径. 上面得到了最大的值为 166 , 根据 166 开始反推:
156> 135, 得出 右
138> 128, 得出 右
88> 76, 得出 右
85> 67, 得出 右
85 之后只能向上反推, 得出 3 个下
给出结果: 下下下右右右右
代码如下:
- const arr = [
- [1, 30, 15, 34, 23],
- [20, 6, 8, 27, 19],
- [35, 11, 9, 21, 7],
- [29, 3, 50, 18, 10]
- ];
- function calcPath(matrix) {
- // 存相加的值用
- const bestPathSum = [];
- for (let i = 0; i <matrix.length; i++) {
- bestPathSum.push([]);
- }
- // 求路径过程, 如 1-2-3 3 个数当中只有 2 个 "-", 可得路径过程 = 路径长度 - 1
- let bestPathValue = [];
- const RIGHT = '右';
- const DOWN = '下';
- let goDownLen = matrix.length - 1;
- let goRightLen = matrix[0].length - 1;
- // 二维数组计算, 取最大值作为存储
- for (let i = 0; i < arr.length; i++) {
- for (let j = 0; j < arr[i].length; j++) {
- // 第一步设置第一个值作为基础
- if (i === 0 && j === 0) {
- bestPathSum[i][j] = matrix[i][j];
- } else if (i === 0) {
- // 第一个数组往右计算
- bestPathSum[i][j] = bestPathSum[i][j - 1] + matrix[i][j];
- } else if (j === 0) {
- // 多个数组以第一个值往下计算
- bestPathSum[i][j] = bestPathSum[i - 1][j] + matrix[i][j];
- } else {
- // 除索引 0 外的其他值计算
- bestPathSum[i][j] = Math.max(bestPathSum[i - 1][j], bestPathSum[i][j - 1]) + matrix[i][j];
- }
- }
- }
- // 输出路径
- for (let i = goDownLen + goRightLen; i> 0; i--) {
- if (goDownLen === 0) {
- goRightLen--;
- bestPathValue.push(RIGHT);
- } else if (goRightLen === 0) {
- goDownLen--;
- bestPathValue.push(DOWN);
- } else {
- if (bestPathSum[goDownLen][goRightLen - 1]> bestPathSum[goDownLen - 1][goRightLen]) {
- goRightLen--;
- bestPathValue.push(RIGHT);
- } else {
- goDownLen--;
- bestPathValue.push(DOWN);
- }
- }
- }
- const result = {
- bestPath: bestPathValue.reverse().join('-'),
- maxValue: bestPathSum[bestPathSum.length - 1][bestPathSum[0].length - 1]
- }
- return result;
- }
- calcPath(arr);
- // output {bestPath: "下 - 下 - 下 - 右 - 右 - 右 - 右", maxValue: 166}
至于上面的时间复杂度和空间复杂度结果计算, 由于这块知识还不是很稳(还在学习中...), 就先不给出计算结果了... 再理解理解复杂度计算过程再说... 先以运行结果给出结论.
2018 年刷完部分网络基础知识, 整理出了 18 篇阅读时的笔记, 其中一些例子的计算过程是通过新建场景来计算得出, 确保理解的正确, 有兴趣的同学可以往前翻一翻随笔.
最后顺便定个 2019 年小目标: 主学 JavaScript 编程(前端切图仔的身份不能忘), 辅补算法知识.
来源: https://yq.aliyun.com/articles/688720