字符串变换、子序列、高精度运算——LeetCode

一、字符串变换

1、密钥格式化（简单）

自己的想法

方法一：使用 StringBuilder

• 执行用时：11 ms, 在所有 Java 提交中击败了81.77%的用户
• 内存消耗：38.3 MB, 在所有 Java 提交中击败了91.92%的用户

class Solution {
    public String licenseKeyFormatting(String S, int K) {
        StringBuilder s = new StringBuilder();
        // 统计已打印字符个数
        int count = 0;
        // 倒序遍历字符串
        for (int i = S.length() - 1; i >= 0; i--) {
            if (S.charAt(i) != '-') {
                // 计算什么时候打印分隔符
                if (count != 0 && count % K == 0) {
                    s.append('-');
                }
                // 转为大写字母添加
                s.append(Character.toUpperCase(S.charAt(i)));
                count++;
            }
        }
        // 反转字符串
        return s.reverse().toString();
    }
}

看题解后

方法二：使用 char[]

  使用数组存储结果，需要先计算所需空间（字符个数 + 分隔符个数）。

• 执行用时：4 ms, 在所有 Java 提交中击败了99.05%的用户
• 内存消耗：38.3 MB, 在所有 Java 提交中击败了92.60%的用户

class Solution {
    public String licenseKeyFormatting(String S, int K) {
        char[] array = S.toCharArray();
        // 统计字符的个数
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != '-') {
                // 将小写字符转为大写字符
                if (array[i] > 'Z') {
                    array[i] -= 32;
                }
                count++;
            }
        }
        // 没有字符返回空串
        if (count == 0) {
            return "";
        }
        // 计算分隔符的个数
        int separator = count / K;
        // 如果正好整除，分隔符个数 - 1
        separator = count % K == 0 ? separator - 1 : separator;
        // 存储结果的数组
        char[] result = new char[count + separator];
        // 指向结果数组的下标，倒序赋值
        int index = result.length - 1;
        // 统计已打印字符个数
        int letter = 0;
        for (int i = S.length() - 1; i >= 0; i--) {
            if (array[i] != '-') {
                // 计算什么时候打印分隔符
                if (letter != 0 && letter % K == 0) {
                    result[index--] = '-';
                }
                result[index--] = array[i];
                letter++;
            }
        }
        return new String(result);
    }
}

2、Z 字形变换（中等）

自己的想法

方法一：模拟

• 执行用时：10 ms, 在所有 Java 提交中击败了37.93%的用户
• 内存消耗：38.9 MB, 在所有 Java 提交中击败了65.32%的用户

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        List<List<Character>> list = new ArrayList<>();
        // 初始化
        for (int i = 0; i < numRows; i++) {
            list.add(new ArrayList<>());
        }
        int count = 0;
        boolean is = true;
        // 模拟 Z 生成 List
        for (char c : s.toCharArray()) {
            list.get(count).add(c);
            count = is ? count + 1 : count - 1;
            if (count == -1) {
                is = true;
                count = 1;
            } else if (count == numRows) {
                is = false;
                count = numRows - 2;
            }
        }
        StringBuilder stringBuilder = new StringBuilder(s.length());
        // 按行拼接
        for (int i = 0; i < numRows; i++) {
            for (Character c : list.get(i)) {
                stringBuilder.append(c);
            }
        }
        return stringBuilder.toString();
    }
}

看题解后

方法二：模拟（优化）

• 执行用时：6 ms, 在所有 Java 提交中击败了78.16%的用户
• 内存消耗：38.9 MB, 在所有 Java 提交中击败了66.44%的用户

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        List<StringBuilder> list = new ArrayList<>();
        // 初始化
        for (int i = 0; i < numRows; i++) {
            list.add(new StringBuilder());
        }
        int index = 0;
        boolean is = false;
        // 模拟 Z 生成 List
        for (char c : s.toCharArray()) {
            list.get(index).append(c);
            // 到边界则反转
            if (index == 0 || index == numRows - 1) {
                is = !is;
            }
            index += is ? 1 : -1;
        }
        StringBuilder result = new StringBuilder();
        // 按行拼接
        for (int i = 0; i < numRows; i++) {
            result.append(list.get(i));
        }
        return result.toString();
    }
}

