简单

7-1 ⽤栈实现队列

class MyStack {
list = [];
push(item) {
return this.list.push(item);
}
peek() {
return this.list[this.list.length - 1];
}
pop() {
return this.list.pop();
}
empty() {
return this.list.length === 0;
}
}
class MyQueue {
stack = new MyStack();
helperStack = new MyStack();

push(item) {
this.stack.push(item);
}
peek() {
if(this.helperStack.empty()) {
while(!this.stack.empty()) {
this.helperStack.push(this.stack.pop());
}
}
return this.helperStack.peek();
}
pop() {
this.peek();
return this.helperStack.pop();
}
empty() {
return this.stack.empty() && this.helperStack.empty();
}
}
var fs = require('fs');
var buf = '';
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
const queue = new MyQueue();
 const input = buf.split('\n');
const commands = input[0].split(',');
const parameters = input[1].split(',');
const res = [];
commands.forEach((command, index) => {
switch(command) {
case 'push': {
queue.push(parameters[index]);
res.push('null');
return;
}
case 'pop': {
res.push(queue.pop());
return;
}
case 'peek': {
res.push(queue.peek());
return;
}
case 'empty': {
res.push(queue.empty());
return;
}
default:
return;
}
});
console.log(res.join(','));
});

7-2 合作圈

function countCircles(M) {
let result = 0
const visited = Array(M.length).fill(0);
const N = M.length;
function dfs(i) {
visited[i] = 1;
const relations = M[i];
for(let j = 0; j < N; j++) {
if(!relations[j] || visited[j]) {
continue;
}
dfs(j);
}
}

for(let i = 0; i < N; i++) {

if(visited[i]) {
continue;
}
 result++;
dfs(i);
}
return result;
}
var fs = require('fs');
var buf = '';
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
const M = buf.split('|').map(
(row) =>
row.split(' ').map(
(item) => parseInt(item)
)
);
console.log(countCircles(M));
});

7-3 ⼤⼭的数⽬

var fs = require('fs');
var buf = '';

class Union {
constructor(m, n, grid) {
this.count = 0
this.parent = new Array(m * n)
this.rank = new Array(m * n)
for (let i =0; i < m; i++) {
for (let j = 0; j < n; j++) {
const xy = i * n + j
if (grid[i][j] === 1) {
this.parent[xy] = xy
this.count += 1
}
this.rank[xy] = 0 // 表示集合中的个数
}
}
}

// 找到根元素
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x])
}
return this.parent[x]
}
 union(x, y) {
let rootX = this.find(x)
let rootY = this.find(y)
if (rootX !== rootY) {
// 排名⼩的合并到排名⾼的
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX
} else {
// 我这⾥默认合并到y中，同时，要对y的排名提⾼下
// 这样y就是x的并集
this.parent[rootX] = rootY
if (this.rank[rootX] === this.rank[rootY]) {
this.rank[rootY] += 1
}
}
this.count -= 1
}
}
getCount() {
return Math.max(this.count, 0)
}
}

function getMountainCount(m, n ,grid) {

let union = new Union(m, n, grid)
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
for (let [x, y] of [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]) {
// ⼭周围还是⼭，合并在⼀起
// 注意下标的合法性
if (x >= 0 && x <= m - 1 && y >= 0 && y <= n - 1 && grid[i][j] === 1 &&
grid[x][y] === 1) {
union.union(i * n + j, x * n + y)
}
}
}
}

return union.getCount()
}

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
const lines = buf.split('\n');
const [m ,n] = lines[0].split(' ').map(n => +n)
const grid = new Array(m)
lines.slice(1).forEach((line, index) => {
grid[index] = new Array(n)
 line.split(' ').forEach((num, i) => {
grid[index][i] = +num
})
})
console.log(getMountainCount(m, n, grid))
});

7-4 跳跃

var fs = require('fs');
var buf = '';
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
console.log(buf.split('\n')[1].includes('0') ? 'True' : 'False');
});

7-5 检测回⽂字符串

