【剑指】6.4 抽象建模能力
Wallace Xu 2020-08-18 动态规划算术
有时我们会遇到一些从生活中抽取出来的问题，遇到这类问题我们需要分析其内在规律，再进一步选择合适的模型予以解决。
# 面试题60：n个骰子的点数
# 题目描述
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n（1 <= n <= 11），打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
# 解题思路
使用动态规划数组dp[i][j]表示已经投掷了i个骰子时，点数之和为j的概率，则dp[i][j]可以从所有dp[i-1][j-k]~dp[i-1][j-1]的和再乘以1/6得到（1<=k<=6，k<=j），本质是第i个骰子投出了k点。
public double[] twoSum(int n) {
double[][] result = new double[n + 1][6 * n + 1];
for (int i = 1; i <= 6; i++) {
result[1][i] = 1 / 6.0;
}
for (int i = 2; i <= n; i++) {
for (int j = i; j <= 6 * i; j++) {
for (int k = 1; k <= 6 && k < j; k++) {
result[i][j] += result[i - 1][j - k];
}
result[i][j] *= result[1][1];
}
}
return Arrays.copyOfRange(result[n], n, 6 * n + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 面试题61：扑克牌中的顺子
# 题目描述
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。输入数组长度为 5 ，数组的数取值为 [0, 13]。
# 解题思路
不用真正地排序，只需要用hash来统计每张牌出现地次数即可。发现有非零的对子直接返回false，之后找到顺子地最小值和最大值，max和min之间有max-min-1个空位需要填满，已有nums.length - hash[0]-2个非0数，还有hash[0]个0。如果需要填满地位置超过了后两者的和则不是顺子，否则一定能构成顺子。
public boolean isStraight(int[] nums) {
int[] hash = new int[14];
for (int num : nums) {
//发现有非零的对子直接返回false
if (++hash[num] != 1 && num != 0)
return false;
}
//这里已经保证数组中除0外的牌最多只有一张，找到顺子数值的左右边界
int min = 0, max = 0;
for (int i = 1; i < 14; i++) {
if (min == 0 && hash[i] != 0)
min = i;
if (hash[i] != 0)
max = i;
}
int nonZero = nums.length - hash[0];
//max和min之间有max-min-1个空位需要填满，已有nonZero-2个非0数，还有hash[0]个0
//特例max和min相等即原数组只有一个非0数，那么左边小于0，右边大于0，也不影响
if (max - min - 1 > nonZero - 2 + hash[0])
return false;
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 面试题62：圆圈中最后剩下的数字
# 题目描述
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
# 解题思路
经典的解法是可以使用一个大小为O(n)的循环链表来模拟，还可以使用反推法，反推最终的安全位在人数为n时的编号。
- 人数为1时，安全位置在这时的编号（相对于开始位置的偏移量）为0；
- 人数为2时，安全位置在0~1中的编号为(0+m)%2；（删除位置的下标为m-1，下一轮的开始位置在m，加上人数为1时安全位置的偏移量后再取模）
- 人数为3时，安全位置在0~2中的编号为((0+m)%2+m)%3；（依然是从m开始加上人数为n-1时安全位距离开始位置的偏移量）
依次类推可以得到最终的结果。
public int lastRemaining(int n, int m) {
int result = 0;
for (int i = 2; i <= n; i++) {
result = (result + m) % i;
}
return result;
}
1
2
3
4
5
6
7
2
3
4
5
6
7
# 面试题63：股票的最大利润
见前面做过的LeetCode股票系列。