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

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. 数字 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"]]
输出: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 &#x1f31f;&#x1f31f; 35. 搜索插入位置 Search Insert Position &#x1f31f; 36. 有效的数独 Valid Sudoku &#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 …...

Web前端:6种基本的前端编程语言

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

九【springboot】

Springboot一 Spring Boot是什么二 SpringBoot的特点1.独立运行的spring项目三 配置开发环境四 配置开发环境五 创建 Spring Boot 项目1.在 IntelliJ IDEA 欢迎页面左侧选择 Project &#xff0c;然后在右侧选择 New Project&#xff0c;如下图2.在新建工程界面左侧&#xff0c…...

《程序员成长历程的四个阶段》

阶段一&#xff1a;不知道自己不知道(Unconscious incompetence) 大学期间&#xff0c;我和老师做过一些小项目&#xff0c;自认为自己很牛&#xff0c;当时还去过一些公司面试做兼职&#xff0c;但是就是不知道为什么没有回复。那个时期的我&#xff0c;压根不知道自己不知道&…...

【SpringBoot】Spring data JPA的多数据源实现

一、主流的多数据源支持方式 将数据源对象作为参数&#xff0c;传递到调用方法内部&#xff0c;这种方式增加额外的编码。将Repository操作接口分包存放&#xff0c;Spring扫描不同的包&#xff0c;自动注入不同的数据源。这种方式实现简单&#xff0c;也是一种“约定大于配置…...

uni-app基础知识介绍

uni-app的基础知识介绍 1、在第一次将代码运行在微信开发者工具的时候&#xff0c;应该进行如下的配置: &#xff08;1&#xff09;将微信开发者工具路径进行配置&#xff1b; [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lbyk5Jw2-16790251840…...

Word2010(详细布局解释)

目录一、界面介绍二、选项卡1、文件选项卡&#xff08;保存、打开、新建、打印、保存并发送、选项&#xff09;2、开始选项卡&#xff08;剪贴板、字体、段落、样式、编辑&#xff09;3、插入选项卡&#xff08;页、表格、插图、链接、页眉页脚、文本、符号&#xff09;4、页面…...

Spring如何实现Quartz的自动配置

Spring如何实现Quartz的自动配置1. 开启Quartz自动配置2. Quartz自动配置的实现过程2.1 核心类图2.2 核心方法3. 任务调度执行3.1 大致流程3.2 调整线程池的大小如果想在应用中使用Quartz任务调度功能&#xff0c;可以通过Spring Boot实现Quartz的自动配置。以下介绍如何开启Qu…...

计算机组成原理——作业四

一. 单选题&#xff08;共11题&#xff0c;33分&#xff09; 1. (单选题, 3分)四片74181 ALU和一片74182 CLA器件相配合,具有如下进位传递功能:________。 A. 行波进位B. 组内先行进位,组间行波进位C. 组内先行进位,组间先行进位D. 组内行波进位,组间先行进位 我的答案: C 3…...

2023前端面试题(经典面试题)

经典面试题Vue2.0 和 Vue3.0 有什么区别&#xff1f;vue中计算属性和watch以及methods的区别&#xff1f;单页面应用和多页面应用区别及优缺点&#xff1f;说说 Vue 中 CSS scoped 的原理&#xff1f;谈谈对Vue中双向绑定的理解&#xff1f;为什么vue2和vue3语法不可以混用&…...

【Linux内网穿透】使用SFTP工具快速实现内网穿透

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

SQL语句性能分析

1. 数据库服务器的优化步骤 当我们遇到数据库调优问题的时候&#xff0c;该如何思考呢&#xff1f;这里把思考的流程整理成下面这张图。 整个流程划分成了 观察&#xff08;Show status&#xff09; 和 行动&#xff08;Action&#xff09; 两个部分。字母 S 的部分代表观察&…...

【K3s】第28篇 详解 k3s-killall.sh 脚本

目录 k3s-killall.sh 脚本 k3s-killall.sh 脚本 为了在升级期间实现高可用性&#xff0c;当 K3s 服务停止时&#xff0c;K3s 容器会继续运行。 要停止所有的 K3s 容器并重置容器的状态&#xff0c;可以使用k3s-killall.sh脚本。 killall 脚本清理容器、K3s 目录和网络组件&a…...

生成时序异常样本-学习记录-未完待续

1.GAN&VAE&#xff5c;时间序列生成及异常注入那些事儿&#xff1a;主要讲了数据增广&#xff0c;用GAN、WGAN、DCGAN、VAE&#xff0c;有给几个代码的github的链接&#xff0c;非常有用 2.时序异常检测综述&#xff0c;写的非常好 3.自编码器原理讲解&#xff0c;后面还附…...

自定义类型的超详细讲解ᵎᵎ了解结构体和位段这一篇文章就够了ᵎ

目录 1.结构体的声明 1.1基础知识 1.2结构体的声明 1.3结构体的特殊声明 1.4结构体的自引用 1.5结构体变量的定义和初始化 1.6结构体内存对齐 那对齐这么浪费空间&#xff0c;为什么要对齐 1.7修改默认对齐数 1.8结构体传参 2.位段 2.1什么是位段 2.2位段的内存分配…...

【五】springboot启动源码 - onRefresh

onRefresh 源码解析 Initialize other special beans in specific context subclasses. 核心是创建一个web服务容器&#xff08;并未在这个方法启动&#xff09; createWebServer第182行&#xff0c;获取ServletWebServerFactory的具体实现 getWebServerFactory方法&#xff…...

带你一文透彻学习【PyTorch深度学习实践】分篇——线性回归(训练周期:前馈、反馈、权重更新)

“梦想使你迷醉,距离就成了快乐;追求使你充实,失败和成功都是伴奏;当生命以美的形式证明其价值的时候,幸福是享受,痛苦也是享受。” --------史铁生《好运设计》 🎯作者主页:追光者♂🔥 🌸个人简介:计算机专业硕士研究生💖、2022年CSDN博客之星人工…...

【前端八股文】浏览器系列:性能优化——HTML、CSS、JS、渲染优化

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

Linux分文件编程:静态库与动态库的生成和使用

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

技术人的管理学-业务管理

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

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 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 是德州仪器&#xff08;TI&#xff09;推出的一款 汽车级同步降压转换器&#xff08;DC-DC开关稳压器&#xff09;&#xff0c;属于高性能电源管理芯片。核心特性包括&#xff1a; 输入电压范围&#xff1a;2.95V–6V&#xff0c;输…...

2.2.2 ASPICE的需求分析

ASPICE的需求分析是汽车软件开发过程中至关重要的一环&#xff0c;它涉及到对需求进行详细分析、验证和确认&#xff0c;以确保软件产品能够满足客户和用户的需求。在ASPICE中&#xff0c;需求分析的关键步骤包括&#xff1a; 需求细化&#xff1a;将从需求收集阶段获得的高层需…...

2025.6.9总结(利与弊)

凡事都有两面性。在大厂上班也不例外。今天找开发定位问题&#xff0c;从一个接口人不断溯源到另一个 接口人。有时候&#xff0c;不知道是谁的责任填。将工作内容分的很细&#xff0c;每个人负责其中的一小块。我清楚的意识到&#xff0c;自己就是个可以随时替换的螺丝钉&…...

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███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...