华为机试

HJ5 进制转换

写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

方法一，直接使用parseInt()

const readline = require('readline')

const rl = readline.createInterface({
  input: process.stdin
})

rl.on('line', line => {
  console.log(parseInt(line))
})

parseInt接受两个参数，第一个参数是字符串，第二个参数是进制，表示把前一个数字当成某个进制去解析，取值范围是2-36，如果第二个参数是0或者不填，会自己推断前面的数的进制最后返回一个十进制的数或者NaN。

16进制 0xa 8进制 0o7 2进制 01

方法二，自己计算

const readline = require('readline')

const rl = readline.createInterface({
	input: process.stdin,
})

const map = new Map([
	['0', 0],
	['1', 1],
	['2', 2],
	['3', 3],
	['4', 4],
	['5', 5],
	['6', 6],
	['7', 7],
	['8', 8],
	['9', 9],
	['a', 10],
	['b', 11],
	['c', 12],
	['d', 13],
	['e', 14],
	['f', 15],
])

// 0xaa1
rl.on('line', (line) => {
	let reuslt = 0 // 结果
	let position = -1 // 第几位

	// 倒着遍历 前两位是 0x
	for (let i = line.length - 1; i > 1; i--) {
		const cur = line[i]
		position++

		// 数字
		if (/[0-9]/.test(cur)) {
			reuslt += 16 ** position * map.get(cur)
		}

		// 字母
		if (/[a-fA-F]/.test(cur)) {
      reuslt += 16 ** position * map.get(cur.toLocaleLowerCase())
		}
	}

  console.log(reuslt)
})

NC61 两数之和

给一个整数数组，找里面两个数相加等于目标值的数，返回索引

/* 暴力求解 */
const findSumIndex = (arr, sum) => {
	for (let i = 0; i < arr.length; i++) {
		for (j = i + 1; j < arr.length; j++) {
			if (arr[i] + arr[j] === sum) {
				return [i, j]
			}
		}
	}

	return null
}

/* 使用个map key是数组的每一项，值是索引 */
const findSumIndex = (arr, sum) => {
	const map = new Map()

	arr.forEach((item, index) => {
		map.set(item, index)
	})

	for (let i = 0; i < arr.length; i++) {
		const diffVal = sum - arr[i]
		if (map.has(diffVal)) {
			return [i, map.get(diffVal)]
		}
	}

	return null
}

HJ3 明明的随机数

明明的随机数

控制台第一次输入，是数组的长度接下来的输入是数组的内容

最后输出排好序的去过重复的数组

快排排序 Set去重

const readline = require("readline")

const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
})

// 快速排序
function quickSort(arr: number[]) {
	// 出口
	if (arr.length <= 1) {
		return arr
	}

	// 选基准
	const pivotIndex = Math.floor(arr.length / 2)
	const pivot = arr.splice(pivotIndex, 1)[0]

	const left = []
	const right = []

	// 小于基准的放左边 大于基准的放右边
	arr.forEach((item) => {
		if (item < pivot) {
			left.push(item)
		} else {
			right.push(item)
		}
	})

	// 递归拼接结果
	return quickSort(left).concat([pivot], quickSort(right))
}
/* 
输入：
	3
	2
	2
	1
复制
输出：
	1
	2
*/

// 记录第几次输入
let count = 0
// 记录数组的长度
let arrLength = 0
// 记录数组
let arr = []

rl.on('line', (input) => {
	count++
	// 第一次输入的是数组的长度
	if (count === 1) {
		arrLength = +input
	}
	if (count > 1) {
		// 第接下来输入的是数组成员
		arr.push(+input)

		// 数组长度与输入的长度一致 表示需要输出结果
		if (arr.length === arrLength) {
			// 去重 排序
			const result = quickSort(Array.from(new Set(arr)))
			// 输出结果
			result.forEach((item) => {
				console.log(item)
			})
			rl.close()
		}
	}
})

HJ10 字符个数统计

输入一串字符串统计不重复字符的个数

使用个set 然后看set的长度

import readline from 'node:readline'

const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
})

rl.on('line', (input: string) => {
	const length = new Set(input.split('')).size
	console.log(length)
	rl.close()
})

NC68 跳台阶

题解1

题解2

一只青蛙一次可以跳上一级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

/* 
 跳台阶 每次只能跳一步或两步 有多少种跳发

 只有1级台阶 有1种跳法 f(1) = 1
 只有2级台阶 有2种跳法 先跳1级再跳1级，或者直接跳2级 f(2) = 2
 
 （推断状态转移方程）
 当有3级台阶 可以站在第1级台阶跳，也可以站在第2级台阶跳
 站在第1级台阶跳的时候，剩下2级台阶，有f(2)种跳法
 站在第2级台阶跳的时候，剩下1级台阶，有f(1)种跳法

 所以得到 f(3) = f(2) + f(1)

 推断出 f(n) = f(n-1) + f(n-2)
*/

// 直接递归效率很慢 很容易就爆栈
function trainWays(num: number): number {
	if (num === 1) {
		return 1
	}
	if (num === 2) {
		return 2
	}
	return trainWays(num - 1) + trainWays(num - 2)
}

改成for循环的 % (Math.pow(10, 9) + 7) 是题目要求的

function trainWays(n: number): number {
	const result: number[] = [1, 1]
	for (let j = 2; j < n + 1; j++) {
		result[j] = (result[j - 1] + result[j - 2]) % (Math.pow(10, 9) + 7)
	}
	return result[n]
}

HJ17 坐标移动

坐标移动，

shell

	W
A		D
	S

WSAD 这四个字母代表上下左右，非法的字母无效，求最后的坐标

比如：A10;S20;W10;D30;X;A1A;B10A11;;A10 输出：10,-10

shell

A10;								S20;					W10;					D30;					X;		A1A;		B10A11;	;		A10

`[-10, 0]`		`[-10, -20]`		`[-10, -10]`		`[20,-10]`			无效	无效		无效				`[10,-10]`

判断字符串是否是有效的
判断走多少步数
判断正负

import readline from 'readline'

/* 
		W
	A		D
		S
	上下左右判断坐标轴
*/

const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
})

// 判断方向和步数
const getStep = (str: string) => {
	if (!/^[AWDS]\d+$/.test(str)) {
		return
	}

	const result = {
		key: '',
		step: 0,
	}

	str.replace(/([AWDS])(\d+)/, (match, position, step) => {
		let _step = Number(step)
		if (position === 'A') {
			result.key = 'x'
			result.step = -_step
		} else if (position === 'D') {
			result.key = 'x'
			result.step = _step
		} else if (position === 'W') {
			result.key = 'y'
			result.step = _step
		} else if (position === 'S') {
			result.key = 'y'
			result.step = -_step
		}
		return match
	})
	return result
}

// 存储坐标
const position = {
	x: 0,
	y: 0,
}

rl.on('line', (line) => {
	const stepStrArr = line.split(';')
	stepStrArr.forEach((stepStr) => {
		const stepObj = getStep(stepStr)
		if (stepObj && stepObj.key) {
			const { key, step } = stepObj
			position[key] += step
		}
	})

	console.log(`${position.x},${position.y}`)
})

HJ20 密码验证合格程序

长度大于8位 .length
包括大小写字母、数字、其他符号至少三种
1. /\d/ 判断数字
2. /[a-z]/ 判断小写字母
3. /[A-Z]/ 判断大写字母
4. /\W/ 其他字符
不能有长度大于2，公共的重复子串

关键点是长度大于2的公共的重复子串，大于2就是3个或者3个以上的子串。可以暴力枚举，也就八位，计算也很快。或者使用正则比较巧的正则 /(\S{3,}).*\1/

(\S{3,}) 表示匹配长度至少为3的非空白字符
.*匹配任意字符
\1反向引用，匹配第一个捕获组

所以，如果这个正则匹配上，就说明有重复的大于2的公共子串。

const readline = require('readline');

const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
})

/* 
	密码合格校验
	1.长度超过8位
	2.包括大小写字母.数字.其它符号,以上四种至少三种
	3.不能有相同长度超2的子串重复
*/

// 是否有小写字母
function hasLowerCase(str: string): boolean {
	return /[a-z]/.test(str)
}

// 是否有大写字母
function hasUpperCase(str: string): boolean {
	return /[A-Z]/.test(str)
}

// 是否有数字
function hasNumber(str: string): boolean {
	return /\d/.test(str)
}

