09/05 🔥 LeetCode 热题 HOT 100 -- 22, 23,31

22. 括号生成

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateParenthesisHelper(n, n, "", result);
        return result;
    }

    private void generateParenthesisHelper(int leftNeeded, int rightNeeded, String currentString, List<String> result) {
        // 递归终止条件
        if (leftNeeded == 0 && rightNeeded == 0) {
            result.add(currentString);
            return;
        }

        // 只有当左边需要的括号>0才加
        if (leftNeeded > 0) {
            generateParenthesisHelper(leftNeeded - 1, rightNeeded, currentString + "(", result);
        }

        if (leftNeeded < rightNeeded) {
            generateParenthesisHelper(leftNeeded, rightNeeded - 1, currentString + ")", result);
        }
    }
}

23. 合并K个升序链表

解法一: 每次合并两个链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        ListNode merged = lists[0];

        for (int i = 1; i < lists.length; i++) {
            merged = mergeTwoLists(merged, lists[i]);
        }

        return merged;
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }

        ListNode dummyHead = new ListNode(-1);
        ListNode p = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        p.next = l1 == null ? l2 : l1;
        return dummyHead.next;
    }
}

解法二：利用优先队列对所有元素一次合并

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

        PriorityQueue<ListNode> pq = new PriorityQueue<>((l1, l2)->l1.val - l2.val);
        for (ListNode i : lists) {
            if (i != null) {
                pq.offer(i);
            }
        }

        ListNode head = new ListNode(-1);
        ListNode prev = head;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
        // 先指定当前指针位置的下一节点，然后移动指针到下一节点
            prev.next = node;
            prev = prev.next;
            if (node.next != null) {
                pq.offer(node.next);
            }
        }

        return head.next;
    }
}

31. 下一个排列

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // i = 3
        // 找到后面数字递减开始的位置，即找到左边尽量靠右的较小的数
        // [1, 4, 5, 3, 1]
        while (i >= 0 && nums[i + 1] <= nums[i]) { // nums[1 + 1] > nums[1], 跳出
            i--;
        }
        // i = 1

        if (i >= 0) {
            // 找到i右边比nums[i]大的数
            int j = nums.length - 1; // j = 4
            while (j >= i && nums[j] <= nums[i]) { // nums[2] > nums[1], 跳出
                j--;
            }
            // j = 2

            swap(i, j, nums);
        }
        // [1, 5, 4, 3, 1]

        // Reverse all the numbers after i
        int start = i + 1; // start = 2

        reverse(nums, start);
        // [1, 5, 1, 3, 4]
    }

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

    private void reverse(int[] nums, int start) {
        int end = nums.length - 1;
        while (start < end) {
            swap(start, end, nums);
            start++;
            end--;
        }
    }
}
}

本作品采用《CC 协议》，转载必须注明作者和本文链接