数字与字符串间转换——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%的用户

 1class Solution {
 2    public String getHint(String secret, String guess) {
 3        // secretArray 和 guessArray 分别记录 两个字符串中非公牛的各个数字的数量
 4        int[] secretArray = new int[10];
 5        int[] guessArray = new int[10];
 6        // 公牛
 7        int A = 0;
 8        for (int i = 0; i < secret.length(); i++) {
 9            // 如果同位的数字相等则，公牛++
10            if (secret.charAt(i) == guess.charAt(i)) {
11                A++;
12            } else {
13                secretArray[secret.charAt(i) - '0']++;
14                guessArray[guess.charAt(i) - '0']++;
15            }
16        }
17        // 奶牛
18        int B = 0;
19        for (int i = 0; i < 10; i++) {
20            // 不同位上的相同数字的数量
21            B += Math.min(secretArray[i], guessArray[i]);
22        }
23        StringBuilder stringBuilder = new StringBuilder();
24        return stringBuilder.append(A).append('A').append(B).append('B').toString();
25    }
26}

看题解后

方法二：一次遍历

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

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

 1class Solution {
 2
 3    public String getHint(String secret, String guess) {
 4        int[] array = new int[10];
 5        int A = 0, B = 0;
 6        for (int i = 0; i < secret.length(); i++) {
 7            if (secret.charAt(i) == guess.charAt(i)) {
 8                A++;
 9            } else {
10                // 判断 guess 在 i 之前是否该数字
11                if (array[secret.charAt(i) - '0']++ < 0) {
12                    B++;
13                }
14                // 判断 secret 在 i 之前是否该数字
15                if (array[guess.charAt(i) - '0']-- > 0) {
16                    B++;
17                }
18            }
19        }
20        StringBuilder stringBuilder = new StringBuilder();
21        return stringBuilder.append(A).append('A').append(B).append('B').toString();
22    }
23}

2、Fizz Buzz（简单）

自己的想法

方法一：暴力

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

 1class Solution {
 2    public List<String> fizzBuzz(int n) {
 3        List<String> list = new ArrayList<>();
 4        for (int i = 1; i <= n; i++) {
 5            if (i % 3 == 0 && i % 5 == 0) {
 6                list.add("FizzBuzz");
 7            } else if (i % 3 == 0) {
 8                list.add("Fizz");
 9            } else if (i % 5 == 0) {
10                list.add("Buzz");
11            } else {
12                list.add(String.valueOf(i));
13            }
14        }
15        return list;
16    }
17}

看题解后

switch 写法

 1class Solution {
 2    public List<String> fizzBuzz(int n) {
 3        List<String> list = new ArrayList<>();
 4        for (int i = 1; i <= n; i++) {
 5            switch ((i % 3 == 0 ? 1 : 0) + (i % 5 == 0 ? 2 : 0)) {
 6                case 0:
 7                    list.add(String.valueOf(i));
 8                    break;
 9                case 1:
10                    list.add("Fizz");
11                    break;
12                case 2:
13                    list.add("Buzz");
14                    break;
15                case 3:
16                    list.add("FizzBuzz");
17                    break;
18                default:
19            }
20        }
21        return list;
22    }
23}

方法二：重写 List

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

 1class Solution {
 2    public List<String> fizzBuzz(int n) {
 3        return  new java.util.AbstractList<String>() {
 4            @Override
 5            public String get(int i) {
 6                i++;
 7                switch ((i % 3 == 0 ? 1 : 0) + (i % 5 == 0 ? 2 : 0)) {
 8                    case 0:
 9                        return String.valueOf(i);
10                    case 1:
11                        return "Fizz";
12                    case 2:
13                        return "Buzz";
14                    case 3:
15                        return "FizzBuzz";
16                    default:
17                        return "";
18                }
19            }
20
21            @Override
22            public int size() {
23                return n;
24            }
25        };
26    }
27}

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

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

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

 1class Solution {
 2
 3    public List<String> fizzBuzz(int n) {
 4        List<String> result = new ArrayList<>();
 5        LinkedHashMap<Integer, String> map = new LinkedHashMap<Integer, String>() {{
 6            put(3, "Fizz");
 7            put(5, "Buzz");
 8        }};
 9        for (int num = 1; num <= n; num++) {
10            String numAnsStr = "";
11            for (Integer key : map.keySet()) {
12                // 拼接合法的字符串
13                if (num % key == 0) {
14                    numAnsStr = numAnsStr.concat(map.get(key));
15                }
16            }
17            // 如果没有拼接，则拼接原数
18            if ("".equals(numAnsStr)) {
19                numAnsStr = numAnsStr.concat(Integer.toString(num));
20            }
21            result.add(numAnsStr);
22        }
23        return result;
24    }
25}

