狗家月初昂塞

Teddies 发表于 2018-11-22 11:48
一共任意多骰子，只扔一次，所有骰子一起扔，没有顺序要求，只要有可能扔出那个目标单词就返回true，如果 ...

不好意思，想再问一下这道题的细节，所以给定的骰子都会在input里面出现吗？比如input里面包含10个array来表示骰子的话，是否说明有且只有10个骰子呢？这样如果target word长度大于10，就直接返回false？还是说10个array表示10种不同的骰子，每一种骰子可以有任意个呢？非常感谢lz！！！

SakuraBlossom 发表于 2018/12/01 15:23:16


不好意思，想再问一下这道题的细节，所以给定的骰子都会在input里面出现吗？比如input里面包含10个array来表示骰子的话，是否说明有且只有10个骰子呢？这样如果target word长度大...

目标词汇长度超过骰子数量直接返回false，每种骰子只有一个，不一定所有骰子都要用到

Teddies 发表于 2018-12-2 08:05
目标词汇长度超过骰子数量直接返回false，每种骰子只有一个，不一定所有骰子都要用到

谢谢lz！

楼主，求问第五轮有重复怎么办呀？谢谢

yexiaojiaycc 发表于 2018-12-4 17:03
楼主，求问第五轮有重复怎么办呀？谢谢

还可以用一样的做法，只不过要在移动双指针的时候跳过重复的数字。
比如 [1,1,1,2,2,2,3,3,3], K = 4，双指针一开始在 i = 0, j = 7, 由二项式定理计算一次结果，之后移动左指针，跳过重复，i = 3,  2 + 3 = 5 > 4，所以移动右指针，跳过重复，到 j = 4，由于两个指针所指的数值相同，意味着结束这次计算就要跳出循环结束，所以再用一次二项式定理计算一次结果，然后直接返回。

补充内容 (2018-12-7 23:43):
不好意思，我这个follow up说错了，解法还是有问题，请具体参考我下面回复的最新的帖子，也欢迎提出更好的解法，谢谢～

你好楼主，round 5可以举一个例子吗？“使得这些sub group满足 min(S) + max(S) <= K” 是说S 里的max - min <= k吗？ 那如果是[1,2,3] k = 4的时候，[1,2,3] 作为一个subgroup就是复合条件的呀？ 因为max=3 min= 1。 同样的也不理解有重复的情况：比如你举的例子 [1,1,1,2,2,2,3,3,3], K = 4的时候整个数组就是符合条件的呀？因为max = 3, min = 1, 3 +1 <= 4

UUOlidd 发表于 2018-12-7 11:40
你好楼主，round 5可以举一个例子吗？“使得这些sub group满足 min(S) + max(S)

首先补充一下这道题不用考虑空集，不过其实考不考虑就是答案加一的事，不影响做题。

在没有重复的时候，我继续使用你的例子。[1,2,3] K=4的时候整个数组确实是符合条件的，所以一开始左指针指在1，右指针指在3，1+3 <= 4, 所以只需要在[2,3]中选择0个，1个或者2个元素，相当于排列组合的组合求和，C(2,0) + C(2,1) + C(2,2) = 1 + 2 + 1 = 4, 简化使用二项式定理得出一共有2^2=4种选法，对应的subGroup是[1],[1,2],[1,3],[1,2,3]. 然后左指针向右移动到2，2+3 > 4，不符合条件，右指针往回移动指到2，2 + 2 <= 4，从排列组合的角度看就是C(0,0) = 1, 只有一种选择，对应的subGroup是[2]，由于左右指针所指的数值相等，右指针不再移动，从这之后我们只需要移动左指针，直到左指针指向的元素值大于K为止，继续移动左指针指向3，3 <= 4, 答案 +1，左指针已经指向最后一个元素了，结束，返回答案4 + 1 + 1 = 6。如果考虑空集的情况就返回7。

对于有重复的，总体思路也是差不多的，不过不好意思我上一个帖子里稍微有些问题，不能再使用二项式定理直接计算了，因为这样还是会有重复的答案。比如[1,1,1,2,2,2,3,3,3] K = 4，一开始左指针指向1，右指针指向3，除了最小值的1以外还有8个元素可以选择，如果用二项式定理那么还会选到重复的结果，比如可能会出现多个[1,1,2]的subgroup, 所以目前我想到的一种使用hash set过滤重复，或者写一个helper函数，返回从某些特定元素种选择n个元素的不重复选法数量，即 int helper(vector<int>& v, int n)，这个helper函数最暴力的方法就是直接backtracking。我因为面试的时候没有回答道这一问，因此还没有细想过这个follow up, 如果有更好的解法欢迎大家讨论。

补充内容 (2018-12-7 23:44):
在有重复的时候，之前帖子里提到移动指针的时候跳过重复还是对的

Subgroup [2],[3] 不也是么。应该从1，2,3 combination。八种可能吧？ [], 1， 2，3, 12, 13, 23, 123.

sifangyou1 发表于 2018/12/08 04:16:55
Subgroup [2],[3] 不也是么。应该从1，2,3 combination。八种可能吧？ [], 1， 2，3, 12, 13, 23, 123.

我们讨论的是K = 4，Subgroup [2, 3]，最小值是2，最大值是3，2 + 3 = 5 > 4，不符合条件

Teddies 发表于 2018-12-7 23:41
首先补充一下这道题不用考虑空集，不过其实考不考虑就是答案加一的事，不影响做题。

在没有重复的时候 ...

学习到了，谢谢你的回复