Leetcode-470 – Implement Rand10() with Rand7()

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Implement RAND10 with RAND7

Fibonacci numbers

[making address]

Implement RAND10 with RAND7

Fibonacci numbers

[Implement RAND10 with RAND7]

Idea 1: Opportunistic (not strictly solved)

• Online O.J. is really not very smart
• Such probability tests are difficult for him to verify the accuracy of all use cases
• So we can cut corners

 public int rand10(a) {
            int res = 0;
            for(int i = 0; i < 10; i++){
                res += rand7();
            }
            return res % 10 + 1;
        }

Copy the code

• Time complexity O(1)
• Space complexity O(1)

Idea 2: probability conversion

• The probability of rand10 -> rand7 is the same
• I’m not going to write the formula for the sum of probabilities at sign jerry_nju
• You can take a look at this big guy’s problem
• Then we do a bigger conversion to RAND49 -> RAND7

 public int rand10(a) {
            int num = (rand7() - 1) * 7 + rand7();
            while (num > 10) {
                num = (rand7() - 1) * 7 + rand7();
            }
            return num;
        }
Copy the code

• Time complexity O(1)
• Space complexity O(1)

Idea 3: The optimization of idea 2

• We can drop nine numbers and just take forty

public int rand10(a) {
            int num = (rand7() - 1) * 7 + rand7();
            while (num > 40) {
                num = (rand7() - 1) * 7 + rand7();
            }
            return 1 + num % 10;
        }
Copy the code

• Time complexity O(1)
• Space complexity O(1)

Train of thought 4: Train of thought 3 optimization

• It’s the same idea
• The code is also CV from the understanding is not complicated, but I did not think of this problem
• It’s more math. I’m not really good at it

public int rand10(a) {
            while (true) {
                int num = (rand7() - 1) * 7 + rand7();
                // If it is below 40, return directly
                if (num <= 40) return 1 + num % 10;
                // generate a random number between 41 and 49
                num = (num - 40 - 1) * 7 + rand7();
                if (num <= 60) return 1 + num % 10;
                < span style = "max-width: 100%; clear: both
                num = (num - 60 - 1) * 7 + rand7();
                if (num <= 20) return 1 + num % 10; }}Copy the code

• Time complexity O(1)
• Space complexity O(1)

[Fibonacci sequence]

Idea 1: dynamic programming + scrolling array

• The Fibonacci sequence only relates to the first two numbers, so define two states
• Some dimension optimization is similar to the knapsack problem

 public int[] smallestK(int[] arr, int k) {
            int[] f = new int[] {0.1};
        int mod = (int) 1e9 + 7;

        public int fib(int n) {
            if (n < 2) {
                return f[n];
            }
            for (int i = 2; i <= n; i++) {
                f[i & 1] = (f[0] + f[1]) % mod;
            }
            return f[n & 1] % mod; }}Copy the code

• Time complexity O(n)
• Space complexity O(1)

Idea 2: Matrix fast powers

• I forgot that you could use matrix powers
• The specific code can refer to the three Leaf big guy’s problem solving code
• I’m not going to write CV here
• It’s pretty easy to understand this simple two-dimensional multiplication after learning modern times
• Time complexity O(LGN)
• Space complexity O(1)