[JavaScript知识库]判断是不是平衡二叉树 - 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
    }
}