Day 12 of leetcode + day 1 of DL

DL

1. What is over fitting ?

Because the model is too complex , Model learning ability is too strong , The data used for training is relatively simple compared with complex models , Therefore, the model learns that there is noise in the data , What the model learns is not the true distribution of the data set .

Over fitting means that the accuracy of the model in the training set is very high , But it is very low in the test set .

2. Causes of over fitting ?

Data is relatively limited , Simple ,  But the model structure is too complex .

3. What are the ways to solve the problem of fitting ?

Add data   Data enhancement , Theoretically, as long as there is enough data , There will be no fitting and under fitting .

Use small models , L1 and L2 Regularization ,  Dropout,  increase BN layer ,  Use residual structure ....

Choose the right network structure , By reducing network depth   Increase the number of neurons   Number of full connection layers, etc , Reduce the scale of network parameters .

LeetCode

1. The next bigger element III

Give you a positive integer  n , Please find the smallest integer that meets the conditions , It consists of rearranging  n  Each number present in the consists of , And its value is greater than  n . If there is no such positive integer , Then return to  -1 .

Be careful  , The returned integer should be a  32 An integer  , If there is an answer that satisfies the meaning of the question , But it's not  32 An integer  , Also return to  -1 .

analysis :

Notice that the next spread is always larger than the current spread , Unless the permutation is already the largest permutation . We hope to find a way , Can find a new sequence larger than the current sequence , And the magnitude of the increase is as small as possible . In particular ：

1. We need to put a left 「 Lower decimal 」 With a right 「 Larger number 」 In exchange for , To make the current arrangement larger , So we get the next permutation .
2. And we want this 「 Lower decimal 」 Try to keep to the right , and 「 Larger number 」 As small as possible . When the exchange is complete ,「 Larger number 」 The numbers on the right need to be rearranged in ascending order . This can ensure that the new arrangement is larger than the original arrangement , Make the increase as small as possible .

In order to arrange [4,5,2,6,3,1] For example ：

1. The right couple we can find 「 Lower decimal 」 And 「 Larger number 」 The combination of 2  And 3, Satisfy 「 Lower decimal 」 Try to keep to the right , and 「 Larger number 」 As small as possible .
2. When we complete the exchange, the arrangement becomes [4,5,3,6,2,1], At this point we can rearrange 「 Lower decimal 」 The sequence on the right , The sequence becomes [4,5,3,1,2,6].

In particular , We describe the algorithm as follows , For length is n  Permutation a：

First, find the first sequence pair from back to front (i,i+1), Satisfy a[i] < a[i+1]. such 「 Lower decimal 」 That is to say a[i]. here [i+1,n) It must be a descending sequence .

If a sequence pair is found , So in the interval [i+1,n) Find the first element from back to front j Satisfy a[i] < a[j]. such 「 Larger number 」 That is to say a[j].

In exchange for a[i] And a[j], At this point, it can be proved that the interval [i+1,n) Must be in descending order . We can directly use the double pointer to reverse the interval [i+1,n) Make it in ascending order , There is no need to sort the interval .

class Solution {
    public int nextGreaterElement(int n) {
        char[] nums = Integer.toString(n).toCharArray();
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i < 0) {
            return -1;
        }

        int j = nums.length - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        swap(nums, i, j);
        reverse(nums, i + 1);
        long ans = Long.parseLong(new String(nums));
        return ans > Integer.MAX_VALUE ? -1 : (int) ans;
    }

    public void reverse(char[] nums, int begin) {
        int i = begin, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    public void swap(char[] nums, int i, int j) {
        char temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

2. Ugly number

We will include only qualitative factors 2、3 and 5 The number of is called ugly （Ugly Number）. Seek the order from small to large n Ugly number .

analysis :

The problem of dynamic programming .  Recurrence properties of ugly numbers ： Ugly numbers contain only factors 2, 3, 5, So there is “ Ugly number =  Some clown number × Some factor ”.

Ugly number recurrence formula ：  If index  a,b,c Meet the above conditions , Then the next ugly number ​ In the following three cases   minimum value  :

                ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

 

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
}

3. The first character that appears only once

In string s Find the first character that appears only once . without , Return a single space . s Contains only lowercase letters .

analysis :

First, create a hash table , Traverse s Count for each letter , Then traverse from beginning to end s, Find one whose first count is 1 The letter of .

class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character,Integer> hashMap = new HashMap<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            hashMap.put(chars[i],hashMap.getOrDefault(chars[i],0)+1);
        }
        for (int i = 0; i < chars.length; i++) {
            if (hashMap.get(chars[i])==1){
                return chars[i];
            }
        }
        return ' ';


    }
}

4. Reverse pairs in arrays

Two numbers in an array , If the number in front is greater than the number in the back , Then these two numbers form a reverse order pair . Enter an array , Find the total number of reverse pairs in this array .

analysis :

Divide and conquer + Merge sort .

class Solution {
    int[] nums, tmp;
    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length - 1);
    }
    private int mergeSort(int l, int r) {
        //  Termination conditions 
        if (l >= r) return 0;
        //  Recursive partition 
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        //  Consolidation phase 
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = nums[k];
        for (int k = l; k <= r; k++) {
            if (i == m + 1)
                nums[k] = tmp[j++];
            else if (j == r + 1 || tmp[i] <= tmp[j])
                nums[k] = tmp[i++];
            else {
                nums[k] = tmp[j++];
                res += m - i + 1; //  Statistical reverse order pair 
            }
        }
        return res;
    }
}