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

Categories:

题目描述
思路分析
1. 解法一：回溯（推荐）
相似题目

题目描述

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

思路分析

解法一：回溯（推荐）

核心思路：

从左到右枚举数字作为序列元素，要求不超过 32 位整数范围。

若已有两个以上元素，则必须满足斐波那契和关系。

成功遍历到末尾即得到答案。

复杂度分析：

时间复杂度：O(2^n)，其中 n 表示字符串长度。

空间复杂度：O(n)，用于递归栈与路径。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> splitIntoFibonacci(String num) {
        List<Integer> res = new ArrayList<>();
        dfs(num, 0, res);
        return res;
    }

    private boolean dfs(String num, int index, List<Integer> path) {
        if (index == num.length()) {
            return path.size() >= 3;
        }

        long value = 0;
        for (int i = index; i < num.length(); i++) {
            if (i > index && num.charAt(index) == '0') {
                break;
            }
            value = value * 10 + (num.charAt(i) - '0');
            if (value > Integer.MAX_VALUE) {
                break;
            }

            int size = path.size();
            if (size >= 2) {
                long sum = (long) path.get(size - 1) + path.get(size - 2);
                if (value < sum) {
                    continue;
                }
                if (value > sum) {
                    break;
                }
            }

            path.add((int) value);
            if (dfs(num, i + 1, path)) {
                return true;
            }
            path.remove(path.size() - 1);
        }

        return false;
    }
}

func splitIntoFibonacci(num string) []int {
	path := make([]int, 0)
	var dfs func(idx int) bool

	dfs = func(idx int) bool {
		if idx == len(num) {
			return len(path) >= 3
		}

		value := int64(0)
		for i := idx; i < len(num); i++ {
			if i > idx && num[idx] == '0' {
				break
			}
			value = value*10 + int64(num[i]-'0')
			if value > int64(^uint32(0)>>1) {
				break
			}

			if len(path) >= 2 {
				sum := int64(path[len(path)-1] + path[len(path)-2])
				if value < sum {
					continue
				}
				if value > sum {
					break
				}
			}

			path = append(path, int(value))
			if dfs(i + 1) {
				return true
			}
			path = path[:len(path)-1]
		}

		return false
	}

	dfs(0)
	return path
}

相似题目

题目	难度	考察点
306. 累加数	中等	回溯
93. 复原 IP 地址	中等	回溯
77. 组合	中等	回溯
131. 分割回文串	中等	回溯
842. 将数组拆分成斐波那契序列	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/53597550