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

相关文章

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. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

Golang基于内存的键值存储缓存库go-cache

《Golang基于内存的键值存储缓存库go-cache》go-cache是一个内存中的key:valuestore/cache库,适用于单机应用程序,本文主要介绍了Golang基于内存的键值存储缓存库... 目录文档安装方法示例1示例2使用注意点优点缺点go-cache 和 Redis 缓存对比1)功能特性