2021 05 13

The 5 leetcodes sorted out this week are 53-maximum subsequence sum, 78-subset, 77-combination, 46-full permutation and 200-island number respectively.

53 maximum suborder sum

Topic describes

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

• Example 1:

Input: nums = [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.Copy the code

• Example 2:

Input: nums = [1] Output: 1Copy the code

• Example 3:

Input: nums = [0] Output: 0Copy the code

• Example 4:

Input: nums = [-1] Output: -1Copy the code

• Example 5:

Input: nums = [-100000] Output: -100000Copy the code

• Tip:

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
Copy the code

Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution: the violent method

The brute force method is to take the sum of each successive subarray and take the maximum. Use two Pointers I and j to represent the beginning and end of a continuous subarray. Move j back one bit at a time, summing. If j reaches the end, move I back one bit, continuing to compute the sum of all continuous subarrays starting with the following character.

public int maxSubArray(int[] nums){
    int result = Integer.MIN_VALUE;
    int sum = 0;
    for(int i = 0; i < nums.length; ++i){
        // The summation is restarted each time the first element of the subarray changes
        sum = 0;
        for(int j = i; j < nums.length;++j){
            sum += nums[j];
            result = Math.max(result,sum);
        }
    }
    return result;
}
Copy the code

Solution two dynamic programming

Assuming p[I] represents the sum of the largest continuous subsequence ending in nums[I], then for p[I +1], either take nums[I +1] itself or add to p[I], i.e., p[I +1] = Max (nums[I +1],nums[I +1] + p[I]).

Note that p[I] can only calculate the maximum sum of subsequences ending in nums[I]. There are a total of nums.length.

// Dynamic programming
public int maxSubArray(int[] nums) {
    int result = nums[0];
    int sum = nums[0];
    for(int i = 1; i < nums.length; ++i){
        sum = Math.max(sum + nums[i],nums[i]);
        result = Math.max(result,sum);
    }
    return result;
}
Copy the code

Solution: divide and conquer

For a given array, if you split the array from mid into left and right, then there are three possible cases of the maximum suborder sum, and you only need to return the larger values of those three cases.

• Case 1: The largest suborder sum is in the left half

For example, the largest suborder sum of [1,4,-1,2,-2] is on the left, [1,4].

• Case 2: The largest suborder sum is in the right half

For example, the largest suborder sum of [2,-2,-1,4,1] is on the right, [4,1].

• Case 3: Maximum suborder sum spans left and right

For example, the maximum suborder sum of [-2,2,4,1,-1] across the left and right sides is [2,4,1].

Int maxSubArray(int[] nums,int left,int right); The termination condition for recursion is left == right.

In the first two cases, you can make direct recursive calls to get the maximum sum of suborders on the left and right sides. For the third case, which does not follow the rules of recursion, we need to do additional calculations, so let’s focus on the third case.

In the third case, the maximum continuous suborder and the sum of the following two parts:

• The left tomidThe sum of the largest continuous suborder at the end
• The right tomid + 1The sum of the largest continuous suborders at the beginning

For example, [-2,2,4,1,-3,4], the maximum sum of suborders ending in mid on the left is 6; The maximum sum of suborders on the right starting with mid+1 is 2. So the maximum sum across the left and right is 8.

Note that the third case is not the sum of the largest continuous suborders on the left and right sides. This is because the sum of the largest continuous suborder on one side is not necessarily contiguous to the sum of the largest continuous suborder on the other side. For example, in the figure above, the largest continuous suborder on the right is actually [4], but it is not adjacent to [2,4] on the left.

The code implementation is as follows:

/ / the main method
public int maxSubArray(int[] nums){
    return maxSubArray(nums,0,nums.length - 1);
}

public int maxSubArray(int[] nums,int left,int right){
    // Recursive termination condition
    if(left == right){
        return nums[left];
    }
    int mid = left + (right - left)/2;
    int leftMax = maxSubArray(nums,left,mid);
    int rightMax = maxSubArray(nums,mid + 1,right);
    int midMax = midMax(nums,left,mid,right);
    return max(leftMax,rightMax,midMax);
}

// Solve the third case
private int midMax(int[] nums,int left,int mid,int right){
    int leftMax = nums[mid];
    int rightMax = nums[mid + 1];
    int sum = nums[mid];
    int i = 0;
    // start from mid-1 and walk forward
    for(i = mid - 1; i >= left; --i){
        sum += nums[i];
        leftMax = leftMax > sum ? leftMax : sum;
    }
    sum = nums[mid+1];
    // start with mid + 2
    for(i = mid + 2; i <= right; ++i){
        sum += nums[i];
        rightMax = rightMax > sum ? rightMax : sum;
    }
    return leftMax + rightMax;
}

private int max(int a,int b,int c){
    return a > b ? (a > c ? a : c) : (b > c ? b : c);
}

Copy the code

78 a subset

Topic describes

You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

• Example 1:

Output: input: nums = [1, 2, 3], [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]Copy the code

• Example 2:

Nums = [0] Output: [[],[0]]Copy the code

• Tip:

1 <= nums.length <= 10-10 <= nums[I] <= 10 All elements in nums are differentCopy the code

Source: LeetCode link: leetcode-cn.com/problems/su… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Method a DFS

DFS (depth-first search) and backtracking both make use of recursion ideas. We first draw a recursion tree using nums=[1,2,3] as an example.

Since repeating sets are not counted (for example, [1,2] and [2,1] are repeated), we can traverse each time from the next element of the current element, which is why the recursion tree is incomplete due to pruning.

DFS starts at the root of the recursion tree, follows a path to the bottom and back up. So DFS traversal of a subset of the order is [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3].

DFS recursive function is as follows, where:

• resultsRepresents the final result set
• startIndicates where in the array the current path starts traversal
• subsetRepresents a subset of the current path representation

public void dfs(int[] nums,List<List<Integer>> results,int start,List<Integer> subset){
    // Copy a subset to avoid passing references
    results.add(new ArrayList<>(subset));
    // Recursion termination condition, pruning condition
    if(start == nums.length){
        return;
    }
    for(int i = start; i < nums.length; ++i){
        // Continue along the current path until you reach a node and join the subset
        subset.add(nums[i]);
        dfs(nums,results,i+1,subset);
        // After returning to the previous layer, the subset elements added to the current layer need to be removed
        subset.remove(subset.size() - 1); }}Copy the code

Call a recursive function and return the result:

public List<List<Integer>> subsets(int[] nums){
    List<List<Integer>> results = new ArrayList<>();
    dfs(nums,results,0.new ArrayList<Integer>());
    return results;
}
Copy the code

Solution two: backtracking

Backtracking traverses the length of the subset, which can be 1 to nums.length except for empty subsets. If, in traversal recursion, the length of the subset is found to be equal to the length of the current traversal, trace back up one level.

Backtracking traversal produce a subset of the order for the [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3].

The design of the backtracking recursive function is as follows:

• lenRepresents the length of the current subset
• startIndicates the element at which to start traversing and the next time backtracestart + 1No duplicate sets are guaranteed

// backtrace recursive function
public void backtracking(int[] nums,List<List<Integer>> results,int len,int start,List<Integer> subset){
    // Recursive termination condition
    if(len == subset.size()){
        results.add(new ArrayList<>(subset));
        return ;
    }
    for(int i = start; i < nums.length; ++i){
        subset.add(nums[i]); 
        backtracking(nums,results,len,i+1,subset);
        subset.remove(subset.size() - 1); }}Copy the code

Recursive traceback calls to the possible length:

public List<List<Integer>> subsets(int[] nums){
    List<List<Integer>> results = new ArrayList<>();
    results.add(new ArrayList<>());
    for(int i = 1; i <= nums.length; ++i){
        backtracking(nums,results,i,0.new ArrayList<Integer>());
    }
    return results;
}
Copy the code

Solution three extension method

The idea of the extension method is to iterate over a set of numbers, adding the current element to each of the previous subsets to form a new subset, and then merging the previous subset and the new subset into the final subset set.

For example, nums=[1,2,3], the initial subset is [].

• To traverse the1, add the existing subset, get[1], and the previous subset, which is[], [1]
• To traverse the2, add the existing subset, get[2], [1, 2], and the previous subset, which is[], [1], [2], [1, 2]
• To traverse the3, add the existing subset, get[3], [1, 3], [2, 3], [1, 2, 3], and the previous combination, the subset is[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

The extension method is implemented as follows:

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    results.add(new ArrayList<>());

    for(int i = 0; i < nums.length; ++i){
        // Copy the existing subset set
        List<List<Integer>> copied = new ArrayList<>();
        for(List<Integer> list : results){
            ArrayList<Integer> temp = new ArrayList<>(list);
            copied.add(temp);
        }
        // Add the current elements to results
        for(List<Integer> list : copied){ list.add(nums[i]); results.add(list); }}return results;
}
Copy the code

77 combination

Topic describes

Given two integers n and k, return 1… All possible combinations of k numbers in n.

• Example:

Input: n = 4, k = 2 output: [[2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4],]Copy the code

Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution method – retrospective method

The idea and implementation logic of the backtracking method are similar. With the experience of question 78 above, we can also draw the recursion tree of this problem:

The green nodes are recursive trees with n=4 and k=2. The recursive function Combine is defined as follows, and the termination condition of recursion is that the size of the combination is equal to k.

// backtrace recursive function
void combine(List<List<Integer>> results,int n,int k,int start,List<Integer> comb){
   if(comb.size() == k){
       // results.add(comb) causes references to be passed and is not desirable
       results.add(new ArrayList<>(comb));
       return;
   }
   for(inti = start; i <= n; i++){ comb.add(i); combine(results,n,k,i+1,comb);
       // Going back to the previous level, the last element of the combination needs to be removed
       comb.remove(comb.size() - 1); }}/ / the main function
public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> results = new ArrayList();
    combine(results,n,k,1.new ArrayList<>());
    return results;
}
Copy the code

