当前位置：网站首页>[leetcode] longest increasing subsequence problem and its application

[leetcode] longest increasing subsequence problem and its application

2022-06-23 05:20:00 【Xiaozhu Xiaozhu will never admit defeat】

List of articles

- - The longest increasing subsequence problem and its application

The longest increasing subsequence problem and its application

300. The longest increasing subsequence

Please refer to 【Leetcode】 Calculate longest series （ Dynamic programming ） Chinese vs 300. The longest increasing subsequence Explanation . There are two main ways to solve problems ： Dynamic programming 、 greedy + Two points search .

Interview questions 17.08. Circus tower

1. Title Description

leetcode link ： Interview questions 17.08. Circus tower
Insert picture description here

2. Thought analysis

The topic should be in 2 On dimensions ( Height + weight ) At the same time, keep strictly increasing .

Then we can arrange one of the dimensions in order , To ensure that it keeps increasing in one dimension （ This is not strictly incremental ）; Then you can focus on another dimension .

Rank the height and weight first , In ascending order of height , Same height , Weight in descending order , Here you can use a two-dimensional array lambda Expression writing . You can refer to ：Java Array 、ArrayList、HashMap Sort the summary .

Then we calculate the longest increasing subsequence . The height is in ascending order , Just judge your weight . To deal with the problem of weight is to deal with the problem of the longest increasing subsequence .

Refer to the solution of the longest increasing subsequence .

3. Reference code

Method 1 ： Dynamic programming （ Overtime ）

class Solution {
    
    public int bestSeqAtIndex(int[] height, int[] weight) {
    
        int n = height.length;
        int[][] person = new int[n][2];
        for (int i = 0; i < n; i++) {
    
            person[i] = new int[]{
    height[i], weight[i]};
        }
        //  Same height , Weight descending 
        Arrays.sort(person, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int i = 0; i < n; i++) {
    
            for (int j = 0; j < i; j++) {
    
                if (person[i][1] > person[j][1]) {
    
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(dp[i], res); 
        }
        return res;
    }
}

Method 2 ： greedy + Two points search

class Solution {
    
    public int bestSeqAtIndex(int[] height, int[] weight) {
    
        int n = height.length;
        int[][] person = new int[n][2];
        for (int i = 0; i < n; i++) {
    
            person[i] = new int[]{
    height[i], weight[i]};
        }
        //  Same height , Weight descending 
        Arrays.sort(person, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int[] per : person) {
    
            int left = 0, right = res;
            while (left < right) {
    
                int mid = (right - left) / 2 + left;
                if (dp[mid] < per[1]) {
      //  What I'm looking for is dp The first in the array is smaller than the current h The location of 
                    left = mid + 1;
                } else {
    
                    right = mid;
                }
            }
            dp[left] = per[1];
            if (res == left) res++;
        }
        return res;
    }
}

Binary search can be adjusted directly API：

Find the specified elements in the ordered array by dichotomy , And returns the subscript of the element .

If the element exists in the array , The subscript of the element in the array will be returned
If the element does not exist in the array , Will return -( The insertion point + 1)

int res1 = Arrays.binarySearch(int[] arr, int key);  //  By default, the entire array is searched 
int res2 = Arrays.binarySearch(int[] arr, int fromIndex, int toIndex, int key);  //  Search the array within the specified index

class Solution {
    
    public int bestSeqAtIndex(int[] height, int[] weight) {
    
        int n = height.length;
        int[][] person = new int[n][2];
        for (int i = 0; i < n; i++) {
    
            person[i] = new int[]{
    height[i], weight[i]};
        }
        //  Same height , Weight descending 
        Arrays.sort(person, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int[] per : person) {
    
            int i = Arrays.binarySearch(dp, 0, res, per[1]);
            if (i < 0) i = -(i + 1); //  If not 
            dp[i] = per[1];
            if (i == res) res++;
        }
        return res;
    }
}

354. The envelope problem of Russian Dolls

1. Title Description

leetcode link ：354. The envelope problem of Russian Dolls
Insert picture description here

2. Thought analysis

Same as the previous question , Only the height and weight range is changed into the length and width of the envelope , The method is exactly the same .

Direct dynamic planning will time out , So you can still use binary search to optimize .

3. Reference code

class Solution {
    
    public int maxEnvelopes(int[][] envelopes) {
    
        int n = envelopes.length;
        Arrays.sort(envelopes, (a, b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
        int[] dp = new int[n];
        Arrays.fill(dp, 1); //  Initialize to 1, Represents the current envelope 
        int max = 0;
        //  Two points search 
        for (int[] env : envelopes) {
    
            int left = 0, right = max;
            while (left < right) {
    
                int mid = (right - left) / 2 + left;
                if (dp[mid] < env[1]) {
      //  What I'm looking for is dp The first in the array is smaller than the current h The location of 
                    left = mid + 1;
                } else {
    
                    right = mid;
                }
            }
            dp[left] = env[1];
            if (left == max) {
    
                max++;
            }
        }
        return max;
    }
}