数字与字符串间转换——LeetCode

@Yi-Xing 2021-04-04 0 评论 0 浏览

LeetCode

1、猜数字游戏（中等）

自己的想法

题意如下：

给两个相等长度只含数字的字符串，计算公牛和奶牛的数量。
公牛：所有同一位上且字符值相等的字符数量，即secret.charAt(i) == guess.charAt(i)。
奶牛：所有不同位上且字符值相等的字符数量。

注意：秘密数字和朋友的猜测数都可能含有重复数字，每位数字只能统计一次。这里所说的是每位数字统计一次，不是每个数字统计一次。即 "1122" 和 "2211" 的结果是 "0A4B"。

方法一：两次遍历

使用两个长度为 10 的数组，secretArray 和 guessArray 分别记录两个字符串中非公牛的各个数字的数量。（下标 0 上的值代表该字符串中 0 的个数）。遍历两个字符串，统计公牛的数量并为数组赋值。不同位上相同的数可以根据两个数组的值来求，对两个数组同位上的最小值求和即可。

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

class Solution {
    public String getHint(String secret, String guess) {
        // secretArray 和 guessArray 分别记录 两个字符串中非公牛的各个数字的数量
        int[] secretArray = new int[10];
        int[] guessArray = new int[10];
        // 公牛
        int A = 0;
        for (int i = 0; i < secret.length(); i++) {
            // 如果同位的数字相等则，公牛++
            if (secret.charAt(i) == guess.charAt(i)) {
                A++;
            } else {
                secretArray[secret.charAt(i) - '0']++;
                guessArray[guess.charAt(i) - '0']++;
            }
        }
        // 奶牛
        int B = 0;
        for (int i = 0; i < 10; i++) {
            // 不同位上的相同数字的数量
            B += Math.min(secretArray[i], guessArray[i]);
        }
        StringBuilder stringBuilder = new StringBuilder();
        return stringBuilder.append(A).append('A').append(B).append('B').toString();
    }
}

看题解后

方法二：一次遍历

我们可以对求奶牛的方法进行优化，将两个数组简化为一个数组。对于每一位，正数代表 secret 中有，负数代表 guess 中有，具体实现如下：

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

class Solution {

    public String getHint(String secret, String guess) {
        int[] array = new int[10];
        int A = 0, B = 0;
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                A++;
            } else {
                // 判断 guess 在 i 之前是否该数字
                if (array[secret.charAt(i) - '0']++ < 0) {
                    B++;
                }
                // 判断 secret 在 i 之前是否该数字
                if (array[guess.charAt(i) - '0']-- > 0) {
                    B++;
                }
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        return stringBuilder.append(A).append('A').append(B).append('B').toString();
    }
}

2、Fizz Buzz（简单）

自己的想法

方法一：暴力

执行用时：1 ms, 在所有 Java 提交中击败了99.05%的用户
内存消耗：39.8 MB, 在所有 Java 提交中击败了35.71%的用户

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 == 0) {
                list.add("FizzBuzz");
            } else if (i % 3 == 0) {
                list.add("Fizz");
            } else if (i % 5 == 0) {
                list.add("Buzz");
            } else {
                list.add(String.valueOf(i));
            }
        }
        return list;
    }
}

看题解后

switch 写法

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            switch ((i % 3 == 0 ? 1 : 0) + (i % 5 == 0 ? 2 : 0)) {
                case 0:
                    list.add(String.valueOf(i));
                    break;
                case 1:
                    list.add("Fizz");
                    break;
                case 2:
                    list.add("Buzz");
                    break;
                case 3:
                    list.add("FizzBuzz");
                    break;
                default:
            }
        }
        return list;
    }
}

方法二：重写 List

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

