一、字符串变换

1、密钥格式化(简单)

自己的想法

方法一:使用 StringBuilder

  • 执行用时:11 ms, 在所有 Java 提交中击败了81.77%的用户
  • 内存消耗:38.3 MB, 在所有 Java 提交中击败了91.92%的用户
 1class Solution {
 2    public String licenseKeyFormatting(String S, int K) {
 3        StringBuilder s = new StringBuilder();
 4        // 统计已打印字符个数
 5        int count = 0;
 6        // 倒序遍历字符串
 7        for (int i = S.length() - 1; i >= 0; i--) {
 8            if (S.charAt(i) != '-') {
 9                // 计算什么时候打印分隔符
10                if (count != 0 && count % K == 0) {
11                    s.append('-');
12                }
13                // 转为大写字母添加
14                s.append(Character.toUpperCase(S.charAt(i)));
15                count++;
16            }
17        }
18        // 反转字符串
19        return s.reverse().toString();
20    }
21}

看题解后

方法二:使用 char[]

  使用数组存储结果,需要先计算所需空间(字符个数 + 分隔符个数)。

  • 执行用时:4 ms, 在所有 Java 提交中击败了99.05%的用户
  • 内存消耗:38.3 MB, 在所有 Java 提交中击败了92.60%的用户
 1class Solution {
 2    public String licenseKeyFormatting(String S, int K) {
 3        char[] array = S.toCharArray();
 4        // 统计字符的个数
 5        int count = 0;
 6        for (int i = 0; i < array.length; i++) {
 7            if (array[i] != '-') {
 8                // 将小写字符转为大写字符
 9                if (array[i] > 'Z') {
10                    array[i] -= 32;
11                }
12                count++;
13            }
14        }
15        // 没有字符返回空串
16        if (count == 0) {
17            return "";
18        }
19        // 计算分隔符的个数
20        int separator = count / K;
21        // 如果正好整除,分隔符个数 - 1
22        separator = count % K == 0 ? separator - 1 : separator;
23        // 存储结果的数组
24        char[] result = new char[count + separator];
25        // 指向结果数组的下标,倒序赋值
26        int index = result.length - 1;
27        // 统计已打印字符个数
28        int letter = 0;
29        for (int i = S.length() - 1; i >= 0; i--) {
30            if (array[i] != '-') {
31                // 计算什么时候打印分隔符
32                if (letter != 0 && letter % K == 0) {
33                    result[index--] = '-';
34                }
35                result[index--] = array[i];
36                letter++;
37            }
38        }
39        return new String(result);
40    }
41}

2、Z 字形变换(中等)

自己的想法

方法一:模拟

  • 执行用时:10 ms, 在所有 Java 提交中击败了37.93%的用户
  • 内存消耗:38.9 MB, 在所有 Java 提交中击败了65.32%的用户
 1class Solution {
 2    public String convert(String s, int numRows) {
 3        if (numRows == 1) {
 4            return s;
 5        }
 6        List<List<Character>> list = new ArrayList<>();
 7        // 初始化
 8        for (int i = 0; i < numRows; i++) {
 9            list.add(new ArrayList<>());
10        }
11        int count = 0;
12        boolean is = true;
13        // 模拟 Z 生成 List
14        for (char c : s.toCharArray()) {
15            list.get(count).add(c);
16            count = is ? count + 1 : count - 1;
17            if (count == -1) {
18                is = true;
19                count = 1;
20            } else if (count == numRows) {
21                is = false;
22                count = numRows - 2;
23            }
24        }
25        StringBuilder stringBuilder = new StringBuilder(s.length());
26        // 按行拼接
27        for (int i = 0; i < numRows; i++) {
28            for (Character c : list.get(i)) {
29                stringBuilder.append(c);
30            }
31        }
32        return stringBuilder.toString();
33    }
34}

看题解后

