20201208
给定一个数字字符串 S,比如 S = "123456579",我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上,斐波那契式序列是一个非负整数列表 F,且满足:
- 1,(也就是说,每个整数都符合 32 位有符号整数类型);
另外,请注意,将字符串拆分成小块时,每个块的数字一定不要以零开头,除非这个块是数字 0 本身。
返回从 S 拆分出来的任意一组斐波那契式的序列块,如果不能拆分则返回 []。
输入:"123456579"
输出:[123,456,579]
输入: "11235813"
输出: [1,1,2,3,5,8,13]
输入: "112358130"
输出: []
解释: 这项任务无法完成。
输入:"0123"
输出:[]
解释:每个块的数字不能以零开头,因此 "01","2","3" 不是有效答案。
输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。
提示:
枚举某个数的过程,假设其前面已经存在满足条件组合(起点 i=3)
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
.. | .. | .. | 4 | 45 | 456 | 4567 | 45678 | 456789 |
注意:
-1 直接结束枚举
抛砖引玉
/**
* @param {string} S
* @return {number[]}
*/
var splitIntoFibonacci = function(S) {
let len = S.length,
_result = []
function helper(list, index, sum, prev) {
let num = 0
if (index === len) return list.length >= 3
for (let i = index; i < len; i++) {
if (i > index && +S[index] === 0) return false
num = num * 10 + parseInt(S[i])
// 溢出
if (num > 2 ** 31 - 1) return false
if (list.length >= 2) {
// 如果新数据小于上一轮两数和,则需要继续拼接
if (num > sum) return false
if (num < sum) continue
}
list.push(num)
if (helper(list, i + 1, prev + num, num)) return true
// 回溯
list.pop()
}
return false
}
helper(_result, 0, 0, 0)
return _result
}
上面写法在递归中传递上一轮两数和(即已经得到的组合的最后两位之和),和当前组合出来的数组。
其实这两个数字都已经存在 list(组合)中了,那么如果不通过参数传递也是可以通过 list 中取到
/**
* @param {string} S
* @return {number[]}
*/
var splitIntoFibonacci = function(S) {
let len = S.length,
_result = Array()
function helper(index, list) {
let num = 0
// 递归到结束时,序列d长度至少要大于3才能形成斐波那契序列
if (index === len) return list.length >= 3
// 新追加的元素需要等于list最后两个元素的和
for (let i = index; i < len; i++) {
num = 10 * num + parseInt(S[i])
if (num > 2 ** 31 - 1) return false
const L = list.length
if (L >= 2 && num === list[L - 1] + list[L - 2]) {
list.push(num)
if (helper(i + 1, list)) return true
// 回溯
list.pop()
}
// 拼接的和不满足向后拼接时:除了数字0之外,0不能作为新数字的起点
if (parseInt(S[i]) === 0 && i === index) return false
}
return false
}
return helper(0, _result) ? _result : []
}
博客: 前端小书童
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号:前端小书童