快来退出咱们吧！

"小和山的菜鸟们"，为前端开发者提供技术相干资讯以及系列根底文章。为更好的用户体验，请您移至咱们官网小和山的菜鸟们 ( 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 = 4person.c = 5console.log('1:', person.b)console.log('2:', person.c)person.__proto__.b = 10console.log('3:', person.b)console.log('4:', Otaku.prototype.b)

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

咱们先来揭晓答案：

1: 12: 53: 14: 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 的原型的属性 bperson.c = 5 // 批改的是 person 的 cconsole.log('1:', person.b) // person.b = 1console.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 = 2Otaku.prototype.b = 4 // 批改的是 person 的原型的属性 bperson.c = 5 // 批改的是 person 的 cconsole.log('1:', person.b) // person.b = 1console.log('2:', person.c) // person.c = 5person.__proto__.b = 10 // 批改的事 preson 的原型的属性bconsole.log('3:', person.b) // person.b = 1console.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 = thisif (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 或者动静布局等等办法都能够解决，解决办法十分多样。这种问题也会有许多变种，比方输入门路等等。

样例代码：

// BFSconst 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)}