方法二:模拟(优化)

  • 执行用时:6 ms, 在所有 Java 提交中击败了78.16%的用户
  • 内存消耗:38.9 MB, 在所有 Java 提交中击败了66.44%的用户
 1class Solution {
 2    public String convert(String s, int numRows) {
 3        if (numRows == 1) {
 4            return s;
 5        }
 6        List<StringBuilder> list = new ArrayList<>();
 7        // 初始化
 8        for (int i = 0; i < numRows; i++) {
 9            list.add(new StringBuilder());
10        }
11        int index = 0;
12        boolean is = false;
13        // 模拟 Z 生成 List
14        for (char c : s.toCharArray()) {
15            list.get(index).append(c);
16            // 到边界则反转
17            if (index == 0 || index == numRows - 1) {
18                is = !is;
19            }
20            index += is ? 1 : -1;
21        }
22        StringBuilder result = new StringBuilder();
23        // 按行拼接
24        for (int i = 0; i < numRows; i++) {
25            result.append(list.get(i));
26        }
27        return result.toString();
28    }
29}

方法三:按行访问

  首先访问行 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 会造成死循环。
10     8       16
21   7 9    15 17
32  6  10  14  18
43 5   11 13   19
54     12      20
  • 执行用时:3 ms, 在所有 Java 提交中击败了98.05%的用户
  • 内存消耗:38.2 MB, 在所有 Java 提交中击败了99.49%的用户
 1class Solution {
 2    public String convert(String s, int numRows) {
 3        if (numRows == 1) {
 4            return s;
 5        }
 6        // Z 的横线字符的间隔数
 7        int interval = 2 * numRows - 2;
 8        char[] result = new char[s.length()];
 9        int index = 0;
10        for (int i = 0; i < numRows; i++) {
11            for (int j = 0; j + i < s.length(); j += interval) {
12                // Z 的两个横线
13                result[index++] = s.charAt(j + i);
14                // Z 中间的斜线,第一行和最后一行不需要
15                if (i != 0 && i != numRows - 1 && j + interval - i < s.length()) {
16                    result[index++] = s.charAt(j + interval - i);
17                }
18            }
19        }
20        return new String(result);
21    }
22}

方法四:计算字符所属行

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

  • 执行用时:16 ms, 在所有 Java 提交中击败了24.91%的用户
  • 内存消耗:39.3 MB, 在所有 Java 提交中击败了23.56%的用户
 1class Solution {
 2    public static String convert(String s, int numRows) {
 3        if (numRows == 1) {
 4            return s;
 5        }
 6        String[] arr = new String[numRows];
 7        // 设置初值
 8        Arrays.fill(arr, "");
 9        // 计算对位间距
10        int period = numRows * 2 - 2;
11        for (int i = 0; i < s.length(); i++) {
12            // 用于计算每个字符所在行
13            int mod = i % period;
14            if (mod < numRows) {
15                arr[mod] += s.charAt(i);
16            } else {
17                arr[period - mod] += s.charAt(i);
18            }
19        }
20        StringBuilder res = new StringBuilder();
21        for (String ch : arr) {
22            res.append(ch);
23        }
24        return res.toString();
25    }
26}

3、文本左右对齐(困难)

看题解后

方法一

普通情况

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

特殊情况

  1. 一行只有一个单词,单词左对齐,右侧填满空格。
  2. 最后一行,所有单词左对齐,中间只有一个空格,最后一个单词右侧填满空格。
  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.7 MB, 在所有 Java 提交中击败了76.61%的用户
 1class Solution {
 2    public List<String> fullJustify(String[] words, int maxWidth) {
 3        // 单词的总个数
 4        int n = words.length;
 5        //len代表当前数个单词长度, start,end代表本行当前单词开始与截止位置
 6        int length = 0, start = 0, end = 0;
 7        StringBuffer line = new StringBuffer();
 8        List<String> result = new ArrayList<>();
 9        while (end < n) {
10            //记录每行单词开始与截止位置
11            for (end = start; end < n; end++) {
12                // 累加单词长度
13                length += words[end].length();
14                // 如果长度超过一行限制,则取前一个单词为截止
15                if (length > maxWidth) {
16                    // 减去最后一个单词的空格,和刚刚加的单词长度
17                    length = length - 1 - words[end].length();
18                    end--;
19                    break;
20                }
21                // 单词尾部空格
22                length++;
23            }
24            // 最后一行,所有单词左对齐,中间只有一个空格,最后一个单词右侧填满空格
25            if (end == n) {
26                for (int i = start; i < end - 1; i++) {
27                    line.append(words[i]);
28                    line.append(' ');
29                }
30                line.append(words[end - 1]);
31                for (int i = line.length(); i < maxWidth; i++) {
32                    line.append(' ');
33                }
34            } else if (end == start) {
35                // 一行只有一个单词,单词左对齐,右侧填满空格
36                line.append(words[end]);
37                for (int j = 0; j < maxWidth - length; j++) {
38                    line.append(' ');
39                }
40            } else {
41                // 每个间隔平均1 + space个,剩余间隔/单词数
42                int space = (maxWidth - length) / (end - start);
43                // 多出来的前 extra 个间隔每个加 1
44                int extra = (maxWidth - length) % (end - start);
45                for (int i = start; i < end; i++) {
46                    line.append(words[i]);
47                    for (int j = 0; j <= space; j++) {
48                        line.append(' ');
49                    }
50                    if (extra-- > 0) {
51                        line.append(' ');
52                    }
53                }
54                line.append(words[end]);
55            }
56            // 添加当前行的字符串
57            result.add(line.toString());
58            // 移动下一行的前指针
59            start = end + 1;
60            // 移动下一行的后指针
61            end = start;
62            // 初始化
63            length = 0;
64            line = new StringBuffer();
65        }
66        return result;
67    }
68}

