leetcode热题100专题21-25题解

leetcode热题100专题21-25题解

T24 53.最大字数和（中等）

题目展示：

力扣https://leetcode-cn.com/problems/maximum-subarray/

思路1

用一个二维数组log[i][j]，记录第i个数到第j个数的和。遍历二维数组的上三角,找到最大字段和。

提交题目时，显示超出内存限制。

        考虑到上式的公式（2），当遍历当前i时，之前i-1行存取的数据没有用到，所以将二维数组改成一维数组log[i]。只记录当前从第i个数作为起点的和。提交题目时，显示超出时间限制。

      看了题解以后，思考：如果当前之和为负数，那么就没有遍历下去的必要了。所以可以直接跳出循环。提交题目，仍然显示超出时间限制。（原因：如果全是正数，那么就要遍历n的平方次。但是实际第一趟遍历就已经找到答案了）

       于是用了评论区中的答案，一趟遍历。如果sum<0，说明前面的数都没有用，可以换下一个数开始遍历。直至遍历到最后。

代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int max = nums[0];
      
        int sum = 0;
        for(int i = 0;i 
 
  T25 55. 跳跃游戏（中等） 
 
题目展示：力扣https://leetcode-cn.com/problems/jump-game/
 
思路1（dfs） 
       使用dfs，但是已经访问过的位置不需要再访问了，因此设置一个visit数组用来记录当前位置是否被访问。如果当前位置已经访问过了，就不再从当前位置继续访问了。
 
代码展示：
 
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 
思路2（bfs） 
        用队列来实现广度遍历，同样设置一个visit数组，用来记录当前位置是否访问过，如果访问过了，就不需要再访问了。
 
代码实现：
 
class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int cur = 0;
        Queue q = new linkedList();
        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;
    }
}
 
思路3 
     记录所能访问的最大位置，如果所能访问的最大位置大于等于最后一个位置，则可以访问到最后一个位置。因此从第一个位置记录，一直循环记录到最大位置，在循环的过程中，如果最大位置更新了，就更新最大位置的值。此种方法，时间复杂度为O(n).
 
代码展示：
 
class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int cur = 0;//记录当前访问的位置
        int max = nums[0];//记录当前所能访问的最大位置
        while(cur<=max){ //关键的一步！！！
            if(max>=len-1)
                return true;
            int num = nums[cur];
            max = Math.max(max,num+cur);//如果当前所能访问的最大位置变了，就更新最大位置
            cur++;
        }

        return false;
    }
}
 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://www.54852.com/zaji/5686704.html