从Leetcode 每日一题练习继续讨论：
题解
本题和求数组的全部子集有一些相似之处, 先排序, 排序可以使得在找与当前数字绝对值相差k的数时只需要看前面的数即可. 保存到当前位置处得到的全部合格的子数组(漂亮的). 在继续遍历时将新的数与之前的所有合格子数组比较, 看原来的子数组中是否有与新的数冲突的数. 若有则不能与新的数组合, 没有则可以组合. 这里为了快速寻找是否冲突, 可以用数组来保存之前的合格子数组, 将之前合格子数组中所有的数作为数组的下标.下标对应位置的值为1. 不包含的数的下标对应位置为0. 考虑数组中的数最大为1000. 这种方法是可以保存所有数的情况的.
代码
func beautifulSubsets(nums []int, k int) int {
sort.Ints(nums)
result := 0
subsets := [][]int{}
new := make([]int,32)
subsets = append(subsets, new)
for _, value := range nums{
if value <= k{
for _, set := range subsets{
newset := []int{}
newset = append(newset, set...)
newset[value/32] = newset[value/32] | 1 << (value % 32)
subsets = append(subsets, newset)
result++
}
}else{
for _,set := range subsets{
if (set[(value-k)/32] & (1 << ((value-k) % 32))) == 0{
newset := []int{}
newset = append(newset, set...)
newset[value/32] = newset[value/32] | 1 << (value % 32)
subsets = append(subsets, newset)
result++
}
}
}
}
return result
}
总结
该方法时间复杂度比较高, 可参见下面的题解中讲解的动态规划解法, 这里要思考为什么同余的性质如此重要. 因为同余将数组中的数按照不同的性质分为了不同的组, 不同的组的数一定不会相差k因此可以随意组合. 最终结果相当于在这些组中任意选取组内一个可行组合进行组间组合. 这样通过将所有组的组内可行方案相乘就能得到最终结果. 而在组内, 通过排序, 因此各个数都同余, 只有相邻的数可能相差k, 不相邻的相差一定是k的2倍及以上, 这样就能用动态规划来求得组内的全部方案, 可以把问题转换为子问题, 如果不相邻的数也可能相差k, 那么问题就很难用动态规划来解决, 因为不知道什么时候才能解决一个子问题, 把相差k限制在相邻数, 我们就知道只要经过了这个相邻的数, 前面的数对后面一定没有影响了, 就解决了一个子问题, 这样相当于隐含携带了前面的数的信息.