class Solution {
    public List<String> fizzBuzz(int n) {
        return  new java.util.AbstractList<String>() {
            @Override
            public String get(int i) {
                i++;
                switch ((i % 3 == 0 ? 1 : 0) + (i % 5 == 0 ? 2 : 0)) {
                    case 0:
                        return String.valueOf(i);
                    case 1:
                        return "Fizz";
                    case 2:
                        return "Buzz";
                    case 3:
                        return "FizzBuzz";
                    default:
                        return "";
                }
            }

            @Override
            public int size() {
                return n;
            }
        };
    }
}

方法三：使用 Map 集合易扩展

为了确保输出 FizzBuzz，而不是 BuzzFizz，用 LinkedHashMap/TreeMap 更好。

执行用时：6 ms, 在所有 Java 提交中击败了39.22%的用户
内存消耗：40.1 MB, 在所有 Java 提交中击败了9.01%的用户

class Solution {

    public List<String> fizzBuzz(int n) {
        List<String> result = new ArrayList<>();
        LinkedHashMap<Integer, String> map = new LinkedHashMap<Integer, String>() {{
            put(3, "Fizz");
            put(5, "Buzz");
        }};
        for (int num = 1; num <= n; num++) {
            String numAnsStr = "";
            for (Integer key : map.keySet()) {
                // 拼接合法的字符串
                if (num % key == 0) {
                    numAnsStr = numAnsStr.concat(map.get(key));
                }
            }
            // 如果没有拼接，则拼接原数
            if ("".equals(numAnsStr)) {
                numAnsStr = numAnsStr.concat(Integer.toString(num));
            }
            result.add(numAnsStr);
        }
        return result;
    }
}

3、相对名次（简单）

自己的想法

方法一：排序 + 二分查找

要想知道指定成绩的排名，第一想法就是对成绩进行排序。首先拷贝成绩数组并对其进行排序，接着使用二分查找，查找每个成绩排第几名即可。

执行用时：4 ms, 在所有 Java 提交中击败了97.37%的用户
内存消耗：39.6 MB, 在所有 Java 提交中击败了53.12%的用户

class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        int[] array = new int[n];
        // 拷贝数组
        System.arraycopy(nums, 0, array, 0, n);
        // 对数组进行排序
        Arrays.sort(array);
        String[] result = new String[n];
        for (int i = 0; i < n; i++) {
            // 查找当前成绩排第几名
            int index = n - Arrays.binarySearch(array, nums[i]);
            switch (index) {
                case 1:
                    result[i] = "Gold Medal";
                    break;
                case 2:
                    result[i] = "Silver Medal";
                    break;
                case 3:
                    result[i] = "Bronze Medal";
                    break;
                default:
                    result[i] = String.valueOf(index);
            }
        }
        return result;
    }
}

看题解后

方法二：TreeMap

使用 TreeMap 来实现对成绩得到排序，key 存储成绩，value 存储成绩在数组中的下标。TreeMap 是按照升序进行排序的，所以在遍历集合时，通过计算可以得出当前成绩的排名。

执行用时：12 ms, 在所有 Java 提交中击败了53.80%的用户
内存消耗：40 MB, 在所有 Java 提交中击败了5.13%的用户

class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        String[] result = new String[n];
        // key 为成绩，value 为成绩在数组中的下标，TreeMap 是按照升序进行排序的
        Map<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            map.put(nums[i], i);
        }
        int count = 0;
        for (Map.Entry<Integer, Integer> set : map.entrySet()) {
            // 计算成绩的排名
            int ranking = n - count++;
            switch (ranking) {
                case 1:
                    result[set.getValue()] = "Gold Medal";
                    break;
                case 2:
                    result[set.getValue()] = "Silver Medal";
                    break;
                case 3:
                    result[set.getValue()] = "Bronze Medal";
                    break;
                default:
                    result[set.getValue()] = String.valueOf(ranking);
            }
        }
        return result;
    }
}

方法三：计数排序

