前言
https://leetcode-cn.com/contest/weekly-contest-284
第一次做力扣的周赛，一共4题写出3题，感觉第四题是可以做出来的，但是大一用的是c++写spfa最短路，周赛的时候都忘了，最后通过看以前的模板补上了，现在看看hard题还是挺简单的，题目描述很垃圾，令人费解。
令人惊喜的是，4题居然都是双一百，离谱
第一题
6031.找出数组中的所有K近邻下标
6031.找出数组中的所有K近邻下标
题解
简单题，，就按照题目写代码即可
代码
func findKDistantIndices(nums []int, key int, k int) (ans []int) { mp := make(map[int]int) for i, v := range nums { if v == key { mp[i] = v } } for i, _ := range nums { for mpK := range mp { if abs(i, mpK) <= k { ans = append(ans, i) break } } } return } func abs(i, j int) int { if i-j > 0 { return i - j } return j - i }
第二题
2201.统计可以提取的工件
2201.统计可以提取的工件
题解
中等题，其实也是简单题，其实一共就4中情况，上下n个，左右n个，1个，正方形4个，if判断一下即可
代码
func digArtifacts(n int, artifacts [][]int, dig [][]int) (ans int) { a := make([][]int, n) for i := range a { a[i] = make([]int, n) } for _, v := range dig { x, y := v[0], v[1] a[x][y]++ } for _, v := range artifacts { x1, y1 := v[0], v[1] x2, y2 := v[2], v[3] if x1 == x2 && y1 == y2 { //1 if a[x1][y1] > 0 { ans++ } } else if x1 != x2 && y1 == y2 { //左右 n f := true for i := x1; i <= x2; i++ { if a[i][y1] == 0 { f = false break } } if f{ ans++ } } else if x1 == x2 && y1 != y2 { //上下 n f := true for i := y1; i <= y2; i++ { if a[x1][i] == 0 { f = false break } } if f{ ans++ } } else if x1 != x2 && y1 != y2 { //4 if a[x1][y1] > 0 && a[x2][y2] > 0 && a[x1][y2] > 0 && a[x2][y1] > 0 { ans++ } } } return ans }
第三题
5227.K次操作后最大化顶端元素
5227.K次操作后最大化顶端元素
题解
贪心，第一眼就是贪心，后面想着要不用dfs试试？发现dfs涉及到回溯的状态，太过复杂，而且是中等题，应该是贪心
只有一个数字，并且k是奇数，则不能放回，即-1 只有一个数字，k是偶数，或者k=0，那么就是这个数字 k=1且len>1，只能移除第一个，则答案就是第二个 如果k小于总个数，则能够遍历到的是0~k-2（移除+放回）和 k（前k个全移除） 如果k等于总个数，则能够遍历到的是0~k-2（移除+放回），不能移除前k个，不然slice就是空了 如果k大于总个数，那么每个都可以遍历到
代码
func maximumTop(nums []int, k int) (ans int) { if len(nums) == 1 && k%2 == 1 {//只有一个数字，并且k是奇数，则不能放回，即-1 return -1 } if len(nums) == 1 && k%2 == 0 || k == 0 {//只有一个数字，k是偶数，或者k=0，那么就是这个数字 return nums[0] } if len(nums) >= 2 && k == 1 {//k=1，只能移除第一个，则答案就是第二个 return nums[1] } if len(nums) > k {//如果k小于总个数，则能够遍历到的是0~k-2（移除+放回）和 k（前k个全移除） for i := 0; i <= k-2; i++ { ans = max(ans, nums[i]) } return max(ans, nums[k]) } if len(nums) == k {//如果k等于总个数，则能够遍历到的是0~k-2（移除+放回），不能移除前k个，不然slice就是空了 for i := 0; i <= k-2; i++ { ans = max(ans, nums[i]) } return ans } if k > len(nums) {//如果k大于总个数，那么每个都可以遍历到 for i := 0; i <= len(nums)-1; i++ { ans = max(ans, nums[i]) } return ans } return } func max(i, j int) int { if i > j { return i } return j }
第四题
2203.得到要求路径的最小带权子图
2203.得到要求路径的最小带权子图
题解
题目描述真的很烂，其实就是给3个点 src1 ，src2 和 dest，求src1能够到达dest，并且src2能够达到dest的两条线路加一起的最小边权。
思路就是，src1跑一遍spfa，则src1到各个点的距离都出来了，src2同理，dest跑反图，即a->b变成a<-b，如果src1和src2到了某一个点，如果某一个点可以到达dest，则就节省了一段路程，即求src1->x +src2->x + dest->x的最小距离，其实如果没有公共点,那么公共点就是dest，即src1->dest+src2->dest,思路其实很清晰，对于写过最短路的来说，这题hard题不算难，但是样例有点坑的，数据规模很大，我之前用INF都是0x3f3f3f3f，没想到会超过这个数值，并且边最大是10的5次乘以10的5次，所以要用链式向前星去存，不能看二维矩阵，不然就oom了
代码
type node struct { v, w int } func minimumWeight(n int, edges [][]int, src1 int, src2 int, dest int) int64 { e := make([][]node, n) eR := make([][]node, n) for _, edge := range edges { u, v, w := edge[0], edge[1], edge[2] e[u] = append(e[u], node{v, w}) eR[v] = append(eR[v], node{u, w}) } INF := math.MaxInt64 var SPFA func(e [][]node, s int) []int SPFA = func(e [][]node, s int) []int { dst := make([]int, n) vis := make([]int, n) for i := range dst { dst[i] = INF } dst[s] = 0 queue := make([]node, 0) queue = append(queue, node{s, 0}) for len(queue) > 0 { u := queue[0].v queue = queue[1:] vis[u] = 0 for _, nodeV := range e[u] { v, w := nodeV.v, nodeV.w if dst[v] > dst[u]+w { dst[v] = dst[u] + w if vis[v] == 0 { queue = append(queue, node{v, dst[v]}) vis[v] = 1 } } } } return dst } s1 := SPFA(e, src1) s2 := SPFA(e, src2) s3 := SPFA(eR, dest) for i := 0; i < n; i++ { if s1[i] != math.MaxInt64 && s2[i] != math.MaxInt64 && s3[i] != math.MaxInt64 { INF = min(INF, s1[i]+s2[i]+s3[i]) } } if INF == math.MaxInt64 { return -1 } return int64(INF) } func min(i, j int) int { if i < j { return i } return j }