3、相对名次（简单）

自己的想法

方法一：排序 + 二分查找

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

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

 1class Solution {
 2    public String[] findRelativeRanks(int[] nums) {
 3        int n = nums.length;
 4        int[] array = new int[n];
 5        // 拷贝数组
 6        System.arraycopy(nums, 0, array, 0, n);
 7        // 对数组进行排序
 8        Arrays.sort(array);
 9        String[] result = new String[n];
10        for (int i = 0; i < n; i++) {
11            // 查找当前成绩排第几名
12            int index = n - Arrays.binarySearch(array, nums[i]);
13            switch (index) {
14                case 1:
15                    result[i] = "Gold Medal";
16                    break;
17                case 2:
18                    result[i] = "Silver Medal";
19                    break;
20                case 3:
21                    result[i] = "Bronze Medal";
22                    break;
23                default:
24                    result[i] = String.valueOf(index);
25            }
26        }
27        return result;
28    }
29}

看题解后

方法二：TreeMap

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

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

 1class Solution {
 2    public String[] findRelativeRanks(int[] nums) {
 3        int n = nums.length;
 4        String[] result = new String[n];
 5        // key 为成绩，value 为成绩在数组中的下标，TreeMap 是按照升序进行排序的
 6        Map<Integer, Integer> map = new TreeMap<>();
 7        for (int i = 0; i < n; i++) {
 8            map.put(nums[i], i);
 9        }
10        int count = 0;
11        for (Map.Entry<Integer, Integer> set : map.entrySet()) {
12            // 计算成绩的排名
13            int ranking = n - count++;
14            switch (ranking) {
15                case 1:
16                    result[set.getValue()] = "Gold Medal";
17                    break;
18                case 2:
19                    result[set.getValue()] = "Silver Medal";
20                    break;
21                case 3:
22                    result[set.getValue()] = "Bronze Medal";
23                    break;
24                default:
25                    result[set.getValue()] = String.valueOf(ranking);
26            }
27        }
28        return result;
29    }
30}

方法三：计数排序

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

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

 1class Solution {
 2    public String[] findRelativeRanks(int[] nums) {
 3        int n = nums.length;
 4        String[] result = new String[n];
 5        int max = 0;
 6        // 找出找出最高的成绩
 7        for (int num : nums) {
 8            if (max < num) {
 9                max = num;
10            }
11        }
12        // 下标为成绩，值为成绩在 nums 数组的下标
13        int[] array = new int[max + 1];
14        for (int i = 0; i < n; i++) {
15            array[nums[i]] = i + 1;
16        }
17        // 记录当前成绩的排名
18        int count = 1;
19        for (int i = array.length - 1; i >= 0; i--) {
20            if (array[i] != 0) {
21                // 根据排名进行赋值
22                switch (count) {
23                    case 1:
24                        result[array[i] - 1] = "Gold Medal";
25                        break;
26                    case 2:
27                        result[array[i] - 1] = "Silver Medal";
28                        break;
29                    case 3:
30                        result[array[i] - 1] = "Bronze Medal";
31                        break;
32                    default:
33                        result[array[i] - 1] = String.valueOf(count);
34                }
35                count++;
36            }
37        }
38        return result;
39    }
40}

4、最小时间差（中等）

看题解后

方法一：排序

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

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

三种计算时间的方法

慢

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