方法三：按行访问

  首先访问行 0 中的所有字符，接着访问行 1，然后行 2，依此类推...

• 对于第 0 行来说，每个字符的间距为2 * numRows − 2，所以字符位于j * (2 * numRows − 2) （j 表示第几个）。
• 第numRows − 1 行中的字符位于索引j * (2 * numRows − 2) + numRows − 1 处。
• 内部 i 行中的字符位于j * (2 * numRows − 2) + i 和(j + 1) * (2 * numRows − 2) - i。
• 对于numRows 等于 1 进行特殊处理，因为2 * 1 − 2 = 0 会造成死循环。

0     8       16
1   7 9    15 17
2  6  10  14  18
3 5   11 13   19
4     12      20

• 执行用时：3 ms, 在所有 Java 提交中击败了98.05%的用户
• 内存消耗：38.2 MB, 在所有 Java 提交中击败了99.49%的用户

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        // Z 的横线字符的间隔数
        int interval = 2 * numRows - 2;
        char[] result = new char[s.length()];
        int index = 0;
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < s.length(); j += interval) {
                // Z 的两个横线
                result[index++] = s.charAt(j + i);
                // Z 中间的斜线，第一行和最后一行不需要
                if (i != 0 && i != numRows - 1 && j + interval - i < s.length()) {
                    result[index++] = s.charAt(j + interval - i);
                }
            }
        }
        return new String(result);
    }
}

方法四：计算字符所属行

  通过 2 * numRows − 2 计算出每个字符所在的行，然后进行拼接。

• 执行用时：16 ms, 在所有 Java 提交中击败了24.91%的用户
• 内存消耗：39.3 MB, 在所有 Java 提交中击败了23.56%的用户

class Solution {
    public static String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        String[] arr = new String[numRows];
        // 设置初值
        Arrays.fill(arr, "");
        // 计算对位间距
        int period = numRows * 2 - 2;
        for (int i = 0; i < s.length(); i++) {
            // 用于计算每个字符所在行
            int mod = i % period;
            if (mod < numRows) {
                arr[mod] += s.charAt(i);
            } else {
                arr[period - mod] += s.charAt(i);
            }
        }
        StringBuilder res = new StringBuilder();
        for (String ch : arr) {
            res.append(ch);
        }
        return res.toString();
    }
}

3、文本左右对齐（困难）

看题解后

方法一：

普通情况

1. 先取出一行能够容纳的单词，将这些单词根据规则填入一行，每个单词中至少有一个间隔。
2. 计算出额外空格的数量（maxWidth - 单词总长度 - 单词间的正常空格），额外空格就是正常书写用不到的空格。
3. 额外空额的平均分配：（maxWidth - 单词总长度 - 单词间的正常空格）/ 间隔数。
4. 多余的额外空格从左往后分配，多余的额外空格数：（maxWidth - 单词总长度 - 单词间的正常空格）% 间隔数。

特殊情况