首先寻找数组中最大的值（成绩最高的），创建一个 int[] array = new int[max + 1]; 的数组用来实现计数排序。array 数组的下标对应成绩，值为该成绩所在的原数组的下标。由于 array 数组的值默认为 0，所以在存储成绩的下标时，应对下标加 1，取时减 1 即可。

执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.3 MB, 在所有 Java 提交中击败了89.32%的用户

class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        String[] result = new String[n];
        int max = 0;
        // 找出找出最高的成绩
        for (int num : nums) {
            if (max < num) {
                max = num;
            }
        }
        // 下标为成绩，值为成绩在 nums 数组的下标
        int[] array = new int[max + 1];
        for (int i = 0; i < n; i++) {
            array[nums[i]] = i + 1;
        }
        // 记录当前成绩的排名
        int count = 1;
        for (int i = array.length - 1; i >= 0; i--) {
            if (array[i] != 0) {
                // 根据排名进行赋值
                switch (count) {
                    case 1:
                        result[array[i] - 1] = "Gold Medal";
                        break;
                    case 2:
                        result[array[i] - 1] = "Silver Medal";
                        break;
                    case 3:
                        result[array[i] - 1] = "Bronze Medal";
                        break;
                    default:
                        result[array[i] - 1] = String.valueOf(count);
                }
                count++;
            }
        }
        return result;
    }
}

4、最小时间差（中等）

看题解后

方法一：排序

求出每个时间的分钟并进行排序，这样就很容易求出最小分钟差了。

一天有 1440 分钟，如果 timePoints >= 1440 则表示有相等的时间，时间差为 0。
最小分钟差为 0，如果计算时，出现分钟差为 0，则可以直接返回，无需再进行计算。
最大时间和最小时间的分钟差可能最小，需要判断一下。

三种计算时间的方法

慢

    public int minute(String s) {
        String[] strs = s.split(":");
        return Integer.parseInt(strs[0]) * 60 + Integer.parseInt(strs[1]);
    }

中

    public int minute(String s) {
        return Integer.parseInt(s.substring(0, 2)) * 60 + Integer.parseInt(s.substring(3, 5));
    }

快，结果并不是真正的时间，但是差不变。（两数加上相等数，差值不变）

    public int minute(String s) {
        return s.charAt(0) * 600 + s.charAt(1) * 60 + s.charAt(3) * 10 + s.charAt(4);
    }

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

class Solution {
    public int findMinDifference(List<String> timePoints) {
        // 一天有 1440 分钟，如果 timePoints >= 1440 则表示有相等的时间，时间差为 0
        if (timePoints.size() >= 1440) {
            return 0;
        }
        // 用来存储每个时间的分钟
        int[] array = new int[timePoints.size()];
        for (int i = 0; i < timePoints.size(); i++) {
            // 计算分钟
            array[i] = minute(timePoints.get(i));
        }
        // 排序
        Arrays.sort(array);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < array.length; i++) {
            // 求出分钟差
            min = Math.min(min, array[i] - array[i - 1]);
            // 如果有最小分钟差，则直接返回
            if (min == 0) {
                return 0;
            }
        }
        // 最大时间和最小时间的分钟差可能最小，需要判断一下
        return Math.min(min, 1440 + array[0] - array[array.length - 1]);
    }

    public int minute(String s) {
        return s.charAt(0) * 600 + s.charAt(1) * 60 + s.charAt(3) * 10 + s.charAt(4);
    }
}

5、最优除法（中等）

看题解后

方法一：数学法

被除数不变，除数越小，商越大。所以当数组长度大于 2 时，将后面的除数全部括起来，即可得到最大的商。

class Solution {
    public String optimalDivision(int[] nums) {
        if (nums.length == 1) {
            return String.valueOf(nums[0]);
        }
        if (nums.length == 2) {
            StringBuilder s = new StringBuilder();
            return s.append(nums[0]).append("/").append(nums[1]).toString();
        }
        StringBuilder s = new StringBuilder();
        s.append(nums[0]).append("/(");
        for (int i = 1; i < nums.length - 1; i++) {
            s.append(nums[i]).append("/");
        }
        s.append(nums[nums.length - 1]).append(")");
        return s.toString();
    }
}

