input:[1,5,4,3,2,5,6]
output:任意三个数能组成三角形的组合数
用python做了下,不知道对不对。
import itertools
input = [1,5,4,3,2,5,6]
temp1 = list(set(input))
temp2 = itertools.combinations_with_replacement(temp1,3)
print([x for x in temp2 if (x[2]-x[0]<x[1])])~~~~
[(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (2, 2, 2), (2, 2, 3), (2, 3, 3), (2, 3, 4), (2, 4, 4), (2, 4, 5), (2, 5, 5), (2, 5, 6), (2, 6, 6), (3, 3, 3), (3, 3, 4), (3, 3, 5), (3, 4, 4), (3, 4, 5), (3, 4, 6), (3, 5, 5), (3, 5, 6), (3, 6, 6), (4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 5, 5), (4, 5, 6), (4, 6, 6), (5, 5, 5), (5, 5, 6), (5, 6, 6), (6, 6, 6)]
更新思路:
能组成三角形的三边长度有个特点就是最长边减去最短边一定要小于第三条边。也就是我们首先要找出Input中给定数字的三条边所有组合,用 Python 是因为有现成的库可以用,Javascript 要完全手写,这个算法你 Google 一下。具体到解题:
1、对输入的数字去重
2、组成所有组合,每个组合中的三个数可以重复(等边或等腰三角形)
3、对每一个组合进行排序,排序的目的在于可以通过index获取最大的数和最小的数和不大不小的数。比如 arr[0]一定是最小数,arr[2]一定是最大数,那么 arr[1]一定是不大不小那个数.
4、筛选出 arr[2]-arr[0]<arr[1] 的组合。
领扣上有原题吧, 里面题解思路都有
https://leetcode-cn.com/probl...
这个问题拆一拆
1 从数组 M 个元素里 取出 3个元素 的组合
2 每个组合,两两相加 均大于第3个数
这个数的意义没有明确,如果是表示边长,且可以或者不可以重复使用,则规则就是从数组中(可重复或者不可重复)的提取3个数,看3个数是否存在任意2个数的和大于第3个数。