算法问题:鸡块有 7/13/29 三种规格,老板让你买 n 块,如何计算是否可行

平静的格子
  • 1
新手上路,请多包涵

问题:在一个平行宇宙中,麦当劳的麦乐鸡块分为 7 块装、13 块装和 29 块装。有一天,你的老板让你出去购买正好为 n 块(0 < n <= 10000)的麦乐鸡块回来,请提供一个算法判断是否可行。

说明:除了三重循环的解法,有没有效率更高一点的方法。求大佬指点。

回复
阅读 1.4k
3 个回答
const checkNuggets = (nuggets) => {
    let temp = []
    temp[7] = true
    temp[13]-= true
    temp[29] = true
    for (let i = 7; i < nuggets; i+= 1) {
        if (temp[i]) {
            temp[i + 7] = true
            temp[i + 13] = true
            temp[i + 29] = true
        } else continue
    }
    return !!temp[nuggets]
}

console.log(checkNuggets(25)) // false
console.log(checkNuggets(26)) // true
console.log(checkNuggets(27)) // true
console.log(checkNuggets(28)) // true
console.log(checkNuggets(29)) // true
console.log(checkNuggets(30)) // false

image.png

取巧的一个思路,反正 n块(0< n <= 10000)

  1. 直接拿到 0-10000 里 7,13,29 所有可能构成的取值,建立哈希表,结束了
  2. 效率肯定很高
function countAll(i, j, k, total) {
    if ((i * 7 + j * 13 + 29 * k) > total) {
        return false;
    }
    if (total === 7 || total === 13 || total === 29) {
        return true;
    }
    if (isVoid(i, j, k, total)) {
        return true;
    } else {
        return countAll(i, j, k + 1 , total) || countAll(i , j + 1, k , total) || countAll(i + 1, j , k , total) ||  false;
    }
}

function isVoid(i, j, k, total) {
    let value = i * 7 + j * 13 + 29 * k;
    if (total % value == 0 && value !== 0) {
        console.log(i , j  , k);
        return true;
    }
    return false;
}
var res = countAll(0, 0 , 0 ,9892);
console.log(res);

递归实现

宣传栏