Leetcode hot topic 100 topic 21-25 solution

T24 53. Maximum number of words and （ secondary ）

Topic presentation ：

Power button https://leetcode-cn.com/problems/maximum-subarray/

Ideas 1

Use a two-dimensional array log[i][j], Record No. i The number to the first j The number and . Traversing the upper triangle of a two-dimensional array , Find the maximum fields and .

When submitting a topic , Show Memory limit exceeded .

        Considering the formula of the above formula （2）, When traversing the current i when , Before i-1 Row access data is not used , So change the two-dimensional array to one-dimensional array log[i]. Only record the current from i The sum of numbers as the starting point . When submitting a topic , Show Time limit exceeded .

      After reading the solution , reflection ： If the current sum is negative , Then there is no need to traverse . So you can just jump out of the loop . Submit the title , Still show Time limit exceeded .（ reason ： If it's all positive , Then we have to traverse n The square of . But the answer has been found in the first iteration ）

        So I used the answer in the comment area , One pass traversal . If sum<0, Explain that the previous numbers are useless , You can change the next number to start traversing . Until it reaches the end .

The code is as follows ：

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int max = nums[0];
      
        int sum = 0;
        for(int i = 0;i<len;i++){
            sum+=nums[i];
            max = Math.max(sum,max);
            if(sum<0)
                sum = 0;
        }
        return max;

    }
}

 T25 55. Jumping game （ secondary ）

Topic presentation ： Power button https://leetcode-cn.com/problems/jump-game/

Ideas 1（dfs）

        Use dfs, But you don't need to visit the location you have already visited , So set a visit The array is used to record whether the current position is accessed . If the current location has been accessed , No longer continue to access from the current location .

Code display ：

class Solution {
    
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int i;
        int[] visit = new int[len];
        for(i = 0;i<=nums[0];i++){
            if(visit[i]!=1){
                visit[i] = 1;
                if(dfs(nums,i,len,visit)==true)
                    return true;
            }  
        }
        return false;
    }
    public boolean dfs(int[] nums,int cur,int len,int[] visit){
        if(cur==len-1)
            return true;
        else if(cur<len-1){
            for(int i=1;i<=nums[cur];i++){
                if(visit[cur+i]!=1){
                    visit[cur+i] = 1;
                    if(dfs(nums,cur+i,len,visit)==true){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

Ideas 2（bfs）

        Using queues to achieve breadth traversal , Also set a visit Array , Used to record whether the current location has been accessed , If visited , You don't need to visit again .

Code implementation ：

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int cur = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        int[] visit = new int[len];
        q.add(0);
        int num = nums[0];
        if(len==1)
            return true;
        while(q.isEmpty()==false){
            num = q.peek();
            for(int i = 1;i<=nums[num];i++){
                if(i+num<=len-1 && visit[i+num]!=1){
                    if(i+num==len-1)
                        return true;
                    q.add(i+num);
                    visit[i+num] = 1;
                }
            }
            q.remove();
        }

        return false;
    }
}

Ideas 3

      Record the maximum location that can be accessed , If the maximum accessible location is greater than or equal to the last location , You can access the last location . So record from the first position , Keep cycling to the maximum position , During the cycle , If the maximum location is updated , Update the value of the maximum position . This method , The time complexity is O(n).

Code display ：

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int cur = 0;// Record the current access location 
        int max = nums[0];// Record the maximum location currently accessible 
        while(cur<=max){ // The key step ！！！
            if(max>=len-1)
                return true;
            int num = nums[cur];
            max = Math.max(max,num+cur);// If the maximum location currently accessible changes , Update the maximum location 
            cur++;
        }

        return false;
    }
}