面试题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 > 1
public 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; }