面试题60：n个骰子的点数
题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
- 算法：循环
- 用两个数组保存骰子总数出现的次数
- 第一个数组保存n个骰子时总和频率
- 第二个数组保存n+1个骰子时总和频率
- 用flag变量交换数组使用上一个骰子迭代计算下一个骰子
- fn(n) = fn-1(n-1) + fn-1(n-2) + fn-1(n-3) + fn-1(n-4) + fn-1(n-5) + fn-1(n-6)
public double[] twoSum(int n) {
if (n <= 0) {
throw new RuntimeException("Invalid arguments");
}
int maxValue = 6;
int[][] count = new int[2][n*maxValue+1];
int flag = 0;
for (int i = 1; i <= maxValue; i++) {
count[flag][i] = 1;
}
for (int k = 2; k <= n; k++) { // k个骰子
for (int i = 1; i < k; i++) { // k个骰子和至少为k，所以小于k的和频率是0
count[1-flag][i] = 0;
}
for (int i = k; i <= k * maxValue; i++) { // k个骰子的和
count[1-flag][i] = 0;
for (int j = 1; j <= maxValue && j < i; j++) { // 使用k-1个骰子计算k个骰子
count[1-flag][i] += count[flag][i-j];
}
}
flag ^= 1;
}
double[] result = new double[n*maxValue-n+1];
double total = Math.pow(maxValue, n);
for (int i = 0; i < n*maxValue-n+1; i++) {
result[i] = count[flag][i+n] / total;
}
return result;
} - 算法：递归
- 类似全排列递归，递归到最后一个骰子终止
public double[] twoSum(int n) {
if (n <= 0) {
throw new RuntimeException("Invalid arguments");
}
int maxValue = 6;
int[] count = new int[n*maxValue-n+1];
for (int i = 1; i <= maxValue; i++) {
countFrequency(n, n-1, maxValue, i, count);
}
double[] result = new double[n*maxValue-n+1];
double total = Math.pow(maxValue, n);
for (int i = 0; i < n*maxValue-n+1; i++) {
result[i] = count[i] / total;
}
return result;
}
// 递归函数的含义：总共original个骰子，现还剩current个骰子未计入和，当前达到的和是sum
public void countFrequency(int original, int current, int maxValue, int sum, int[] count) {
if (current == 0) {
count[sum-original]++;
} else {
for (int i = 1; i <= maxValue; i++) {
countFrequency(original, current-1, maxValue, sum+i, count);
}
}
} 面试题61：扑克牌的顺子
题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王可以看成任意数字。
- 算法：
- 1.排序
- 2.统计0也就是大小王的个数
- 3.统计间隔的个数
- 4.判断
public boolean isStraight(int[] nums) {
checkArguments(nums);
countSort(nums);
int numberOfZero = 0;
int numberOfGap = 0;
for (int x : nums) {
numberOfZero += ((x == 0) ? 1 : 0);
}
for (int i = numberOfZero+1; i < nums.length; i++) {
if (nums[i] == nums[i-1]) { // 对子
return false;
}
numberOfGap += (nums[i] - nums[i-1] - 1);
}
return numberOfZero >= numberOfGap;
}
public void countSort(int[] nums) {
int[] count = new int[14];
for (int x : nums) {
count[x]++;
}
for (int i = 0, k = 0; i < 14; i++) {
while (count[i] != 0) {
nums[k++] = i;
count[i]--;
}
}
} 面试题62：圆圈中最后剩下的数字
题目：0, 1, …, n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
- 算法：闭公式
1. 第一个被删除的数字: k = (m-1)%n
2. 删除之后: 0 1 2 ... n -> 0 1 2 ... k-1 k+1 ... n
3. 整理序列下次删除从k+1开始计数: k+1 ... n-1 0 1 ... k-1
4. 有如下映射和逆映射 p(x) = (x-k-1) % n
k+1 ... n-1 0 1 ... k-1 <====================> 0 ... n-k-2 n-k-1 n-k ... n-2
p-1(x) = (x+k+1) % n
5. 推导:
f(n, m) = f'(n-1, m) = p-1[f(n-1, m)] = [f(n-1, m)+k+1] % n = [f(n-1, m) + m] % n
f'(n-1, m)表示从删除数字计数下一个要删除的数字的序号
f(n-1, m)表示从零计数下一个要删除的数字的序号，经过逆映射就是f'(n-1, m)原序号
6. 递推公式
f(n, m) = 0, n = 1
= [f(n-1, m)+m] % n, n > 1public int lastRemaining(int n, int m) {
if (n <= 0 || m <= 0) {
return -1;
}
int last = 0;
for (int i = 2; i <= n; i++) {
last = (last + m) % i;
}
return last;
} - 算法：
- Java迭代器
public int lastRemaining(int n, int m) {
if (n <= 0 || m <= 0) {
return -1;
}
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
list.add(i);
}
Iterator<Integer> it = list.iterator();
while (list.size() > 1) {
int i = 0;
for (; i < m; i++) {
it.next();
if (!it.hasNext()) {
if (i == m - 1) { // 当迭代器需要删除的刚好是最后一个结点时，就删除然后跳出循环从头开始
it.remove();
break;
}
it = list.iterator();
}
}
if (i == m) {
it.remove();
} else {
it = list.iterator();
}
}
return list.peekFirst();
} - 算法：
- 自定义环形链表
public int lastRemaining(int n, int m) {
if (n <= 0 || m <= 0) {
return -1;
}
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
ListNode head = new ListNode(0);
ListNode prev = head;
for (int i = 1; i < n; i++) {
prev.next = new ListNode(i);
prev = prev.next;
}
prev.next = head;
while (head.next != head) {
for (int i = 1; i < m; i++) {
head = head.next;
prev = prev.next;
}
prev.next = head.next;
head = head.next;
}
return head.val;
} 面试题63：股票的最大利润
题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖交易该股票可能获得的利润是多少？例如一只股票在某些时间节点的价格为{9, 11, 8, 5, 7, 12, 16, 14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获最大的利润11。
- 算法：
- 维护变量min保存前i-1个数中最小值
- 当前值减去min即是当前值卖出的最大利润
public int maxProfit(int[] prices) {
if (prices == null) {
return -1;
}
if (prices.length <= 1) {
return 0;
}
int min = prices[0];
int maxProfit = prices[1] - min;
for (int i = 2; i < prices.length; i++) {
if (prices[i-1] < min) {
min = prices[i-1];
}
maxProfit = (maxProfit > prices[i]-min) ? maxProfit : (prices[i]-min);
}
return maxProfit > 0 ? maxProfit : 0;
} - 算法：Kadane算法
- 最大连续子数组问题的变种
- 原数组[a1, a2, a3, a4, a5]
- 新数组[0, a2-a1, a3-a2, a4-a3, a5-a4]
- 那么找原数组中最大差就变成了找新数组中最大连续子数组和
- 最大连续子数组问题
public int maxProfit(int[] prices) {
// maxCur表示以当前值结尾的最大值
// maxSoFar表示已经发现的最大值
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.length; i++) {
maxCur = Math.max(0, maxCur + (prices[i] - prices[i-1]));
maxSoFar = Math.max(maxCur, maxSoFar);
}
return maxSoFar;
} 
京公网安备 11010502036488号