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;
};