算法 101-JavaScript描述（政采云）

未完善…

1. 字符串

1.1 整数反转 LeetCode7 Medium

题目

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

思路

主要思想是将数字转换为字符串，运用字符串方法求解。先通过typeof判断所给数据是否为number类型，然后运用String()函数将其转换为字符串，再运用split()方法转换为数组，之后运用数组的reverse()方法翻转数组，再运用join()方法变成字符串。最后使用Number函数转成数字。

注意

注意判断边界情况以及数字正负号的处理。

1.2 有效的字母异位词 LeetCode242 Easy

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

思路一

先将字符串转为数组，在运用sort()方法进行排序，最后再转为字符串进行比较。

注意

js中数组不能直接比较。

思路二

创建一个对象，运用for of遍历其中一个字符串，统计每个字符出现的次数并将其作为新建对象的键值。然后再次使用for of遍历另一个字符串，处理键值。最后使用for in遍历那个对象，判断每个键值是否为0，得出结果。

注意

在运用for in和for of时应使用方括号运算符，不能使用点运算符。因为方括号运算符中的表示变量，而点运算符表示字符串。

1.3 字符串转换整数 (atoi) LeetCode8 Medium

题目

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ‘ ‘ 。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

思路一

先运用string的trim()方法去除字符串两端空格，再利用正则表达式提取满足条件的字符，最后判断是否超过边界。

注意

注意需判断是否超过边界。

思路二

先运用string的trim()方法去除字符串两端空格，再利用行 parseInt（）将字符串转为数字，最后判断是否超过边界。

注意

注意需判断是否超过边界。

1.4 外观数列 LeetCode38 Medium

题目

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：

1
2
3
4
5

1.     1
2.     11
3.     21
4.     1211
5.     111221

第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 “11”
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 “21”
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 “1211”
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 “111221”
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

思路一

运用递归的思想。要得到第n项，即处理第n-1项的结果，运用string的replace（）方法以及正则表达式进行处理替换，终止条件为n===1返回’1’。

注意

注意正则表达式的写法/(\d)\1**{0,}**/g，因至少重复0次，另外注意模板字符串的运用使用使用``反引号包裹${}。

思路二

递归法是由 n 到 1 计算相应的值并层层返回的，循环法正好相反，循环法由 1 计算到 n。然后将最终值返回。处理方法和递归的方法一致。

注意

注意正则表达式的写法/(\d)\1**{0,}**/g，因至少重复0次，另外注意模板字符串的运用使用使用``反引号包裹${}。

1.5 反转字符串 LeetCode344 Easy

题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一 问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

思路一

直接运用数组的reverse()方法。

注意

无注意事项。

思路二

写一个循环，进行首尾替换。可以引入中间变量或运用解构赋值。

1.10 最长回文子串 LeetCode5 Medium

题目

给你一个字符串 s，找到 s 中最长的回文子串。

思路一

暴力解法。用三个嵌套的for循环，列举所有的子串并判断其是否为回文子串，每次判断后记录此子串并与前一次的子串进行长度比较选取较大的子串。

思路二

中心扩展。回文子串一定是对称的，所以我们可以每次选择一个中心，然后从中心向两边扩展判断左右字符是否相等。 中心点的选取有两种情况： 当长度为奇数时，以单个字符为中心； 当长度为偶数时，以两个字符之间的空隙为中心。

注意

String的slice方法，s.slice(++i,j)在执行时第一个参数为i而非i+1,应写为++i。

思路三

动态规划。动态规划算法的核心就是记住已经解决过的子问题的解。根据字符串的长度，建立一个矩阵 dp, 通过不同情况的判断条件，通过 dp[i][j]表示 s[i] 至 s[j] 所代 表的子串是否是回文子串。不同长度的子串，根据不同的条件进行判断是否为回文子串。长度为 1，一定回文 ；长度为 2 或 3，判断首尾是否相同：s[i] === s[j] ；长度 > 3, 首尾字符相同，且去掉首尾之后的子串仍为回文。

注意

