关于前端:前端面试系列六手写程序算法题

35次阅读

共计 6640 个字符，预计需要花费 17 分钟才能阅读完成。

快来退出咱们吧！

“ 小和山的菜鸟们 ”，为前端开发者提供技术相干资讯以及系列根底文章。为更好的用户体验，请您移至咱们官网小和山的菜鸟们 (https://xhs-rookies.com/) 进行学习，及时获取最新文章。

“Code tailor”，如果您对咱们文章感兴趣、或是想提一些倡议，微信关注 “小和山的菜鸟们” 公众号，与咱们取的分割，您也能够在微信上观看咱们的文章。每一个倡议或是同意都是对咱们极大的激励！

面试系列不定期更新，请随时关注

前言

本篇专栏重点在于解说面试中 手写程序题 / 算法题 的面试题内容。

留神： 本篇专栏至只会波及到重点内容，并不会进行拓展。某些题目须要拓展知识点的，咱们会将拓展内容、整体详细信息搁置与每个题目的最后面，能够自行查看。

手写程序题 / 算法题

手写程序题 / 算法题
程序输入题目：构造函数与实例对象间的属性问题
程序编程题：flat、拍平数组、本人实现拍平数组的成果
程序编程题：本人实现 promise all
程序编程题：本人实现 reducer
程序编程题：URL 解析为对象
程序编程题：应用 setTimeout 写一个 setInterval
算法题：无反复字符最大子串的问题
算法题：二叉树的前中后遍历
算法题：迷宫问题
算法题：手写冒泡排序
算法题：不齐全的二叉树的倒置

题目解析

构造函数与实例对象间的属性问题

以下代码输入什么？

function Otaku() {
  this.b = 1
  this.c = 2
}
var person = new Otaku()
Otaku.prototype.b = 4
person.c = 5
console.log('1:', person.b)
console.log('2:', person.c)
person.__proto__.b = 10
console.log('3:', person.b)
console.log('4:', Otaku.prototype.b)

这道题目波及到构造函数与实例对象之间的知识点，背地同样波及原型与原型链的问题，具体见 JavaScript 深刻之从原型到原型链。

咱们先来揭晓答案：

1: 1
2: 5
3: 1
4: 10

你有全答对吗？上面咱们一起来看看这道题。这道题首先给了一个构造函数 Otaku，这个构造函数有两个属性 b 和 c，而后应用 new 创立了它的实例对象 person, 如果你理解原型，那么你必定晓得实例对象 person 曾经取得了构造函数中的属性。

function Otaku() {
  this.b = 1
  this.c = 2
}
var person = new Otaku() // person.b = 1; person.c = 2

看到这里你会发现构造函数 Otaku 有一个属性 prototype，这个构造函数的 prototype 属性指向了一个对象，这个对象正是调用该构造函数而创立的 实例 的原型，也就是这个例子中的 person 原型。也就是说 Otaku.prototype.b = 4; 这条语句中的 b 理论指向的是原型的 b。

function Otaku() {
  this.b = 1
  this.c = 2
}
var person = new Otaku()
Otaku.prototype.b = 4 // 批改的是 person 的原型的属性 b
person.c = 5 // 批改的是 person 的 c
console.log('1:', person.b) // person.b = 1
console.log('2:', person.c) // person.c = 5

看到这里，咱们又发现 person 的属性 __proto__, 这个属性也指向 person 的原型，所以这句话的 b 属性也是指向原型的 b

function Otaku() {
  this.b = 1
  this.c = 2
}
var person = new Otaku() // person.b = 1; person.c = 2
Otaku.prototype.b = 4 // 批改的是 person 的原型的属性 b
person.c = 5 // 批改的是 person 的 c
console.log('1:', person.b) // person.b = 1
console.log('2:', person.c) // person.c = 5
person.__proto__.b = 10 // 批改的事 preson 的原型的属性 b
console.log('3:', person.b) // person.b = 1
console.log('4:', Otaku.prototype.b) // Otaku.prototype.b = 10

这就是后果了，对于这道题波及的知识点，重点还是在原型以及原型链上。

程序编程题

1. flat、拍平数组、本人实现拍平数组的成果

这里只提供两个比较简单的实现，前面还会波及到应用 reduce 和栈、应用Generator、原型链等等，具体见：面试官连环诘问：数组拍平（扁平化）flat 办法实现 – 知乎 (zhihu.com)”)

  1. 最简略的遍历实现
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, 'string', {name: '弹铁蛋同学'}]
// concat + 递归
function flat(arr) {let arrResult = []
  arr.forEach((item) => {if (Array.isArray(item)) {arrResult = arrResult.concat(flat(item)) // 递归
      // 或者用扩大运算符
      // arrResult.push(...arguments.callee(item));
    } else {arrResult.push(item)
    }
  })
  return arrResult
}
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "弹铁蛋同学"}];
  1. 传入数组管制递归层数