二、子序列

1、判断子序列(简单)

自己的想法

方法一:双指针

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

  • 执行用时:2 ms, 在所有 Java 提交中击败了43.64%的用户
  • 内存消耗:36.5 MB, 在所有 Java 提交中击败了36.25%的用户
 1class Solution {
 2
 3    public boolean isSubsequence(String s, String t) {
 4        int indexs = 0, indext = 0;
 5        while (indexs < s.length() && indext < t.length()) {
 6            if (s.charAt(indexs) == t.charAt(indext)) {
 7                indexs++;
 8            }
 9            indext++;
10        }
11        return indexs == s.length();
12    }
13}

看题解后

方法二:动态规划

  前两种方法,我们总是在寻找 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%的用户
 1class Solution {
 2
 3    public boolean isSubsequence(String s, String t) {
 4        int n = t.length();
 5        int[][] dp = new int[n + 1][26];
 6        // 初始化结尾
 7        for (int i = 0; i < 26; i++) {
 8            dp[n][i] = n;
 9        }
10        // 初始化 dp 数组
11        for (int i = n - 1; i >= 0; i--) {
12            for (int j = 0; j < 26; j++) {
13                if (t.charAt(i) - 'a' == j) {
14                    dp[i][j] = i;
15                } else {
16                    // 不相等,则继承上一位的值
17                    dp[i][j] = dp[i + 1][j];
18                }
19            }
20        }
21        int index = 0;
22        for (char c : s.toCharArray()) {
23            // 如果下一个字符在结尾,则表示 t 中没有该字符
24            if (dp[index][c - 'a'] == n) {
25                return false;
26            }
27            // 移动到下一个字符的后面
28            index = dp[index][c - 'a'] + 1;
29        }
30        return true;
31    }
32}

方法三:使用 API

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.6 MB, 在所有 Java 提交中击败了27.39%的用户
 1class Solution {
 2  
 3    public boolean isSubsequence(String s, String t) {
 4        int index = -1;
 5        for (char c : s.toCharArray()) {
 6            index = t.indexOf(c, index + 1);
 7            if (index == -1) {
 8                return false;
 9            }
10        }
11        return true;
12    }
13}

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

自己的想法

方法一:动态规划

  • 执行用时:8 ms, 在所有 Java 提交中击败了98.70%的用户
  • 内存消耗:39.5 MB, 在所有 Java 提交中击败了29.61%的用户
 1class Solution {
 2
 3    public String findLongestWord(String s, List<String> d) {
 4        int n = s.length();
 5        int[][] dp = new int[n + 1][26];
 6        // 初始化结尾
 7        for (int i = 0; i < 26; i++) {
 8            dp[n][i] = n;
 9        }
10        // 初始化 dp 数组
11        for (int i = n - 1; i >= 0; i--) {
12            for (int j = 0; j < 26; j++) {
13                if (s.charAt(i) - 'a' == j) {
14                    dp[i][j] = i;
15                } else {
16                    dp[i][j] = dp[i + 1][j];
17                }
18            }
19        }
20        String result = "";
21        for (String t : d) {
22            // count 记录相等字符的个数
23            int count = 0, index = 0;
24            for (char c : t.toCharArray()) {
25                // 如果下一个字符的下标为 n,则表示该字符不存在
26                if (dp[index][c - 'a'] == n) {
27                    break;
28                }
29                count++;
30                // 移动到下一个字符的后面
31                index = dp[index][c - 'a'] + 1;
32            }
33            // 判断是否到了最后一个字符
34            if (count == t.length()) {
35                // 长度最长且字典顺序最小的字符串
36                if (t.length() > result.length() || (t.length() == result.length() && result.compareTo(t) > 0)) {
37                    result = t;
38                }
39            }
40        }
41        return result;
42    }
43}

