凑数（2）
创作者俱乐部成员
还是凑数问题，从一组数里，找出满足求和的子组合。
昨天的代码里，每次尝试放入dat一个项目之后，会先对dat求和，然后比较判断
求和这一步浪费了大量时间，其实每次递归，可以记住上次求和的结果，每次尝试放入项目之后，只需要进行一次相加
简单说就是用空间换时间，缓存上次求和的结果
| 🔔 | function* cs(arr, s) { arr.sort((x,y)=>x-y) let len = arr.length let dat = [] yield* rec(0, 0, 0) function* rec(start, index, cur) { if (index === len) return for (let i = start; i < len; i++) { dat[index] = arr[i] let acc = cur + arr[i] if (acc < s) { yield* rec(i + 1, index + 1, acc) } else if (acc === s) { yield dat.slice(0, index + 1) } else { return } } } } function coushu1(rng, s) { Application.Volatile(0) return JSON.stringify(cs(rng().flat(), parseInt(s)).next().value) } function coushu(rng, s) { Application.Volatile(0) return [...cs(rng().flat(), parseInt(s))].map(x=>[JSON.stringify(x)]) } |
修改之后，处理几十个数不算太卡了，有点实用价值了，不过应该可以继续优化😁
半夜醒了，水一贴，继续睡。。。
创作者俱乐部成员