中

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

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

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

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

 1class Solution {
 2    public int findMinDifference(List<String> timePoints) {
 3        // 一天有 1440 分钟，如果 timePoints >= 1440 则表示有相等的时间，时间差为 0
 4        if (timePoints.size() >= 1440) {
 5            return 0;
 6        }
 7        // 用来存储每个时间的分钟
 8        int[] array = new int[timePoints.size()];
 9        for (int i = 0; i < timePoints.size(); i++) {
10            // 计算分钟
11            array[i] = minute(timePoints.get(i));
12        }
13        // 排序
14        Arrays.sort(array);
15        int min = Integer.MAX_VALUE;
16        for (int i = 1; i < array.length; i++) {
17            // 求出分钟差
18            min = Math.min(min, array[i] - array[i - 1]);
19            // 如果有最小分钟差，则直接返回
20            if (min == 0) {
21                return 0;
22            }
23        }
24        // 最大时间和最小时间的分钟差可能最小，需要判断一下
25        return Math.min(min, 1440 + array[0] - array[array.length - 1]);
26    }
27
28    public int minute(String s) {
29        return s.charAt(0) * 600 + s.charAt(1) * 60 + s.charAt(3) * 10 + s.charAt(4);
30    }
31}

5、最优除法（中等）

看题解后

方法一：数学法

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

 1class Solution {
 2    public String optimalDivision(int[] nums) {
 3        if (nums.length == 1) {
 4            return String.valueOf(nums[0]);
 5        }
 6        if (nums.length == 2) {
 7            StringBuilder s = new StringBuilder();
 8            return s.append(nums[0]).append("/").append(nums[1]).toString();
 9        }
10        StringBuilder s = new StringBuilder();
11        s.append(nums[0]).append("/(");
12        for (int i = 1; i < nums.length - 1; i++) {
13            s.append(nums[i]).append("/");
14        }
15        s.append(nums[nums.length - 1]).append(")");
16        return s.toString();
17    }
18}

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%的用户

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

性能优化

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

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

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

看题解后

方法一：逐个通分

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

 1class Solution {
 2    public String fractionAddition(String expression) {
 3        // 0 表示当前分子的值，1 表示当前分母的值
 4        int[] output = new int[]{0, 1};
 5        // 当前分数的正负号，字符串的下标
 6        int sign = 1, index = 0;
 7        while (index < expression.length()) {
 8            // 获取当前分数的符号
 9            if (expression.charAt(index) == '-') {
10                sign = -1;
11                index++;
12            } else if (expression.charAt(index) == '+') {
13                sign = 1;
14                index++;
15            }
16            // 分子和分母
17            int molecule = 0, denominator = 0;
18            // 寻找分子，找到 / 则结束
19            while (expression.charAt(index) != '/') {
20                molecule = molecule * 10 + expression.charAt(index) - '0';
21                index++;
22            }
23            index++;
24            // 寻找分母，找到非数字则结束
25            while (index < expression.length() && Character.isDigit(expression.charAt(index))) {
26                denominator = denominator * 10 + expression.charAt(index) - '0';
27                index++;
28            }
29            // 通分,求分子和
30            output[0] = output[0] * denominator + sign * output[1] * molecule;
31            // 通分,求分母
32            output[1] = output[1] * denominator;
33        }
34        // 如果分子等于 0，则为 0/1
35        if (output[0] == 0) {
36            output[1] = 1;
37        } else {
38            // 求最大公因数，把分子转为正数
39            int a = Math.abs(output[0]);
40            int b = output[1];
41            while (b != 0) {
42                int tmp = b;
43                b = a % b;
44                a = tmp;
45            }
46            // 化简
47            output[0] = output[0] / a;
48            output[1] = output[1] / a;
49        }
50        // 拼接字符串
51        return new StringBuilder().append(output[0]).append("/").append(output[1]).toString();
52    }
53}

8、求解方程（中等）

自己的想法