6、复数乘法（中等）

z=a+bi（a,b均为实数）的数称为复数，a 称为实部，b 称为虚部，i 称为虚数单位。记 z1=(a,b)，z2=(x,y)：

$z1 + z2=(a+x,b+y)$
$(a+ib)×(x+iy)=ax+i2by+i(bx+ay)=ax−by+i(bx+ay)$，即$z1 × z2=(ax-by,bx+ay)$

自己的想法

方法一：暴力

执行用时：1 ms, 在所有 Java 提交中击败了94.28%的用户
内存消耗：36.6 MB, 在所有 Java 提交中击败了81.80%的用户

class Solution {
    public String complexNumberMultiply(String a, String b) {
        String[] aArray = a.split("\\+");
        String[] bArray = b.split("\\+");
        int a1 = Integer.parseInt(aArray[0]);
        int b1 = Integer.parseInt(aArray[1].substring(0, aArray[1].length() - 1));
        int c = Integer.parseInt(bArray[0]);
        int d = Integer.parseInt(bArray[1].substring(0, bArray[1].length() - 1));
        return new StringBuilder().append(a1 * c - b1 * d).append("+").append(a1 * d + c * b1).append("i").toString();
    }
}

性能优化

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

class Solution {
    public String complexNumberMultiply(String a, String b) {
        // 获取加号的下标
        int aplus = a.indexOf('+'), bplus = b.indexOf('+');
        int a1 = Integer.parseInt(a.substring(0, aplus));
        int b1 = Integer.parseInt(a.substring(aplus + 1, a.length() - 1));
        int c = Integer.parseInt(b.substring(0, bplus));
        int d = Integer.parseInt(b.substring(bplus + 1, b.length() - 1));
        return new StringBuilder().append(a1 * c - b1 * d).append('+').append(a1 * d + b1 * c).append('i').toString();
    }
}

7、分数加减运算（中等）

看题解后

方法一：逐个通分

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

class Solution {
    public String fractionAddition(String expression) {
        // 0 表示当前分子的值，1 表示当前分母的值
        int[] output = new int[]{0, 1};
        // 当前分数的正负号，字符串的下标
        int sign = 1, index = 0;
        while (index < expression.length()) {
            // 获取当前分数的符号
            if (expression.charAt(index) == '-') {
                sign = -1;
                index++;
            } else if (expression.charAt(index) == '+') {
                sign = 1;
                index++;
            }
            // 分子和分母
            int molecule = 0, denominator = 0;
            // 寻找分子，找到 / 则结束
            while (expression.charAt(index) != '/') {
                molecule = molecule * 10 + expression.charAt(index) - '0';
                index++;
            }
            index++;
            // 寻找分母，找到非数字则结束
            while (index < expression.length() && Character.isDigit(expression.charAt(index))) {
                denominator = denominator * 10 + expression.charAt(index) - '0';
                index++;
            }
            // 通分,求分子和
            output[0] = output[0] * denominator + sign * output[1] * molecule;
            // 通分,求分母
            output[1] = output[1] * denominator;
        }
        // 如果分子等于 0，则为 0/1
        if (output[0] == 0) {
            output[1] = 1;
        } else {
            // 求最大公因数，把分子转为正数
            int a = Math.abs(output[0]);
            int b = output[1];
            while (b != 0) {
                int tmp = b;
                b = a % b;
                a = tmp;
            }
            // 化简
            output[0] = output[0] / a;
            output[1] = output[1] / a;
        }
        // 拼接字符串
        return new StringBuilder().append(output[0]).append("/").append(output[1]).toString();
    }
}

8、求解方程（中等）

自己的想法

方法一：拆分方程

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

