22. 括号生成 Generate Parentheses

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1

输出：["()"]

提示：

1 <= n <= 8

代码：回溯法

package main
import "fmt"
func generateParenthesis(n int) []string {
  var res []string
  var stack []byte
  var backtrack func(int, int)
  backtrack = func(left, right int) {
    if len(stack) == 2*n {
      res = append(res, string(stack))
      return
    }
    if left < n {
      stack = append(stack, '(')
      backtrack(left+1, right)
      stack = stack[:len(stack)-1]
    }
    if right < left {
      stack = append(stack, ')')
      backtrack(left, right+1)
      stack = stack[:len(stack)-1]
    }
  }
  backtrack(0, 0)
  return res
}
func main() {
  fmt.Println(generateParenthesis(3))
  fmt.Println(generateParenthesis(1))
}

递归法：

package main
import "fmt"
func generateParenthesis(n int) []string {
  if n == 0 {
    return []string{}
  }
  res := []string{}
  findParentheses(n, n, "", &res)
  return res
}
func findParentheses(left, right int, str string, res *[]string) {
  if left == 0 && right == 0 {
    *res = append(*res, str)
    return
  }
  if left > 0 {
    findParentheses(left-1, right, str+"(", res)
  }
  if right > 0 && left < right {
    findParentheses(left, right-1, str+")", res)
  }
}
func main() {
  fmt.Println(generateParenthesis(3))
    fmt.Println(generateParenthesis(1))
}

输出：

[((())) (()()) (())() ()(()) ()()()]

[()]

23. 合并K个升序链表 Merge K Sorted Lists

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

相关题目： Leetcode 21 Merge-two-sorted-lists

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]

输出：[1,1,2,3,4,4,5,6]

解释：链表数组如下：

[

1->4->5,

1->3->4,

2->6

]

将它们合并到一个有序链表中得到。

1->1->2->3->4->4->5->6

示例 2：

输入：lists = []

输出：[]

示例 3：

输入：lists = [[]]

输出：[]

提示：

k == lists.length

0 <= k <= 10^4

0 <= lists[i].length <= 500

-10^4 <= lists[i][j] <= 10^4

lists[i] 按升序排列

lists[i].length 的总和不超过 10^4

代码：

