判断是不是平衡二叉树 - js

01 - 两数之和 - js

描述
给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。

示例1
输入:[3,2,4],6
返回值:[2,3]
说明:因为 2+4=6 ,而 2的下标为2 , 4的下标为3 ,又因为 下标2 < 下标3 ,所以输出[2,3]    
思路:双层循环找到两数之和等于目标值时,生序返回两个下标值(注意要跳过自身和自身的相加)

代码实现:

function twoSum( numbers ,  target ) {
    // write code here
    for(let i = 0; i < numbers.length; i ++){
        for(let j = 0; j < numbers.length; j ++){
            if(i === j) break
            if(numbers[i] + numbers[j] === target){
                if(i > j){
                    return [j + 1 , i + 1]
                }else{
                    return [i + 1 , j + 1]
                }
            }
        }
    }
}

02 - 判断是不是平衡二叉树 - js 

描述
输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

示例1
输入:{1,2,3,4,5,6,7}
返回值:true



[思路]:递归判断一个节点的左右子树的高度差是否超过1,然后对每个节点都进行判断

代码实现:

function IsBalanced_Solution(pRoot){
	if(pRoot == null) return true // 默认空树也是平衡二叉树
	// 获取一个节点的树高
	function getNodeTreeHigh(node){
		if(node == null) return 0
		let leftHigh = getNodeTreeHigh(node.left)
		let rightHigh = getNodeTreeHigh(node.right)
		return Math.max(leftHigh,rightHigh) + 1
	}
	// 获取每个节点的左子树高度和右子树高度
	let left = getNodeTreeHigh(pRoot.left)
	let right = getNodeTreeHigh(pRoot.right)
	if(Math.abs(left - right) > 1) return false
	return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
}

03 - 扑克牌顺子 - js

描述
现在有2副扑克牌,从扑克牌中随机五张扑克牌,我们需要来判断一下是不是顺子。
有如下规则:

  1. A为1,J为11,Q为12,K为13,A不能视为14
  2. 大、小王为 0,0可以看作任意牌
  3. 如果给出的五张牌能组成顺子(即这五张牌是连续的)就输出true,否则就输出false。
  4. 数据保证每组5个数字,每组最多含有4个零,数组的数取值为 [0, 13]
示例1
输入:[6,0,2,0,4]
返回值:true
说明:中间的两个0一个看作3,一个看作5 。即:[6,3,2,5,4]
这样这五张牌在[2,6]区间连续,输出true 
思路:
1.最关键的是得到数组中的最大值和最小值,只有在最大值max - 最小值min 小于4的情况下才能满足组成顺子的条件。
2.将数组中的0的个数计算出来
3.将数组中除0以外的数据进行去重
4.比较去重之后的数组的长度加上0的个数是不是等于5并且时max - min要小于4.如果满足这两个条件表示能组成顺子就返回true 如果不满足就表示不能组成顺子返回false

代码实现:

function IsContinuous(numbers){
    // write code here
    let zeroNums = 0
    let newNums = []
    for(let i = 0; i < numbers.length; i ++){
        if(numbers[i] === 0){
            zeroNums ++
        }else {
            newNums.push(numbers[i])
        }
    }
    let max = newNums[0]
    let min = newNums[0]
    for (let i = 0; i < newNums.length; i++) {
        if(min > newNums[i]){
            min = newNums[i]
        }
        if (max < newNums[i]) {
            max = newNums[i]
        }
    }
    newNums = [...new Set(newNums)]
    if(newNums.length + zeroNums == 5 && max - min < 5) return true
    else return false
}

04 - 跳台阶 - js

描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

示例1
输入:2
返回值:2
说明:青蛙要跳上两级台阶有两种跳法,分别是:先跳一级,再跳一级或者直接跳两级。因此答案为2     
思路:一次只能跳一级或者两级台阶,且1阶台阶就只有一种,两级台阶就有两种。到达n级台阶处,可以从n-1处跳过来也可以从n-2处跳过来,所以n= (n - 1)-(n - 2)。那之前的每一阶台阶都是一样的结果,所以递归计算即可。

代码实现:

function jumpFloor(number){
    // write code here
    if(number === 0) return 0
    if(number === 1) return 1
    if(number === 2) return 2
    else {
        return jumpFloor(number - 1) + jumpFloor(number -2)
    }
}

05 - 两个链表的第一个公共结点 && 链表中倒数最后k个结点 - js

两个题目一都是一样的思路,将链表中的数据全部遍历出来放在一个新数组中去,找到目标值之后再遍历一次链表执行返回操作

5.1 两个链表的第一个公共结点

描述
输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)

示例1
输入:{1,2,3},{4,5},{6,7}
返回值:{6,7}
说明:第一个参数{1,2,3}代表是第一个链表非公共部分,第二个参数{4,5}代表是第二个链表非公共部分,最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表,且是有公共节点的       

代码实现:

function FindFirstCommonNode(pHead1, pHead2){
    // write code here
    if(!pHead1 && !pHead2) return null
    let headArr1 = []
    let headArr2 = []
    let node1 = pHead1
    let node2 = pHead2
    while(node1){
        headArr1.push(node1.val)
        node1 = node1.next
    }
    while(node2){
        headArr2.push(node2.val)
        node2 = node2.next
    }
    let repeated = 0
    for(let i = 0; i < headArr1.length; i ++){
        for(let j = 0 ; j < headArr2.length ; j ++){
        // 这里要多向后判断一位数据,防止单个位置数据重复
            if(headArr1[i] === headArr2[j] && headArr1[i + 1] === headArr2[ j + 1]){
                repeated = headArr2[j]
                break
            }
        }
        if(repeated !== 0) break
    }
    
    if(repeated === 0) return null
    else {
        while(pHead1){
            if(pHead1.val === repeated){
                return pHead1
            }
            pHead1 = pHead1.next
        }
    }
}

5.2 链表中倒数最后k个结点

描述
输入一个长度为 n 的链表,设链表中的元素的值为 ai ,返回该链表中倒数第k个节点。
如果该链表长度小于k,请返回一个长度为 0 的链表。

示例1
输入:{1,2,3,4,5},2
返回值:{4,5}
说明:返回倒数第2个节点4,系统会打印后面所有的节点来比较。 

代码实现:

function FindKthToTail( pHead ,  k ) {
    // write code here
    if(pHead == null) return pHead
    let nodeArr = []
    let node = pHead
    while(node){
        nodeArr.push(node.val)
        node = node.next
    }
    let indexVal = nodeArr[nodeArr.length - k]
    while(pHead){
        if(indexVal === pHead.val){
            return pHead
        }
        pHead = pHead.next
    }
}
上一篇:java数据结构 两数之和


下一篇:两个数满足相加之和等于目标数 target