GuilinDev

Lc0842

05 August 2008

842 Split Array into Fibonacci Sequence

题目

Given a string 

1

S
of digits, such as 
1

S = "123456579"
, we can split it into a Fibonacci-like sequence 
1

[123, 456, 579].

Formally, a Fibonacci-like sequence is a list 

1

F
of non-negative integers such that:

  • 1

    0 <= F[i] <= 2^31 - 1
    , (that is, each integer fits a 32-bit signed integer type);
  • 1

    F.length >= 3
    ;
  • and 
    1

    F[i] + F[i+1] = F[i+2]
    for all 
    1

    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 

1

S
, or return 
1

[]
if it cannot be done.

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2
3

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

Example 4:

1
2
3

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

Example 5:

1
2
3

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

Note:

  1. 1

    1 <= S.length <= 200

  2. 1

    S
    contains only digits.

分析

  1. Remove elements with leading zero
  2. The element in the sequence should be at most 
    1

    Integer.MAX_VALUE
  3. The sequence should has at least 3 elements
  4. If current number is larger than the sum of previous two elements, stop backtracking
  5. If we find a valid sequence, stop backtracking

代码

1




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    List<Integer> result;

    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> current = new ArrayList<>();
        backtracking(current, S, 0, 0);
        return result != null ? result : new ArrayList<>();
    }

    public void backtracking(List<Integer> current, String S, int prevIndex, int index) {
        // 3. The sequence should has at least 3 elements
        if( index == S.length() && current.size() > 2)
            result = new ArrayList<>(current);
        else{
            for(int i = index; i < S.length(); i++) {
                // 1. Remove elements with leading zero
                if( S.charAt(prevIndex) == '0' && i + 1 - prevIndex > 1 )
                    break;

                long longValue = Long.parseLong(S.substring(prevIndex, i + 1));
                // 2. The element in the sequence should be at most Integer.MAX_VALUE
                if( longValue > Integer.MAX_VALUE )
                    break;
                int size = current.size();
                if( current.size() < 2 ) {
                    current.add((int) longValue);
                    backtracking(current, S, i + 1, i + 1);
                    // 5. If we find a valid sequence, stop backtracking
                    if( result != null )
                        break;
                    current.remove(current.size() - 1);
                }
                else{
                    long sum = (long)current.get(size - 1) + (long)current.get(size - 2);
                    // 4. If current number is larger than the sum of previous two elements, stop backtracking
                    if( longValue > sum )
                        break;
                    else if( longValue < sum )
                        continue;
                    else {
                        current.add((int) longValue);
                        backtracking(current, S, i + 1, i + 1);
                        if( result != null )
                            break;
                        current.remove(current.size() - 1);
                    }
                }
            }
        }
    }
}




另外一个思路



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> result = new ArrayList<>();
        backtracking(S, result, 0);
        return result;
    }

    public boolean backtracking(String s, List<Integer> result, int index1) {
        if (index1 == s.length() && result.size() >= 3) { // 结果集中至少3个数
            return true;
        }
        for (int index2 = index1; index2 < s.length(); index2++) { // 从当前index开始直到末尾
            if (s.charAt(index1) == '0' && index2 > index1) { //当前数字为0，且不在第一个位置
                break;
            }
            long num = Long.parseLong(s.substring(index1, index2 + 1));
            if (num > Integer.MAX_VALUE) {
                break;
            }
            int size = result.size();
            // early termination
            if (size >= 2 && num > result.get(size - 1) + result.get(size - 2)) {
                break;
            }
            if (size <= 1 || num == result.get(size - 1) + result.get(size - 2)) {
                result.add((int) num);
                // branch pruning. if one branch has found fib seq, return true to upper call
                if (backtracking(s, result, index2 + 1)) {
                    return true;
                }
                result.remove(result.size() - 1);
            }
        }
        return false;
    }
}




		
	





      
      

        This site is open source. Improve this page.