当前位置:网站首页>leetcode842. Split the array into Fibonacci sequences
leetcode842. Split the array into Fibonacci sequences
2022-07-04 10:17:00 【JoesonChan】
subject
Given a string of numbers S, such as S = "123456579", We can divide it into Fibonacci sequences [123, 456, 579].
Formally , The Fibonacci sequence is a list of nonnegative integers F, And meet :
- 0 <= F[i] <= 2^31 - 1,( in other words , Every integer matches 32 Bit signed integer type );
- F.length >= 3;
- For all 0 <= i < F.length - 2, There are F[i] + F[i+1] = F[i+2] establish .
in addition , Please note that , When you split a string into small pieces , The number of each block must not start with zero , Unless this block is a number 0 In itself .
Return from S Any set of Fibonacci sequence blocks that are split out , If it can't be split, return [].
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 : []
explain : The task cannot be accomplished .
Example 4:
Input :"0123"
Output :[]
explain : The number of each block cannot start with zero , therefore "01","2","3" Not a valid answer .
Example 5:
Input : "1101111"
Output : [110, 1, 111]
explain : Output [11,0,11,11] It's also accepted .
Tips :
- 1 <= S.length <= 200
- character string S There are only numbers in it .
public static List<Integer> _143_fabonaci(String text) {
List<Integer> result = new ArrayList<>();
boolean suc = dfsFabonaci(text.toCharArray(), 0, result);
// If you return true, explain result The array satisfies the Fibonacci sequence
return suc ? result : new ArrayList<>();
}
private static boolean dfsFabonaci(char[] chars, int index, List<Integer> result) {
if (index == chars.length && result.size() >= 3) {
return true;
}
if (index == chars.length) {
return false;
}
Long num = 0L;
int cursor = index;
while (cursor < chars.length) {
num = num * 10 + (chars[cursor] - '0');
if (num > Integer.MAX_VALUE) {
break;
}
// The current number exceeds the previous two , prune
if ((result.size() >= 2 && result.get(result.size() - 1) + result.get(result.size() - 2) < num.intValue())) {
break;
}
// The current list is less than two , Or the first two sums of the current list are equal to the current value , Recursion
if ((result.size() < 2 || result.get(result.size() - 1) + result.get(result.size() - 2) == num.intValue())) {
result.add(num.intValue());
boolean res = dfsFabonaci(chars, cursor + 1, result);
if (res) {
return true;
}
result.remove(result.size() - 1);
}
// If you encounter 0, There is no need to continue , prevent 0xx Numbers
if (num == 0L) {
break;
}
cursor++;
}
return false;
}
边栏推荐
- Press the button wizard to learn how to fight monsters - identify the map, run the map, enter the gang and identify NPC
- 查看CSDN个人资源下载明细
- PHP code audit 3 - system reload vulnerability
- Work order management system OTRs
- 技术管理进阶——如何设计并跟进不同层级同学的绩效
- Deep learning 500 questions
- Vs201 solution to failure to open source file HPP (or link library file)
- Exercise 9-3 plane vector addition (15 points)
- Hands on deep learning (III) -- Torch Operation (sorting out documents in detail)
- Batch distribution of SSH keys and batch execution of ansible
猜你喜欢
品牌连锁店5G/4G无线组网方案
直方图均衡化
智慧路灯杆水库区安全监测应用
Work order management system OTRs
Fabric of kubernetes CNI plug-in
Write a mobile date selector component by yourself
智能网关助力提高工业数据采集和利用
Machine learning -- neural network (IV): BP neural network
Basic principle of servlet and application of common API methods
Debug:==42==ERROR: AddressSanitizer: heap-buffer-overflow on address
随机推荐
Sword finger offer 31 Stack push in and pop-up sequence
六月份阶段性大总结之Doris/Clickhouse/Hudi一网打尽
7-17 crawling worms (15 points)
MySQL case
Dynamic address book
Golang Modules
C语言指针经典面试题——第一弹
MongoDB数据日期显示相差8小时 原因和解决方案
How can people not love the amazing design of XXL job
Reprint: summation formula of proportional series and its derivation process
基于线性函数近似的安全强化学习 Safe RL with Linear Function Approximation 翻译 1
System. Currenttimemillis() and system Nanotime (), which is faster? Don't use it wrong!
C # use smtpclient The sendasync method fails to send mail, and always returns canceled
A little feeling
If the uniapp is less than 1000, it will be displayed according to the original number. If the number exceeds 1000, it will be converted into 10w+ 1.3k+ display
Go context basic introduction
5g/4g wireless networking scheme for brand chain stores
Vs201 solution to failure to open source file HPP (or link library file)
What are the advantages of automation?
Use the data to tell you where is the most difficult province for the college entrance examination!