未分類

Heaters

BinarySearch, Go, LeetCode

Heaters

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

  1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
  2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
  3. As long as a house is in the heaters’ warm radius range, it can be warmed.
    All the heaters follow your radius standard and the warm radius will the same.

Example 1:

1
2
3
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

1
2
3
Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.
提示 解題應用
BinarySearch 改用Sort

Default:

1
2
3
func findRadius(houses []int, heaters []int) int {
}

解答思路:

如果兩個參數值是在由小至大排序的情況下，應該不會有什麼大問題，在此條件的前提下，盡可能先找出在房子後頭的火爐，如果火爐在該房前頭就找下一個火爐，如果到最後一個火爐的位置該房子還是在火爐後頭，這時才開始計算房子與火爐的距離，因為火爐已經到底所以就直接計算尚未遍歷房子的最後一棟(因為要找離火爐最遠的位置當半徑)，如果該距離比目前所存的半徑大就是結果，而另外一方面如果發現有房子在火爐前頭的情況，這時就計算房子與火爐的距離，如果該火爐非第一個，就同時再計算前一個火爐(會在該房子前面)的距離，同時比較房子與前面火爐的距離哪個比較近，以距離比較小的為主，如果又比目前找出的半徑大才做儲存，直到所有的房子遍歷完才回傳半徑。

程式碼解說:

一開始用內建的library先將房子與火爐從小到大做排序，接著就是開始計算最小半徑，盡可能先找出在房子後頭的火爐，現在先只看如果只有火爐在房子前頭的情況，如果火爐還沒到最後一個就繼續往後找，而最後到最後一個火爐的位置時，如果該房子還是在火爐後頭，就直接將還沒遍歷房子中的最後一棟與火爐相減找出距離，如果該長度比半徑大就將其取代，並回傳結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
sort.Ints(houses)
sort.Ints(heaters)
var pre int
var post int
var radius int
var houseIndex int
var heaterIndex int
for true {
	if houses[houseIndex] < heaters[heaterIndex] {
		...
	} else {
		if heaterIndex != len(heaters)-1 {
			heaterIndex++
		} else {
			pre = houses[len(houses)-1] - heaters[heaterIndex]
			if pre > radius {
				radius = pre
			}
			break
		}
	}
}
return radius

發現有火爐在房子後頭的情況，找出房子與前後頭火爐位置的距離，此時火爐的位置在第一個，此時並不存在前一個火爐在房子前頭，將前頭距離以題目所給予的最大值在儲存，最後比較前後頭距離誰比較小，如果又剛好比目前找到的半徑大就將其取代，直到遍歷完所有的房子才跳開回圈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if houses[houseIndex] < heaters[heaterIndex] {
	post = heaters[heaterIndex] - houses[houseIndex]
	if heaterIndex != 0 {
		pre = houses[houseIndex] - heaters[heaterIndex-1]
	} else {
		pre = 1000000000
	}
	if pre < post && pre > radius {
		radius = pre
	} else if post < pre && post > radius {
		radius = post
	}
	houseIndex++
	if houseIndex == len(houses) {
		break
	}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func findRadius(houses []int, heaters []int) int {
	sort.Ints(houses)
	sort.Ints(heaters)
	var pre int
	var post int
	var radius int
	var houseIndex int
	var heaterIndex int
	for true {
		if houses[houseIndex] < heaters[heaterIndex] {
			post = heaters[heaterIndex] - houses[houseIndex]
			if heaterIndex != 0 {
				pre = houses[houseIndex] - heaters[heaterIndex-1]
			} else {
				pre = 1000000000
			}
			if pre < post && pre > radius {
				radius = pre
			} else if post < pre && post > radius {
				radius = post
			}
			houseIndex++
			if houseIndex == len(houses) {
				break
			}
		} else {
			if heaterIndex != len(heaters)-1 {
				heaterIndex++
			} else {
				pre = houses[len(houses)-1] - heaters[heaterIndex]
				if pre > radius {
					radius = pre
				}
				break
			}
		}
	}
	return radius
}

總結:

給二陣列其一為房子的位置，另一為火爐的位置，找出每個相同火爐能提供的最小半徑來涵蓋所有房子，首先先將兩陣列進行排序，一開始盡可能先找出在房子後頭的火爐，如果火爐在該房前頭就找下一個火爐，如果到最後一個火爐的位置該房子還是在火爐後頭，這時才開始計算房子與火爐的距離，因為火爐已經到底所以就直接計算尚未遍歷房子的最後一棟(因為要找離火爐最遠的位置當半徑)，如果該距離比目前所存的半徑大就是結果，而另外一方面如果發現有房子在火爐前頭的情況，這時就計算房子與火爐的距離，如果該火爐非第一個，就同時再計算前一個火爐(會在該房子前面)的距離，同時比較房子與前面火爐的距離哪個比較近，以距離比較小的為主，如果又比目前找出的半徑大才做儲存，直到所有的房子遍歷完才回傳半徑。

分享到