Условие
Дано множество уникальный целых положительных чисел, найти наибольшее подмножетсво в котором каждая пара элементов отвечает следущим условиям:
$$S_i \bmod S_j = 0$$ or $$S_j \bmod S_i = 0$$.
Если несколько таким подмножеств - -венуть любое
пример 1
1
2
|
Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)
|
пример 2
1
2
|
Input: [1,2,4,8]
Output: [1,2,4,8]
|
Решение
HashMap
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
func largestDivisibleSubset(nums []int) []int {
haveOne := false
sort.Ints(nums)
q := make(map[int][]int, 0)
for idx :=range nums {
if nums[idx] == 1 {
haveOne = true
continue
}
q[nums[idx]] = []int{}
for jdx:=idx+1; jdx<len(nums); jdx++ {
if nums[jdx]%nums[idx] == 0 {
q[nums[idx]] = append(q[nums[idx]], nums[jdx])
}
}
}
var w []int
for idx:= range q {
res := helper(q, idx)
if len(res)>len(w) {
w = res
}
}
if haveOne {
return append([]int{1}, w...)
}
return w
}
func helper(q map[int][]int, idx int) []int {
if _, ok := q[idx]; !ok {
return []int{}
}
if len(q[idx]) == 0 {
return []int{idx}
}
tmp := []int{}
for jdx := range q[idx] {
w := helper (q, q[idx][jdx])
if len(w) == len(q[idx]) {
return append([]int{idx}, w...)
}
if len(w)>len(tmp) {
tmp = w
}
}
return append([]int{idx}, tmp...)
}
|