const isEqual = (char1, char2) => {

return char1.toUpperCase() === char2.toUpperCase();
};
const isWordOrNumber = (char) => {
const code = char.charCodeAt();
return (code >= 65 && code <= 90) ||
(code >= 97 && code <= 122) ||
(code >= 48 && code <= 57);
};
const isPlalindrome = (str) => {
let i = 0, j = str.length - 1;
while(i < j) {
debugger;
if(!isWordOrNumber(str[i])) {
i++;
continue;
}
if(!isWordOrNumber(str[j])) {
j--;
continue;
}
if(isEqual(str[i], str[j])) {
i++;
j--;
} else {
return 0;
}
}
return 1;
 };
var fs = require('fs');
var buf = '';
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
console.log(isPlalindrome(buf));
});

7-6 同构字符串

const isSameStructure = (s, t) => {

const map = new Map();
for(let i = 0; i < s.length; i++) {
if(map.has(s[i])) {
const char = map.get(s[i]);
if(char !== t[i]) {
return 0;
}
} else {
map.set(s[i], t[i]);
}
}
return 1;
};
var fs = require('fs');
var buf = '';
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
const [s, t] = buf.split('\n')[0].split(',');
console.log(isSameStructure(s, t) && isSameStructure(t, s));
});

7-7 数字拆分求和

const splitNum = (k) => {

const res = [];
for(let start = 1; start < k; start++) {
const seq = [];
let sum = 0;
let i = start;
let diff = 1;
while(sum < k && i < k) {
sum += i;
seq.push(i);
 if(sum === k) {
res.push(seq);
break;
}
i += diff;
diff++;
}
}
return res;
};
var fs = require('fs');
var buf = '';
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
const k = parseInt(buf);
const seqs = splitNum(k);
seqs.forEach((seq) => {
console.log(seq.join(','));
})
});

7-8 最⻓的美好字符⼦串

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
const t = buf.split('\n')[0];
var allMatched = []
for (let i = 0; i < t.length; i++) {
var map = new Map()
var matched = ""
var tmp = []
for (let j = i; j < t.length; j++) {
let c = t[j];
tmp.push(c);
let key = c.toLowerCase();
if (map.has(key)) {
if (map.get(key) === 1 && tmp.includes(c.toUpperCase()) &&
tmp.includes(c.toLowerCase())) {
map.set(key, 2);
}
} else {
 map.set(key, 1);
}
var append = true;
for (let i of map.values()) {
if (i === 1) {
append = false;
break;
}
}
if (append) {
matched += tmp.join("");
tmp = [];
}
}
if (matched.length > 0) {
allMatched.push(matched);
}
}
var retV = "";
for (let i of allMatched) {
if (i.length > retV.length) {
retV = i;
}
}
console.log(retV);
});

7-9 最⼩硬币个数

const minCoinCount = (n) => {

let rest = n;
const countOfFive = Math.floor(rest / 5)
rest = rest % 5;
const countOfTwo = Math.floor(rest / 2)
rest = rest % 2
return countOfFive + countOfTwo + rest
};
var fs = require('fs');
var buf = '';
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
console.log(minCoinCount(parseInt(buf)))
});

7-10 判断⼆叉树是不是搜索树

class Node {
 left = null
right = null
val = null
constructor(val) {
this.val = val;
}
}

function getNode(val) {
if (!val) return null;
if (val == 'null') return null;
return new Node(Number(val));
}

// 构建⼆叉树
function buildTree(list) {
if (list.length < 1) return null;
let queue = [];
let root = new Node(list[0])
queue.push(root);
let index = 0;
while (queue.length > 0 && index < list.length - 1) {
let node = queue.shift();
let left = getNode(list[++index])
let right = getNode(list[++index])
node.left = left;
node.right = right;
if (left != null) queue.push(left);
if (right != null) queue.push(right);
}
return root;
}

// 判断是否合法⼆叉树
// https://leetcode.cn/problems/legal-binary-search-tree-lcci/description/
function isValidBST(root) {
function helper(node, lower, higher) {
if (!node) return true;
let val = node.val;
if (val <= lower || val >= higher) return false;
return helper(node.left, lower, val) && helper(node.right, val, higher);
}
return helper(root, -Infinity, Infinity);
}

const readline = require('readline');

const rl = readline.createInterface(process.stdin, process.stdout);
rl.on('line', function (line) {
const list = line.split(',');
const root = buildTree(list);
console.log(isValidBST(root));
});
7-11 买票需要的时间

