1946.子字符串突变后可能得到的最大整数

给你一个字符串 num ，该字符串表示一个大整数。另给你一个长度为 10 且 下标从 0 开始 的整数数组 change ，该数组将 0-9 中的每个数字映射到另一个数字。更规范的说法是，数字 d 映射为数字 change[d] 。

你可以选择 突变 num 的任一子字符串。突变 子字符串意味着将每位数字 num[i] 替换为该数字在 change 中的映射（也就是说，将 num[i] 替换为 change[num[i]]）。

请你找出在对 num 的任一子字符串执行突变操作（也可以不执行）后，可能得到的 最大整数 ，并用字符串表示返回。

子字符串是字符串中的一个 连续序列。

示例 1

输入：num = “132”, change = [9,8,5,0,3,6,4,2,6,8]
输出：”832”
解释：替换子字符串 “1”：

• 1 映射为 change[1] = 8

因此 “132” 变为 “832”
“832” 是可以构造的最大整数，所以返回它的字符串表示

示例 2

输入：num = “021“, change = [9,4,3,5,7,2,1,9,0,6]
输出：”934“
解释：替换子字符串 “021”：

• 0 映射为 change[0] = 9
• 2 映射为 change[2] = 3
• 1 映射为 change[1] = 4

因此，”021“ 变为 “934“
“934” 是可以构造的最大整数，所以返回它的字符串表示

示例 3

输入：num = “5“, change = [1,4,7,5,3,2,5,6,9,4]
输出：”5“
解释：”5” 已经是可以构造的最大整数，所以返回它的字符串表示

提示

• 有一个「子字符串」的概念，这个子字符串是连续的

Solution 1

第一次使用了比较直接粗暴的解法

class Solution {
    public String maximumNumber(String num, int[] change) {
        // 将字符串转为字符数组
        char[] charArray = num.toCharArray();
        // 是否能「突变」
        boolean isCanChange = true;
        // 是否「已突变」（用于判断连续）
        boolean isChanged = false;
        // 输出
        StringBuilder result = new StringBuilder();
        for (char c : charArray) {
            if (isCanChange) {
                // char转String转int
                int n = Integer.parseInt(c + "");
                // 获取用于突变的隐射值
                int cn = change[n];
                if (cn > n) {
                    // 可以突变
                    isChanged = true;
                    result.append(cn);
                } else if (cn == n) {
                    // 等于时维持是否已突变的状态，不改变
                    result.append(cn);
                } else {
                    // 小于时如果已突变，则不允许往下继续突变
                    if (isChanged) {
                        isCanChange = false;
                    }
                    result.append(n);
                }
            } else {
                // 不允许突变，直接拼接原字符
                result.append(c);
            }
        }
        return result.toString();
    }
}

• 执行用时：29 ms（击败 13.64% 使用 Java 的用户）
• 内存消耗：45.48 MB（击败 6.82% 使用 Java 的用户）

Solution 2

查看其他解法后，改良解法

class Solution {
    public String maximumNumber(String num, int[] change) {
        // 将字符串转为字符数组
        char[] nums = num.toCharArray();
        // 突变次数
        int k = 0;
        // 字符串长度
        final int length = num.length();
        // 遍历字符数组
        for(int i = 0; i < length; i++) {
            // 获取第 i 个位置上的数字（巧妙避免类型转换）
            int n = nums[i] - '0';
            // 判断是否符合突变条件
            if (n < change[n]) {
                // 可以突变，则将突变值赋值给原字符数组
                nums[i] = (char) ('0' + change[n]);
                // 突变次数 +1
                k++;
            } else if (n > change[n] && k > 0) {
                // 如果已开始突变，但出现「断开」，直接结束
                break;
            }
        }
        return new String(nums);
    }
}

• 执行用时：8 ms（击败 72.73% 使用 Java 的用户）
• 内存消耗：44.43 MB（击败 11.36% 使用 Java 的用户）

测试用例

• Case 1

  num = "132"
  change = [9,8,5,0,3,6,4,2,6,8]
  预期结果："832"

• Case 2

  num = "021"
  change = [9,4,3,5,7,2,1,9,0,6]
  预期结果："934"

• Case 3

  num = "5"
  change = [1,4,7,5,3,2,5,6,9,4]
  预期结果："5"

• Case 4

  num = "330"
  change = [9,3,6,3,7,3,1,4,5,8]
  预期结果："339"

• Case 5

  num = "000000"
  change = [1,3,5,3,5,3,2,7,4,3]
  预期结果："111111"

• Case 6

  num = "214010"
  change = [6,7,9,7,4,0,3,4,4,7]
  预期结果："974676"

• Case 7

  num = "334111"
  change = [0,9,2,3,3,2,5,5,5,5]
  预期结果："334999"

Tips

char 在 java 中占 2 个字节

char 在内存中存储的是该字符在 Unicode 字符集中的排序位置

char a = 'a';
char aa = 97;
System.out.println(a == aa); // true

Source

1946. 子字符串突变后可能得到的最大整数 - 力扣（LeetCode）