// 是否有特殊字符
function hasSpecialChar(str: string): boolean {
	// 或者 return /[^a-zA-Z0-9]/.test(str);
	return /\W/.test(str)
}

// 是否有大于2长度的重复子串
function hasRepeatSubStr(str: string): boolean {
	for (let i = 0; i < str.length - 2; i++) {
		const subStr = str.slice(i, i + 3)
		const restStr = str.slice(i + 3)
		if (restStr.includes(subStr)) {
			return true
		}
	}
	return false
}

// 是否有大于2长度的重复子串 使用正则
function hasRepeatSubStrReg(str: string): boolean {
	return /(\S{3,}).*\1/.test(str)
}

rl.on('line', (line: string) => {
	if (line.length < 8) {
		console.log('NG')
		return
	}

	let count = 0 // 记录满足条件的个数
	if (hasLowerCase(line)) {
		count++
	}
	if (hasUpperCase(line)) {
		count++
	}
	if (hasNumber(line)) {
		count++
	}
	if (hasSpecialChar(line)) {
		count++
	}

	if (count < 3) {
		console.log('NG')
		return
	}

	if (hasRepeatSubStrReg(line)) {
		console.log('NG')
		return
	}

	console.log('OK')
})

HJ23 删除字符串中出现次数最少的字符

删除字符串中出现次数最少的字符

记录每个字符出现的次数
找到次数最少的字符
拼接字符串

import readline from 'readline'

const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
})

rl.on('line', (line) => {
	const res = delMinChar(line)
	console.log(res)
})

/* 
	删除字符串中出现次数最少的字符
*/

function delMinChar(str: string): string {
	const obj = {} // 存储字符出现的次数

	// 统计字符出现的次数
	for (let i = 0; i < str.length; i++) {
		const item = str[i]
		if (Object.keys(obj).includes(item)) {
			obj[item]++
		} else {
			obj[item] = 1
		}
	}

	// 找出最小的值
	let min = Infinity
	for (const key in obj) {
		if (obj[key] < min) {
			min = obj[key]
		}
	}

	// 拼接字符串
	let result = ''
	for (let i = 0; i < str.length; i++) {
		const item = str[i]
		if (obj[item] !== min) {
			result += item
		}
	}

	return result
}

HJ33 整数与IP地址间的转换

一串ip串比如 10.0.3.193

可以转换为二进制的 00001010 00000000 00000011 11000001

然后将这一串32位二进制可以再转换为十进制 167773121

输入： 10.0.3.193 167969729

输出： 167773121 10.3.3.193

十进制转二进制 number.toSring(2)
二进制转十进制 parseInt(str, 2)
补零操作 str.padStart(8, 0)

import readline from 'readline'

const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
})

const input = []

rl.on('line', (line) => {
	input.push(line)

	if (input.length == 2) {
		input.forEach((item: string) => {
			if (item.includes('.')) {
				// 是ip
				const ipArr = item.split('.').map(Number)
				let binaryStr = ''
				ipArr.forEach((ip: number) => {
					const binary = ip.toString(2)
					binaryStr += binary.padStart(8, '0')
				})

				const intNum = parseInt(binaryStr, 2)

				console.log(intNum)
			} else {
				// 是十进制的数字
				// 十进制转2进制 补零 一共是32位
				const binary = Number(item).toString(2).padStart(32, '0')
				// 八位一组 截取字符串
				const binaryArr = binary.match(/\d{8}/g)
				let ipStrArr = []
				binaryArr.forEach((item) => {
					// 二进制转十进制
					ipStrArr.push(parseInt(item, 2))
				})
				console.log(ipStrArr.join('.'))
			}
		})
	}
})

HJ101 输入整型数组和排序标识，对其元素按照升序或降序进行排序

输入一串数字，控制升序降序

使用sort 或者自己写排序算法

const readline = require('readline')

const rl = readline.createInterface({
	input: process.stdin,
})

const inputs: string[] = []
rl.on('line', (line) => {
	inputs.push(line)

	if (inputs.length === 3) {
		const [, str, order] = inputs
		if (+order === 0) {
			const res = str.split(' ').sort((a, b) => {
				return Number(a) - Number(b)
			})
			console.log(res.join(' '))
		} else {
			const res = str.split(' ').sort((a, b) => {
				return Number(b) - Number(a)
			})
			console.log(res.join(' '))
		}
	}
})

自己写个快排去排序

const readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin
})

const inputs: string[] = []
rl.on('line', line => {
    inputs.push(line)

    if (inputs.length === 3) {
        const [, str, order] = inputs
        const res = quickSort(str.split(' ').map(Number), +order)
        console.log(res.join(' '))
    }

})

function quickSort(arr: number[], flag: number) {
    // 出口
    if (arr.length <= 1) {
        return arr
    }

    // 基准
    const pivotIndex = Math.floor(arr.length / 2)
    const pivot = arr.splice(pivotIndex, 1)[0]

    // 定义左右数组
    const left = []
    const right = []

    // 比较
    for(let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            flag === 0 ? left.push(arr[i]) : right.push(arr[i])
        } else {
            flag === 0 ? right.push(arr[i]) : left.push(arr[i])
        }
    }
    // 返回
    return quickSort(left, flag).concat([pivot], quickSort(right, flag))
}

HJ106 字符逆序

把一个字符串颠倒输出

方法太多了

使用repeat方法
倒着遍历

使用reverse

const readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin
})

rl.on('line', (line: string) => {
    const res = line.split('').reverse().join('')
    console.log(res)
})

倒着遍历

const readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin
})

rl.on('line', (line: string) => {
    let str = ''
    let index = line.length

    while(index) {
        str += line[--index]
    }

    console.log(str)
})

HJ8 合并表记录

遍历相加

const readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin
})

const inputs: string[] = []

rl.on('line', (line: string) => {
    inputs.push(line)
    const [ count, ...strs ] = inputs
    if (strs.length  === +count) {
        const tempArr = []
        strs.forEach(item => {
            const [ index, value ] = item.split(' ')
            const curNum = tempArr[index] ? tempArr[index] : 0
            tempArr[index] = (Number(curNum) + Number(value))
        })
        tempArr.forEach((item ,index) => {
            if (item !== undefined) {
                console.log(`${index} ${item}`)
            }
        })
    }
})

HJ14 字符串排序

一组字符串按照字典序排列

两种方法

直接使用sort
自己封装排序方法，逐个比较字符串，然后使用快速排序排列

直接使用sort

const readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin
})

const inputs: string[] = []
rl.on('line', (line: string) => {
    inputs.push(line)
    const [ count, ...items ] = inputs

    if(items.length === +count) {
        const res = items.sort()
        res.forEach(item => {
            console.log(item)
        })
    }
})

自己封装

const readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin
})

const inputs: string[] = []
rl.on('line', (line: string) => {
    inputs.push(line)
    const [ count, ...items ] = inputs

    if(items.length === +count) {
        const res = quickSort(items)
        res.forEach(item => {
            console.log(item)
        })
    }
})



// 比较两个字符串
function compareStr(str1: string, str2: string) {
    let index1 = 0  // str1遍历的索引
    let index2 = 0  // str2遍历的索引
    let len1 = str1.length
    let len2 = str2.length

    while(index1 < len1 && index2 < len2) {
        const s1 = str1[index1]
        const s2 = str2[index2]
        if (s1 < s2) {
            return -1
        } else if (s1 > s2) {
            return 1
        }

        index1++
        index2++
    }

    if (len1 > len2) {
        return 1
    } else if (len1 < len2) {
        return -1
    } else {
        return 0
    }
}

// 快排 按字典序
function quickSort(arr: string[]) {
    // 出口
    if (arr.length <=1) {
        return arr
    }

    // 基准
    const pivotIndex = Math.floor( arr.length / 2 )
    const pivot = arr.splice(pivotIndex, 1)[0]

    const left: string[] = []
    const right: string[] = []

    // 比较
    arr.forEach((item: string) => {
        const flag = compareStr(pivot, item)
        if (flag > 0) {
            left.push(item)
        } else {
            right.push(item)
        }
    })

    // 返回结果
    return quickSort(left).concat([pivot], quickSort(right))
}

HJ27 查找兄弟单词

判断是否是兄弟单词的方法有很多种

简单点，直接重新排序比较排好序的字符串

然后把输入输出弄明白就好了这个题的输入输出描述的太绕

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
});