When encountering recursion problems, in addition to recursion trees, I usually draw simple block diagrams like the following to deepen my understanding of the recursion process. The black box represents the invocation of recursive functions, and the statements are executed from top to bottom.

46 permutations

Topic describes

Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.

• Example 1:

Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the code

• Example 2:

Input: nums = [0,1] output: [[0,1],[1,0]Copy the code

• Example 3:

Input: nums = [1] Output: [[1]Copy the code

Source: LeetCode link: leetcode-cn.com/problems/pe… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution method – retrospective method

This problem can also be solved using backtracking. For nums=[1,2,3], draw the recursion tree:

Each path in a recursion tree forms a permutation, and each element appears in the permutation, but in a different order. So when you find a path with duplicate elements, you prune it.

The recursive function is simpler than the previous ones. The recursive function terminates when the size of the current array is equal to the length of the array, i.e. all elements are in the array.

// backtrace recursive function
public void permute(List<List<Integer>> results,int[] nums, List<Integer> ans){
    if(ans.size() == nums.length){
        results.add(new ArrayList<>(ans));
        return;
    }
    for(int i = 0; i < nums.length; i++){
        // Prune the path if it already exists in the permutation
        if(! ans.contains(nums[i])){ ans.add(nums[i]); permute(results,nums,ans); ans.remove(ans.size() -1); }}}Copy the code

Call a recursive function to solve:

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    permute(results,nums,new ArrayList<>());
    return results;
}
Copy the code

Number of 200 islands

Topic describes

Given a two-dimensional grid of ‘1’ (land) and ‘0’ (water), count the number of islands in the grid.

Islands are always surrounded by water, and each island can only be formed by connecting adjacent lands horizontally and/or vertically. Furthermore, you can assume that all four sides of the grid are surrounded by water.

• Example 1:

Input: the grid = [[" 1 ", "1", "1", "1", "0"], [" 1 ", "1", "0", "1", "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "0" and "0", "0"]] output: 1Copy the code

• Example 2:

Input: the grid = [[" 1 ", "1", "0" and "0" and "0"], [" 1 ", "1", "0" and "0" and "0"], [" 0 "and" 0 ", "1", "0" and "0"], [" 0 "and" 0 ", "0", "1", "1"]] output: 3Copy the code

• Tip:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i] [j] with a value of '0' or '1'Copy the code

Source: LeetCode link: leetcode-cn.com/problems/nu… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Method a BFS

An island is either surrounded by a boundary or a ‘0’. If you walk through the array and find land, it becomes ‘0’, and if there’s land around it, it becomes ‘0’, so when there’s no land around, you find an entire island, and since it’s all turned into water, it doesn’t conflict with the next island. Until the end of the iteration.

The process of turning the land around the land into an island until there is no land around it can use BFS breadth first search, which is usually used with queues.

If a ‘1’ is encountered while traversing a two-dimensional array, do the following:

• Number of islands plus 1
• Enqueue current element (element’s row and column number)
• Sets the current element to'0'That is, it becomes water
• The queue is traversed until it is empty
  • Take out the first element of the queue, if there is land around (up, down, left, right), add the surrounding elements to the queue and change to'0'.

The implementation code is as follows:

// Method 1 BFS idea
public int numIslands(char[][] grid) {
    Queue<Pos> queue = new LinkedList<>();
    int result = 0;
    for(int i = 0; i < grid.length; i++){
        for(int j = 0; j < grid[0].length; j++){
            if('1' == grid[i][j]){
                result++;
                queue.offer(new Pos(i,j));
                grid[i][j] = '0';
                while(! queue.isEmpty()){ Pos pos = queue.poll();if(pos.x - 1> =0 && grid[pos.x - 1][pos.y] == '1'){
                        queue.add(new Pos(pos.x - 1, pos.y));
                        grid[pos.x - 1][pos.y] = '0';
                    }
                    if(pos.x + 1 < grid.length && grid[pos.x + 1][pos.y] == '1'){
                        queue.add(new Pos(pos.x + 1, pos.y));
                        grid[pos.x + 1][pos.y] = '0';
                    }
                    if(pos.y - 1> =0 && grid[pos.x][pos.y - 1] = ='1'){
                        queue.add(new Pos(pos.x, pos.y - 1));
                        grid[pos.x][pos.y - 1] = '0';
                    }
                    if(pos.y + 1 < grid[0].length && grid[pos.x][pos.y + 1] = ='1'){
                        queue.add(new Pos(pos.x, pos.y + 1));
                            grid[pos.x][pos.y + 1] = '0';
                        }
                    }
                }
            }
        }
        return result;
    }
Copy the code

When a land mass is encountered, it must be part of an island (so the number of islands is increased by 1), spreading out in all directions until it is surrounded by water.

Method two DFS

In the process of extension, you can also use the DFS idea, recursive calls. The recursive function DFS is to set the current element to ‘0’ and recursively expand the directions around it, terminating the recursion if it is surrounded by a boundary or water.

// DFS recursive function
void dfs(char[][] grid, int row, int col){
    if(row < 0 || row > grid.length - 1 || col < 0 || col > grid[0].length - 1 || grid[row][col] == '0') {return;
    }
    grid[row][col] = '0';
    dfs(grid,row - 1,col);
    dfs(grid,row + 1,col);
    dfs(grid,row,col - 1);
    dfs(grid,row,col + 1);
}
Copy the code

Iterate over a two-dimensional array and call DFS when you encounter land.

// Method 2 DFS idea
public int numIslands(char[][] grid) {
    int result = 0;
    for(int i = 0; i < grid.length; i++){
        for(int j = 0; j < grid[0].length; j++){
            if('1'==grid[i][j]){ result++; dfs(grid,i,j); }}}return result;
}
Copy the code

Solution of three union search set

This problem can also be solved by using and looking up UnionFind, which is more complicated, but it’s a good way to understand and look up the idea of UnionFind.

We can map the two-dimensional array of islands to a one-dimensional array root, whose length is Row *col (where row and col are the rows and rows of the two-dimensional array) for each element of the two-dimensional array.

Root [I] indicates the index of the ancestor of the ith element. If I ==root[I], then the ancestor of the ith element is root[I]. For example, root = [1,2,2], the ancestor of the 0th element is root[0] = 1, and the ancestor of the first element is root[1] = 2, and 2 == root[2], indicating that all three elements in the array have the same ancestor 2.

Returning to the question of islands, if some of the land elements share a common ancestor, then they can be considered an island.

Let’s define root in a look-up set class. The unionfind.class definition can be thought of as a template with a find(x) and union(x,y) method for query and merge operations, respectively.

// Look up the set template class
class UnionFind{
    public UnionFind(char[][] grid){}

    public int find(int x){}

    public void union(int x, int y){}}Copy the code

In the island problem, and lookup sets need to define two members:

• root[]: array, maps a two-dimensional array, and records the ancestor of the element
• count: integer. The default value is the number of elements in a two-dimensional arrayNumber of mergers

In the constructor, you initialize root, count, default root[I] = I, that is, you are your ancestor.

// Constructor of unionfind.class
public UnionFind(char[][] grid){
    int eles = grid.length * grid[0].length;
    count = eles;
    root = new int[eles];
    for(int i = 0; i < root.length; i++){ root[i] = i; }}Copy the code

Find (x) recursively finds the ancestor of the x-th element.

/** Recursively find the ancestor of X */
public int find(int x){
    if(x == root[x]){
        return x;
    }
    root[x] = find(root[x]);
    return root[x];
}
Copy the code

The function of union(x,y) is to assimilate x and Y so that their ancestors are the same.

public void union(int x, int y){
    int rootX = find(x);
    int rootY = find(y);
    if(rootX != rootY){
        root[rootX] = rootY;
        count--;
    }
}
Copy the code

Unionfind.class should also provide a getCount() function to get the count. (Or you can make count public).

After looking at the code and looking up the set, the following is to use and looking up the set to solve the island number problem.

First define a variable waters to represent the number of 0, traversing the two-dimensional array:

• If it’s water,waters++
• If it is land, the current element is carried out separately with the four elements up, down and leftunionoperation
• The final number of islands isunionFind.count - waters

Why is the number of islands count-waters? We assume that the number of elements in the two-dimensional array is N, and there are waters elements. An island with n elements needs to merge n minus 1 times. That is, the number of final islands = n-waters-merge times, i.e., count-waters.

// select * from ()
public int numIslands(char[][] grid) {
    int waters = 0;
    UnionFind uf = new UnionFind(grid);
    for(int i = 0; i < grid.length; i++){
        for(int j = 0; j < grid[0].length; j++){
            if(grid[i][j] == '0'){
                waters++;
            }else {
                operateDir(uf,grid,i,j,-1.0);
                operateDir(uf,grid,i,j,1.0);
                operateDir(uf,grid,i,j,0, -1);
                operateDir(uf,grid,i,j,0.1); }}}return uf.getCount() - waters;
}

// Perform assimilation merge on a direction
private void operateDir(UnionFind uf,char[][] grid,int i,int j,int xDir,int yDir){
    int x = i + xDir;
    int y = j + yDir;
    if(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == '1'){
        uf.union(x*grid[0].length + y,i*grid[0].length+j); }}Copy the code