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
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!