Golang每日一练(leetDay0013)

目录

37. 解数独 Sudoku Solver  🌟🌟🌟

38. 外观数列 Count and Say  🌟🌟

39. 组合总和 Combination Sum  🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


37. 解数独 Sudoku Solver

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

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

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 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))
	}

}

输出:

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 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))

}

🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力! 

🌟 收藏,你的青睐是我努力的方向! 

评论,你的意见是我进步的财富!  

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/2510.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

大数据技术之Hive

第1章Hive基本概念1.1 Hive1.1.1 Hive的产生背景在那一年的大数据开源社区&#xff0c;我们有了HDFS来存储海量数据、MapReduce来对海量数据进行分布式并行计算、Yarn来实现资源管理和作业调度。但是面对海量数据和负责的业务逻辑&#xff0c;开发人员要编写MR来对数据进行统计…

【Go】K8s 管理系统项目[Jenkins Pipeline K8s环境–应用部署]

K8s 管理系统项目[Jenkins Pipeline K8s环境–应用部署] 1. k8s-plantform-api-Pipeline 考虑到实际工作中前后端可能是不同的同学完成,一般Api部分完成后改动会比较小,web部分改动会比较频繁.于是将api和web分了2个pipeline实现 1.1 GIt仓库 docker目录存放镜像构建相关文件…

简介虚拟地址空间:保障进程间独立性的机制

我们知道&#xff0c;进程之间是相互独立的&#xff0c;在操作系统级别中&#xff0c;一个进程所执行的程序无法直接访问另一个进程所执行的内存区域&#xff08;即实现进程间通信比较困难&#xff09;&#xff1b;一个进程运行的失败也不会影响其它进程的运行。这使我们的操作…

vue编程方法

1&#xff0c;app.vue 其中的moundted只是被执行一次。 系统中所有的组件都放到app。vue文件中。放到根组件中的只是被执行一次的代码可以放到main.js中码&#xff1f; 不可以&#xff0c;因为main文件只是一个js文件不是一个组件。组件中的一些属性不能被使用。比如&#xff…

VS Code上搭建Vue开发环境超详细教程

这篇关于在Visual Studio Code上搭建vue开发环境的超详细教程手把手教会你! 首先在Visual Studio Code上搭建vue开发环境有几个步骤&#xff1a; 1、下载安装node.js 2、安装npm 3、安装cnpm 4、安装vue/cli脚手架 5、创建vue项目 6、运行vue项目 1.下载安装node.js 地址&…

鸟哥的Linux私房菜 正则表示法与文件格式化处理

第十一章、正则表示法与文件格式化处理 https://linux.vbird.org/linux_basic/centos7/0330regularex.php 简体版 http://cn.linux.vbird.org/linux_basic/0330regularex.php 11.2.2 grep的一些高级选项 例题一、搜索特定字符串 例题二、利用中括号 [] 来搜寻集合字符 例题四…

8个python自动化脚本提高打工人幸福感~比心~

人生苦短&#xff0c;我用Python 最近有许多打工人都找我说打工好难 每天都是执行许多重复的任务&#xff0c; 例如阅读新闻、发邮件、查看天气、打开书签、清理文件夹等等&#xff0c; 使用自动化脚本&#xff0c;就无需手动一次又一次地完成这些任务&#xff0c; 非常方便…

蓝桥杯嵌入式RTC实时时钟

文章目录 前言一、RTC是什么二、cubemx的配置三、函数的使用总结前言 本篇文章将给大家介绍RTC实时时钟。 一、RTC是什么 STM32的实时时钟RTC是一个独立的定时器,RTC时钟内部依靠BCD码计数。RTC实时时钟提高时钟、闹钟、日历功能。RTC功耗较低,可以使用在低功耗设备上。 …

Redis为什么选择单线程?Redis为什么这么快?

