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 main

import "fmt"

func searchRange(nums []int, target int) []int {
	left, right := -1, -1
	// 查找左边界
	l, r := 0, len(nums)-1
	for l <= r {
		mid := (l + r) / 2
		if nums[mid] == target {
			left = mid
			r = 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)-1
	for l <= r {
		mid := (l + r) / 2
		if nums[mid] == target {
			right = mid
			l = 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 main

import "fmt"

func searchInsert(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for l <= r {
		mid := (l + r) / 2
		if 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 main

import "fmt"

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
}

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 main

import "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] = true
			cols[j][num] = true
			boxs[(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 main

import (
	"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每日一练 专栏

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

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

相关文章

VsCode SSH远程连接服务器【内网穿透公网连接】

VsCode SSH远程连接服务器【内网穿透公网连接】

文章目录1.前言2.VS code的安装和设置2.1 VS code的下载安装2.2 OpenSSH的启用2.3 为VS code配置ssh2.4 局域网内测试VS code的ssh连接2.5 Cpolar下载安装3.Cpolar端口设置3.1 Cpolar云端设置3.2 Cpolar本地设置4.公网访问测试5.结语1.前言 记得笔者小时候看电视&#xff0c;看…
阅读更多...
【安全与风险】密码学介绍

【安全与风险】密码学介绍

密码学介绍密码历史密码换位&#xff08;Transposition&#xff09;与置换&#xff08;Substitution&#xff09;替换密码&#xff08;Substiution Cipher&#xff09;凯撒密码 &#xff08;100BC 公元前100年&#xff09;移位密码破坏替换密码维吉尼亚密码现代密码学核心原理从…
阅读更多...
TCP三次握手/四次挥手

TCP三次握手/四次挥手

TCP三次握手 任何基于TCP的应用&#xff0c;在发送数据之前&#xff0c;都需要由TCP进行“三次握手”建立连接示意图 第一次握手&#xff1a;客户端PC发送一个SYN位置1&#xff08;SYN1代表请求服务端建立连接&#xff09;的TCP报文发送给要建立TCP连接的Server&#xff0c;此…
阅读更多...
23种设计模式

23种设计模式

参考链接&#xff1a; 【狂神说Java】通俗易懂的23种设计模式教学&#xff08;停更&#xff09;_哔哩哔哩_bilibili 23种设计模式【狂神说】_狂神说设计模式_miss_you1213的博客-CSDN博客 1. 单例模式 参考链接&#xff1a; 【狂神说Java】单例模式-23种设计模式系列_哔哩哔哩…
阅读更多...
Linux(网络基础---网络层)

Linux(网络基础---网络层)

文章目录0. 前言1. IP协议1-1 基本概念1-2 协议头格式2. 网段划分2-1 基本概念2.2 IP地址分五大类2-3 特殊的IP地址2-4 IP地址的数量限制2-5 私有IP地址和公网IP地址2-6 路由0. 前言 前面我们讲了&#xff0c;应用层、传输层&#xff1b;本章讲网络层。 应用层&#xff1a;我…
阅读更多...
GPT-4是个编程高手，真服了！

GPT-4是个编程高手，真服了！

上周给大家发了一个GPT-4教数学的介绍&#xff0c;很多人都被震撼了&#xff0c;感觉有可能在教育行业引发革命。它在编程领域表现如何&#xff1f;先不说能否替代程序员&#xff0c;这个还有待更多的测试和反馈&#xff0c;我想先试试它能不能像教数学那样教编程。我找了个Jav…
阅读更多...
Docker的可视化界面工具

Docker的可视化界面工具

Docker的可视化界面工具1. Portainer1.1 Introduction1.1.1 Official1.2 Download And Deploy1.3 Dashboard1.3.1 Dashboard2. Shipyard2.1 Introduction2.1.1 Character2.1.2 Official2.2 Download And Deploy2.2.1 脚本下载镜像2.2.2 执行脚本2.2.2 查看下载的镜像2.3 Dashbo…
阅读更多...
“工作三年，跳槽要求涨薪50%”，合理吗？

“工作三年，跳槽要求涨薪50%”，合理吗？

如果问在TI行业涨工资最快的方式是什么&#xff1f;回答最多的一定是&#xff1a;跳槽&#xff01;前段时间&#xff0c;知乎上这样一条帖子引发了不少IT圈子的朋友的讨论 &#xff0c;有网友提问 “程序员跳槽要求涨薪50%过分吗&#xff1f;”截图来源于知乎&#xff0c;如侵删…
阅读更多...
【百面成神】多线程基础16问，你能坚持到第几问

【百面成神】多线程基础16问，你能坚持到第几问

前 言 &#x1f349; 作者简介&#xff1a;半旧518&#xff0c;长跑型选手&#xff0c;立志坚持写10年博客&#xff0c;专注于java后端 ☕专栏简介&#xff1a;纯手打总结面试题&#xff0c;自用备用 &#x1f330; 文章简介&#xff1a;多线程最基础、重要的16道面试题 文章目…
阅读更多...
【百面成神】Redis基础11问，你能坚持到第几问

【百面成神】Redis基础11问，你能坚持到第几问

前 言 &#x1f349; 作者简介&#xff1a;半旧518&#xff0c;长跑型选手&#xff0c;立志坚持写10年博客&#xff0c;专注于java后端 ☕专栏简介&#xff1a;纯手打总结面试题&#xff0c;自用备用 &#x1f330; 文章简介&#xff1a;Redis最基础、重要的11道面试题 文章目录…
阅读更多...
AI 未来已至，向量数据库站在新的节点上

AI 未来已至，向量数据库站在新的节点上

“AI 的 iPhone 时刻已经到来。” 在刚刚结束的 NVIDIA GTC Keynote 中&#xff0c;这句话被 NVIDIA CEO 黄仁勋反复提及&#xff0c;长达 1 个多小时的分享中&#xff0c;生成式 AI 相关的内容占据了绝大部分比重。他表示&#xff0c;生成式 AI 的火热能力为企业带来了挑战&a…
阅读更多...
2022/3/22 从CV方向角度 —快速解读Nvidia 2023GTC

2022/3/22 从CV方向角度 —快速解读Nvidia 2023GTC

GTC分享内容和个人看法 3月21号11点&#xff0c;Nvidia开启了GTC主题演讲&#xff0c;这些年英伟达加速库的发展和对AI的投入应用&#xff0c;不难看出掌握GPU加速计算技术的N家肯定是宣扬AI方向的产品和生产工具&#xff0c;下面我将简要汇总下演讲的内容&#xff0c;和从我自…
阅读更多...
Java语言-----类与对象的秘密

Java语言-----类与对象的秘密

目录 前言 一、类与对象的介绍 二、类的实例化 三.类与对象的使用方法 3.1对象的初始化 3.2内存显示图 四.this的使用方法 总结 &#x1f63d;个人主页&#xff1a; tq02的博客_CSDN博客-C语言,Java领域博主 &#x1f308;理想目标&#xff1a;努力学习&#xff0c;向Java进…
阅读更多...
修改linux网卡配置文件的文件名

修改linux网卡配置文件的文件名

修改linux网卡配置文件的文件名 查看自己系统中网卡配置文件的文件名 #查看网卡的配置文件名&#xff0c;已经网络的状态 ip a查看系统是否可以使用ifconfig命令 #输入命令 ifconfig #出现以下图片表示ifconfig的命令可用。可能出现的错误&#xff1a;ifconfig command no foun…
阅读更多...
第十七天 JavaScript、Vue详细总结

第十七天 JavaScript、Vue详细总结

目录 JavaScript、Vue 1. JavaScript常用对象 1.1 Array对象 1.2 String对象 1.3 自定义对象 1.4 JSON 1.5 BOM 1.6 DOM 2. 事件监听 2.1 事件绑定 2.2 常见事件 2.3 案例 3. Vue 3.1 概述 3.2 快速入门 3.3 常用指令 3.4 生命周期 JavaScript、Vue 今日目标&…
阅读更多...
为什么说网络安全是风口行业？是IT行业最后的红利？

为什么说网络安全是风口行业？是IT行业最后的红利？

前言 “没有网络安全就没有国家安全”。当前&#xff0c;网络安全已被提升到国家战略的高度&#xff0c;成为影响国家安全、社会稳定至关重要的因素之一。 网络安全行业特点 1、就业薪资非常高&#xff0c;涨薪快 2021年猎聘网发布网络安全行业就业薪资行业最高人均33.77万&…
阅读更多...
2023年2月用户体验GX评测：国有行及股份行持续领跑，农商行农信社积极探索用户体验提升

2023年2月用户体验GX评测：国有行及股份行持续领跑，农商行农信社积极探索用户体验提升

易观&#xff1a;2023年2月易观千帆用户体验GX评测显示&#xff0c;国有行及股份制银行继续领跑手机银行用户体验&#xff0c;平安口袋银行、中国工商银行、招商银行稳居AAAAA级&#xff1b;城商行、农商行、农信社重视用户体验&#xff0c;银行下一步重点依然是狠抓用户体验建…
阅读更多...
【java基础】Stream流的各种操作

【java基础】Stream流的各种操作

文章目录基本介绍流的创建流的各种常见操作forEach方法filter方法map方法peek方法flatMap方法limit和skip方法distinct方法sorted方法收集结果收集为数组&#xff08;toArray&#xff09;收集为集合&#xff08;collect&#xff09;收集为Map关于流的一些说明&#xff08;终结操…
阅读更多...
WEB网站服务（一）

WEB网站服务（一）

1.1 Apache网站服务基础1.1.1Apache简介Apache HTTP Server是开源软件项目的杰出代表&#xff0c;基于标准的HTTP网络协议提供网页浏览服务。Apache服务器可以运行在Linux,UNIX&#xff0c;windows等多种操作系统平台中。1.Apache的起源1995年&#xff0c;Apache服务程序的1.0版…
阅读更多...
Linux- 系统随你玩之--玩出花活的命令浏览器-双生姐妹花

Linux- 系统随你玩之--玩出花活的命令浏览器-双生姐妹花

文章目录1、背景2、命令浏览器-双生姐妹花2.1、姐妹花简介2.2 、验名正身2.3、常用功能选项3、常用实操3.1、发送请求获取文件3.1.1、抓取页面内容到一个文件中3.1.2、多个文件下载3.1.3、下载ftp文件3.1.4、断点续传3.1.5、上传文件3.1.6、内容输出3.2 、利用curl测试接口3.3 …
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站