当前位置: 首页 > 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;他们既需要系统的管理知识&#…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...