本文转自掘金 - 图雀社区：字节跳动最爱考的64道算法题（JS版）

缘起

现在大厂面试中，算法题几乎为必考项，且近几年频现 LeetCode真题，此篇为拿到字节、腾讯、京东 Offer的笔者本人在准备面试过程中亲自刷过以及遇到过高频算法题。文章内容会分模块整理，对于笔者在面试过程中遇到的真题，会给予着重
【🔥】标出。

同时，可以毫不客气的说，如果你准备时间有限，又想追求算法题准备效率最大化，那么你只需要按照大纲把下面的题目刷完，并把代码烂熟于心，就几乎可以应对
90% 的面试算法考题了。

整理这篇内容的目的一个是笔者在之前准备面试时的一点积累，而它确实也帮助笔者在面试算法题中过关斩将，同时呢，也希望能够在金三银四给予拼搏的你，一点点帮助就好！💪

文末有福利 ：）😈

本篇内容包括如下模块：

• 高频算法题系列：链表
• 【🔥】【有真题】高频算法题系列：字符串
• 【🔥】【有真题】高频算法题系列：数组问题
• 高频算法题系列：二叉树
• 【🔥】高频算法题系列：排序算法
• 【🔥】高频算法题系列：二分查找
• 【🔥】高频算法题系列：动态规划
• 高频算法题系列：BFS
• 【🔥】高频算法题系列：栈
• 【🔥】高频算法题系列：DFS
• 【🔥】高频算法题系列：回溯算法

其中标🔥的部分代表非常高频的考题，其中不乏笔者遇到的原题。其中对于每一类，首先会列出包含的考题，然后针对每一道考题会给出难度、考察知识点、是否是面试真题，在每道题详细介绍时，还会给出每道题的LeetCode链接，帮助读者理解题意，以及能够进行实际的测验，还可以观看其他人的答案，更好的帮助准备。

在Github上搭建静态博客

Hexo和jekyll都可以在Github上搭建静态博客。二者都是基于GitHub Pages实现的。他们都可以快速的搭建一个静态博客，并且在部署到GitHub上之后，你可以通过特定的域名进行访问。

今天我们主要看看如何使用Hexo来在GitHub上快速地搭建一个我们自己的静态博客。

生成的博客大概长这样

什么是Hexo

Hexo是一个快速、简洁且高效的博客框架。Hexo 使用 Markdown（或其他渲染引擎）解析文章，在几秒内，即可利用靓丽的主题生成静态网页。

安装Hexo

在安装Hexo之前，首先需要安装Node.js和Git两个工具。

引子

字节面试的过程中，被问到了一道处理大数求和的问题，求两个大数整数字符串的和，要求不能使用Number直接转换相加。

因为js中浮点数精度问题，处理大数求和的时候，不能直接使用浮点数配合科学计数法这种方式处理。这里我选取了按照各位数上的数字相加，单独处理进位数字的方式来实现的。

思路

我的大概思路是这样的：

1. 将数字字符串按照从个位到高位数字的顺序处理成数组保存；
2. 用一个结果数组保存两个运算数组各位数字相加的结果，中间需要处理满10进位的逻辑，可以使用临时变量temp存储，下一位求和的时候加上进位数字即可；
3. 需要注意最终循环结束后，如果有进位数字，需要额外处理；
4. 最终将结果数组reverse，拼接成字符串，再转换成结果数值，或者也可以遍历结果数组，把所有数位上的数字相加求值。

代码实现

下面是我的简单实现：

实现一下数组的filter方法

题目：实现一下数组的filter方法

这里需要直接在数组原型上绑定方法，同时需要注意filter参数支持传入的参数以及其顺序，第一个参数是当前元素，第二个参数是下标，第三个参数是当前数组

我的实现是这样的：

Array.prototype.myFilter = function (fn) {
    // 调用错误处理
    if (!Array.isArray(this)) {
        throw new Error('Function myFilter must be called by an array!')
    }
    // 传参错误处理
    if (typeof fn !== 'function') {
        throw new TypeError(`${fn} must be a function!`)
    }
    const res = [];
    const arr = this;
    for (let i = 0; i < arr.length; i++) {
        // 注意filter方法可以传入多个参数
        const temp = fn(arr[i], i, arr);
        if (temp) {
            res.push(arr[i]);
        }
    }
    return res;
}

