算法模式

[funnycoderstar]

1. 递归

1.1 JavaScript中调用栈大小的限制

1.2 斐波那契数列

2. 动态规划

2.1 最少硬币找零问题

function minCoinChange(coins, amount) {
    const cache = [];

    const makeChange = (value) => {
        if (!value) {
            return [];
        }
        if (cache[value]) {
            return cache[value];
        }
        let min = [];
        let newMin;
        let newAmount;
        for (let i = 0; i < coins.length; i++) {
            const coin = coins[i];
            newAmount = value - coin;
            if (newAmount >= 0) {
                newMin = makeChange(newAmount);
            }
            if (
                newAmount >= 0 &&
                (newMin.length < min.length - 1 || !min.length) &&
                (newMin.length || !newAmount)
            ) {
                min = [coin].concat(newMin);
                console.log('new Min ' + min + ' for ' + amount);
            }
        }
        return (cache[value] = min);
    };
    return makeChange(amount);
}
console.log(minCoinChange([1, 5, 10, 25], 36)); // [1, 10, 25];
console.log(minCoinChange.makeChange(36)); // [1, 10, 25];

2.2 背包问题

// 找出构成解决方案的物品
function findValues(n, capacity, kS) {
    let i = n;
    let k = capacity;
    console.log('解决方案包含以下物品');
    while (i > 0 && k > 0) {
        if (kS[i][k] !== kS[i - 1][k]) {
            console.log('物品' + i + ',重量' + weights[i -1] + ',价值' + values[i-1]);
            i--;
            k -= kS[i][k];
        } else {
            i--;
        }
    }
}

function knapSack(capacity, weights, values, n) {
    const kS = [];
    // 初始化将用于寻找解决方案的矩阵kS[n + 1][capacity +1];
    for (let i = 0; i <= n; i++) {
        kS[i] = [];
    }
    for (let i = 0; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            // 忽略矩阵的第一列和第一行, 只处理索引不为0的列和行
            if (i === 0 || w === 0) {
                kS[i][w] = 0;
            } else if (weights[i - 1] <= w) {
                // 物品的重量必须小于约束(capacity)才有可能称为解决方案的一部分
                const a = values[i - 1] + kS[i - 1][w - weights[i - 1]];
                const b = kS[i - 1][w];
                // 当找到可以构成解决方案的物品时, 选择价值最大的那个
                kS[i][w] = a > b ? a : b; // max(a,b)
            } else {
                // 否则, 总重量就会超出背包能够携带的重量, 此时忽略, 用之前的值
                kS[i][w] = kS[i - 1][w];
            }
        }
    }
    findValues(n, capacity, kS);
    return kS[n][capacity];
}
var values = [3, 4, 5],
weights = [2, 3, 4],
capacity = 5,
n = values.length;
console.log(knapSack(capacity, weights, values, n)); // 输出7

2.3 最长公共子序列

找出两个字符串序列的最长子序列(在两个字符串序列中以相同顺序出现, 但不要求连续(非字符串子串)的字符串序列)的长度

function printSolution(solution, wordX, m, n) {
    let a = m;
    let b = n;
    let x = solution[a][b];
    let answer = '';
    while (x !== '0') {
        if (solution[a][b] === 'diagonal') {
            answer = wordX[a - 1] + answer;
            a--;
            b--;
        } else if (solution[a][b] === 'left') {
            b--;
        } else if (solution[a][b] === 'top') {
            a--;
        }
        x = solution[a][b];
    }
    return answer;
}
function lcs(wordX, wordY) {
    const m = wordX.length;
    const n = wordY.length;
    const l = [];
    const solution = [];
    for (let i = 0; i <= m; i++) {
        l[i] = [];
        solution[i] = [];
        for (let j = 0; j <= n; j++) {
            l[i][j] = 0;
            solution[i][j] = '0';
        }
    }
    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            if (i === 0 || j === 0) {
                l[i][j] = 0;
            } else if (wordX[i - 1] === wordY[j - 1]) {
                l[i][j] = l[i - 1][j - 1] + 1;
                solution[i][j] = 'diagonal';
            } else {
                const a = l[i - 1][j];
                const b = l[i][j - 1];
                l[i][j] = a > b ? a : b; // max(a,b)
                solution[i][j] = l[i][j] === l[i - 1][j] ? 'top' : 'left';
            }
        }
    }
    return printSolution(solution, wordX, m, n);
}