leetcode_hot100

1. 两数之和

方法一：HashMap

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(target - nums[i]))
                return new int[]{map.get(target - nums[i]), i};
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

2. 两数相加

方法一：链表

/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int val = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carry;
            carry = val >= 10 ? 1 : 0;
            cur.next = new ListNode(carry == 0 ? val : val % 10);
            cur = cur.next;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        if (carry == 1)
            cur.next = new ListNode(1);
        return dummy.next;
    }
}

3. 无重复字符的最长子串

方法一：滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0, n = s.length();
        Map<Character, Integer> map = new HashMap<>();
        for (int left = 0, right = 0; right < n; ++right) {
            char ch = s.charAt(right);
            while (map.containsKey(ch)) {
                left = Math.max(left, map.get(ch) + 1);
                map.remove(ch);
            }
            map.put(ch, right);
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

4. 寻找两个正序数组的中位数

方法一：划分区间

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length)
            return findMedianSortedArrays(nums2, nums1);
        int m = nums1.length, n = nums2.length;
        int median1 = 0, median2 = 0; // 如果有m + n是偶数，median2是第二个中位数
        int left = 0, right = m; // i == m时，表示nums1全被划分为前一部分
        while (left <= right) {
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            // 当m + n是偶数，规定前一部分和后一部分的长度相同
            // 当m + n是奇数，规定前一部分的长度 == 后一部分的长度 + 1
            // j = (m + n + 1 ) / 2 - i 可以很好地满足，不管m+n是奇数还是偶数
            int i = (left + right) / 2, j = (m + n + 1) / 2 - i;
            int nums_i = i == m ? Integer.MAX_VALUE : nums1[i];
            int nums_im1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int nums_j = j == n ? Integer.MAX_VALUE : nums2[j];
            int nums_jm1 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            if (nums_im1 <= nums_j) {
                median1 = Math.max(nums_im1, nums_jm1);
                median2 = Math.min(nums_i, nums_j);
                left = i + 1;
            }
            else {
                right = i - 1;
            }
        }
        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
}

5. 最长回文子串

方法一：DP

注意遍历顺序

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length(), max = 0;
        int[] maxIndex = new int[2];
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            char ch1 = s.charAt(i);
            for (int j = i; j < n; ++j) {
                char ch2 = s.charAt(j);
                if (j - i + 1 <= 2)
                    dp[i][j] = ch1 == ch2 ? j - i + 1 : 0;
                else
                    dp[i][j] = (ch1 == ch2 && dp[i + 1][j - 1] > 0) ? 2 + dp[i + 1][j - 1] : 0;
                if (dp[i][j] > max) {
                    max = dp[i][j];
                    maxIndex[0] = i;
                    maxIndex[1] = j;
                }
            }
        }
        return s.substring(maxIndex[0], maxIndex[1] + 1);
    }
}

10. 正则表达式匹配

方法一：DP

题解

初始化非常重要！！！！

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        // dp[i][j]:s[0:i]与p[0:j]是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true; // 空串与空串匹配
        for (int j = 1; j <= n; ++j)
            if (p.charAt(j - 1) == '*')
                dp[0][j] = dp[0][j - 2];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                else if (p.charAt(j - 1) == '*') {
                    if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    else 
                        dp[i][j] = dp[i][j - 2];
                }
            }
        }
        return dp[m][n];
    }
}

11. 盛最多水的容器

方法一：双指针贪心

移动短板，可以证明不会漏掉最大的结果

class Solution {
    public int maxArea(int[] height) {
        int n = height.length, max = 0;
        int left = 0, right = n - 1;
        while (left < right) {
            int length = right - left;
            max = height[left] < height[right] ? Math.max(max, length * height[left++]) : Math.max(max, length * height[right--]);
        }
        return max;
    }
}

方法二：回溯(超时)

class Solution {
    public int maxArea(int[] height) {
        n = height.length;
        this.height = height;
        dfs(0, n - 1);
        return res;
    }

