算法问题：根据和值得到组成的数组

  • Z时代
  • 2024-03-05
  • 分类：IT

题目描述

根据输入的值，得到相加等于这个值的固定长度数组。
比如用户输入10，需要得到固定长度为3且每一位不超过5的组合数组，比如得到：
[1,4,5]，[2,3,5]等等。
当用户输入的数值比较大 和要求返回的数组长度比较大时，如何优化效率。
//
输入一个正整数N，获取全部可组成N的数组，数组的长度为M，并且数组中的元素不允许重复，数组中元素的值大于0小于P

回答：

你这题在leetcode中有类似的：组合总和 III

只不过里面最大值是9，那你换成动态的就可以，直接拿题解中的回答「手画图解」明确用于剪枝的约束条件改一点点点点就可以了

const combinationSum = (k, n, max = 9) => {
  const res = []; 
  // 基于当前已选的comb数组(和为sum)，在数start到数9中继续选
  const dfs = (start, comb, sum) => { 
    if (comb.length == k) {     // 选够k个数 结束递归
      if (sum == n) {           // 组合中数之和等于n
        res.push(comb.slice()); // 将它的拷贝加入解集
      }
      return;
    }
    for (let i = start; i <= max; i++) { // 枚举出所有的选择（选项）
      comb.push(i);                    // 作出一个选择i
      dfs(i + 1, comb, sum + i);       // 基于该选择i，往下递归
      comb.pop();                      // 撤销这个选择
    }
  };
  dfs(1, [], 0);  // 入口
  return res;
};
combinationSum(3, 10, 5)
// [1, 4, 5]
// [2, 3, 5]
已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ，欢迎正在阅读的你也加入。

回答：

个人觉得你可能是想要一个红包开奖算法，类似红包一共 200 元，分成 10 , 每个最大限制 30 元；

如果是红包问题的话因为存在一些不确定性，就不需要枚举所有可能，并且还可以按照线性复杂度得到想要的其中一个可能，具体看代码：

const redPacket = (money, num, max) => {
    let remain = money, res = [];
    for (let i = 0; i < num; i++) {
        let min = Math.ceil(remain - max * (num - i - 1));
        min = Math.max(min, 0);
        const iMax = Math.min(remain, max);
        const m = Math.round(Math.random() * (iMax - min) + min);
        res.push(m);
        remain -= m;
    }
    return res;
}
console.log(redPacket(10, 3, 5));
// [ 1, 5, 4 ]
console.log(redPacket(10, 3, 5));
// [ 2, 4, 4 ]

同时也可以把函数拆分成按步进行，这样对未来总是处在一种不可预测的状态， 我这里用 yield 迭代模拟，你自己可以把函数中的参数字节修改成 剩余金额剩余还需要开的红包数量最大值 然后把 for 循环去掉就可以做到调用一次开一次红包的功能；

const redPacketOpen = function* (money, num, max) {
    let remain = money, res = [];
    for (let i = 0; i < num; i++) {
        let min = Math.ceil(remain - max * (num - i - 1));
        min = Math.max(min, 0);
        const iMax = Math.min(remain, max);
        const m = Math.round(Math.random() * (iMax - min) + min);
        res.push(m);
        remain -= m;
        yield m;
    }
    return res;
}
const p = redPacketOpen(10, 3, 5);
console.log( p.next().value ); // 5
console.log( p.next().value ); // 2
console.log( p.next().value ); // 3

以上是 算法问题：根据和值得到组成的数组 的全部内容， 来源链接： utcz.com/p/944517.html

回到顶部