[toc]
第一题：找规律题
738. 单调递增的数字 - 力扣（LeetCode）
就是找规律
从左往右，确认前后是否满足x<=y，是就继续往下遍历
当发现不满足时， 要么是2466111这种有2个6，要么是2456111这种有1个6
前者要变成2459999， 后者变成2455999
可以看到就是找到6的最左边，把他变成6-1之后， 后面的全是9即可。
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
| class Solution {
public int monotoneIncreasingDigits(int n) {
String s = String.valueOf(n);
boolean is9 = false;
int max = 0;
char[] cs = new char[s.length()];
for (int i = 0; i < s.length();i++) {
if (is9) {
cs[i] = '9';
continue;
}
int num = s.charAt(i) - '0';
if (i+1 < s.length() && num > s.charAt(i+1) - '0') {
int j = i;
while(j>=0&&num == s.charAt(j) - '0') {
j--;
}
j++;
i = j;
cs[i] = (char)(s.charAt(i) - 1);
is9 = true;
} else {
cs[i] = (char)(num + '0');
max = Math.max(num, max);
}
}
return Integer.valueOf(new String(cs));
}
}
|
第二题：找重复数字就要记得利用位运算异或
645. 错误的集合 - 力扣（LeetCode）
有时间O(nlogn)的排序解法（排序的时候求丢失的数字也很麻烦）
也有空间O（n)的哈希表解法
最佳应该是时间O(N)空间O(1)，即利用位运算特点
将当前数组和1~n数组合并成1个新数组
那么丢失的数字a只有1个， 重复的数字b则有3个， 其他的都是2个
通过异或得到a^b的值
那么就是经典的分组方法， 先找到a^b中不相同的某一位， 然后进行划分分组， 基于划分后的分组再做异或，就能得到2个值了。
再遍历一次就能知道谁丢了谁重复
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
| class Solution {
public int[] findErrorNums(int[] nums) {
int xorSum = 0;
for (int i = 0; i < nums.length;i++) {
xorSum ^= (i+1);
xorSum ^= nums[i];
}
int diffBit = xorSum & (-xorSum);
int sum0 = 0, sum1 = 0;
for (int i = 0; i < nums.length;i++) {
if ((nums[i] & diffBit) > 0) {
sum1 ^= nums[i];
} else {
sum0 ^= nums[i];
}
if (((i+1) & diffBit) > 0) {
sum1 ^= (i+1) ;
} else {
sum0 ^= (i+1) ;
}
}
for (int num : nums) {
if (num == sum1) {
return new int[]{sum1, sum0};
} else if (num == sum0){
return new int[]{sum0, sum1};
}
}
return new int[]{};
}
}
|
第三题：双指针处理退格问题
844. 比较含退格的字符串 - 力扣（LeetCode）
最佳解法肯定是双指针， 空间O1， 不要用栈， 从右往左遍历即可
但是边界条件处理比较恶心，记得在while循环里判断，别放到外面搞，比较麻烦。
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
| class Solution {
public boolean backspaceCompare(String s, String t) {
int si = s.length()-1, ti = t.length()-1;
int spopCount = 0, tpopCount = 0;
while(true) {
while(si >=0 && (s.charAt(si) == '#' || spopCount > 0)) {
if (s.charAt(si) == '#') {
spopCount++;
} else {
spopCount--;
}
si--;
}
while(ti >=0 && (tpopCount >0 || t.charAt(ti) == '#')) {
if (t.charAt(ti) == '#') {
tpopCount++;
} else {
tpopCount--;
}
ti--;
}
if (si ==-1 && ti == -1) {
return true;
} else if (si == -1 || ti == -1) {
return false;
}
if (si >=0 && ti >= 0 && s.charAt(si) != t.charAt(ti)) {
return false;
}
si--;
ti--;
}
}
}
|