使用双层for循环遍历时，注意外层表示长度，内层表示字符串的开始位置。如果外层表示开始位置，内层表示长度，则在长度>3时判断去掉首尾之后的子串是否为回文会有误。

2. 数学

2.1 罗马数字转整数 LeetCode13 Easy

题目

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

思路一

运用for循环进行遍历，判断是否属于每一种特殊情况并做相关处理以及不属于特殊情况的处理方法。

注意

属于特殊情况时，循环计数应+1并写上continue;语句。

思路二

使用对象包含每一种特殊情况的取值，然后在罗马数字中遍历此对象，运用sString的includes（）方法判断是否存在特殊情况并作出相应处理，然后运用正则表达式的replace（）方法，替换为空字符串。最后再做常规处理，即无特殊情况的处理。

注意

运用for of遍历以及使用对象包含每一种特殊情况的取值的方法，正则表达式的replace（）方法不改变原字符串.

2.2 Fizz Buzz LeetCode412 Easy

题目

给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：

answer[i] == “FizzBuzz” 如果 i 同时是 3 和 5 的倍数。
answer[i] == “Fizz” 如果 i 是 3 的倍数。
answer[i] == “Buzz” 如果 i 是 5 的倍数。
answer[i] == i （以字符串形式）如果上述条件全不满足。

思路一

for循环，判断属于哪种情况并做相应处理，再通过Array的push方法在数组末添加元素。

3. 数组

3.1 轮转数组 LeetCode189 Medium

题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

思路一

首先计算出需要截取的数组元素的长度，即 k = k % nums.length;然后运用Array的splice()方法，截取需要移动的成员，再通过数组的扩展运算符 ... 并运用Array的unshift()方法，放到数组前面。

注意

注意需计算出需要截取的数组元素的长度，可降低时间复杂度，另外需区分Array的splice()和slice()的区别，前者会改变原数组，后者不会改变。

思路二

1.首先计算出需要循环移动的次数； 2. 通过数组的 unshift() 和 pop() 方法实现旋转，循环执行 k 次。

注意

先使用pop()方法，再使用unshift()方法，unshift()方法将把它的参数插入数组的头部，并将已经存在的元素顺次地移到较高的下标处，这种处理不会占用额外空间。

3.2 只出现一次的数字 LeetCode136 Easy

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出 现了一次的元素。

思路一

使用reduce方法,将数组的一个元素与下一个元素做异或比较。由于有一个数只出现了一次，其他数皆出现了两次，最后相同的数都会异或成0，唯一出现的数与0异或就会得到其本身。

注意

主要是对于异或的运用。

3.3 两数之和 LeetCode1 Easy

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

思路一

通过双重循环，暴力枚举每一种组合，再通过判断语句，如果两数满足和为target，则返回它们的数组下标。

注意

因为题目要求元素在答案里不能重复出现，且可以按任何顺序返回答案，所以部分组合已经遍历过，无需重复遍历。

思路二

利用哈希表，运用Array的some()方法进行处理，将每个元素的值和它的索引加到表中，检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中。

注意

判断成立的条件应为typeof lookup[target - v] ==="number"，如果为lookup[target - v]在下标为0时会判断错误。

3.4 旋转图像 LeetCode48 Medium

题目

给定一个 n × n 的二维矩阵表示一个图像，将图像顺时针旋转 90 度。 必须在原地旋转图像，需要直接修改输入的二维矩阵，不要使用另一个矩阵来旋转图像。

思路一

先将矩阵沿左上角到右下角的对角线进行对称,运用for双层循环，内层循环的计数值的初始值为外层循环的计数值，然后将矩阵沿垂直中线对称即可。运用for双层循环，内层循环计数值小于Math.floor(n / 2)，n为矩阵长度。

注意

注意两个for双层循环的内层循环计数值的初始值即范围。

3.5 删除有序数组中的重复项 LeetCode26 Easy

题目

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。

思路一

运用for循环，在循环时，如果后面的数与当前循环的值相同，则利用Array的splice()方法，删除当前数，数组长度减一。

注意