rl.on("line", (line: string) => {
    const [, ...items] = line.split(" ");

    const k = items.pop();
    const base = items.pop();

    const resultArr = items
        .filter((item: string) => {
            if (isBrother(item, base)) {
                return true;
            }
        })
        .sort();

    console.log(resultArr.length)
    if(resultArr[+k - 1 ]) {
        console.log(resultArr[+k - 1 ])
    }

});

// 判断是否是兄弟单词
function isBrother(str1: string, str2: string) {
    if (str1.length !== str2.length || str1 === str2) {
        return false;
    }

    return str1.split("").sort().join("") === str2.split("").sort().join("");
}

合并区间

给个二维数组，每一项都是个区间，将重合的区间进行合并

先按照每一项的左区间排序
有几种情况
1. 当前项的右区间 < 后一项的左区间保存当前项比对后一项
2. 当前项的右区间 = 后一项的左区间合并
3. 当前项的右区间 < 后一项的右区间合并
4. 当前项的右区间 = 后一项的右区间合并
5. 当前项的右区间 > 后一项的右区间丢弃后一项

class Interval {
    start: number;
    end: number;
    constructor(start: number, end: number) {
        this.start = start;
        this.end = end;
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param intervals Interval类一维数组
 * @return Interval类一维数组
 */
export function merge(intervals: Interval[]): Interval[] {
    if (!intervals.length) {
        return [];
    }

    // 左区间排序
    intervals.sort((a: Interval, b: Interval) => {
        return a.start - b.start;
    });

    const first = intervals[0];

    const res = [new Interval(first.start, first.end)];

    for (let i = 1; i < intervals.length; i++) {
        const cur = res[res.length - 1];
        const next = intervals[i];
        if (cur.end < next.start) {
            // 下一个区间 最小值也比 当前区间最大值大
            res.push(new Interval(next.start, next.end));
        } else if (cur.end === next.start) {
            // 正好接轨
            cur.end = next.end;
        } else if (cur.end > next.start && cur.end < next.end) {
            // 有交集
            cur.end = next.end;
        } else if (cur.end === next.end) {
            // 正好包含
            cur.end = next.end;
        } else {
            // 包含下一个
            continue;
        }
    }

    return res;
}

HJ68 成绩排序

给名字和成绩，按照成绩从小到大排列或者从大到小排列但是要保持相同分数的名字顺序还是之前的。

用一个临时数组，使用成绩作为索引，收集每一项，数组索引是有序的。

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
});

const inputs: string[] = [];

rl.on("line", (line: string) => {
    inputs.push(line);

    const [count, order, ...items] = inputs;

    if (items.length === Number(count)) {
        const res = sort(items, Number(order))
        res.forEach(([name, score]) => {
            console.log(`${name} ${score}`)
        })
    }
});

function sort(items: string[], oreder: number) {
    let tempArr = [];
    items.forEach((item) => {
        const [name, score] = item.split(" ");
        if (!tempArr[score]) {
            tempArr[score] = [[name, score]];
        } else {
            tempArr[score].push([name, score]);
        }
    });

    // 获取结果
    const reuslt = [];

    if (oreder === 1) {
        // 从小到大排
        for (let i = 0; i < tempArr.length; i++) {
            const curItem = tempArr[i] as { name: string; score: string }[];
            if (curItem) {
                curItem.forEach((item) => {
                    reuslt.push(item);
                });
            }
        }
    } else {
        // 从大到小排
        for (let i = tempArr.length -1; i >= 0; i--) {
            const curItem = tempArr[i] as { name: string; score: string }[];
            if (curItem) {
                curItem.forEach((item) => {
                    reuslt.push(item);
                });
            }
        }
    }
    return reuslt;
}

使用sort

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
});

const inputs: string[] = [];

rl.on("line", (line: string) => {
    inputs.push(line);

    let [count, order, ...items] = inputs;

    if (items.length === Number(count)) {
        const newItems = items.map((item, index) => {
            const [ name, score ] =  item.split(' ')
            return [name, Number(score), index]
        })

        newItems.sort((a, b) => {
            const [name1, score1, index1] = a
            const [ name2, score2, index2 ] = b
            let scoreResult = Number(score1) - Number(score2)
            let indexResult = Number(index1) - Number(index2)
            if (Number(order) === 0) { // 倒排
                scoreResult = Number(score2) - Number(score1)
            }
            if (scoreResult === 0) {
                return indexResult
            } else {
                return scoreResult
            }
        })

        newItems.forEach(([name,score]) => {
            console.log(`${name} ${score}`)
        })
    }
});

NC52 有效括号序列

给出字符串只包含 () [] {} 判断是不是有效的

使用栈

碰到左括号就入栈
碰到右括号就与栈顶元素匹配，匹配不上就返回false，匹配上就出栈

特殊情况特殊判断

只有左括号
只有右括号


/*
    借助辅助栈 左括号入栈
 */
export function isValid(s: string): boolean {
    let stack = []

    for(let i = 0; i < s.length; i++) {
        const cur = s[i]
        if (cur === '(' || cur === '{' || cur === '[') {
            stack.push(cur)
        } else {
            const top = stack.pop()
            if (!top || (cur === ')' && top !== '(') || (cur === ']' && top !== '[') || (cur === '}' && top !== '{')) {
                return false
            }
        }
    }

    // 遍历完了 栈还未清空 说明没匹配上
    if(stack.length) {
        return false
    }

    return true
}

1614. 括号的最大嵌套深度

给定有效括号的字符串，匹配括号嵌套的最深层级

使用栈，左括号入栈，匹配到右括号出栈，保留这个过程中，栈的最大长度

function maxDepth(s: string): number {
    let stack = []
    let max = 0
    for(let i = 0; i< s.length; i++) {
        const cur = s[i]
        if(!['(', ')', '[', ']', '{', '}'].includes(cur)) { // 不是括号的跳过
            continue
        }else if (['(', '[', '{'].includes(cur)) { // 左括号入栈
            stack.push(cur)
            max = Math.max(max, stack.length) // 记录最大深度
        } else { // 是右括号
            stack.pop() // 出栈
            max = Math.max(max, stack.length) // 记录最大深度
        }
    }
    return max
};

***** 面试题 08.08. 有重复字符串的排列组合

面试题 08.08. 有重复字符串的排列组合

给一个字符串，输出全排列的结果，字符串里有重复的值

先写一个好理解的方法

先排好一个，剩下的都是没排好序的再排好一个 ... 排好了 n-1个剩下1个没排好排好了 n个剩下0个没排好（出口，记录结果）

function permutation(S: string): string[] {
    const result = recursion([], [], [...S], S)
    return Array.from(new Set(result))
};

/**
    result 存放结果集
    inOrder 排好序的
    left 未排好序的
    s 初始字符串
 */
 function recursion(result: string[] = [], inOrder: string[], left: string[],  s: string) {
    // 出口
    if (inOrder.length === s.length) {
        result.push(inOrder.join(''))
    } else {
        // 剩余的每一项都需要排列
        left.forEach((item, index) => {
            const newLeft = [...left]
            newLeft.splice(index, 1)
            recursion(result, inOrder.concat(item), newLeft, s)
        })
    }

    return result
 }

优化，重复的字符，递归过之后，就不再递归了

function permutation(S: string): string[] {
   const result = recursion([], [], [...S], S)
   return result
};

/**
   result 存放结果集
   inOrder 排好序的
   left 未排好序的
   s 初始字符串
*/
function recursion(result: string[] = [], inOrder: string[], left: string[],  s: string) {
   // 出口
   if (inOrder.length === s.length) {
       result.push(inOrder.join(''))
   } else {
       const visitedObj = {} // 保存是否排序过的状态
       for(let i = 0; i < left.length; i++) {

           const item = left[i]
           if (visitedObj[item]) {
               continue
           }

           const newLeft = [...left]
           newLeft.splice(i, 1)

           visitedObj[item] = true // 标记为使用过
           recursion(result, inOrder.concat(item), newLeft, s)
       }
   }

   return result
}

参考：js实现排列组合算法（全排列）

leetcode 77. 组合

77. 组合

参考

从 n 个数里面选出来几个数，一共有多少种取法

输入 3 2 表示从 1-3 里选出来2个输出 3
因为有 [1, 2] [1, 3] [2, 3] 三种取法

正常写法

