- 刷题日记 - 3
- 13. 罗马数字转整数 - 力扣（LeetCode）
- 12. 整数转罗马数字 - 力扣（LeetCode）
- 58. 最后一个单词的长度 - 力扣（LeetCode）
- 14. 最长公共前缀 - 力扣（LeetCode）
- 151. 反转字符串中的单词 - 力扣（LeetCode）
- LCP 40. 心算挑战 - 力扣（LeetCode）
- 6. Z 字形变换 - 力扣（LeetCode）
刷题日记 - 3
记录刷题。
难度：简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public int romanToInt(String s) {
int len = s.length();
char[] charArray = s.toCharArray();
HashMap<Character, Integer> map = new HashMap<>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int res = 0;
char last = 'I';
for (int i = len - 1; i >= 0; i--) {
char cur = charArray[i];
if (map.get(cur) < map.get(last)) {
res -= map.get(cur);
} else {
res += map.get(cur);
last = cur;
}
}
return res;
}
}
|
根据罗马数字的规律来即可。
正常情况下是小的字符在右边，但是类似于IV = 5 - 1这种特例，增加变量last记录一下上一个字符，如果当前字符小于上一个字符，表明这就是特殊情况。
难度：中等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public String intToRoman(int num) {
StringBuilder res = new StringBuilder();
int[] vals = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
for (int i = 0; i < vals.length; i++) {
while (num >= vals[i]) {
num -= vals[i];
res.append(symbols[i]);
}
}
return res.toString();
}
}
|
每次都减去可能的最大值。
难度：简单
从前往后：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public int lengthOfLastWord(String s) {
char[] charArray = s.toCharArray();
int res = 0;
int tmp = 0;
int p = 0;
int len = s.length();
while (p < len) {
if (charArray[p] != ' ') {
tmp++;
p++;
} else if (charArray[p] == ' ') {
res = tmp;
tmp = 0;
p++;
while (p < len && charArray[p] == ' ') {
p++;
}
}
if (p == len && tmp != 0) {
res = tmp;
}
}
return res;
}
}
|
从后往前：
这个方法其实更合理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int lengthOfLastWord(String s) {
char[] charArray = s.toCharArray();
int len = charArray.length;
int res = 0;
for(int i=len-1;i>=0;i--){
char cur = charArray[i];
if(cur==' '&&res==0) continue;
if(cur!=' ') res++;
if(cur==' ') break;
}
return res;
}
}
|
从最后一个字符开始向前遍历，如果遇到' '并且res=0就跳过，表示这是结尾多余的空字符。
但是如果遇到了' '并且res>0，表明最后一个单词的长度已经被遍历过去了。
难度：简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public String longestCommonPrefix(String[] strs) {
StringBuilder sb = new StringBuilder("");
int idx = 0;
boolean flag = true;
char hold = ' ';
while (flag) {
for (String str : strs) {
if (idx >= str.length()) {
flag = false;
break;
}
char cur = str.charAt(idx);
if (hold == ' ') {
hold = cur;
} else if (hold != cur) {
flag = false;
break;
}
}
idx++;
if (flag) sb.append(hold);
hold = ' ';
}
return sb.toString();
}
}
|
用指针idx去同步指向每一个str的某个字符的位置，注意break的时机。
难度：中等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public String reverseWords(String s) {
LinkedList<String> stack = new LinkedList<>();
char[] charArray = s.toCharArray();
int len = charArray.length;
StringBuilder sb = new StringBuilder();
int p = 0;
while (p < len) {
while (p < len && charArray[p] == ' ') {
p++;
}
if (p == len) break;
while (p < len && charArray[p] != ' ') {
sb.append(charArray[p]);
p++;
}
stack.push(sb.toString());
sb.setLength(0);
}
StringBuilder res = new StringBuilder();
while (stack.size() > 1) {
res.append(stack.pop());
res.append(' ');
}
if (!stack.isEmpty()) {
res.append(stack.pop());
}
return res.toString();
}
}
|
将String转换为字符串数组，这样更快。
然后再一个一个将单词提取出来，由于需要反转，所以用到了栈。
StringBuilder的清空方法是 StringBuilder.setLength(0)
难度：简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| class Solution {
public int maxmiumScore(int[] cards, int cnt) {
int[] bucket = new int[1001];
for(int card: cards){
bucket[card]++;
}
int oddMin = -1;
int evenMin = -1;
int p = 1000;
int res = 0;
while(cnt > 0){
p = findNextNum(bucket, p);
res += p;
bucket[p]--;
cnt--;
if(p % 2 == 1) oddMin = p;
if(p % 2 == 0) evenMin = p;
}
if(res % 2 == 0) return res;
int nextOdd = (evenMin == -1) ? -1 : findNextOddNum(bucket, p);
int nextEven = (oddMin == -1) ? -1 : findNextEvenNum(bucket, p);
if(nextOdd == -1 && nextEven == -1) return 0;
if(nextOdd == -1 && nextEven != -1) return res - oddMin + nextEven;
if(nextOdd != -1 && nextEven == -1) return res - evenMin + nextOdd;
return Math.max(res - oddMin + nextEven, res - evenMin + nextOdd);
}
private int findNextNum(int[] bucket, int p){
while(p >= 0 && bucket[p] == 0){
p--;
}
if(p != -1){
return p;
}
return -1;
}
private int findNextOddNum(int[] bucket, int p){
while((p >= 0 && bucket[p] == 0) || (p % 2 == 0)){
p--;
}
if(p != -1){
return p;
}
return -1;
}
private int findNextEvenNum(int[] bucket, int p){
while((p >= 0 && bucket[p] == 0) || (p % 2 == 1)){
p--;
}
if(p != -1){
return p;
}
return -1;
}
}
|
这个题难度其实挺大的。
首先要想好思路：想要最终的结果最大，直接排序，从后往前累加即可。
但是题目要求最终累加结果是偶数才能算有效，所以累加结束之后需要判res是否为偶数，如果是偶数则直接返回。
如果是奇数，那么可以通过以下两种方法将res改为偶数：
- 删除已选中的数中最小的奇数，选择下一个偶数 （如果已经选中的数中没有奇数，这不可能….因为
res是奇数；如果下面没有偶数了，那这种方法行不通）
- 删除已选中的数中最小的偶数，选择下一个奇数（如果已经选中的数中没有偶数，这种方法行不通）
如果两个方法都能凑效，res取最大的那一个。
如果两个方法都不奏效…..那没办法了，找不到cnt个数的和为偶数的情况。
由于card[i]的值范围为0-1000，所以我直接用计数排序了，排序的时间复杂度为O(n)
难度：中等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
public String convert(String s, int numRows) {
int len = s.length();
if (len <= numRows || numRows == 1) return s;
char[] charArray = s.toCharArray();
StringBuilder sb = new StringBuilder();
int interval = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
if (i == 0) {
int p = 0;
while (p < len) {
sb.append(charArray[p]);
p += interval;
}
}
else if (i == numRows - 1) {
int p = numRows - 1;
while (p < len) {
sb.append(charArray[p]);
p += interval;
}
}
else {
int p1 = i;
int p2 = 2 * numRows - 2 - i;
while (p1 < len && p2 < len) {
sb.append(charArray[p1]);
sb.append(charArray[p2]);
p1 += interval;
p2 += interval;
}
if (p1 < len) {
sb.append(charArray[p1]);
}
}
}
return sb.toString();
}
}
|
这个中等题难度甚至不如上一题心算挑战。
此题只需要找到数学规律即可。
1
2
3
4
5
6
7
| 0
1 2n-3
. .
. .
. n+2
n-2 n
n-1
|
第一行和最后一行只有一个值，中间行有两个值。