注意删除数组中的数后，应注意数组长度和循环计数值的关系，，处理后数组长度减一，splice()方法的用法，第一个参数是删除开始位置，第二个参数值删除个数，且改变原数组。

思路二

我们用 一个数组 来记录不重复的下标数量，第一个数必定不是重复的，即 nums[0] 肯定是不重复的， 所以从第二项（即 nums[1]）开始，遍历数组，判断该下标的值跟不重复的数组最后一个元素 nums[count] 是否相同，如果不相同，将该元素值赋值给 nums[count + 1] ，然后 count++，继续遍 历。待遍历结束时，我们可以通过 count 数量来判断不重复元素个数，因为 count 是从 0 开始的， 故返回的新数组的长度为 count + 1。

注意

注意从第二项开始遍历。

3.14 字母异位词分组 LeetCode49 Medium

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

思路一

排序分类。先创建个空对象，用于储存字母异位词，然后创建个空数组，用与返回结果。遍历数组里的元素，将每个字母异位词进行排序，并将排序后的字符串作为 key，可知 key 值一样的即为字母异位 词，将他们置于同一个数组中， 待上述遍历结束，再遍历对象，将 对象的每一个值，push 到数组中。

思路二

计数分类。和思路一的不同在于判断两个字符串是否为字母异位词的方法不同。我们先遍历数组，每次都创建一个长度为 26，元素全是 0 的数组，用于记录每个单词中每个字符出现的次数；然后将其转化为字符串作为 key，将 key 值一样的字母异位词置于同一个数组中。最 后返回数组。

注意

数组间不能直接判断是否相同，可以运用JSON.stringify()转换数组为字符串进行判断

3.15 三数之和 LeetCode15 Medium

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

思路一

首先对数组进行排序，便于在插入的时候去重，进行双指针遍历时，遇到重复的数就方便跳过。设两个指针指向数组首尾，每次计算两个指针所指数与每次遍历的数三数之和，因为数组已经从小到大排序了，所以如果三数之和大于0则尾指针前移，小于0则首指针后移，如果等于0则添加此组合，并进行去重。

注意

在数组中因避免这种写法：while(left<right&&r===nums[right-1]){right–;}，在加粗出容易超出边界。

思路二

三重循环，但是时间会超时，不做详解。

3.16 无重复字符的最长子串 LeetCode3 Medium

题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

思路一

初始化一个数组和最大值， 从前向后遍历字符串， 如果该字符不在数组中（使用Array的indexOf()方法进行判断），则把字符 push 到数组中，并且比较记录下当前最大值。 否则就从头部向外shift字符直到该重复字符被移除（也可以使用slice（）方法直接截断数组,a.slice(a.indexOf(s[i])+1,i+1)）， 如此循环直到结束。

思路二

通过for (char of s){}遍历字符串，记录当前正在遍历的不重复字串的子集 string ， 在遍历过程中不断地添加不重复字符，遇到重复字符则截断 string 达到 string 内补字符不重复的条件。

4. 链表

4.1 回文链表 LeetCode234 Easy

题目

请判断一个链表是否为回文链表。进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路一

主要思想为字符串拼接比较，遍历链表，定义两个临时变量为空字符串，做处理a=a+head.val;b=head.val+b;存储正、反两个拼接的字符串， 比较正、反字符串是否相同。

思路二

定义一个全局指针初始化值为head，用于正序遍历，运用调用递归函数进行链表的逆序遍历，递归出口为 head 为 null，返回true，即遍历结束，判断正序遍历的节点值是否全部都等于逆序遍历的节点值。

注意

注意此方法的空间复杂度为0(n),另外注意递归的使用方法。

4.2 环形链表 LeetCode141 Easy

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

思路一

定义两个指针，即快慢指针，利用while循环，循环条件为快指针不为空以及快指针的next不为空。两个指针同时出发，快指针一次走两步，慢指针一次走一步。 如果快指针和慢指针相遇，则证明此链表是环形链表，不相遇则不是环形链表。

注意

注意while循环条件为快指针不为空以及快指针的next不为空。

