未分類

Largest Divisible Subset

DynamicProgramming, Go, LeetCode, Math

Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

1
2
3
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

1
2
3
nums: [1,2,4,8]
Result: [1,2,4,8]
提示 解題應用
Math 規律觀查

Default:

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

解答思路:

這題最主要是要先知道一個觀念，數組之間的數字存在互相整除的狀況下，如果有一較大的值要判斷是否能放入數組之中，確定該值能整除目前數組中的最大值即可，反之如果有一較小的值要判斷，確定目前數組中的最小值能整除該值即可，所以只要先將整個數列做排序，接著遍歷已排序後的數列，每次將取出的數字作為中心，往左(更小的值)右(更大的值)兩側尋找可以放入數組的目標，並且記得放入時要更新目前的最大、最小值，如此一來在遍歷結束後就可以在數列裡頭找出最大且數字間存在能互相整除的數組。

程式碼解說:

如思路所述一開始便將整個數列做排序，每次將取出的數字作為中心(最大、最小的初始值皆為取出的數字)，往左(更小的值)右(更大的值)兩側尋找可以放入數組的目標(存在互相整除的狀況)，並且記得放入時要更新目前的最大、最小值，接著比較暫存的數組大小是否比要回傳的結果數組大，如果比較大就將其做取代，最後待遍歷結束後就可以直接回傳結果陣列

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
var sj int
var small int
var big int
var tmp []int
var result []int
sort.Ints(nums)
for i, si := range nums {
	tmp = []int{}
	small = si
	big = si
	for j := len(nums[:i]) - 1; j >= 0; j-- {
		sj = nums[j]
		if small%sj == 0 {
			small = sj
			tmp = append([]int{sj}, tmp...)
		}
	}
	for _, sj := range nums[i:] {
		if sj%big == 0 {
			big = sj
			tmp = append(tmp, sj)
		}
	}
	if len(tmp) > len(result) {
		result = tmp
	}
}
return result

完整程式碼:

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
func largestDivisibleSubset(nums []int) []int {
	var sj int
	var small int
	var big int
	var tmp []int
	var result []int
	sort.Ints(nums)
	for i, si := range nums {
		tmp = []int{}
		small = si
		big = si
		for j := len(nums[:i]) - 1; j >= 0; j-- {
			sj = nums[j]
			if small%sj == 0 {
				small = sj
				tmp = append([]int{sj}, tmp...)
			}
		}
		for _, sj := range nums[i:] {
			if sj%big == 0 {
				big = sj
				tmp = append(tmp, sj)
			}
		}
		if len(tmp) > len(result) {
			result = tmp
		}
	}
	return result
}

總結:

如果要在數列裡頭找出最大且數字間存在能互相整除的數組，最主要是要先知道一個觀念，如果有一較大的值要判斷是否能放入數組之中，確定該值能整除目前數組中的最大值即可，反之如果有一較小的值要判斷，確定目前數組中的最小值能整除該值即可，所以只要先將整個數列做排序，接著遍歷已排序後的數列，每次將取出的數字作為中心，往左(更小的值)右(更大的值)兩側尋找可以放入數組的目標，並且記得放入時要更新目前的最大、最小值，如此一來在遍歷結束後就能找出最大的數組。

分享到