function combine(n: number, k: number): number[][] {
	const res: number[][] = []
	if (k <= 0 || n < k) {
		return res
	}
  // 递归过程中临时存储的路径
	const path: number[] = []
	dfs(n, k, 1, path, res)
	return res
}

function dfs(n: number, k: number, begin: number, path: number[], res: number[][]): void {
	// 递归终止条件是：path 的长度等于 k
	if (path.length === k) {
		res.push([...path])
		return
	}

	// 遍历可能的搜索起点
	for (let i = begin; i <= n; i++) {
		// 向路径变量里添加一个数
		path.push(i)
		// 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
		dfs(n, k, i + 1, path, res)
		// 回溯，移除路径中最后一个元素
    // 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
		path.pop()
	}
}

剪枝

function combine(n: number, k: number): number[][] {
	const res: number[][] = []
	if (k <= 0 || n < k) {
		return res
	}
	// 递归过程中临时存储的路径
	const path: number[] = []
	dfs(n, k, 1, path, res)
	return res
}

function dfs(n: number, k: number, begin: number, path: number[], res: number[][]): void {
	// 剪枝 路径已有的加上所有剩余的数都不够k个 就不用继续递归了
	if (path.length + (n - begin + 1) < k) {
		return
	}

	// 递归终止条件是：path 的长度等于 k
	if (path.length === k) {
		res.push([...path])
		return
	}

	// 遍历可能的搜索起点
	for (let i = begin; i <= n; i++) {
		// 向路径变量里添加一个数
		path.push(i)
		// 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
		dfs(n, k, i + 1, path, res)
		// 回溯，移除路径中最后一个元素
		// 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
		path.pop()
	}
}

好理解的版本

/* 
  组合

  ['a', 'b', 'c'] 选出来两个

  ['a', 'b']
  ['a', 'c']
  ['b', 'c']
*/

function combination(arr: string[], count: number) {
	/**
	 *
	 * @param arr 原始数组
	 * @param count 需要选择的个数
	 * @param begin 当前递归的开始索引
	 * @param path 递归过程中的路径
	 * @param result 结果
	 */
	const dfs = (arr: string[], count: number, begin: number, path: string[], result: string[][]) => {
		
		// 剪枝
		const leftCount = arr.length - begin // 剩余的个数
		const curPathCount = path.length // 当前路径已经保存的个数
		if (leftCount + curPathCount < count) {
			// 如果把剩余的都加上 还不够长度，直接就不递归了
			return
		}

		// 出口
		if (path.length === count) {
			result.push([...path])
			return
		}

		for (let i = begin; i < arr.length; i++) {
			path.push(arr[i]) // 保存路径
			dfs(arr, count, i + 1, path, result)
			// 回溯 路径回退
			path.pop()
		}
	}

	const result: string[][] = []
	dfs(arr, count, 0, [], result)

	console.log(result)
}

combination(['a', 'b', 'c'], 2)

674. 最长连续递增序列

/* 
  最长递增子序列

  遍历一遍
  有一个递增 count就加1
  遇到递减 count就重置为1

  统计这个过程中count的最大值
*/

function findLengthOfLCIS(nums: number[]): number {
	let count = 1
	let max = 1

  for(let i = 0; i < nums.length - 1; i++) {
    if(nums[i] < nums[i + 1]) {
      count++
    } else {
      count = 1
    }

    max = Math.max(count, max)
  }

	return max
}

HJ75 最长公共子串计算（只能是连续的子串）

求最长公共子串（不是公共子序列）

HJ75 公共子串计算

给两个字符串，计算出最长的公共子串

shell

        a   b   c   d

        0   0   0   0

a   0   1   0   0   0 

b   0   0   2   0   0

c   0   0   0   3   0

d   0   0   0   0   4

e   0   0   0   0   0

const readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin
})

const inputs: string[] = []
rl.on('line', (line: string) => {
    inputs.push(line)
    if (inputs.length === 2) {
        const [str1, str2]  = inputs
        const result = getCommonStrLength(str1, str2)
        console.log(result)
    }
})

function getCommonStrLength(str1: string, str2: string): number {
    // 声明一个状态转移数组 二维的 多增加一行一列 用来表示初始状态
    let len1 = str1.length
    let len2 = str2.length

    let dp = new Array(len1 + 1).fill([]).map(() => {
        return new Array(len2 + 1).fill(0)
    })

    // 记录最大公共子串长度
    let max = 0

    // 比对二维数组 记录状态
    for(let i = 1; i < len1 + 1; i++) {
        for (let j = 1; j < len2 + 1; j++) {
            const a = str1[i-1]
            const b = str2[j-1]

            if (a === b) { // 相等的话 状态 + 1
                dp[i][j] = dp[i-1][j-1] + 1
            }

            max = Math.max(max, dp[i][j])
        }
    }

    return max
}

最长公共子序列（子串可以删除前缀或者后缀，也就是说不一定是连续的）

求最长公共子序列（不是公共子串）

比如 abcde ace 结果输出 3.

1143. 最长公共子序列

shell

        a   b   c   d   e

    0   0   0   0   0   0

a   0   1   1   1   1   1

c   0   1   1   2   2   2

e   0   1   1   2   2   3

