[已解决]Python：每日一题 316

zltzlt

今天的题目：

给定一个整数数组 a 和一个正整数 k，求 “从数组中选择四个数，要求四个数的乘积小于等于 k” 的方案总数。

说明：每次选择四个数时，值相同的两个数可以同时被选。

示例 1：

输入：a = [1, 1, 1, 2, 2]，k = 3
输出：2
解释：两种方法分别是：
a[0]，a[1]，a[2]，a[3]
a[0]，a[1]，a[2]，a[4]

示例 2：

输入：a = [2, 4, 9, 4, 3]，k = 300
输出：4
解释：四种方法分别是：
a[0]，a[1]，a[3]，a[4]
a[0]，a[1]，a[2]，a[4]
a[0]，a[2]，a[3]，a[4]
a[0]，a[1]，a[2]，a[3]

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-1-27 13:42:35

科比也去世了，这几天真的太抑郁了，不过还是要说：我们一定能渡过难关！

1. def fun316(a,k):
   
2.     def depow(num,jie):
   
3.         res = 1
   
4.         while True:
   
5.             if res ** jie > num:
   
6.                 break
   
7.             res = res + 1
   
8.         return res - 1
   
9.         
   
10.     def Couple(m,n):
    
11.         up = 1
    
12.         down = 1
    
13.         for i in range(1,n + 1):
    
14.             up = up * (m + 1 -i)
    
15.             down = down * i
    
16.         return up//down
    
17.    
    
18.     def inner(jie,pre,mul_num):
    
19.         if jie == 0:
    
20.             return 1
    
21.         if jie == 1:
    
22.             maxPossible = k//mul_num
    
23.             count = 0
    
24.             for i in range(pre + 1,M):
    
25.                 temp = sorted_set_a[i]
    
26.                 if temp <= maxPossible:
    
27.                     count += dictionary[temp]
    
28.                 else:
    
29.                     break
    
30.             return count
    
31.         else:
    
