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思路3q = 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; } } 记录所能访问的最大位置,如果所能访问的最大位置大于等于最后一个位置,则可以访问到最后一个位置。因此从第一个位置记录,一直循环记录到最大位置,在循环的过程中,如果最大位置更新了,就更新最大位置的值。此种方法,时间复杂度为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; } }欢迎分享,转载请注明来源:内存溢出
评论列表(0条)