标题中提到的4道题目都较为简单，合并到一起写解题记录。
66 Plus One
概述
Plus One 即给定以数组形式表示各位的数字，将这一数字加1的结果输出为数组即可。
分析
这一题主要处理的是常规的运算的进位问题，同时，由于数组并没有确定数字为int，那么位数不定，需要按照正常的竖式运算的步骤进行。
当计算发现最高位需要进位时，申请更大的空间，返回结果。
解法
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
| public class Solution {
public int[] plusOne(int[] digits) {
int[] r = new int[digits.length];
int now = 1;
for (int i = digits.length - 1; i >= 0; --i) {
r[i] = (now + digits[i]) % 10;
now = (now + digits[i]) / 10;
}
if (now > 0) {
int[] result = new int[digits.length + 1];
for (int i = digits.length; i >= 1; --i) {
result[i] = r[i - 1];
}
result[0] = now;
return result;
}
return r;
}
}
|
67 Add Binary
概述
Add Binary 与 66 Plus One 很相似，只不过由十进制数变为了二进制数的加法。
输入是字符串，输出也是字符串。
分析
二进制加法，仍然按照竖式计算的方式进行即可。无需多说。
解法
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
| public class Solution {
public String addBinary(String a, String b) {
int now = 0;
String result = "";
int ai = a.length() - 1;
int bi = b.length() - 1;
for (; ai >= 0 || bi >= 0; --ai, --bi) {
int val = 0;
if (ai >= 0 && bi >= 0) {
char ac = a.charAt(ai);
char bc = b.charAt(bi);
val = now + (ac - '0') + (bc - '0');
} else if (ai >= 0) {
char ac = a.charAt(ai);
val = now + (ac - '0');
} else {
char bc = b.charAt(bi);
val = now + (bc - '0');
}
result = val % 2 + result;
now = val / 2;
}
if (now > 0) {
result = 1 + result;
}
return result;
}
}
|
83 Remove Duplicates from Sorted List
概述
Remove Duplicates from Sorted List 即在已排序的单向链表中完成去重。
分析
链表已排序，去重工作变得相当容易，只需要判断当前节点的值是否等于上一节点的值，如果等于则将链表当前的下一指针指向下下一个节点，周而复始。
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (null == head) {
return null;
}
ListNode r = head;
int now = 0;
while (r.next != null) {
now = r.val;
if (now == r.next.val) {
r.next = r.next.next;
} else {
r = r.next;
}
}
return head;
}
}
|
217 Contains Duplicate
概述
Contains Duplicate 判断数组中是否有重复的值。
分析
使用Hash完成这一判断最为容易，判断一个值是否在 HashMap 中存在即可。
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
public boolean containsDuplicate(int[] nums) {
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int n : nums) {
if (m.containsKey(n)) {
return true;
}
m.put(n, 1);
}
return false;
}
}
|