Day 9 of leetcode question brushing

1. Permutation of prime numbers

Please help me to 1 To n  Number design arrangement scheme , Make all of 「 Prime number 」 Should be placed in 「 Prime index 」（ Index from 1 Start ） On ; You need to return the total number of possible solutions .

Let's review 「 Prime number 」： The prime number must be greater than 1 Of , And it cannot be expressed by the product of two positive integers less than it . Because the answer could be big , So please return to the answer   model mod 10^9 + 7  Then the result is .

analysis ：

According to the meaning of the question, prime numbers can only be arranged in the position of prime numbers , Then it has a factorial arrangement of prime numbers , Total number of programmes = Factorial of prime number * Factorial of composite numbers . So first we need to know the number of prime numbers , Define a function to determine whether the current number is a prime number , Then count 1 To n The number of prime numbers , Finally, the total number of schemes is obtained .

class Solution {
    static final int MOD = 1000000007;
    public int numPrimeArrangements(int n) {
        int primeNum = 0;
        for (int i = 1; i <= n ; i++) {
            if (isPrime(i)) primeNum++;
        }
        long res = 1;
        for (int i = primeNum; i > 0; i--) {
            res *= i;
            res = res%MOD;
        }
        int other = n - primeNum;
        for (int i = other; i > 0; i--) {
            res *= i;
            res = res%MOD;
        }
        return (int) res;

    }

    boolean isPrime(int n){
        if (n==1){
            return false;
        }
        else {
            for (int i = 2; i < n; i++) {
                if (n%i==0){
                    return false;
                }
            }
        }
        return true;
    }
}

2. A digit in a sequence of numbers

The numbers are in 0123456789101112131415… Serializes the format of a string into a sequence of characters . In this sequence , The first 5 position （ From the subscript 0 Start counting ） yes 5, The first 13 Is it 1, The first 19 Is it 4, wait .

Please write a function , Ask for any n The number corresponding to bit .

analysis ：

First of all, we need to find the rules in the number sequence ：

Look at the table above , Can launch various  digit  The number of digits below  count Calculation formula ：count=9×start×digit .

Based on the above analysis , The solution can be divided into three steps ：

1. determine n  Where Numbers Of digit , Write it down as digit;
2. determine n  Where Numbers , Write it down as num ;
3. determine n yes num Which digit in , And return the result .

class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (n > count) { // 1.
            n -= count;
            digit += 1;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit; // 2.
        return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
    }
}

3. Make the array the smallest number

Enter an array of nonnegative integers , Put all the numbers in the array together to form a number , Print the smallest of all the numbers that can be spliced .

analysis ：

Two Numbers x ,y, Is to use String Type saved , If x+y<y+x, Then we should put x In front of , According to this rule, the whole array can be sorted , From small to large , Then splice it into a string and return . The steps are generally ：

1. First put the integer array nums Turn into String Array str

2. Use built-in functions to define comparison rules , Yes str Sort

3. Yes, ordered str Traverse , utilize StringBuilder Splice each item

4. Return the spliced value

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
}