leetcode-572-581

leetcode 572 581题

leetcode572题题目:

给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例1示例2

解答:
  1. 先定义一个函数isCommon,这个函数用来判断两个树是否是相等的。
  2. 然后在isSubtree这个函数中,首先判断s是否为null,如果为null,返回false;如果s和t经isCommon这个函数判断是相同的,那么返回true;否则去判断,s.left里面是否包含树t或者s.right里面是否包含树t。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var isSubtree = function(s, t) {
if(!s){
return false;
}
if(isCommon(s,t)){
return true;
}
return isSubtree(s.left,t)||isSubtree(s.right,t);
};
function isCommon(s,t){
if(!s&&!t){
return true;
}
if(!s||!t){
return false;
}
if(s.val!==t.val){
return false;
}
return isCommon(s.left,t.left)&&isCommon(s.right,t.right);
}

leetcode581题题目:

给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。

你找到的子数组应是最短的,请输出它的长度。

示例:

    输入: [2, 6, 4, 8, 10, 9, 15]
    输出: 5
    解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。

解答:

分为两个步骤:

  1. 遍历整个数组元素,确定最终的high值。如果是数组的第一个元素,那么将maxValue值确定为该值,如果不是,将nums[i]值与maxValue值进行比较,如果小于maxValue,代表这个值是乱序中的一个,故此时的high值为这个元素对应的i;无论是否小于maxValue,我们都需要重新确定maxValue值,这个值为现在的maxValue值与nums[i]两者最大值。
  2. 同上面,遍历整个数组元素,确定最终的low值。如果是数组的最后一个元素,将minValue确定为该值,如果不是,将nums[i]与minValue值进行比较,如果大于minValue,代表这个值是乱序中的一个,故此时的low值为这个元素对应的i;无论是否大于minValue,我们都需要重新确定maxValue值,这个值为现在的minValue值与nums[i]两者的最小值。
  3. 确定了low和high,就可以通过两者的差值再加1得到最终的乱序序列长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var findUnsortedSubarray = function(nums) {
if(nums.length==0||nums.length==1){
return 0;
}
var maxValue;
var minValue;
var high = 0;
var low = 1;
for(var i=0;i<nums.length;i++){
if(i==0){
maxValue = nums[i];
}else{
if(nums[i]<maxValue){
high = i;
}
maxValue = Math.max(nums[i],maxValue);
}
}
for(var i=nums.length-1;i>=0;i--){
if(i==nums.length-1){
minValue = nums[i];
}else{
if(nums[i]>minValue){
low = i;
}
minValue = Math.min(nums[i],minValue);
}
}
return high-low+1;
};
分享到