// reduce + 递归
function flat(arr, num = 1) {
  return num > 0
    ? arr.reduce((pre, cur) => pre.concat(Array.isArray(cur) ? flat(cur, num - 1) : cur), [])
    : arr.slice()}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, 'string', {name: '弹铁蛋同学'}]
flat(arr, Infinity)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "弹铁蛋同学"}];

2. 本人实现 promise all

Promise.newAll = function (promiseArr) {let results = []

  return new Promise((reslove, reject) => {promiseArr.forEach((item_promise) => {item_promise.then((res) => results.push(res)).catch((err) => reject(err))
    })
    return reslove(results)
  })
}

3. 本人实现 reducer

留神：不能应用箭头函数，箭头函数中没有 this 所有会导致 sourcearr 为空对象

Array.prototype.fakereduce = function (fn, initnumber = 0) {
  let sum_increase = initnumber
  let sourcearr = this
  for (let i = 0; i < sourcearr.length; i++) {sum_increase = fn(sum_increase, sourcearr[i])
  }
  return sum_increase
}

这个只是最根本的，只蕴含前两个参数，也没有检测是否为函数。(上面退出判断状况)

// 判断调用对象是否为数组
if (Object.prototype.toString.call([]) !== '[object Array]') {throw new TypeError('not a array')
}
// 判断调用数组是否为空数组
const sourceArray = this
if (sourceArray.length === 0) {throw new TypeError('empty array')
}
// 判断传入的第一个参数是否为函数
if (typeof fn !== 'function') {throw new TypeError(`${fn} is not a function`)
}

4. URL 解析为对象

将以下输出的 URL 转化为对象：

http://www.baidu.com/s?wd= 春节 &name=justin

{
    wd: '春节',
    name: 'justin'
}

这道题重点在于宰割，将 ? 后的键值对取出来，并搁置于对象中，不同的键值对通过 & 符号宰割。具体代码如下（这里也只给出一种解法）：

let urlToJson = (url = window.location.href) => {
  // 箭头函数默认传值为以后页面 url
  url = url.encodeURIComponent()
  let obj = {},
    index = url.indexOf('?'),
    params = url.substr(index + 1)

  if (index != -1) {let parr = params.split('&')
    for (let i of parr) {let arr = i.split('=')
      obj[arr[0]] = arr[1]
    }
  }
  return obj
}

5. 应用 setTimeout 写一个 setInterval

扩大： 应用 setInterval 实现一个 setTimeout

const mySetInterval = (callback, time) => {;(function inner() {const timer = setTimeout(() => {callback()
      clearTimeout(timer)
      inner()}, time)
  })()}

算法题

1. 无反复字符最大子串的问题

具体请见：3. 无反复字符的最长子串 – 力扣（LeetCode）(leetcode-cn.com)”)

大抵有两种办法：暴力遍历、滑动窗口

这边给出滑动窗口代码，详情解释请看 leetcode 解析：

var lengthOfLongestSubstring = function (s) {
  // 哈希汇合，记录每个字符是否呈现过
  const occ = new Set()
  const n = s.length
  // 右指针，初始值为 -1，相当于咱们在字符串的左边界的左侧，还没有开始挪动
  let rk = -1,
    ans = 0
  for (let i = 0; i < n; ++i) {if (i != 0) {
      // 左指针向右挪动一格，移除一个字符
      occ.delete(s.charAt(i - 1))
    }
    while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
      // 一直地挪动右指针
      occ.add(s.charAt(rk + 1))
      ++rk
    }
    // 第 i 到 rk 个字符是一个极长的无反复字符子串
    ans = Math.max(ans, rk - i + 1)
  }
  return ans
}

