This is the 13th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

N dice

Sword point Offer 60. n dice roll

Difficulty: Medium

Topic: leetcode-cn.com/problems/ng…

If you throw n dice on the ground, the sum of all the dice facing up is s. Enter n and print the probability of occurrence of all possible values of s.

You need to return the answer with a set of floating-point numbers, where the ith element represents the probability of being the ith smallest in the set of numbers that the n dice can roll.

Example 1:

Input: 1 output: [0.16667, 0.16667, 0.16667, 0.16667, 0.16667, 0.16667]Copy the code

Example 2:

Input: 2 output: [0.02778, 0.05556, 0.08333, 0.11111, 0.13889, 0.16667, 0.13889, 0.11111, 0.08333, 0.05556, 0.02778]Copy the code

Limitation: 1 <= n <= 11

Answer key

N dice, if you use violence, then the time complexity will be O(), which is obviously unrealistic.

Dynamic programming

And since the probability or the sum of the rolls is related to the probability and the sum of the rolls, we can use dynamic programming to solve this problem.

The steps are as follows:

  • Set DP to the probability of the sum of the dice in each roll. The initial sum of the dice is 1 to 6.

  • I’m going to roll it based on how many times I roll the dice

    • Set TMP to the probability of the sum of the rolls of the die, starting with all zeros. If you roll 5 dice and you get all 5 ones, you get the minimum sum of 5, so it’s not hard to figure out that the minimum sum is 6n minus n plus 1 is 5n plus 1.
    • Depending on the last DP result, it alternates with TMP [I] for each roll of the die, since the new die can only be rolled from 1 to 6, so “last result /6” is added for each TMP advance.
    • After calculating TMP, assign TMP to DP so that it can be used next time.

  • At the end of the traversal, return DP.

 / * * *@param {number} n
  * @return {number[]}* /
 var dicesProbability = function (n) {
   let dp = new Array(6).fill(1/6);
   for (let i = 2; i <= n; i++) {
     let tmp = new Array(5 * i + 1).fill(0);
     for (let j = 0; j < dp.length; j++) {
       for (let k = 0; k < 6; k++) {
         tmp[j + k] += dp[j] / 6;
       }
     }
     dp = tmp;
   }
   return dp;
 };
Copy the code
  • Time complexity: O(N^2)
  • Space complexity: O(N)

The straight of a playing card

61. A straight in a playing card

Difficulty: Easy

Topic: leetcode-cn.com/problems/bu…

Randomly draw 5 cards from the playing cards, to determine whether it is a sequence, that is, whether the 5 cards are consecutive. 2 ~ 10 is the number itself, A is 1, J is 11, Q is 12, K is 13, and the large and small wang are both 0, which can be regarded as any number. A cannot be treated as 14.

Example 1:

Input: [1,2,3,4,5] output: TrueCopy the code

Example 2:

Input: [0,0,1,2,5] output: TrueCopy the code

Restriction: the length of the array is 5 and the value of the number of arrays is 0,13.

Answer key

When I first saw example 2, I wondered why [0,0,1,2,5] is a straight card. In fact, it means that 0 is a wild card. If 0 can be used as any card, it can be regarded as [1,2,3,4,5].

The conditions for judging that 5 cards are straight are as follows:

  • Except for wang, all the other cards are not repeated
  • 5 cards to meet the “largest card – the smallest card (except king) < 5”

Method one set + traversal

  • Use Set to remove the weight
  • Get Max and min while traversing.
 / * * *@param {number[]} nums
  * @return {boolean}* /
 var isStraight = function (nums) {
   const set = new Set(a);let max = 0,
     min = 14;
   for (let num of nums) {
     if (num === 0) continue;
     max = Math.max(max, num);
     min = Math.min(min, num);
     if (set.has(num)) return false;
     set.add(num);
   }
   return max - min < 5;
 };
Copy the code
  • Time complexity: O(N), in this case N is 5
  • Space complexity: O(N)

Method two sort + traversal

  • So let’s sort the array
  • Return false if nums[I] is equal to nums[I +1]
  • After sorting, the last element nums[4] is the highest card, and the last element nums[joker] is the smallest card, where joker is the number of Kings
 var isStraight = function (nums) {
   let joker = 0; // It is used to judge the number of big and small wangs, which is used as the subscript
   nums.sort((a, b) = > a - b); // Remember to add the function in sort()
   // The for loop only needs to determine the first four digits
   for (let i = 0; i < 4; i++) {
     if (nums[i] === 0) joker++;
     else if (nums[i] === nums[i + 1]) return false;
   }
   return nums[4] - nums[joker] < 5;
 };
Copy the code
  • Time complexity: O(NlogN), sort uses quicksort requires O(NlogN)
  • Space complexity: O(1)

Practice daily! The front end small adorable new one, hope can point to like ~