1. 一行只有一个单词，单词左对齐，右侧填满空格。
2. 最后一行，所有单词左对齐，中间只有一个空格，最后一个单词右侧填满空格。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.7 MB, 在所有 Java 提交中击败了76.61%的用户

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        // 单词的总个数
        int n = words.length;
        //len代表当前数个单词长度， start,end代表本行当前单词开始与截止位置
        int length = 0, start = 0, end = 0;
        StringBuffer line = new StringBuffer();
        List<String> result = new ArrayList<>();
        while (end < n) {
            //记录每行单词开始与截止位置
            for (end = start; end < n; end++) {
                // 累加单词长度
                length += words[end].length();
                // 如果长度超过一行限制，则取前一个单词为截止
                if (length > maxWidth) {
                    // 减去最后一个单词的空格，和刚刚加的单词长度
                    length = length - 1 - words[end].length();
                    end--;
                    break;
                }
                // 单词尾部空格
                length++;
            }
            // 最后一行，所有单词左对齐，中间只有一个空格，最后一个单词右侧填满空格
            if (end == n) {
                for (int i = start; i < end - 1; i++) {
                    line.append(words[i]);
                    line.append(' ');
                }
                line.append(words[end - 1]);
                for (int i = line.length(); i < maxWidth; i++) {
                    line.append(' ');
                }
            } else if (end == start) {
                // 一行只有一个单词，单词左对齐，右侧填满空格
                line.append(words[end]);
                for (int j = 0; j < maxWidth - length; j++) {
                    line.append(' ');
                }
            } else {
                // 每个间隔平均1 + space个，剩余间隔/单词数
                int space = (maxWidth - length) / (end - start);
                // 多出来的前 extra 个间隔每个加 1
                int extra = (maxWidth - length) % (end - start);
                for (int i = start; i < end; i++) {
                    line.append(words[i]);
                    for (int j = 0; j <= space; j++) {
                        line.append(' ');
                    }
                    if (extra-- > 0) {
                        line.append(' ');
                    }
                }
                line.append(words[end]);
            }
            // 添加当前行的字符串
            result.add(line.toString());
            // 移动下一行的前指针
            start = end + 1;
            // 移动下一行的后指针
            end = start;
            // 初始化
            length = 0;
            line = new StringBuffer();
        }
        return result;
    }
}

二、子序列

1、判断子序列（简单）

自己的想法

方法一：双指针

  使用两个指针分别指向两个字符串的起始索引，每次循环判断两个指针指向的字符是否相等，相等则两个指针向右移动，不相等则只移动 t 的指针。最后如果 s 指针移动到末尾，则 s 是为 t 的子序列。

• 执行用时：2 ms, 在所有 Java 提交中击败了43.64%的用户
• 内存消耗：36.5 MB, 在所有 Java 提交中击败了36.25%的用户

class Solution {

    public boolean isSubsequence(String s, String t) {
        int indexs = 0, indext = 0;
        while (indexs < s.length() && indext < t.length()) {
            if (s.charAt(indexs) == t.charAt(indext)) {
                indexs++;
            }
            indext++;
        }
        return indexs == s.length();
    }
}

看题解后

方法二：动态规划

  前两种方法，我们总是在寻找 t 中的下一个匹配的字符，浪费了大量的时间。我们可以对字符串 t 的每一个字符作预处理，记录从该位置开始往后每一个字符第一次出现的位置。创建 dp 数组 int[][] dp = new int[n + 1][26];，dp[i][j] 的值表示：字符串 t 中下标为 i 的字符后的 'a' + j 字符所在的位置，为 t.length() 则表示不存在。

• 执行用时：6 ms, 在所有 Java 提交中击败了10.34%的用户
• 内存消耗：39.1 MB, 在所有 Java 提交中击败了5.04%的用户

class Solution {

    public boolean isSubsequence(String s, String t) {
        int n = t.length();
        int[][] dp = new int[n + 1][26];
        // 初始化结尾
        for (int i = 0; i < 26; i++) {
            dp[n][i] = n;
        }
        // 初始化 dp 数组
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t.charAt(i) - 'a' == j) {
                    dp[i][j] = i;
                } else {
                    // 不相等，则继承上一位的值
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        int index = 0;
        for (char c : s.toCharArray()) {
            // 如果下一个字符在结尾，则表示 t 中没有该字符
            if (dp[index][c - 'a'] == n) {
                return false;
            }
            // 移动到下一个字符的后面
            index = dp[index][c - 'a'] + 1;
        }
        return true;
    }
}

方法三：使用 API

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.6 MB, 在所有 Java 提交中击败了27.39%的用户

class Solution {
  
    public boolean isSubsequence(String s, String t) {
        int index = -1;
        for (char c : s.toCharArray()) {
            index = t.indexOf(c, index + 1);
            if (index == -1) {
                return false;
            }
        }
        return true;
    }
}

2、通过删除字母匹配到字典里最长单词（中等）

自己的想法

