leetcode-236-238

leetcode236题238题:

leetcode236题(二叉树的最近公共祖先):

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

树

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
var lowestCommonAncestor = function(root, p, q) {
if(root==null||p==root||q==root){
return root;
}
var left = lowestCommonAncestor(root.left,p,q);
var right = lowestCommonAncestor(root.right,p,q);
if(left&&right){
return root;
}
return left?left:right;
};

leetcode238题(除自身以外数组的):

给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入:[1,2,3,4]

输出:[24,12,8,6]

说明:不要使用除法,且在 O(n) 时间复杂度内完成此题。

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var productExceptSelf = function(nums) {
var dp = [];
var bp = [];
for(var i=0;i<nums.length;i++){
dp[i] = 1;
bp[i] = 1;
}
for(var i=1;i<nums.length;i++){
dp[i] = dp[i-1]*nums[i-1];
}
for(var j=nums.length-2;j>=0;j--){
bp[j] = bp[j+1]*nums[j+1];
}
for(var i=0;i<nums.length;i++){
dp[i] = dp[i]*bp[i];
}
return dp;
};
分享到