[LeetCode] 842. Split Array into Fibonacci Sequenc

zhaofeihao 發(fā)布于2019-08-16 13:50 / 2285人閱讀

Problem

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
F.length >= 3;
and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.
Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]
Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]
Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.
Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.
Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.
Note:

1 <= S.length <= 200
S contains only digits.

Solution

class Solution {
    public List splitIntoFibonacci(String S) {
        List res = new ArrayList<>();
        if (S == null) return res;
        helper(S, 0, res);
        return res;
    }
    private boolean helper(String str, int start, List res) {
        if (start == str.length() && res.size() > 2) return true;
        for (int i = start; i < str.length(); i++) {
            if (str.charAt(start) == "0" && i != start) break;
            long num = Long.parseLong(str.substring(start, i+1));
            if (num > Integer.MAX_VALUE) return false;
            int size = res.size();
            if (size >= 2 && num > res.get(size-2) + res.get(size-1)) break;
            if (size <= 1 || num == res.get(size-2) + res.get(size-1)) {
                res.add((int)num);
                if (helper(str, i+1, res)) return true;
                res.remove(res.size()-1);
            }
        }
        return false;
    }
}

GPU云服務(wù)器云服務(wù)器 LeetCode Fibonacci into merge into

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72403.html

相關(guān)文章

[Leetcode] Binary Tree Longest Consecutive Sequenc

摘要：遞歸法復(fù)雜度時(shí)間空間思路因?yàn)橐易铋L的連續(xù)路徑，我們在遍歷樹的時(shí)候需要兩個(gè)信息，一是目前連起來的路徑有多長，二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長度，左子樹長度，和右子樹長度中較大的那個(gè) Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

xi4oh4o 2019-08-14 16:16 評(píng)論0 收藏0
leetcode410. Split Array Largest Sum

摘要：在這里，邊界被設(shè)置為該數(shù)組中可以得到的子數(shù)組元素和的最小值和最大值。在確定了數(shù)組元素和的上界和下界之后，就需要找出一種方法，來不斷壓縮區(qū)間直到最后一種?？梢允褂弥虚g位置作為數(shù)組元素和的邊界，即假設(shè)所有的連續(xù)數(shù)組的和都不會(huì)超過值。題目要求 Given an array which consists of non-negative integers and an integer m, y...

Jonathan Shieber 2019-08-16 17:31 評(píng)論0 收藏0
[LintCode/LeetCode] Binary Tree Serialization

摘要：這里要注意的是的用法。所以記住，用可以從自動(dòng)分離出數(shù)組。跳過第一個(gè)元素并放入數(shù)組最快捷語句建立的用意記錄處理過的結(jié)點(diǎn)并按處理所有結(jié)點(diǎn)和自己的連接下面先通過判斷，再修改的符號(hào)的順序，十分巧妙更輕便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...

keithyau 2019-08-14 15:12 評(píng)論0 收藏0
Licia：最全最實(shí)用的 JavaScript 工具庫

摘要：為了避免不同項(xiàng)目之間進(jìn)行復(fù)制粘貼，可以將這些常用的函數(shù)封裝到一起并發(fā)布包。目前所包含模塊已達(dá)三百個(gè)，基本可以滿足前端的日常工發(fā)需求。二使用打包工具該項(xiàng)目自帶打包工具，可以通過配置文件或命令行掃描源碼自動(dòng)生成項(xiàng)目專用的工具庫。前言在業(yè)務(wù)開發(fā)過程中，我們經(jīng)常會(huì)重復(fù)使用日期格式化、cookie 操作、模板、瀏覽器判斷、類型判斷等功能。為了避免不同項(xiàng)目之間進(jìn)行復(fù)制粘貼，可以將這些常用的函數(shù)...

luxixing 2019-08-22 17:00 評(píng)論0 收藏0
JavaScript中的算法（附10道面試常見算法題解決方法和思路）

摘要：中的算法附道面試常見算法題解決方法和思路關(guān)注每日一道面試題詳解面試過程通常從最初的電話面試開始，然后是現(xiàn)場面試，檢查編程技能和文化契合度。值得記住的數(shù)組方法有和。一個(gè)好的解決方案是使用內(nèi)置的方法。 JavaScript中的算法（附10道面試常見算法題解決方法和思路）關(guān)注github每日一道面試題詳解 Introduction 面試過程通常從最初的電話面試開始，然后是現(xiàn)場面試，檢查編程...

Cruise_Chan 2019-08-26 10:22 評(píng)論0 收藏0