HJ93 数组分组 题解

by 限时烟花

抽丝剥茧

这道题要求对输入一整个数组进行分组。要求分解为和相同的两个集合，并且要求：

1. 5的倍数在一个集合；
2. 3的倍数（不包括5的倍数）在一个集合。（即5的倍数的优先级大于3的倍数）

化繁为简

很直观的一个想法就是，先处理5和3的倍数集合，这样，加上剩余的数字集合。就将输入处理为三个集合。接下来只需要对剩余集合中的数字进行每一种可能的尝试。 那么自然而然地就可以想到递归的解决方法。

码上行动

def cal(s5, s3, re):
    if len(re) == 0:
        if s5 == s3:
            return True
        else:
            return False
    else:
        return cal(s5+re[0], s3, re[1:]) or cal(s5, s3+re[0], re[1:])
    
    
while True:
    try:
        length = int(input())
        num = list(map(int, input().split()))
        num_5 = []
        num_3 = []
        remains = []
        for i in num:
            if i % 5 == 0:
                num_5.append(i)
            elif i % 3 == 0:
                num_3.append(i)
            else:
                remains.append(i)
        sum_5 = sum(num_5)
        sum_3 = sum(num_3)
        res = cal(sum_5, sum_3, remains)
        if res:
            print('true')
        else:
            print('false')
    except:
        break
        

心有成算

时间复杂度：因为递归，且在最坏情况下，剩余集合长度为n，故时间复杂度为$O(2^n)O(2^n)$

空间复杂度：因为使用n长的空间来存储输入，故空间复杂度为$O(n)O(n)$

例题图解

另辟蹊径

基本思路不变，但你换一种处理手段：

while True:
    try:
        length = int(input())
        num = list(map(int, input().strip().split()))
        res = 0
        # 计算初始3,5倍数的差值
        for _ in range(length):
            i = num.pop(0)
            if i % 3 == 0:
                res += i
            elif i % 5 == 0:
                res -= i
            else:
                num.append(i)
        res = {res}
        # 结果计算，把之前结果，分别计算当前值的+和- 2种情况，然后把结果再放回去，给下一次计算
        while num:
            i = num.pop(0)
            res_plus = [x + i for x in res]
            res_plus.extend([x - i * 2 for x in res_plus])
            res = set(res_plus)
        # 最后如果0值在结果中，表示可以算出，如果不在则不行
        if 0 in res:
            print('true')
        else:
            print('false')
    except:
        break

时间复杂度：在最坏情况下，因为进行了双层循环，故时间复杂度为$O(n^2)O(n^2)$

空间复杂度：因为使用n长的空间来存储输入，故空间复杂度为$O(n)O(n)$