function ticketTime(tickets, k) {
let sum = 0;
for(let i = 0; i < k; i++) {
// 排在你前⾯的⼈，他的票没买完的话，第⼆轮也会在你前⾯；
// 他买的票张数⼩于等于你的张数，则他在你前⾯耗时tickets[i], 他买的张数⼤于你的张数，耗时
tickets[k]，因为你买完票就离开了
// if(tickets[i] <= tickets[k]) { 这个⼈耗时 = tickets[i]} else { 这个⼈耗时 =
tickets[k]}, 所以取⼆者中的最⼩值， 总时间累加就好了
sum += Math.min(tickets[i], tickets[k]);
}
sum += tickets[k]; // ⾃⼰买票耗时
for(let j = k + 1; j < tickets.length; j++) {
sum += Math.min(tickets[j], tickets[k] - 1);
}
return sum;
}
var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
const lines = buf.split('\n')
const tickets = lines[0].split(' ').map(i => Number(i))
const index = Number(lines[1])
console.log(ticketTime(tickets, index))
});

7-12 ⽆法吃午餐的学⽣数量

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
const c = buf.split('\n');
var students = c[0].split(" ").map((item) => parseInt(item));
var sandwiches = c[1].split(" ").map((item) => parseInt(item));
var retV = students.length;
while (sandwiches.length > 0) {
let s = sandwiches.shift();
 let idx = students.indexOf(s);
if (idx === -1) {
break;
}
retV -= 1;
students.splice(idx, 1);
}
console.log(retV);
});

7-13 求最后⼀块⽯头的重量

// 排序
// 然后递归撞就完了
const getLastWeight = (arr)=>{
if (!arr.length) {
return 0
}

arr.sort((a,b)=>b-a)
const dfs = (curValue, index, arr) =>{
// 撞完了 结束递归
if(index > arr.length -1) {
return curValue
}
return dfs(Math.abs(curValue-arr[index]), index+1, arr)
}

return dfs(0, 0, arr)

}

// 处理输⼊
let buf = ''
process.stdin.on('readable', ()=>{
const chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
process.stdin.on('end', ()=>{
console.log(getLastWeight(buf.split('\n')[0].split(',').map(item=>~~item)))
})

7-14 最⼩栈

// 根据栈的特性，每次⼊栈记录下当前栈内的最⼩值，维护⼀个辅助栈即可
var MinStack = function() {
this.stack = [];
// 这个是辅助栈，保持和主栈⼀样⻓度即可
this.helperStack = [Infinity];
};
MinStack.prototype.push = function(x) {
 this.stack.push(x);
// 这样就记录下了 实际栈内每个值对应的最⼩值
this.helperStack.push(Math.min(this.helperStack[this.helperStack.length-1], x))
};
// 为什么Array.prototype.at⽅法⽤不了啊？ 什么上古运⾏环境？
// 要写⼀堆的 xxx.length-1
MinStack.prototype.pop = function() {
this.stack.pop();
this.helperStack.pop()
};
MinStack.prototype.top = function() {
return this.stack[this.stack.length-1];
};
MinStack.prototype.getMin = function() {
return this.helperStack[this.helperStack.length-1];
};

let buf = ''

process.stdin.on("readable", ()=>{
const chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
process.stdin.on("end", ()=>{
const [opStr, valueStr] = buf.split('\n')
const opList = opStr.split(',')
const values = valueStr.split(',')
const minStack = new MinStack()
let res = []
for( let i=0; i<opList.length; i++) {
const item = minStack[opList[i]](values[i])
// 这⾥真的搞，⼀定要拼成符合预期的结果
res.push(item === undefined ? "null" : item)
}
console.log(res.toString())
})

7-15 字符串编辑距离 JS 动态规划

function minDistance(word1, word2) {

let m = word1.length, n = word2.length;
const dp = Array.from(new Array(m+1), () => new Array(n+1).fill(0));
for(let i=0; i<m+1; i++) {
dp[i][0] = i;
}
for(let j=0; j<n+1; j++) {
dp[0][j] = j;
}
for(let i=1; i<m+1; i++) {
for(let j=1; j<n+1; j++) {
 dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1;
if (word1[i-1]==word2[j-1]) {
dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1])
}
}
}
return dp[m][n];
}
let buf ='';
process.stdin.on('readable', function() {
let chunk = process.stdin.read();
if (chunk) buf+=chunk;
})
process.stdin.on('end', function() {
const [word1, word2] = buf.split(' ');
console.log(minDistance(word1, word2));
})

7-16 给定数字组成最⼤时间 JS 朴素写法

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

function getMaxNumWithMax(max, arr) {

var retV = null;
for (let i = 0; i < arr.length; i++) {
if (arr[i] <= max) {
if (retV === null || retV < arr[i]) {
retV = arr[i];
}
}
}
return retV;
}

process.stdin.on('end', function() {
var c = buf.split('\n')[0].split(',').map((i) => parseInt(i));
var ret = ""
var h = getMaxNumWithMax(2, c);
if (h === null) {
console.log('');
return;
}
ret += h;
c.splice(c.indexOf(h), 1);
var tmp = getMaxNumWithMax((h === 2 ? 3 : 9), c);
 if (tmp === null) {
console.log('');
return;
}
ret += `${tmp}:`;
c.splice(c.indexOf(tmp), 1);
tmp = getMaxNumWithMax(5, c);
if (tmp === null) {
console.log('');
return;
}
ret += `${tmp}`;
c.splice(c.indexOf(tmp), 1);
ret += c[0];
console.log(ret)
});

7-17 交换和

7-18 最⻓回⽂⼦串

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
const c = buf.split('\n')[0];
const len = c.length;
var D = new Array(len).fill(null).map(() => new Array(len).fill(null));
for (let i = 0; i < len; i++) {
D[i][i] = true
}
var [t0, t1] = [0, 0]
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
D[j][i] = c[i] === c[j] && ((i - j === 1) ? true : D[j + 1][i - 1]);
if (D[j][i] && i - j > t1 - t0) {
[t1, t0] = [i, j];
}
}
}
console.log(c.substring(t0, t1 + 1));
});
 var fs = require('fs');
