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

“ 小和山的菜鸟们 ”，为前端开发者提供技术相干资讯以及系列根底文章。为更好的用户体验，请您移至咱们官网小和山的菜鸟们 (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 深刻之从原型到原型链。

咱们先来揭晓答案：

你有全答对吗？上面咱们一起来看看这道题。这道题首先给了一个构造函数 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

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

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

最简略的遍历实现

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: "弹铁蛋同学"}];

传入数组管制递归层数

// 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: "弹铁蛋同学"}];

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

留神：不能应用箭头函数，箭头函数中没有 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`)
}

将以下输出的 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
}

扩大： 应用 setInterval 实现一个 setTimeout

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

具体请见：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
}

二叉树构造如下：

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

题目形容：

在一个 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],
  ]),
)

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

样例代码：

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
      }
    }
  }
}

题目形容：

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

树形构造如下:

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

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

快来退出咱们吧！

前言

手写程序题 / 算法题

题目解析

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

程序编程题

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

2. 本人实现 promise all

3. 本人实现 reducer

4. URL 解析为对象

5. 应用 setTimeout 写一个 setInterval

算法题

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

2. 二叉树的前中后遍历

3. 迷宫问题

4. 手写冒泡排序

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