每日5题Day4 - LeetCode 16 - 20

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：16. 最接近的三数之和 - 力扣（LeetCode）

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        //别用dp了，使用双指针省空间一些，
        Arrays.sort(nums);
        //用变量代替数组长度
        int n = nums.length;
        //我们找到的和可能大于或者小于target，
        //最终返回结果是一个差值，初始化一个最大值吧
        int best = Integer.MAX_VALUE;
        //注意范围是n - 2，因为三个数之和
        for(int i = 0; i < n - 2; i++){
            //去重
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            //规定左右边界
            int j = i + 1, k = n - 1;
            //判断了
            while(j < k){
                int cursum = nums[i] + nums[j] + nums[k];
                if(cursum == target){
                    //题目说只有一组满足要求，如果发现最后解可以直接返回了
                    return target;
                }
                if(Math.abs(cursum - target) < Math.abs(best - target)){
                    best = cursum;
                }
                else if(cursum > target){
                    k--;
                }
                else{
                    j++;
                }
            }
        }
        return best;
    }
}

第二题：17. 电话号码的字母组合 - 力扣（LeetCode）

class Solution {
    public List<String> letterCombinations(String digits) {
        //考虑特殊情况
        if(digits.equals("")){
            return new ArrayList<>();
        }
        //读题可以发现这个其实相当于一个dfs的题目，回溯一下
        char[] words = digits.toCharArray();
        //返回最后的结果
        List<String> res = new ArrayList<>();
        //存储的过程
        Deque<Character> path = new ArrayDeque<>();
        //因为存在映射
        Map<Character, List<Character>> map = new HashMap<>();
        map.put('2', Arrays.asList('a', 'b', 'c'));
        map.put('3', Arrays.asList('d', 'e', 'f'));
        map.put('4', Arrays.asList('g', 'h', 'i'));
        map.put('5', Arrays.asList('j', 'k', 'l'));
        map.put('6', Arrays.asList('m', 'n', 'o'));
        map.put('7', Arrays.asList('p', 'q', 'r', 's'));
        map.put('8', Arrays.asList('t', 'u', 'v'));
        map.put('9', Arrays.asList('w', 'x', 'y', 'z'));
        traversal(0, words, res, path, map);
        return res;
    }
 
    private static void traversal(int cur_idx, char[] words, List<String> res, Deque<Character> path, Map<Character, List<Character>> map){
        //所有数字都遍历了，可以添加结果了
        if(cur_idx == words.length){
            StringBuilder sb = new StringBuilder();
            for(char ch : path){
                sb.append(ch);
            }
            res.add(sb.toString());
            return;
        }
        //每次添加字母进去的过程
        for(char ch : map.get(words[cur_idx])){
            path.offerLast(ch);
            traversal(cur_idx + 1, words, res, path, map);
            path.pollLast();
        }
    }
}

第三题：18. 四数之和 - 力扣（LeetCode）

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);  
        for (int i = 0; i < nums.length - 3; i++) {
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }
            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

第四题：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //搞一个头节点
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        //找到要删除的点
        while(n > 0){
            cur = cur.next;
            n--;
        }
        ListNode pre = dummy;
        //从头找到要删除点的前一个点
        while(cur.next != null){
            pre = pre.next;
            cur = cur.next;
        }
        //跳过要删除的点直接连接
        pre.next = pre.next.next;
        return dummy.next;
    }
}

 第五题：20. 有效的括号 - 力扣（LeetCode）

class Solution {
    public boolean isValid(String s) {
        //用hashmap来存一下相匹配的括号
        Map<Character, Character> map = new HashMap<>();
        map.put('}', '{');
        map.put(')', '(');
        map.put(']', '[');
        Deque<Character> deque = new ArrayDeque<>();
        //遍历放入，是左括号就放入栈，右括号就弹出看是否匹配
        for(char ch : s.toCharArray()){
            if(!map.containsKey(ch)){
                deque.offerLast(ch);
            }
            else{
                if(map.get(ch) == deque.peekLast()){
                    deque.pollLast();
                }else{
                    return false;
                }
            }
 
        }
        //记得判断栈是否为空，不然就还有左括号，消除不完
        return deque.size() == 0;
    }
}