2024-01-20：用go語(yǔ)言，小扣在探索叢林的過程中，無(wú)意間發(fā)現(xiàn)了傳說(shuō)中"落寞的黃金之都"，

而在這片建筑廢墟的地帶中，小扣使用探測(cè)儀監(jiān)測(cè)到了存在某種帶有「祝福」效果的力場(chǎng)，

經(jīng)過不斷的勘測(cè)記錄，小扣將所有力場(chǎng)的分布都記錄了下來(lái)，

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

表示第 i 片力場(chǎng)將覆蓋以坐標(biāo) (x,y) 為中心，邊長(zhǎng)為 side 的正方形區(qū)域。

若任意一點(diǎn)的 力場(chǎng)強(qiáng)度 等于覆蓋該點(diǎn)的力場(chǎng)數(shù)量。

請(qǐng)求出在這片地帶中 力場(chǎng)強(qiáng)度 最強(qiáng)處的 力場(chǎng)強(qiáng)度。

注意：力場(chǎng)范圍的邊緣同樣被力場(chǎng)覆蓋。

輸入： forceField = [[0,0,1],[1,0,1]]。

輸出：2。

來(lái)自lc的LCP 74. 最強(qiáng)祝福力場(chǎng)。

答案2024-01-20：

來(lái)自左程云。

靈捷3.5

大體過程如下：

1.定義一個(gè)變量n表示力場(chǎng)數(shù)量，初始化為forceField的長(zhǎng)度。

2.創(chuàng)建兩個(gè)空數(shù)組xs和ys，長(zhǎng)度為n*2，用于存儲(chǔ)力場(chǎng)覆蓋區(qū)域的邊界坐標(biāo)。

3.遍歷forceField，對(duì)于每個(gè)力場(chǎng)，將其中心坐標(biāo)以及邊長(zhǎng)轉(zhuǎn)換成邊界坐標(biāo)，并保存到xs和ys中。

4.對(duì)xs和ys進(jìn)行排序。

5.去除xs和ys中的重復(fù)元素，并分別記錄剩余元素的數(shù)量，得到sizex和sizey。

6.創(chuàng)建二維數(shù)組diff，大小為(sizex+2) x (sizey+2)，用于記錄每個(gè)力場(chǎng)的覆蓋數(shù)量。

7.遍歷forceField，對(duì)于每個(gè)力場(chǎng)，找到其在xs和ys中對(duì)應(yīng)的邊界索引，并根據(jù)索引更新diff數(shù)組。

8.初始化變量ans為0，用于記錄最大的力場(chǎng)強(qiáng)度。

9.使用動(dòng)態(tài)規(guī)劃的思想，從diff[1][1]開始遍歷diff數(shù)組，依次計(jì)算每個(gè)位置的力場(chǎng)強(qiáng)度，并更新ans。

10.返回ans作為最大的力場(chǎng)強(qiáng)度。

總的時(shí)間復(fù)雜度：O(nlogn)，其中n為力場(chǎng)數(shù)量，排序的時(shí)間復(fù)雜度為O(nlogn)。

總的額外空間復(fù)雜度：O(n)，存儲(chǔ)了xs和ys數(shù)組。

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)
}

總結(jié)

以上是生活随笔為你收集整理的2024-01-20：用go语言，小扣在探索丛林的过程中，无意间发现了传说中“落寞的黄金之都“， 而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场， 经过不断的勘测记录，的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。