var buf = '';
function findLongestPlindrome(str) {
const len = str.length;
let res = '';
for(let i = 0; i < 2 * len - 1; i++) {
let left = Math.floor(i / 2);
let right = left + i % 2;
let temp = left === right ? 1 : 2;
while(left >= 0 && right < len && str[left] === str[right]) {
left--;
right++;
temp+=2;
}
if (temp - 2 > res.length) {
res = str.slice(left + 1, right);
}
if (res.length === len) {
break;
}
}
return res;
}
process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
process.stdin.on('end', function() {
buf.split('\n').forEach(function(line) {
if (line) {
console.log(findLongestPlindrome(line));
}
});
});

中等
7-1 连续的⼦数组和

// 前缀和
// dp[i] 表示下表为 i 的数组的前缀和
// 当 i > 0 时， i,j 区间的和为 dp[j] - dp[i-1]

const getSubArrSum = (arr, k) => {

let count = 0;
const dp = new Array(arr.length);
for(let i = 0; i < arr.length; i++) {
if (i === 0) {
dp[0] = arr[i]
} else {
dp[i] = arr[i] + dp[i-1]
 }
}

for(let i = 0; i < arr.length - 1; i++) {

for(let j = i + 1; j < arr.length; j++) {
let sum;
if (i > 0) {
sum = dp[j] - dp[i - 1];
} else {
sum = dp[j]
}
if (sum === 0 || sum % k === 0) {
// console.log('aaa', i, j)
count++;
}
}
}
return count;
}

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
const lines = buf.split('\n');
const arr = lines[0].split(',').map(v => +v);
const k = +lines[1];
const res = getSubArrSum(arr,k);
console.log(res > 0 ? 1 : 0);
});

7-2 或运算的最⼩翻转次数