class Solution {
    public String solveEquation(String equation) {
        // leftx 左x前的系数，leftn 左常数，rightx 右x前的系数，rightn 右常数
        int leftx = 0, leftn = 0, rightx = 0, rightn = 0;
        // 记录当前数字的符号，字符串的下标
        int sign = 1, index = 0;
        // 记录当前是左边还是右边
        boolean is = true;
        while (index < equation.length()) {
            // 如果发现 =，则更换方向，并刷新符号
            if (equation.charAt(index) == '=') {
                index++;
                sign = 1;
                is = false;
            }
            // 截取符号
            if (equation.charAt(index) == '+') {
                sign = 1;
                index++;
            } else if (equation.charAt(index) == '-') {
                sign = -1;
                index++;
            }
            // 计算数字
            int number = 0;
            while (index < equation.length() && Character.isDigit(equation.charAt(index))) {
                number = number * 10 + equation.charAt(index++) - '0';
            }
            // 如果下一个字符为 x，则表示当前数字为 x 的系数
            if (index < equation.length() && equation.charAt(index) == 'x') {
                // 可能出现 0x ，应不做处理 ，所以需要判断
                if (index == 0 || equation.charAt(index - 1) != '0') {
                    if (is) {
                        // number 默认为 0，可能出现 x，应为 1x 加 1
                        leftx += sign * (number == 0 ? 1 : number);
                    } else {
                        rightx += sign * (number == 0 ? 1 : number);
                    }
                }
                index++;
            } else {
                if (is) {
                    leftn += sign * number;
                } else {
                    rightn += sign * number;
                }
            }
        }
        // 求左边 x 的系数
        leftx -= rightx;
        // 求右边的常数
        rightn -= leftn;
        // 如果两遍都为 0，则表示有无限解
        if (leftx == 0 && rightn == 0) {
            return "Infinite solutions";
        } else if (leftx == 0) {
            // 如果只有 x 的系数为 0，则表示没有解
            return "No solution";
        } else {
            StringBuilder s = new StringBuilder();
            return s.append("x=").append(rightn / leftx).toString();
        }
    }
}

9、外观数列（简单）

自己的想法

方法一：循环

执行用时：8 ms, 在所有 Java 提交中击败了36.13%的用户
内存消耗：36 MB, 在所有 Java 提交中击败了70.93%的用户

class Solution {
    public String countAndSay(int n) {
        StringBuilder result = new StringBuilder();
        result.append(1);
        for (int i = 1; i < n; i++) {
            // 记录当前行的字符串
            StringBuilder s = new StringBuilder();
            // 记录每个数字的开始索引
            int start = 0;
            for (int j = 1; j < result.length(); j++) {
                // 当数字发生改变时执行
                if (result.charAt(j) != result.charAt(start)) {
                    s.append(j - start).append(result.charAt(start));
                    start = j;
                }
            }
            // 字符串最后一个数字
            s.append(result.length() - start).append(result.charAt(start));
            result = s;
        }
        return result.toString();
    }
}

看题解后

方法二：递归

执行用时：2 ms, 在所有 Java 提交中击败了91.78%的用户
内存消耗：36.2 MB, 在所有 Java 提交中击败了49.94%的用户

class Solution {
    public String countAndSay(int n) {
        // 递归终止条件
        if (n == 1) {
            return "1";
        }
        // 获取到上一层的字符串
        String s = countAndSay(n - 1);
        StringBuilder result = new StringBuilder();
        // 记录每个数字的开始索引
        int start = 0;
        for (int i = 1; i < s.length(); i++) {
            // 当数字发生改变时执行
            if (s.charAt(i) != s.charAt(start)) {
                result.append(i - start).append(s.charAt(start));
                start = i;
            }
        }
        // 字符串最后一个数字
        result.append(s.length() - start).append(s.charAt(start));
        return result.toString();
    }
}

10、压缩字符串（中等）

自己的想法

方法一：双指针

