Leetcode 300 longest increasing subsequence (greedy + binary search for the first element subscript smaller than nums[i]), leetcode 200 island number (deep search), leetcode 494 target sum (DFS backtr

Top 1：LeetCode 300 The longest increasing subsequence （ greedy + Two points search ）

Title Description ：
Give you an array of integers nums , Find the length of the longest strictly increasing subsequence .
Subsequence Is a sequence derived from an array , Delete （ Or do not delete ） Elements in an array without changing the order of the rest . for example ,[3,6,2,7] It's an array [0,3,1,6,2,2,7] The subsequence .

Example 1：
Input ：nums = [10,9,2,5,3,7,101,18]
Output ：4
explain ： The longest increasing subsequence is [2,3,7,101], So the length is 4 .

Example 2：
Input ：nums = [0,1,0,3,2,3]
Output ：4

Example 3：
Input ：nums = [7,7,7,7,7,7,7]
Output ：1

Dichotomy finds subscript links of elements that meet conditions ： Dichotomy

One 、 Let the length of the longest ascending subsequence calculated at present be len（ At the beginning len=1,） Construct an incremental list d（d[1]=nums[0]）

Two 、 encounter nums[i] When , If nums[i]>d[len] Just update d[++len] = nums[i]; otherwise , stay d Array The binary search finds the first ratio nums[i] Small subscript element pos, And update the d[pos + 1] = nums[i]（ Replace the corresponding element ）

Binary search in the incremental list The first one is better than nums[i] Small subscript element The code is as follows ：

int l = 1, r = len, pos = 0;
while (l <= r) {
    
    int mid = (l + r) >> 1;
    if (d[mid] < nums[i]) {
    
        pos = mid;
        l = mid + 1;
    } else {
    
        r = mid - 1;
    }
}
d[pos + 1] = nums[i];   //  No instructions found d[] All the numbers in it are better than nums[i] Big , Update at this time d[1]【nums[i] The corresponding is d[i+1]】

3、 ... and 、 initial pos=0 To prevent while Circular dichotomy cannot be found （ That is, all elements are better than nums[i] Big ）, Update when d[0+1]=nums[i]

Understanding ：

0 8 4 12 2 3 4 Updated to 0 3 4 But it doesn't affect the result 【 At first, only maintenance 0 4 12 to update 12 Previous （ Meet the ratio 12 Big ones are also updated 12）
So the enterprise level understanding is as follows ：

Dichotomy to find the first ratio nums[i] Small element subscripts understand ：

When l=1,r=len=8 When subscribing , The following table and divide by two Get is In the middle of the and The element subscript at the end of the upper half
For example, we insert 2 go in , according to d[mid]<nums[i] Just pos=mid,+1,else Just -1 The logic of , When 2=2 yes -1, I found it pos, next l+1 Jump out of while（l<=r） loop , I found it 1 Subscript of element 1

• Time complexity ： Array nums The length of is n, We use the elements in the array to update d Array , And update d Array needs to be O(logn) Binary search , So the total time complexity is O(nlogn).
• Spatial complexity ： Additional length required is n+1 Of d Array .

You can use the complete code ：

public int lengthOfLIS(int[] nums) {
    
    int len = 1, n = nums.length;
    if (n == 0) return 0;
    int[] d = new int[n + 1];
    d[len] = nums[0];
    for (int i = 1; i < n; i++) {
    
        if (nums[i] > d[len]) {
    
            d[++len] = nums[i];
        } else {
    
            int l = 1, r = len, pos = 0;
            while (l <= r) {
    
                int mid = (l + r) >> 1;
                if (d[mid] < nums[i]) {
    
                    pos = mid;
                    l = mid + 1;
                } else {
    
                    r = mid - 1;
                }
            }
            d[pos + 1] = nums[i];   //  No instructions found d[] All the numbers in it are better than nums[i] Big , Update at this time d[1]【nums[i] The corresponding is d[i+1]】
        }
    }
    return len;
}

Top2：LeetCode 200 Number of Islands （ Deep search ）

Title Description ：
Here you are ‘1’（ land ） and ‘0’（ water ） A two-dimensional mesh of , Please calculate the number of islands in the grid .

Islands are always surrounded by water , And each island can only be Horizontal direction and / Or adjacent vertically The land connection formed .

Besides , You can assume that all four sides of the mesh are surrounded by water .

Example 1：
Input ：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
Output ：1

Example 2：
Input ：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
Output ：3

One 、 double for Loop through the entire grid , If grid[r][c] == '1' Just num_isLand++, then dfs Search up and down, left and right ’0’, Cut off conditions are To the border and grid[r][c]=='0'

• Time complexity ：O（MN）, among M and N They are the number of rows and the number of columns .【 This is not very understandable , Reference resources Full Permutation ： The time complexity of recursion 】
• Spatial complexity ：O（MN）, In the worst case , The whole grid is land , The depth first search reaches MN

You can use the complete code

public int numIslands(char[][] grid) {
    
    if (grid == null || grid.length == 0) return 0;
    int nr = grid.length;
    int nc = grid[0].length;
    int numIslands = 0;
    for (int r = 0; r < nr; r++) {
    
        for (int c = 0; c < nc; c++) {
    
            if (grid[r][c] == '1') {
    
                numIslands++;
                dfs(grid, r, c);
            }
        }
    }
    return numIslands;
}

private void dfs(char[][] grid, int r, int c) {
    
    int nr = grid.length;
    int nc = grid[0].length;
    if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
    
        return;
    }
    grid[r][c] = '0';
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

Top3：LeetCode 494 Objectives and （dfs to flash back ）

Title Description ：
Give you an array of integers nums And an integer target .

Add... Before each integer in the array ‘+’ or ‘-’ , And then concatenate all the integers , You can construct a expression ：

for example ,nums = [2, 1] , Can be in 2 Before adding ‘+’ , stay 1 Before adding ‘-’ , And then concatenate them to get the expression “+2-1” .
Returns the 、 The result is equal to target Different expression Number of .

Example 1：
Input ：nums = [1,1,1,1,1], target = 3
Output ：5
explain ： Altogether 5 Ways to make the ultimate goal and 3 .
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Example 2：
Input ：nums = [1], target = 1
Output ：1

One 、 Array nums You can add symbols to every element of the + or -, So each element has 2 A way to add symbols ,n Total number 2^n A way to add symbols

Backtracking process dfs（nums,target,index,sum） Maintain a counter in count, When encountering an expression, the result is equal to the target number target when , take count The value of the add 11. After traversing all the expressions , The result is equal to the target number target Number of expressions .

• Time complexity ： Backtracking involves traversing all the different expressions , share 2^n Two different expressions , among n yes nums.length, So the total time complexity is O（2 Of n Power ）
• Spatial complexity ： The space complexity mainly depends on the stack space of recursive calls , The depth of the stack does not exceed n. So for O（n）

You can use the complete code ：

int count = 0;
public int findTargetSumWays(int[] nums, int target) {
    
    backtrack(nums, target, 0, 0);
    return count;
}

private void backtrack(int[] nums, int target, int index, int sum) {
    
    if (index == nums.length) {
    
        if (sum == target) count++;
    } else {
    
        backtrack(nums, target, index + 1, sum + nums[index]);
        backtrack(nums, target, index + 1, sum - nums[index]);
    }
}