小米秋招面试题题解

题目描述

今天同学分享了一个小米面试题,题目描述在牛客网上可以看到。这里将题目描述重述一下:

在游戏Dota2中,有一位非常强大的英雄卡尔,他有三种属性:冰、火、雷。同时卡尔身上有三个无顺序的属性槽,他可以从三种属性中任意选择三个放入属性槽中,然后通过当前的属性组合召唤技能。每种不同的属性组合都可以为卡尔召唤出不同的技能,共有十种组合:

1、冰冰冰

2、冰冰火

3、冰冰雷

4、冰火火

5、冰火雷

6、冰雷雷

7、火火火

8、火火雷

9、火雷雷

10、雷雷雷

现在我们想继续加强卡尔,如果给卡尔四种属性:冰、火、雷、风,同时给卡尔四个无顺序的属性槽,从而让卡尔可以从四种属性中任意选择四个,则请问卡尔共可以召唤出多少种不同的技能?

  • 28
  • 35
  • 48
  • 64

题解

穷举法

看到这道题首先想到的是:这是一道排列组合题,但是要包含判重操作。但是在数学上判重操作有点复杂,所以我先写个小程序穷举一下,得出正确结果。

穷举法的思路是这样的,我以三个元素为例子,假设冰对应数字0,火对应数字1,雷对应数字2,然后去构造一组高位至低位数字不严格递增的三进制数

  1. 冰冰冰-000
  2. 冰冰火-001
  3. 冰冰雷-002
  4. 冰火火-011
  5. 冰火雷-012
  6. 冰火火-022
  7. 火火火-111
  8. 火火雷-112
  9. 火雷雷-122
  10. 雷雷雷-222

将思路延展至四个元素,就可以假设冰对应数字0,火对应数字1,雷对应数字2,风对应数字3,去构造相对应的四进制数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let element = ['冰','火','雷','风',];
let num = 3;
let count = 0;
for (var i1 = 0; i1 <= num; i1++) {
for (var i2 = 0; i2 <= num; i2++) {
for (var i3 = 0; i3 <= num; i3++) {
for(var i4 = 0; i4<=num;i4++){
if (i1<=i2&&i2<=i3&&i3<=i4) {
console.log(element[i1]+element[i2]+element[i3]+element[i4]);
++count;
}
}
}
}
}
console.log('冰火雷风的总数: ',count);

因为懒,所以直接写了一个js,然后在控制台中:

1
$ node bhlf.js

最后的结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
冰冰冰冰
冰冰冰火
冰冰冰雷
冰冰冰风
冰冰火火
冰冰火雷
冰冰火风
冰冰雷雷
冰冰雷风
冰冰风风
冰火火火
冰火火雷
冰火火风
冰火雷雷
冰火雷风
冰火风风
冰雷雷雷
冰雷雷风
冰雷风风
冰风风风
火火火火
火火火雷
火火火风
火火雷雷
火火雷风
火火风风
火雷雷雷
火雷雷风
火雷风风
火风风风
雷雷雷雷
雷雷雷风
雷雷风风
雷风风风
风风风风
冰火雷风的总数: 35

数学解法

解法一

首先写出一种分类讨论的解法,这也是题解中常见的报告。将四个技能槽看作四个箱子,然后将冰、火、雷、风四个元素看作球,将球丢入四个箱子中,可以写出对应的公式为:
$$
{ C }_{ 4 }^{ 1 }+{ C }_{ 4 }^{ 2 }{ C }_{ 2 }^{ 1 }+{ C }_{ 4 }^{ 2 }+{ C }_{ 4 }^{ 3 }{ C }_{ 3 }^{ 1 }+{ C }_{ 4 }^{ 4 }=35
$$

解法二

但是上述解法要分类讨论,这里感谢yj童鞋给出的思路,将题目条件抽象为
$$
\begin{cases}
a+b+c+d=4\\
a,b,c,d\ge 0\\
\end{cases}
$$
其中a,b,c,d分别为冰火雷风元素,每一个元素至少为0个,至多为4个,且四个元素的总和必为4。在这里使用一个技巧(便于分割),令A=a+1,B=b+1,C=c+1,D=d+1,则上述条件变为:
$$
\begin{cases}
A+B+C+D=8\\
A,B,C,D\ge 1
\end{cases}
$$
上述问题可抽象为,共有八个球,需要将这八个球分为四组,那么就要在七个位置切三刀。则答案为:
$$
{ C }_{ 7 }^{ 3 }=35
$$
举例说明,如下情况为1115,则说明冰火雷三元素均为0,风元素为4个球。

〇|〇|〇|〇〇〇〇〇

如下情况为2222,则说明冰火雷风四个元素个有一个球。

〇〇|〇〇|〇〇|〇〇

接着可以在冰火雷三元素上进行验证,同理条件可以抽象为
$$
\begin{cases}
a+b+c=3\\
a,b,c,d\ge 0
\end{cases}
$$
运用技巧令A=a+1,B=b+1,C=c+1,上述条件变为:
$$
\begin{cases}
A+B+C=6\\
A,B,C\ge 1
\end{cases}
$$
则三个球共可以切出${ C }_{ 5 }^{ 2 }=10​$个技能。

杨辉三角

1
2
3
4
5
6
7
8
9

       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1
   1 5 10 10 5 1
  1 6 15 20 15 6 1
 1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1

由杨辉三角的性质可知第n行的第 k 个数字为组合数${ C }_{ n-1 }^{ k-1 }​$,则看到第6行第3个数字为3个元素的解,第8行第4个数字为4个元素的解。