37. 解数独 Sudoku Solver

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [

["5","3",".",".","7",".",".",".","."],

["6",".",".","1","9","5",".",".","."],

[".","9","8",".",".",".",".","6","."],

["8",".",".",".","6",".",".",".","3"],

["4",".",".","8",".","3",".",".","1"],

["7",".",".",".","2",".",".",".","6"],

[".","6",".",".",".",".","2","8","."],

[".",".",".","4","1","9",".",".","5"],

[".",".",".",".","8",".",".","7","9"]]

输出：

[["5","3","4","6","7","8","9","1","2"],

["6","7","2","1","9","5","3","4","8"],

["1","9","8","3","4","2","5","6","7"],

["8","5","9","7","6","1","4","2","3"],

["4","2","6","8","5","3","7","9","1"],

["7","1","3","9","2","4","8","5","6"],

["9","6","1","5","3","7","2","8","4"],

["2","8","7","4","1","9","6","3","5"],

["3","4","5","2","8","6","1","7","9"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9

board[i].length == 9

board[i][j] 是一位数字或者 '.'

题目数据保证输入数独仅有一个解

代码：

package main
import "fmt"
func solveSudoku(board [][]byte) {
  rows := make([]map[byte]bool, 9) // 行集合
  cols := make([]map[byte]bool, 9) // 列集合
  sudo := make([]map[byte]bool, 9) // 3x3宫格集合
  empty := make([][2]int, 0)       // 空格子坐标
  // 初始化行、列、3x3宫格集合
  for i := 0; i < 9; i++ {
    rows[i] = make(map[byte]bool)
    cols[i] = make(map[byte]bool)
    sudo[i] = make(map[byte]bool)
    for j := 1; j <= 9; j++ {
      rows[i][byte(j+'0')] = true
      cols[i][byte(j+'0')] = true
      sudo[i][byte(j+'0')] = true
    }
  }
  // 预处理，将空格子坐标和行、列、3x3宫格集合更新
  for i := 0; i < 9; i++ {
    for j := 0; j < 9; j++ {
      if board[i][j] != '.' {
        val := board[i][j]
        delete(rows[i], val)
        delete(cols[j], val)
        delete(sudo[(i/3)*3+j/3], val)
      } else {
        empty = append(empty, [2]int{i, j})
      }
    }
  }
  // 回溯函数
  var backtrack func(int) bool
  backtrack = func(iter int) bool {
    // 所有空格子坐标均已填充
    if iter == len(empty) {
      return true
    }
    // 获取空格子坐标
    i, j := empty[iter][0], empty[iter][1]
    // 获取该格子所在3x3宫格索引
    k := (i/3)*3 + j/3
    // 该格子可选数值集合
    choices := make(map[byte]bool)
    for num := range rows[i] {
      if cols[j][num] && sudo[k][num] {
        choices[num] = true
      }
    }
    for num := range choices {
      // 尝试填充该格子
      board[i][j] = num
      // 更新行、列、3x3宫格集合
      delete(rows[i], num)
      delete(cols[j], num)
      delete(sudo[k], num)
      // 递归填充下一个空格子
      if backtrack(iter + 1) {
        return true
      }
      // 回溯，还原现场
      rows[i][num] = true
      cols[j][num] = true
      sudo[k][num] = true
    }
    // 所有数值均不可选，回溯到上一层
    board[i][j] = '.'
    return false
  }
  backtrack(0)
}
func main() {
  board := [][]byte{
    {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
    {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
    {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
    {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
    {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
    {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
    {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
    {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
    {'.', '.', '.', '.', '8', '.', '.', '7', '9'}}
  solveSudoku(board)
  for _, row := range board {
    for _, col := range row {
      fmt.Print(col-48, " ")
    }
    fmt.Println()
  }
  answer := [][]byte{
    {'5', '3', '4', '6', '7', '8', '9', '1', '2'},
    {'6', '7', '2', '1', '9', '5', '3', '4', '8'},
    {'1', '9', '8', '3', '4', '2', '5', '6', '7'},
    {'8', '5', '9', '7', '6', '1', '4', '2', '3'},
    {'4', '2', '6', '8', '5', '3', '7', '9', '1'},
    {'7', '1', '3', '9', '2', '4', '8', '5', '6'},
    {'9', '6', '1', '5', '3', '7', '2', '8', '4'},
    {'2', '8', '7', '4', '1', '9', '6', '3', '5'},
    {'3', '4', '5', '2', '8', '6', '1', '7', '9'}}
  // 判断与答案是否一致
  equal := true
  for i, row := range board {
    for j, col := range row {
      if col != answer[i][j] {
        equal = false
        break
      }
    }
    if !equal {
      break
    }
  }
  fmt.Println(equal)
}

输出：

5 3 4 6 7 8 9 1 2

6 7 2 1 9 5 3 4 8

1 9 8 3 4 2 5 6 7

8 5 9 7 6 1 4 2 3

4 2 6 8 5 3 7 9 1

7 1 3 9 2 4 8 5 6

9 6 1 5 3 7 2 8 4

2 8 7 4 1 9 6 3 5

3 4 5 2 8 6 1 7 9

true

代码2：

package main
import "fmt"
type position struct {
  x int
  y int
}
func solveSudoku(board [][]byte) {
  pos, find := []position{}, false
  for i := 0; i < len(board); i++ {
    for j := 0; j < len(board[0]); j++ {
      if board[i][j] == '.' {
        pos = append(pos, position{x: i, y: j})
      }
    }
  }
  putSudoku(&board, pos, 0, &find)
}
func putSudoku(board *[][]byte, pos []position, index int, succ *bool) {
  if *succ == true {
    return
  }
  if index == len(pos) {
    *succ = true
    return
  }
  for i := 1; i < 10; i++ {
    if checkSudoku(board, pos[index], i) && !*succ {
      (*board)[pos[index].x][pos[index].y] = byte(i) + '0'
      putSudoku(board, pos, index+1, succ)
      if *succ == true {
        return
      }
      (*board)[pos[index].x][pos[index].y] = '.'
    }
  }
}
func checkSudoku(board *[][]byte, pos position, val int) bool {
  // 判断行是否有重复数字
  for i := 0; i < len((*board)[0]); i++ {
    if (*board)[pos.x][i] != '.' && int((*board)[pos.x][i]-'0') == val {
      return false
    }
  }
  // 判断列是否有重复数字
  for i := 0; i < len((*board)); i++ {
    if (*board)[i][pos.y] != '.' && int((*board)[i][pos.y]-'0') == val {
      return false
    }
  }
  // 判断九宫格是否有重复数字
  posx, posy := pos.x-pos.x%3, pos.y-pos.y%3
  for i := posx; i < posx+3; i++ {
    for j := posy; j < posy+3; j++ {
      if (*board)[i][j] != '.' && int((*board)[i][j]-'0') == val {
        return false
      }
    }
  }
  return true
}
func main() {
  board := [][]byte{
    {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
    {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
    {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
    {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
    {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
    {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
    {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
    {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
    {'.', '.', '.', '.', '8', '.', '.', '7', '9'}}
  solveSudoku(board)
  for _, row := range board {
    for _, col := range row {
      fmt.Print(col-48, " ")
    }
    fmt.Println()
  }
  answer := [][]byte{
    {'5', '3', '4', '6', '7', '8', '9', '1', '2'},
    {'6', '7', '2', '1', '9', '5', '3', '4', '8'},
    {'1', '9', '8', '3', '4', '2', '5', '6', '7'},
    {'8', '5', '9', '7', '6', '1', '4', '2', '3'},
    {'4', '2', '6', '8', '5', '3', '7', '9', '1'},
    {'7', '1', '3', '9', '2', '4', '8', '5', '6'},
    {'9', '6', '1', '5', '3', '7', '2', '8', '4'},
    {'2', '8', '7', '4', '1', '9', '6', '3', '5'},
    {'3', '4', '5', '2', '8', '6', '1', '7', '9'}}
  // 判断与答案是否一致
  equal := true
  for i, row := range board {
    for j, col := range row {
      if col != answer[i][j] {
        equal = false
        break
      }
    }
    if !equal {
      break
    }
  }
  fmt.Println(equal)
}

38. 外观数列 Count and Say

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = "1"

countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1. 1

2. 11

3. 21

4. 1211

5. 111221

第一项是数字 1 描述前一项，这个数是 1 即 “ 一个 1 ”，记作 "11"

描述前一项，这个数是 11 即 “ 二个 1 ” ，记作 "21"

描述前一项，这个数是 21 即 “ 一个 2 + 一个 1 ” ，记作 "1211"

描述前一项，这个数是 1211 即 “ 一个 1 + 一个 2 + 二个 1 ” ，记作 "111221"

要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

示例 1：

输入：n = 1

输出："1"

解释：这是一个基本样例。

示例 2：

输入：n = 4

输出："1211"

解释：

countAndSay(1) = "1"

countAndSay(2) = 读 "1" = 一个 1 = "11"

countAndSay(3) = 读 "11" = 二个 1 = "21"

countAndSay(4) = 读 "21" = 一个 2 + 一个 1 = "12" + "11" = "1211"

提示：

1 <= n <= 30

代码：

package main
import (
  "fmt"
  "strconv"
  "strings"
)
func countAndSay(n int) string {
  if n == 1 {
    return "1"
  }
  prev := countAndSay(n - 1)
  var res strings.Builder
  for i, j := 0, 0; j <= len(prev); j++ {
    if j == len(prev) || prev[j] != prev[i] {
      res.WriteString(strconv.Itoa(j - i))
      res.WriteByte(prev[i])
      i = j
    }
  }
  return res.String()
}
func main() {
  for i := 1; i < 6; i++ {
    fmt.Println(countAndSay(i))
  }
}

输出：

1211

111221

39. 组合总和 Combination Sum

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7

输出：[[2,2,3],[7]]

解释：

2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。

7 也是一个候选， 7 = 7 。仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8

输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1

输出: []

提示：

1 <= candidates.length <= 30

1 <= candidates[i] <= 200

candidate 中的每个元素都互不相同

1 <= target <= 500

代码：

package main
import "fmt"
func combinationSum(candidates []int, target int) [][]int {
  var res [][]int
  var backtrack func([]int, int, int)
  backtrack = func(path []int, sum int, start int) {
    if sum >= target {
      if sum == target {
        res = append(res, append([]int{}, path...))
        return
      }
      return
    }
    for i := start; i < len(candidates); i++ {
      path = append(path, candidates[i])
      backtrack(path, sum+candidates[i], i)
      path = path[:len(path)-1]
    }
  }
  backtrack([]int{}, 0, 0)
  return res
}
func main() {
  candidates := []int{2, 3, 6, 7}
  fmt.Println(combinationSum(candidates, 7))
  candidates = []int{2, 3, 5}
  fmt.Println(combinationSum(candidates, 8))
  candidates = []int{2}
  fmt.Println(combinationSum(candidates, 1))
}

输出：

[[2 2 3] [7]]

[[2 2 2 2] [2 3 3] [3 5]]

[]

代码2：

package main
import (
  "fmt"
  "sort"
)
func combinationSum(candidates []int, target int) [][]int {
  if len(candidates) == 0 {
    return [][]int{}
  }
  c, res := []int{}, [][]int{}
  sort.Ints(candidates)
  findcombinationSum(candidates, target, 0, c, &res)
  return res
}
func findcombinationSum(nums []int, target, index int, c []int, res *[][]int) {
  if target <= 0 {
    if target == 0 {
      b := make([]int, len(c))
      copy(b, c)
      *res = append(*res, b)
    }
    return
  }
  for i := index; i < len(nums); i++ {
    if nums[i] > target {
      break
    }
    c = append(c, nums[i])
    findcombinationSum(nums, target-nums[i], i, c, res)
    c = c[:len(c)-1]
  }
}
func main() {
  candidates := []int{2, 3, 6, 7}
  fmt.Println(combinationSum(candidates, 7))
  candidates = []int{2, 3, 5}
  fmt.Println(combinationSum(candidates, 8))
  candidates = []int{2}
  fmt.Println(combinationSum(candidates, 1))
}