近期遇到的计(算)算(法)题及解(javascript)

以下是近期遇到的三个计(算)算(法)题... 提到这些问题的时候简单理了下思路,后面又以JavaScript代码实现并顺便记个笔记...

问题一:从无序数组里取出M个值,总和为N,得出一个解即可

思路:

  1. 递归直到长度为M为止,得出数组子集;
  2. 对得出的数组子集进行计算,如果相加的和等于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不到。两种方法在nodejs端皆可用,前者效率是后者的10倍,所以...就直接贴了效率较佳的代码。

先说思路:

  1. 考虑到回文长度奇偶的区别,预先处理字符串,中间加_连接;
  2. 以字符串做循环,分别以当前索引的字符为中心将两边的值做比较,如果是回文,则返回回文长度的1/2;
  3. 如果回文长度大于当前存的最长回文长度变量的值,则更新最长回文长度变量和最长回文中心索引值变量;
  4. 当字符串长度减去循环中心小于最长回文长度变量,则说明以右边字符为中心的回文不会比当前获得的最长回文长了,就不用继续浪费计算资源了。

代码如下:

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编程(前端切图仔的身份不能忘),辅补算法知识。

上一篇:如果非得了解下git系统... - 实践篇


下一篇:分步理解 Promise 的实现