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:
# 大体过程如下:
1.定义一个变量`n`表示力场数量,初始化为`forceField`的长度。
2.创建两个空数组`xs`和`ys`,长度为`n*2`,用于存储力场覆盖区域的边界坐标。
3.遍历`forceField`,对于每个力场,将其中心坐标以及边长转换成边界坐标,并保存到`xs`和`ys`中。
4.对`xs`和`ys`进行排序。
5.去除`xs`和`ys`中的重复元素,并分别记录剩余元素的数量,得到`sizex`和`sizey`。
6.创建二维数组`diff`,大小为`(sizex+2) x (sizey+2)`,用于记录每个力场的覆盖数量。
7.遍历`forceField`,对于每个力场,找到其在`xs`和`ys`中对应的边界索引,并根据索引更新`diff`数组。
8.初始化变量`ans`为0,用于记录最大的力场强度。
9.使用动态规划的思想,从`diff[1][1]`开始遍历`diff`数组,依次计算每个位置的力场强度,并更新`ans`。
10.返回`ans`作为最大的力场强度。
总的时间复杂度:O(nlogn),其中n为力场数量,排序的时间复杂度为O(nlogn)。
总的额外空间复杂度:O(n),存储了`xs`和`ys`数组。
# go完整代码如下:
```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)
}
```