算法6

输入
5
5000 2000 5000 8000 1800
输出
3
说明
最终构造出的树如下，高度为3

class TreeNode {
	constructor(val) {
		this.val = val;
		this.left = null;
		this.mid = null;
		this.right = null;
	}
}
class Tree {
	insert (root, val) {
		if (root === null) {
			return new TreeNode(val);
		}
 
		if (val < root.val - 500) {
			root.left = this.insert(root.left, val)
		} else if (val > root.val + 500) {
			root.right = this.insert(root.right, val)
		} else {
			root.mid = this.insert(root.mid, val)
		}
 
		return root; // 返回根节点
	}
	getHeight (root) {
		if (root === null) {
			return 0;
		}
		let leftHeight = this.getHeight(root.left);
		let midHeight = this.getHeight(root.mid);
		let rightHeight = this.getHeight(root.right);
 
		return Math.max(leftHeight, midHeight, rightHeight) + 1;
	}
}
 
let tree = new Tree();
let root = null;
const readline = require('readline')
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
})
rl.on('line', (line) => {
	const N = parseInt(line);
	rl.on('line', (line2) => {
		const numbers = line2.split(' ').map(Number);
		for (let number of numbers) {
			root = tree.insert(root, number)
		}
		const height = tree.getHeight(root);
		console.log(height);
	})
})

abc1 A
xyz B

abc1

abc1 A  
xyz A
 
输出 NULL

const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
})
 
let shapeMap = new Map();
rl.on('line', (line) => {
	const [palyerId, shape] = line.split(' ')
	if (shapeMap.has(shape)) {
		shapeMap.get(shape).push(playerId)
	} else {
		shapeMap.set(shape, [playerId])
	}
}).on('close', () => {
	if (shapeMap.size !== 2) {
		console.log('NULL')
		process.exit(0)
	}
	let winners;
 
	if (shapeMap.has('A') && shapeMap.has('B')) {
		winners = shapeMap.get('A');
	} else if (shapeMap.has('B') && shapeMap.has('C')) {
		winners = shapeMap.get('B');
	} else if (shapeMap.has('C') && shapeMap.has('A')) {
		winners = shapeMap.get('C');
	} else {
		console.log('NULL')
		process.exit(0)
	}
 
	winners.sort()
	for (let i = 0; i < winners.length; i++) {
		console.log(winners[i])
	}
})

function isTrunPoint(prev, curr, next) {
	const dx1 = curr[0] - prev[0]
	const dy1 = curr[1] - prev[1]
	const dx2 = next[0] - curr[0]
	const dy2 = next[1] - curr[1]
 
	return dx1 * dy2 !== dy1 * dx2;
}
function simplifyPath(points) {
	if (points.length < 2) return points;
	const result = [points[0]]
	for (let i = 1; i < points.length - 1; i++) {
		if (isTrunPoint(points[i - 1], points[i], points[i + 1])) {
			result.push(point[i])
		}
	}
}
const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
})
 
const points = []
rl.on('line', (line) => {
	const nums = line.split(' ').map(Number);
	for (let i = 0; i < nums.length; i += 2) {
		points.push([nums[i], nums[i + 1]])
	}
	el.close()
}).on('close', () => {
	const simplifiedPoints = simplifyPath(points);
	const output = simplifiedPoints.map(point => {
		return point.join(' ')
	}).join(' ')
	console.log(output);
	process.exit(0);
})

输入：
bb1234aa
 
输出：
10
 
bb12-34aa
 
输出 -31
说明 1 + 2 - 34 = 31;

function getMinSum (str) {
	let numArr = str.split(/[^\d-]+/);
	let res = 0;
 
	function getNumSum(num) {
		let sum = 0;
		for (let c of num) {
			sum += parseInt(c);
		}
		return sum;
	}
 
	for (let i = 0; i < numArr.length; i++) {
		if (numArr[i]) {
			if (numArr[i].indexOf('-') === -1) {
				res += getNumSum(numArr[i]);
			} else {
				let isNeg = numArr[i].startsWith('-');
				let subStrs = numArr[i].split('-');
				for (let i = 0; i < subStrs.length; i++) {
					if (subStrs[i]) {
						let ele = parseInt(subStrs[i])
						if (i === 0) {
							res += isNeg ? (0 - ele) : getNumSum(subStrs[i])
						} else {
							res -= ele;
						}
					}
				}
				
			}
		}
	}
	console.log(res);
}

/**
*
* @param nums  正整数数列，长度范围 [1,10000]
* @param jump  跳数，范围 [1,10000]
* @param left  幸存数量，范围 [1,10000]
* @return 幸存数之和
*/
int sumOfLeft(int[] nums,int jump,int left)

输入：
[1,2,3,4,5,6,7,8,9],4,3
 
输出：
13
 
说明：
从1(索引为0)开始起跳,中间跳过4个数字因此依次删除 6,2,8,5,4,7。 剩余 1,3,9,返回和为13

const readline = require('readline')
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout
})
 
let nums = []
let jump = 0;
let left = 0;
 
rl.on('line', (line) => {
	if (!this.nums.length) {
		this.nums = line.split(',').map(Number)
	} else if (!jump) {
		jump = parseInt(line);
	} else if (!left) {
		left = parseInt(line);
		console.log(sumOfLeft(nums, jump, left))
		rl.close()
	}
})
 
