“This is the 8th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

takeaway

Fat friends in order to better help new students adapt to the algorithm and questions, recently we began a special assault step by step. We’re going to start with one of the most frustrating types of algorithms, dynamic programming and we’re going to do a 21-day incubation program. What are you waiting for? Come and join us for 21 days of dynamic programming challenge!!

21 Days Dynamic Planning Introduction

Given an integer n, please find and return the NTH ugly number.

Ugly numbers are positive integers that contain only prime factors 2, 3, and/or 5.

The sample1: Enter: n =10Output:12Explanation: [1.2.3.4.5.6.8.9.10.12] is made before10A sequence of ugly numbers.Copy the code
The sample2: Enter: n =1Output:1Explanation:1Usually regarded as an ugly number.Copy the code
class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if(dp[i] == num5) { p5++; }}returndp[n]; }}Copy the code

Given an integer n, how many binary search trees are composed of exactly n nodes with different values from 1 to n? Returns the number of binary search tree species that satisfy the problem.

The sample1: Enter: n =3Output:5
Copy the code
The sample2: Enter: n =1Output:1
Copy the code
class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j]; }}returnG[n]; }}Copy the code

The interview questions

Continue the Linux command series

Process-related commands17The Java Virtual Machine Process Status Tool (JPS) is the Java Development Kit (JDK)1.5Provide a display of all the current Java process PID command, simple and practical, very suitable for Linux/Unix platform on the simple view of the current Java process some simple situation.18-a: all processes are displayed. -A: all processes that are not related to terminal. -u: processes related to A valid user. A long, detailed list of PID informationCopy the code