方法一：拆分方程

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

 1class Solution {
 2    public String solveEquation(String equation) {
 3        // leftx 左x前的系数，leftn 左常数，rightx 右x前的系数，rightn 右常数
 4        int leftx = 0, leftn = 0, rightx = 0, rightn = 0;
 5        // 记录当前数字的符号，字符串的下标
 6        int sign = 1, index = 0;
 7        // 记录当前是左边还是右边
 8        boolean is = true;
 9        while (index < equation.length()) {
10            // 如果发现 =，则更换方向，并刷新符号
11            if (equation.charAt(index) == '=') {
12                index++;
13                sign = 1;
14                is = false;
15            }
16            // 截取符号
17            if (equation.charAt(index) == '+') {
18                sign = 1;
19                index++;
20            } else if (equation.charAt(index) == '-') {
21                sign = -1;
22                index++;
23            }
24            // 计算数字
25            int number = 0;
26            while (index < equation.length() && Character.isDigit(equation.charAt(index))) {
27                number = number * 10 + equation.charAt(index++) - '0';
28            }
29            // 如果下一个字符为 x，则表示当前数字为 x 的系数
30            if (index < equation.length() && equation.charAt(index) == 'x') {
31                // 可能出现 0x ，应不做处理 ，所以需要判断
32                if (index == 0 || equation.charAt(index - 1) != '0') {
33                    if (is) {
34                        // number 默认为 0，可能出现 x，应为 1x 加 1
35                        leftx += sign * (number == 0 ? 1 : number);
36                    } else {
37                        rightx += sign * (number == 0 ? 1 : number);
38                    }
39                }
40                index++;
41            } else {
42                if (is) {
43                    leftn += sign * number;
44                } else {
45                    rightn += sign * number;
46                }
47            }
48        }
49        // 求左边 x 的系数
50        leftx -= rightx;
51        // 求右边的常数
52        rightn -= leftn;
53        // 如果两遍都为 0，则表示有无限解
54        if (leftx == 0 && rightn == 0) {
55            return "Infinite solutions";
56        } else if (leftx == 0) {
57            // 如果只有 x 的系数为 0，则表示没有解
58            return "No solution";
59        } else {
60            StringBuilder s = new StringBuilder();
61            return s.append("x=").append(rightn / leftx).toString();
62        }
63    }
64}

9、外观数列（简单）

自己的想法

方法一：循环

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

 1class Solution {
 2    public String countAndSay(int n) {
 3        StringBuilder result = new StringBuilder();
 4        result.append(1);
 5        for (int i = 1; i < n; i++) {
 6            // 记录当前行的字符串
 7            StringBuilder s = new StringBuilder();
 8            // 记录每个数字的开始索引
 9            int start = 0;
10            for (int j = 1; j < result.length(); j++) {
11                // 当数字发生改变时执行
12                if (result.charAt(j) != result.charAt(start)) {
13                    s.append(j - start).append(result.charAt(start));
14                    start = j;
15                }
16            }
17            // 字符串最后一个数字
18            s.append(result.length() - start).append(result.charAt(start));
19            result = s;
20        }
21        return result.toString();
22    }
23}

看题解后

方法二：递归

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

 1class Solution {
 2    public String countAndSay(int n) {
 3        // 递归终止条件
 4        if (n == 1) {
 5            return "1";
 6        }
 7        // 获取到上一层的字符串
 8        String s = countAndSay(n - 1);
 9        StringBuilder result = new StringBuilder();
10        // 记录每个数字的开始索引
11        int start = 0;
12        for (int i = 1; i < s.length(); i++) {
13            // 当数字发生改变时执行
14            if (s.charAt(i) != s.charAt(start)) {
15                result.append(i - start).append(s.charAt(start));
16                start = i;
17            }
18        }
19        // 字符串最后一个数字
20        result.append(s.length() - start).append(s.charAt(start));
21        return result.toString();
22    }
23}

10、压缩字符串（中等）

自己的想法

方法一：双指针

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

 1class Solution {
 2    public int compress(char[] chars) {
 3        // start 记录新字符的起始下标，index 记录当前存储的下标
 4        int start = 0, index = 0;
 5        for (int i = 1; i <= chars.length ; i++) {
 6            // 如果字符发生改变或遍历到最后一位则进行存储
 7            if (i == chars.length || chars[i] != chars[start]) {
 8                // 存储字符
 9                chars[index++] = chars[start];
10                // 计算长度，长度为 1 不存储
11                int length = i - start;
12                if (length != 1) {
13                    for (char c :  String.valueOf(length).toCharArray()) {
14                        chars[index++] = c;
15                    }
16                }
17                // 更换新字符的起始下标
18                start = i;
19            }
20        }
21        return index;
22    }
23}

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

自己的想法