function sumOfLeft(nums, jump, left) {
	if (left >= nums.length) {
		return nums.reduce((acc, cur) => {
			return acc + cur
		}, 0)
	}
	let index = 0;
	let list = nums.slice();
	while (list.length > left) {
		index = (index + jump + 1) % list.length;
 
		list.splice(index, 1)
 
		index = index - 1;
	}
 
	return list.reduce((acc, cur) => {
		return acc + cur;
	}, 0)
}

const readline = require('readline')
const rl = readline.createInterface({
	input: process.stdin,
	output: process.steout,
})
rl.on('line', (line) => {
	const allNums = line.split(' ').map(Number)
	let maxTime = 0;
 
	const nodeQueue = []
	nodeQueue.push(0);
 
	while (nodeQueue.length) {
		const parentNodeIndex = nodeQueue.shift();
 
		const leftIndex = 2 * parentNodeIndex + 1;
		const rightIndex = 2 * parentNodeIndex + 2;
		if (leftIndex < allNums.length && allNums[leftIndex] !== -1) {
			allNums[leftIndex] += allNums[parentNodeIndex]
			nodeQueue.push(leftIndex)
			maxTime = Math.max(maxTime, allNums[leftIndex])
		}
		if (rightIndex < allNums.length && allNums[rightIndex] !== -1) {
			allNums[rightIndex] += allNums[parentNodeIndex]
			nodeQueue.push(rightIndex)
			maxTime = Math.max(maxTime, allNums[rightIndex])
		}
	}
	console.log(maxTime);
	rl.close();
})

20*19*20*
 
输出tst

const readline = require('readline')
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout
})
rl.on('line', (line) => {
	let s = line;
	const replaceEles = Array.from({
		length: 26
	}, (_, i) => {
		return [i + 1, String.fromCharCode(97 + i)]
	})
 
	replaceEles.reverse().forEach(([key, val]) => {
		s = s.replaceAll(key >= 10 ? `${key}*` : key.toString(), val);
	})
 
	console.log(s)
})

输入：
5
5 15 40 30 10
 
输出：
40 100 30 60 15 30 5 15 10
 
说明：
根据输入，生成哈夫曼树，按照中序遍历返回。所有节点中，左节点权值小于等于右节点权值之和。当左右节点权值相同时左子树高度小于右子树。结果如上图

class Node {
	constructor (value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}
class MinPriorityQueue {
	constructor () {
		this.elements = []
	}
	enqueue(element) {
		this.elements.push(element);
		this.elements.sort((a, b) => a.value - b.value);
	}
	dequeue() {
		return this.elements.shift(); // 移除并返回数组第一个元素
	}
	isEmpty() {
		return this.elements.length === 0;
	}
}
function buildHuffmanTree (values) {
	const pq = new MinPriorityQueue();
	values.forEach(value => {
		pq.enqueue(new Node(value))
	})
 
	while (pq.elements.length > 1) {
		let left = pq.dequeue();
		let right = pq.dequeue();
		const parent = new Node(left.value + right.value);
		parent.left = left;
		parent.right = right;
		pq.enqueue(parent);
	}
 
	return pq.dequeue();
}
function inorderTraversal(root) {
	if (root) {
		inorderTraversal(root.left);
		console.log(root.value)
		inorderTraversal(root.right);
	}
}
 
const readline = require('readline')
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout
})
rl.on('line', (n) => {
	rl.on('line', (line) > {
		const values = line.split(' ').map(Number)
		const root = buildHuffmanTree(values);
		const result = ''
		console.log(reslut);
		rl.close();
	})
})

5
1,2
1,1,0,1,0
1,1,0,0,0
0,0,1,0,1
1,0,0,1,0
0,0,1,0,1
 
输出 3

// num 5;
// confirmedCases 1,2
// inputs ['1,1,0,1,0', '1,1,0,0,0']
function getHesuanNum (num, confirmedCases, inputs) {
	let confirm = confirmedCases.split(',').map(Number);
  let visited = new Array(num).fill(false);
  let contacts = Array.from({ length: num }, () => {
    return Array(num).fill(false);
  })
  inputs.forEach((value, index) => {
    let split = value.split(',')
    contacts[index] = split.map(value => value == 1);
  })
  console.log('contacts', contacts);
 
  function dfs (contacts, visited, start) {
    visited[start] = true;
    for (let i = 0; i < contacts.length; i++) {
      if (contacts[start][i] && !visited[i]) {
        dfs(contacts, visited, i);
      }
    }
  }
  confirm.forEach((value) => {
    dfs(contacts, visited, value);
  })
  console.log('visited', visited);
  let count = 0;
  visited.forEach((hasVisited, index) => {
    if (hasVisited && !confirm.includes(index)) {
      count++;
    }
  })
  console.log(count);
}

输入
7
1 2 2 7 3 6 1
3
输出
10
 
 
输入
3
1 2 3
3
输出
6
说明
全部获取所有的香蕉，因此最终根数为1+2+3 = 6

function getMaxBanner (length, banners, count) {
	let bannersArr = banners.split(' ');
	let totalBanner = bannersArr.recuce((acc, cur) => {
		return acc + cur;
	}, 0);
	if (count === bannersArr.length) {
		return totalBanner;
	}
	let minWindowSum = Infinity;
	let windowSize = length - count;
	let currentWindowCount = 0;
	for (let i = 0; i < windowSize; i++) {
		currentWindowCount += bannersArr[i];
	}
	minWindowSum = currentWindowCount;
	for (let i = windowSize; i < length; i++) {
		currentWindowCount += (number[i] - number[i - windowSize]);
		minWindowSum = Math.min(minWindowSum, currentWindowCount);
	}
 
	console.log(total - minWindowSum);
}