Interview -- 基础手写题
大约 5 分钟
数组去重方法汇总
- 利用
Set去重 - 利用
for循环遍历，includes（能识别 NAN）、indexOf（不能识别 NAN）
// 1. set 去重
function unique(arr) {
// 或者 return Array.from(new Set(arr))
return [...new Set(arr)]
}
// 2. for 循环遍历
function unique2(arr) {
if (!Array.isArray(arr)) return
const resArr = []
for (const item of arr) {
if (!resArr.includes(item)) {
resArr.push(item)
}
}
return resArr
}
对象相等判断
function deepEqual(obj1, obj2) {
if (obj1 === obj2) return true
if (
typeof obj1 !== 'object' ||
obj1 === null ||
typeof obj2 !== 'object' ||
obj2 === null
) {
return false
}
const keys1 = Object.keys(obj1)
const keys2 = Object.keys(obj2)
if (keys1.length !== keys2.length) return false
for (const key of keys1) {
if (!keys2.includes(key) || !deepEqual(obj1[key], obj2[key])) return false
}
}
手写 Array 的 filter、map、some、every 和 reduce 方法
手写 filter
Array.prototype.myFilter = function (callback) {
const len = this.length
const res = []
for (let i = 0; i < len; i++) {
const item = this[i] // 当前项
if (callback(item)) {
res.push(item)
}
}
return res
}
const words = ['spray', 'elite', 'exuberant', 'destruction', 'present']
const result = words.myFilter((word) => word.length > 6)
console.log('🚀 ~ myFilter:', result)
手写 map
Array.prototype.myMap = function (callback) {
const len = this.length
const res = []
for (let i = 0; i < len; i++) {
const item = this[i]
res.push(callback(item))
}
return res
}
const array = [1, 4, 9, 16]
const map1 = array.myMap((x) => x * 2)
console.log('🚀 ~ myMap:', map1)
手写 some
Array.prototype.mySome = function (callback) {
const len = this.length
for (let i = 0; i < len; i++) {
const item = this[i]
if (callback(item)) {
return true
}
}
return false
}
const array = [1, 2, 3, 4, 5]
const even = (element) => element % 2 === 0
console.log('🚀 ~ mySome:', array.mySome(even))
手写 every
Array.prototype.myEvery = function (callback) {
const len = this.length
for (let i = 0; i < len; i++) {
const item = this[i]
if (!callback(item)) {
return false
}
}
return true
}
const isBelowThreshold = (currentValue) => currentValue < 40
const array = [1, 30, 39, 29, 10, 13]
console.log('🚀 ~ myEvery:', array.every(isBelowThreshold))
手写 reduce
Array.prototype.myReduce = function (callback, pre) {
const len = this.length
for (let i = 0; i < len; i++) {
if (pre !== undefined) {
pre = callback(pre, this[i], i, this)
} else {
pre = callback(this[i], this[i + 1], i, this)
i++ // 提前一项结束
}
}
return pre
}
const array = [1, 2, 3, 4]
// 0 + 1 + 2 + 3 + 4
const initialValue = 0
const sumWithInitial = array.reduce(
(accumulator, currentValue) => accumulator + currentValue,
initialValue
)
console.log('🚀 ~ myReduce:', sumWithInitial)
实际应用： runPromisesInSequence
const runPromisesInSequence = (array, initialValue) => {
array.reduce((promiseChain, currentFunction) => {
return promiseChain.then(currentFunction)
}, Promise.resolve(initialValue))
}
实现一个简单的模板引擎
const tpl = template('<p>hey there {{ name }} {{ name }}</p>')
const res = tpl({ name: 'Neo' })
console.log('🚀 ~ template:', res)
function template(str) {
return function (obj) {
for (let key in obj) {
const val = obj[key]
const reg = new RegExp(`{{\\s+${key}\\s+}}`, 'g')
str = str.replace(reg, val)
}
return str
}
}
对象扁平化
/**
* 对象扁平化
* 说明：请实现 flatten(input) 函数，input 为一个 javascript 对象（Object 或者 Array），返回值为扁平化后的结果。
* 示例：
* var input = {
* a: 1,
* b: [ 1, 2, { c: true }, [ 3 ] ],
* d: { e: 2, f: 3 },
* g: null,
* }
* var output = flatten(input);
* output如下
* {
* "a": 1,
* "b[0]": 1,
* "b[1]": 2,
* "b[2].c": true,
* "b[3][0]": 3,
* "d.e": 2,
* "d.f": 3,
* // "g": null, 值为null或者undefined，丢弃
* }
*/
function flatten(obj) {
const res = {}
const recur = (target, oldKey) => {
for (const key in target) {
let newKey = ''
if (oldKey) {
// 区分是否是初次递归
if (Array.isArray(target)) {
newKey = `${oldKey}[${key}]`
} else {
newKey = `${oldKey}.${key}`
}
} else {
if (Array.isArray(target)) {
newKey = `[${key}]`
} else {
newKey = key
}
}
if (target[key] != null) {
// 剔除非空结果
if (typeof target[key] === 'object') {
recur(target[key], newKey) // 递归扁平值
} else {
res[newKey] = target[key] // 添加结果
}
}
}
}
recur(obj, '')
// 返回扁平结果
return res
}
const inputObj = {
a: 1,
b: [1, 2, { c: true }, [3]],
d: { e: 2, f: 3 },
g: null,
}
console.log('🚀 ~ flatten:', flatten(inputObj))
根据表达式计算字母数
/**
* 根据表达式计算字母数
* 说明：
* 给定一个描述字母数量的表达式，计算表达式里的每个字母实际数量
* 表达式格式：
* 字母紧跟表示次数的数字，如 A2B3
* 括号可将表达式局部分组后跟上数字，(A2)2B
* 数字为1时可缺省，如 AB3。
* 示例：
* countOfLetters('A2B3'); // { A: 2, B: 3 }
* countOfLetters('A(A3B)2'); // { A: 7, B: 2 }
* countOfLetters('C4(A(A3B)2)2'); // { A: 14, B: 4, C: 4 }
*/
function countOfLetters(str) {
let i = 0
const strLen = str.length
const strMap = [new Map()] // 栈
/** 获取当前字母后续的数字 */
const getNum = () => {
if (i === strLen || isNaN(Number(str[i]))) {
return 1 // 到末尾了 || 不是数字，视作 1
}
let num = 0
while (i < strLen && !isNaN(Number(str[i]))) {
num = num * 10 + Number(str[i]) // 扫描数字
i++
}
return num
}
while (i < strLen) {
const curStr = str[i]
if (curStr === '(') {
i++
strMap.unshift(new Map()) // 压栈
} else if (curStr === ')') {
i++
const beforeMap = strMap.shift() // 退栈
const newMap = strMap[0]
const num = getNum() // 获取括号后的数字
// 合并对象
for (const [beforeStr, beforeNum] of beforeMap.entries()) {
newMap.set(beforeStr, (newMap.get(beforeStr) || 0) + beforeNum * num)
}
} else {
// 当前为字母
const mapStr = curStr // 当前字母
i++
const curNum = getNum() // 获取字母数量
const curMap = strMap[0]
curMap.set(mapStr, (curMap.get(mapStr) || 0) + curNum) // 统计数量
}
}
const resMap = strMap[0]
return Object.fromEntries(resMap.entries())
}
// 测试
console.log(countOfLetters('A2B3')) // { A: 2, B: 3 }
console.log(countOfLetters('A(A3B)2')) // { A: 7, B: 2 }
console.log(countOfLetters('C4(A(A3B)2)2')) // { A: 14, B: 4, C: 4 }
数组转 tree 结构的数据
思路:
建立查找表：遍历原始数组，创建一个对象（查找表），其中每个节点的 id 是键，节点本身（包括一个空的 children 数组）是值。这一步允许我们快速查找每个节点。
构建树结构：再次遍历原始数组，根据每个节点的 parentId 将其添加到相应父节点的 children 数组中。如果节点没有 parentId，则将其视为根节点，直接添加到最终的树数组中。
function arrayToTree(array) {
const tree = []
const lookup = {}
// 创建一个查找表，以便快速访问每个节点
array.forEach((item) => {
lookup[item.id] = { ...item, children: [] }
})
// 构建树结构
array.forEach((item) => {
if (item.parentId === null) {
// 如果没有 parentId，说明是根节点
tree.push(lookup[item.id])
} else {
// 否则，将当前节点添加到其父节点的 children 数组中
if (lookup[item.parentId]) {
lookup[item.parentId].children.push(lookup[item.id])
}
}
})
return tree
}
// 示例数据
const data = [
{ id: 1, parentId: null, name: '根节点1' },
{ id: 2, parentId: 1, name: '子节点1-1' },
{ id: 3, parentId: 1, name: '子节点1-2' },
{ id: 4, parentId: 2, name: '子节点1-1-1' },
{ id: 5, parentId: null, name: '根节点2' },
{ id: 6, parentId: 5, name: '子节点2-1' },
]
const tree = arrayToTree(data)
console.log(JSON.stringify(tree, null, 2))
Loading...