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循环解决业务管理问题总结前言 没有人天生就会管理,优秀的管理者都是在知行合一的过程中成长起来的,他们既需要系统的管理知识&#…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...

企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...

elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...