看题解后

方法二:使用 API

  • 执行用时:7 ms, 在所有 Java 提交中击败了99.60%的用户
  • 内存消耗:39.2 MB, 在所有 Java 提交中击败了81.42%的用户
 1class Solution {
 2  
 3    public String findLongestWord(String s, List<String> d) {
 4        String result = "";
 5        for (String t : d) {
 6            if (isSubsequence(t, s)) {
 7                // 获取长度最长且字典顺序最小的字符串
 8                if (result.length() < t.length() || (result.length() == t.length() && result.compareTo(t) > 0)) {
 9                    result = t;
10                }
11            }
12        }
13        return result;
14    }
15
16    // 判断 t 是否为 s 的子序列
17    public boolean isSubsequence(String t, String s) {
18        int index = -1;
19        for (int i = 0; i < t.length(); i++) {
20            index = s.indexOf(t.charAt(i), index + 1);
21            if (index == -1) {
22                return false;
23            }
24        }
25        return true;
26    }
27}

3、最长特殊序列 Ⅰ(简单)

自己的想法

方法一

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

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36 MB, 在所有 Java 提交中击败了89.93%的用户
1class Solution {
2
3    public int findLUSlength(String a, String b) {
4        if (a.equals(b)) {
5            return -1;
6        }
7        return Math.max(a.length(), b.length());
8    }
9}

4、最长特殊序列 II(中等)

看题解后

方法一:检查每个字符串

  • 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.1 MB, 在所有 Java 提交中击败了29.39%的用户
 1class Solution {
 2
 3    public int findLUSlength(String[] strs) {
 4        int max = -1;
 5        for (int i = 0; i < strs.length; i++) {
 6            boolean is = true;
 7            for (int j = 0; j < strs.length; j++) {
 8                if (i == j) {
 9                    continue;
10                }
11                // 如果 i 是 j 的子序列,则结束循环
12                if (isSubsequence(strs[i], strs[j])) {
13                    is = false;
14                    break;
15                }
16            }
17            if (is && max < strs[i].length()) {
18                max = strs[i].length();
19            }
20        }
21        return max;
22    }
23
24
25    // 判断 s 是否为 t 的子序列
26    public boolean isSubsequence(String s, String t) {
27        int index = -1;
28        for (char c : s.toCharArray()) {
29            index = t.indexOf(c, index + 1);
30            if (index == -1) {
31                return false;
32            }
33        }
34        return true;
35    }
36}

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

  • 执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.3 MB, 在所有 Java 提交中击败了20.27%的用户
 1class Solution {
 2
 3    public int findLUSlength(String[] strs) {
 4        // 根据字符串长度进行排序,降序排序
 5        Arrays.sort(strs, new Comparator<String>() {
 6            @Override
 7            public int compare(String o1, String o2) {
 8                return o2.length() - o1.length();
 9            }
10        });
11        for (int i = 0; i < strs.length; i++) {
12            boolean is = true;
13            for (int j = 0; j < strs.length; j++) {
14                if (i == j) {
15                    continue;
16                }
17                // 如果 i 是 j 的子序列,则结束循环
18                if (isSubsequence(strs[i], strs[j])) {
19                    is = false;
20                    break;
21                }
22            }
23            if (is) {
24                return strs[i].length();
25            }
26        }
27        return -1;
28    }
29
30    // 判断 s 是否为 t 的子序列
31    public boolean isSubsequence(String s, String t) {
32        int index = -1;
33        for (char c : s.toCharArray()) {
34            index = t.indexOf(c, index + 1);
35            if (index == -1) {
36                return false;
37            }
38        }
39        return true;
40    }
41}

