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.
class Solution { public ListsplitIntoFibonacci(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; } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/72403.html
摘要:遞歸法復(fù)雜度時(shí)間空間思路因?yàn)橐易铋L(zhǎng)的連續(xù)路徑,我們?cè)诒闅v樹(shù)的時(shí)候需要兩個(gè)信息,一是目前連起來(lái)的路徑有多長(zhǎng),二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長(zhǎng)度,左子樹(shù)長(zhǎng)度,和右子樹(shù)長(zhǎng)度中較大的那個(gè) Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...
摘要:在這里,邊界被設(shè)置為該數(shù)組中可以得到的子數(shù)組元素和的最小值和最大值。在確定了數(shù)組元素和的上界和下界之后,就需要找出一種方法,來(lái)不斷壓縮區(qū)間直到最后一種。可以使用中間位置作為數(shù)組元素和的邊界,即假設(shè)所有的連續(xù)數(shù)組的和都不會(huì)超過(guò)值。 題目要求 Given an array which consists of non-negative integers and an integer m, y...
摘要:這里要注意的是的用法。所以記住,用可以從自動(dòng)分離出數(shù)組。跳過(guò)第一個(gè)元素并放入數(shù)組最快捷語(yǔ)句建立的用意記錄處理過(guò)的結(jié)點(diǎn)并按處理所有結(jié)點(diǎn)和自己的連接下面先通過(guò)判斷,再修改的符號(hào)的順序,十分巧妙更輕便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...
摘要:為了避免不同項(xiàng)目之間進(jìn)行復(fù)制粘貼,可以將這些常用的函數(shù)封裝到一起并發(fā)布包。目前所包含模塊已達(dá)三百個(gè),基本可以滿足前端的日常工發(fā)需求。二使用打包工具該項(xiàng)目自帶打包工具,可以通過(guò)配置文件或命令行掃描源碼自動(dòng)生成項(xiàng)目專(zhuān)用的工具庫(kù)。 前言 在業(yè)務(wù)開(kāi)發(fā)過(guò)程中,我們經(jīng)常會(huì)重復(fù)使用日期格式化、cookie 操作、模板、瀏覽器判斷、類(lèi)型判斷等功能。為了避免不同項(xiàng)目之間進(jìn)行復(fù)制粘貼,可以將這些常用的函數(shù)...
摘要:中的算法附道面試常見(jiàn)算法題解決方法和思路關(guān)注每日一道面試題詳解面試過(guò)程通常從最初的電話面試開(kāi)始,然后是現(xiàn)場(chǎng)面試,檢查編程技能和文化契合度。值得記住的數(shù)組方法有和。一個(gè)好的解決方案是使用內(nèi)置的方法。 JavaScript中的算法(附10道面試常見(jiàn)算法題解決方法和思路) 關(guān)注github每日一道面試題詳解 Introduction 面試過(guò)程通常從最初的電話面試開(kāi)始,然后是現(xiàn)場(chǎng)面試,檢查編程...
閱讀 2260·2023-04-25 14:50
閱讀 1234·2021-10-13 09:50
閱讀 1866·2019-08-30 15:56
閱讀 1839·2019-08-29 15:29
閱讀 2887·2019-08-29 15:27
閱讀 3548·2019-08-29 15:14
閱讀 1192·2019-08-29 13:01
閱讀 3299·2019-08-26 14:06