const minFlips = (a, b, c) => {

let count = 0;
for (let i = 0; i < 30; i++) { // 最多30位，遍历每⼀位
const bitA = (a >> i) & 1; // 获取a的第i位
const bitB = (b >> i) & 1; // 获取b的第i位
const bitC = (c >> i) & 1; // 获取c的第i位

if ((bitA | bitB) !== bitC) { // 检查按位或运算是否符合c的第i位

if (bitC === 0) {
count += (bitA + bitB); // 如果c的第i位为0，需要翻转a和b的第i位
} else {
count += 1; // 如果c的第i位为1，⾄少需要翻转a和b中的⼀个第i位
}
 }
}
return count; // 返回翻转次数
}

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
const a = ~~buf.split('\n')[0].split(',')[0];
const b = ~~buf.split('\n')[0].split(',')[1];
const c = ~~buf.split('\n')[0].split(',')[2];
console.log(minFlips(a, b, c));
});

7-3 删除⽆效的括号

const normalizeStr = (str)=>{

// 括号匹配，右括号对⽐栈顶，然后括号⼊，留在栈内的就是未能匹配上的括号
// 这⾥记录序号，后续在原str中剔除⽆效序号即可
let stack = []
for(let i=0; i<str.length; i++) {
const charCode = str.charCodeAt(i)
// ( 40 , ) 41
if(charCode === 41 && stack.length && str[stack[stack.length-1]] === '(') {
// 栈顶元素括号匹配
// console.log('栈顶匹配 -->')
stack.pop()
}else if ([40, 41].includes(charCode)){
stack.push(i)
}
}
return str.split('').map((e, idx)=>stack.includes(idx) ? '': e).join('')
}

let buf = ''

process.stdin.on('readable', ()=>{
const chunk = process.stdin.read()
if (chunk) buf += chunk.toString()
})
process.stdin.on('end', ()=>{
console.log(normalizeStr(buf.split('\n')[0]))
})

7-4 钥匙与房间
 const checkCanEneterAllRooms = (rooms)=>{
// 记录⾛过的路
let map = {}
const backtrack = (allRooms, roomIndex, count)=>{
// 标记⾛过
map[roomIndex] = true
// ⾛的步数超过所有房间的个数说明重复，别⾛了
if (count > allRooms.length) {
return
}
const room = allRooms[roomIndex]
// console.log('room', room)
room.forEach(next=>backtrack(allRooms, next, count+1))
}
backtrack(rooms, 0, 0)

// 如果⾛过的房间刚好等于所有的房间个数，说明每个都⾛了
return (Object.keys(map).length === rooms.length)
}

let buf = ''

