Golang每日一练(leetDay0012)
目录
34. 查找元素首末位置 Find-first-and-last-position-of-element-in-sorted-array 🌟🌟
35. 搜索插入位置 Search Insert Position 🌟
36. 有效的数独 Valid Sudoku 🌟🌟
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
34. 查找元素的首末位置 Find-first-and-last-position-of-element-in-sorted-array 🌟🌟
原标题:在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums
,和一个目标值 target
。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
进阶:
- 你可以设计并实现时间复杂度为
O(log n)
的算法解决此问题吗?
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8 输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6 输出:[-1,-1]
示例 3:
输入:nums = [], target = 0 输出:[-1,-1]
提示:
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums
是一个非递减数组-10^9 <= target <= 10^9
代码:二分法
对于查找左边界,设置一个变量 left,初始值为 -1,表示目标值在数组中不存在。然后用二分法查找目标值,如果找到目标值,就更新 left 的值,并继续在左半边查找,直到找到最左边的目标值。对于查找右边界,设置另一个变量 right,初始值为 -1,然后用类似的方法查找目标值的右边界。 最后,判断 left 是否等于 -1,如果是,说明目标值在数组中不存在,直接返回 [-1, -1]。 否则,返回 [left, right]。
package mainimport "fmt"func searchRange(nums []int, target int) []int {left, right := -1, -1// 查找左边界l, r := 0, len(nums)-1for l <= r {mid := (l + r) / 2if nums[mid] == target {left = midr = mid - 1} else if nums[mid] > target {r = mid - 1} else {l = mid + 1}}// 如果左边界没找到,直接返回if left == -1 {return []int{-1, -1}}// 查找右边界l, r = 0, len(nums)-1for l <= r {mid := (l + r) / 2if nums[mid] == target {right = midl = mid + 1} else if nums[mid] > target {r = mid - 1} else {l = mid + 1}}return []int{left, right}
}func main() {nums := []int{5, 7, 7, 8, 8, 10}fmt.Println(searchRange(nums, 8))fmt.Println(searchRange(nums, 6))nums = []int{}fmt.Println(searchRange(nums, 0))}
输出:
[3 4]
[-1 -1]
[-1 -1]
35. 搜索插入位置 Search Insert Position 🌟
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)
的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums
为 无重复元素 的 升序 排列数组-10^4 <= target <= 10^4
代码:
用二分法查找目标值,如果找到目标值,就返回其索引;如果目标值不在数组中,就返回它应该插入的位置。
具体实现:用两个指针 l 和 r,分别指向数组的左边界和右边界。然后用二分法查找目标值。每次查找时,取中间位置 mid,然后将目标值与 nums[mid] 进行比较。如果相等,就返回 mid;如果目标值小于 nums[mid],就将右边界 r 更新为 mid-1;如果目标值大于 nums[mid],就将左边界 l 更新为 mid+1。最后,如果目标值不在数组中,就返回左边界 l。
package mainimport "fmt"func searchInsert(nums []int, target int) int {l, r := 0, len(nums)-1for l <= r {mid := (l + r) / 2if nums[mid] == target {return mid} else if nums[mid] > target {r = mid - 1} else {l = mid + 1}}return l
}func main() {nums := []int{1, 3, 5, 6}fmt.Println(searchInsert(nums, 5))fmt.Println(searchInsert(nums, 2))fmt.Println(searchInsert(nums, 7))}
输出:
2
1
4
另一种写法:
func searchInsert(nums []int, target int) int {
l, r := 0, len(nums)-1
for l <= r {
mid := l + (r-l)>>1 //等价于: mid := (l + r) / 2
if nums[mid] >= target {
r = mid - 1
} else {
if (mid == len(nums)-1) || (nums[mid+1] >= target) {
return mid + 1
}
l = mid + 1
}
}
return 0
}
完整代码:
package mainimport "fmt"func searchInsert(nums []int, target int) int {l, r := 0, len(nums)-1for l <= r {mid := l + (r-l)>>1 //等价于: mid := (l + r) / 2if nums[mid] >= target {r = mid - 1} else {if (mid == len(nums)-1) || (nums[mid+1] >= target) {return mid + 1}l = mid + 1}}return 0
}func main() {nums := []int{1, 3, 5, 6}fmt.Println(searchInsert(nums, 5))fmt.Println(searchInsert(nums, 2))fmt.Println(searchInsert(nums, 7))}
36. 有效的数独 Valid Sudoku 🌟🌟
请你判断一个 9 x 9
的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
- 数字
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"]] 输出:true
示例 2:
输入:board = [["8","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"]] 输出:false 解释:除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示:
board.length == 9
board[i].length == 9
board[i][j]
是一位数字(1-9
)或者'.'
代码:
用三个数组来表示行、列、小九宫: rows、cols 和 boxs。
其中,rows[i][num] 表示第 i 行是否出现过数字 num,
cols[j][num] 表示第 j 列是否出现过数字 num,
boxs[k][num] 表示第 k 个子数独是否出现过数字 num。
遍历数独每一个位置,如果该位置为数字,则判断该数字在当前位置所在的行、列、小九宫中是否已经出现过。如果已经出现过,则该数独无效;否则,将其记录在对应的数组中。
package mainimport "fmt"func isValidSudoku(board [][]byte) bool {rows := make([]map[byte]bool, 9)cols := make([]map[byte]bool, 9)boxs := make([]map[byte]bool, 9)for i := 0; i < 9; i++ {rows[i] = make(map[byte]bool)cols[i] = make(map[byte]bool)boxs[i] = make(map[byte]bool)}for i := 0; i < 9; i++ {for j := 0; j < 9; j++ {if board[i][j] == '.' {continue}num := board[i][j]if rows[i][num] || cols[j][num] || boxs[(i/3)*3+j/3][num] {return false}rows[i][num] = truecols[j][num] = trueboxs[(i/3)*3+j/3][num] = true}}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'}}fmt.Println(isValidSudoku(board))board = [][]byte{{'8', '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'}}fmt.Println(isValidSudoku(board))}
输出:
true
false
循环暴力:分别对行、列、小九宫循环判断
package mainimport ("fmt""strconv"
)func isValidSudoku(board [][]byte) bool {for i := 0; i < 9; i++ {tmp := [10]int{}for j := 0; j < 9; j++ {cellVal := board[i][j : j+1]if string(cellVal) != "." {index, _ := strconv.Atoi(string(cellVal))if index > 9 || index < 1 {return false}if tmp[index] == 1 {return false}tmp[index] = 1}}}for i := 0; i < 9; i++ {tmp := [10]int{}for j := 0; j < 9; j++ {cellVal := board[j][i]if string(cellVal) != "." {index, _ := strconv.Atoi(string(cellVal))if index > 9 || index < 1 {return false}if tmp[index] == 1 {return false}tmp[index] = 1}}}for i := 0; i < 3; i++ {for j := 0; j < 3; j++ {tmp := [10]int{}for ii := i * 3; ii < i*3+3; ii++ {for jj := j * 3; jj < j*3+3; jj++ {cellVal := board[ii][jj]if string(cellVal) != "." {index, _ := strconv.Atoi(string(cellVal))if tmp[index] == 1 {return false}tmp[index] = 1}}}}}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'}}fmt.Println(isValidSudoku(board))board = [][]byte{{'8', '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'}}fmt.Println(isValidSudoku(board))}
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
![]() | Golang每日一练 专栏 |
![]() | Python每日一练 专栏 |
![]() | C/C++每日一练 专栏 |
![]() | Java每日一练 专栏 |
相关文章:

Golang每日一练(leetDay0012)
目录 34. 查找元素首末位置 Find-first-and-last-position-of-element-in-sorted-array 🌟🌟 35. 搜索插入位置 Search Insert Position 🌟 36. 有效的数独 Valid Sudoku 🌟🌟 🌟 每日一练刷题专栏 …...

Web前端:6种基本的前端编程语言
如果你想在前端web开发方面开始职业生涯,学习JavaScript是必须的。它是最受欢迎的编程语言,它功能广泛,功能强大。但JavaScript并不是你唯一需要知道的语言。HTML和CSS对于前端开发至关重要。他们将帮助你开发用户友好的网站和应用程序。什么…...

九【springboot】
Springboot一 Spring Boot是什么二 SpringBoot的特点1.独立运行的spring项目三 配置开发环境四 配置开发环境五 创建 Spring Boot 项目1.在 IntelliJ IDEA 欢迎页面左侧选择 Project ,然后在右侧选择 New Project,如下图2.在新建工程界面左侧,…...
《程序员成长历程的四个阶段》
阶段一:不知道自己不知道(Unconscious incompetence) 大学期间,我和老师做过一些小项目,自认为自己很牛,当时还去过一些公司面试做兼职,但是就是不知道为什么没有回复。那个时期的我,压根不知道自己不知道&…...
【SpringBoot】Spring data JPA的多数据源实现
一、主流的多数据源支持方式 将数据源对象作为参数,传递到调用方法内部,这种方式增加额外的编码。将Repository操作接口分包存放,Spring扫描不同的包,自动注入不同的数据源。这种方式实现简单,也是一种“约定大于配置…...
uni-app基础知识介绍
uni-app的基础知识介绍 1、在第一次将代码运行在微信开发者工具的时候,应该进行如下的配置: (1)将微信开发者工具路径进行配置; [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lbyk5Jw2-16790251840…...

Word2010(详细布局解释)
目录一、界面介绍二、选项卡1、文件选项卡(保存、打开、新建、打印、保存并发送、选项)2、开始选项卡(剪贴板、字体、段落、样式、编辑)3、插入选项卡(页、表格、插图、链接、页眉页脚、文本、符号)4、页面…...

Spring如何实现Quartz的自动配置
Spring如何实现Quartz的自动配置1. 开启Quartz自动配置2. Quartz自动配置的实现过程2.1 核心类图2.2 核心方法3. 任务调度执行3.1 大致流程3.2 调整线程池的大小如果想在应用中使用Quartz任务调度功能,可以通过Spring Boot实现Quartz的自动配置。以下介绍如何开启Qu…...
计算机组成原理——作业四
一. 单选题(共11题,33分) 1. (单选题, 3分)四片74181 ALU和一片74182 CLA器件相配合,具有如下进位传递功能:________。 A. 行波进位B. 组内先行进位,组间行波进位C. 组内先行进位,组间先行进位D. 组内行波进位,组间先行进位 我的答案: C 3…...
2023前端面试题(经典面试题)
经典面试题Vue2.0 和 Vue3.0 有什么区别?vue中计算属性和watch以及methods的区别?单页面应用和多页面应用区别及优缺点?说说 Vue 中 CSS scoped 的原理?谈谈对Vue中双向绑定的理解?为什么vue2和vue3语法不可以混用&…...

【Linux内网穿透】使用SFTP工具快速实现内网穿透
文章目录内网穿透简介1. 查看地址2.局域网测试连接3.创建tcp隧道3.1. 安装cpolar4.远程访问5.固定TCP地址内网穿透简介 是一种通过公网将内网服务暴露出来的技术,可以使得内网服务可以被外网访问。以下是内网穿透的一些应用: 远程控制:通过内…...

SQL语句性能分析
1. 数据库服务器的优化步骤 当我们遇到数据库调优问题的时候,该如何思考呢?这里把思考的流程整理成下面这张图。 整个流程划分成了 观察(Show status) 和 行动(Action) 两个部分。字母 S 的部分代表观察&…...
【K3s】第28篇 详解 k3s-killall.sh 脚本
目录 k3s-killall.sh 脚本 k3s-killall.sh 脚本 为了在升级期间实现高可用性,当 K3s 服务停止时,K3s 容器会继续运行。 要停止所有的 K3s 容器并重置容器的状态,可以使用k3s-killall.sh脚本。 killall 脚本清理容器、K3s 目录和网络组件&a…...
生成时序异常样本-学习记录-未完待续
1.GAN&VAE|时间序列生成及异常注入那些事儿:主要讲了数据增广,用GAN、WGAN、DCGAN、VAE,有给几个代码的github的链接,非常有用 2.时序异常检测综述,写的非常好 3.自编码器原理讲解,后面还附…...

自定义类型的超详细讲解ᵎᵎ了解结构体和位段这一篇文章就够了ᵎ
目录 1.结构体的声明 1.1基础知识 1.2结构体的声明 1.3结构体的特殊声明 1.4结构体的自引用 1.5结构体变量的定义和初始化 1.6结构体内存对齐 那对齐这么浪费空间,为什么要对齐 1.7修改默认对齐数 1.8结构体传参 2.位段 2.1什么是位段 2.2位段的内存分配…...

【五】springboot启动源码 - onRefresh
onRefresh 源码解析 Initialize other special beans in specific context subclasses. 核心是创建一个web服务容器(并未在这个方法启动) createWebServer第182行,获取ServletWebServerFactory的具体实现 getWebServerFactory方法ÿ…...
带你一文透彻学习【PyTorch深度学习实践】分篇——线性回归(训练周期:前馈、反馈、权重更新)
“梦想使你迷醉,距离就成了快乐;追求使你充实,失败和成功都是伴奏;当生命以美的形式证明其价值的时候,幸福是享受,痛苦也是享受。” --------史铁生《好运设计》 🎯作者主页:追光者♂🔥 🌸个人简介:计算机专业硕士研究生💖、2022年CSDN博客之星人工…...

【前端八股文】浏览器系列:性能优化——HTML、CSS、JS、渲染优化
文章目录HTMLCSSCSS加载会造成阻塞吗JavaScript渲染优化参考本系列目录:【前端八股文】目录总结 是以《代码随想录》八股文为主的笔记。详情参考在文末。 代码随想录的博客_CSDN博客-leecode题解,ACM题目讲解,代码随想录领域博主 性能优化,从以下几个方…...

Linux分文件编程:静态库与动态库的生成和使用
目录 一,Linux库引入之分文件编程 ① 简单说明 ② 分文件编程优点 ③ 操作逻辑 ④ 代码实现说明 二,Linux库的基本说明 三,Linux库之静态库的生成与使用 ① 静态库命名规则 ② 静态库制作步骤 ③ 静态库的使用 四,Linu…...

技术人的管理学-业务管理
主要内容前言制定计划遇到的问题?过程监控遇到的问题?复盘改进遇到的问题?通过PDCA循环解决业务管理问题总结前言 没有人天生就会管理,优秀的管理者都是在知行合一的过程中成长起来的,他们既需要系统的管理知识&#…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...

uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析
1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器(TI)推出的一款 汽车级同步降压转换器(DC-DC开关稳压器),属于高性能电源管理芯片。核心特性包括: 输入电压范围:2.95V–6V,输…...
2.2.2 ASPICE的需求分析
ASPICE的需求分析是汽车软件开发过程中至关重要的一环,它涉及到对需求进行详细分析、验证和确认,以确保软件产品能够满足客户和用户的需求。在ASPICE中,需求分析的关键步骤包括: 需求细化:将从需求收集阶段获得的高层需…...
2025.6.9总结(利与弊)
凡事都有两面性。在大厂上班也不例外。今天找开发定位问题,从一个接口人不断溯源到另一个 接口人。有时候,不知道是谁的责任填。将工作内容分的很细,每个人负责其中的一小块。我清楚的意识到,自己就是个可以随时替换的螺丝钉&…...
Java多线程实现之Runnable接口深度解析
Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录
#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...