20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<>() {
            {
                put(‘)‘, ‘(‘);
                put(‘}‘, ‘{‘);
                put(‘]‘, ‘[‘);
            }
        };
        Deque<Character> stack = new LinkedList<>();

        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //ch为左括号，直接入栈
            if (!map.containsKey(ch)) {
                stack.push(ch);
            } else {
                //ch为右括号，检查ch与栈顶元素是否配对
                if (stack.isEmpty() || stack.pop() != map.get(ch)) {
                    return false;
                }
            }
        }

        //遍历完所有括号后，stack为空则说明有效
        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 l1, ListNode l2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode temp = dummyNode;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                temp.next = l1;
                l1 = l1.next;
            } else {
                temp.next = l2;
                l2 = l2.next;
            }

            temp = temp.next;
        }

        if (l1 != null) temp.next = l1;
        if (l2 != null) temp.next = l2;

        return dummyNode.next;
    }
}

递归版：编写递归程序时一定不要用自己脑袋去模拟递归栈，而是要根据已知函数定义来写代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //base case
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

递归不理解的推荐题解：画解算法：21. 合并两个有序链表

22. 括号生成

思路：对于只有一种括号的情况，要生成合法括号字符串只需要满足：

• 左边的的括号数不多于括号对数

• 右边的括号数不多于左边的括号数

因此，只需要用回溯法生成所有组合，然后除去不符合条件的即可

class Solution {
    public List<String> generateParenthesis(int n) {
        char[] candidates = new char[] {‘(‘, ‘)‘};
        StringBuilder track = new StringBuilder();

        dfs(candidates, track, n, 0, 0);

        return res;
    }

    private List<String> res = new LinkedList<>();

    //left, right 分别记录当前track中左括号和右括号的数量
    private void dfs(char[] candidates, StringBuilder track, int n, int left, int right) {
        //去除不符合条件的结果，剪枝
        if (left > n || right > left) return;

        if (track.length() == 2*n) {
            res.add(track.toString());
            return;
        }

        for (int i = 0; i < candidates.length; i++) {
            //选择
            track.append(candidates[i]);

            if (candidates[i] == ‘(‘) {
                dfs(candidates, track, n, left + 1, right);
            } else if (candidates[i] == ‘)‘) {
                dfs(candidates, track, n, left, right + 1);
            }

            //撤销
            track.deleteCharAt(track.length() - 1);
        }
    } 
}

23. 合并K个升序链表

思路一：循环依次合并链表

思路二：两两归并

