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