const a1 = [2, 3, 4, 5, 6, 7, 8];
const fn = (el, i) => {
    return el > 4;
}
console.log('数组原生filter结果：', a1.filter(fn)); // [5, 6, 7, 8]
console.log('自定义filter结果：', a1.myFilter(fn)); // [5, 6, 7, 8]

地图服务在前端页面的某些场景下，尤其是交通和旅游相关业务中会经常见到。前端在进行地图相关业务的开发时，会遇到各种各样的问题，今天我结合一下自己之前业务开发中所遇到的一些地图相关的问题，跟大家分享一下前端地图开发过程中的一些经验。这里会省略掉一部分地图基础知识的介绍，有需要的小伙伴可以自行查阅一下相关资料。

一、选择哪个地图服务

前端进行地图相关业务开发时，需要根据具体的业务需求选择地图服务商。

对于某些地图属性需求较弱的地方，比如单纯展示一个地点在地图上的定位点，可以考虑使用静态的地图图片进行展示，这样可以直接调用地图服务的接口获取静态图片，而无需为此启用一整个地图服务。

具体选择哪一家地图服务商，可以大致参照下面的方法进行选择。

1. 如果地图业务需要在APP原生页面运行，APP内已经有很成熟的解决方案了，直接参考APP内的实现方案进行选择；

2. 如果为web端地图业务，需要进行具体的分析考虑，比如地图是不是涉及到海外数据信息的展示、业务的预估访问量、地图使用的成本等问题。

   • 如果地图需求涉及到海外地图服务，那么目前来看，可选择的就只剩下谷歌地图、百度地图，当然，高德地图和腾讯地图目前也提供海外地图服务，只是目前仍处于试用阶段。最好的选择当然是谷歌地图，只是谷歌地图还有一些其他限制，由于某些众所周知的原因，谷歌地图在国内只能走cn域名的接口，而且这个接口只能在http协议下才能调用，不能走https协议。

   • 如果地图仅仅涉及到国内地图服务，那么直接选择百度地图或者高德地图；

   • 关于使用费用问题，需要结合具体的业务访问量、收益等因素综合考量之后进行选择。

之前在项目中遇到了需要实现文件下载的方法，在网络上查找资料后，发现了下面这种通过Blob和XMLHttpRequest实现文件下载的方法。

非跨域文件的下载

// 通过 ajax 获取 Blob
function getBlob(url) {
    return new Promise(resolve => {
        const xhr = new XMLHttpRequest();
        xhr.open('GET', url, true);
        xhr.responseType = 'blob';
        xhr.onload = () => {
            if (xhr.status === 200) {
                resolve(xhr.response);
            }
        };
        xhr.send();
    });
}
// 保存重命名
function saveAs(blob, filename) {
    if (window.navigator.msSaveOrOpenBlob) {
        navigator.msSaveBlob(blob, filename);
    } else {
        const link = document.createElement('a');
        link.href = window.URL.createObjectURL(blob);
        link.download = filename;
        link.click();
        window.URL.revokeObjectURL(link.href);
    }
}
// 封装保存方法
function download(url, filename) {
    getBlob(url).then(blob => {
        saveAs(blob, filename);
    });
}

// 使用例子
download('https://github.com/vuejs/vue-router', 'vue-router.html');

上边这种方式可以解决非跨域文件的下载问题，但是遇到跨域文件时就无能为力了。

最近面试，遇到了几道题，当时没有回答好。这里记录一下，方便以后参考查阅！

数组相关

1. 在不使用遍历方法的情况下，计算数组 [1,2,3,4,5,6,7] 所有元素的平均值、获取到数组中的最大值。
当时第一眼看到这个题目的时候，还以为是要考我某个数组的api，思前想后并没有一点头绪。中间比较接近了已经，我想到了数组的join()方法。。。后来查阅资料，发现了面试官想要的答案。使用eval()方法以及Math方法。。