process.stdin.on('readable',()=>{
const chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
process.stdin.on('end',()=>{
const arrStr = buf.split('\n')[0]
const child = arrStr.substring(1, arrStr.length-2).split(';');
const arr = [];

for (let i = 0; i < child.length; i++) {

const numbers = child[i].replace(/\[|\]/g,'').split(',').map(Number);
arr.push(numbers);
}
console.log(checkCanEneterAllRooms(arr))
})

7-5 三数之和

let input = '';

process.stdin.on('readable',function(){
const chunk = process.stdin.read();
input += chunk || ''
})
process.stdin.on('end',function(){
input = input.replace('\n','')
inputArr = input.split(' ').map(Number)
console.log(fn(inputArr))
})
 function fn(nums){
if(nums.length < 3) return 0
let res = 0
nums.sort((a,b)=>a-b)
for(let i=0; i < nums.length - 2; i++){
if(nums[i] > 0 ) break //和必>0
if(nums[i] === nums[i-1]) continue
let left = i + 1, right = nums.length - 1
while(left < right){
const sum = nums[i] + nums[left] + nums[right]
if(sum === 0){
res++
while(nums[left] === nums[left+1]) left++ //去重
while(nums[right] === nums[right-1]) right-- //去重
left++
right--
}
if(sum > 0) right--
if(sum < 0) left++
}
}
return res
}

7-6 最⼩树

let input = '';

process.stdin.on('readable',function(){
const chunk = process.stdin.read();
input += chunk || ''
})
process.stdin.on('end',function(){
input = input.replace('\n','')
inputArr = input.split(' ')
console.log(fn(inputArr))
})
function fn(nums){
let negativeIndex = nums.findIndex(item => item < 0)
let negativeValue = ''
if(negativeIndex !== -1){
negativeValue = nums[negativeIndex];
nums.splice(negativeIndex,1)
}
if(negativeValue){
nums.sort((a,b)=>(b+a)-(a+b))
}else{
nums.sort((a,b)=>(a+b)-(b+a))
}
return negativeValue + nums.join('')
}
7-7 联通⽹络的操作次数

const getMinOperation = (n, m, connection)=>{

// 要可以联通，那线缆m最少要 >= 计算机n - 1, 即3台电脑就要2条线
// console.log(n, m , connection)
if (m < n - 1) {
return -1
}
// 我们根据连通关系，算⼀下有⼏个计算机没连的，那么剩下最少的操作显然就是 【剩余计算机数量】 的操作
// 即剩下⼀台计算机没链，就要⼀个操作连⼀下
const pc = new Array(n).fill(false)
for(let item of connection) {
// ⼀条线连两个电脑，所以k和v都要被记录
const [k, v] = item
pc[k] = true
pc[v] = true
}
return pc.filter(item=>!item).length
}

let buf = ''

process.stdin.on('readable',()=>{
const chunk = process.stdin.read()
if(chunk) buf += chunk.toString()
})
process.stdin.on('end',()=>{
const [line1, ...otherLine] = buf.split('\n')
const [n, m] = line1.split(' ').map(Number)
const connection = otherLine.map(item=>item.split(' '))
console.log(getMinOperation(n, m, connection))
})

7-8 分段反转链表

class ListNode {
constructor(addr, val, next) {
this.addr = addr;
this.val = val;
this.next = next;
}
}

// https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
// K 个⼀组翻转链表 递归
function reverseKGroup(head, k) {
let cur = head;
let count = 0;
// 统计当前分组节点个数 count
// cur 移动到下⼀个分组头节点
while (cur && count < k) {
 cur = cur.next;
count++;
}
if (count == k) { // 判断分组否有K个数，如果没有直接返回head
cur = reverseKGroup(cur, k); // 递归反转下⼀个分组
while (count > 0) { // 头插法翻转链表
count--;
let temp = head.next;
head.next = cur;
cur = head;
head = temp;
}
head = cur;
}
return head;
};

// 递归构建链表
function buildLinkList(headAddr, nodeMap) {
let [addr, val, nextAddr] = nodeMap[headAddr];
let head = new ListNode(addr, val, null);
if (nextAddr != -1) {
head.next = buildLinkList(nextAddr, nodeMap);
}
return head;
}

let buf = '';

process.stdin.on('readable', function() {
let chunk = process.stdin.read();
if(chunk) buf+= chunk;
});
process.stdin.on('end', function() {
let firstLine = buf.split('\n')[0];
let [headAddr, N, K] = firstLine.split(' ');
K = Number(K);
let lines = buf.split('\n').slice(1);
let nodeMap = {};

for (let line of lines) {

let [addr, val, next] = line.split(' ');
nodeMap[addr] = [addr, val, next];
}

let head = buildLinkList(headAddr, nodeMap); // 构建链表

head = reverseKGroup(head, K); // 反转链表
// 输出链表
while (head != null) {
console.log(`${head.addr} ${head.val} ${head.next ? head.next.addr : -1}`);
head = head.next;
}
})

⾼级
7-1 按格式合并两个链表

class Node {
addr = null
val = null
next = null
constructor(map, addr, l) {
l.val += 1;
this.addr = addr;
let [v, n] = map.get(addr);
this.val = v;
if (n !== '-1') {
this.next = new Node(map, n, l);
}
}
toString() {
let [n, retV] = [this, []];
while (n !== null) {
retV.push(`${n.addr} ${n.val} ${n.next === null ? '-1' : n.next.addr}`);
n = n.next;
}
return retV.join('\n');
}
reverse() {
// 反转链表
let [h, c] = [null, this];
while (c !== null) {
[c.next, h, c] = [h, c, c.next];
}
return h;
}
}

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
const c = buf.split('\n');
const [startAddr1, startAddr2, totalNum] = c[0].split(' ');
// Map 只是为了⽅便构建链表数据结构
const map = new Map();
for (let i = 1; i <= parseInt(totalNum); i++) {
 let [a1, v, n] = c[i].split(' ');
map.set(a1, [v, n]);
}
//构建两个链表并且直接返回链表⻓度
let length1 = { val: 0 };
let length2 = { val: 0 };
var L1 = new Node(map, startAddr1, length1);
var L2 = new Node(map, startAddr2, length2);
if (length1.val < length2.val) {
// 确保 L1 是⻓的链表
[L1, L2] = [L2, L1];
}
// 反转短链表
L2 = L2.reverse();
let [cl1, cl2] = [L1, L2];
while (cl2 !== null) {
// ⻓链表每隔2个结点，插⼀个短链表的结点。直到短链表没有剩余结点
cl1 = cl1.next;
[cl1.next, cl2.next, cl2, cl1] = [cl2, cl1.next, cl2.next, cl1.next];
}
console.log("" + L1);
});