function longestCommonSubsequence(str1: string, str2: string): number {
    // 初始化dp
    const len1 = str1.length
    const len2 = str2.length

    const dp = new Array(len1 + 1).fill([]).map(() => {
        return new Array(len2 + 1).fill(0)
    })

    // 遍历dp 计算状态
    for(let i = 1; i < len1 + 1; i++) {
        for( let j = 1; j < len2 + 1; j++ ) {
            const a = str1[i-1]
            const b = str2[j-1]

            if (a === b) { // 相等的话 状态+1
                dp[i][j] = dp[i-1][j-1] + 1
            } else { // 不相等的话 记录之前的最大值
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    return dp[len1][len2]
};

NC17 最长回文子串

找到一串字符串中最长的回文子串

回文串就是正反都一样的字符串

方法一暴力枚举

写个方法判断是否是回文

枚举出所有的子串保存最大回文的长度

/* 
  判断是否是回文字符串
*/
function isSymmetryStr(str: string): boolean {
	let i = 0
	let j = str.length - 1
	while (i < j) {
		if (str[i] !== str[j]) {
			return false
		}
		i++
		j--
	}

	return true
}

/* 
  暴力枚举
  枚举所有子串 保存最长的回文子串长度
*/
function getLongestPalindrome(str: string): number {
	let max = 1
	for (let i = 0; i < str.length; i++) {
		for (let j = i; j < str.length; j++) {
			let subStr = str.slice(i, j + 1)
			if (isSymmetryStr(subStr)) {
				max = Math.max(max, subStr.length)
			}
		}
	}

	return max
}

方法二使用动态规划

回文子串正反都一样，所以可以把字符翻转下，然后求两个字符串的最长公共子串就是最长回文子串

shell


export function getLongestPalindrome(s: string): number {

    const str1 = s
    const str2 = s.split('').reverse().join('')

    const len1 = str1.length
    const len2 = str2.length

    let max = 0

    const dp = new Array(len1 + 1).fill([]).map(() => {
        return new Array(len2 + 1).fill(0)
    })


    for(let i = 1; i < len1 + 1; i++) {
        for(let j = 1; j < len2 + 1; j++) {
            const a = str1[i - 1]
            const b = str2[j - 1]

            if (a === b) {
                dp[i][j] = dp[i-1][j-1] + 1 
            }

            max = Math.max(max, dp[i][j])
        }
    }

    return max
}

有个大用例过不去

const str = 'acbdcbbbdbdaaccbcacdacdccababcddabddaaaaaaabdbabcdddaacabacbacbbdabdacddbbadaacbbdcbccacacdabcabacacbbbdcccacdcdcdcbcbabdcdacdddbbabcaccddddddabdacaabccdcabcbcbabacaaaccaccaddabbdadcdacdcdbaadbcabdcdcaaacbcadccbbddbaddcaddcaadcbbcbbdcbdadcddabdddcdbddbbdabaaddcaadd'

76. 最小覆盖子串

题解

一个字符串 s1 一个字符串 s2

判断 s1中能不能涵盖 s2的所有字符子串，找到最小值

shell

比如：
    s1 = "adobecodebanc"
    s2 = "abc"

    输出 banc
    最小覆盖子串 banc 包含 所有s2的字符

使用滑动窗口(超大用例还需要优化这是我自己写的不太行)

/* 
  最小覆盖子串

  使用滑动窗口

  一个开始指针 begin，一个结束指针 end

  步骤一 先扩大窗口 end++ 直到满足条件

  步骤二 再缩小窗口 begin++ 直到不满足条件 记录下之前满足条件的结果

  重复步骤一二 直到 end 到达数组末尾
*/

function minWindow(str1: string, str2: string): string {
	let begin = 0
	let end = 0

	// 维护一个 map 存储 当前窗口中的字符
	let map = new Map<string, number>()

	// 记录结果
	let res = {
		begin: -1,
		end: -1,
		len: Infinity,
	}

	// 遍历字符串
	while (end < str1.length) {
		// 扩大滑动窗口 一直匹配到符合条件的
		while (end < str1.length) {
			// 如果当前窗口满足条件 记录结果 跳出循环
			if (check(str2, map)) {
				// 记录结果
				let curLen = end - begin
				if (res.len > curLen) {
					res = {
						begin,
						end,
						len: curLen,
					}
				}
				break
			}

			// 不满足条件 继续扩大窗口
			const key = str1[end]
			map.set(key, (map.get(key) || 0) + 1) // 记录当前窗口中的字符
			end++
		}

		// 缩小滑动窗口 一直缩小到不符合条件
		while (begin < end) {
			// 不符合条件 跳出循环
			if (!check(str2, map)) {
				break
			}
			let curLen = end - begin
			// 符合条件 记录结果 缩小窗口
			if (res.len > curLen) {
				res = {
					begin,
					end,
					len: curLen,
				}
			}

			const key = str1[begin]
			map.set(key, map.get(key) - 1) // 记录当前窗口中的字符
			begin++
		}
	}

	if (res.len === Infinity) {
    return ''
  }

  return str1.slice(res.begin, res.end)
}

// 判断当前窗口是否满足条件
function check(str2: string, map: Map<string, number>): boolean {
	// clone 一份 map
	let newMap = new Map()
	for (let [key, value] of map) {
		newMap.set(key, value)
	}

	for (let i = 0; i < str2.length; i++) {
		const key = str2[i]
		if (!newMap.get(key)) {
			return false
		}

		const newValue = (newMap.get(key) || 0) - 1

		if (newValue < 0) {
			return false
		}

		newMap.set(key, newValue)
	}

	return true
}

题解上的滑动窗口花了三个半小时才看懂代码贴上题解

/* 
  字符转换为code 'a'.charCodeAt(0)
  code转换为字符 String.fromCharCode(96)
*/
function minWindow(s: string, t: string): string {
	if (s == null || s.length === 0 || t == null || t.length === 0) {
		return ''
	}

	// 记录t中字符的个数 128个字符 是 26个字母大小写 + 10个数字 + 32个特殊字符 够表示所有字符了
	const need: number[] = new Array(128).fill(0)
	// 记录需要的字符的个数
	for (let i = 0; i < t.length; i++) {
		need[t.charCodeAt(i)]++
	}

	let l = 0 // 左指针
	let r = 0 // 右指针
	let size = Number.MAX_VALUE // 窗口大小
	let count = t.length  // 需要的字符个数
	let start = 0 // 最小覆盖串的起始位置

	// 遍历所有字符
	while (r < s.length) {
		const c = s.charCodeAt(r)
		if (need[c] > 0) { // 
			// 需要字符c
			count-- // 需要的字符个数减一
		}
		need[c]-- // 把右边的字符加入窗口
		if (count === 0) {
			// 窗口中已经包含所有字符 收缩左边窗口 直到碰到一个需要的字符
			while (l < r && need[s.charCodeAt(l)] < 0) {
				need[s.charCodeAt(l)]++ // 释放右边移动出窗口的字符
				l++ // 左指针右移
			}
			if (r - l + 1 < size) {
				// 挑战最小窗口大小，更新最小窗口开始的start
				size = r - l + 1
				start = l // 记录下最小值时候的开始位置，最后返回覆盖串时候会用到
			}
			// l向右移动后窗口肯定不能满足了 重新开始循环
			need[s.charCodeAt(l)]++
			l++
			count++
		}
		r++
	}
	return size === Number.MAX_VALUE ? '' : s.slice(start, start + size)
}

使用滑动窗口自己又写了一遍增加了注释更换了变量名更容易理解点

/**
    使用滑动窗口
    定义两个指针 begin end
    初始都从 0 开始
    步骤一 先放大滑动窗口 end++ 一直放大到满足 子串 这时候的子串已经满足覆盖条件了 但不一定是最短的
    步骤二 再缩小子串 begin++ 一直缩小到再缩小一个 就要不满足覆盖条件了 这时候的子串长度肯定比之前的短
    重复 步骤一 步骤二 一直重复到end的索引超出字符串长度 结束

    记录过程中的结果 取最短的那个
    记录最短的那个索引就行 resultStartIndex 然后记录个最短的长度 resultSize 
    最后返回的字符串 就是 str1.slice(resultStartIndex, resultStartIndex+resultSize)

    难点来了**

    难点一：声明一个数组存放需要的字符串 needArr 如果字符串是 aabb 那么就需要2个a 2个b
        有一个巧妙的办法声明数据格式，可以将字符串转换为ASII码 这样就可以直接使用数组的下标表示字符串，存储的值就表示需要的格式 所以 needArr是 number[] 格式的

        2**7 = 128 数组的长度是128个就足够表示所有字符了，因为有 26个小写+26个大写+10个数字+32个特殊字符

        使用 'a'.charCodeAt(0) 可以将字符转换为 ASII码
        使用 String.fromCharCode(90) 可以将ASII码转换为字符
    
    难点二：可以定义一个变量 用来记录 遍历过程中 需要的字符个数 count 默认是 str2.length 
        扩大滑动窗口时，每遍历得到一个所需字符 count就减1 当count为0的时候 表示滑动窗口 覆盖了所有子项 这时候就可以缩放滑动窗口了
        缩放的时候 一旦不满足要求了 count立马就加1 表示移除了一个

 */
function minWindow(str1: string, str2: string): string {
	if (!str1 || !str2) {
		return ''
	}

	// 记录所有需要的字符个数
	const needArr = new Array(128).fill(0)
	// 遍历 str2 搜集需要字符的个数
	for (let i = 0; i < str2.length; i++) {
		const charCode = str2.charCodeAt(i)
		needArr[charCode]++
	}

	let begin = 0 // 开始索引
	let end = 0 // 结束索引
	let count = str2.length // 还需要几个字符
	let resultStartIndex = 0 // 记录最终结果的开始索引
	let resultSize = Number.MAX_VALUE // 记录最终结果的长度

	// 遍历
	while (end < str1.length) {
		const curCharCode = str1.charCodeAt(end)
		if (needArr[curCharCode] > 0) {
			// 遍历到了需要的字符
			count-- // 需要字符就减一
		}

		needArr[curCharCode]-- // 遍历一个字符 就把计数器减一个 初始状态的时候 除了需要的字符大于0 其他不需要的字符都是0 所以不需要的字符遍历一次 就变成负数了 （1）

		// 需要的字符变成0个时 说明滑动窗口已经涵盖所有字符了 这时候应该开始缩放滑动窗口了
		if (count === 0) {
			// 缩放滑动窗口 一直缩放到下一个就不符合要求为止
			while (begin < end) {
				const curCharCode = str1.charCodeAt(begin)
				if (needArr[curCharCode] < 0) {
					// 在（1）中 变成负数的都是不需要的，所以可以安全的缩放滑动窗口
					needArr[curCharCode]++ // 释放左边移除窗口的字符
					begin++ // 开始指针右移 缩放窗口
				} else {
					break
				}
			}
			// 滑动窗口缩放到了下一个临界点 再缩放就不符合条件了 这时记录结果
			if (end - begin + 1 < resultSize) {
				resultStartIndex = begin // 记录当前结果开始索引
				resultSize = end - begin + 1 // 记录当前结果字符串长度
			}

			// 再缩放一位 这时缩放的一位就会不满足覆盖条件 重置下数组
			const curCharCode = str1.charCodeAt(begin)
			needArr[curCharCode]++ // 待会一移动走 这小子就又得需要一个了 所以重置一下
			begin++ // 缩放
			count++ // 移动了一位覆盖条件里的值，所需要的值就得加回来
		}

		end++
	}

	return resultSize === Number.MAX_VALUE ? '' : str1.slice(resultStartIndex, resultStartIndex + resultSize)
}

HJ41 称砝码

给一堆砝码看能称出来多少种数量

使用个set 初始化为 0

然后用set去加别的砝码这样可以一直保持不重复

/**
 1千克的砝码 2个
 2千克的砝码 1个

 使用数组表示 [1, 1, 2]
 */

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin
})

const inputs: string[] = []
rl.on('line', (line: string) => {

    inputs.push(line)

    if(inputs.length === 3) {
        let [ , weights, counts ] = inputs
        let arrs: number[] = []

        const _weights = weights.split(' ')
        const _counts = counts.split(' ')

        _weights.forEach((weight, index) => {
            const count: number = +_counts[index]
            for (let i = 0; i< count; i++) {
                arrs.push(+weight)
            }
        })

        const res = getAll(arrs)
        console.log(res)

    } 
})

function getAll(arr: number[]): number {
    const set = new Set<number>()
    set.add(0)

    for(let i = 0; i < arr.length; i++) {
        const newSet = new Set<number>(set)
        newSet.forEach(item => {
            set.add(item + arr[i])
        })
    }

    return set.size
}

二叉树的先序遍历深度优先搜索

跟左右递归实现

/* 
  二叉树的遍历
            A
          /   \
          B     C
        /   \   /
        D   E  F   
  
  先序遍历：根左右  A B D E C F
  中序遍历：左根右  D B E A F C
  后序遍历：左右根  D E B F C A

  层次遍历：A B C D E F
*/

function TreeNode(val) {
    this.val = val
    this.left = null
    this.right = null
}

const A = new TreeNode('A')
const B = new TreeNode('B')
const C = new TreeNode('C')
const D = new TreeNode('D')
const E = new TreeNode('E')
const F = new TreeNode('F')

A.left = B
A.right = C
B.left = D
B.right = E
C.left = F

const result = []
function preOrder(root) {
    // 出口
    if (!root) {
        return
    }
    result.push(root.val) // 根
    preOrder(root.left) // 左
    preOrder(root.right) // 又
}
preOrder(A)
console.log(result) // [ 'A', 'B', 'D', 'E', 'C', 'F' ]

非递归实现

/* 
  二叉树的遍历
            A
          /   \
          B     C
        /   \   /
        D   E  F   
  
  先序遍历：根左右  A B D E C F
  中序遍历：左根右  D B E A F C
  后序遍历：左右根  D E B F C A

  层次遍历：A B C D E F
*/

function TreeNode(val) {
	this.val = val
	this.left = this.right = null
}

const A = new TreeNode('A')
const B = new TreeNode('B')
const C = new TreeNode('C')
const D = new TreeNode('D')
const E = new TreeNode('E')
const F = new TreeNode('F')

A.left = B
A.right = C
B.left = D
B.right = E
C.left = F

// 先序遍历 非递归实现
function preOrder(root) {
	if (!root) {
		return
	}

	const result = [] // 存放结果
	// 使用栈模拟递归
	const stack = [root]

	while (stack.length > 0) {
		// 出栈
		let cur = stack.pop()

		if (cur !== null) {
			// 先序遍历是 根左右 所以入栈顺序就是 右左根 （因为栈是先进后出的）
			cur.right !== null && stack.push(cur.right) // 右
			cur.left !== null && stack.push(cur.left) // 左

			stack.push(cur) // 根
			stack.push(null) // 增加一个标识位，当pop出的是这个标识位时，说明栈顶的节点需要处理了
		} else {
			// 当出栈的是 null 时，说明是等待处理的节点
			cur = stack.pop() // 再次出栈，就是需要处理的节点

			// 逻辑都写在这里
			result.push(cur.val)
		}
	}

	return result
}

const res = preOrder(A)
console.log(res)

二叉树的中序遍历

左根右递归

/* 
  二叉树的遍历
            A
          /   \
          B     C
        /   \   /
        D   E  F   
  
  先序遍历：根左右  A B D E C F
  中序遍历：左根右  D B E A F C
  后序遍历：左右根  D E B F C A

  层次遍历：A B C D E F
*/

function TreeNode(val) {
	this.val = val
	this.left = this.right = null
}

const A = new TreeNode('A')
const B = new TreeNode('B')
const C = new TreeNode('C')
const D = new TreeNode('D')
const E = new TreeNode('E')
const F = new TreeNode('F')

A.left = B
A.right = C
B.left = D
B.right = E
C.left = F

const result = []
// 中序遍历 递归
function inorder(root) {
  if (!root) return
  inorder(root.left) // 左
  result.push(root.val) // 根
  inorder(root.right) // 右
}
inorder(A)
console.log(result) // [ 'D', 'B', 'E', 'A', 'F', 'C' ]

非递归

/* 
  二叉树的遍历
            A
          /   \
          B     C
        /   \   /
        D   E  F   
  
  先序遍历：根左右  A B D E C F
  中序遍历：左根右  D B E A F C
  后序遍历：左右根  D E B F C A

  层次遍历：A B C D E F
*/

function TreeNode(val) {
	this.val = val
	this.left = this.right = null
}

const A = new TreeNode('A')
const B = new TreeNode('B')
const C = new TreeNode('C')
const D = new TreeNode('D')
const E = new TreeNode('E')
const F = new TreeNode('F')

A.left = B
A.right = C
B.left = D
B.right = E
C.left = F

// 中序遍历 非递归
function inorder(root) {
	if (!root) {
		return
	}
	const result = []
	const stack = [root]

	while (stack.length > 0) {
		let cur = stack.pop()

		if (cur !== null) {
			// 中序遍历是左根右 使用栈模拟 就应该反着来  右根左 因为栈是先进后出的
			cur.right !== null && stack.push(cur.right)

			stack.push(cur)
			stack.push(null) // 添加标识位 当pop出标识位时 说明栈顶元素应该处理了

			cur.left !== null && stack.push(cur.left)
		} else {
			// 栈顶弹出null 说明该处理栈顶元素了
			cur = stack.pop()
			// 逻辑都在这里写
			result.push(cur.val)
		}
	}

	return result
}

const res = inorder(A)
console.log(res) // [ 'D', 'B', 'E', 'A', 'F', 'C' ]

二叉树的后序遍历

左右跟

递归

/* 
  二叉树的遍历
            A
          /   \
          B     C
        /   \   /
        D   E  F   
  
  先序遍历：根左右  A B D E C F
  中序遍历：左根右  D B E A F C
  后序遍历：左右根  D E B F C A

  层次遍历：A B C D E F
*/

function TreeNode(val) {
	this.val = val
	this.left = this.right = null
}

const A = new TreeNode('A')
const B = new TreeNode('B')
const C = new TreeNode('C')
const D = new TreeNode('D')
const E = new TreeNode('E')
const F = new TreeNode('F')

A.left = B
A.right = C
B.left = D
B.right = E
C.left = F

const result = []
// 后序遍历 递归
function postOrder(root) {
	if (!root) return
	postOrder(root.left) // 左
	postOrder(root.right) // 右
	result.push(root.val) // 根
}

postOrder(A)
console.log(result) // [ 'D', 'E', 'B', 'F', 'C', 'A' ]

非递归

/* 
  二叉树的遍历
            A
          /   \
          B     C
        /   \   /
        D   E  F   
  
  先序遍历：根左右  A B D E C F
  中序遍历：左根右  D B E A F C
  后序遍历：左右根  D E B F C A

  层次遍历：A B C D E F
*/

function TreeNode(val) {
	this.val = val
	this.left = this.right = null
}

const A = new TreeNode('A')
const B = new TreeNode('B')
const C = new TreeNode('C')
const D = new TreeNode('D')
const E = new TreeNode('E')
const F = new TreeNode('F')

A.left = B
A.right = C
B.left = D
B.right = E
C.left = F

// 后序遍历 非递归
function postOrder(root) {
	if (!root) {
		return
	}

	const result = []
	const stack = [root]

	while (stack.length > 0) {
		// 出栈
		let cur = stack.pop()

		if (cur !== null) {
			// 后序遍历 左右根 所以入栈顺序应该是 根 右 左 因为栈是先进后出的
			stack.push(cur) // 根
			stack.push(null) // null作为标记

			cur.right !== null && stack.push(cur.right) // 右
			cur.left !== null && stack.push(cur.left) // 左
		} else {
			// 每次弹出的是null时 栈顶元素就是该处理的节点
			cur = stack.pop()
			result.push(cur.val)
		}
	}

	return result
}

const res = postOrder(A)
console.log(res) // [ 'D', 'E', 'B', 'F', 'C', 'A' ]

二叉树的层次遍历广度优先搜索

层次遍历一层一层找使用队列

/* 
  二叉树的遍历
            A
          /   \
          B     C
        /   \   /
        D   E  F   
  
  先序遍历：根左右  A B D E C F
  中序遍历：左根右  D B E A F C
  后序遍历：左右根  D E B F C A

  层次遍历：A B C D E F
*/

function TreeNode(val) {
	this.val = val
	this.left = this.right = null
}

const A = new TreeNode('A')
const B = new TreeNode('B')
const C = new TreeNode('C')
const D = new TreeNode('D')
const E = new TreeNode('E')
const F = new TreeNode('F')

A.left = B
A.right = C
B.left = D
B.right = E
C.left = F

// 层次遍历 使用队列
function levelOrder(root) {
	if (!root) {
		return []
	}

	const result = []
	const queue = [root] // 使用栈模拟队列 队列是先进先出的 使用 push 和 shift

	while (queue.length > 0) {
		// 出队 先进先出
		const node = queue.shift()
		result.push(node.val)

		// 入队
		if (node.left) {
			queue.push(node.left)
		}
		if (node.right) {
			queue.push(node.right)
		}
	}

	return result
}

const res = levelOrder(A)
console.log(res) // [ 'A', 'B', 'C', 'D', 'E', 'F' ]

从上到下打印二叉树

JZ32 从上往下打印二叉树

层次遍历

function PrintFromTopToBottom(root: TreeNode): number[] {
    if (!root) {
        return []
    }

    const result = []
    const queue = [root] // 使用栈模拟队列

    while(queue.length > 0) {
        // 出队
        const node = queue.shift()
        result.push(node.val)

        // 入队
        if (node.left) {
            queue.push(node.left)
        }
        if (node.right) {
            queue.push(node.right)
        }
    }

    return result
}

HJ108 求最小公倍数

/*
    求两个数的最小公倍数
    可以将两数相乘 除以 两数的最大公约数

    所以就变成求两数的最大公约数

    求最大公约数可以使用辗转相除法

    比如求 252和105的最大公约数
    
    第一步：252 = 105 * 2 + 42 ，所以可以求 105 和 42 的最大公约数
    第二步：105 = 42 * 2 + 21， 所以可以求 42 和 21 的最大公约数
    第三步：42 = 21 * 2 + 0， 余数为0，算法结束，所以结果就是 21
*/

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin
})

