验证二叉树
二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。
只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时，返回 true；否则返回 false。
如果节点 i 没有左子节点，那么 leftChild[i] 就等于 -1。右子节点也符合该规则。
注意：节点没有值，本问题中仅仅使用节点编号。
示例 1：
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] 输出：true
示例 2：
输入：n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1] 输出：false
示例 3：
输入：n = 2, leftChild = [1,0], rightChild = [-1,-1] 输出：false
示例 4：
输入：n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1] 输出：false
提示：
1 <= n <= 10^4leftChild.length == rightChild.length == n-1 <= leftChild[i], rightChild[i] <= n - 1
/**
* @param {number} n
* @param {number[]} leftChild
* @param {number[]} rightChild
* @return {boolean}
*/
var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
let fa = new Array(n).fill(-1);
// 如果一个节点有两个fa就是问题。或者循环的fa，或者是没有root。
for(let i = 0;i<n;i++) {
if(leftChild[i] != -1) {
if(fa[leftChild[i]] != -1) return false;
fa[leftChild[i]] = i;
}
if(rightChild[i] != -1) {
if(fa[rightChild[i]] != -1) return false;
fa[rightChild[i]] = i;
}
}
let count = 0;
for(let i = 0;i<n;i++) {
if(fa[i] == -1) count++;
}
return count == 1;
}
/*
var validateBinaryTreeNodes = function(n, l, r) {
let vis = new Array(n).fill(0);
let flag = 0;
for(let i=0;i<n;i++)
{
if(l[i]!=-1)vis[l[i]]++;
if(r[i]!=-1)vis[r[i]]++;
}
for(let i=0;i<n;i++)
{
if(vis[i]==0)
{
if(!flag)flag=1;
else return 0;
}
if(vis[i]>1)return 0;
}
if(!flag)return 0;
return 1;
}
*/
/*
var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
let id = new Array(n).fill(0);
for (let i = 0; i < n; ++i) {
if (leftChild[i] != -1)
id[leftChild[i]]++;
if (rightChild[i] != -1)
id[rightChild[i]]++;
}
let count = 0;
for (let i = 0; i < n; ++i) {
if (id[i] == 2) return false;
if (id[i] == 0) ++count;
}
return count == 1;
}
*/
/*
var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
const parent = new Array(n).fill(-1);
for (let i = 0; i < n; i++) {
if (leftChild[i] > -1) {
if (parent[leftChild[i]] > -1) return false;
parent[leftChild[i]] = i;
}
if (rightChild[i] > -1) {
if (parent[rightChild[i]] > -1) return false;
parent[rightChild[i]] = i;
}
}
let root = -1;
for (let i = 0; i < n; i++) {
if (parent[i] === -1) {
if (root > -1) return false;
root = i;
}
}
let num = 0;
var dfs = function(i) {
num++;
if (leftChild[i] > -1) dfs(leftChild[i]);
if (rightChild[i] > -1) dfs(rightChild[i]);
}
dfs(root);
return num === n;
};
*/
/*
var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
for(let i=0; i<n; i++){
let l = leftChild[i],
r = rightChild[i];
let sub = [];
if( l!==-1){
sub.push(l)
}
if(l!==-1) {
sub.push(l)
}
let arr = [];
while(sub.length){
let node = sub.shift();
}
}
};
*/
var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
const queue = [0];
const set = new Set(queue);
while (queue.length) {
const i = queue.shift();
if (set.has(leftChild[i])) {
return false;
} else if (leftChild[i] !== -1) {
set.add(leftChild[i]);
queue.push(leftChild[i]);
}
if (set.has(rightChild[i])) {
return false;
} else if (rightChild[i] !== -1) {
set.add(rightChild[i]);
queue.push(rightChild[i]);
}
}
return set.size === n;
};
// 如果存在环，就不是二叉树，set中元素个数不为n就存在断层，其实还有一种可能就是根结点不是0；
当时就是不知道怎么判断存在环，和断层。while(queue.length){}有这个趋势，但是对数组中节点和索引反应不过来。
先 0 这个节点，拿出它的左节点1和右节点2，放到queue中。在弹出1这个节点，它又是索引拿到它的左3和右节点4，如果3或4存在于set中就存在。1->0(3或4)就是环
形成三的最大倍数
给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。
由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。
如果无法得到答案，请返回一个空字符串。
示例 1：
输入：digits = [8,1,9] 输出："981"
示例 2：
输入：digits = [8,6,7,1,0] 输出："8760"
示例 3：
输入：digits = [1] 输出：""
示例 4：
输入：digits = [0,0,0,0,0,0] 输出："0"
提示：
1 <= digits.length <= 10^40 <= digits[i] <= 9- 返回的结果不应包含不必要的前导零。
/** * @param {number[]} digits * @return {string} */ var largestMultipleOfThree = function(digits) { digits.sort((a, b) => a - b); const map = [[], [], []]; let sum = 0; for (const n of digits) { map[n % 3].push(n); sum += n; } function format(arr) { arr.sort((a, b) => b - a); while (arr.length > 1 && arr[0] === 0) { arr.shift(); } return arr.join(''); } // console.log(sum, sum % 3); if (sum % 3 === 0) { return format(digits); } else if (sum % 3 === 1) { if (map[1].length >= 1) { map[1].shift(); return format([...map[0], ...map[1], ...map[2]]); } else if (map[2].length >= 2) { map[2].shift(); map[2].shift(); return format([...map[0], ...map[1], ...map[2]]); } else { return ''; } } else { if (map[2].length >= 1) { map[2].shift(); return format([...map[0], ...map[1], ...map[2]]); } else if (map[1].length >= 2) { map[1].shift(); map[1].shift(); return format([...map[0], ...map[1], ...map[2]]); } else { return ''; } } }; /* var largestMultipleOfThree = function(digits) { const num = new Array(10).fill(0); let sum = 0; for (let i = 0; i < digits.length; i++) { sum += digits[i]; num[digits[i]]++; } if (sum % 3 === 1) { for (let i = 1; i < 9; i+=3) { if (num[i] > 0) { num[i]--; sum-= i; break; } } if (sum % 3 === 1) { for (let i = 2; i < 9; i+=3) { if (num[i] > 0) { num[i]--; sum-= i; if (sum % 3 === 0) break; } if (num[i] > 0) { num[i]--; sum-= i; if (sum % 3 === 0) break; } } } } if (sum % 3 === 2) { for (let i = 2; i < 9; i+=3) { if (num[i] > 0) { num[i]--; sum-= i; break; } } if (sum % 3 === 2) { for (let i = 1; i < 9; i+=3) { if (num[i] > 0) { num[i]--; sum-= i; if (sum % 3 === 0) break; } if (num[i] > 0) { num[i]--; sum-= i; if (sum % 3 === 0) break; } } } } if (!sum) return num[0] ? '0' : ''; let result = ''; for (let i = 9; i > -1; i--) { for (let j = 0; j < num[i]; j++) { result = result + i; } } return result; } */ /* 以前的想法： 排序，去掉最小的，一直去掉最小的，后果就是有时去掉的不是最小的也能满足条件，这样它的位数会很长，自然数字就是最大的。 后来想： DP, len(digits) = Math.max(len(digits), len) var largestMultipleOfThree = function(digits) { digits.sort((a,b)=>a-b); let len = digits.length; let n = len; let sub = []; let s = 0; let index0=0; while(n--){ let sum = digits.reduce((a,b)=>a+b); if(sum === 0){ return "0" }else if(sum%3===0){ let ii = digits.indexOf(s); if(ii>-1 && s!==0){ digits.splice(ii, 1); digits.splice(index0, 0, ...sub) } break; }else{ let j = 0; len = digits.length; while(digits.length ===len){ if(digits[j]!==0){ index0 = j; s+=digits[j]; sub.push(digits[j]) digits.splice(j, 1); } else { j++; } } } } return digits.reverse().join('') }; */
var largestMultipleOfThree = function(digits) { let arr = new Array(10).fill(0), sum = 0; let ans = ''; const del=(m)=>{ for(let i=m;i<=9;i+=3)if(arr[i]){arr[i]--,sum-=i;return 1;} return 0; } digits.forEach(f=>{ arr[f]++; sum+=f }) if(sum%3 ===1){ if(!del(1)){ del(2); del(2); } } if(sum%3 ===2){ if(!del(2)){ del(1); del(1); } } if(!sum && arr[0]){ return "0"; } for(let i=9;i>=0;i--)while(arr[i]--)ans+=i+''; return ans; }
以前的想法： 排序，去掉最小的，一直去掉最小的，后果就是有时去掉的不是最小的也能满足条件，这样它的位数会很长，自然数字就是最大的。 后来想： DP, len(digits) = Math.max(len(digits), len),还是不对。
这个数是0～9这10个数构成，完全可以用数组统计每个数对应的个数，然后从后向前遍历拼接最大数