三、高精度运算

1、加一(简单)

自己的想法

方法一:使用 if

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.9 MB, 在所有 Java 提交中击败了58.83%的用户
 1class Solution {
 2    public int[] plusOne(int[] digits) {
 3        for (int index = digits.length - 1; index >= 0; index--) {
 4            // 如果没进行进位,则结束循环
 5            if (digits[index] != 9) {
 6                digits[index]++;
 7                return digits;
 8            }
 9            digits[index] = 0;
10        }
11        digits = new int[digits.length + 1];
12        digits[0] = 1;
13        return digits;
14    }
15}

看题解后

方法二:使用 %

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.7 MB, 在所有 Java 提交中击败了82.25%的用户
 1class Solution {
 2    public int[] plusOne(int[] digits) {
 3        for (int index = digits.length - 1; index >= 0; index--) {
 4            digits[index]++;
 5            digits[index] %= 10;
 6            // 如果没进行进位,则结束循环
 7            if (digits[index] != 0) {
 8                return digits;
 9            }
10        }
11        digits = new int[digits.length + 1];
12        digits[0] = 1;
13        return digits;
14    }
15}

2、二进制求和(简单)

自己的想法

方法一:模拟

  • 执行用时:2 ms, 在所有 Java 提交中击败了97.93%的用户
  • 内存消耗:37.1 MB, 在所有 Java 提交中击败了84.97%的用户
 1class Solution {
 2    public String addBinary(String a, String b) {
 3        StringBuilder s = new StringBuilder();
 4        int x = a.length() - 1, y = b.length() - 1;
 5        // 进位
 6        int num = 0;
 7        while (x >= 0 || y >= 0) {
 8            int value = (x >= 0 ? a.charAt(x--) - '0' : 0) + (y >= 0 ? b.charAt(y--) - '0' : 0) + num;
 9            s.append(value % 2);
10            num = value / 2;
11        }
12        if (num == 1) {
13            s.append(1);
14        }
15        return s.reverse().toString();
16    }
17}

3、字符串相加(简单)

自己的想法

方法一:模拟

  • 执行用时:2 ms, 在所有 Java 提交中击败了99.47%的用户
  • 内存消耗:38.5 MB, 在所有 Java 提交中击败了63.13%的用户
 1class Solution {
 2    public String addStrings(String num1, String num2) {
 3        StringBuilder s = new StringBuilder();
 4        int x = num1.length() - 1, y = num2.length() - 1;
 5        // 进位
 6        int num = 0;
 7        while (x >= 0 || y >= 0) {
 8            int value = (x >= 0 ? num1.charAt(x--) - '0' : 0) + (y >= 0 ? num2.charAt(y--) - '0' : 0) + num;
 9            s.append(value % 10);
10            num = value / 10;
11        }
12        if (num == 1) {
13            s.append(1);
14        }
15        return s.reverse().toString();
16    }
17}

4、字符串相乘(中等)

自己的想法

方法一:模拟

6ENF0QCDS65CU4M2KAG.png

  • 执行用时:23 ms, 在所有 Java 提交中击败了27.65%的用户
  • 内存消耗:38.5 MB, 在所有 Java 提交中击败了71.11%的用户
 1class Solution {
 2    public String multiply(String num1, String num2) {
 3        // 如果有一个为 0,则积为 0
 4        if (num1.equals("0") || num2.equals("0")) {
 5            return "0";
 6        }
 7        StringBuilder result = new StringBuilder();
 8        for (int x = num1.length() - 1; x >= 0; x--) {
 9            if (num1.charAt(x) != '0') {
10                StringBuilder s = new StringBuilder();
11                // 123 * 456, 2*456 时是 20*456
12                for (int i = x; i < num1.length() - 1; i++) {
13                    s.append(0);
14                }
15                // 记录进位
16                int num = 0;
17                for (int y = num2.length() - 1; y >= 0; y--) {
18                    // 求出乘积
19                    int value = (num1.charAt(x) - '0') * (num2.charAt(y) - '0') + num;
20                    // 余数是当前数字,除数是进位的数
21                    s.append(value % 10);
22                    num = value / 10;
23                }
24                if (num > 0) {
25                    s.append(num);
26                }
27                // 求出上次和这次结果的和
28                result = addStrings(result, s.reverse());
29            }
30        }
31        return result.toString();
32    }
33
34    public StringBuilder addStrings(StringBuilder num1, StringBuilder num2) {
35        StringBuilder s = new StringBuilder();
36        int x = num1.length() - 1, y = num2.length() - 1;
37        // 进位
38        int num = 0;
39        while (x >= 0 || y >= 0) {
40            int value = (x >= 0 ? num1.charAt(x--) - '0' : 0) + (y >= 0 ? num2.charAt(y--) - '0' : 0) + num;
41            s.append(value % 10);
42            num = value / 10;
43        }
44        if (num == 1) {
45            s.append(1);
46        }
47        return s.reverse();
48    }
49}
50