rl.on('line', (line: string) => {
    const [a, b] = line.split(' ').map(Number)
    const lcm  = getLcm(a, b)
    console.log(lcm)
})


/*
    求最大公约数
*/
function getGcd(a: number, b: number) {
    let x = Math.max(a, b)
    let y = Math.min(a, b)

    while(y > 0) {
        const mod = x % y
        x = y // 拿小数再继续与模计算
        y = mod // 
    }
    return x
}

function getLcm(a: number, b: number) {
    const gcd = getGcd(a, b)
    return a * b / gcd
}

HJ28 素数伴侣（战略性放弃看不懂以后有时间了再细看）

HJ28 素数伴侣

参考

给一组数字，长度是偶数，每两个一组相加后是素数，就称这两个数是素数伴侣。尽可能多的找出这组数据中组成素数伴侣的个数

素数的定义：大于1的整数，除了1和它自身，不能被其他数整除，这样的数是素数，也叫质数

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
const inputs = []
rl.on('line', function (line) {
    inputs.push(line)

    if (inputs.length === 2) {
        const [count, nums] = inputs
        const res = main(nums)
        console.log(res)
    }
});


function main(str: string): number {
	const arr = str.split(' ').map(Number)

	// 奇数
	const odds: number[] = []
	// 偶数
	const evens: number[] = []

	for (let i = 0; i < arr.length; i++) {
		if (arr[i] % 2 === 0) {
			evens.push(arr[i])
		} else {
			odds.push(arr[i])
		}
	}

	const evensMatch: number[] = new Array(evens.length).fill(0)
	let result = 0

	for (let i = 0; i < odds.length; i++) {
		const used: number[] = new Array(evens.length).fill(0)
		if (find(odds[i], evens, used, evensMatch)) {
			result++
		}
	}

	return result
}