方法一：暴力

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

 1class Solution {
 2    public int myAtoi(String s) {
 3        // index 记录字符串的下标
 4        int n = s.length(), index = 0;
 5        // true 表示正数
 6        boolean sign = true;
 7        // 因为可能超过 Integer 界限，所以用 Long
 8        long result = 0;
 9        // 消除空格
10        while (index < n && s.charAt(index) == ' ') {
11            index++;
12        }
13        // 判断符号
14        if (index < n && s.charAt(index) == '-') {
15            sign = false;
16            index++;
17        } else if (index < n && s.charAt(index) == '+') {
18            index++;
19        }
20        // 如果不是数字则结束循环
21        while (index < n && Character.isDigit(s.charAt(index))) {
22            result = result * 10 + s.charAt(index++) - '0';
23            // 判断是否越正数界
24            if (sign && result > Integer.MAX_VALUE) {
25                return Integer.MAX_VALUE;
26            } else if (!sign && result > Integer.MAX_VALUE + 1L) {
27                // 判断是否越负数界
28                return Integer.MIN_VALUE;
29            }
30        }
31        return sign ? (int) result : (int) result * -1;
32    }
33}

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

自己的想法

方法一：暴力

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

 1class Solution {
 2    public int romanToInt(String s) {
 3        if (s.length() == 0) {
 4            return 0;
 5        }
 6        char front = s.charAt(0);
 7        int result = 0;
 8        for (char c : s.toCharArray()) {
 9            switch (c) {
10                case 'I':
11                    result += 1;
12                    break;
13                case 'V':
14                    if (front == 'I') {
15                        // 因为之前多加了个 I，所以这里是 3
16                        result += 3;
17                    } else {
18                        result += 5;
19                    }
20                    break;
21                case 'X':
22                    if (front == 'I') {
23                        result += 8;
24                    } else {
25                        result += 10;
26                    }
27                    break;
28                case 'L':
29                    if (front == 'X') {
30                        result += 30;
31                    } else {
32                        result += 50;
33                    }
34                    break;
35                case 'C':
36                    if (front == 'X') {
37                        result += 80;
38                    } else {
39                        result += 100;
40                    }
41                    break;
42                case 'D':
43                    if (front == 'C') {
44                        result += 300;
45                    } else {
46                        result += 500;
47                    }
48                    break;
49                case 'M':
50                    if (front == 'C') {
51                        result += 800;
52                    } else {
53                        result += 1000;
54                    }
55                    break;
56                default:
57            }
58            front = c;
59        }
60        return result;
61    }
62}

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

自己的想法

方法一：贪心

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

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

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

看题解后

方法一：分治法

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

 1class Solution {
 2    // one[2] = 2 数值的字符串表示
 3    String[] one = {"Zero", "One", "Two", "Three", "Four", "Five", "Six",
 4            "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
 5            "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
 6    // ten[2] = 2 * 10 数值的字符串表示
 7    String[] ten = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty",
 8            "Sixty", "Seventy", "Eighty", "Ninety"};
 9
10    /**
11     * 分治法 + 哈希表方式
12     */
13    public String numberToWords(int num) {
14        if (num == 0) {
15            return one[0];
16        }
17        StringBuilder sb = new StringBuilder();
18        if (num / 1_000_000_000 > 0) {
19            // 取十亿位
20            sb.append(one[num / 1_000_000_000]);
21            sb.append(" Billion");
22            num = num % 1_000_000_000;
23        }
24        if (num / 1_000_000 > 0) {
25            // 取百万位（亿、千万、百万）
26            getThree(num / 1_000_000, sb);
27            sb.append(" Million");
28            num = num % 1_000_000;
29        }
30        if (num / 1000 > 0) {
31            // 取千位（十万、万、千）
32            getThree(num / 1000, sb);
33            sb.append(" Thousand");
34            num = num % 1000;
35        }
36        if (num > 0) {
37            // 取个位（百、十、个）
38            getThree(num, sb);
39        }
40        return sb.toString();
41    }
42
43    public void getThree(int num, StringBuilder sb) {
44        if (num / 100 > 0) {
45            // 取百位
46            if (sb.length() > 0) {
47                sb.append(" ");
48            }
49            sb.append(one[num / 100]);
50            sb.append(" Hundred");
51            num = num % 100;
52        }
53        if (num == 0) {
54            return;
55        }
56        // 取十位
57        if (num < 20) {
58            // 可直接取值的情况：10，11，12，13...19
59            if (sb.length() > 0) {
60                sb.append(" ");
61            }
62            sb.append(one[num]);
63        } else {
64            // [20, 99] 的情况，需要十位 + 个位分别转换字符串
65            if (sb.length() > 0) {
66                sb.append(" ");
67            }
68            // 十位转换
69            sb.append(ten[num / 10]);
70            num = num % 10;
71            if (num > 0) {
72                if (sb.length() > 0) {
73                    sb.append(" ");
74                }
75                // 个位转换
76                sb.append(one[num]);
77            }
78        }
79    }
80}