思路二

利用哈希表数据结构，使用Es6的Map数据结构，新建一个空的Map对象，在while中进行遍历，每次循环在Map中新增一个键值对，键名为当前节点，键值为1，遍历中，判断Map 对象中是否存在相同节点且值为 1，即判断该节点是否已经遍历过了，则可得出该链表是否为环形链表。

注意

注意该方法空间复杂度为O（n），另外注意Map用法。

思路三

运用ES6中新引入的一种数据类型–Symbol，它代表独一无二的值:

1
2
3
4

let s1 = Symbol();
let s2 = Symbol();

s1 === s2 // false

在遍历中将每个节点的 val 值改为用 Symbol 创建的独一无二的值，若循环过程中存在节点的 val 等于这个值，那么证明当前不是第一次循环到该节点，即链表为环形链表，反之不是。

4.3 删除链表中的节点 LeetCode237 Easy

题目

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

思路一

删除给定的节点，在获取当前节点后，将下一个节点的值赋给当前节点， 然后将当前节点指向下下个节点，完成删除。

思路二

利用Object.assign() 方法， Object.assign(a,b) 能合并两个对象(a和b)，并覆盖到第一个参数(a)所指的地址上（可以改变地址），让node.next覆盖 node，即node的所有属性都是node.next的所有属性，包括next和val.

注意

Object.assign(node,node.next)，即node的所有属性都是node.next的所有属性，包括next和val.

4.4 反转链表 LeetCode206 Easy

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题

思路一

用迭代的方法实现. 先存储其前一个节点，在遍历链表过程中，申请一个新的临时空间用于前后元素交换。

思路二

用递归的方法实现。

注意

注意每层递归函数都返回反转前的尾结点，也就是反转后的头节点（返回的结点是不变的，且此返回值不对后续处理造成影响），此外为了防止链表循环，需要将head.next设置为空。还有再次注意到js中null表示空，这需要与c语言中NULL做区分。

4.5 删除链表的倒数第 N 个结点 LeetCode19 Medium

题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

思路一

双指针法。先设first和second指向head，让first 指针前进 n，如果 first为空，说明要删除的节点正是 head 节点，那么直接返回 head 的下一个节点。如果不为空，则让让 second 从 head 开始和 first 一起前进，直到 first 到了最后，此时 second 的下一个节点就是要删除的节点，做出 second.next = second.next.next处理。

注意

注意first为空时的处理，还有second.next = second.next.next这一步，而不是second.next=first，这仅适用于n为2时。

思路二

单向链表成为双向链表。先遍历，让单向链表成为双向链表，先找到其尾节点，从这个节点向前查找，n–，直到n=1时，此时的节点就是我们要找的节点，然后直接删除。

4.6 合并两个有序链表 LeetCode21 Easy

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路一

创建一个新链表，通过判断两个链表当前值，将较小值放到新链表的下个节点，较小值的链表重新赋值为其下一节点，直到参数链表都为空时结束。

思路二

用递归的方式， 若两个链表中有一个链表为空，则返回另一个链表,依次比较两个链表中首项的大小，保留数值小的为链表当前值，直到一个链表参数为空则结束。

4.7 两数相加 LeetCode2 Medium

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路一

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。

注意

注意需要保存进位值用于下一位相加，另外当链表遍历完时，如果进位值大于0，应再加一个结点存储进位值。

思路二

将输入的链表转换为逆序的字符串（字符串可以更容易的取出每一位数，无论是正序取出还是逆序取出），再将字符串转换为数（可以考虑使用BigInt,确保精度），然后将两个链表转换的数相加，再转换为字符串，然后逆序放入新的链表。

5. 二叉树

5.1 最小栈 LeetCode155 Medium

题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

思路一

创建最小元素栈时，开辟两个数组，一个用于存储压栈元素，另一个用于存储最小元素序列。push栈数据同时，存储当前栈中最小元素，pop栈数据的同时pop最小元素栈栈顶数据.

思路二