2. 二叉树的前中后遍历

二叉树构造如下：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**

遍历办法有很多种，咱们这边采纳递归的办法。

前序遍历：

function preOrderReducer(head) {if (head === null) {return}
  console.log(head.val)
  preOrderReducer(head.left)
  preOrderReducer(head.right)
}

中序遍历

function preOrderReducer(head) {if (head === null) {return}
  preOrderReducer(head.left)
  console.log(head.val)
  preOrderReducer(head.right)
}

后序遍历

function preOrderReducer(head) {if (head === null) {return}
  preOrderReducer(head.left)
  preOrderReducer(head.right)
  console.log(head.val)
}

3. 迷宫问题

题目形容：

在一个 n * m 的迷宫内，终点为【0，0】，起点为【n -1，m -1】，现须要你判断该迷宫是否有至多一条通路。如果有通路即返回 true，否则返回 false。

n * m 迷宫内可能会遇到墙壁，如果以后地位为 1，则代表以后地位是墙壁，不能行走。

输出： n、m、maze（数组）

输入： true / false

例如：

input：3 3 [[0,1,1],[0,0,0],[0,1,0] ]
output: true

题目解析：

一般来说 BFS、DFS 或者动静布局等等办法都能够解决，解决办法十分多样。这种问题也会有许多变种，比方输入门路等等。

样例代码：

// BFS
const findMazeWay = (n, m, maze) => {if (maze[(0, 0)] === 1) {
    // 如果终点为墙壁则间接无解
    return false
  } else {return dfsSearch(0, 0, maze)
  }
  function dfsSearch(index_n, index_m, maze) {maze[index_n][index_m] = -1 // 走过的路断定为 -1
    if (index_n === n - 1 && index_m === m - 1) {return true}
    if (index_m + 1 <= m - 1 && maze[index_n][index_m + 1] === 0)
      dfsSearch(index_n, index_m + 1, maze)
    if (index_n + 1 <= n - 1 && maze[index_n + 1][index_m] === 0)
      dfsSearch(index_n + 1, index_m, maze)
    if (index_m - 1 >= 0 && maze[index_n][index_m - 1] === 0) dfsSearch(index_n, index_m - 1, maze)
    if (index_n - 1 >= 0 && maze[index_n - 1][index_m] === 0) dfsSearch(index_n - 1, index_m, maze)
  }
}

console.log(
  findMazeWay(3, 3, [[0, 1, 1],
    [0, 0, 1],
    [1, 0, 0],
  ]),
)

问题拓展：如果胜利了，请输入至多一条胜利门路。（或是输入所有可胜利的门路）

4. 手写冒泡排序

样例代码：

function mySort(arr) {for (let i = 0; i < arr.length - 1; i++) {for (let j = i; j < arr.length; j++) {if (arr[i] > arr[j]) {let temp = arr[j]
        arr[j] = arr[i]
        arr[i] = temp
      }
    }
  }
}

5. 不齐全的二叉树的倒置

题目形容：

假如有一棵树二叉树，咱们须要将其左子树全副转化为右子树。（对于每一个子节点，都须要转化）

树形构造如下:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**

题目解析：

这道题重点在于遍历树，并且在遍历的状况下，须要替换两个子树，所以不能采纳 DFS 深度遍历。遍历办法有很多种，这里给出的解决方案为其中的一种。

样例代码：

const treeReBuild(tree: TreeNode){if(tree === null){return}
    let temp = tree.right
    tree.right = tree.left
    tree.left = temp

    treeReBuild(tree.left)
    treeReBuild(tree.right)
}

正文完
前端
发表至： 前端
2021-08-25
 0
关于前端:如何在-Kitten-里绘制两个相邻的正方体并响应用户输入事件
关于前端:Plugin-和-Loader-的区别
关于前端:window系统如何调试苹果手机
关于前端:PWA-应用和原生应用的一些区别