var arr = [1,2,3,4,5,6,7];
// 求平均值先要求出数组所有元素之和，需要用到eval()方法
// eval()方法可以返回一个字符串表达式的计算结果
// 所以先要将数组转换成为表达式，这里需要用'+'把数组所有元素连接起来，这里就要用数组的join()方法
var sum = eval(arr.join('+'));
var average = sum/arr.length;
console.log('数组中所有元素的平均值为：' + average);

// 获取最大值
var maxNum = Math.max.apply(null, arr);
console.log('数组中的最大值为：' + maxNum)

看到上边这样的方法之后，在不使用遍历方法的情况下，还可以对数组进行其他的各种运算，这里就不一一写出了。

前言

数组去重方法老生常谈，面试中经常会被问到。很多人面试时被问到时，可能只记得几种最简单的方法。其实，数组去重的方法有好几种。今天我们就一起来总结一下数组去重的方法。

双层循环

我们首先想到的方法，很可能是使用 indexOf 来循环判断一遍，但在这个方法之前，让我们先看看最原始的方法：

var array = [1, 1, '1', '1'];

function unique(array) {
    // res用来存储结果
    var res = [];
    for (var i = 0, arrayLen = array.length; i < arrayLen; i++) {
        for (var j = 0, resLen = res.length; j < resLen; j++ ) {
            if (array[i] === res[j]) {
                break;
            }
        }
        // 如果array[i]是唯一的，那么执行完循环，j等于resLen
        if (j === resLen) {
            res.push(array[i])
        }
    }
    return res;
}

console.log(unique(array)); // [1, "1"]

在这个方法中，我们使用循环嵌套，最外层循环 array，里面循环 res，如果 array[i] 的值跟 res[j] 的值相等，就跳出循环，如果都不等于，说明元素是唯一的，这时候 j 的值就会等于 res 的长度，根据这个特点进行判断，将值添加进 res。

最近更新日期：2017.10.25

1. JavaScript相关文章

阮一峰JavaScript系列文章

1. undefined 与null 的区别
2. JavaScript内存泄漏教程
3. JavaScript 运行机制详解：再谈Event Loop
4. 什么是 Event Loop？
5. http://www.ruanyifeng.com/blog/2013/10/event_loop.html
6. 浏览器的同源政策及其规避方法
7. 跨域资源共享 CORS 详解
8. JavaScript严格模式详解
9. Javascript异步编程的4种方法

张鑫旭的文章

1. 了解JS中的全局对象window.self和全局作用域self
2. 去除inline-block元素间间距的N种方法
3. …待更新

说明：

1. CentOS 7 自带的有Git，只是版本较低，好像是版本1.8.3.1，这里介绍最新版本的安装方法，如果你想更新到最新版本，可以参考这篇文档；
2. 以下所有代码均为在命令行输入的命令，$符号后的为一条完整命令，依次输入即可；
3. 在连接到服务器之后，从用户根目录开始执行下面的操作。

1. 安装依赖库。依次运行下列命令:
   $ yum install curl-devel expat-devel gettext-devel openssl-devel zlib-devel
$ yum install gcc perl-ExtUtils-MakeMaker
$ yum -y groupinstall "Development Tools"

2. 卸载旧版本的Git。运行下面的命令：
   $ yum remove git

3. 下载最新版Git到服务器
   $ wget https://github.com/git/git/archive/v2.14.0.tar.gz

4. 解压文件，进入文件夹
   $ tar zxvf v2.14.0.tar.gz
$ cd git-2.14.0

5. 编译安装
   $ make configure
$ ./configure --prefix=/usr/local/git --with-iconv=/usr/local/libiconv
$ make all doc
$ sudo make install install-doc install-html

6. 修改环境变量，编辑/etc/profile文件
   $ sudo vim /etc/profile

7. 在文件最后一行添加以下代码（按”i”进入编辑模式，输入）
   $ export PATH=/usr/local/git/bin:$PATH
   输入完成后，按ESC键退出编辑模式，然后输入:wq 并回车，保存生效

8. 输入下面这条命令
   $ source /etc/profile

9. 查看是否安装成功，使用下面这条命令：
   $ git --version

10. 如果显示 git version 2.14.0，说明Git 2.14.0安装成功