执行用时：1 ms, 在所有 Java 提交中击败了98.52%的用户
内存消耗：38 MB, 在所有 Java 提交中击败了80.26%的用户

class Solution {
    public int compress(char[] chars) {
        // start 记录新字符的起始下标，index 记录当前存储的下标
        int start = 0, index = 0;
        for (int i = 1; i <= chars.length ; i++) {
            // 如果字符发生改变或遍历到最后一位则进行存储
            if (i == chars.length || chars[i] != chars[start]) {
                // 存储字符
                chars[index++] = chars[start];
                // 计算长度，长度为 1 不存储
                int length = i - start;
                if (length != 1) {
                    for (char c :  String.valueOf(length).toCharArray()) {
                        chars[index++] = c;
                    }
                }
                // 更换新字符的起始下标
                start = i;
            }
        }
        return index;
    }
}

11、字符串转换整数 (atoi)（中等）

自己的想法

方法一：暴力

执行用时：2 ms, 在所有 Java 提交中击败了99.30%的用户
内存消耗：38.3 MB, 在所有 Java 提交中击败了80.98%的用户

class Solution {
    public int myAtoi(String s) {
        // index 记录字符串的下标
        int n = s.length(), index = 0;
        // true 表示正数
        boolean sign = true;
        // 因为可能超过 Integer 界限，所以用 Long
        long result = 0;
        // 消除空格
        while (index < n && s.charAt(index) == ' ') {
            index++;
        }
        // 判断符号
        if (index < n && s.charAt(index) == '-') {
            sign = false;
            index++;
        } else if (index < n && s.charAt(index) == '+') {
            index++;
        }
        // 如果不是数字则结束循环
        while (index < n && Character.isDigit(s.charAt(index))) {
            result = result * 10 + s.charAt(index++) - '0';
            // 判断是否越正数界
            if (sign && result > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            } else if (!sign && result > Integer.MAX_VALUE + 1L) {
                // 判断是否越负数界
                return Integer.MIN_VALUE;
            }
        }
        return sign ? (int) result : (int) result * -1;
    }
}

12、罗马数字转整数（简单）

自己的想法

方法一：暴力

执行用时：4 ms, 在所有 Java 提交中击败了99.95%的用户
内存消耗：38.4 MB, 在所有 Java 提交中击败了85.07%的用户

class Solution {
    public int romanToInt(String s) {
        if (s.length() == 0) {
            return 0;
        }
        char front = s.charAt(0);
        int result = 0;
        for (char c : s.toCharArray()) {
            switch (c) {
                case 'I':
                    result += 1;
                    break;
                case 'V':
                    if (front == 'I') {
                        // 因为之前多加了个 I，所以这里是 3
                        result += 3;
                    } else {
                        result += 5;
                    }
                    break;
                case 'X':
                    if (front == 'I') {
                        result += 8;
                    } else {
                        result += 10;
                    }
                    break;
                case 'L':
                    if (front == 'X') {
                        result += 30;
                    } else {
                        result += 50;
                    }
                    break;
                case 'C':
                    if (front == 'X') {
                        result += 80;
                    } else {
                        result += 100;
                    }
                    break;
                case 'D':
                    if (front == 'C') {
                        result += 300;
                    } else {
                        result += 500;
                    }
                    break;
                case 'M':
                    if (front == 'C') {
                        result += 800;
                    } else {
                        result += 1000;
                    }
                    break;
                default:
            }
            front = c;
        }
        return result;
    }
}

13、整数转罗马数字（中等）

自己的想法

方法一：贪心

执行用时：5 ms, 在所有 Java 提交中击败了91.86%的用户
内存消耗：37.7 MB, 在所有 Java 提交中击败了87.93%的用户

class Solution {
    public String intToRoman(int num) {
        int[] number = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] letter = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < number.length; i++) {
            // 如果足够，则进行减法操作
            while (num >= number[i]) {
                num -= number[i];
                s.append(letter[i]);
            }
        }
        return s.toString();
    }
}

