未分類

House Robber II

DynamicProgramming, Go, LeetCode

House Robber II

Note:

This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

提示 解題應用
DynamicProgramming 規律觀查

Default:

1
2
3
func rob(nums []int) int {
}

解答思路:

建議可以先參考先前House Robber的解法，解說較為詳細，基本上概念完全一樣，只是重覆使用先前的程式碼而已，如果能找出數列中不連續的極大值總合，現在該數列是表示為圓環要篩選頭尾為連續的情況就不會太困難。

與之前一樣將其分為左(index奇數)與右(index偶數)來區別，之後只要判斷如果輪到該數而那一側的總合結果比另一側小，這時另一側的總合就能取代原本那一側的總合，再分別繼續往下重覆上述動作，至於如果是圓環要如何避免頭尾連續，其實只要將陣列分作兩種情況(“陣列的開頭到尾巴的前一項”與”陣列的開頭下一項到尾巴”)，再分別當作普通數列找不連續的極大值總合，最後再比較哪一種情況總合比較大就會是我們要的結果。

程式碼解說:

因為對於數列是圓環要避免頭尾連續，之後要將其分作兩種情況，分別是陣列不包含開頭的資料與陣列不包含結尾的資料，不過在那之前要先判斷如果陣列長度為0就回傳0，如果長度為1就回傳該個唯一的值，接著就可以將此兩種情況分別當作普通數列找不連續的極大值總合，最後再比較哪一種情況總合比較大就會是我們要的結果

1
2
3
4
5
6
7
8
9
10
11
12
13
func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	} else if len(nums) == 1 {
		return nums[0]
	}
	excludeFront := robSum(nums[1:])
	excludeRear := robSum(nums[:len(nums)-1])
	if excludeFront > excludeRear {
		return excludeFront
	}
	return excludeRear
}

此部分與先前找出數列中不連續極大值總合的程式碼完全一模一樣就不再多做解說

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func robSum(nums []int) int {
	var odd int
	var even int
	for i, v := range nums {
		if i%2 != 0 {
			odd = odd + v
			if even > odd {
				odd = even
			}
		} else {
			even = even + v
			if odd > even {
				even = odd
			}
		}
	}
	if odd > even {
		return odd
	}
	return even
}

完整程式碼:

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
func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	} else if len(nums) == 1 {
		return nums[0]
	}
	excludeFront := robSum(nums[1:])
	excludeRear := robSum(nums[:len(nums)-1])
	if excludeFront > excludeRear {
		return excludeFront
	}
	return excludeRear
}
func robSum(nums []int) int {
	var odd int
	var even int
	for i, v := range nums {
		if i%2 != 0 {
			odd = odd + v
			if even > odd {
				odd = even
			}
		} else {
			even = even + v
			if odd > even {
				even = odd
			}
		}
	}
	if odd > even {
		return odd
	}
	return even
}

總結:

建議可以先參考先前House Robber的解法，解說較為詳細，基本上概念完全一樣，只是如果數列是圓環要如何避免頭尾連續，其實只要將陣列分作兩種情況(“陣列的開頭到尾巴的前一項”與”陣列的開頭下一項到尾巴”)，再分別當作普通數列找不連續的極大值總合，最後再比較哪一種情況總合比較大就會是我們要的結果。

分享到