/* 
  判断一个数是否是质数
*/
function isPrime(num: number): boolean {
	if (num <= 1) {
		return false
	}

	for (let i = 2; i <= Math.sqrt(num); i++) {
		if (num % i === 0) {
			return false
		}
	}

	return true
}

function find(x: number, evens: number[], used: number[], evensMatch: number[]): boolean {
	for (let i = 0; i < evens.length; i++) {
		if (isPrime(x + evens[i]) && used[i] === 0) {
			used[i] = 1
			if (evensMatch[i] === 0 || find(evensMatch[i], evens, used, evensMatch)) {
				evensMatch[i] = x
				return true
			}
		}
	}
	return false
}

HJ60 查找组成一个偶数最接近的两个素数

任意一个大于2的偶数都可以由两个素数相加组成，找出来最接近的两个

/*
	从中间开始往两边找
	最近的两个素数就是
*/
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin
})

rl.on('line', (line: string)=> {
    const res = main(+line)
    res.forEach(num => {
        console.log(num)
    })
})


/*
    判断是否是素数
 */
function isPrime(num: number): boolean {
    if (num <=1) {
        return false
    }

    for(let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) {
            return false
        }
    }

    return true
}

/*
    给出一个偶数 找最接近的两个素数相加
 */
function main(num: number): [number, number] {
    let x = num / 2
    let y = num - x

    while(x > 1) {
        if (isPrime(x) && isPrime(y)) {
            break
        }
        x--
        y = num - x
    }

    return [x, y]
}

994. 腐烂的橘子

参考

/* 

  橘子感染速度

  每次都会感染周围的橘子 上 下 左 右

  给定一个矩阵，求多少次能感染完所有的橘子

  使用广度优先搜索

  2 1 1
  1 1 0
  0 1 1

  2表示坏橘子
  1表示好橘子
  0表示空橘子

  求所有橘子都被感染的最小时间
  也有可能有橘子永远感染不到 返回 -1
*/

function orangesRotting(grid: number[][]): number {
	const row = grid.length // 行数
	const col = grid[0].length // 列数

	// 使用广度优先搜索 需要一个队列
	const queue: number[][] = []

	let count = 0 // 表示新鲜橘子的数量

	// 遍历二维数组 找出所有新鲜橘子 和 腐烂的橘子
	for (let i = 0; i < row; i++) {
		for (let j = 0; j < col; j++) {
			if (grid[i][j] === 1) {
				count++
			} else if (grid[i][j] === 2) {
				queue.push([i, j]) // 坏橘子入队
			}
		}
	}

	let round = 0 // 表示腐烂的轮数

	// 开始遍历
	while (count > 0 && queue.length > 0) {
		// 当新鲜橘子数量为0 或者队列为空时结束
		round++ // 腐烂的轮数加1

		const n = queue.length // 当前队列的长度

		for (let i = 0; i < n; i++) {
			// 开始感染
			const [r, c] = queue.shift() // 出队

			// 上 (注意越界)
			if (r - 1 >= 0 && grid[r - 1][c] === 1) {
				// 上面有个好橘子 感染
				grid[r - 1][c] = 2 // 感染
				count-- // 新鲜橘子数量减1
				queue.push([r - 1, c]) // 入队
			}

			// 下 （注意越界）
			if (r + 1 < row && grid[r + 1][c] === 1) {
				// 下面有个好橘子 感染
				grid[r + 1][c] = 2 // 感染
				count-- // 新鲜橘子数量减1
				queue.push([r + 1, c]) // 入队
			}

			// 左 （注意越界）
			if (c - 1 >= 0 && grid[r][c - 1] === 1) {
				// 左面有个好橘子 感染
				grid[r][c - 1] = 2 // 感染
				count-- // 新鲜橘子数量减1
				queue.push([r, c - 1]) // 入队
			}

			// 右 （注意越界）
			if (c + 1 < col && grid[r][c + 1] === 1) {
				// 右面有个好橘子 感染
				grid[r][c + 1] = 2 // 感染
				count-- // 新鲜橘子数量减1
				queue.push([r, c + 1]) // 入队
			}
		}
	}

  // 最后如果还有好橘子 返回 -1 全部感染 就返回腐烂的轮数
  return count > 0 ? -1 : round
}