package main
import "fmt"
type ListNode struct {
  data int
  next *ListNode
}
func build(nums []int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{data: nums[0]}
  p := head
  for i := 1; i < len(nums); i++ {
    node := &ListNode{data: nums[i]}
    p.next = node
    p = p.next
  }
  return head
}
func (head *ListNode) travel() {
  for p := head; p != nil; p = p.next {
    fmt.Print(p.data)
    if p.next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
func mergeKLists(lists []*ListNode) *ListNode {
  length := len(lists)
  if length < 1 {
    return nil
  }
  if length == 1 {
    return lists[0]
  }
  num := length / 2
  left := mergeKLists(lists[:num])
  right := mergeKLists(lists[num:])
  return mergeTwoLists1(left, right)
}
func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
  if l1 == nil {
    return l2
  }
  if l2 == nil {
    return l1
  }
  if l1.data < l2.data {
    l1.next = mergeTwoLists1(l1.next, l2)
    return l1
  }
  l2.next = mergeTwoLists1(l1, l2.next)
  return l2
}
func main() {
  nums := [][]int{[]int{1, 4, 5}, []int{1, 3, 4}, []int{2, 6}}
  lists := []*ListNode{}
  for _, num := range nums {
    node := build(num)
    node.travel()
    lists = append(lists, node)
  }
  fmt.Print("Merge Result: ")
  mergeKLists(lists).travel()
}

输出：

1->4->5<nil>

1->3->4<nil>

2->6<nil>

Merge Result: 1->1->2->3->4->4->5->6<nil>

堆 Heap：

package main
import (
  "container/heap"
  "fmt"
)
type ListNode struct {
  data int
  next *ListNode
}
func build(nums []int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{data: nums[0]}
  p := head
  for i := 1; i < len(nums); i++ {
    node := &ListNode{data: nums[i]}
    p.next = node
    p = p.next
  }
  return head
}
func (head *ListNode) travel() {
  for p := head; p != nil; p = p.next {
    fmt.Print(p.data)
    if p.next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
type MinHeap []*ListNode
func (h MinHeap) Len() int {
  return len(h)
}
func (h MinHeap) Less(i, j int) bool {
  return h[i].data < h[j].data
}
func (h MinHeap) Swap(i, j int) {
  h[i], h[j] = h[j], h[i]
}
func (h *MinHeap) Push(x interface{}) {
  *h = append(*h, x.(*ListNode))
}
func (h *MinHeap) Pop() interface{} {
  n := len(*h)
  x := (*h)[n-1]
  *h = (*h)[:n-1]
  return x
}
func mergeKLists(lists []*ListNode) *ListNode {
  h := &MinHeap{}
  for _, node := range lists {
    if node != nil {
      heap.Push(h, node)
    }
  }
  dummy := &ListNode{}
  cur := dummy
  for h.Len() > 0 {
    node := heap.Pop(h).(*ListNode)
    cur.next = node
    cur = cur.next
    if node.next != nil {
      heap.Push(h, node.next)
    }
  }
  return dummy.next
}
func main() {
  nums := [][]int{[]int{1, 4, 5}, []int{1, 3, 4}, []int{2, 6}}
  lists := []*ListNode{}
  for _, num := range nums {
    node := build(num)
    node.travel()
    lists = append(lists, node)
  }
  fmt.Print("Merge Result: ")
  mergeKLists(lists).travel()
}

24. 两两交换链表中的节点 Swap Nodes In Pairs

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]

输出：[2,1,4,3]

示例 2：

输入：head = []

输出：[]

示例 3：

输入：head = [1]

输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内

0 <= Node.val <= 100

代码：

package main
import "fmt"
type ListNode struct {
  data int
  next *ListNode
}
func build(nums []int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{data: nums[0]}
  p := head
  for i := 1; i < len(nums); i++ {
    node := &ListNode{data: nums[i]}
    p.next = node
    p = p.next
  }
  return head
}
func (head *ListNode) travel() {
  for p := head; p != nil; p = p.next {
    fmt.Print(p.data)
    if p.next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
func swapPairs(head *ListNode) *ListNode {
  if head == nil || head.next == nil {
    return head
  }
  res := head.next
  var behind *ListNode
  for head.next != nil {
    nextnode := head.next
    if behind != nil && behind.next != nil {
      behind.next = nextnode
    }
    var next *ListNode
    if head.next.next != nil {
      next = head.next.next
    }
    if head.next.next != nil {
      head.next = next
    } else {
      head.next = nil
    }
    nextnode.next = head
    behind = head
    if head.next != nil {
      head = next
    }
  }
  return res
}
func main() {
  nums := []int{1, 2, 3, 4}
  head := build(nums)
  head.travel()
  swapPairs(head).travel()
  nums = append(nums, 5)
  head = build(nums)
  head.travel()
  swapPairs(head).travel()
}

输出：

1->2->3->4<nil>

2->1->4->3<nil>

1->2->3->4->5<nil>

2->1->4->3->5<nil>

递归法：

package main
import "fmt"
type ListNode struct {
  data int
  next *ListNode
}
func build(nums []int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{data: nums[0]}
  p := head
  for i := 1; i < len(nums); i++ {
    node := &ListNode{data: nums[i]}
    p.next = node
    p = p.next
  }
  return head
}
func (head *ListNode) travel() {
  for p := head; p != nil; p = p.next {
    fmt.Print(p.data)
    if p.next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
func swapPairs(head *ListNode) *ListNode {
  if head == nil || head.next == nil {
    return head
  }
  node := head.next
  head.next = swapPairs(node.next)
  node.next = head
  return node
}
func main() {
  nums := []int{1, 2, 3, 4}
  head := build(nums)
  head.travel()
  swapPairs(head).travel()
  nums = append(nums, 5)
  head = build(nums)
  head.travel()
  swapPairs(head).travel()
}