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

本文主要是介绍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语言解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---