将字符串数字拆分成单个数字_【LeetCode】842.将数组拆分成斐波那契序列

【LeetCode】842. Split Array into Fibonacci Sequence 将数组拆分成斐波那契序列(Medium)(JAVA)

题目描述&＃xff1a;

Given a string S of digits, such as S &＃61; "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 <&＃61; F[i] <&＃61; 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);

• F.length >&＃61; 3;

• and F[i] &＃43; F[i&＃43;1] &＃61; F[i&＃43;2] for all 0 <&＃61; i 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 <&＃61; S.length <&＃61; 200

• S contains only digits.

题目大意

给定一个数字字符串 S&＃xff0c;比如 S &＃61; "123456579"&＃xff0c;我们可以将它分成斐波那契式的序列 [123, 456, 579]。

形式上&＃xff0c;斐波那契式序列是一个非负整数列表 F&＃xff0c;且满足&＃xff1a;

• 0 <&＃61; F[i] <&＃61; 2^31 - 1&＃xff0c;(也就是说&＃xff0c;每个整数都符合 32 位有符号整数类型)&＃xff1b;

• F.length >&＃61; 3&＃xff1b;

• 对于所有的0 <&＃61; i

另外&＃xff0c;请注意&＃xff0c;将字符串拆分成小块时&＃xff0c;每个块的数字一定不要以零开头&＃xff0c;除非这个块是数字 0 本身。

返回从 S 拆分出来的任意一组斐波那契式的序列块&＃xff0c;如果不能拆分则返回 []。

解题方法

1. 首先要看清楚例子&＃xff0c;将数组拆分成斐波那契序列&＃xff1a;数组里的每个元素不一定是相等的

2. 所以要从第一个数字长度 i 从 1 到 S.length() / 2&＃xff0c;第二个长度 j 也从 1 到 S.length() / 2&＃xff0c;因为要满足至少三个&＃xff0c;而且三个数字肯定大于前两个数组所以, S.length() - i - j >&＃61; Math.max(i, j)

3. 判断第三个是否是前两个的和&＃xff0c;从 i &＃43; j 位开始&＃xff0c;判断接下来的部分是否 num1 &＃43; num2 (我这里直接用的 string 的 startWith 方法&＃xff0c;判断的方法很多)

4. 后面不断循环&＃xff0c;看是否能到能把所有字符判断完

5. note: 这里还有很多可以优化的地方&＃xff1a;1、可以不用创建新的字符串&＃xff0c;这样可以节省空间&＃xff0c;也不用 delete 字符&＃xff1b;2、比较可以不用 startWith 方法&＃xff0c;可以一个个 char 比较

class Solution {
    public List splitIntoFibonacci(String S) {List list &＃61; new ArrayList<>();int max &＃61; S.length() / 2;for (int i &＃61; 1; i <&＃61; max; i&＃43;&＃43;) {
            long num &＃61; Long.parseLong(S.substring(0, i));if (num >&＃61; Integer.MAX_VALUE) break;if (S.charAt(0) &＃61;&＃61; &＃39;0&＃39; && i > 1) continue;for (int j &＃61; 1; j <&＃61; max && (S.length() - i - j) >&＃61; Math.max(i, j); j&＃43;&＃43;) {if (S.charAt(i) &＃61;&＃61; &＃39;0&＃39; && j > 1) continue;
                StringBuilder sb &＃61; new StringBuilder(S);num &＃61; Long.parseLong(S.substring(0, i));
                list &＃61; new ArrayList<>();
                list.add((int) num);num &＃61; Long.parseLong(S.substring(i, i &＃43; j));if (num >&＃61; Integer.MAX_VALUE) break;
                list.add((int) num);
                sb.delete(0, i &＃43; j);while (sb.length() > 0) {int size &＃61; list.size();num &＃61; list.get(size - 1) &＃43; list.get(size - 2);if (num >&＃61; Integer.MAX_VALUE) break;if (!sb.toString().startsWith(num &＃43; "")) break;
                    list.add((int) num);
                    sb.delete(0, (num &＃43; "").length());
                }if (sb.length() &＃61;&＃61; 0 && list.size() >&＃61; 3) return list;
            }
        }return new ArrayList<>();
    }
}

执行耗时:8 ms,击败了20.32% 的Java用户
内存消耗:38.7 MB,击败了66.05% 的Java用户