15、比较版本号（中等）

自己的想法

方法一：双指针

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

 1class Solution {
 2
 3    public int compareVersion(String version1, String version2) {
 4        int index1 = 0, index2 = 0;
 5        while (index1 < version1.length() || index2 < version2.length()) {
 6            // 记录 v1 下标从 index1 到小数点的数值
 7            int number1 = 0;
 8            for (int i = index1; i <= version1.length(); i++) {
 9                if (i == version1.length() || version1.charAt(i) == '.') {
10                    // 更新下次的起始下标
11                    index1 = i + 1;
12                    break;
13                }
14                number1 = number1 * 10 + version1.charAt(i) - '0';
15            }
16            // 记录 v2 下标从 index2 到小数点的数值
17            int number2 = 0;
18            for (int i = index2; i <= version2.length(); i++) {
19                if (i == version2.length() || version2.charAt(i) == '.') {
20                    index2 = i + 1;
21                    break;
22                }
23                number2 = number2 * 10 + version2.charAt(i) - '0';
24            }
25            if (number1 > number2) {
26                return 1;
27            } else if (number1 < number2) {
28                return -1;
29            }
30        }
31        return 0;
32    }
33}

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%的用户

 1class Solution {
 2  
 3    public int magicalString(int n) {
 4        // index 表示字符串 A 的索引，根据该索引的字符生成指定个数的字符，
 5        int index = 1;
 6        StringBuilder s = new StringBuilder();
 7        // 第一个字符为 1
 8        s.append(1);
 9        while (s.length() < n) {
10            // 因为需要根据字符串 A，来确定在字符串 S 生成字符的个数
11            // 所以当字符串 A 越界时，则根据前一个字符进行生成
12            if (index == s.length()) {
13                // 如果前一个字符为 1，则生成 22。
14                s.append(s.charAt(s.length() - 1) == '1' ? 22 : 1);
15                index++;
16            } else {
17                // 如果字符串 A 没有越界，则字符串 A 决定生成字符的个数。
18                // 而字符串 S 的最后一个字符决定生成的字符是 1 还是 2
19                if (s.charAt(s.length() - 1) == '1') {
20                    s.append(s.charAt(index++) == '1' ? 2 : 22);
21                } else {
22                    s.append(s.charAt(index++) == '1' ? 1 : 11);
23                }
24            }
25        }
26        // count 统计 1 的个数
27        int count = 0;
28        // 遍历字符串统计 1 的个数
29        for (int i = 0; i < n; i++) {
30            if (s.charAt(i) == '1') {
31                count++;
32            }
33        }
34        return count;
35    }
36}

看题解后

方法二：使用 int[]

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

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

 1class Solution {
 2
 3    public int magicalString(int n) {
 4        if (n == 0) {
 5            return 0;
 6        }
 7        if (n <= 3) {
 8            return 1;
 9        }
10        int[] array = new int[n];
11        // 设置初值
12        array[0] = 1;array[1] = 2;array[2] = 2;
13        // 统计 1 的个数，前三个字符中有 1 个 1
14        int count = 1;
15        // index 表示字符串 A 的索引，length 表示字符串有效字符的个数， value 表示下次生成的字符
16        int index = 2, length = 3, value = 1;
17        while (length < n) {
18            // 根据 array[index] 的值决定生成几个 value
19            for (int i = 0; i < array[index] && length < n; i++) {
20                array[length++] = value;
21                // 统计 1 的个数
22                if (value == 1) {
23                    count++;
24                }
25            }
26            // 更换生成的字符，3-1=2，3-2=1，实现 1 和 2 的交替
27            value = 3 - value;
28            index++;
29        }
30        return count;
31    }
32}