leetcode-124-128

leetcode124题128题

leetcode124题(二叉树中的最大路径和):

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxPathSum = function(root) {
var maxSum = -Infinity;
function maxGain(root){//包含根节点的一边最大路径和
if(root==null){//如果节点不存在,返回0
return 0;
}
var left_gain = Math.max(maxGain(root.left),0);//左边的最大路径和
var right_gain = Math.max(maxGain(root.right),0);//右边的最大路径和
var newPathGain = root.val + left_gain + right_gain;//包含根节点在内的两边最大路径和
maxSum = Math.max(maxSum,newPathGain);//取二者最大值
return root.val+Math.max(left_gain,right_gain);//
}
maxGain(root);
return maxSum;
};

leetcode128题(最长连续序列):

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var longestConsecutive = function(nums) {
var obj = {};
for(var i=0;i<nums.length;i++){
obj[nums[i]] = nums[i];
}
var maxLength = 0;
for(var prop in obj){
if(obj[prop-1]==undefined){
var curNum = obj[prop];
var curLength = 1;
while(obj[curNum+1]!=undefined){
curLength++;
curNum = curNum+1;
}
maxLength = Math.max(curLength,maxLength);
}
}
return maxLength;
};
分享到