7-2

7-3 拼接最⼤数

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number} k
* @return {number[]}
*/

// 单调栈实现，数组中得到指定⻓度的最⼤⼦序列
var MaxSubsequence = function(nums, k) {
const length = nums.length;
const stacks = new Array(k).fill(0);
let top = -1; // 栈顶位置
let remain = length - k; // 能够从栈中弹出的元素数量，保证栈中⼀定存在 k 个数满⾜要求

for(let i = 0; i < length; i++) {

const num = nums[i];
while(top >= 0 && stacks[top] < num && remain > 0) {
// 1、栈顶 >= 0
// 2、当前值 > 栈顶元素
// 3、可弹出数量 > 0
// 弹出栈顶元素
remain--;
top--;
}
 if (top < k - 1) {
stacks[++top] = num;
} else {
// 栈溢出，弹出元素
remain--;
}
}

return stacks;
}

// 合并两个数组
// 合并规则
// 1、每次取 compare 判定为⼤的数组中的索引（保证合并后的数组拼接是最⼤的）
var merge = (arr1, arr2) => {
const len1 = arr1.length;
const len2 = arr2.length;
if (len1 === 0) {
return arr2;
}
if (len2 === 0) {
return arr1;
}
const mergeLength = len1 + len2;
const merged = new Array(mergeLength).fill(0);
let index1 = 0;
let index2 = 0;
for(let i = 0; i < mergeLength; i++) {
if (compare(arr1, index1, arr2, index2) > 0) {
merged[i] = arr1[index1++]
} else {
merged[i] = arr2[index2++]
}
}

return merged
}

// ⽐较两个数组的⼤⼩
// ⽐较规则：
// 1、索引对应的值⼤，该数组判定为⼤
// 2、索引对应的值相等，则看后⾯⼀位，遵循规则1
// 3、如果其中⼀个数组遍历完了，则⻓度⻓的那个数组判定为⼤
var compare = (arr1, index1, arr2, index2) => {
const len1 = arr1.length;
const len2 = arr2.length;
while(index1 < len1 && index2 < len2) {
const diff = arr1[index1] - arr2[index2]
if (diff !== 0) {
return diff;
}
index1++;
 index2++;
}
return (len1 - index1) - (len2 - index2)
}

var maxNumber = function(nums1, nums2, k) {

const m = nums1.length;
const n = nums2.length;
const maxS = new Array(k).fill(0);
let start = Math.max(0, k - n);
let end = Math.min(k, m);
for(let i = start; i <= end; i++) {
const s1 = new MaxSubsequence(nums1, i);
const s2 = new MaxSubsequence(nums2, k - i)
const curS = merge(s1, s2);
if (compare(curS, 0, maxS, 0) > 0) {
maxS.splice(0, k, ...curS);
}
}
return maxS;
};

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
const lines = buf.split('\n');
const arr1 = lines[0].split(',').map(v => +v)
const arr2 = lines[1].split(',').map(v => +v)
const k = +lines[2];
const r = maxNumber(arr1, arr2, k)
console.log(r.join(','));
});

7-4 最⻓递增⼦序列

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
 process.stdin.on('end', function() {
const c = buf.split('\n')[0].split(' ').map((i) => parseInt(i));
const stack = [];
let ret = 0;
while (c.length > 0) {
let f = c.shift();
while (stack.length > 0 && stack[stack.length - 1] >= f) {
stack.pop();
}
stack.push(f);
ret = Math.max(ret, stack.length);
}
console.log(ret);
});

7-5