1.合并二叉树
题目：
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的思路：递归合并。从上到下依次递归遍历子树，值合并，子树的子树也按照结构一样合并
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} t1
* @param {TreeNode} t2
* @return {TreeNode}
*/
var mergeTrees = function(t1, t2) {
if (!t1 || !t2) return t1 || t2;
t1.val = t1.val + t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
};
2.三个数的最大乘积
题目：给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
思路：三个数的最大乘积，因为负负得正，所以要找到最大的正数，然后找到第二大和第三大的正数，以及最小及第二小的负数。第二大的正数和第三大的正数的乘积与最小及第二小的负数的乘积比较，取较大值，乘以最大的正数，就是结果
/**
* @param {number[]} nums
* @return {number}
*/
var maximumProduct = function(nums) {
if(nums.length==3)return nums.reduce((res,i)=>res*i,1)
let min1 = 0;
let min2 = 0;
let max1 = 0;
let max2 = 0;
let max3 = 0;
for (const n of nums) {
if (n < 0) {
if (n <= min1) {
min2 = min1;
min1 = n;
} else if (n <= min2) {
min2 = n;
}
} else {
if (n >= max3) {
max1 = max2;
max2 = max3;
max3 = n;
} else if (n >= max2) {
max1 = max2;
max2 = n;
} else if (n >= max1) {
max1 = n;
}
}
}
return max3 * Math.max(min1 * min2, max1 * max2);
};
3.平方数之和
题目：给定一个非负整数
c
，你要判断是否存在两个整数
a
和
b
，使得 a2 + b2 = c。
思路：可以先固定一个数，求是否有另一个数，使得等式成立。a从c的平方根取整数部分开始计算，每次减一，直到1（不需要到0，因为是0的场景，那么另一个数是c的平方根）
/**
* @param {number} c
* @return {boolean}
*/
var judgeSquareSum = function(c) {
if(!c)return true
const middle = ~~Math.sqrt(c, 2);
for (let i = middle; i; i--) {
if (Number.isInteger(Math.sqrt(c - i * i, 2))) return true;
}
return false;
};
4.二叉树的层平均值
题目：给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
思路：其实就是二叉树层序遍历的延伸，做法是一样的
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var averageOfLevels = function(root) {
if (!root) return [];
let res = [],
stack = [root];
while (stack.length) {
let curr = 0,
temp = [];
count = 0;
while (stack.length) {
let node = stack.shift();
curr += node.val;
count++;
if (node.left) temp.push(node.left);
if (node.right) temp.push(node.right);
}
res.push(curr / count);
stack.push(...temp);
}
return res;
};
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var averageOfLevels = function(root) {
if(!root)return []
const stack = [
{
node: root,
level: 1,
},
];
let num = 0;
let sum = 0;
let curLevel = 1;
const res = [];
while (stack.length) {
const item = stack.shift();
if (!item.node) continue;
if (item.level === curLevel) {
sum += item.node.val;
num++;
} else {
res.push(sum / num);
curLevel = item.level;
num = 1;
sum = item.node.val;
}
stack.push({
node: item.node.left,
level: item.level + 1,
});
stack.push({
node: item.node.right,
level: item.level + 1,
});
}
res.push(sum / num);
return res;
};
5.子数组最大平均数
题目：给定
n
个整数，找出平均数最大且长度为
k
的连续子数组，并输出该最大平均数。
思路：滑动窗口。平均值最大其实是总和最大。先从0开始计算前k个的总和，然后往后一次遍历，每次遍历的时候，总和就是减去前一个数，加上后一个数
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findMaxAverage = function(nums, k) {
const l = nums.length;
let v = 0;
for (let i = 0; i < k; i++) {
v += nums[i];
}
let max = v;
for (let i = 1; i <= l - k; i++) {
v = v - nums[i - 1] + nums[i + k - 1];
max = max > v ? max : v;
}
return max / k;
};