看题解后

方法二:数组

617S2A8NG5GO29RRI.png

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

  • 执行用时:2 ms, 在所有 Java 提交中击败了99.85%的用户
  • 内存消耗:38.6 MB, 在所有 Java 提交中击败了57.53%的用户
 1class Solution {
 2    public String multiply(String num1, String num2) {
 3        // 如果有一个为 0,则积为 0
 4        if (num1.equals("0") || num2.equals("0")) {
 5            return "0";
 6        }
 7        int x = num1.length();
 8        int y = num2.length();
 9        // 两个两位数相乘最多为四位数
10        int[] result = new int[x + y];
11        for (int i = x - 1; i >= 0; i--) {
12            int value = num1.charAt(i) - '0';
13            // 记录 i 和 y 每个数的乘积
14            for (int j = y - 1; j >= 0; j--) {
15                result[i + j + 1] += value * (num2.charAt(j) - '0');
16            }
17        }
18        // 处理进位
19        for (int i = x + y - 1; i > 0; i--) {
20            result[i - 1] += result[i] / 10;
21            result[i] %= 10;
22        }
23        StringBuilder s = new StringBuilder();
24        // 判断最高位是否进位了
25        for (int i = result[0] == 0 ? 1 : 0; i < result.length; i++) {
26            s.append(result[i]);
27        }
28        return s.toString();
29    }
30}

5、累加数(中等)

看题解后

方法一:回溯 + 剪枝

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

  剪枝:

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

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

  • 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗:36.5 MB, 在所有 Java 提交中击败了46.63%的用户
 1class Solution {
 2    /**
 3     * 字符串
 4     */
 5    String s;
 6    /**
 7     * 字符串的长度
 8     */
 9    int n;
10
11    public boolean isAdditiveNumber(String num) {
12        this.s = num;
13        this.n = num.length();
14        return toFlashBack(0, 0, 0, 0);
15    }
16
17    /**
18     * @param index    当前的下标
19     * @param sum      前两个数的和
20     * @param previous 前一个数的值
21     * @param count    已生成几个数
22     */
23    public boolean toFlashBack(int index, long sum, long previous, int count) {
24        // 如果已生成三个数及以上则返回 true
25        if (index == n) {
26            return count >= 3;
27        }
28        // 拼接数字的值,值可能越 int 界所以使用 long
29        long value = 0;
30        // 开始拼接数字
31        for (int i = index; i < n; i++) {
32            // 除 0 以外,其他数字第一位不能为 0
33            if (i > index && s.charAt(index) == '0') {
34                break;
35            }
36            // 计算数值
37            value = value * 10 + s.charAt(i) - '0';
38            // 判断数值是否合法,如果前面有两个以上的数,则判断前两个数的和是否等于这个数
39            if (count >= 2) {
40                if (value < sum) {
41                    // 小的话继续向后继续拼接
42                    continue;
43                } else if (value > sum) {
44                    // 大的话直接结束,再往后拼接无意义
45                    break;
46                }
47            }
48            // 使用该数,向下递归
49            if (toFlashBack(i + 1, previous + value, value, count + 1)) {
50                return true;
51            }
52            // 没有可恢复原样的变量
53        }
54        return false;
55    }
56}

标题:字符串变换、子序列、高精度运算——LeetCode
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2021/04/04/1617544705865.html
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!