leetcode第259场周赛前三题,GO语言解法

2023-10-28 16:48

本文主要是介绍leetcode第259场周赛前三题,GO语言解法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第一次打周赛,时间把握不住,只做出来前三题,并且第三题是比赛结束后才做出来的。现在比赛结束了,记录一下做题代码和一些关键的思想。同样的解题笔记已经在leetcode解题发表过了。

由于第四题是困难题,不会做也不是很想做,就放弃了,等我真的有实力了再试试吧。

所有代码同时也会放入码云中:https://gitee.com/sampsontse/leetcode-golang

求一个star!

第一题:执行操作后的变量值

题目:存在一种仅支持 4 种操作和 1 个变量 X 的编程语言:

++X 和 X++ 使变量 X 的值 加 1
--X 和 X-- 使变量 X 的值 减 1
最初,X 的值是 0

给你一个字符串数组 operations ,这是由操作组成的一个列表,返回执行所有操作后, X 的 最终值 。

例子:

输入:operations = ["--X","X++","X++"]
输出:1
解释:操作按下述步骤执行:
最初,X = 0
--X:X 减 1 ,X =  0 - 1 = -1
X++:X 加 1 ,X = -1 + 1 =  0
X++:X 加 1 ,X =  0 + 1 =  1

思路:这题有点简单的过分,感觉就是给个参与分。因为只有四个操作,那么使用map[string]int来记录四个操作的string,++X和X++的int为1,--X和X--的int为-1。

func finalValueAfterOperations(operations []string) int {opera := map[string]int{"X++": 1,"++X": 1,"--X": -1,"X--": -1,}x := 0for _, v := range operations {if i, ok := opera[v]; ok {x = x + i}}return x
}

第二题:数组美丽值求和

题目:给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i(1 <= i <= nums.length - 2),nums[i] 的 美丽值 等于:

  • 2,对于所有 0 <= j < i 且 i < k <= nums.length - 1 ,满足 nums[j] < nums[i] < nums[k]
  • 1,如果满足 nums[i - 1] < nums[i] < nums[i + 1] ,且不满足前面的条件
  • 0,如果上述条件全部不满足

返回符合 1 <= i <= nums.length - 2 的所有 nums[i] 的 美丽值的总和 。

例子:

输入:nums = [1,2,3]
输出:2
解释:对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 2

思路1:暴力求解,这里时间会超时

思路2:新建两个长度和nums一样数组:pre和suf,分别记录以nums[i]结尾的最大值和以nums[i]开头的最小值,然后通过 nums[i]是否大于pre[i-1]并且nums[i]是否小于suf[i+1] 这个条件来判断漂亮值是否为2;如果不为2,判断nums[i-1]<nums[i]<num[i+1]来判断漂亮值是否为1。

func SumOfBeauties(nums []int) int {total := 0n := len(nums)pre := make([]int, n)suf := make([]int, n)pre[0] = nums[0]suf[n-1] = nums[n-1]for i := 1; i < n; i++ {if pre[i-1] < nums[i] {pre[i] = nums[i]} else {pre[i] = pre[i-1]}}for i := n - 2; i >= 0; i-- {if nums[i] < suf[i+1] {suf[i] = nums[i]} else {suf[i] = suf[i+1]}}fmt.Println(pre)fmt.Println(suf)for i := 1; i <= n-2; i++ {if pre[i-1] < nums[i] && nums[i] < suf[i+1] {total += 2} else if nums[i-1] < nums[i] && nums[i] < nums[i+1] {total++}}return total
}

第三题:检测正方形

题目:

给你一个在 X-Y 平面上的点构成的数据流。设计一个满足下述要求的算法:

添加 一个在数据流中的新点到某个数据结构中。可以添加 重复 的点,并会视作不同的点进行处理。
给你一个查询点,请你从数据结构中选出三个点,使这三个点和查询点一同构成一个 面积为正 的 轴对齐正方形 ,统计 满足该要求的方案数目。
轴对齐正方形 是一个正方形,除四条边长度相同外,还满足每条边都与 x-轴 或 y-轴 平行或垂直。

实现 DetectSquares 类:

DetectSquares() 使用空数据结构初始化对象
void add(int[] point) 向数据结构添加一个新的点 point = [x, y]
int count(int[] point) 统计按上述方式与点 point = [x, y] 共同构造 轴对齐正方形 的方案数。

实例:

关键思路
通过map[int]map[int]int来保存每个坐标下点的位置
第一个key表示x轴
第二个key表示y轴
map[x][y]来表示这里点的个数

例子:
假设传入的点为point1(x,y)

通过map查找x相同y不同的节点位置point2(x,y2),计算两个节点之间的距离distance=|y-y2|
查找point左边是否存在点point3(x-distance,y)和point4是否存在点point4(x-distance,y2)
如果point3和point4都存在点,那么可以构成正方形的个数为point2的个数 * point3的个数 * point4的个数

type DetectSquares struct {table map[int]map[int]int
}func Constructor() DetectSquares {return DetectSquares{table: map[int]map[int]int{},}
}func (this *DetectSquares) Add(point []int) {x, y := point[0], point[1]if _, ok1 := this.table[x]; ok1 {if _, ok2 := this.table[x][y]; ok2 {this.table[x][y]++} else {this.table[x][y] = 1}} else {this.table[x] = map[int]int{}this.table[x][y] = 1}
}func (this *DetectSquares) Count(point []int) int {x, y := point[0], point[1]res := 0if yMap, ok := this.table[x]; ok {for y1 := range yMap {if y1 == y {continue}var distance intdistance = y1 - yif distance < 0 {distance = -distance}// 左边if _, ok1 := this.table[x-distance]; ok1 {countY2, ok2 := this.table[x-distance][y]  // 传入点的左边的个数countY3, ok3 := this.table[x-distance][y1] // 与传入点同一个纵轴的左边的个数if ok2 && ok3 {res += this.table[x][y1] * countY2 * countY3}}// 右边if _, ok1 := this.table[x+distance]; ok1 {countY2, ok2 := this.table[x+distance][y]  // 传入点的右边的个数countY3, ok3 := this.table[x+distance][y1] // 与传入点同一个纵轴的右边的个数if ok2 && ok3 {res += this.table[x][y1] * countY2 * countY3}}}}return res
}

最后:

所有题目来自于leetcode第239场周赛

这篇关于leetcode第259场周赛前三题,GO语言解法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/294570

相关文章

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》:本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

go 指针接收者和值接收者的区别小结

《go指针接收者和值接收者的区别小结》在Go语言中,值接收者和指针接收者是方法定义中的两种接收者类型,本文主要介绍了go指针接收者和值接收者的区别小结,文中通过示例代码介绍的非常详细,需要的朋友们下... 目录go 指针接收者和值接收者的区别易错点辨析go 指针接收者和值接收者的区别指针接收者和值接收者的

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

go中空接口的具体使用

《go中空接口的具体使用》空接口是一种特殊的接口类型,它不包含任何方法,本文主要介绍了go中空接口的具体使用,具有一定的参考价值,感兴趣的可以了解一下... 目录接口-空接口1. 什么是空接口?2. 如何使用空接口?第一,第二,第三,3. 空接口几个要注意的坑坑1:坑2:坑3:接口-空接口1. 什么是空接

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件