方法一：动态规划

• 执行用时：8 ms, 在所有 Java 提交中击败了98.70%的用户
• 内存消耗：39.5 MB, 在所有 Java 提交中击败了29.61%的用户

class Solution {

    public String findLongestWord(String s, List<String> d) {
        int n = s.length();
        int[][] dp = new int[n + 1][26];
        // 初始化结尾
        for (int i = 0; i < 26; i++) {
            dp[n][i] = n;
        }
        // 初始化 dp 数组
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (s.charAt(i) - 'a' == j) {
                    dp[i][j] = i;
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        String result = "";
        for (String t : d) {
            // count 记录相等字符的个数
            int count = 0, index = 0;
            for (char c : t.toCharArray()) {
                // 如果下一个字符的下标为 n，则表示该字符不存在
                if (dp[index][c - 'a'] == n) {
                    break;
                }
                count++;
                // 移动到下一个字符的后面
                index = dp[index][c - 'a'] + 1;
            }
            // 判断是否到了最后一个字符
            if (count == t.length()) {
                // 长度最长且字典顺序最小的字符串
                if (t.length() > result.length() || (t.length() == result.length() && result.compareTo(t) > 0)) {
                    result = t;
                }
            }
        }
        return result;
    }
}

看题解后

方法二：使用 API

• 执行用时：7 ms, 在所有 Java 提交中击败了99.60%的用户
• 内存消耗：39.2 MB, 在所有 Java 提交中击败了81.42%的用户

class Solution {
  
    public String findLongestWord(String s, List<String> d) {
        String result = "";
        for (String t : d) {
            if (isSubsequence(t, s)) {
                // 获取长度最长且字典顺序最小的字符串
                if (result.length() < t.length() || (result.length() == t.length() && result.compareTo(t) > 0)) {
                    result = t;
                }
            }
        }
        return result;
    }

    // 判断 t 是否为 s 的子序列
    public boolean isSubsequence(String t, String s) {
        int index = -1;
        for (int i = 0; i < t.length(); i++) {
            index = s.indexOf(t.charAt(i), index + 1);
            if (index == -1) {
                return false;
            }
        }
        return true;
    }
}

3、最长特殊序列 Ⅰ（简单）

自己的想法

方法一：

  如果 a == b，则肯定没有特殊子序列。如果不相等则返回长度最长的字符串。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36 MB, 在所有 Java 提交中击败了89.93%的用户

class Solution {

    public int findLUSlength(String a, String b) {
        if (a.equals(b)) {
            return -1;
        }
        return Math.max(a.length(), b.length());
    }
}

4、最长特殊序列 II（中等）

看题解后

方法一：检查每个字符串

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.1 MB, 在所有 Java 提交中击败了29.39%的用户

class Solution {

    public int findLUSlength(String[] strs) {
        int max = -1;
        for (int i = 0; i < strs.length; i++) {
            boolean is = true;
            for (int j = 0; j < strs.length; j++) {
                if (i == j) {
                    continue;
                }
                // 如果 i 是 j 的子序列，则结束循环
                if (isSubsequence(strs[i], strs[j])) {
                    is = false;
                    break;
                }
            }
            if (is && max < strs[i].length()) {
                max = strs[i].length();
            }
        }
        return max;
    }


    // 判断 s 是否为 t 的子序列
    public boolean isSubsequence(String s, String t) {
        int index = -1;
        for (char c : s.toCharArray()) {
            index = t.indexOf(c, index + 1);
            if (index == -1) {
                return false;
            }
        }
        return true;
    }
}

方法二：排序 + 检查每个字符串

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.3 MB, 在所有 Java 提交中击败了20.27%的用户

class Solution {

