LeetCodeHOT100：60. n个骰子的点数、4. 探求两个正序数组的中位数

剑指 Offer 60. n个骰子的点数

   标题：把n个骰子扔在地上，全部骰子朝上一面的点数之和为s。输入n，打印出s的全部大概的值出现的概率。
你必要用一个浮点数数组返回复案，此中第 i 个元素代表这 n 个骰子所能掷出的点数集会集第 i 小的谁人的概率。
示例 1：
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
    思绪分析： 时间复杂度为                                    O                         (                                   n                            3                                  )                              O(n^3)                  O(n3)，此中第一个循环的次数是                                    n                              n                  n，第二个循环的次数是                                    6                         n                              6n                  6n，第三个循环的次数是                                    6                              6                  6，因此总次数为                                    n                         ×                         6                         n                         ×                         6                         =                         O                         (                                   n                            3                                  )                              n \times 6n \times 6 = O(n^3)                  n×6n×6=O(n3)。
  空间复杂度为                               O                      (                               n                         2                              )                          O(n^2)               O(n2)，必要开辟一个二维数组 dp，巨细为                               (                      n                      +                      1                      )                      ×                      (                      6                      n                      +                      1                      )                          (n+1) \times (6n+1)               (n+1)×(6n+1)。

1. class Solution {
2.     public double[] dicesProbability(int n) {
3.         // 特判，当 n 为 0 时，返回空数组
4.         if (n == 0) {
5.             return new double[0];
6.         }
8.         // 创建一个二维数组 dp，dp[i][j] 表示投掷 i 个骰子，点数之和为 j 的次数
9.         int[][] dp = new int[n + 1][6 * n + 1];
11.         // 初始化只投掷一个骰子的情况，即 dp[1][1~6] = 1
12.         for (int i = 1; i <= 6; i++) {
13.             dp[1][i] = 1;
14.         }
16.         // 从投掷两个骰子开始，逐渐增加骰子个数
17.         for (int i = 2; i <= n; i++) {
18.             // 对于每个骰子数之和 j，枚举最后一个骰子的点数 k
19.             for (int j = i; j <= 6 * n; j++) {
20.                 for (int k = 1; k <= 6; k++) {
21.                     // 如果 j 大于等于 k，则 j-k 是一个合法的下标
22.                     if (j >= k) {
23.                         // 计算投掷 i 个骰子，点数之和为 j 的次数
24.                         dp[i][j] += dp[i - 1][j - k];
25.                     }
26.                 }
27.             }
28.         }
30.         // 计算所有情况的可能性总数，即 6 的 n 次方
31.         double count = Math.pow(6, n);
33.         // 创建一个长度为 5*n+1 的数组 res，用于存储所有可能点数的概率
34.         double[] res = new double[5 * n + 1];
35.         int index = 0;
36.         // 枚举所有可能点数 i，将 dp[n][i] 除以总次数 count 得到概率
37.         for (int i = n; i <= 6 * n; i++) {
38.             res[index++] = dp[n][i] / count;
39.         }
41.         return res;
42.     }
43. }

复制代码

4. 探求两个正序数组的中位数

   标题：给定两个巨细分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
表明：归并数组 = [1,2,3] ，中位数 2
    思绪分析： 假设我们要找出两个数组中的第k小的数，我们可以比力两个数组的中位数mid1和mid2，假设mid1小于mid2，则nums1中前k/2个元素肯定不大概是第k小的数（由于nums1中前k/2个元素加上nums2中前k/2个元素最多只能构成k个元素，而这k个元素中已经有mid1和mid2了，因此nums1中前k/2个元素肯定不大概是第k小的数），因此我们可以将这些元素删除。此时，我们必要在nums1的剩余元素和nums2中查找第k-k/2小的数，这可以通过递归实现。为了克制每次都将数组的前k/2个元素都复制到一个新的数组中，我们可以使用指针来标记当前查找的地区，在每次递归调用时调解指针即可。具体来说，我们可以编写一个名为findK的函数，该函数吸收四个参数：数组nums1、数组nums2、两个指针l1和l2，以及要查找的第k小的数。函数的返回值是两个数组中第k小的数。在每次递归调用中，我们必要判定各种边界条件，以克制出现数组下标越界等错误。此中，假如k=1，则阐明我们已经找到了当前查找的中位数，此时只必要返回两个数组中较小的谁人元素即可。假如删除这个条件，则在递归查找的过程中无法正确判定何时已经找到了中位数，从而导致错误的效果。在盘算中位数时，我们必要分别处理处罚数组长度为奇数和偶数的情况。假如数组长度为奇数，则中位数是第(len+1)/2个元素；假如数组长度为偶数，则中位数是第len/2个元素和第(len+2)/2个元素的均匀值。末了，我们可以编写一个名为findMedianSortedArrays的函数，该函数吸收两个已排序的数组nums1和nums2，并返回它们的中位数。

1. class Solution {
2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3.         // 计算两个数组的总长度
4.         int len = nums1.length + nums2.length;
5.         // 如果总长度为奇数，则中位数是第(len+1)/2个数
6.         if (len % 2 == 1) {
7.             return findK(nums1, 0, nums2, 0, (len + 1) / 2) * 1.0;
8.         } else { // 如果总长度为偶数，则中位数是第len/2个数和第(len+2)/2个数的平均值
9.             return (findK(nums1, 0, nums2, 0, len / 2) + findK(nums1, 0, nums2, 0, (len + 2) / 2)) * 0.5;
10.         }
11.     }
13.     // 在两个数组中查找第k小的数
14.     private int findK(int[] nums1, int l1, int[] nums2, int l2, int k) {
15.         // 如果nums1中已经没有元素，则第k小的数在nums2中
16.         if (l1 >= nums1.length) {
17.             return nums2[l2 + k - 1];
18.         }
20.         // 如果nums2中已经没有元素，则第k小的数在nums1中
21.         if (l2 >= nums2.length) {
22.             return nums1[l1 + k - 1];
23.         }
25.         // 如果k=1，则第k小的数就是nums1和nums2中较小的那个
26.         if (k == 1) {
27.             return Math.min(nums1[l1], nums2[l2]);
28.         }
30.         // 在nums1和nums2中各取k/2个元素进行比较
31.         int mid1 = Integer.MAX_VALUE;
32.         int mid2 = Integer.MAX_VALUE;
33.         if (nums1.length - l1 >= k / 2) {
34.             mid1 = nums1[l1 + k / 2 - 1];
35.         }
37.         if (nums2.length - l2 >= k / 2) {
38.             mid2 = nums2[l2 + k / 2 - 1];
39.         }
41.         // 如果nums1中的中位数小于nums2中的中位数，则第k小的数一定不在nums1的前k/2个元素中，可以排除这些元素，继续在剩余的元素中查找第k-k/2小的数；否则第k小的数一定不在nums2的前k/2个元素中，可以排除这些元素，继续在剩余的元素中查找第k-k/2小的数
42.         if (mid1 < mid2) {
43.             return findK(nums1, l1 + k / 2, nums2, l2, k - k / 2);
44.         } else {
45.             return findK(nums1, l1, nums2, l2 + k / 2, k - k / 2);
46.         }
47.     }
48. }

复制代码

96. 差别的二叉搜刮树

   标题：给你一个整数
返回满意题意的二叉搜刮树的种数。
示例 1：
输入：n = 3
输出：5
    思绪分析： 使用一个一维数组 dp 来记
  [code][/code]