用一个 min 变量保存最小值,min初始值为0（只要不超出数值范围均可，因为后面在第一次push时，会将入栈的值赋值给min，但是建议为0，因为不容易出现溢出），每次push操作压栈时,保存的是入栈的值和最小值min的差值，而不是入栈的值。pop出栈时，通过 min 值和栈顶的值得到。

注意

注意仅第一次push时，会将入栈的值赋值给min（需要对数组的长度进行判断），另外在top方法中应注意处理数组长度为1时，直接返回数组中唯一的值，不需要再加min,因为数组的第一个值就是min.最后注意在两数差值有溢出风险。

6. 动态规划

6.1 最大子数组和 LeetCode53 Medium

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

思路一

从数组获取第一个值为最大值和中间值 ,遍历数组，如果中间值大于0,则和中间值相加，相加结果和最大值比较，较大值赋值给最大值。如果中间值小于0，则将当前值作为中间值。

思路二

分治方法。运用递归，每次求得左右两半部分各自最大子数组和，然后处理两个部分一起的最大子数组和。递归结束条件为左右下标相等。

6.2 爬楼梯 LeetCode70 Easy

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路一

递归+记忆化数组。递归函数：f(n) = f(n − 1) + f(n − 2)，创建一个记忆化数组，记录楼层计算过的结果，降低时间复杂度。

思路二

动态规划+滚动数组。f(n) = f(n − 1) + f(n − 2)。但是由于这里的f(n)只和 f(n - 1) 与 f(n - 2)有关，所以可以用滚动数组思想.

6.6 跳跃游戏 LeetCode55 Medium

题目

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路一

贪心。先初始化最远位置为0，然后遍历数组，如果当前位置能到达，并且当前位置+跳数>最远位置，就更新最远位置， 每次循环都比较当前最远位置和当前数组下标，如果最远距离小于等于当前下标就返回false。

思路二

动态规划。遍历数组，每到一个点 ，我们就去判断是否可以到达当前点；如果可以，就记录true，否则为 false，最后判断是否可以到达最后一个点。

6.7 不同路径 LeetCode62 Medium

题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

思路一

动态规划。利用双层for循环，状态转移方程为 dp[i][j] = dp[i − 1][j] + dp[i][j − 1]。

思路二

深度优先搜索+记忆化数组。dfs[i][j] = dfs[i − 1][j] + dfs[i][j − 1]。开辟一个记忆数组记录结果。

思路三

组合数学。从左上角到右下角的过程中，我们需要移动 m+n-2 次，其中有 m-1次向下移动，n-1次向右移动。因此路径的总数，就等于从 m+n-2次移动中选择 m-1次向下移动的方案数。

7. 回溯算法

7.1 括号生成 LeetCode22 Medium

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

思路一

采用回溯法，如果自定义的字符串长度刚好满足条件，那么就说明这个组合是正确的的，把它放入数组。 否则，递归执行添加左括号，添加右括号的操作。递归结束条件为结果字符串长度等于左右括号的总个数（2n），则返回最终结果。

7.3 电话号码的字母组合 LeetCode17 Medium

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路一

利用队列的先进先出的特点，把队列中的第一个元素拿出，再与后面的挨个拼接

1. 先在队列中插入一个空字符
2. 取出队列中的第一个元素，与后一位数字对应的字符进行挨个拼接 。
3. 重复第二步，直到结束。

注意

let a = [1, 2, 3];

let b = a;

let c = a;

此代码中a,b,c仍然是同一个地址。

思路二

回溯。可以穷举所有的可能性，找到所有的可能性。回溯过程中维护一个字符串，表示已有的字母排列。 如果有数字需要被输入，就遍历数字对应的字母进行组合 。 当发现没有数字输入时，说明已经走完了，得到结果。

7.4 全排列 LeetCode46 Medium

题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

思路一

回溯法.构造一颗生成树，遍历需要全排列的数组，将不同位置的数字与目前树结合起来 ,重复该操作直到需要全排列的数组长度为 0，即表明完成了全排列，因为数字不能重复，所以在每次遍历后应对数组做出处理，之后传入剩余的数组。

