标题中提到的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 26 |
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 35 |
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 23 |
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 16 17 |
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; } } |