手写实现
合并区间
var merge = function(intervals) {
intervals.sort((p, q) => p[0] - q[0]); // 按照左端点从小到大排序
const ans = [];
for (const p of intervals) {
const m = ans.length;
if (m && p[0] <= ans[m - 1][1]) { // 可以合并
ans[m - 1][1] = Math.max(ans[m - 1][1], p[1]); // 更新右端点最大值
} else { // 不相交,无法合并
ans.push(p); // 新的合并区间
}
}
return ans;
};
Promise.finally
Promise.prototype.finally = function (callback) {
return this.then((data) => {
return Promise.resolve(callback()).then(() => data); // data 上一个promise的成功态
}, err => {
return Promise.resolve(callback()).then(() => {
throw err; // 把之前的失败的err,抛出去
});
})
}
接雨水
var trap = function(height) {
const n = height.length;
if (n == 0) {
return 0;
}
const leftMax = new Array(n).fill(0);
leftMax[0] = height[0];
for (let i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
const rightMax = new Array(n).fill(0);
rightMax[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
let ans = 0;
for (let i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
};
无重复最大子串
var lengthOfLongestSubstring = function(s) {
if (s.length < 2) {
return s.length
}
function findNoDuplicate(start) {
const set = new Set()
let i = start
for (; i < s.length && !set.has(s[i]); i++) {
set.add(s[i])
}
return i
}
let p1 = 0
let p2 = 0
let maxCnt = 0
while (p1 < s.length) {
p2 = findNoDuplicate(p1)
maxCnt = Math.max(maxCnt, p2 - p1)
p1 += 1
}
return maxCnt
};
三数之和
var threeSum = function (nums) {
const res = []
nums.sort((a, b) => a - b)
for (let i = 0; i <= nums.length - 3; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue
}
let p1 = i + 1
let p2 = nums.length - 1
while (p1 < p2) {
const sum = nums[p1] + nums[p2] + nums[i]
if (sum === 0) {
res.push([nums[i], nums[p1], nums[p2]])
while (p1 < p2 && nums[p1] === nums[p1 + 1]) {
p1 += 1
}
while (p1 < p2 && nums[p2] === nums[p2 - 1]) {
p2 -= 1
}
p1 += 1
p2 -= 1
} else if (sum < 0) {
p1 += 1
} else {
p2 -= 1
}
}
}
return res
}
翻转列表(part)
var reverseBetween = function(head, left, right) {
if (left === right) {
return head
}
const dumb = new ListNode(0, head)
let p = dumb
for (let i = 0; i < left - 1; i++) {
p = p.next
}
const leftStart = p
p = p.next`9`
for (let i = 0; i < right - left; i++) {
const q = p.next
p.next = q.next
q.next = leftStart.next
leftStart.next = q
}
return dumb.next
};
防抖
事件触发 n 秒后再执行回调,如果在 n 秒内又被触发,则重新计时
常见场景:
搜索框输入
手机号、邮箱验证的检测
窗口 Resize,只有大小调整好后,再重新计算渲染
function debounce(fn, delay) {
var timer; // 维护一个 timer
return function () {
var _this = this; // 取debounce执行作用域的this
var args = arguments;
if (timer) {
clearTimeout(timer);
}
timer = setTimeout(function () {
fn.apply(_this, args); // 用apply指向调用debounce的对象,相当于_this.fn(args);
}, delay);
};
}
节流
防抖可能会产生“饥饿“问题,节流类似于给函数赋予一个 CD,一次函数执行后的一定时间内不能再被触发
常见场景
高频次提交,表单重复提交
滚动加载
function throttle(fn, delay) {
let locked = false
return function() {
const _this = this, args = arguments
if (!locked) {
locked = true
setTimeout(() => {
fn.call(_this, ...args)
locked = false
}, delay)
}
}
}
浅拷贝 & 深拷贝
浅拷贝
浅拷贝只复制第一层,使用 Object.assign() 可以实现
深拷贝
JSON.stringify(), JSON.parse()
递归实现
function deepClone(obj){ let objClone = Array.isArray(obj)?[]:{}; if(obj && typeof obj==="object"){ for(const key in obj){ if(obj.hasOwnProperty(key)){ //判断ojb子元素是否为对象,如果是,递归复制 if(obj[key]&&typeof obj[key] ==="object"){ objClone[key] = deepClone(obj[key]); }else{ //如果不是,简单复制 objClone[key] = obj[key]; } } } } return objClone; }
获取页面 URL
window.location.href
交集 并集 差集
// 交集
function intersect(arr1, arr2) {
const a = new Set(arr1), b = new Set(arr2)
return [...a].filter(e => b.has(e))
}
// 并集
function union(arr1, arr2) {
return [... new Set([...arr1, ...arr2])]
}
// 差集
function minus(arr1, arr2) {
const a = new Set(arr1), b = new Set(arr2)
return [...a].filter(e => !b.has(e))
}
千分位数字
// toLocaleString()
const n = 1532512.5111
console.log(n.toLocaleString())
// regx
判断对象是否为空
function isEmpty(obj) {
return obj === null || obj === undefined || (typeof obj === 'object' && Object.keys(obj).length === 0 )
}
传入 [1,[[2],3,4],5] ,返回 [1,2,3,4,5]
function flatten(arr) {
return arr.reduce((pre, cur) => pre.concat(Array.isArray(cur) ? flatten(cur) : cur), [])
}
console.log(flatten([1, [[2], 3, 4], 5]))
// solution 2
function flatten(arr) {
var result = [];
for (var i = 0, len = arr.length; i < len; i++) {
if (Array.isArray(arr[i])) {
result = result.concat(flatten(arr[i]))
}
else {
result.push(arr[i])
}
}
return result;
}
// solution 3
function flatten(arr) {
while (arr.some(item => Array.isArray(item))) {
arr = [].concat(...arr);
}
return arr;
}
16 进制转 rgb
function toRGB(color) {
const res = []
color = color.replace('#', '')
for (let i = 0; i < color.length; i += 2)
res.push(parseInt(color.substring(i, i + 2), 16))
return `(${res.join(',')})`
}
实现 sleep
function sleep(time) {
return new Promise(resolve => {
setTimeout(resolve, time)
})
}
console.log('start')
sleep(1000).then(() => console.log('end'))
生成 N 个范围在 (min, max) 中的数
function rand(min, max, N) {
const res = new Set()
while (res.size < N)
res.add(Math.random() * (max - min + 1) + min)
return [...res]
}
console.log(rand(10, 20, 5)) // [11.017595557525082, 15.637361330399937, 11.837208769291326, 20.813048069221455, 10.988156387379528]
拆分查询参数
function getParams() {
const res = {}
const str = window.location.search.substring(1)
if (str.length < 1)
return res
const params = str.split('&')
for (const param of params) {
const i = param.indexOf('=')
res[param.substring(0, i)] = param.substring(i + 1)
}
return res
}
去掉字符串前后的空格
function trim(str) {
let left = 0, right = str.length - 1
// left side
while (left < str.length && str[left] === ' ')
left++
if (left === str.length)
return ''
// right side
while (right >= 0 && str[right] === ' ')
right--
return str.substring(left, right + 1)
}
console.log(trim('b '))
// 正则
function trim(str) {
return str.replace(/^\s*/, "").replace(/\s*$/, "")
}
三数之和,双指针
var threeSum = function (nums) {
if (nums.length < 2)
return []
const res = new Set()
nums.sort((a, b) => a - b)
for (let i = 0; i < nums.length - 2; i++) {
let left = i + 1, right = nums.length - 1
while (left < right) {
const sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
// 注意不要直接添加数组,不然不能去重
res.add([nums[i], nums[left], nums[right]].join(','))
left++
right--
} else if (sum < 0) {
left++
} else {
right--
}
}
}
return [...res].map(x => x.split(','))
};
环形链表
var detectCycle = function(head) {
if (!head)
return null
let slow = head, fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
// 存在 loop,寻找入口
let p1 = head, p2 = fast
while(p1 !== p2) {
p1 = p1.next
p2 = p2.next
}
return p1
}
}
return null
};
二叉树公共祖先
var lowestCommonAncestor = function(root, p, q) {
if (!root ||root === p || root === q)
return root
const l = lowestCommonAncestor(root.left, p, q)
const r = lowestCommonAncestor(root.right,p, q)
if (l && r)
return root
else if (l && !r)
return l
else if (!l && r)
return r
else
return null
}
层序构建二叉树
function TreeNode(val, left, right) {
this.val = (val === undefined ? 0 : val)
this.left = (left === undefined ? null : left)
this.right = (right === undefined ? null : right)
}
function createTree(arr) {
if (arr.length === 0)
return null
const root = new TreeNode(arr.shift(), null, null)
const queue = [root]
while (queue.length > 0) {
const len = queue.length
for (let i = 0; i < len; i++) {
const t = queue.shift()
const l = arr.shift(), r = arr.shift()
t.left = l == null ? null : new TreeNode(l, null, null)
t.right = r == null ? null : new TreeNode(r, null, null)
t.left && queue.push(t.left)
t.right && queue.push(t.right)
}
}
return root
}
快排
function quickSort(arr) {
if (arr.length < 2)
return arr
const splitIdx = Math.floor(arr.length / 2)
const pivot = arr.splice(splitIdx, 1)[0]
const left = [], right = []
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot)
left.push(arr[i])
else
right.push(arr[i])
}
return [...quickSort(left), pivot, ...quickSort(right)]
}
归并排序
function mergeSort(arr) {
if (arr.length < 2)
return arr
const mid = Math.floor(arr.length / 2)
const left = arr.slice(0, mid), right = arr.slice(mid)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
const res = []
while (left.length > 0 && right.length > 0) {
if(left[0] < right[0])
res.push(left.shift())
else
res.push(right.shift())
}
while(left.length)
res.push(left.shift())
while(right.length)
res.push(right.shift())
return res
}
ES5 继承
function A() {
this.className = 'A'
}
A.prototype.whoami = function() {
console.log(this.className)
}
function B() {
this.className = 'B'
}
B.prototype = new A()
B.prototype.constructor = A
const b = new B()
b.whoami()
// 或者
function B() {
A.call(this)
}
异步加法
// 模拟一个异步加法
async function asyncAdd(a, b) {
await new Promise(resolve => setTimeout(resolve, Math.floor(Math.random() * 500)))
return a + b
}
// 使用归并递归相加
async function solve(nums) {
if (nums.length < 2)
return nums[0]
const mid = Math.floor(nums.length / 2)
// 注意 solve 函数本身就是异步的,所以要在调用前加 await !
const l = await solve(nums.slice(0, mid)), r = await solve(nums.slice(mid, nums.length))
return await asyncAdd(l, r)
}
solve([1, 2, 3, 4, 5]).then(v => console.log(v))
function asyncAdd(a, b) {
return new Promise(resolve => setTimeout(() => resolve(a + b), Math.random() * 1000))
}
async function solve(arr) {
const sum = await arr.reduce(async (pre, cur) => await asyncAdd(await pre, cur), 0)
console.log(sum)
}
solve([1,2,3]) // 6
function asyncAdd(a, b) {
return new Promise(resolve => setTimeout(() => resolve(a + b), Math.random() * 1000))
}
async function asyncSum(arr) {
if (arr.length < 2) return arr[0]
const promiseList = []
let i = 0
for (; i < arr.length - 1; i += 2)
promiseList.push(asyncAdd(arr[i], arr[i + 1]))
if (i < arr.length)
promiseList.push(arr[arr.length - 1])
return asyncSum(await Promise.all(promiseList))
}
asyncSum([1, 2, 3, 4, 5, 6, 7, 8, 9]).then(v => console.log(v)) // 45
手写 new
function myNew(Func, ...args) {
// 创建一个空的对象,将实例化对象的原型指向构造函数的原型对象
const instance = Object.create(Func.prototype);
// 将构造函数的this指向实例化对象
const res = Func.apply(instance, args);
//判断返回值
return typeof res === "object" ? res : instance;
}
手写实现 bind
Function.prototype.bind = function (thisArg, ...args) {
const obj = this // 谁调用了 bind,this 就指向谁
return function (...rest) {
return obj.apply(thisArg, [...args, ...rest])
}
}
Last updated