注意

在递归中应注意不要使用数组的push()方法，最好使用扩展运算符。

思路二

插值排列法。遍历需要全排列的数组，将不同位置的数字抽离出来，插入到剩余数组的不同位置，即可得到该数字与另一个数组的全排列结果。 将一个固定的数字，插入到另一个数组 的全排列结果的不同位置， 遍历需要全排列的数组，将不同的数字连接到不同的树上继续全排列剩下的数组与生成的树，当剩余数组长度为0时，表明完成了全排列。

8. 排序算法

8.9 搜索旋转排序数组 LeetCode33 Medium

题目

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

思路一

先用Math.min.apply(null, nums)和Math.max.apply(null, nums)计算数组中的最大最小值。当目标值大于数组最后一位时，数组查询位置从 0 到数字中在最大位置，当目标值小于等于数组最后一位时，数组查询位置从数组中最小值的位置开始，到数组的最后一 位。 循环二分查询，计算定位数组的中间值，数组的值等于目标查询结束。

注意

此方法时间复杂度不为 O(log n)，因为求了最大值与最小值。

思路二

定义左右值分别为数组第一个和最后一个的下标 ，中间下标值为最大最小值的平均数 ，如果数组中间数等于目标直接返回下标 。数组的中间值小于数组最后一个值，后半部分还处于升序，如果目标值在这部分数组中，则左下标等于中间值+1，代表目标值在后半部分数组，反之重新定义右下标为中间值-1，目标在前半数组。 数组中间值大于数组最后一个值，代表前半部分数组处于升序，如果目标在前半数组中，右标 更新为中间值-1，反之，左下标更新为中间值+1。循环二分查询，计算定位数组的中间值，数组的值等于目标查询结束。

注意

二分查找主要是同过目标值与中间值进行比较，从而直接确定目标值在哪一部分。如果不是升序或降序数组，则需要进一步确定目标值位置。

8.10 在排序数组中查找元素的第一个和最后一个位置 LeetCode34 Medium

题目

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

思路一

二分查找，找到左边第一个不小于目标值的位置 ,然后从位置开始到最后，二分查找，确定右边最后一个符合条件值的位置 ，最后校验下标是否符合，得到结果。

8.12. 颜色分类 LeetCode75 Medium

题目

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

思路一

双指针遍历.设定一头一尾两个指针 begin 和 end，然后利用for循环从头开始遍历数组。如果遇到 0，则将该数值与begin指向的值交换，并且使begin++。 如果遇到 2，则将该数值与end指向的值交换，并且使end–。 如果遇到 1，则不做操作。

8.15 合并区间 LeetCode56 Medium

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

思路一

先将列表中的区间按照左端点升序排序。定义一个新的数组，用于存储新的数组区间，新数组的第一个值为原数组的第一个值。然后从第二个值开始遍历原数组，比较当前区间的最小值是否大于新数组最后一个区间的最大值， 如果满足则push进入新的数组；又或者比较当前区间的最大值是否大于新新数组的随后一个区间的最大值，若满足则将新数组的最后一个区间的最大值替换成当前区间的最大值。

注意

要先进行原数组排序操作，可以降低做题难度。

9. 栈和队列

9.6 有效的括号 LeetCode20 Easy

题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

思路一

利用头插法建立链栈，如果使用尾插法建立则不易删除节点（即出栈操作）。在遇到左括号的时候，将其入栈。在遇到右括号的时候，刚好就可以与栈中的左括号进行匹配，如果正确，就把左括号出栈 。 如果最终栈为空，说明全部匹配成功。

注意

注意JS的垃圾回收机制。在链表中:

let a = new ListNode(1);

let b = a;

a = null;

b仍然指向新建的空间，不为空。

另外需要使用头插法建立链表。

思路二

用 Map 数据类型，建立数组栈。在遇到左括号的时候，将其入栈。在遇到右括号的时候，刚好就可以与栈中的左括号进行匹配，如果正确，就把左括号出栈 。 如果最终栈为空，说明全部匹配成功。