14、整数转换英文表示（困难）

看题解后

方法一：分治法

执行用时：2 ms, 在所有 Java 提交中击败了98.69%的用户
内存消耗：36.6 MB, 在所有 Java 提交中击败了80.89%的用户

class Solution {
    // one[2] = 2 数值的字符串表示
    String[] one = {"Zero", "One", "Two", "Three", "Four", "Five", "Six",
            "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
            "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    // ten[2] = 2 * 10 数值的字符串表示
    String[] ten = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty",
            "Sixty", "Seventy", "Eighty", "Ninety"};

    /**
     * 分治法 + 哈希表方式
     */
    public String numberToWords(int num) {
        if (num == 0) {
            return one[0];
        }
        StringBuilder sb = new StringBuilder();
        if (num / 1_000_000_000 > 0) {
            // 取十亿位
            sb.append(one[num / 1_000_000_000]);
            sb.append(" Billion");
            num = num % 1_000_000_000;
        }
        if (num / 1_000_000 > 0) {
            // 取百万位（亿、千万、百万）
            getThree(num / 1_000_000, sb);
            sb.append(" Million");
            num = num % 1_000_000;
        }
        if (num / 1000 > 0) {
            // 取千位（十万、万、千）
            getThree(num / 1000, sb);
            sb.append(" Thousand");
            num = num % 1000;
        }
        if (num > 0) {
            // 取个位（百、十、个）
            getThree(num, sb);
        }
        return sb.toString();
    }

    public void getThree(int num, StringBuilder sb) {
        if (num / 100 > 0) {
            // 取百位
            if (sb.length() > 0) {
                sb.append(" ");
            }
            sb.append(one[num / 100]);
            sb.append(" Hundred");
            num = num % 100;
        }
        if (num == 0) {
            return;
        }
        // 取十位
        if (num < 20) {
            // 可直接取值的情况：10，11，12，13...19
            if (sb.length() > 0) {
                sb.append(" ");
            }
            sb.append(one[num]);
        } else {
            // [20, 99] 的情况，需要十位 + 个位分别转换字符串
            if (sb.length() > 0) {
                sb.append(" ");
            }
            // 十位转换
            sb.append(ten[num / 10]);
            num = num % 10;
            if (num > 0) {
                if (sb.length() > 0) {
                    sb.append(" ");
                }
                // 个位转换
                sb.append(one[num]);
            }
        }
    }
}

15、比较版本号（中等）

自己的想法

方法一：双指针

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

class Solution {

    public int compareVersion(String version1, String version2) {
        int index1 = 0, index2 = 0;
        while (index1 < version1.length() || index2 < version2.length()) {
            // 记录 v1 下标从 index1 到小数点的数值
            int number1 = 0;
            for (int i = index1; i <= version1.length(); i++) {
                if (i == version1.length() || version1.charAt(i) == '.') {
                    // 更新下次的起始下标
                    index1 = i + 1;
                    break;
                }
                number1 = number1 * 10 + version1.charAt(i) - '0';
            }
            // 记录 v2 下标从 index2 到小数点的数值
            int number2 = 0;
            for (int i = index2; i <= version2.length(); i++) {
                if (i == version2.length() || version2.charAt(i) == '.') {
                    index2 = i + 1;
                    break;
                }
                number2 = number2 * 10 + version2.charAt(i) - '0';
            }
            if (number1 > number2) {
                return 1;
            } else if (number1 < number2) {
                return -1;
            }
        }
        return 0;
    }
}

16、神奇字符串（中等）

自己的想法

题意

字符串 S 的前几个元素如下：S = "1221121221221121122 ......"，我们来研究一下字符串 S 是如何生成的。