    public int findLUSlength(String[] strs) {
        // 根据字符串长度进行排序，降序排序
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.length() - o1.length();
            }
        });
        for (int i = 0; i < strs.length; i++) {
            boolean is = true;
            for (int j = 0; j < strs.length; j++) {
                if (i == j) {
                    continue;
                }
                // 如果 i 是 j 的子序列，则结束循环
                if (isSubsequence(strs[i], strs[j])) {
                    is = false;
                    break;
                }
            }
            if (is) {
                return strs[i].length();
            }
        }
        return -1;
    }

    // 判断 s 是否为 t 的子序列
    public boolean isSubsequence(String s, String t) {
        int index = -1;
        for (char c : s.toCharArray()) {
            index = t.indexOf(c, index + 1);
            if (index == -1) {
                return false;
            }
        }
        return true;
    }
}

三、高精度运算

1、加一（简单）

自己的想法

方法一：使用 if

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.9 MB, 在所有 Java 提交中击败了58.83%的用户

class Solution {
    public int[] plusOne(int[] digits) {
        for (int index = digits.length - 1; index >= 0; index--) {
            // 如果没进行进位，则结束循环
            if (digits[index] != 9) {
                digits[index]++;
                return digits;
            }
            digits[index] = 0;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

看题解后

方法二：使用 %

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.7 MB, 在所有 Java 提交中击败了82.25%的用户

class Solution {
    public int[] plusOne(int[] digits) {
        for (int index = digits.length - 1; index >= 0; index--) {
            digits[index]++;
            digits[index] %= 10;
            // 如果没进行进位，则结束循环
            if (digits[index] != 0) {
                return digits;
            }
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

2、二进制求和（简单）

自己的想法

方法一：模拟

• 执行用时：2 ms, 在所有 Java 提交中击败了97.93%的用户
• 内存消耗：37.1 MB, 在所有 Java 提交中击败了84.97%的用户

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder s = new StringBuilder();
        int x = a.length() - 1, y = b.length() - 1;
        // 进位
        int num = 0;
        while (x >= 0 || y >= 0) {
            int value = (x >= 0 ? a.charAt(x--) - '0' : 0) + (y >= 0 ? b.charAt(y--) - '0' : 0) + num;
            s.append(value % 2);
            num = value / 2;
        }
        if (num == 1) {
            s.append(1);
        }
        return s.reverse().toString();
    }
}

3、字符串相加（简单）

自己的想法

方法一：模拟

• 执行用时：2 ms, 在所有 Java 提交中击败了99.47%的用户
• 内存消耗：38.5 MB, 在所有 Java 提交中击败了63.13%的用户

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder s = new StringBuilder();
        int x = num1.length() - 1, y = num2.length() - 1;
        // 进位
        int num = 0;
        while (x >= 0 || y >= 0) {
            int value = (x >= 0 ? num1.charAt(x--) - '0' : 0) + (y >= 0 ? num2.charAt(y--) - '0' : 0) + num;
            s.append(value % 10);
            num = value / 10;
        }
        if (num == 1) {
            s.append(1);
        }
        return s.reverse().toString();
    }
}

4、字符串相乘（中等）

自己的想法

方法一：模拟

• 执行用时：23 ms, 在所有 Java 提交中击败了27.65%的用户
• 内存消耗：38.5 MB, 在所有 Java 提交中击败了71.11%的用户

class Solution {
    public String multiply(String num1, String num2) {
        // 如果有一个为 0，则积为 0
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        StringBuilder result = new StringBuilder();
        for (int x = num1.length() - 1; x >= 0; x--) {
            if (num1.charAt(x) != '0') {
                StringBuilder s = new StringBuilder();
                // 123 * 456, 2*456 时是 20*456
                for (int i = x; i < num1.length() - 1; i++) {
                    s.append(0);
                }
                // 记录进位
                int num = 0;
                for (int y = num2.length() - 1; y >= 0; y--) {
                    // 求出乘积
                    int value = (num1.charAt(x) - '0') * (num2.charAt(y) - '0') + num;
                    // 余数是当前数字，除数是进位的数
                    s.append(value % 10);
                    num = value / 10;
                }
                if (num > 0) {
                    s.append(num);
                }
                // 求出上次和这次结果的和
                result = addStrings(result, s.reverse());
            }
        }
        return result.toString();
    }

    public StringBuilder addStrings(StringBuilder num1, StringBuilder num2) {
        StringBuilder s = new StringBuilder();
        int x = num1.length() - 1, y = num2.length() - 1;
        // 进位
        int num = 0;
        while (x >= 0 || y >= 0) {
            int value = (x >= 0 ? num1.charAt(x--) - '0' : 0) + (y >= 0 ? num2.charAt(y--) - '0' : 0) + num;
            s.append(value % 10);
            num = value / 10;
        }
        if (num == 1) {
            s.append(1);
        }
        return s.reverse();
    }
}

看题解后

方法二：数组

  使用数组代替字符串存储结果，则可以减少对字符串的操作。

• 执行用时：2 ms, 在所有 Java 提交中击败了99.85%的用户
• 内存消耗：38.6 MB, 在所有 Java 提交中击败了57.53%的用户

class Solution {
    public String multiply(String num1, String num2) {
        // 如果有一个为 0，则积为 0
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int x = num1.length();
        int y = num2.length();
        // 两个两位数相乘最多为四位数
        int[] result = new int[x + y];
        for (int i = x - 1; i >= 0; i--) {
            int value = num1.charAt(i) - '0';
            // 记录 i 和 y 每个数的乘积
            for (int j = y - 1; j >= 0; j--) {
                result[i + j + 1] += value * (num2.charAt(j) - '0');
            }
        }
        // 处理进位
        for (int i = x + y - 1; i > 0; i--) {
            result[i - 1] += result[i] / 10;
            result[i] %= 10;
        }
        StringBuilder s = new StringBuilder();
        // 判断最高位是否进位了
        for (int i = result[0] == 0 ? 1 : 0; i < result.length; i++) {
            s.append(result[i]);
        }
        return s.toString();
    }
}

5、累加数（中等）

看题解后

方法一：回溯 + 剪枝

  回溯：对字符串进行拆分来生成数字，从头开始遍历所有可能。从第三个数开始，需要判断拆分出的数是否等于前两个数的和，满足时才进行拆分，然后寻找下一个数；否则不进行拆分，继续循环拼接生成新的数字。

  剪枝：

• 除 0 以外，其他数字不能以 0 开头，如果第一个字符为 0，则不再向下拼接。
• 从第三个数开始，如果该值比前两个数值的和大，则没必要再向下拼接，越往后拼接的数只会越大。

  文中拆分的意思：将当前子串当做序列中的一个数字，然后就可以寻找下一个数字了。拼接的意思：当前数字不合法，需要借助后面的字符来组成新的数字。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.5 MB, 在所有 Java 提交中击败了46.63%的用户

class Solution {
    /**
     * 字符串
     */
    String s;
    /**
     * 字符串的长度
     */
    int n;

    public boolean isAdditiveNumber(String num) {
        this.s = num;
        this.n = num.length();
        return toFlashBack(0, 0, 0, 0);
    }

    /**
     * @param index    当前的下标
     * @param sum      前两个数的和
     * @param previous 前一个数的值
     * @param count    已生成几个数
     */
    public boolean toFlashBack(int index, long sum, long previous, int count) {
        // 如果已生成三个数及以上则返回 true
        if (index == n) {
            return count >= 3;
        }
        // 拼接数字的值，值可能越 int 界所以使用 long
        long value = 0;
        // 开始拼接数字
        for (int i = index; i < n; i++) {
            // 除 0 以外，其他数字第一位不能为 0
            if (i > index && s.charAt(index) == '0') {
                break;
            }
            // 计算数值
            value = value * 10 + s.charAt(i) - '0';
            // 判断数值是否合法，如果前面有两个以上的数，则判断前两个数的和是否等于这个数
            if (count >= 2) {
                if (value < sum) {
                    // 小的话继续向后继续拼接
                    continue;
                } else if (value > sum) {
                    // 大的话直接结束，再往后拼接无意义
                    break;
                }
            }
            // 使用该数，向下递归
            if (toFlashBack(i + 1, previous + value, value, count + 1)) {
                return true;
            }
            // 没有可恢复原样的变量
        }
        return false;
    }
}