将数组拆分成斐波那契序列

「爱情、让人受尽委屈。」 2022-12-27 06:25 165阅读 0赞

> leetcode 842题 \[medium\]  
> 中：[将数组拆分成斐波那契序列][Link 1]  
> 英：[Split Array Into Fibonacci Sequence][]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70 1]

### 题解 ###

##### 1. 思路（回溯 + 剪枝） #####

1.  其实主要就是确定斐波那契数列的第1、2个数，后边的相应就确定了

##### 2. 时间复杂度：O(nlog²C) #####

1.  其中 n 是字符串的长度，C 是题目规定的整数范围  2 31 − 1 2^\{31\}−1 231−1
2.  真正回溯的空间只有斐波那契数列的前两个数，后边的遍历只是做检测

##### 3. 空间复杂度：O(n) 记录结果 #####

##### 4. 实现 #####

/** * @param {string} S * @return {number[]} */
    var splitIntoFibonacci = function(S) { 
        // 预处理
        if(S.length < 3) return [];
        let sLen = S.length;
        let CURR_MAX_INT = Math.pow(2, 31) - 1; // 题目中要求的Fibonacci的最大值
    
        // 回溯，剪枝
        // 剪枝1：firstEnd < Math.ceil(sLen / 2) 所剩位数必须 >= 第一个数字的位数
        for(let firstEnd = 1; firstEnd < Math.ceil(sLen / 2); firstEnd++){     // firstEnd右开
            // 第一层循环，构建Fibonacci第1个数字
            let firstStr = S.slice(0, firstEnd);
            let first = Number(firstStr);
            // 溢出与0开头
            if(first > CURR_MAX_INT) break;    // 溢出
            if(firstStr.length !== first.toString().length) break;  // 0开头的非0数字
    
            // 剪枝2：secondEnd <= ( sLen - Math.max(firstEnd, Math.ceil((sLen-firstEnd) / 2)) ) 取前两个数后，剩下位数必须 >= 前两个数字的最大位数 
            for(let secondEnd = firstEnd + 1; secondEnd <= ( sLen - Math.max(firstEnd, Math.ceil((sLen-firstEnd) / 2)) ); secondEnd++){   // secondEnd右开
                // 第二层循环，构建Fibonacci第2个数字
                let secondStr = S.slice(firstEnd, secondEnd);
                let second = Number(secondStr);
                // 溢出与0开头
                if(second > CURR_MAX_INT) break;    // 溢出
                if(secondStr.length !== second.toString().length) break;    // 0开头的非0数字
                
                // 斐波那契判断
                let pre = first, curr = second;
                let next = pre + curr;
                let lastEnd = secondEnd;        // 已检索的idx尾部(开区间，相当于下一次检索的开头)
                let currResult = [pre, curr];   // 记录当前符合Fibonacci的结果
                while(lastEnd < sLen){ 
                    if(next > CURR_MAX_INT) break;  // 溢出
    
                    let findNextStr = S.substr(lastEnd, next.toString().length);
                    let findNext = Number(findNextStr)
                    if(findNextStr.length !== findNext.toString().length) break;    // 0开头的非0数字
    
                    if(findNext === next){ 
                        pre = curr;
                        curr = next;
                        next = pre + curr;
                        lastEnd += curr.toString().length;
                        currResult.push(curr);
                    }
                    else break; // 不符合斐波那契数列
                }
                if(lastEnd === sLen) { 
                    // 找到符合条件的斐波那契数列
                    return currResult;
                }
            }
        }
        return [];
    };

[Link 1]: https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/
[Split Array Into Fibonacci Sequence]: https://leetcode.com/problems/split-array-into-fibonacci-sequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201208115545384.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/4deb4a367647447799c0db96e45fc34f.png