小优化，上下左右移动的if 使用数组表示

/* 

  橘子感染速度

  每次都会感染周围的橘子 上 下 左 右

  给定一个矩阵，求多少次能感染完所有的橘子

  使用广度优先搜索

  2 1 1
  1 1 0
  0 1 1

  2表示坏橘子
  1表示好橘子
  0表示空橘子

  求所有橘子都被感染的最小时间
  也有可能有橘子永远感染不到 返回 -1
*/

function orangesRotting(grid: number[][]): number {
	const row = grid.length // 行数
	const col = grid[0].length // 列数

	// 使用广度优先搜索 需要一个队列
	const queue: number[][] = []

	let count = 0 // 表示新鲜橘子的数量

	// 四个方向
	const directions = [
		[-1, 0], // 上
		[1, 0], // 下
		[0, -1], // 左
		[0, 1], // 右
	]

	// 遍历二维数组 找出所有新鲜橘子 和 腐烂的橘子
	for (let i = 0; i < row; i++) {
		for (let j = 0; j < col; j++) {
			if (grid[i][j] === 1) {
				count++
			} else if (grid[i][j] === 2) {
				queue.push([i, j]) // 坏橘子入队
			}
		}
	}

	let round = 0 // 表示腐烂的轮数

	// 开始遍历
	while (count > 0 && queue.length > 0) {
		// 当新鲜橘子数量为0 或者队列为空时结束
		round++ // 腐烂的轮数加1

		const n = queue.length // 当前队列的长度

		for (let i = 0; i < n; i++) {
			// 开始感染
			const [r, c] = queue.shift() // 出队

			// 四个方向开始感染 使用数组代替四个if
			for (let dir = 0; dir < directions.length; dir++) {
				const rr = r + directions[dir][0]
				const cc = c + directions[dir][1]

				const isInArea = rr >= 0 && cc >= 0 && rr < row && cc < col

				if (isInArea && grid[rr][cc] === 1) {
					// 在范围内 并且是好橘子
					grid[rr][cc] = 2 // 感染
					count-- // 新鲜橘子减1
					queue.push([rr, cc]) // 入队
				}
			}
		}
	}

	// 最后如果还有好橘子 返回 -1 全部感染 就返回腐烂的轮数
	return count > 0 ? -1 : round
}

204. 计数质数

给一个数，计算所有小于它的质数个数。

可以一个一个遍历，判断，但是时间很慢

/*
    倒着判断，是否是质数
    统计个数
*/
function countPrimes(n: number): number {
    // 计算结果
    let result = 0

    for(let i = n - 1; i > 1; i--) {
        if (isPrime(i)) {
            result++
        }
    }

    return result
};

/*
    质数只能被1和它本身整除 大于1的整数
 */
function isPrime(num: number): boolean {
    if (num <=1) {
        return false
    }

    for( let i =2; i<= Math.sqrt(num); i++ ) {
        if(num % i === 0) {
            return false
        }
    }

    return true
}

优化 TODO

HJ25 数据分类处理

/*
    关键是读懂题 两个序列 I 和 R
    序列的第一个数字 表示 后续有多少个数字
    I = [countI, ...iNums]
    R = [countR, ...rNums]

    将 rNums 排序（从小到大），然后去重，

    遍历 rNums: rNum
        将每一项 rNum 与 iNums 去匹配，记录包含的数字 iNum 和 索引 iIndex
    
    存储到 Map 里 
        {
            rNum: [
                [ iNum, iIndex  ],
            ],
            ...
        }
    
    最后遍历一遍 rNums 从 Map 取值 拼接结果 result = []
    
    遍历 rNums: rNum
    如果 Map 中 有 Map[rNum] 并且 Map[rNum].length 大于0
        result.push(rNum)
        result.push(Map[rNum].length)


        遍历 Map[rNum]: [iNum, iIndex]
        result.push(iIndex, iNum)
    
    
    最后返回结果
        result.length + result
 */

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

const inputs: string[] = []
rl.on('line', (line: string) => {
    inputs.push(line)

    if(inputs.length === 2) {
        const [I, R] = inputs.map(item => {
            return item.split(' ').map(Number)
        })

        const result = main(I, R)
        console.log(result)
    }
})



type MapItem = [number, number][]

function main(I: number[], R: number[]) {
    let [ countI, ...iNums ] = I
    let [ countR, ...rNums ] = R

    rNums = Array.from(new Set(rNums)).sort((a, b) => {
        return a - b
    })

    const map = new Map<number, MapItem>()

    rNums.forEach((rNum: number) => {
        iNums.forEach((iNum: number, iIndex: number) => {
            if (String(iNum).includes(String(rNum))) {
                if (!map.get(rNum)) {
                    map.set(rNum, [])
                }
                map.get(rNum).push([iNum, iIndex])
            }
        })
    })

    // 拼接结果
    const result: number[] = []

    rNums.forEach((rNum: number) =>{
        if (map.get(rNum) && map.get(rNum).length) {
            result.push(rNum)
            result.push(map.get(rNum).length)

            map.get(rNum).forEach(([iNum, iIndex]) => {
                result.push(iIndex, iNum)
            })
        }
    })

    return `${result.length} ${result.join(' ')}`
}

华为机试 ​

HJ5 进制转换 ​

NC61 两数之和 ​

HJ3 明明的随机数 ​

HJ10 字符个数统计 ​

NC68 跳台阶 ​

HJ17 坐标移动 ​

HJ20 密码验证合格程序 ​

HJ23 删除字符串中出现次数最少的字符 ​

HJ33 整数与IP地址间的转换 ​

HJ101 输入整型数组和排序标识，对其元素按照升序或降序进行排序 ​

HJ106 字符逆序 ​

HJ8 合并表记录 ​

HJ14 字符串排序 ​

HJ27 查找兄弟单词 ​

合并区间 ​

HJ68 成绩排序 ​

NC52 有效括号序列 ​

1614. 括号的最大嵌套深度 ​

***** 面试题 08.08. 有重复字符串的排列组合 ​

leetcode 77. 组合 ​

674. 最长连续递增序列 ​

HJ75 最长公共子串计算（只能是连续的子串） ​

最长公共子序列（子串可以删除前缀或者后缀，也就是说 不一定是连续的） ​

NC17 最长回文子串 ​

76. 最小覆盖子串 ​

HJ41 称砝码 ​

二叉树的先序遍历 深度优先搜索 ​

二叉树的中序遍历 ​

二叉树的后序遍历 ​

二叉树的层次遍历 广度优先搜索 ​

从上到下打印二叉树 ​

HJ108 求最小公倍数 ​

HJ28 素数伴侣（战略性放弃 看不懂 以后有时间了再细看） ​

HJ60 查找组成一个偶数最接近的两个素数 ​

994. 腐烂的橘子 ​

204. 计数质数 ​

HJ25 数据分类处理 ​

华为机试

HJ5 进制转换

NC61 两数之和

HJ3 明明的随机数

HJ10 字符个数统计

NC68 跳台阶

HJ17 坐标移动

HJ20 密码验证合格程序

HJ23 删除字符串中出现次数最少的字符

HJ33 整数与IP地址间的转换

HJ101 输入整型数组和排序标识，对其元素按照升序或降序进行排序

HJ106 字符逆序

HJ8 合并表记录

HJ14 字符串排序

HJ27 查找兄弟单词

合并区间

HJ68 成绩排序

NC52 有效括号序列

1614. 括号的最大嵌套深度

***** 面试题 08.08. 有重复字符串的排列组合

leetcode 77. 组合

674. 最长连续递增序列

HJ75 最长公共子串计算（只能是连续的子串）

最长公共子序列（子串可以删除前缀或者后缀，也就是说不一定是连续的）

NC17 最长回文子串

76. 最小覆盖子串

HJ41 称砝码

二叉树的先序遍历深度优先搜索

二叉树的中序遍历

二叉树的后序遍历

二叉树的层次遍历广度优先搜索

从上到下打印二叉树

HJ108 求最小公倍数

HJ28 素数伴侣（战略性放弃看不懂以后有时间了再细看）

HJ60 查找组成一个偶数最接近的两个素数

994. 腐烂的橘子

204. 计数质数

HJ25 数据分类处理