假设字符串 S 第一个字符为 1 时，那么第二个字符是什么呢？
我们不妨假设还存在一个字符串 A 它决定字符串 S 中连续字符的个数且字符串 A 等于字符串 S。
所以当字符串 S 的第一个字符为 1 时，字符串 A 的第一个字符也为 1。
因为字符串 A 决定字符串 S 中连续字符的个数，所以字符串 S 的第一个字符最多能有 1 个。
因为字符串 S 只包含 '1' 和 '2'且第一个字符最多能有 1 个，所以第二个字符一定为 2。
S = 12 所以 A = 12，因为 A 的第二个字符为 2，所以 S 中第二个字符应该出现两次，S = 122。
S = 122 所以 A = 122，因为 A 的第三个字符为 2，所以 S 的下一个字符也应该出现两次，S = 12211。
S = 12211 所以 A = 12211，因为 A 的第四个字符为 1，所以 S 的下一个字符出现一次，S = 122112。
...

之后只需生成一个长度为 n 的字符串 S，统计其中 1 的个数即可。题目中的示例的解释写错了，前 6 个元素应该是 122112，它只给了 5 个元素。

方法一：使用 StringBuilder

执行用时：20 ms, 在所有 Java 提交中击败了38.81%的用户
内存消耗：37.4 MB, 在所有 Java 提交中击败了70.90%的用户

class Solution {
  
    public int magicalString(int n) {
        // index 表示字符串 A 的索引，根据该索引的字符生成指定个数的字符，
        int index = 1;
        StringBuilder s = new StringBuilder();
        // 第一个字符为 1
        s.append(1);
        while (s.length() < n) {
            // 因为需要根据字符串 A，来确定在字符串 S 生成字符的个数
            // 所以当字符串 A 越界时，则根据前一个字符进行生成
            if (index == s.length()) {
                // 如果前一个字符为 1，则生成 22。
                s.append(s.charAt(s.length() - 1) == '1' ? 22 : 1);
                index++;
            } else {
                // 如果字符串 A 没有越界，则字符串 A 决定生成字符的个数。
                // 而字符串 S 的最后一个字符决定生成的字符是 1 还是 2
                if (s.charAt(s.length() - 1) == '1') {
                    s.append(s.charAt(index++) == '1' ? 2 : 22);
                } else {
                    s.append(s.charAt(index++) == '1' ? 1 : 11);
                }
            }
        }
        // count 统计 1 的个数
        int count = 0;
        // 遍历字符串统计 1 的个数
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                count++;
            }
        }
        return count;
    }
}

看题解后

方法二：使用 int[]

通过观察我们不难发现，只有生成第二个字符时，会出现 index == s.length()，即字符串 A 越界。后面生成字符串时只会越来越多，不可能再出现字符串 A 越界的情况，所以我们可以将前三个字符提前设置好。

执行用时：3 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.6 MB, 在所有 Java 提交中击败了59.70%的用户

class Solution {

    public int magicalString(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 3) {
            return 1;
        }
        int[] array = new int[n];
        // 设置初值
        array[0] = 1;array[1] = 2;array[2] = 2;
        // 统计 1 的个数，前三个字符中有 1 个 1
        int count = 1;
        // index 表示字符串 A 的索引，length 表示字符串有效字符的个数， value 表示下次生成的字符
        int index = 2, length = 3, value = 1;
        while (length < n) {
            // 根据 array[index] 的值决定生成几个 value
            for (int i = 0; i < array[index] && length < n; i++) {
                array[length++] = value;
                // 统计 1 的个数
                if (value == 1) {
                    count++;
                }
            }
            // 更换生成的字符，3-1=2，3-2=1，实现 1 和 2 的交替
            value = 3 - value;
            index++;
        }
        return count;
    }
}

标题：数字与字符串间转换——LeetCode
作者：Yi-Xing
地址：http://zyxwmj.top/articles/2021/04/04/1617544382668.html
博客中若有不恰当的地方，请您一定要告诉我。前路崎岖，望我们可以互相帮助，并肩前行！