32.             maxPossible = depow(k//mul_num,jie)
    
33.             count = 0
    
34.             for i in range(pre + 1,M):
    
35.                 temp = sorted_set_a[i]
    
36.                 if temp <= maxPossible:
    
37.                     number = dictionary[temp]
    
38.                     possible_num = min([number,jie])
    
39.                     for inner_i in range(1,possible_num + 1):
    
40.                         count = count + Couple(number,inner_i)*inner(jie - inner_i,i,mul_num*(temp**inner_i))
    
41.                 else:
    
42.                     break
    
43.             return count
    
44.                
    
45.     if len(a) < 4:
    
46.         return 0
    
47.    
    
48.     dictionary = {}   
    
49.     for each in a:
    
50.         try:
    
51.             dictionary[each] += 1
    
52.         except Exception:
    
53.             dictionary[each] = 1
    
54.     sorted_set_a = sorted(set(a))
    
55.     M = len(sorted_set_a)
    
56.     return inner(4,-1,1)

复制代码

跳转到最佳答案楼层

TJBEST

科比也去世了，这几天真的太抑郁了，不过还是要说：我们一定能渡过难关！

1. def fun316(a,k):
   
2.     def depow(num,jie):
   
3.         res = 1
   
4.         while True:
   
5.             if res ** jie > num:
   
6.                 break
   
7.             res = res + 1
   
8.         return res - 1
   
9.         
   
10.     def Couple(m,n):
    
11.         up = 1
    
12.         down = 1
    
13.         for i in range(1,n + 1):
    
14.             up = up * (m + 1 -i)
    
15.             down = down * i
    
16.         return up//down
    
17.    
    
18.     def inner(jie,pre,mul_num):
    
19.         if jie == 0:
    
20.             return 1
    
21.         if jie == 1:
    
22.             maxPossible = k//mul_num
    
23.             count = 0
    
24.             for i in range(pre + 1,M):
    
25.                 temp = sorted_set_a[i]
    
26.                 if temp <= maxPossible:
    
27.                     count += dictionary[temp]
    
28.                 else:
    
29.                     break
    
30.             return count
    
31.         else:
    
32.             maxPossible = depow(k//mul_num,jie)
    
33.             count = 0
    
34.             for i in range(pre + 1,M):
    
35.                 temp = sorted_set_a[i]
    
36.                 if temp <= maxPossible:
    
37.                     number = dictionary[temp]
    
38.                     possible_num = min([number,jie])
    
39.                     for inner_i in range(1,possible_num + 1):
    
40.                         count = count + Couple(number,inner_i)*inner(jie - inner_i,i,mul_num*(temp**inner_i))
    
41.                 else:
    
42.                     break
    
43.             return count
    
44.                
    
45.     if len(a) < 4:
    
46.         return 0
    
47.    
    
48.     dictionary = {}   
    
49.     for each in a:
    
50.         try:
    
51.             dictionary[each] += 1
    
52.         except Exception:
    
53.             dictionary[each] = 1
    
54.     sorted_set_a = sorted(set(a))
    
55.     M = len(sorted_set_a)
    
56.     return inner(4,-1,1)

复制代码

冬雪雪冬

1. def func(a, k):
   
2.     import itertools, functools
   
3.     count = 0
   
4.     for each in itertools.combinations(a, 4):
   
5.         if functools.reduce(lambda x, y: x * y, each) <= k:
   
6.             count += 1
   
7.     return count

复制代码

zltzlt

冬雪雪冬 发表于 2020-1-27 13:59

输入长度为 400 的数组超时

TJBEST

a中都是非负整数？有没有负整数或者0？

zltzlt

TJBEST 发表于 2020-1-27 14:21
a中都是非负整数？有没有负整数或者0？

都是正整数。

冬雪雪冬

zltzlt 发表于 2020-1-27 14:20
输入长度为 400 的数组超时

这样是不是快些。

1. def func(a, k):
   
2.     a.sort()
   
3.     len1 = len(a)
   
4.     count = 0
   
5.     for i1 in range(len1- 3):
   
6.         for i2 in range(i1 + 1, len1 - 2):
   
7.             for i3 in range(i2 + 1, len1 - 1):
   
8.                 for i4 in range(i3 + 1, len1):
   
9.                     if a[i1] * a[i2] * a[i3] * a[i4] <= k:
   
10.                         count += 1
    
11.                     else:
    
12.                         break
    
13.     return count

复制代码

zltzlt

冬雪雪冬 发表于 2020-1-27 14:40
这样是不是快些。

快了一点，输入 a = [1] * 1000，k = 5 超时

776667

1. from itertools import combinations
   
2. 
   
3. def fun316(a,k):
   
4.     list_len = [i for i in range(len(a))]
   
5.     result = 0
   
6.     for i in combinations(list_len,4):
   
7.         if eval('%s*%s*%s*%s'%(a[i[0]],a[i[1]],a[i[2]],a[i[3]])) <= k:
   
8.             result += 1
   
9.     return result

复制代码

zltzlt

776667 发表于 2020-1-27 16:46

效率过低，输入长度为 400 的数组超时

546623863

1. def fun316(a,b):
   
2.     count = 0
   
3.     length = len(a)
   
4.     if length >= 4:
   
5.         for i in range(length):
   
6.             if i < (length - 3):
   
7.                 for j in range(i + 1,length):
   
8.                     if j < (length - 2):
   
9.                         for k in range(j + 1,length):
   
10.                             if k < (length - 1):
    
11.                                 for l in range(k + 1,length):
    
12.                                     if l <length and a[i] * a[j] * a[k] * a[l] <= b:
    
13.                                         count += 1
    
14.                             else:
    
15.                                 continue
    
16.                     else:
    
17.                         continue
    
18.             else:
    
19.                 break
    
20.     return count

复制代码

这应该是最容易想到的一种吧，不过效率可能不太高，楼主给点意见，我等会再改改

546623863

1. def fun316(a,b):
   
2.     count = 0
   
3.     length = len(a)
   
4.     if length >= 4:
   
5.         for i in range(length):
   
6.             if i < (length - 3) and a[i] <= b:
   
7.                 for j in range(i + 1,length):
   
8.                     if j < (length - 2) and a[i] * a[j] <= b:
   
9.                         for k in range(j + 1,length):
   
10.                             if k < (length - 1) and a[i] * a[j] * a[k] <= b:
    
11.                                 for l in range(k + 1,length):
    
12.                                     if l <length and a[i] * a[j] * a[k] * a[l] <= b:
    
13.                                         count += 1
    
14.                             else:
    
15.                                 continue
    
16.                     else:
    
17.                         continue
    
18.             else:
    
19.                 break
    
20.     return count

复制代码

在第一种的基础上加了点条件，应该会快一点

zltzlt

546623863 发表于 2020-1-27 18:43
在第一种的基础上加了点条件，应该会快一点

输入 a = [1] * 1000，k = 5 超时

546623863

1. def fun316(a,b):
   
2.     count = 0
   
3.     length = len(a)
   
4.     a.sort()
   
5.     if length >= 4:
   
6.         for i in range(length):
   
7.             if i < (length - 3) and a[i] <= b:
   
8.                 for j in range(i + 1,length):
   
9.                     if j < (length - 2) and a[i] * a[j] <= b:
   
10.                         p = j + 1
    
11.                         q = length - 1
    
12.                         temp = b / (a[i] * a[j])
    
13.                         if (a[p] * a[p+1]) > temp:
    
14.                             continue
    
15.                         if (a[q] * a[q-1]) <= temp:
    
16.                             count += (q - p + 1)*(q - p)/2
    
17.                             continue
    
18.                         while q > p:
    
19.                             if a[p] * a[q] <= temp:
    
20.                                 count += (q - p)
    
21.                                 p += 1
    
22.                             else:
    
23.                                 q -= 1
    
24.                     else:
    
25.                         break
    
26.             else:
    
27.                 break
    
28.     return int(count)

复制代码

这个不是单纯的暴力循环了，刚才自己测了一下，比第一种快不少

zltzlt

546623863 发表于 2020-1-27 19:24
这个不是单纯的暴力循环了，刚才自己测了一下，比第一种快不少

输入长度为 1000 的数组超时

阴阳神万物主

k值相对很小的情况下耗时较长，比如：a=[1]*100,k=0

1. def solve(a,k):
   
2.     a.sort(reverse=True)
   
3.     res = 1
   
4.     le = len(a)
   
5.     for i in range(le,4,-1):
   
6.         res *= i
   
7.     for i in range(le-4,1,-1):
   
8.         res //= i
   
9.     mul = 1
   
10.     for x in range(le-3):
    
11.         mul *= a[x]
    
12.         for y in range(x+1,le-2):
    
13.             mul *= a[y]
    
14.             for i in range(y+1,le-1):
    
15.                 mul *= a[i]
    
16.                 for j in range(i+1,le):
    
17.                     mul *= a[j]
    
18.                     if mul <= k:
    
19.                         return res
    
20.                     res -= 1
    
21.                     mul //= a[j]
    
22.                 mul //= a[i]
    
23.             mul //= a[y]
    
24.         mul //= a[x]
    
25.     return res
    
26. if __name__ == '__main__':
    
27.     print('示例1 输出：',solve(a = [1, 1, 1, 2, 2], k = 3))
    
28.     print('示例1 输出：',solve(a = [2, 4, 9, 4, 3], k = 300))
    

复制代码

冬雪雪冬

zltzlt 发表于 2020-1-27 14:45
快了一点，输入 a = [1] * 1000，k = 5 超时

再次修改

1. def func(a, k):
   
2.     set1 = set(a)
   
3.     b = []
   
4.     for i in set1:
   
5.         b.extend([i] * min(a.count(i), 4))
   
6.     import itertools, functools
   
7.     count = 0
   
8.     for each in itertools.combinations(b, 4):
   
9.         if functools.reduce(lambda x, y: x * y, each) <= k:
   
10.             count += 1
    
11.     return count

复制代码

zltzlt

阴阳神万物主 发表于 2020-1-28 03:31
k值相对很小的情况下耗时较长，比如：a=[1]*100,k=0

解答错误

输入：
a = [38, 88, 50, 83, 37, 85, 82, 10, 97, 35, 50, 69, 89, 3, 51, 3, 13, 61, 65, 66, 4, 46, 64, 44, 5, 45, 36, 10, 52, 52, 84, 48, 86, 24, 49, 79, 79, 95, 14, 4, 43, 28, 75, 41, 55, 4, 7, 61, 94, 3, 66, 32, 75, 56]，k = 3002
输出：292826
预期结果：1365

zltzlt

冬雪雪冬 发表于 2020-1-28 11:27
再次修改

还是很慢，建议不要用 combinations

wanting-for

一个数只能选择一次，还是可以重复选择呢？