Remove Duplicates from Sorted List，Merge Sorted Array，Number of 1 Bits，Remove Linked List Elements，Reverse Linked List均较为简单，简要记录。
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;
}
}
|
88 Merge Sorted Array
概述
Merge Sorted Array，为两个已排序数组进行合并操作。
分析
归并排序很常见，但是本题的限制在于，没有第三个数组用于结果。可用的空间在于第一个数组。
那么，常规的归并操作无法实现了。
但是，可以考虑将大于第二个数组内的数值全部搬移到数组二中，即交换其值。由于数组已排序，数组的最后一个值必然是当前数组中的最大值。通过比较各个值，可以得知其应处于的位置。
经过上述操作之后，第一个数组中的值必然是小于第二个数组中的值的。
经过如是操作后，再讲第二个数组中的已排序的两个数组中最大的数字们搬运到第一个数组中。
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i2 = n - 1; i2 >= 0; --i2) {
for (int i1 = 0; i1 < m; ++i1) {
if (nums1[i1] > nums2[i2]) {
int tmp = nums1[i1];
nums1[i1] = nums2[i2];
nums2[i2] = tmp;
}
}
}
for (int i = 0; i < n; ++i) {
nums1[m + i] = nums2[i];
}
}
}
|
191 Number of 1 Bits
概述
Number of 1 Bits，判断一个整形数字中转化为二进制串之后二进制数字中存在的1的个数。
分析
整形数字转化为二进制数后，无符号的情况下，最多为32位，可以看做2^a + 2^b + 2^c + 2^d的形式，那么，从最大值开始，也就是第32位开始，逐一尝试，可以得出组合，即1的个数。
但是Java中int数字带来的的问题在于，它无法表示无符号整形。
考虑到这样的问题，将其转化为long型进行操作。
然而在传入的参数n大于Integer.MAX_VALUE时，即溢出时，Java中会变为一个负数（再次参见 SO 上的问题 How does Java handle integer underflows and overflows and how would you check for it?），简单来说，可以通过传入参数加上4294967296L获得其无符号整数的值。
能正确表示这一数字，即可尝试判断1的个数了。
解法
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
| public class Solution {
public int hammingWeight(int n) {
long unsignedN = n;
if (unsignedN < 0) {
unsignedN += 4294967296L;
}
int num = 0;
int maxPos = 31;
while (unsignedN > 0) {
for (int pos = maxPos; pos >= 0; --pos) {
if (((long)1<<pos) <= unsignedN) {
++num;
unsignedN -= ((long)1<<pos);
maxPos = pos - 1;
break;
}
}
}
return num;
}
}
|
203 Remove Linked List Elements
概述
Remove Linked List Elements，删除链表中的所有给定的值。
分析
链表删除值，需要注意处理的的主要是头结点，当头结点是需要删除的值时，只需将头结点前移即可。
当不是头结点时，使用常规的链表操作即可。
解法
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 ListNode removeElements(ListNode head, int val) {
ListNode prev = null;
ListNode now = head;
while (now != null) {
if (now.val == val) {
if (prev == null) {
head = now.next;
now = head;
} else {
prev.next = now.next;
now = now.next;
}
continue;
}
prev = now;
now = now.next;
}
return head;
}
}
|
206 Reverse Linked List
概述
Reverse Linked List，反转单向链表。
分析
反转单向链表不一定要通过指针操作，将值列表反转之后重新为链表赋值也是可以的。
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class Solution {
public ListNode reverseList(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
ListNode h = head;
int idx = 0;
while (h != null) {
vals.add(idx, h.val);
h = h.next;
++idx;
}
h = head;
--idx;
while (h != null) {
h.val = vals.get(idx);
h = h.next;
--idx;
}
return head;
}
}
|