当前位置：首页 > news >正文

Golang每日一练(leetDay0013)

news 2025/8/8 23:59:10

37. 解数独 Sudoku Solver 🌟🌟🌟

38. 外观数列 Count and Say 🌟🌟

39. 组合总和 Combination Sum 🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

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 mainimport "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')] = truecols[i][byte(j+'0')] = truesudo[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) boolbacktrack = 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] = truecols[j][num] = truesudo[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 := truefor i, row := range board {for j, col := range row {if col != answer[i][j] {equal = falsebreak}}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 mainimport "fmt"type position struct {x inty int
}func solveSudoku(board [][]byte) {pos, find := []position{}, falsefor 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 = truereturn}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%3for 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 := truefor i, row := range board {for j, col := range row {if col != answer[i][j] {equal = falsebreak}}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 mainimport ("fmt""strconv""strings"
)func countAndSay(n int) string {if n == 1 {return "1"}prev := countAndSay(n - 1)var res strings.Builderfor 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))}}

输出：

1
11
21
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 mainimport "fmt"func combinationSum(candidates []int, target int) [][]int {var res [][]intvar 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 mainimport ("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))}