2024-01-20:用go语言,小扣在探索丛林的过程中,无意间发现了传说中

2024-01-20:用go语言,小扣在探索丛林的过程中,无意间发现了传说中”落寞的黄金之都”,

而在这片建筑废墟的地带中,小扣使用探测仪监测到了存在某种带有「祝福」效果的力场,

经过不断的勘测记录,小扣将所有力场的分布都记录了下来,

forceField[i] = [x,y,side] ,

表示第 i 片力场将覆盖以坐标 (x,y) 为中心,边长为 side 的正方形区域。

若任意一点的 力场强度 等于覆盖该点的力场数量。

请求出在这片地带中 力场强度 最强处的 力场强度。

注意:力场范围的边缘同样被力场覆盖。

输入: forceField = [[0,0,1],[1,0,1]]。

输出:2。

来自lc的LCP 74. 最强祝福力场。

答案2024-01-20:

来自左程云

灵捷3.5

大体过程如下:

1.定义一个变量n表示力场数量,初始化为forceField的长度。

2.创建两个空数组xsys,长度为n*2,用于存储力场覆盖区域的边界坐标。

3.遍历forceField,对于每个力场,将其中心坐标以及边长转换成边界坐标,并保存到xsys中。

4.对xsys进行排序。

5.去除xsys中的重复元素,并分别记录剩余元素的数量,得到sizexsizey

6.创建二维数组diff,大小为(sizex+2) x (sizey+2),用于记录每个力场的覆盖数量。

7.遍历forceField,对于每个力场,找到其在xsys中对应的边界索引,并根据索引更新diff数组。

8.初始化变量ans为0,用于记录最大的力场强度。

9.使用动态规划的思想,从diff[1][1]开始遍历diff数组,依次计算每个位置的力场强度,并更新ans

10.返回ans作为最大的力场强度。

总的时间复杂度:O(nlogn),其中n为力场数量,排序的时间复杂度为O(nlogn)。

总的额外空间复杂度:O(n),存储了xsys数组。

go完整代码如下:

package main

import (
    "fmt"
    "sort"
)

func fieldOfGreatestBlessing(forceField [][]int) int {
    n := len(forceField)
    xs := make([]int64, n*2)
    ys := make([]int64, n*2)
    for i := 0; i < n; i++ {
        x := int64(forceField[i][0])
        y := int64(forceField[i][1])
        r := int64(forceField[i][2])
        xs[i*2] = (x << 1) - r
        xs[i*2+1] = (x << 1) + r
        ys[i*2] = (y << 1) - r
        ys[i*2+1] = (y << 1) + r
    }
    sort.Slice(xs, func(i, j int) bool { return xs[i] < xs[j] })
    sort.Slice(ys, func(i, j int) bool { return ys[i] < ys[j] })
    sizex := removeDuplicates(xs)
    sizey := removeDuplicates(ys)
    diff := make([][]int, sizex+2)
    for i := range diff {
        diff[i] = make([]int, sizey+2)
    }
    for i := 0; i < n; i++ {
        x := int64(forceField[i][0])
        y := int64(forceField[i][1])
        r := int64(forceField[i][2])
        a := binarySearch(xs, (x<<1)-r)
        b := binarySearch(ys, (y<<1)-r)
        c := binarySearch(xs, (x<<1)+r)
        d := binarySearch(ys, (y<<1)+r)
        set(diff, a, b, c, d)
    }
    ans := 0
    for i := 1; i < len(diff); i++ {
        for j := 1; j < len(diff[0]); j++ {
            diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]
            ans = max(ans, diff[i][j])
        }
    }
    return ans
}

func removeDuplicates(nums []int64) int {
    size := 1
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[size-1] {
            nums[size] = nums[i]
            size++
        }
    }
    return size
}

func binarySearch(nums []int64, v int64) int {
    l, r := 0, len(nums)-1
    var m, ans int
    for l <= r {
        m = (l + r) / 2
        if nums[m] >= v {
            ans = m
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return ans + 1
}

func set(diff [][]int, a, b, c, d int) {
    diff[a][b] += 1
    diff[c+1][d+1] += 1
    diff[c+1][b] -= 1
    diff[a][d+1] -= 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    forceField := [][]int{{0, 0, 1}, {1, 0, 1}}
    result := fieldOfGreatestBlessing(forceField)
    fmt.Println(result)
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
455
粉丝
21
喜欢
37
收藏
22
排名:465
访问:1.9 万
私信
所有博文
社区赞助商