/**
 * 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) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        return mergeKLists(lists, 0, lists.length - 1);
    }

    //合并数组中下标在[left, right]之间的链表
    private ListNode mergeKLists(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }

        int mid = left + (right - left) / 2;
        ListNode leftList = mergeKLists(lists, left, mid);
        ListNode rightList = mergeKLists(lists, mid + 1, right);

        return mergeTwoList(leftList, rightList);
    }

    private ListNode mergeTwoList(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode temp = dummyNode;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                temp.next = l1;
                l1 = l1.next;
            } else {
                temp.next = l2;
                l2 = l2.next;
            }

            temp = temp.next;
        }

        if (l1 != null) temp.next = l1;
        if (l2 != null) temp.next = l2;

        return dummyNode.next;
    }
}

思路三：优先队列

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        //优先队列，小的链表结点位于队列前
        Queue<ListNode> pq = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                pq.offer(lists[i]);
            }
        }

        ListNode dummyNode = new ListNode(-1);
        ListNode temp = dummyNode;
        while (!pq.isEmpty()) {
            ListNode minNode = pq.poll();

            temp.next = minNode;
            temp = minNode;

            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }

        return dummyNode.next;
    }

}

31. 下一个排列

简单来说，对于数字排列来说字典顺序可以理解为升序。

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;

        //从右往左找找第一对升序数的位置，i指向较大元素
        int i = len - 1;
        while (i >= 1 && nums[i] <= nums[i - 1]) {
            i--;
        }

        //存在升序对时：
        //最坏情况下，交换升序对 nums[i - 1]、 nums[i]即可找到下一个排列;
        //好点的情况下，升序对右侧（低位）可能存在 nums[k] 大于 nums[i - 1]，那么交换他们即可;
        if (i >= 1) {
            for (int k = len - 1; k >= i; k--) {
                if (nums[k] > nums[i - 1]) {
                    swap(nums, k, i - 1);
                    break;
                }  
            }
        }

        reverse(nums, i, len - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

32. 最长有效括号

思路：利用栈存储下标，方便计算有效括号子串长度。

• 首先将 -1 入栈垫底
• 当字符为‘(‘，直接将下标入栈
• 当字符为‘)‘，弹出栈顶元素，若此时栈不为空，说明配对成功，然后用‘)‘下标减去此时栈顶元素下标即为当前有效括号子串长度；若此时栈为空，说明未配对成功，直接将‘)‘下标入栈垫底。

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);

        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ‘(‘) {
                stack.push(i);
            } else if (s.charAt(i) == ‘)‘){
                stack.pop();

                // ) 配对成功
                if (!stack.isEmpty()) {
                    maxLen = Math.max(maxLen, i - stack.peek());
                // ) 配对失败
                } else {
                    stack.push(i);
                }
            }
        }

        return maxLen;
    }
}

33. 搜索旋转排序数组

思路：可知旋转后的数组分为前后两段，都为升序，且前面一段始终大于后面一段。可以利用二分法，始终拿 nums[mid] 和 nums[right] 比较然后缩小范围，具体如下：

• 若 nums[mid] 小于 nums[right]， 说明 mid 位于后半段，那么 nums[mid, right]有序；
• 若 nums[mid] 大于 nums[right]， 说明 mid 位于前半段，那么 nums[left, mid] 有序。找到有序区间后可以根据 target 值快速缩小区间。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        //跳出循环时，left、 right 相邻，且都可能为target
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            //找到了
            if (nums[mid] == target) {
                return mid;
            // mid 位于后半段上升段
            } else if (nums[mid] < nums[right]) {
                // target 位于[mid, right]之间
                if (target >= nums[mid] && target <= nums[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            // mid 位于前半段上升段
            } else if (nums[mid] > nums[right]) {
                // target 位于 [left, mid]之间
                if (target >= nums[left] && target <= nums[mid]) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            // 由于 left + 1 < right，且nums不包含重复数，故不可能出现nums[mid] == nums[right]的情况
        }

        if (nums[left] == target) return left;
        if (nums[right] == target) return right;

        return -1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

思路：带边界二分查找，利用 while (left + 1 < right)容易处理边界条件。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length <= 0) return new int[] {-1, -1};

        //左边界
        int left = searchBorder(nums, target, Border.LEFT);
        if (left == -1) return new int[] {-1, -1};

        //右边界
        int right = searchBorder(nums, target, Border.RIGHT);
        return new int[] {left, right};
    }

    private int searchBorder(int[] nums, int target, Border border) {
        int left = 0;
        int right = nums.length - 1;

        //跳出循环时，left、 right 相邻，且都可能为target
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                //查找左边界
                if (border == Border.LEFT) {
                    right = mid;
                //查找右边界
                } else if (border == Border.RIGHT) {
                    left = mid;
                }
            } else if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid;
            }
        }

        //没找到
        if (nums[left] != target && nums[right] != target) {
            return -1;
        }

        //查找左边界，优先返回左边元素
        if (border == Border.LEFT) {
            return nums[left] == target ? left : right;
        //查找右边界，优先返回右边元素
        } else if (border == Border.RIGHT) {
            return nums[right] == target ? right : left;
        } else {
            throw new IllegalArgumentException("非法选项");
        }
    }
}

//使用枚举代替静态变量
enum Border {
    LEFT, RIGHT
}

39. 组合总和

思路：回溯法

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        LinkedList<Integer> track = new LinkedList<>();
        Arrays.sort(candidates); //排序后可实现进一步剪枝
        dfs(candidates, track, target, 0);
        return res;
    }

    private List<List<Integer>> res = new LinkedList<>();

    private void dfs(int[] candidates, LinkedList<Integer> track, int target, int start) {
        //不会再出现target小于0的情况
        //base case
        if (target == 0) {
            res.add(new LinkedList<>(track));
            return;
        }

        //通过start改变可选列表
        for (int i = start; i < candidates.length; i++) {
            //由于此时candidates是有序的，candidates[i] 后面的元素都大于target，直接忽略
            if (target - candidates[i] < 0) {
                break;
            }
            
            track.offerLast(candidates[i]);
            dfs(candidates, track, target - candidates[i], i);
            track.pollLast();
        }
    }
}

推荐题解：回溯算法 + 剪枝（回溯经典例题详解）

42. 接雨水

推荐一种不使用单调栈而是使用备忘录的解法：

思路一：在左边找大于等于当前高度的最大值，右边也找大于等于当前高度的最大值，两者取最小值再减去当前高度即为当前下标所能接的雨水量。

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        int len = height.length;

        //分别记录元素左边和右边的最大值
        int[] leftMax = new int[len];
        int[] rightMax = new int[len];

        //最左边元素左边的最大值
        leftMax[0] = height[0];
        //最右边元素右边的最大值
        rightMax[len - 1] = height[len - 1];

        for (int i = 1; i < len; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        for (int i = len - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int area = 0;
        for (int i = 1; i < len - 1; i++) {
            area += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return area;
    }
}

思路二：单调栈

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        
        //用来存储元素下标
        Deque<Integer> stack = new LinkedList<>();

        int area = 0;
        for (int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();

                if (stack.isEmpty()) {
                    break;
                }

                int width = i - stack.peek() - 1;
                int high = Math.min(height[stack.peek()], height[i]) - height[top];

                area += width * high;
            }
            //入栈
            stack.push(i);
        }

        return area;
    }
}

推荐图解帮助理解：【接雨水】单调递减栈，简洁代码，动图模拟

???? LeetCode 热题 HOT 100（11-20）