n个骰子的点数
剑指 Offer 60. n个骰子的点数 - 力扣（Leetcode）
题目要求
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
例子：
1
2
3
4
5
| 输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
|
提示：
1 <= n <= 11
思路分析
动态对话
- dp函数的含义：当骰子的个数为
i时，点数为j时，一共有dp[i][j]中组合；
- 关系式：
dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2]+...+dp[i-1][j-6];
- 初始值：
dp[1][1] = 1;dp[1][2] = 1 ... dp[1][6] = 1;
代码实现
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
| class Solution {
public double[] dicesProbability(int n) {
int[][] dp = new int[n+1][6*n+1];
for(int i = 1;i <= 6; i++){
dp[1][i] = 1;
}
for(int i=2;i<=n;i++){
for(int j=i;j<=6 * i;j++){
for(int k=1;k<=6;k++){
if(j < k) break;
dp[i][j] += dp[i-1][j-k];
}
}
}
double[] res = new double[5 * n +1];
int index = 0;
double sum = Math.pow(6,n);
for(int i =n;i <= 6*n;i++){
res[index++] = dp[n][i] / sum;
}
return res;
}
}
|
扑克牌中的顺子
面试题61. 扑克牌中的顺子 - 力扣（Leetcode）
题目要求
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
例子：
1
2
3
4
5
| 输入: [1,2,3,4,5]
输出: True
输入: [0,0,1,2,5]
输出: True
|
提示：
-
数组长度为 5
-
数组的数取值为 [0, 13] .
思路分析
集合 时间O(n) 空间O(n)
若要成为顺子，需要满足以下条件：
- 不能存在重复的数，大小王除外；
- 最大值 - 最小值 < 5，大小王除外；
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public boolean isStraight(int[] nums) {
Set<Integer> res = new HashSet<>();
int max = -1,min = 25;
for(int i=0;i<nums.length;i++){
if(nums[i] == 0) continue;
if(res.contains(nums[i])) return false;
res.add(nums[i]);
max = Math.max(nums[i],max);
min = Math.min(nums[i],min);
}
return max - min < 5;
}
}
|
圆圈中最后剩下的数字
剑指 Offer 62. 圆圈中最后剩下的数字 - 力扣（Leetcode）
题目要求
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
例子：
1
2
3
4
5
| 输入: n = 5, m = 3
输出: 3
输入: n = 10, m = 17
输出: 2
|
提示：
1 <= n <= 10^51 <= m <= 10^6
思路分析
经典约瑟夫环问题，可以使用环形链表(时间O(n*n))解决，这里使用递归(时间O(n))来解决
- 每次删除某一个数字后，就对剩余的这些数字重新编号，难点时找出删除前和删除后数字编号的映射关系；
- 递归函数定义：f(n,m)表示当数字个数为m时，剩余数字的编号为f(n,m);
- 难点：找出f(n,m)和f(n-1,m)的关系；
- 通过分析删除前后n和m的关系，可以得出：
new = (old +m)%n，即f(n,m) = (f(n-1,m)+m) % n;
- 若m = 0，表示只剩最后一个数字，返回即可；
环形链表解决参考：【Java 数据结构与算法】单向环形链表 | Hey,Joker (jokerdig.com)
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int lastRemaining(int n, int m) {
if(n == 0) return n;
int res = 1;
for(int i=1;i <= n;i++){
res = (res + m) % i;
}
return res;
}
}
|
股票的最大利润
剑指 Offer 63. 股票的最大利润 - 力扣（Leetcode）
题目要求
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
例子：
1
2
3
4
5
6
7
8
| 输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
|
提示：
0 <= 数组长度 <= 10^5
思路分析
- 定义
int min = Integer.MAX_VALUE,max = 0;
- 再遍历的过程中，时刻将买入最小值保存到min；
- 当遇到当前值prices[i]大于min，就试着卖出，即
prices[i]-min，并将结果保存到max，max来记录利润的最大值；
- 最后将max返回即可
代码实现
时间O(n) 空间O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int max = 0;
for(int i=0;i<prices.length;i++){
if(prices[i] < min){
min = prices[i];
}else{
max = Math.max(max,prices[i]-min);
}
}
return max;
}
}
|
求1+2+…+n
剑指 Offer 64. 求1+2+…+n - 力扣（Leetcode）
题目要求
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
例子：
1
2
3
4
5
| 输入: n = 3
输出: 6
输入: n = 9
输出: 45
|
提示：
1 <= n <= 10000
思路分析
使用递归来实现，但是不能使用题目说到的关键字，那我们就考虑使用与或门来实现递归的停止条件；
代码实现
1
2
3
4
5
6
7
8
9
10
| class Solution {
int sum = 0;
public int sumNums(int n) {
boolean falg = n >= 1 && sumNums(n - 1) > 1;
sum = sum + n;
return sum;
}
}
|
微信
