给自己的目标：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一题

在做题的过程中记录下解题的思路或者重要的代码碎片以便后来翻阅。
项目源码：github上的Leetcode

16. 3SumClosest

题目：输入一行数字和一个目标数字，求出三个数相加最接近目标的值。

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路与 3sum 一样，都是先排序再前后取值，只不过目标值从0变为要输入的值。

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int distance = Integer.MAX_VALUE;
        int min = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || i > 0 && nums[i] != nums[i - 1]) {
                int start = i + 1, end = nums.length - 1, t = target - nums[i];
                while (start < end) {
                    int value = nums[start] + nums[end];
                    if (value == t) {
                        return target;
                    } else if (value > t) {
                        end--;
                        if (distance > value - t) {
                            distance = value - t;
                            min = nums[i] + value;
                        }
                    } else {
                        start++;
                        if (distance > t - value) {
                            distance = t - value;
                            min = nums[i] + value;
                        }
                    }
                }
            }
        }
        return min;
    }
}

17. Letter Combinations of a Phone Number

题目：求老式手机上按下数字键后所有的字符组合，按下0和1会导致数组为空。

手机键盘

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

利用char的数字特性来找到键盘的规律，之后便是不断循环添加字符。

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        List<String> temp = new ArrayList<>();
        for (int i = 0; i < digits.length(); i++) {
            temp.clear();
            temp.addAll(result);
            result.clear();
            char c = digits.charAt(i);
            if (c <= '1' || c > '9') {
                return result;
            } else {
                char start;
                if (c <= '7') {
                    start = (char) ((c - '2') * 3 + 'a');
                } else {
                    start = (char) ((c - '2') * 3 + 1 + 'a');
                }
                int size = (c == '7' || c == '9') ? 4 : 3;
                if (temp.size() == 0) {
                    for (char k = start; k <start + size; k++) {
                        result.add(String.valueOf(k));
                    }
                } else {
                    for (String aTemp : temp) {
                        for (char k = start; k < start + size; k++) {
                            result.add(aTemp + String.valueOf(k));
                        }
                    }
                }
            }

        }
        return result;
    }
}

18. 4Sum

题目：给出一行数字和一个目标值，求出其中4个数相加等于目标值的所有组合。不能有重复。

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

思路同 3sum 一样，不过要在 3sum 上再套上一层循环。

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            if (i == 0 || i > 0 && nums[i] != nums[i - 1]) {
                int t = target - nums[i];
                threeSum(nums, t, result, i + 1);
            }
        }
        return result;
    }
    
    public void threeSum(int[] nums, int target, List<List<Integer>> result, int k) {
        for (int i = k; i < nums.length - 2; i++) {
            if (i == k || (i > k && nums[i] != nums[i - 1])) {
                int start = i + 1, end = nums.length - 1, t = target - nums[i];
                while (start < end) {
                    if (nums[start] + nums[end] == t) {
                        result.add(Arrays.asList(nums[k-1], nums[start], nums[end], nums[i]));
                        while (start < end && nums[end] == nums[end - 1]) end--;
                        while (start < end && nums[start + 1] == nums[start]) start++;
                        end--;
                        start++;
                    } else if (nums[start] + nums[end] < t) {
                        start++;
                    } else {
                        end--;
                    }
                }
            }
        }
    }
}

19. Remove Nth Node From End of List

题目：输入一串节点和一个数字n,n表示从尾部开始数起的第n个节点，这个节点将会从节点列表汇中删除。

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

首先从头到尾遍历一遍获取节点列表的长度，之后便是再从头部开始找到要删除的节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return head;
        int len = 0;
        ListNode dummy = new ListNode(-1), pt = dummy;
        dummy.next = head;
        
        while (pt.next != null) {
            pt = pt.next;
            len++;
        }
        pt = dummy;
        for (int cnt = len - n; cnt > 0; cnt--) pt = pt.next;
        if (pt.next != null) {
            pt.next = pt.next.next;
        }
        return dummy.next;
    }
}

20. Valid Parentheses

题目：有效的括号，输入一行只包含"(){}[]"的字符串，判断是否有效（即括号能否左右对应）

使用栈FILO的特性来匹配。

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> p = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                p.push(c);
            } else if (c == ')' || c == '}' || c == ']') {
                if (p.size() == 0) {
                    return false;
                }
                if (c == ')' && p.pop() != '(') {
                    return false;
                } else if (c == '}' && p.pop() != '{') {
                    return false;
                } else if (c == ']' && p.pop() != '[') {
                    return false;
                }
            }
        }
        if (p.size() != 0) return false;
        return true;
    }
}