    private void dfs(int left, int right) {
        if (left == right) {
            return;
        }
        res = Math.max(res, (right - left) * Math.min(height[right], height[left]));
        dfs(left + 1, right);
        dfs(left, right - 1);
    }

    int n, res = 0;
    int[] height;

}

15. 三数之和

二刷没做出来

方法一：排序 + 双指针

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; ++i) {
            if (nums[i] > 0)
                break;
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left + 1] == nums[left])
                        ++left;
                    while (left < right && nums[right - 1] == nums[right])
                        --right;
                    ++left;
                    --right;
                }
                else if (nums[i] + nums[left] + nums[right] < 0) 
                    ++left;
                else 
                    --right;
            } 
        }
        return res;
    }
}

17. 电话号码的字母组合

方法一：回溯

class Solution {
    public List<String> letterCombinations(String digits) {
        dfs(digits, 0);
        return res;
    }

    private void dfs(String digits, int index) {
        if (index == digits.length()) {
            if (sb.length() > 0)
                res.add(new String(sb));
            return;
        }
        int curDigit = digits.charAt(index) - '0'; // 2
        String curStr = map[curDigit];
        for (int i = 0; i < curStr.length(); ++i) {
            sb.append(curStr.charAt(i));
            dfs(digits, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
}   

19. 删除链表的倒数第 N 个结点

方法一：模拟

/**
 * 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 dummyHead = new ListNode(-1, head), cur = head, pre = dummyHead;
        for (int i = 0; i < n; ++i)
            cur = cur.next;
        while (cur != null) {
            cur = cur.next;
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return dummyHead.next;
    }
}

20. 有效的括号

方法一：栈 + HashMap 模拟

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{')
                stack.push(ch);
            else {
                if (stack.isEmpty())
                    return false;
                if (map.get(ch) != stack.pop())
                    return false;
            }
        }
        return stack.isEmpty();
    }
}

21. 合并两个有序链表

方法二：递归

题解

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }
        else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

方法三：迭代

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null)
            return l1 == null ? l2 : l1;
        ListNode dummyHead = new ListNode(), cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }
            else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummyHead.next;
    }
}

方法一：模拟

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        ListNode dummyHead = new ListNode(-1), cur = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = new ListNode(list1.val);
                list1 = list1.next;
            }
            else {
                cur.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 == null)
            cur.next = list2;
        if (list2 == null)
            cur.next = list1;
        return dummyHead.next;
    }
}

22. 括号生成

方法一：回溯

class Solution {
    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(0, 0);
        return res;
    }

    private void dfs(int left, int right) {
        if (left + right == 2 * n) {
            res.add(new String(sb));
            return;
        }
        if (left < n) {
            sb.append('(');
            dfs(left + 1, right);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (left > right) {
            sb.append(')');
            dfs(left, right + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    int n;
}

23. 合并 K 个升序链表

方法一：暴力

1. 把所有ListNode的值加入小根堆
2. 不断弹出小根堆，并创建新节点

/**
 * 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 mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (ListNode node : lists) {
            ListNode cur = node;
            while (cur != null) {
                queue.add(cur.val);
                cur = cur.next;
            }
        }
        ListNode dummyHead = new ListNode(-1), cur = dummyHead;
        while (!queue.isEmpty()) {
            cur.next = new ListNode(queue.poll());
            cur = cur.next;
        }
        return dummyHead.next;
    }
}

方法二：迭代

注意：debug很久，类比一道题：给出一个链表的头节点head，初始cur指向head，然后遍历cur，让cur = cur.next，head的位置没有变

 // minNode = minNode.next; 没有修改头节点的指针
lists[minIndex] = lists[minIndex].next; // 添加这行代码以更新指针

代码

/**
 * 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 mergeKLists(ListNode[] lists) {
        ListNode dummyHead = new ListNode(-1), cur = dummyHead;
        int k = lists.length;
        while (true) {
            int minIndex = -1, minVal = 10001;
            ListNode minNode = null;
            for (int i = 0; i < k; ++i) {
                if (lists[i] == null)
                    continue;
                if (minVal > lists[i].val) {
                    minVal = lists[i].val;
                    minIndex = i;
                    minNode = lists[i];
                }
            }
            if (minIndex == -1)
                break;
            cur.next = minNode;
            cur = cur.next;
            // minNode = minNode.next; 没有修改头节点的指针
            lists[minIndex] = lists[minIndex].next; // 添加这行代码以更新指针
        }
        return dummyHead.next;
    }
}

方法三：小根堆优化方法二

不能按照以下方式初始化queue的大小，会报错

PriorityQueue<ListNode> queue = new PriorityQueue<>(k, (v1, v2) -> v1.val - v2.val);

代码

/**
 * 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 mergeKLists(ListNode[] lists) {
        ListNode dummyHead = new ListNode(-1), cur = dummyHead;
        int k = lists.length;
        PriorityQueue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for (ListNode x : lists)
            if (x != null)
                queue.add(x);
        while (!queue.isEmpty()) {
            ListNode minNode = queue.poll();
            cur.next = minNode;
            cur = cur.next;
            minNode = minNode.next;
            if (minNode != null)
                queue.add(minNode);
        }
        return dummyHead.next;
    }
}

方法四：分治

/**
 * 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 mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r)
            return lists[l];
        else if (l > r)
            return null;
        int mid = (l + r) >> 1;
        ListNode l1 = merge(lists, l, mid);
        ListNode l2 = merge(lists, mid + 1, r);
        return mergeTwoList(l1, l2);        
    }

    public ListNode mergeTwoList(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) 
            return l1 == null ? l2 : l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoList(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoList(l1, l2.next);
            return l2;
        }
    }
}

31. 下一个排列

方法一：双指针模拟

题解

class Solution {
    public void nextPermutation(int[] nums) {
        // 1. 从后往前，找到第一个升序序列，nums[i] < nums[j] (i < j)
        int n = nums.length, i = n - 2, j = n - 1, k = n - 1; 
        if (n == 1)
            return;
        while (i >= 0 && nums[i] >= nums[j]) {
            --i;
            --j;
        }
        // 如果i == -1，则此时nums是最大的逆序对，跳转到第3步(全部翻转)
        // 2.从后往前，找到第一个大于nums[i]的数nums[k]，并swap (nums[k]是最小的大于nums[i]的数)
        if (i >= 0) {
            while (nums[k] <= nums[i])
                --k;
            int temp = nums[i];
            nums[i] = nums[k];
            nums[k] = temp;
        }
        // 3.将j到末尾的子数组翻转
        k = n - 1;
        while (j < k) {
            int temp = nums[j];
            nums[j] = nums[k];
            nums[k] = temp;
            ++j;
            --k;
        }
    }
}

32. 最长有效括号

方法一：DP

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length(), max = 0;
        // dp[i]: 以s.charAt(i)结尾的子串的最长有效括号长度
        int[] dp = new int[n];
        // 1.找到第一个左括号，前面的右括号是无效的
        int start = 0;
        while (start < n) {
            if (s.charAt(start) == '(')
                break;
            ++start;
        }
        for (int i = start + 1; i < n; ++i) {
            char pre = s.charAt(i - 1), ch = s.charAt(i);
            // 2.只考虑右括号
            if (ch == ')') {
                // 如果前一个括号是左括号，那么以ch结尾的子串至少长为2，如果前面也有有小括号，把长度累加
                if (pre == '(')
                    dp[i] = 2 + (i - 2 > start ? dp[i - 2] : 0);
                // 前一个括号是右括号
                else {
                    // 3.考虑 "((()))"
                    // 如果前一个右括号形成了有效括号，并且这个有效括号的前一个字符是'('，那么以ch结尾的子串至少
                    // 长为2 + dp[i - 1]
                    //4.考虑 "()(())"，计算出"(())"后，再往前面找一位，如果有有效括号，继续累加
                    //  在3.的基础上，在
                    if (dp[i - 1] > 0 && i - dp[i - 1] > start && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = 2 + dp[i - 1] + (i - dp[i - 1] - 2 > start ? dp[i - dp[i - 1] - 2] : 0);
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}