手撕
节流-防抖
const throttle1 = (fn,wait = 500) => { //必须返回函数否则是函数的直接调用
return function(...args) { // 不能是箭头函数，让this指向该标签，否则this指向windiw
if(!this.timer){//检测是否开启了定时器
this.timer = setTimeout(() => {//没有开启则开启新的定时器，必须是箭头函数，否则this指向windiw
fn.apply(this,args) //fn必须是普通函数，否则没法改变this指向
this.timer = null//清除定时器
},wait)
}
}
}
const debounce = (func, wait = 50) => {
// 缓存一个定时器id
// 这里返回的函数是每次用户实际调用的防抖函数
// 如果已经设定过定时器了就清空上一次的定时器
// 开始一个新的定时器，延迟执行用户传入的方法
return function(...args) {
if (this.timer) clearTimeout(timer)
this.timer = setTimeout(() => {
func.apply(this, args)
}, wait)
}
}call-apply-bind
1.call
Function.prototype.myCall = function (context = window, ...args) {
// this-->func context--> obj args--> 传递过来的参数
// 在context上加一个唯一值不影响context上的属性
let key = Symbol("key")
context[key] = this // context为调用的上下文,this此处为函数，将这个函数作为context的方法
// let args = [...arguments].slice(1) //第一个参数为obj所以删除,伪数组转为数组
let result = context[key](...args)
delete context[key] // 不删除会导致context属性越来越多
return result
}2.apply
Function.prototype.myApply = function (context = window, args) {
// this-->func context--> obj args--> 传递过来的参数
// 在context上加一个唯一值不影响context上的属性
let key = Symbol("key")
context[key] = this // context为调用的上下文,this此处为函数，将这个函数作为context的方法
let result = context[key](...args) // 这里和call传参不一样
delete context[key] // 不删除会导致context属性越来越多
return result
}3.bind
Function.prototype.myBind = function (context = window, ...args) {
const temp = this
return function F(...args2) {
if (this instanceof F) {
return new temp(...args, args2)
}
temp.myCall(context, ...args, ...args2)
}
}Promise
实现
class MyPromise {
constructor(fn) {
this.resolvedCallbacks = []
this.rejectedCallbacks = []
this.state = "PENDING"
this.value = ""
fn(this.resolve.bind(this), this.reject.bind(this))
}
resolve(value) {
if (this.state === "PENDING") {
this.state = "RESOLVED"
this.value = value
this.resolvedCallbacks.map((cb) => cb(value))
}
}
reject(value) {
if (this.state === "PENDING") {
this.state = "REJECTED"
this.value = value
this.rejectedCallbacks.map((cb) => cb(value))
}
}
then(onFulfilled, onRejected) {
if (this.state === "PENDING") {
this.resolvedCallbacks.push(onFulfilled)
this.rejectedCallbacks.push(onRejected)
}
if (this.state === "RESOLVED") {
onFulfilled(this.value)
}
if (this.state === "REJECTED") {
onRejected(this.value)
}
}
}异步函数
const time = (timer) => {
return new Promise((resolve) => {
setTimeout(() => {
resolve()
}, timer)
})
}
const ajax1 = () =>
time(2000).then(() => {
console.log(1)
return 1
})
const ajax2 = () =>
time(3000).then(() => {
console.log(2)
return 2
})
const ajax3 = () => {
time(1000).then(() => {
console.log(3)
return 3
})
}Promise.all
Promise.all = function (promises) {
return new Promise((resolve, reject) => {
let result = []
let index = 0
let len = promises.length
if (len === 0) {
resolve(result)
return
}
for (let i = 0; i < len; i++) {
// 为什么不直接 promise[i].then, 因为promise[i]可能不是一个promise
Promise.resolve(promise[i])
.then((data) => {
result[i] = data
index++
if (index === len) resolve(result)
})
.catch((err) => {
reject(err)
})
}
})
}
Promise.all1([ajax1(), ajax2(), ajax3()]).then((res) => {
console.log(res)
})有顺序的执行 promose
function mergePromise(ajaxArr) {
const data = [] //存放返回结果
let promise = Promise.resolve()
ajaxArr.forEach((ajax) => {
promise = promise.then(ajax).then((res) => {
data.push(res)
return data
})
})
return promise
}
mergePromise([ajax1, ajax2, ajax3]).then((res) => {
console.log(res)
})限制并发
function limitLoad(url, handler, limit) {
let sequence = [...url]
//初始化promise容器
let promises = sequence.splice(0, limit).map((url, index) => {
return handler(url).then(() => {
return index
})
})
return sequence
.reduce((pCollect, url) => {
return pCollect
.then(() => {
return Promise.race(promises) //返回已经完成的下标
})
.then((fastestIndex) => {
promises[fastestIndex] = handler(url).then(() => {
return fastestIndex
})
})
.catch((err) => {
console.log(err)
})
}, Promise.resolve())
.then(() => {
return Promise.all(promises)
})
}模拟红绿的灯
async function fn() {
await ajax1()
await ajax2()
await ajax3()
await fn()
}
-----------------------------------------------------
function fn() {
Promise.resolve().then(ajax1).then(ajax2).then(ajax3).then(fn)
}
fn()eventBus
class EventBus {
constructor() {
this._events = new Map()
}
on(type, fn) {
const handler = this._events.get(type)
if (!handler) {
this._events.set(type, [fn])
} else {
handler.push(fn)
}
}
emit(type, ...args) {
let handler = this._events.get(type)
if (handler) {
for (let fn of handler) {
fn.apply(this, args)
}
}
}
off(type, fn) {
const handler = this._events.get(type)
const index = handler.findIndex((e) => e === fn)
if (index >= 0) {
handler.splice(index, 1)
}
if (handler.length === 0) {
this._events.delete(type)
}
}
once(type, fn) {
let _self = this
function handler() {
fn.apply(this, arguments)
_self.off(type, handler)
}
this.on(type, handler)
}
}
// 下面是 测试代码
function test1(...params) {
console.log(11, params)
}
function test2(...params) {
console.log(22, params)
}
function test3(...params) {
console.log(33, params)
}
function test4(...params) {
console.log(33, params)
}
//测试用例
let eb = new EventBus()
eb.on("event1", test1)
eb.on("event1", test2)
eb.on("event1", test3)
eb.emit("event1", "第一次")
eb.off("event1", test1)
eb.emit("event1", ["第二次1", "第二次2"])
eb.once("once", test4)
eb.emit("once", "执行一次", 1, 2, 3)
eb.emit("once", 134)算法
伪数组转换
什么是伪数组
本身并不能调用数组方法，它是一个另外一种对象类型，只不过属性从 0 开始排，依次为 0，1，2…最后还有 callee 和 length 属性。我们也把这样的对象称为类数组
var arr = [..arguments]
let args = Array.prototype.slice.call(arguments);//(start,end)
let args = Array.from(arguments);
let args = Array.prototype.concat.apply([], arguments);数组扁平化
- for 循环遍历判断是否数组 是的递归调用 concat 递归调用该数组 否则 push 新数组
var a = [1, [2, [3, 4, 5]]]
function flatten(arr) {
let result = []
for (let i = 0; i < arr.length; i++) {
if (Array.isArray(arr[i])) {
result = result.concat(flatten(arr[i]))
} else {
result.push(arr[i])
}
}
return result
}
flatten(a) // [1, 2, 3, 4，5]利用 reduce 方法 +concat
// 方法2 var arr = [1, [2, [3, 4]]] function flatten(arr) { return arr.reduce(function (prev, next) { return prev.concat(Array.isArray(next) ? flatten(next) : next) }, []) } console.log(flatten(arr)) // [1, 2, 3, 4，5]some+[…]
// 方法3 var arr = [1, [2, [3, 4]]] function flatten(arr) { while (arr.some((item) => Array.isArray(item))) { arr = [].concat(...arr) } return arr } console.log(flatten(arr)) // [1, 2, 3, 4，5]arr.toString().split(‘,’);
arr.flat([depth])
正则
// 方法 6 let arr = [1, ["2", [3, [4, 5]]], 6] function flatten(arr) { let str = JSON.stringify(arr) //[1,["2",[3,[4,5]]],6] str = str.replace(/(\[|\])/g, "") str = "[" + str + "]" return JSON.parse(str) } console.log(flatten(arr)) // [1, 2, 3, 4，5]
深拷贝
JSON.parse
const newObj = JSON.parse(JSON.stringify(oldObj))局限性：
会忽略 undefined
不能序列化函数
不能解决循环引用的对象
他无法实现对函数 、RegExp 等特殊对象的克隆
会抛弃对象的 constructor,所有的构造函数会指向 Object
对象有循环引用,会报错
（递归）
function deepClone(obj) {
// 如果是 值类型 或 null，则直接return
if (typeof obj !== "object" || obj === null) {
return obj
}
let copy = {}
if (obj.constructor === Array) {
copy = []
}
// 遍历对象的key
for (let key in obj) {
// 如果key是对象的自有属性
if (obj.hasOwnProperty(key)) {
// 递归调用深拷贝方法
copy[key] = deepClone(obj[key])
}
}
return copy
}数组去重
new Set（）
;[...new Set(arr)] Array.from(new Set(arr))
对象数组不能去重
indexOf
function unique(arr) { var array = [] for (var i = 0; i < arr.length; i++) { if (array.indexOf(arr[i]) === -1) { array.push(arr[i]) } } return array }对象数组 NaN 不能去重
new Map()
function unique(arr) {
let result = []
let map = new Map()
arr.forEach((item) => {
if (!map.has(item)) {
result.push(item)
map.set(item, true)
}
})
return result
}- hasOwnProperty
简单版本
只保留一个对象
typeof [1]+[1] object1
typeof {a:1}+{a:1} object[object Object]
function unique(arr){
let result = []
let obj = {}
arr.forEach(item => {
if(!obj.hasOwnProperty(typeof item+item)){
result.push(item)
obj[typeof item+item] = true
}
});
return result
}完整版本
function unique(arr) {
let result = []
let obj = {}
arr.forEach((item) => {
if (Object.prototype.toString.call(item) === "[object Object]") {
// console.log(item);
// console.log(JSON.stringify(item));
if (!obj.hasOwnProperty(JSON.stringify(item))) {
console.log(JSON.stringify(item))
result.push(item)
obj[JSON.stringify(item)] = true
}
}
if (
!obj.hasOwnProperty(typeof item + item) &&
Object.prototype.toString.call(item) !== "[object Object]"
) {
console.log("a", item)
result.push(item)
obj[typeof item + item] = true
}
})
return result
}排序
冒泡
每一轮操作，都会将这一轮中最大的元素放置到数组的末尾
function bubbleSort(arr) { // 缓存数组长度 const len = arr.length // 外层循环用于控制从头到尾的比较+交换到底有多少轮 for (let i = 0; i < len; i++) { // 区别在这里，我们加了一个标志位 let flag = false // 内层循环用于完成每一轮遍历过程中的重复比较+交换 for (let j = 0; j < len - 1 - i; j++) { // 若相邻元素前面的数比后面的大 if (arr[j] > arr[j + 1]) { // 交换两者 ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] flag = true } } // 若一次交换也没发生，则说明数组有序，直接放过 if (flag == false) return arr } // 返回数组 return arr }选择排序
每次都找出当前范围内的最小值，把它放在当前范围的头部
function selectSort(arr) { // 缓存数组长度 const len = arr.length // 定义 minIndex，缓存当前区间最小值的索引，注意是索引 let minIndex // i 是当前排序区间的起点 for (let i = 0; i < len - 1; i++) { // 初始化 minIndex 为当前区间第一个元素 minIndex = i // i、j分别定义当前区间的上下界，i是左边界，j是右边界 for (let j = i; j < len; j++) { // 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j if (arr[j] < arr[minIndex]) { minIndex = j } } // 如果 minIndex 对应元素不是目前的头部元素，则交换两者 if (minIndex !== i) { ;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] } } return arr }插入排序
找到元素在它前面那个序列中的正确位置
function insertSort(arr) {
// 缓存数组长度
const len = arr.length
// temp 用来保存当前需要插入的元素
let temp
// i用于标识每次被插入的元素的索引
for (let i = 1; i < len; i++) {
// j用于帮助 temp 寻找自己应该有的定位
let j = i
temp = arr[i]
// 判断 j 前面一个元素是否比 temp 大
while (j > 0 && arr[j - 1] > temp) {
// 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
arr[j] = arr[j - 1]
j--
}
// 循环让位，最后得到的 j 就是 temp 的正确索引
arr[j] = temp
}
return arr
}归并排序
归并排序是对分治思想的典型应用，它按照如下的思路对分治思想“三步走”的框架进行了填充：
- 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
- 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。 合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组
function mergeSort(arr) {
const len = arr.length
// 处理边界情况
if (len <= 1) {
return arr
}
// 计算分割点
const mid = Math.floor(len / 2)
// 递归分割左子数组，然后合并为有序数组
const leftArr = mergeSort(arr.slice(0, mid))
// 递归分割右子数组，然后合并为有序数组
const rightArr = mergeSort(arr.slice(mid, len))
// 合并左右两个有序数组
arr = mergeArr(leftArr, rightArr)
// 返回合并后的结果
return arr
}
function mergeArr(arr1, arr2) {
// 初始化两个指针，分别指向 arr1 和 arr2
let i = 0,
j = 0
// 初始化结果数组
const res = []
// 缓存arr1的长度
const len1 = arr1.length
// 缓存arr2的长度
const len2 = arr2.length
// 合并两个子数组
while (i < len1 && j < len2) {
if (arr1[i] < arr2[j]) {
res.push(arr1[i])
i++
} else {
res.push(arr2[j])
j++
}
}
// 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
if (i < len1) {
return res.concat(arr1.slice(i))
} else {
return res.concat(arr2.slice(j))
}
}快排
function partition(arr, left = 0, right = arr.length - 1) {
if (arr.length <= 1) {
return arr
}
if (left > right) {
return
}
let value = arr[left]
let i = left,
j = right
while (i !== j) {
while (arr[j] >= value && j > i) {
j--
}
while (arr[i] <= value && i < j) {
i++
}
if (i < j) {
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
;[arr[i], arr[left]] = [arr[left], arr[i]]
partition(arr, left, i - 1)
partition(arr, i + 1, right)
return arr
}堆排序
字符串
转化为驼峰命名
var s1 = "get-element-by-id"
// 转化为 getElementById
var f = function (s) {
return s.replace(/-\w/g, function (x) {
return x.slice(1).toUpperCase()
})
}判断是否是回文串
str ==== str.split('').reverse().join('')
----------------------
function isPalindrome(str) {
// 缓存字符串的长度
const len = str.length
// 遍历前半部分，判断和后半部分是否对称
for(let i=0;i<len/2;i++) {
if(str[i]!==str[len-i-1]) {
return false
}
}
return true
}
--------------------
// 工具方法，用于判断字符串是否回文
function isPalindrome(st, ed) {
while(st<ed) {
if(s[st] !== s[ed]) {
return false
}
st++
ed--
}
return true
}删除一个是否回文
const validPalindrome = function (s) {
// 缓存字符串的长度
const len = s.length
// i、j分别为左右指针
let i = 0,
j = len - 1
// 当左右指针均满足对称时，一起向中间前进
while (i < j && s[i] === s[j]) {
i++
j--
}
// 尝试判断跳过左指针元素后字符串是否回文
if (isPalindrome(i + 1, j)) {
return true
}
// 尝试判断跳过右指针元素后字符串是否回文
if (isPalindrome(i, j - 1)) {
return true
}
// 工具方法，用于判断字符串是否回文
function isPalindrome(st, ed) {
while (st < ed) {
if (s[st] !== s[ed]) {
return false
}
st++
ed--
}
return true
}
// 默认返回 false
return false
}无重复字符的最长子串
var lengthOfLongestSubstring = function (s) {
const set = new Set() //判断滑动窗口内是否有重复元素
let j = 0, //滑动窗口左边界
maxLength = 0
if (s.length === 0) {
//极端情况
return 0
}
for (let i = 0; i < s.length; i++) {
//滑动窗口右边界
if (!set.has(s[i])) {
//当前元素不在set中 就加入set 然后更新最大长度，i++继续下一轮循环
set.add(s[i])
maxLength = Math.max(maxLength, set.size)
} else {
//set中有重复元素不断让j++ 并删除窗口之外的元素 直到滑动窗口内没有重复的元素
while (set.has(s[i])) {
set.delete(s[j])
j++
}
set.add(s[i]) //放心将s[i]加入set中
}
}
return maxLength
}最长回文子串
var longestPalindrome = function (s) {
if (s.length < 2) {
return s
}
let l = 0
let r = 0
for (let i = 0; i < s.length; i++) {
// 回文子串长度是奇数
helper(i, i)
// 回文子串长度是偶数
helper(i, i + 1)
}
function helper(m, n) {
while (m >= 0 && n < s.length && s[m] == s[n]) {
m--
n++
}
// 注意此处m,n的值循环完后 是恰好不满足循环条件的时刻 如果此轮询得到回文串长度大于之前记录， 记录此轮循边界
if (n - m - 1 > r - l - 1) {
r = n
l = m
}
}
return s.slice(l + 1, r)
}最长上升子序列模型
// 入参是一个数字序列
const lengthOfLIS = function (nums) {
// 缓存序列的长度
const len = nums.length
// 处理边界条件
if (!len) {
return 0
}
// 初始化数组里面每一个索引位的状态值
const dp = new Array(len).fill(1)
// 初始化最大上升子序列的长度为1
let maxLen = 1
// 从第2个元素开始，遍历整个数组
for (let i = 1; i < len; i++) {
// 每遍历一个新元素，都要“回头看”，看看能不能延长原有的上升子序列
for (let j = 0; j < i; j++) {
// 若遇到了一个比当前元素小的值，则意味着遇到了一个可以延长的上升子序列，故更新当前元素索引位对应的状态
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
// 及时更新上升子序列长度的最大值
if (dp[i] > maxLen) {
maxLen = dp[i]
}
}
// 遍历完毕，最后到手的就是最大上升子序列的长度
return maxLen
}数组
创建
const arr = new Array(7).fill(1)注意：fill([])后面传递的是引用数据类型
两数求和问题
哈希表 map
const twoSum = function (nums, target) {
// 这里我用对象来模拟 map 的能力
const map = {}
// 缓存数组长度
const len = nums.length
// 遍历数组
for (let i = 0; i < len; i++) {
// 判断当前值对应的 target 差值是否存在（是否已遍历过）
if (map[target - nums[i]]) {
// 若有对应差值，那么答案get！
return [map[target - nums[i]], i]
}
// 若没有对应差值，则记录当前值
map[nums[i]] = i
}
}合并升序数组
const merge = function (nums1, m, nums2, n) {
// 初始化两个指针的指向，初始化 nums1 尾部索引k
let i = m - 1,
j = n - 1,
k = m + n - 1
// 当两个数组都没遍历完时，指针同步移动
while (i >= 0 && j >= 0) {
// 取较大的值，从末尾往前填补
if (nums1[i] >= nums2[j]) {
nums1[k] = nums1[i]
i--
k--
} else {
nums1[k] = nums2[j]
j--
k--
}
}
// nums2 留下的情况，特殊处理一下
while (j >= 0) {
nums1[k] = nums2[j]
k--
j--
}
}function mergeArr(arr1, arr2) {
// 初始化两个指针，分别指向 arr1 和 arr2
let i = 0,
j = 0
// 初始化结果数组
const res = []
// 缓存arr1的长度
const len1 = arr1.length
// 缓存arr2的长度
const len2 = arr2.length
// 合并两个子数组
while (i < len1 && j < len2) {
if (arr1[i] < arr2[j]) {
res.push(arr1[i])
i++
} else {
res.push(arr2[j])
j++
}
}
// 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
if (i < len1) {
return res.concat(arr1.slice(i))
} else {
return res.concat(arr2.slice(j))
}
}三数求和
/**
* @param {number[]} nums
* @return {number[][]}
*/
const threeSum = function (nums) {
// 用于存放结果数组
let res = []
// 给 nums 排序
nums = nums.sort((a, b) => {
return a - b
})
// 缓存数组长度
const len = nums.length
// 注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数
for (let i = 0; i < len - 2; i++) {
// 左指针 j
let j = i + 1
// 右指针k
let k = len - 1
// 如果遇到重复的数字，则跳过
if (i > 0 && nums[i] === nums[i - 1]) {
continue
}
while (j < k) {
// 三数之和小于0，左指针前进
if (nums[i] + nums[j] + nums[k] < 0) {
j++
// 处理左指针元素重复的情况
while (j < k && nums[j] === nums[j - 1]) {
j++
}
} else if (nums[i] + nums[j] + nums[k] > 0) {
// 三数之和大于0，右指针后退
k--
// 处理右指针元素重复的情况
while (j < k && nums[k] === nums[k + 1]) {
k--
}
} else {
// 得到目标数字组合，推入结果数组
res.push([nums[i], nums[j], nums[k]])
// 左右指针一起前进
j++
k--
// 若左指针元素重复，跳过
while (j < k && nums[j] === nums[j - 1]) {
j++
}
// 若右指针元素重复，跳过
while (j < k && nums[k] === nums[k + 1]) {
k--
}
}
}
}
// 返回结果数组
return res
}比较版本号
var compareVersion = function (version1, version2) {
const arr1 = version1.split(".")
const arr2 = version2.split(".")
while (arr1.length && arr2.length) {
const n1 = Number(arr1.shift())
const n2 = Number(arr2.shift())
if (n1 > n2) return 1
if (n1 < n2) return -1
}
if (arr1.length) {
// arr2 数组已经为空
return arr1.every((item) => Number(item) === 0) ? 0 : 1
}
//if (temp2.length === 0) {
// for (const value of temp1) {
// if (Number(value) !== 0) return 1
// }
//}
if (arr2.length) {
// arr1 数组已经为空
return arr2.every((item) => Number(item) === 0) ? 0 : -1
}
return 0
}千位分隔符
var thousandSeparator = function (n) {
let str = n.toString()
return str.replace(/\d{1,3}(?=(\d{3})+$)/g, (s) => `${s}.`)
}var thousandSeparator = function (n) {
let arr = n.toString().split("")
for (let i = arr.length - 3; i >= 0; i -= 3) {
arr.splice(i, 0, ".")
}
return arr.join("").replace(/^\./, "")
}拆解 URL 参数中 queryString
function querySearch(url) {
const query = url.split("?").pop().split("#").shift().split("&")
const res = {}
query.forEach((item) => {
const [key, val] = item.split("=")
res[key] = val
})
return res
}
const url = "www.alipay.com/index.html?user=anyone&tip=haha#first"
console.log(querySearch(url))返回最接近输入值的数字
function findNext(n, arr) {
const tempArr = [...arr]
tempArr.push(n)
tempArr.sort((a, b) => {
return a - b
})
let index = tempArr.indexOf(n)
if (index === 0) {
return tempArr[index + 1]
} else if (index === tempArr.length - 1) {
return tempArr[index - 1]
}
return tempArr[index] - tempArr[index - 1] >=
tempArr[index + 1] - tempArr[index]
? tempArr[index + 1]
: tempArr[index - 1]
}连续子数组的最大和
- 贪心算法
var maxSubArray = function (nums) {
let ans = nums[0]
let sum = 0
for (const num of nums) {
if (sum > 0) {
// 继续加当前元素
sum += num
} else {
// 加上当前元素只会对最终数组和起减少的作用，而不是增大数组和，所以就直接以当前元素为起点新起数组求最大数组和
sum = num
}
ans = Math.max(ans, sum)
}
return ans
}动态规划
/** * @param {number[]} nums * @return {number} */ var maxSubArray = function (nums) { let n = nums.length if (n == 0) return 0 let dp = new Array(n).fill(0) // base case 第一个元素前面没有子数组 dp[0] = nums[0] // 状态转移方程 for (let i = 1; i < n; i++) { dp[i] = Math.max( // 自成一派 nums[i], // 与前面的子数组合并 nums[i] + dp[i - 1] ) } return Math.max(...dp) }/** * @param {number[]} nums * @return {number} */ var maxSubArray = function (nums) { let n = nums.length if (n == 0) return 0 let cur = nums[0] //保存上一次的最大值 let res = cur //保存结果 for (let i = 1; i < n; i++) { cur = Math.max(nums[i], nums[i] + cur) res = Math.max(res, cur) } return res }全排列
// 入参是一个数组 const permute = function (nums) { // 缓存数组的长度 const len = nums.length // curr 变量用来记录当前的排列内容 const curr = [] // res 用来记录所有的排列顺序 const res = [] // visited 用来避免重复使用同一个数字 const visited = {} // 定义 dfs 函数，入参是坑位的索引（从 0 计数） function dfs(nth) { // 若遍历到了不存在的坑位（第 len+1 个），则触碰递归边界返回 if (nth === len) { // 此时前 len 个坑位已经填满，将对应的排列记录下来 res.push(curr.slice()) return } // 检查手里剩下的数字有哪些 for (let i = 0; i < len; i++) { // 若 nums[i] 之前没被其它坑位用过，则可以理解为“这个数字剩下了” if (!visited[nums[i]]) { // 给 nums[i] 打个“已用过”的标 visited[nums[i]] = 1 // 将nums[i]推入当前排列 curr.push(nums[i]) // 基于这个排列继续往下一个坑走去 dfs(nth + 1) // nums[i]让出当前坑位 curr.pop() // 下掉“已用过”标识 visited[nums[i]] = 0 } } } // 从索引为 0 的坑位（也就是第一个坑位）开始 dfs dfs(0) return res }
队列
如何用栈实现一个队列？
push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。
/** * 初始化构造函数 */ const MyQueue = function () { // 初始化两个栈 this.stack1 = [] this.stack2 = [] } /** * Push element x to the back of queue. * @param {number} x * @return {void} */ MyQueue.prototype.push = function (x) { // 直接调度数组的 push 方法 this.stack1.push(x) } /** * Removes the element from in front of queue and returns that element. * @return {number} */ MyQueue.prototype.pop = function () { // 假如 stack2 为空，需要将 stack1 的元素转移进来 if (this.stack2.length <= 0) { // 当 stack1 不为空时，出栈 while (this.stack1.length !== 0) { // 将 stack1 出栈的元素推入 stack2 this.stack2.push(this.stack1.pop()) } } // 为了达到逆序的目的，我们只从 stack2 里出栈元素 return this.stack2.pop() } /** * Get the front element. * @return {number} * 这个方法和 pop 唯一的区别就是没有将定位到的值出栈 */ MyQueue.prototype.peek = function () { if (this.stack2.length <= 0) { // 当 stack1 不为空时，出栈 while (this.stack1.length != 0) { // 将 stack1 出栈的元素推入 stack2 this.stack2.push(this.stack1.pop()) } } // 缓存 stack2 的长度 const stack2Len = this.stack2.length return stack2Len && this.stack2[stack2Len - 1] } /** * Returns whether the queue is empty. * @return {boolean} */ MyQueue.prototype.empty = function () { // 若 stack1 和 stack2 均为空，那么队列空 return !this.stack1.length && !this.stack2.length }找出所有滑动窗口里的最大值。
const maxSlidingWindow = function (nums, k) { // 缓存数组的长度 const len = nums.length // 初始化结果数组 const res = [] // 初始化双端队列 const deque = [] // 开始遍历数组 for (let i = 0; i < len; i++) { // 当队尾元素小于当前元素时 while (deque.length && nums[deque[deque.length - 1]] < nums[i]) { // 将队尾元素（索引）不断出队，直至队尾元素大于等于当前元素 deque.pop() } // 入队当前元素索引（注意是索引） deque.push(i) // 当队头元素的索引已经被排除在滑动窗口之外时 while (deque.length && deque[0] <= i - k) { // 将队头元素索引出队 deque.shift() } // 判断滑动窗口的状态，只有在被遍历的元素个数大于 k 的时候，才更新结果数组 if (i >= k - 1) { res.push(nums[deque[0]]) } } // 返回结果数组 return res }
栈
栈的设计——“最小栈”问题
const MinStack = function () {
this.stack = []
// 定义辅助栈
this.stack2 = []
}
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
this.stack.push(x)
// 若入栈的值小于当前最小值，则推入辅助栈栈顶
if (this.stack2.length == 0 || this.stack2[this.stack2.length - 1] >= x) {
this.stack2.push(x)
}
}
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
// 若出栈的值和当前最小值相等，那么辅助栈也要对栈顶元素进行出栈，确保最小值的有效性
if (this.stack.pop() == this.stack2[this.stack2.length - 1]) {
this.stack2.pop()
}
}
/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.stack[this.stack.length - 1]
}
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
// 辅助栈的栈顶，存的就是目标中的最小值
return this.stack2[this.stack2.length - 1]
}有效括号
var isValid = function (s) {
var map = new Map([
["(", ")"],
["[", "]"],
["{", "}"],
])
var arr = []
var i = 0
for (const ch of s) {
switch (ch) {
case "(":
case "[":
case "{":
arr.push(ch)
i++
break
case ")":
case "]":
case "}":
// arr.push()
if (ch == map.get(arr[i - 1])) {
arr.pop()
i--
} else {
return false
}
}
}
return arr.length === 0
}链表
链表的合并
const mergeTwoLists = function (l1, l2) {
// 定义头结点，确保链表可以被访问到
let head = new ListNode()
// cur 这里就是咱们那根“针”
let cur = head
// “针”开始在 l1 和 l2 间穿梭了
while (l1 && l2) {
// 如果 l1 的结点值较小
if (l1.val <= l2.val) {
// 先串起 l1 的结点
cur.next = l1
// l1 指针向前一步
l1 = l1.next
} else {
// l2 较小时，串起 l2 结点
cur.next = l2
// l2 向前一步
l2 = l2.next
}
// “针”在串起一个结点后，也会往前一步
cur = cur.next
}
// 处理链表不等长的情况
cur.next = l1 !== null ? l1 : l2
// 返回起始结点
return head.next
}链表结点的删除
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
const deleteDuplicates = function (head) {
// 设定 cur 指针，初始位置为链表第一个结点
let cur = head
// 遍历链表
while (cur != null && cur.next != null) {
// 若当前结点和它后面一个结点值相等（重复）
if (cur.val === cur.next.val) {
// 删除靠后的那个结点（去重）
cur.next = cur.next.next
} else {
// 若不重复，继续遍历
cur = cur.next
}
}
return head
}给定一个排序链表，删除所有含有重复数字的结点，只保留原始链表中 没有重复出现的数字。
const deleteDuplicates = function (head) {
// 极端情况：0个或1个结点，则不会重复，直接返回
if (!head || !head.next) {
return head
}
// dummy 登场
let dummy = new ListNode()
// dummy 永远指向头结点
dummy.next = head
// cur 从 dummy 开始遍历
let cur = dummy
// 当 cur 的后面有至少两个结点时
while (cur.next && cur.next.next) {
// 对 cur 后面的两个结点进行比较
if (cur.next.val === cur.next.next.val) {
// 若值重复，则记下这个值
let val = cur.next.val
// 反复地排查后面的元素是否存在多次重复该值的情况
while (cur.next && cur.next.val === val) {
// 若有，则删除
cur.next = cur.next.next
}
} else {
// 若不重复，则正常遍历
cur = cur.next
}
}
// 返回链表的起始结点
return dummy.next
}删除链表的倒数第 N 个结点
const removeNthFromEnd = function (head, n) {
// 初始化 dummy 结点
const dummy = new ListNode()
// dummy指向头结点
dummy.next = head
// 初始化快慢指针，均指向dummy
let fast = dummy
let slow = dummy
// 快指针闷头走 n 步
while (n !== 0) {
fast = fast.next
n--
}
// 快慢指针一起走
while (fast.next) {
fast = fast.next
slow = slow.next
}
// 慢指针删除自己的后继结点
slow.next = slow.next.next
// 返回头结点
return dummy.next
}链表的反转
const reverseList = function (head) {
// 初始化前驱结点为 null
let pre = null
// 初始化目标结点为头结点
let cur = head
// 只要目标结点不为 null，遍历就得继续
while (cur !== null) {
// 记录一下 next 结点
let next = cur.next
// 反转指针
cur.next = pre
// pre 往前走一步
pre = cur
// cur往前走一步
cur = next
}
// 反转结束后，pre 就会变成新链表的头结点
return pre
}局部反转一个链表
const reverseBetween = function (head, m, n) {
// 定义pre、cur，用leftHead来承接整个区间的前驱结点
let pre, cur, leftHead
// 别忘了用 dummy 嗷
const dummy = new ListNode()
// dummy后继结点是头结点
dummy.next = head
// p是一个游标，用于遍历，最初指向 dummy
let p = dummy
// p往前走 m-1 步，走到整个区间的前驱结点处
for (let i = 0; i < m - 1; i++) {
p = p.next
}
// 缓存这个前驱结点到 leftHead 里
leftHead = p
// start 是反转区间的第一个结点
let start = leftHead.next
// pre 指向start
pre = start
// cur 指向 start 的下一个结点
cur = pre.next
// 开始重复反转动作
for (let i = m; i < n; i++) {
let next = cur.next
cur.next = pre
pre = cur
cur = next
}
// leftHead 的后继结点此时为反转后的区间的第一个结点
leftHead.next = pre
// 将区间内反转后的最后一个结点 next 指向 cur
start.next = cur
// dummy.next 永远指向链表头结点
return dummy.next
}判断链表是否成环
const hasCycle = function (head) {
// 只要结点存在，那么就继续遍历
while (head) {
// 如果 flag 已经立过了，那么说明环存在
if (head.flag) {
return true
} else {
// 如果 flag 没立过，就立一个 flag 再往 下走
head.flag = true
head = head.next
}
}
return false
}定位环的起点
const detectCycle = function (head) {
while (head) {
if (head.flag) {
return head
} else {
head.flag = true
head = head.next
}
}
return null
}相交链表
- 哈希表
var getIntersectionNode = function (headA, headB) {
if (!headA || !headB) return null
const hashmap = new Map()
let pA = headA
while (pA) {
hashmap.set(pA, 1)
pA = pA.next
}
let pB = headB
while (pB) {
if (hashmap.has(pB)) return pB
pB = pB.next
}
return null
}双指针
var getIntersectionNode = function (headA, headB) { if (!headA || !headB) return null let pA = headA, pB = headB while (pA !== pB) { pA = pA === null ? headB : pA.next pB = pB === null ? headA : pB.next } return pA }
二叉树
递归遍历
var preorderTraversal = function (root) {
// 首先声明一个数组用来存放遍历得到的节点val值
const result = []
// 采用递归遍历
function preorder(node) {
// 如果节点为空直接返回
if (!node) return
// 先序遍历就是把当前节点输出 放在左右递归调用之前 将其数值放入结果数组
result.push(node.val)
// 然后递归遍历左孩子
preorder(node.left)
// 最后递归遍历右孩子
preorder(node.right)
}
preorder(root)
// 返回结果
return result
}迭代遍历（利用栈思想）
前序
/** * @param {TreeNode} root * @return {number[]} */ const preorderTraversal = function (root) { // 定义结果数组 const res = [] // 处理边界条件 if (!root) { return res } // 初始化栈结构 const stack = [] // 首先将根结点入栈 stack.push(root) // 若栈不为空，则重复出栈、入栈操作 while (stack.length) { // 将栈顶结点记为当前结点 const cur = stack.pop() // 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部 res.push(cur.val) // 若当前子树根结点有右孩子，则将右孩子入栈 if (cur.right) { stack.push(cur.right) } // 若当前子树根结点有左孩子，则将左孩子入栈 if (cur.left) { stack.push(cur.left) } } // 返回结果数组 return res }后序
/** * @param {TreeNode} root * @return {number[]} */ const postorderTraversal = function (root) { // 定义结果数组 const res = [] // 处理边界条件 if (!root) { return res } // 初始化栈结构 const stack = [] // 首先将根结点入栈 stack.push(root) // 若栈不为空，则重复出栈、入栈操作 while (stack.length) { // 将栈顶结点记为当前结点 const cur = stack.pop() // 当前结点就是当前子树的根结点，把这个结点放在结果数组的头部 res.unshift(cur.val) // 若当前子树根结点有左孩子，则将左孩子入栈 if (cur.left) { stack.push(cur.left) } // 若当前子树根结点有右孩子，则将右孩子入栈 if (cur.right) { stack.push(cur.right) } } // 返回结果数组 return res }
中序
const inorderTraversal = function (root) {
// 定义结果数组
const res = []
// 初始化栈结构
const stack = []
// 用一个 cur 结点充当游标
let cur = root
// 当 cur 不为空、或者 stack 不为空时，重复以下逻辑
while (cur || stack.length) {
// 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来
while (cur) {
// 将途径的结点入栈
stack.push(cur)
// 继续搜索当前结点的左孩子
cur = cur.left
}
// 取出栈顶元素
cur = stack.pop()
// 将栈顶元素入栈
res.push(cur.val)
// 尝试读取 cur 结点的右孩子
cur = cur.right
}
// 返回结果数组
return res
}层序遍历
- 返回数组
function BFS(root) {
const res = []
const queue = [] // 初始化队列queue
// 根结点首先入队
queue.push(root)
// 队列不为空，说明没有遍历完全
while (queue.length) {
const top = queue[0] // 取出队头元素
// 访问 top
res.push(top.val)
// 如果左子树存在，左子树入队
if (top.left) {
queue.push(top.left)
}
// 如果右子树存在，右子树入队
if (top.right) {
queue.push(top.right)
}
queue.shift() // 访问完毕，队头元素出队
}
}- 返回二维数组
var levelOrder = function (root) {
/* 非递归的实现方式 */
let res = []
if (root == null) return res
let queue = [root]
// while 循环控制从上向下一层层遍历
while (queue.length) {
let size = queue.length
// 记录这一层的节点值
let level = []
// for 循环控制每一层从左向右遍历
for (let i = 0; i < size; i++) {
let cur = queue.shift()
level.push(cur.val)
if (cur.left != null) queue.push(cur.left)
if (cur.right != null) queue.push(cur.right)
}
res.push(level)
}
return res
}动态规划
爬楼梯
const climbStairs = function(n) {
// 处理递归边界
if(n === 1) {
return 1
}
if(n === 2){
return 2
}
// 递归计算
return climbStairs(n-1) + climbStairs(n-2)
};
--------------------
// 定义记忆数组 f
const f = []
const climbStairs = function(n) {
if(n==1) {
return 1
}
if(n==2) {
return 2
}
// 若f[n]不存在，则进行计算
if(f[n]===undefined) f[n] = climbStairs(n-1) + climbStairs(n-2)
// 若f[n]已经求解过，直接返回
return f[n]
};
-------------
const climbStairs = function(n) {
// 初始化状态数组
const f = [];
// 初始化已知值
f[1] = 1;
f[2] = 2;
// 动态更新每一层楼梯对应的结果
for(let i = 3;i <= n;i++){
f[i] = f[i-2] + f[i-1];
}
// 返回目标值
return f[n];
};如何优雅地找硬币
const coinChange = function (coins, amount) {
// 用于保存每个目标总额对应的最小硬币个数
const f = []
// 提前定义已知情况
f[0] = 0
// 遍历 [1, amount] 这个区间的硬币总额
for (let i = 1; i <= amount; i++) {
// 求的是最小值，因此我们预设为无穷大，确保它一定会被更小的数更新
f[i] = Infinity
// 循环遍历每个可用硬币的面额
for (let j = 0; j < coins.length; j++) {
// 若硬币面额小于目标总额，则问题成立
if (i - coins[j] >= 0) {
// 状态转移方程
f[i] = Math.min(f[i], f[i - coins[j]] + 1)
}
}
}
// 若目标总额对应的解为无穷大，则意味着没有一个符合条件的硬币总数来更新它，本题无解，返回-1
if (f[amount] === Infinity) {
return -1
}
// 若有解，直接返回解的内容
return f[amount]
}背包模型
function knapsack(n, c, w, value) {
// dp是动态规划的状态保存数组
const dp = new Array(c + 1).fill(0)
// res 用来记录所有组合方案中的最大值
let res = -Infinity
for (let i = 1; i <= n; i++) {
for (let v = c; v >= w[i]; v--) {
// 写出状态转移方程
dp[v] = Math.max(dp[v], dp[v - w[i]] + value[i])
// 即时更新最大值
if (dp[v] > res) {
res = dp[v]
}
}
}
return res
}最长上升子序列模型
// 入参是一个数字序列
const lengthOfLIS = function (nums) {
// 缓存序列的长度
const len = nums.length
// 处理边界条件
if (!len) {
return 0
}
// 初始化数组里面每一个索引位的状态值
const dp = new Array(len).fill(1)
// 初始化最大上升子序列的长度为1
let maxLen = 1
// 从第2个元素开始，遍历整个数组
for (let i = 1; i < len; i++) {
// 每遍历一个新元素，都要“回头看”，看看能不能延长原有的上升子序列
for (let j = 0; j < i; j++) {
// 若遇到了一个比当前元素小的值，则意味着遇到了一个可以延长的上升子序列，故更新当前元素索引位对应的状态
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
// 及时更新上升子序列长度的最大值
if (dp[i] > maxLen) {
maxLen = dp[i]
}
}
// 遍历完毕，最后到手的就是最大上升子序列的长度
return maxLen
}函数
实现 add(1)(2)()
function add(a) {
return function (b) {
if (!b) return a
return add(a + b)
}
}
