leetcode-53-55-56-62-64

leetcode53题55题56题62题64题

leetcode53题(最大子序和):

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
var maxSubArray = function(nums) {
var sum = nums[0];
var maxSum = Math.max(sum,-Infinity);
for(var i=1;i<nums.length;i++){
if(sum<0){
sum = nums[i];
}else{
sum = sum + nums[i];
}
maxSum = Math.max(sum,maxSum);
}
return maxSum;
};

leetcode55题(跳跃游戏):

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

解答:
1
2
3
4
5
6
7
8
9
10
11
12
var canJump = function(nums) {
var k = 0;//k表示目前能跳到的最远的位置
for(var i=0;i<nums.length;i++){
//如果前面最远能调到的位置小于i,表示无法到达i位置
if(i>k){
return false;
}
//在i时的时候最远能调到k位置
k = Math.max(k,nums[i]+i);
}
return true;
};

leetcode56题(合并区间):

给出一个区间的集合,请合并所有重叠的区间。

示例:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var merge = function(intervals) {
var result = [];
intervals.sort(compare);
var i=0;
var len = intervals.length;
while(i<len){
var currLeft = intervals[i][0];
var currRight = intervals[i][1];
while(i<len-1&&intervals[i+1][0]<=currRight){
i++;
currRight = Math.max(currRight,intervals[i][1]);
}
result.push([currLeft,currRight]);
i++;
}
return result;
};
function compare(arr1,arr2){
return arr1[0]-arr2[0];
}

leetcode62题(不同路径):

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

问总共有多少条不同的路径?

图

示例:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

输入: m = 7, n = 3
输出: 28

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//解法一,这里采用的数组为二维数组
var uniquePaths = function(m, n) {
var dp = [];
for(var i=0;i<m;i++){
dp[i] = [];
for(var j=0;j<n;j++){
dp[i][j] = 0;
}
}
for(var i=0;i<m;i++){
for(var j=0;j<n;j++){
if(i==0&&j==0){
dp[i][j] = 1;
}else if(i==0&&j!=0){
dp[i][j] = dp[i][j-1];
}else if(i!=0&&j==0){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = dp[i][j-1]+dp[i-1][j];
}
}
}
return dp[m-1][n-1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var uniquePaths = function(m, n) {
if(m<=0||n<=0){
return 0;
}
if(m==1||n==1){
return 1;
}
var dp = [];
dp[0] = 1;
for(var i=1;i<n;i++){
dp[i] = 0;
}
for(var i=0;i<m;i++){
for(var j=1;j<n;j++){
//采用空间压缩的方式,dp[j]存储上一行该j位置上的元素,dp[j-1]存储的是这一行前一列的元素
dp[j] = dp[j]+dp[j-1];
}
}
return dp[n-1];
}

leetcode64(最小路径和):

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var minPathSum = function(grid) {
var row = grid.length;
var column = grid[0].length;
for(var i=0;i<row;i++){
for(var j=0;j<column;j++){
if(i==0&&j==0){
continue;
}else if(i==0){
grid[i][j] = grid[i][j-1]+grid[i][j];
}else if(j==0){
grid[i][j] = grid[i-1][j]+grid[i][j];
}else{
grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
}
}
}
return grid[row-1][column-1];
};
分享到