Appearance
全局配置
分类题目
一、字符串类
1. 反转字符串中的单词
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入："Let's take LeetCode contest" 输出："s'teL ekat edoCteeL tsetnoc"
提示： 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string-iii
javascript
/**
* @param {string} s
* @return {string}
*/
const reverseWords = (str) => {
return str.length ? str.match(/[\S]+/g).map(item => {
return item.split('').reverse().join('')
}).join(' ') : ''
}2.计数二进制字符串
给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。
重复出现的子串要计算它们出现的次数。
示例 1 :
输入: "00110011" 输出: 6 解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
请注意，一些重复出现的子串要计算它们出现的次数。
另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。 示例 2 :
输入: "10101" 输出: 4 解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
提示：
s.length 在1到50,000之间。 s 只包含“0”或“1”字符。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-binary-substrings
分析： 规律如下 
从头开始找，每次索引后移一位进行查找。
代码思路1：
- 需要循环遍历，从头开始，到倒数第二位结束，因为条件限制至少两位数（具有相同数量的连续1和0），最后一位就不用遍历了。 for (i = 0; i < str.length - 1; i ++;)
- 每次循环内需要做的事为，找到当前索引开始，到结尾处，满足条件的字符串。 r = match(str.slice(i))
- 如果满足条件 if r
- 就将其放入存放最终结果的数组中 result.push(r)
javascript
const countBinarySubstrings = (str) => {
// 建立数据结构，堆栈，保存数据
let r = []
// 给定任意子输入都返回第一个符合条件的子串
let match = (str) => {
// 如果找到前一部分，连续的1或者0
let j = str.match(/^(0+|1+)/)[0]
// 继续匹配接下来的字符串是否满足条件：如果是0开头的子串，看接下来j.length长度的子串是否是1。如果是1开头子串，类推。
// 这里需要注意的是“异或”运算：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。即1^1为0，0^1为1。
let o = (j[0] ^ 1).toString().repeat(j.length)
let reg = new RegExp(`^(${j}${o})`)
if (reg.test(str)) {
// RegExp.$1是RegExp的一个属性,指的是与正则表达式匹配的第一个子匹配(以括号为标志)字符串
// RegExp这个对象会在我们调用了正则表达式的方法后, 自动将最近一次的结果保存在里面,这里我们也可以用str.slice(0, j.length * 2 - 1)
return RegExp.$1
} else {
return ''
}
}
// 通过for循环控制程序运行的流程
for (let i = 0, len = str.length - 1; i < len; i++) {
let sub = match(str.slice(i))
if (sub) {
r.push(sub)
}
}
return r.length
}该方法当字符串过大时，可能出现如下错误:Uncaught SyntaxError: Invalid regular expression: 。。。。。。。 Regular expression too large at RegExp.test，很有可能通不过测试。
代码思路2： 我们可以将字符串 ss 按照 00 和 11 的连续段分组，存在counts 数组中，例如 s = 00111011，可以得到这样的 counts 数组：counts = [2, 3, 1, 2]。 即[00,111,0,11]。
这里counts 数组中两个相邻的数一定代表的是两种不同的字符。假设counts 数组中两个相邻的数字为 u 或者 v，它们对应着 u 个 0 和 v 个 1，或者 u 个 1 和 v 个 0。它们能组成的满足条件的子串数目为 min { u, v }即一对相邻的数字对答案的贡献。
我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。即min(2,3) + min(3,1) + min(1,2) = 4。
javascript
var countBinarySubstrings = function(s) {
const counts = [];
let ptr = 0, n = s.length;
while (ptr < n) {
const c = s.charAt(ptr);
let count = 0;
while (ptr < n && s.charAt(ptr) === c) {
++ptr;
++count;
}
counts.push(count);
}
let ans = 0;
for (let i = 1; i < counts.length; ++i) {
ans += Math.min(counts[i], counts[i - 1]);
}
return ans;
};这个实现的时间复杂度和空间复杂度都是 O(n)O(n)。
对于某一个位置 i，其实我们只关心 i−1 位置的 counts 值是多少，所以可以用一个 last 变量来维护当前位置的前一个位置，这样可以省去一个 counts 数组的空间。
javascript
var countBinarySubstrings = function(s) {
let ptr = 0, n = s.length, last = 0, ans = 0;
while (ptr < n) {
const c = s.charAt(ptr);
let count = 0;
while (ptr < n && s.charAt(ptr) === c) {
++ptr;
++count;
}
ans += Math.min(count, last);
last = count;
}
return ans;
};二、数组类
1.电话号码组合（公式运算）
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1： 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2： 输入：digits = "" 输出：[]
示例 3： 输入：digits = "2" 输出：["a","b","c"]
提示： 0 <= digits.length <= 4 digits[i] 是范围 ['2', '9'] 的一个数字。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
javascript
export default (str) => {
// 对输入做处理，如果小于1返回空（LeetCode测试用例）
if (str.length < 1) return []
// 建立电话号码键盘映射
let map = ['', 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
// 如果只给了一个按键，直接把按键内容取出来并按单个字符分组就可以了（LeetCode测试用例）
if (str.length < 2) return map[str].split('')
// 把输入字符串按单字符分隔变成数组，234=>[2,3,4]
let num = str.split('')
// 保存键盘映射后的字母内容，如 23=>['abc','def']
let code = []
num.forEach(item => {
if (map[item]) {
code.push(map[item])
}
})
// 递归函数，不停的将数组前两项字符串组合
let comb = (arr) => {
// 临时变量用来保存前两个组合的结果
let tmp = []
// 最外层的循环是遍历第一个元素，里层的循环是遍历第二个元素
for (let i = 0, il = arr[0].length; i < il; i++) {
for (let j = 0, jl = arr[1].length; j < jl; j++) {
// 每项组合的结果
tmp.push(`${arr[0][i]}${arr[1][j]}`)
}
}
// 删除原本的前两项，并用两项生成结果的数组代替，
arr.splice(0, 2, tmp)
// 如果有超过两项的内容，就表示用生成的结果继续和第三项进行组合递归调用
if (arr.length > 1) {
comb(arr)
} else {
return tmp
}
// 最终结果会被合成到第一项数组当中
return arr[0]
}
// 返回这个递归函数的结果
return comb(code)
}
javascript
const letterCombinations = (digits) => {
if (digits.length == 0) return [];
const res = [];
const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
// dfs: 当前构建的字符串为curStr，现在“翻译”到第i个数字，基于此继续“翻译”
const dfs = (curStr, i) => { // curStr是当前字符串，i是扫描的指针
// 深度遍历到最深一层后，再下一次，数组越界，就将上次（最深一层）的结果放进res数组。
// 例如，234，一次深度遍历curStr变化过程a->ad->adg->将adg放进res中
if (i > digits.length - 1) { // 指针越界，递归的出口
res.push(curStr); // 将解推入res
return; // 结束当前递归分支
}
const letters = map[digits[i]]; // 当前数字对应的字母
for (const letter of letters) { // 一个字母是一个选择，对应一个递归分支
dfs(curStr + letter, i + 1); // 选择翻译成letter，生成新字符串，i指针右移继续翻译（递归）
}
};
dfs('', 0); // 递归的入口，初始字符串为''，从下标0开始翻译
return res;
};2.卡牌分组（归类运算）
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。
示例 1： 输入：[1,2,3,4,4,3,2,1] 输出：true 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
示例 2： 输入：[1,1,1,2,2,2,3,3] 输出：false 解释：没有满足要求的分组。
示例 3： 输入：[1] 输出：false 解释：没有满足要求的分组。
示例 4： 输入：[1,1] 输出：true 解释：可行的分组是 [1,1]
示例 5： 输入：[1,1,2,2,2,2] 输出：true 解释：可行的分组是 [1,1]，[2,2]，[2,2]
提示： 1 <= deck.length <= 10000 0 <= deck[i] < 10000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards
分析： 1.输入的数组是无序的 -> 根据示例结果，需要将其排序 2.每组都有x张牌，组内数量相同 -> 每组数量相同，但由示例5中可得知，不同数字的数量是不同，但却可以分组使其每组数量相同。-> 需要求最大公约数 3.求最大公约数需要用到欧几里得算法，即辗转相除法。两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。 gcd(a,b) = gcd(b,a mod b) // gcd是英文Greatest Common Divisor（最大公约数）的缩写。 证明如下：
md
// 若g为a、b的公约数则g满足：
a = g * l // ①
b = g * m // ②
// 其中，l、m为整数，同时，a又可由b表示为:
a = k * b + r // ③ k不等于0。
//其中，k为整数，r为a除以b后的余数，那么由①②可将③变形为：
g * l = k * g * m + r
// 移项得：
r = g * (l - k * m) // 所以g是a和b的最大公约数，同时也是a除以b的余数（即a mod b）的公约数。
// 如何证明g是a mod b 的 "最大" 公约数呢？
// 反证法：假设存在g' > g 且 g' 同时整除 b 和 a mod b（在下式中记为r),那么必有:
b = g' * m'
r = g' * l'
// 又由③可得：
a = k * g' * m' + g' * l' = g'( m'k + l')
// 所以，g'也是a、b的公约数，但a、b的最大公约数已经为g，而又存在 g' > g 为a、b的公约数这显然矛盾，故证明 gcd(a,b) = gcd(b,a mod b)而求a、b的最大公约数有递归和非递归两种形式： 递归版：
javascript
function gcd (a, b) {
if (b === 0) {
return a;
} else {
return gcd(b, a % b)
}
}非递归版：
javascript
function gcd (a, b) {
while(b !== 0) {
let t = a % b
a = b
b = t
}
return a
}javascript
// 每一组都有X张牌，那么X和卡牌总数N,从数学的角度上说，X是N的约数。两个或多个整数共有约数中最大的一个被称为最大公约数。最后还需要判断该公约数是否大于等于2。
var hasGroupsSizeX = function(deck) {
// 最大公约数计算公式
function gcd(num1, num2) {
// 利用辗转相除法来计算最大公约数
return num2 === 0 ? num1 : gcd(num2, num1 % num2);
}
// 相同牌出现次数Map
let timeMap = new Map();
// 遍历牌
deck.forEach(num => {
// 统计每张牌出现的次数
timeMap.set(num, timeMap.has(num) ? timeMap.get(num) + 1 : 1);
});
// Map.protype.values()返回的是一个新的Iterator对象，所以可以使用扩展运算符(...)来构造成数组
let timeAry = [...timeMap.values()];
/*
最大公约数
因为该数组是出现次数数组，最小值至少为1（至少出现1次），所以默认赋值为数组首位对公约数计算无干扰
*/
let g = timeAry[0];
// 遍历出现次数，计算最大公约数
timeAry.forEach(time => {
// 因为需要比较所有牌出现次数的最大公约数，故需要一个中间值
g = gcd(g, time);
});
// 判断是否满足题意
return g >= 2;
};3.种花问题（筛选运算）
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。
示例 1： 输入：flowerbed = [1,0,0,0,1], n = 1 输出：true
示例 2： 输入：flowerbed = [1,0,0,0,1], n = 2 输出：false
提示： 1 <= flowerbed.length <= 2 * 104 flowerbed[i] 为 0 或 1 flowerbed 中不存在相邻的两朵花 0 <= n <= flowerbed.length
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/can-place-flowers
分析： 
javascript
var canPlaceFlowers = function(flowerbed, n) {
// 计算当前两个下标之间能种花的数量
let count = 0;
// 整个花坛的长度
const m = flowerbed.length;
// 前一个种花位置的索引
let prev = -1;
// 遍历整个花坛
for (let i = 0; i < m; i++) {
// 如果某个位置有种花
if (flowerbed[i] === 1) {
// 从头开始均未种过话
if (prev < 0) {
// 此时 当前位置至起点可种花 i / 2 （向下取整）朵花
count += Math.floor(i / 2);
// 否则
} else {
// 当前位置至前一次有花的位置，可种花的数量为，两个位置之差，再减2（因为不能挨着边上两朵花），再除2
count += Math.floor((i - prev - 2) / 2);
}
// 此时，记录当前位置存进前一次位置变量中
prev = i;
}
}
// 遍历完成后，还剩最右边花坛的位置，如果前一次位置仍为初始值-1，即从头到尾根本没有种过花
if (prev < 0) {
// 总数就为，花坛长度+1，再除2，向下取整（因为最边上是可以种花的）
count += (m + 1) / 2;
} else {
// 否则之前是有种过花的，那么最右侧可种花数量为：最终的位置的索引(m - 1) - 前一次有花的位置（prev），再除2向下取整
count += (m - prev - 1) / 2;
}
// 计算满足规则种花的数量是否大于等于要求的数量
return count >= n;
};4.格雷编码（二进制运算）
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
格雷编码序列必须以 0 开头。
示例 1: 输入: 2 输出: [0,1,3,2] 解释: 00 - 0 01 - 1 11 - 3 10 - 2 对于给定的 n，其格雷编码序列并不唯一。 例如，[0,2,3,1] 也是一个有效的格雷编码序列。 00 - 0 10 - 2 11 - 3 01 - 1
示例 2: 输入: 0 输出: [0] 解释: 我们定义格雷编码序列必须以 0 开头。 给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。 因此，当 n = 0 时，其格雷编码序列为 [0]。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/gray-code
分析： 以n=0,1,2,3,4的结果来看
md
// 10进制
[0]
[0, 1]
[0, 1, 3, 2]
[0, 1, 3, 2, 6, 7, 5, 4]
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
// 2进制，更明显的规律见下图
["0"]
["0", "1"]
["00", "01", "11", "10"]
["000", "001", "011", "010", "110", "111", "101", "100"]
["0000", "0001", "0011", "0010", "0110", "0111", "0101", "0100", "1100", "1101", "1111", "1110", "1010", "1011", "1001", "1000"]我们可以发现，随着数字位数n的增加，格雷编码后一位编码的总可以依赖前一位编码有规律的构成： 1.先按2机制处理，最后转为10进制。 2.后一次结果的上半部分：总是对前一次的结果的加0。（加0数值不变，即仍为前一次的结果。） 3.后一次结果的下半部分：总是对前一次的结果倒序后在最前面加1。（加1，相当于1向左移动了n位后再加上原来各自的数再逆序） 4. 左移操作：例如， a << b，将 a 的二进制形式向左移 b 比特位，右边用0填充。 5.以n=3为例，下半部分的规律为 ，1向左移动3位，即100 分别加上原本的 [00， 01， 11， 10]再逆序。 100 + 000 100 + 001 100 + 011 100 + 010 就相当于(1 <<< 3) 和原本n=2时的各数字进行按位"或"操作。
从右往左看图，从上往下看数：
javascript
/**
* @param {number} n
* @return {number[]}
*/
var grayCode = function (n) {
if (n === 0) return [0];
const codes = grayCode(--n);
return [...codes, ...codes.map(x => (1 << n) | x).reverse()];
};三、正则类
1.重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1: 输入: "abab" 输出: True 解释: 可由子字符串 "ab" 重复两次构成。
示例 2: 输入: "aba" 输出: False 输入: "abcabcabcabc" 输出: True 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/repeated-substring-pattern
分析： 使用模式匹配及其捕获，详见 https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Guide/Regular_Expressions#special-capturing-parentheses
解1：
javascript
var repeatedSubstringPattern = function(s) {
let reg = /^(\w+)\1+$/
return reg.test(s)
};解2： 假设母串S是由子串s重复N次而成， 则 S+S则有子串s重复2N次， 现在S=Ns，S+S=2Ns 因此s在(S+S).slice(1,-1)中必出现一次以上;
创建一个新的字符串str,它等于原来的字符串S再加上S自身，这样其实就包含了所有移动的字符串。 直接判断str中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串。
javascript
**
* @param {string} s
* @return {boolean}
*/
var repeatedSubstringPattern = function(s) {
let s1 = (s + s).slice(1, -1);
return s1.indexOf(s) != -1;
};2.正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。 '.' 匹配任意单个字符 '' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1： 输入：s = "aa" p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
示例 2: 输入：s = "aa" p = "a*" 输出：true 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3： 输入：s = "ab" p = "." 输出：true 解释："." 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4： 输入：s = "aab" p = "cab" 输出：true 解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5： 输入：s = "mississippi" p = "misisp*." 输出：false
提示： 0 <= s.length <= 20 0 <= p.length <= 30 s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。 保证每次出现字符 * 时，前面都匹配到有效的字符
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/regular-expression-matching
分析：
javascript
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var regMatch = function (s, p) => {
let isMatch = (s, p) => {
// 边界情况，如果s和p都为空，说明处理结束了，返回true，否则返回false
if (p.length <= 0) {
return !s.length
}
// 判断p模式字符串的第一个字符和s字符串的第一个字符是不是匹配
let match = false
if (s.length > 0 && (p[0] === s[0] || p[0] === '.')) {
match = true
}
// p有模式的
if (p.length > 1 && p[1] === '*') {
// 第一种情况：s*匹配0个字符
// 第二种情况：s*匹配1个字符，递归下去，用来表示s*匹配多个s
return isMatch(s, p.slice(2)) || (match && isMatch(s.slice(1), p))
} else {
return match && isMatch(s.slice(1), p.slice(1))
}
}
return isMatch(s, p)
}四、排序类
时间复杂度：https://www.jianshu.com/p/f4cca5ce055a
1.冒泡排序
javascript
const bubbleSort = (arr) => {
// 冒泡排序
for (let i = arr.length - 1, tmp; i > 0; i--) {
for (let j = 0; j < i; j++) {
tmp = arr[j]
if (tmp > arr[j + 1]) {
arr[j] = arr[j + 1]
arr[j + 1] = tmp
}
}
}
return arr
}2.快速排序
javascript
const selectSort = (arr) => {
// 选择排序
for (let i = 0, len = arr.length, min; i < len; i++) {
min = arr[i]
for (let j = i + 1; j < len; j++) {
if (arr[j] < min) {
let c = min
min = arr[j]
arr[j] = c
}
}
arr[i] = min
}
return arr
}3.按奇偶排序
按奇偶排序数组 II 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。 你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7] 输出：[4,5,2,7] 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
提示： 2 <= A.length <= 20000 A.length % 2 == 0 0 <= A[i] <= 1000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-array-by-parity-ii
分析： 为数组的偶数下标部分和奇数下标部分分别维护指针 i, ji,j。随后，在每一步中，如果 A[i]A[i] 为奇数，则不断地向前移动 jj（每次移动两个单位），直到遇见下一个偶数。此时，可以直接将 A[i]A[i] 与 A[j]A[j] 交换。我们不断进行这样的过程，最终能够将所有的整数放在正确的位置上。。
解：
javascript
const oddEvenSort = (arr) => {
// 进行升序排序
arr.sort((a, b) => a - b)
// 声明一个空数组用来存储奇偶排序后的数组
let r = []
// 记录奇数、偶数位下标
let odd = 1
let even = 0
// 对数组进行遍历
arr.forEach(item => {
if (item % 2 === 1) {
r[odd] = item
odd += 2
} else {
r[even] = item
even += 2
}
})s
return r
}4.第k个最大值
数组中的第K个最大元素 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
说明: 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
分析： 排序后找的第K大的值
解1：
javascript
const kRank = (arr, k) => {
return arr.sort((a, b) => b - a)[k - 1]
}解2： 更有效率，不需要排序那么多，降序冒泡前K个即可。
javascript
export default (arr, k) => {
let len = arr.length - 1
// 冒泡排序
for (let i = len, tmp; i > len - k; i--) {
for (let j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
tmp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = tmp
}
}
}
return arr[len - (k - 1)]5.最大区间
最大间距 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。 如果数组元素个数小于 2，则返回 0。
示例 1: 输入: [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2: 输入: [10] 输出: 0 解释: 数组元素个数小于 2，因此返回 0。
说明: 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-gap
分析：
解1：
javascript
function maxRange (arr) => {
// 如果数组长度小于2返回0
if (arr.length < 2) {
return 0
}
// 排序
arr.sort()
// 用它来保存相邻元素的最大差值
let max = 0
for (let i = 0, len = arr.length - 1, tmp; i < len; i++) {
tmp = arr[i + 1] - arr[i]
if (tmp > max) {
max = tmp
}
}
return max
}解2： 将区间计算放在冒泡排序之中，减少一次遍历
javascript
function maxRange2 (arr) => {
if (arr.length < 2) {
return 0
}
let max = 0
let len = arr.length - 1
let space
for (let i = len, tmp; i > 0; i--) {
for (let j = 0; j < i; j++) {
tmp = arr[j]
if (tmp > arr[j + 1]) {
arr[j] = arr[j + 1]
arr[j + 1] = tmp
}
}
if (i < len) {
// 由于i>0，所以，这里最小只计算到了arr[2]-arr[1]
space = arr[i + 1] - arr[i]
if (space > max) {
max = space
}
}
}
return Math.max(max, arr[1] - arr[0])
}6.缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
示例 1： 输入：nums = [1,2,0] 输出：3
示例 2： 输入：nums = [3,4,-1,1] 输出：2
示例 3： 输入：nums = [7,8,9,11,12] 输出：1
提示： 0 <= nums.length <= 300 -231 <= nums[i] <= 231 - 1
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/first-missing-positive
解1：
javascript
function lackOfMinPositiveNumber (arr) {
// 过滤掉非正整数
arr = arr.filter(item => item > 0)
// 正整数数组是不是为空
if (arr.length) {
// 升序，目的：方便从左到右取最小值arr[0]
arr.sort((a, b) => a - b)
// 如果第一个元素不为1，返回1
if (arr[0] !== 1) {
return 1
} else {
// 从左边开始遍历，只要下一个元素和当前元素差值>1说明当前元素的下一个值（+1）
for (let i = 0, len = arr.length - 1; i < len; i++) {
if (arr[i + 1] - arr[i] > 1) {
return arr[i] + 1
}
}
// 如果数组是连续的正整数【1,2,3,4,5,6】
return arr.pop() + 1
}
} else {
return 1
}
}解2： 没必要排序很多，每次找到最小值，进行判断即可。
javascript
function lackOfMinPositiveNumber2 (arr) {
arr = arr.filter(item => item > 0)
// 实现选择排序，先拿到最小值，如果第一个元素不是1直接返回1，如果是1，就要比相邻元素差值
for (let i = 0, len = arr.length, min; i < len; i++) {
min = arr[i]
for (let j = i + 1; j < len; j++) {
if (arr[j] < min) {
let c = min
min = arr[j]
arr[j] = c
}
}
arr[i] = min
if (i > 0) {
if (arr[i] - arr[i - 1] > 1) {
return arr[i - 1] + 1
}
} else {
if (min !== 1) {
return 1
}
}
}
return arr.length ? arr.pop() + 1 : 1
}7.快速排序
解1
javascript
const quickSort = (arr) => {
let len = arr.length
if (len < 2) {
return arr
} else {
// 选标尺元素
let flag = arr[0]
let left = []
let right = []
// 把剩余的元素遍历下，比标尺元素小的放左边，大的放右边
for (let i = 1, tmp; i < len; i++) {
tmp = arr[i]
if (tmp < flag) {
left.push(tmp)
} else {
right.push(tmp)
}
}
// 进行递归操作
return quickSort(left).concat(flag, quickSort(right))
}
}解2： 上面的算法，会因数组长度，空间复杂度相应增加，我们希望使用in-place原地算法，不增加额外内存。
只用一个数组，利用数组内元素交换，实现快速排序，不开辟额外内存存储中间变量。
红色：作为标尺元素的下标 紫色：从标尺元素的后一位开始，每找到一位比标尺元素小的元素，下标加一，记录该下标 蓝色：每次遍历开始的位置下标
交换3、9，交换后，紫色（代表比标尺元素小的元素游标位置）游标加一
交换1、7，交换后，紫色游标再加一
到达末尾，让紫色游标前一位和标尺元素下标进行交换
交换后：小于标尺元素的在标尺元素左边；大于等于标尺元素的在标尺元素的右边，本轮划分交换结束。 此后，紫色下标左右两边分别按此方式递归操作。
javascript
const quickSort = (arr) => {
// 数组指定两个位置进行值交换
let swap = (arr, i, j) => {
let tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
// 按照上述演示，完成一次划分交换
let findCenter = (arr, left, right) => {
let flag = arr[left]
let idx = left + 1
for (let i = idx; i <= right; i++) {
if (arr[i] < flag) {
swap(arr, idx, i)
idx++
}
}
swap(arr, left, idx - 1)
return idx
}
// 递归排序
let sort = (arr, left, right) => {
if (left < right) {
let center = findCenter(arr, left, right)
sort(arr, left, center - 1)
sort(arr, center, right)
}
}
// 调用快速排序
sort(arr, 0, arr.length - 1)
return arr
}五、递归类
1.复原IP地址
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
示例 1： 输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2： 输入：s = "0000" 输出：["0.0.0.0"]
示例 3： 输入：s = "1111" 输出：["1.1.1.1"]
示例 4： 输入：s = "010010" 输出：["0.10.0.10","0.100.1.0"]
示例 5： 输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示： 0 <= s.length <= 3000 s 仅由数字组成
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/restore-ip-addresses
分析： 由于我们需要找出所有可能复原出的 IP 地址，因此可以考虑使用回溯的方法，对所有可能的字符串分隔方式进行搜索，并筛选出满足要求的作为答案。
设题目中给出的字符串为 ss。我们用递归函数 \textit{dfs}(\textit{segId}, \textit{segStart})dfs(segId,segStart) 表示我们正在从 s[\textit{segStart}]s[segStart] 的位置开始，搜索 IP 地址中的第 \textit{segId}segId 段，其中 \textit{segId} \in {0, 1, 2, 3}segId∈{0,1,2,3}。由于 IP 地址的每一段必须是 [0, 255][0,255] 中的整数，因此我们从 \textit{segStart}segStart 开始，从小到大依次枚举当前这一段 IP 地址的结束位置 \textit{segEnd}segEnd。如果满足要求，就递归地进行下一段搜索，调用递归函数 \textit{dfs}(\textit{segId} + 1, \textit{segEnd} + 1)dfs(segId+1,segEnd+1)。
特别地，由于 IP 地址的每一段不能有前导零，因此如果 s[\textit{segStart}]s[segStart] 等于字符 00，那么 IP 地址的第 \textit{segId}segId 段只能为 00，需要作为特殊情况进行考虑。
在搜索的过程中，如果我们已经得到了全部的 44 段 IP 地址（即 \textit{segId} = 4segId=4），并且遍历完了整个字符串（即 \textit{segStart} = |s|segStart=∣s∣，其中 |s|∣s∣ 表示字符串 ss 的长度），那么就复原出了一种满足题目要求的 IP 地址，我们将其加入答案。在其它的时刻，如果提前遍历完了整个字符串，那么我们需要结束搜索，回溯到上一步。
解：
javascript
const recoverIp = (str) => {
// 保存所有符合条件的IP地址
let r = []
// 分四步递归处理ip分段
let search = (cur, sub) => {
// 非法输入过滤，LeetCode测试用例(111111111111111111111111111111111111111111111111111111111111)
if (sub.length > 12) {
return
}
// 边界条件
if (cur.length === 4 && cur.join('') === str) {
r.push(cur.join('.'))
} else {
// 正常的处理过程
for (let i = 0, len = Math.min(3, sub.length), tmp; i < len; i++) {
tmp = sub.substring(0, i + 1)
if (tmp - 256 < 0) {
// 转换下数据类型，如 01为1（LeetCode测试用例）
search(cur.concat([tmp * 1]), sub.substr(i + 1))
}
}
}
}
search([], str)
return r
}2.关联字符串
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1： 输入： s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9]
解释： 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。
示例 2： 输入： s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
分析：
解1：
javascript
const relatedString = (str, words) => {
// 保存结果
let result = []
// 记录数组的长度，做边界条件计算
let num = words.length
// 递归函数体
let range = (r, _arr) => {
if (r.length === num) {
result.push(r)
} else {
_arr.forEach((item, idx) => {
// 复制一份_arr
let tmp = [].concat(_arr)
// 去除掉第一个单词后的数组，类似ABC，去掉A
tmp.splice(idx, 1)
// 剩下的继续递归
range(r.concat(item), tmp)
})
}
}
range([], words)
// [0, 9, -1] filter 之后[0,9]
return result.map(item => {
return str.indexOf(item.join(''))
}).filter(item => item !== -1).sort()
}解2： 上述解法存在当数据量大的时候组合数太多导致效率变低的缺点。 现在我们利用利用查找每个单词在字符串的位置，然后通过计算这些位置是不是连续的。 比如 abforbarcd,[for,bar]，那么for的起始位置是2,bar的起始位置是5;说明这两个单词是连续的2+3(for的长度)=5 for:[{start:2,end:5}] bar:[{start:5,end:8}] 判断上一个单词的end和下一个单词的start是不是相同来计算两个单词是不是挨着
javascript
const relatedString2 = (str, words) => {
// 计算字符串的总长度
let strLen = str.length
// 计算所有的单词数量
let wordsLen = words.length
// 计算所有单词出现的起始位置和截止位置
let pos = {}
// 如果字符串的长度小于所有单词的总长度直接返回
if (strLen < words.join('').length) {
return []
}
// 遍历所有单词查找在字符串中的起始位置和截止位置
words.every(word => {
if (pos[word]) {
return true
}
let wl = word.length
let tmp = []
for (let i = 0, len = strLen - wl, idx; i <= len; i++) {
idx = str.slice(i).indexOf(word)
if (idx > -1) {
if (idx === 0) {
tmp.push({
start: i,
end: i + wl
})
} else if (str[i + 1] !== word[0]) {
i += idx - 1
}
} else {
break
}
}
// 如果没有匹配到单词终止遍历
if (tmp[0] === undefined) {
return false
} else {
// 保存当前单词的位置，遍历下一个单词
pos[word] = tmp.sort((a, b) => a.start - b.start)
return true
}
})
// 只要有一个单词没找到说明不能匹配到连续的字符串
if (words.find(item => !pos[item])) {
return []
}
let result = []
// 计算所有单词的位置
let match = (poses) => {
// 记录是不是所有单词都被匹配到了，每一次都应该把所有单词都包括进来并且是相邻的
let record = []
let len = Object.keys(poses).length
// 如果没有单词的位置说明处理结束了
if (len < 1) {
return -1
}
while (1) {
// 每次循环应该把记录清空
record.length = 0
// 按照起始位置进行升序排序
let minV = Number.MAX_SAFE_INTEGER
let minK = ''
// 优先找到所有单词其实位置最小的单词开始匹配
for (let [k, v] of Object.entries(poses)) {
if (!v.length) {
return false
} else {
if (v[0].start < minV) {
minK = k
minV = v[0].start
}
}
}
if (!minK) {
return false
}
// 起始位置最小的单词
let first = poses[minK].shift()
if (!first) {
return false
}
// 记录下这个起始位置
let start = first.start
// 记录words列表中的单词
record.push(words.findIndex(item => item === minK))
// 每次循环要匹配到所有单词
for (let i = 1; i < wordsLen; i++) {
for (let j = 0, next; j < wordsLen; j++) {
if (record.includes(j)) {
continue
}
if (poses[words[j]][0] === undefined) {
return false
}
next = poses[words[j]].find(item => item.start === first.end)
if (next) {
record.push(j)
first = next
break
}
}
}
// 如果所有单词的顺序是挨着的，记录下当前的起始位置
if (record.length === wordsLen && !record.find(item => item === undefined)) {
result.push(start)
}
}
}
match(pos)
// 对 result 去重，如 result=[1,1,2,3] [...new Set(result)]===[1,2,3]
return [...new Set(result)]
}六、栈
概念 栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
1.棒球比赛
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
整数 x - 表示本回合新获得分数 x "+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。 "D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。 "C" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。 请你返回记录中所有得分的总和。
示例 1： 输入：ops = ["5","2","C","D","+"] 输出：30 解释： "5" - 记录加 5 ，记录现在是 [5] "2" - 记录加 2 ，记录现在是 [5, 2] "C" - 使前一次得分的记录无效并将其移除，记录现在是 [5]. "D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10]. "+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15]. 所有得分的总和 5 + 10 + 15 = 30
示例 2： 输入：ops = ["5","-2","4","C","D","9","+","+"] 输出：27 解释： "5" - 记录加 5 ，记录现在是 [5] "-2" - 记录加 -2 ，记录现在是 [5, -2] "4" - 记录加 4 ，记录现在是 [5, -2, 4] "C" - 使前一次得分的记录无效并将其移除，记录现在是 [5, -2] "D" - 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4] "9" - 记录加 9 ，记录现在是 [5, -2, -4, 9] "+" - 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5] "+" - 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14] 所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27
示例 3： 输入：ops = ["1"] 输出：1
提示： 1 <= ops.length <= 1000 ops[i] 为 "C"、"D"、"+"，或者一个表示整数的字符串。整数范围是 [-3 * 104, 3 * 104] 对于 "+" 操作，题目数据保证记录此操作时前面总是存在两个有效的分数 对于 "C" 和 "D" 操作，题目数据保证记录此操作时前面总是存在一个有效的分数
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/baseball-game
分析：
解：
javascript
const sumGrade = (arr) => {
// 用数组来实现堆栈结构，pop,push
let result = []
// 上一轮的数据
let pre1
// 上上轮的数据
let pre2
// 对数组进行遍历，遍历的目的是处理得分
arr.forEach(item => {
switch (item) {
case 'C':
if (result.length) {
result.pop()
}
break
case 'D':
pre1 = result.pop()
result.push(pre1, pre1 * 2)
break
case '+':
pre1 = result.pop()
pre2 = result.pop()
result.push(pre2, pre1, pre2 + pre1)
break
default:
result.push(item * 1)
}
})
return result.reduce((total, num) => { return total + num })
}2.最大矩阵
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 解释：最大矩形如上图所示。
示例 2： 输入：matrix = [] 输出：0
示例 3： 输入：matrix = [["0"]] 输出：0
示例 4： 输入：matrix = [["1"]] 输出：1
示例 5： 输入：matrix = [["0","0"]] 输出：0
提示： rows == matrix.length cols == matrix[0].length 0 <= row, cols <= 200 matrix[i][j] 为 '0' 或 '1'
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximal-rectangle
分析：
1.一个矩形可以从每行任意位置形成（以左上角作为形成位置），故每行都需要判断计算。 2.以第一行为例，对于每个矩形形成的位置可通过如下思路计算： 以上图为例，只关注每行连续1的首尾下标，重新构建二维数组，然后将其视为堆栈，逐行弹出，进行合并。上行和下行合并时： （1）重叠部分，起始取大值，结束下标取小值，形成新元素，push回堆栈中。例如，[[0,1]]和[[0,1],[3,4]]合成后，取[[0,1]]。放入堆栈继续同第三行计算 （注：上行数组可能和下行不止一个数组重叠，故需要迭代计算，每种情况都考虑到。） （2）如果此时行数已经超过了2行，就可计算出以某行为左上角，形成矩形的最大面积了：行数（即递归次数）* 宽度（首尾下标差），并做记录。 3.迭代，依次计算每一行为左上角为起始所形成的最大矩形的面积。并比较数组中各行最后所有的矩形面积的大小。
解：
javascript
const findMaxArea = (arr) => {
let result = []
let reg = /1{2,}/g
// 把二位数组重新表达，把相邻的1提取出来（起始点+截止点）
arr = arr.map(item => {
let str = item.join('')
let r = reg.exec(str)
let rs = []
while (r) {
rs.push([r.index, r.index + r[0].length - 1])
r = reg.exec(str)
}
return rs
})
// 通过递归计算相邻的矩阵
let maxRect = (arr, result, n = 1) => {
// 弹出第一行
let top = arr.pop()
// 弹出第二行
let next = arr.pop()
// 记录第一行的每一个起始点和截止点
let tt
// 记录第二行的每一个起始点和截止点
let nn
// 记录交叉的起始索引
let start
// 记录交叉的截止索引
let end
let width = 1
let maxWidth = 1
n++
for (let i = 0, il = top.length; i < il; i++) {
tt = top[i]
for (let j = 0, jl = next.length; j < jl; j++) {
nn = next[j]
width = Math.min(tt[1], nn[1]) - Math.max(tt[0], nn[0])
// 修改避免相邻两个数的差值为1（实际宽度为2）没有为start,end赋值导致的bug,应该加上=
if (width >= maxWidth) {
maxWidth = width
start = Math.max(tt[0], nn[0])
end = Math.min(tt[1], nn[1])
}
}
}
// 如果没有找到交叉点
if (start === undefined || end === undefined) {
if (n < 3) {
return false
} else {
width = top[0][1] - top[0][0] + 1
if (width > 1) {
result.push((n - 1) * width)
}
}
} else {
// 找到交叉点继续下一行
if (arr.length > 0) {
arr.push([
[start, end]
])
maxRect(arr, result, n++)
} else {
// 从某一行一直计算到最后一行，这个时候start和end一直有值，所以不会进入到if层，这个时候n就是累计的行数（高），end-start+1就是宽
result.push(n * (end - start + 1))
}
}
}
while (arr.length > 1) {
maxRect([].concat(arr), result)
arr.pop()
}
// 取最大值
let max = 0
let item = result.pop()
while (item) {
if (item > max) {
max = item
}
item = result.pop()
}
return max > 0 ? max : -1
}七、队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。 队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
1.设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。 Front: 从队首获取元素。如果队列为空，返回 -1 。 Rear: 获取队尾元素。如果队列为空，返回 -1 。 enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 isEmpty(): 检查循环队列是否为空。 isFull(): 检查循环队列是否已满。
示例： MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4
提示： 所有的值都在 0 至 1000 的范围内； 操作数将在 1 至 1000 的范围内； 请不要使用内置的队列库。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/design-circular-queue
解：
javascript
class MyCircularQueue {
constructor (k) {
// 用来保存数据长度为k的数据结构
this.list = Array(k)
// 队首指针
this.front = 0
// 队尾的指针
this.rear = 0
// 队列的长度
this.max = k
}
enQueue (num) {
if (this.isFull()) {
return false
} else {
this.list[this.rear] = num
this.rear = (this.rear + 1) % this.max
return true
}
}
deQueue () {
let v = this.list[this.front]
this.list[this.front] = ''
this.front = (this.front + 1) % this.max
return v
}
isEmpty () {
return this.front === this.rear && !this.list[this.front]
}
isFull () {
return this.front === this.rear && !!this.list[this.front]
}
Front () {
return this.list[this.front]
}
Rear () {
let rear = this.rear - 1
return this.list[rear < 0 ? this.max - 1 : rear]
}
}2.任务调度器
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
示例 1： 输入：tasks = ["A","A","A","B","B","B"], n = 2 输出：8 解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B 在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
示例 2： 输入：tasks = ["A","A","A","B","B","B"], n = 0 输出：6 解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0 ["A","A","A","B","B","B"] ["A","B","A","B","A","B"] ["B","B","B","A","A","A"] ... 诸如此类
示例 3： 输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2 输出：16 解释：一种可能的解决方案是： A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
提示： 1 <= task.length <= 104 tasks[i] 是大写英文字母 n 的取值范围为 [0, 100]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/task-scheduler
分析： 1.不同任务需要交叉执行。 2.同类任务数多的任务先执行，少的作为间隔分散其中，否则，任务数多的堆积到后面只能待命。 3.基于以上两点，需要对任务进行分类存储。 4.冷却时间n内执行一组任务。
解：
javascript
const taskManager = (tasks, n) => {
// 存储任务最终执行的顺序
let q = ''
// 任务分类，统计不同种类任务次数
let Q = {}
tasks.forEach(item => {
if (Q[item]) {
Q[item]++
} else {
Q[item] = 1
}
})
while (1) {
let keys = Object.keys(Q)
if (!keys[0]) {
break
}
// n+1 为一组任务循环
let tmp = []
for (let i = 0; i <= n; i++) {
// 存储最多的任务
let max = 0
// 对应执行任务
let key
// 记录当前任务种类的位置
let pos
// 从所有的任务重找到未处理数最大的优先安排
keys.forEach((item, idx) => {
if (Q[item] > max) {
max = Q[item]
key = item
pos = idx
}
})
// 如果存在key
if (key) {
// 将该类任务中的一个加入到一组任务中
tmp.push(key)
// 由于需要保证一组任务中不能出现重复类型任务，需要临时从一组任务中删去该类任务
keys.splice(pos, 1)
// 并将任务数量减一
Q[key]--
// 如果任务数量为0
if (Q[key] < 1) {
// 需要从总任务分类中，删去该类任务
delete Q[key]
}
// 一组不同种类的任务组循环完毕后跳出当次循环
} else {
break
}
}
// 记录每次循环执行的任务顺序
// 注意，一组任务长度未到达n+1，证明不同种类任务数不足，需要待命余下的时间，这里用'-'表示待命单位时间
q += tmp.join('').padEnd(n + 1, '-')
}
// 当然最后一组要是以连续-结尾，需要将其移除，因为实际任务已经都执行完了
// A--A--A--
q = q.replace(/-+$/g, '')
return q.length
}八、链表
创建链表数据结构 链表的排序 检测链表闭环
1.排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶： 你可以在 O(n log n) 时间复杂度和 O(n log n) 空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3： 输入：head = [] 输出：[]
提示： 链表中节点的数目在范围 [0, 5 * 104] 内 -105 <= Node.val <= 105
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-list
分析：
根据题目条件，选择快速排序。
单链表的快速排序
解：
javascript
// 声明链表的节点
class Node {
constructor (value) {
this.val = value
this.next = undefined
}
}
// 声明链表的数据结构（手动创建链表）
class NodeList {
constructor (arr) {
// 声明链表的头部节点
let head = new Node(arr.shift())
let next = head
arr.forEach(item => {
next.next = new Node(item)
next = next.next
})
return head
}
}
// 交换两个节点的值（等同于节点交换）
let swap = (p, q) => {
let val = p.val
p.val = q.val
q.val = val
}
// 通过起始节点和终止节点确定基准元素
let partion = (begin, end) => {
let val = begin.val
let p = begin
let q = begin.next
// end为undefined，因为[].shift()为undefined
while (q !== end) {
if (q.val < val) {
p = p.next
swap(p, q)
}
q = q.next
}
// 让基准元素跑到中间去
swap(p, begin)
return p
}
export default function sort (begin, end) {
if (begin !== end) {
let part = partion(begin, end)
sort(begin, part)
sort(part.next, end)
}
}
export {
Node,
NodeList
}检验：
javascript
let head = new NodeList([4, 1, 3, 2, 7, 9, 10, 12, 6])
sort(head)
// 将排序后的链表存在数组中
let res = []
let next = head
while (next) {
res.push(next.val)
next = next.next
}
// 展示数组结构
console.log(res) // [1, 2, 3, 4, 6, 7, 9, 10, 12]2.环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶： 你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示： 链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个 有效索引 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle
分析： 可通过快慢指针来判断链表是否成环，当有环时，快慢指针会出现相遇或快指针落后于慢指针的情况。
解：
javascript
// 声明链表的节点
class Node {
constructor (value) {
this.val = value
this.next = undefined
}
}
// 声明链表的数据结构
class NodeList {
constructor (arr) {
// 声明链表的头部节点
let head = new Node(arr.shift())
let next = head
arr.forEach(item => {
next.next = new Node(item)
next = next.next
})
return head
}
}
export default function isCircle (head) {
// 慢指针
let slow = head
// 快指针
let fast = head.next
while (1) {
if (!fast || !fast.next) {
return false
} else if (fast === slow || fast.next === slow) {
return true
} else {
slow = slow.next
fast = fast.next.next
}
}
}
export {
Node,
NodeList
}检验：
javascript
let head = new NodeList([6, 1, 2, 5, 7, 9])
head.next.next.next.next.next.next = head.next
isCircle(head) // true九、矩阵
1.螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/spiral-matrix
分析： 1.取出第一行 2.取出第二行到第n-1行最后一位 3.取出最后一行元素的反转 4.弹出首尾两行 5.取出新的第n行到第1行的首元素 6.判断arr长度，即行数不为空时，递归上述操作。
解：
javascript
const spiralMatrix = (arr) => {
// 处理每一圈的数据遍历过程
let map = (arr, r = []) => {
for (let i = 0, len = arr.length; i < len; i++) {
if (i === 0) {
// 复制第一行
r = r.concat(arr[i])
} else if (i === len - 1) {
// 复制最后一行的反转
r = r.concat(arr[i].reverse())
} else {
// 增加边界检查（Leetcode测试用例）
if (arr[i].length) {
r.push(arr[i].pop())
}
}
}
// 弹出第一行
arr.shift()
// 弹出最后一行
arr.pop()
for (let i = arr.length - 1; i >= 0; i--) {
// 增加边界检查（Leetcode测试用例）
if (arr[i].length) {
r.push(arr[i].shift())
}
}
if (arr.length) {
return map(arr, r)
} else {
return r
}
}
return map(arr, [])
}2.旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
示例 3： 输入：matrix = [[1]] 输出：[[1]]
示例 4： 输入：matrix = [[1,2],[3,4]] 输出：[[3,1],[4,2]]
提示： matrix.length == n matrix[i].length == n 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/rotate-image
分析： 由例一可得： 原矩阵，可经过两次变换形成最终的矩阵，分别是关于两条直线进行对称交换元素。
解：
javascript
const transformMatrix = (arr) => {
// 获取n的维度
let vecor = arr.length
// 垂直翻转
// 遍历一半的行
for (let i = 0, len = vecor / 2; i < len; i++) {
// 遍历所有列
for (let j = 0, tmp; j < vecor; j++) {
tmp = arr[i][j]
arr[i][j] = arr[vecor - i - 1][j]
arr[vecor - i - 1][j] = tmp
}
}
// 对角线翻转
// 遍历每一行
for (let i = 0; i < vecor; i++) {
// 遍历每行到对角线处的列
for (let j = 0, tmp; j < i; j++) {
tmp = arr[i][j]
arr[i][j] = arr[j][i]
arr[j][i] = tmp
}
}
return arr
}十、二叉树
1.对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2 / \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2 \
3 3
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/symmetric-tree
分析： 构造处的二叉树和数组索引之间的关系： 二叉树的构造：
二叉树的镜像对称判断： 一个节点的左节点和右节点比较，左左子节点和右右子节点比较；左右子节点和右左子节点比较。
解:
javascript
// 二叉树的节点
class Node {
constructor (val) {
this.val = val
this.left = this.right = undefined
}
}
class Tree {
constructor (data) {
// 临时存储所有节点，方便寻找父子节点
let nodeList = []
// 顶节点
let root
for (let i = 0, len = data.length; i < len; i++) {
let node = new Node(data[i])
nodeList.push(node)
if (i > 0) {
// 计算当前节点属于那一层
let n = Math.floor(Math.sqrt(i + 1))
// 记录当前层的起始点
let q = Math.pow(2, n) - 1
// 记录上一层的起始点
let p = Math.pow(2, n - 1) - 1
// 找到当前节点的父节点
let parent = nodeList[p + Math.floor((i - q) / 2)]
// 将当前节点和上一层的父节点做关联
if (parent.left) {
parent.right = node
} else {
parent.left = node
}
}
}
root = nodeList.shift()
// 清空数组
nodeList.length = 0
// 返回根节点
return root
}
// 判断是否对称
static isSymmetry (root) {
// 空树
if (!root) {
return true
}
// 递归判断，
let walk = (left, right) => {
// 边界为二叉树无左右子节点
if (!left && !right) {
return true
}
// 如果仅一边有或值不对称
if ((left && !right) || (!left && right) || (left.val !== right.val)) {
return false
}
// 两个子节点都有且对称，递归处理，子节点进行比较，左左和右右比，左右和右左比。
return walk(left.left, right.right) && walk(left.right, right.left)
}
return walk(root.left, root.right)
}
}
export default Tree
export {
Node
}2.验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
示例 1: 输入: 2 /
1 3 输出: true
示例 2: 输入: 5 /
1 4 /
3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
分析： 构造举例：
解：
javascript
// 定义节点
class Node {
constructor (val) {
this.val = val
this.left = this.right = undefined
}
}
// 定义二叉搜索树
class Tree {
constructor (data) {
// 声明根节点
let root = new Node(data.shift())
// 遍历所有的数据，递归插入到当前这棵搜索树中去
data.forEach(item => {
this.insert(root, item)
})
return root
}
// 插入(当前节点、需插入的新数据)
insert (node, data) {
// 比较当前数值和当前节点数值得大小
if (node.val > data) {
// 判断当前节点是否有左节点
if (node.left === undefined) {
// 没有左节点，插入该处
node.left = new Node(data)
} else {
// 有左节点，递归判断
this.insert(node.left, data)
}
} else {
if (node.right === undefined) {
node.right = new Node(data)
} else {
this.insert(node.right, data)
}
}
}
// 判断该二叉树是否是二叉搜索树
static walk (root) {
// 遍历到无子节点
if (!root.left && !root.right) {
return true
// 仍存在子节点，并且左子节点大于该节点或右子节点小于子节点
} else if ((root.left && root.val < root.left.val) || (root.right && root.val > root.right.val)) {
return false
// 正常情况，左<中<右，继续递归判断子节点
} else {
return Tree.walk(root.left) && Tree.walk(root.right)
}
}
}
export default Tree
export {
Node
}十一、堆
1.根据字符出现频率排序（堆排序）
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1: 输入: "tree" 输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2: 输入: "cccaaa" 输出: "cccaaa"
解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3: 输入: "Aabb"
输出: "bbAa"
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。 注意'A'和'a'被认为是两种不同的字符。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-characters-by-frequency
解：
javascript
class Heap {
constructor (str) {
// 统计各个字符出现的个数
let map = new Map()
str.split('').forEach(item => {
if (map.has(item)) {
map.set(item, map.get(item) + 1)
} else {
map.set(item, 1)
}
})
this.map = map
// 记录各字符出现的次数
this.data = Array.from(map.values())
}
sort () {
let iArr = this.data
let n = iArr.length
if (n <= 1) {
return iArr
} else {
for (let i = Math.floor(n / 2); i >= 0; i--) {
Heap.maxHeapify(iArr, i, n)
}
for (let j = 0; j < n; j++) {
Heap.swap(iArr, 0, n - 1 - j)
Heap.maxHeapify(iArr, 0, n - 1 - j - 1)
}
return iArr
}
}
// 最终按频率输出字符串
toString () {
// 出现频率排序的数组
let arr = this.sort()
let str = []
while (arr.length) {
// 最大频次
let top = arr.pop()
// 遍历存储字符及频次的map
for (let [k, v] of this.map) {
if (v === top) {
// 还原对应出现频次字符
str.push(k.repeat(v))
// 删除计算过的字符
this.map.delete(k)
break
}
}
}
// 转换为字符串
return str.join('')
}
// 交换两个元素
static swap (arr, a, b) {
if (a === b) {
return
}
let c = arr[a]
arr[a] = arr[b]
arr[b] = c
}
// 构建最大堆的过程
static maxHeapify (Arr, i, size) {
// 左节点（索引）
let l = i * 2 + 1
// 右节点
let r = i * 2 + 2
let largest = i
// 父节点i和左节点l做比较取最大
if (l <= size && Arr[l] > Arr[largest]) {
largest = l
}
// 右节点和最大值比较
if (r <= size && Arr[r] > Arr[largest]) {
largest = r
}
if (largest !== i) {
Heap.swap(Arr, i, largest)
Heap.maxHeapify(Arr, largest, size)
}
}
}
export default Heap2.超级丑数（堆查找）
编写一段程序来查找第 n 个超级丑数。
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
示例: 输入: n = 12, primes = [2,7,13,19] 输出: 32 解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
说明: 1 是任何给定 primes 的超级丑数。 给定 primes 中的数字以升序排列。 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。 第 n 个超级丑数确保在 32 位有符整数范围内。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/super-ugly-number
质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 因数是指整数a除以整数b(b≠0) 的商正好是整数而没有余数，我们就说b是a的因数。 质因数就是一个数的约数，并且是质数。 丑数就是只包含质因子2，3和5的数。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
分析：
1.找当前数的质因数 2.查是否都在质数列表primes中 3.是否达到指定数n
堆查找，由于不是线性查找，性能很高。对判断是否到达指定数n时，能快速得出结论。
解：
javascript
class Ugly {
constructor (n, primes) {
// 指定查找到第几个超级丑数
this.n = n
// 传入的质因数列表构造为堆保存
this.primes = new Heap(primes)
}
// 计算超级丑数
getAll () {
// 超级丑数列表
let res = [1]
let i = 2
let primes = this.primes
while (res.length < this.n) {
let arr = Ugly.getPrimes(i)
let k = 0
let l = arr.length
for (;k < l; k++) {
if (!primes.find(arr[k])) {
break
}
}
// k===l有两种情况，一种就是当前这个数压根没有质因数；一种是所有质因数都在指定列表中
if (k === l) {
// 没有质因数时
if (l === 0) {
// 判断质因数列表中是否存在当前数
if (primes.find(i)) {
res.push(i)
}
} else {
res.push(i)
}
}
i++
}
return res[this.n - 1]
}
// 计算指定正整数n的质因数
static getPrimes (n) {
let prime = (n) => {
// 存储所有的质因数
let arr = []
// 此处用n/2便于理解，因为n除以一个大于n/2的显然小于2，不再可能被大于2的因数整除
// 事实上，这里计算到sqrt(n)+1 即可。因为，假设n存在大于等于sqrt(n)的因数y,则x=n/y必同时为n的因数，其值小于等于sqrt(n)。
// 故，实际上我们测到sqrt(n)+1即可。（防止精度损失导致少枚举一个数故+1）
for (let i = 2; i < n / 2 + 1; i++) {
if (n % i === 0 && !prime(i).length) {
arr.push(i)
}
}
return arr
}
return prime(n)
}
}
class Heap {
constructor (arr) {
this.data = arr
this.max = arr.length
this.sort()
}
sort () {
let iArr = this.data
let n = iArr.length
if (n <= 1) {
return iArr
} else {
for (let i = Math.floor(n / 2); i >= 0; i--) {
Heap.maxHeapify(iArr, i, n)
// 构建一次最大堆即可
}
return iArr
}
}
// 堆查找元素（查找值，查找节点索引）
find (val, i = 0) {
let arr = this.data
// 如果当前值大于大根堆根元素，（初始时i=0为根节点），或查找索引大于堆下标，证明堆中不存在
if (val > arr[i] || i > this.max) {
return false
// 查找值等于当前节点值
} else if (val === arr[i]) {
return val
// 查找值小于当前节点值
} else {
// 去该节点的左子节点和右子节点中递归查找
return this.find(val, i * 2 + 1) || this.find(val, i * 2 + 2)
}
}
// 交换两个元素
static swap (arr, a, b) {
if (a === b) {
return
}
let c = arr[a]
arr[a] = arr[b]
arr[b] = c
}
// 构建最大堆的过程
static maxHeapify (Arr, i, size) {
// 左节点（索引）
let l = i * 2 + 1
// 右节点
let r = i * 2 + 2
let largest = i
// 父节点i和左节点l做比较取最大
if (l <= size && Arr[l] > Arr[largest]) {
largest = l
}
// 右节点和最大值比较
if (r <= size && Arr[r] > Arr[largest]) {
largest = r
}
if (largest !== i) {
Heap.swap(Arr, i, largest)
Heap.maxHeapify(Arr, largest, size)
}
}
}
export default Ugly
export {
Heap
}十二、贪婪
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
例如，平时购物找零钱时，为使找回的零钱的硬币数最少，不要求找零钱的所有方案，而是从最大面值的币种开始，按递减的顺序考虑各面额，先尽量用大面值的面额，当不足大面值时才去考虑下一个较小面值，这就是贪心算法。
1.买卖股票的最佳时机
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1: 输入: prices = [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2: 输入: prices = [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3: 输入: prices = [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示： 1 <= prices.length <= 3 * 104 0 <= prices[i] <= 104
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
分析：
解：
javascript
const getMaxProfit = (prices) => {
// 用来保存利润
let count = 0
for (let i = 0, len = prices.length; i < len; i++) {
for (let j = i; j < len - 1; j++) {
// 后一天价格大于当天价格
if (prices[j + 1] > prices[j]) {
// 累积利润，暂不卖出
count += prices[j + 1] - prices[j]
i = j
// 后一天价格小于等于当天价格，证明当前已在价格高点
} else {
i = j
// 将股票卖出，重新计算跳出当前买卖周期，买入股票，开始外层下一买卖周期
break
}
}
}
return count
}2.柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。 注意，一开始你手头没有任何零钱。 如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1： 输入：[5,5,5,10,20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2： 输入：[5,5,10] 输出：true
示例 3： 输入：[10,10] 输出：false
示例 4： 输入：[5,5,10,10,20] 输出：false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示： 0 <= bills.length <= 10000 bills[i] 不是 5 就是 10 或是 20
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lemonade-change
解：
javascript
const giveBackChange = (input) => {
// 表示自己的钱箱（用于存储零钱）
let hand = []
// 判断是否有顾客还在
while (input.length) {
// 取出当前排在最前面顾客的钱
let money = input.shift()
// 这种情况不需要找零
if (money === 5) {
hand.push(money)
} else {
// 手里的零钱要降序排列也就说最大的面值的钱放在最前面
hand.sort((a, b) => b - a)
// 顾客的钱减去饮料的钱就是需要找给顾客的零钱
let change = money - 5
for (let i = 0, len = hand.length; i < len; i++) {
if (hand[i] <= change) {
change -= hand[i]
hand.splice(i, 1)
// 删除了元素，数组的长度发生了变化，要维持刚才的i不变
i--
}
if (change === 0) {
break
}
}
// 没有足够的零钱找给顾客
if (change !== 0) {
return false
} else {
// 顾客的钱存起来
hand.push(money)
}
}
}
return true
}十三、动态规划
1.不同路径ii
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释： 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
提示： m == obstacleGrid.length n == obstacleGrid[i].length 1 <= m, n <= 100 obstacleGrid[i][j] 为 0 或 1
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-paths-ii
分析：
- 先算出不考虑障碍物时，从左上到右下，一共有多少中走法。（这是典型的动态规划问题）
- 再排除路径中有障碍物的走法。
到达终点前一步的两种状态：
状态转移方程为： f(m*n) = f((m-1)n) + f(m(n-1))
边界情况是，到达此三格处。
解：
javascript
const getPath = (arr, m, n) => {
let dp = (m, n) => {
// 检查起始或者目标元素是不是1（被占用了），如果起始或者最后那个格就是1，说明怎么都怎么不到那，直接返回0
if (arr[m - 1][n - 1] === 1 || arr[0][0] === 1) {
return 0
}
// 如果在右下角的边界处，即（1,1）位置。
if (m === 2 && n === 2) {
return (arr[1][1] === 1 || arr[1][0] + arr[0][1] === 2) ? 0 : (arr[1][0] === 1 || arr[0][1] === 1) ? 1 : 2
// 单行或单列情况
} else if (m < 2 || n < 2) {
// 单行情况
if (m < 2) {
// 单行情况中，第一行任何元素出现1，则路不通
return arr[m - 1].includes(1) ? 0 : 1
// 单列情况，遍历每行第一个元素，判断是否其中有1，即路被堵的情况
} else {
for (let i = 0; i < m; i++) {
if (arr[i][0] === 1) {
return 0
}
}
// 其它情况返回一，即一种解法，路上是通的
return 1
}
// 非边界时，采用递归判断
} else {
return dp(m - 1, n) + dp(m, n - 1)
}
}
return dp(m, n)
}2. k站中转内最便宜的航班
有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。
示例 1： 输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 输出: 200 解释: 城市航班图如下
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
示例 2： 输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 输出: 500 解释: 城市航班图如下
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。
提示： n 范围是 [1, 100]，城市标签从 0 到 n - 1 航班数量范围是 [0, n * (n - 1) / 2] 每个航班的格式 (src, dst, price) 每个航班的价格范围是 [1, 10000] k 范围是 [0, n - 1] 航班没有重复，且不存在自环
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
分析： 状态转移方程
解：
javascript
const theCheapestFlight = (fights, src, dst, k) => {
// 将fights作为参数和LeetCode一致
let cheap = (fights, src, dst, k) => {
let prev = fights.filter(item => item[1] === dst)
let min = Math.min.apply(null, prev.map(item => {
if (item[0] === src && k > -1) {
return item[2]
} else if (k === 0 && item[0] !== src) {
return Number.MAX_SAFE_INTEGER
} else {
return item[2] + cheap(fights, src, item[0], k - 1)
}
}))
return min
}
// 增加返回值是不是Number.MAX_SAFE_INTEGER，如果是返回-1
let min = cheap(fights, src, dst, k)
return min >= Number.MAX_SAFE_INTEGER ? -1 : min
}