目录专栏导读一、Redis版本迭代二、Redis4.0之前为什么一直采用单线程&#xff1f;三、Redis6.0引入多线程四、Redis主线程和IO线程是如何完成请求的&#xff1f;1、服务端和客户端建立socket连接2、IO线程读取并解析请求3、主线程执行请求命令4、IO线程会写回socket和主线程清…

DM8:LINUX环境安装DM8数据库安装条件--GLIBC版本要求

DM8&#xff1a;LINUX环境安装DM8数据库安装条件--GLIBC版本要求环境介绍1 检查 GLIBC 版本号2 /tmp 临时目录空间要等于或大于2GB3 报错截图3.1 导入授权报错3.2 设置时区报错3.3 DmAPService启动失败3.4 初始化实例报错4 更多达梦数据库使用经验环境介绍 在LINUX环境安装达梦…

一线大厂软件测试常见面试题1500问,背完直接拿捏面试官,

三、测试理论 3.1 你们原来项目的测试流程是怎么样的? 我们的测试流程主要有三个阶段&#xff1a;需求了解分析、测试准备、测试执行。 1、需求了解分析阶段 我们的SE会把需求文档给我们自己先去了解一到两天这样&#xff0c;之后我们会有一个需求澄清会议&#xff0c; 我…

基于Springboot实现口腔牙诊所网站平台【源码+论文】

基于Springboot实现口腔牙诊所网站平台【源码论文】开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea M…

整合SpringCache

整合SpringCache 1、引入依赖cache还有redis <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-cache</artifactId> </dependency>2、写配置 spring:cache:type: redis3、测试使用缓存 Cache…

大数据现在找工作难么

大数据行业工作好找还是难找不是光靠嘴说出来的结合实际&#xff0c;看看市场上的招聘需求和岗位要求就大致知道了 要想符合企业用人规范&#xff0c;学历&#xff0c;工作经验&#xff0c;掌握技能都是非常重要的~ 先来看几个招聘网站的报告数据&#xff1a; Boss直聘发布的…

【蓝桥杯】 C++ 数字三角形 动态规划 ⭐⭐

文章目录题目描述输入描述输出描述实现代码解题思路注意点知识点题目描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径&#xff0c;把路径上面的数加起来可以得到一个和&#xff0c;你的任务就是找到最大的和&#xff08;路径上的每一步…

Python嵌套函数(Nested function)和闭包(closure)

Python嵌套函数&#xff08;Nested function&#xff09;和闭包&#xff08;closure&#xff09; 闭包&#xff08;closure&#xff09;是建立在嵌套函数基础上的&#xff0c;是一种特殊的嵌套函数结构。 先看嵌套函数&#xff08;Nested function&#xff09;。 Python允许…

gan实战(DCGAN、)

一、DCGAN 1.1 参数 &#xff08;1&#xff09;输入&#xff1a;会被放缩到6464 &#xff08;2&#xff09;输出&#xff1a;6464 &#xff08;3&#xff09;数据集&#xff1a; 1.2 实现 import glob import torch from PIL import Image from torch import nn from torch.u…

web前端框架——Vue的特性

目录 前言&#xff1a; 一.vue 二.特性 1.轻量级 2.数据绑定 3.指令 4.插件 三.比较Angular 、React 、Vue 框架之间的比较 1. Angular Angular的优点&#xff1a; 2. React React 的优点&#xff1a; 3.vue 3.Vue的优点&#xff1a; 前言&#xff1a; 本篇文章…

有效的括号长按键入验证外星语词典字符的最短距离用栈实现队列

有效的括号来源&#xff1a;杭哥20. 有效的括号 - 力扣&#xff08;LeetCode&#xff09;bool isValid(char * s) {int szstrlen(s);char stack[sz];int k0;for (int i0;i<sz;i){if (s[i]( || s[i][ || s[i]{){stack[k]s[i];}else{if (k0){return false;}else if (s[i]} &am…

C++ Qt自建网页浏览器

C Qt自建网页浏览器如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01;前言这篇博客针对<<C Qt自建网页浏览器>>编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。 学习与应用推荐首选。文…