# 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) {
return;
}

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

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

### 23. 合并K个升序链表

``````/**
* 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;
}

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;
}
}``````

``````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);
}
}

while (!pq.isEmpty()) {
ListNode node = pq.poll();
// 先指定当前指针位置的下一节点，然后移动指针到下一节点
prev.next = node;
prev = prev.next;
if (node.next != null) {
pq.offer(node.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--;
}
}
}
}``````

(=￣ω￣=)··· 暂无内容！

87

10

21

39