- 手写题
- 算法code
- 三星算法
- 3. 无重复字符的最长子串2次串和数组">3. 无重复字符的最长子串2次串和数组
- 20. 有效的括号1次串和数组">20. 有效的括号1次串和数组
- 384. 打乱数组1次串和数组">384. 打乱数组1次串和数组
- 三星算法
手写题
总结
js基础
- 手写 instanceof方法 (在js中是个操作符)2次instanceof 运算符用于判断构造函数的 prototype 属性是否出现在对象的原型链中的任何位置。
实现步骤:
1. 首先获取类型的原型
2. 然后获得对象的原型
3. 然后一直循环判断对象的原型是否等于类型的原型,直到对象原型为 null ,因为原型链最终为null
具体实现:function myInstanceof(left, right) {let proto = Object.getPrototypeOf(left), // 获取对象的原型prototype = right.prototype; // 获取构造函数的 prototype 对象// 判断构造函数的 prototype 对象是否在对象的原型链上while (true) {if (!proto) return false;if (proto === prototype) return true;proto = Object.getPrototypeOf(proto);}}
function myInstanceOf(left, right) {// 判断对象是不是某个类// left.__proto__ === right.prototype;// 获取对象的隐式原型和构造函数的显式原型let proto = Object.getPrototypeOf(left);prototype = right.prototype;while (true) {// 左边不是对象的情况,隐式原型链判断到null,// 说明不是该构造函数的实例if (!proto) return false;// 隐式原型链上有显式原型,是该类的实例if (proto === prototype) return true;// 继续沿着隐式原型链,进入循环判断proto = Object.getPrototypeOf(proto);}}
- 手写 new 操作符2次在调用 new 的过程中会发生以上四件事情:
(1)首先创建了一个新的空对象
(2)设置原型,将对象的原型设置为函数的 prototype 对象。
(3)让函数的 this 指向这个对象,执行构造函数的代码(为这个新对象添加属性)
(4)判断函数的返回值类型,如果是值类型,返回创建的对象。如果是引用类型,就返回这个引用类型
的对象。function objectFactory() {let newObject = null;//取实参的第一项let constructor = Array.prototype.shift.call(arguments);let result = null;// 判断参数是否是一个函数if (typeof constructor !== "function") {console.error("type error");return;}// 新建一个空对象,对象的原型为构造函数的 prototype 对象newObject = Object.create(constructor.prototype);// 将 this 指向新建对象,并执行函数//也就是让新对象调用构造函数,获得实例属性result = constructor.apply(newObject, arguments);// 判断返回对象let flag = result && (typeof result === "object" || typeof result ==="function");// 判断返回结果return flag ? result : newObject;}// 使用方法objectFactory(构造函数, 初始化参数);
function myNew() {// 初始化参数,构造函数赋值let newObject = null,result = null,constructor = Array.prototype.shift.apply(arguments);// 判断参数是否是函数if (typeof constructor !== "function") {console.error("type error");return;}// 创建一个新对象,对象的原型是构造函数的原型newObject = Object.create(constructor.prototype);//将构造函数的this,挂载到对象上result = constructor.apply(newObject, arguments);// 完整处理返回值的情况let flag =result &&(typeof result === "object" || typeof result === "function");return flag ? result : newObject;}
- 手写 Promise0次
javascript const PENDING = "pending"; const RESOLVED = "resolved"; const REJECTED = "rejected"; function MyPromise(fn) { // 保存初始化状态 var self = this; // 初始化状态 this.state = PENDING; // 用于保存 resolve 或者 rejected 传入的值 this.value = null; // 用于保存 resolve 的回调函数 this.resolvedCallbacks = []; // 用于保存 reject 的回调函数 this.rejectedCallbacks = []; // 状态转变为 resolved 方法 function resolve(value) { // 判断传入元素是否为 Promise 值,如果是,则状态改变必须等待前一个状态改变后再进行改变 if (value instanceof MyPromise) { return value.then(resolve, reject); } // 保证代码的执行顺序为本轮事件循环的末尾 setTimeout(() => { // 只有状态为 pending 时才能转变, if (self.state === PENDING) { // 修改状态 self.state = RESOLVED; // 设置传入的值 self.value = value; // 执行回调函数 self.resolvedCallbacks.forEach(callback => { callback(value); }); } }, 0); } // 状态转变为 rejected 方法 function reject(value) { // 保证代码的执行顺序为本轮事件循环的末尾 setTimeout(() => { // 只有状态为 pending 时才能转变 if (self.state === PENDING) { // 修改状态 self.state = REJECTED; // 设置传入的值 self.value = value; // 执行回调函数 self.rejectedCallbacks.forEach(callback => { callback(value); }); } }, 0); } // 将两个方法传入函数执行 try { fn(resolve, reject); } catch (e) { // 遇到错误时,捕获错误,执行 reject 函数 reject(e); } } MyPromise.prototype.then = function(onResolved, onRejected) { // 首先判断两个参数是否为函数类型,因为这两个参数是可选参数 onResolved = typeof onResolved === "function" ? onResolved : function(value) { return value; }; onRejected = typeof onRejected === "function" ? onRejected : function(error) { throw error; }; // 如果是等待状态,则将函数加入对应列表中 if (this.state === PENDING) { this.resolvedCallbacks.push(onResolved); this.rejectedCallbacks.push(onRejected); } // 如果状态已经凝固,则直接执行对应状态的函数 if (this.state === RESOLVED) { onResolved(this.value); } if (this.state === REJECTED) { onRejected(this.value); } }; - 手写 Promise.then 0次then 方法返回一个新的 promise 实例,为了在 promise 状态发生变化时( resolve / reject 被调
用时)再执行 then 里的函数,我们使用一个 callbacks 数组先把传给then的函数暂存起来,等状态
改变时再调用。
那么,怎么保证后一个 then 里的方法在前一个 then (可能是异步)结束之后再执行呢?
我们可以将传给 then 的函数和新 promise 的 resolve 一起 push 到前一个 promise 的callbacks 数组中,达到承前启后的效果:
- 承前:当前一个 promise 完成后,调用其 resolve 变更状态,在这个 resolve 里会依次调用callbacks 里的回调,这样就执行了 then 里的方法了
启后:上一步中,当 then 里的方法执行完成后,返回一个结果,如果这个结果是个简单的值,就直接调用新 promise 的 resolve ,让其状态变更,这又会依次调用新 promise 的 callbacks数组里的方法,循环往复。。如果返回的结果是个 promise ,则需要等它完成之后再触发新promise 的 resolve ,所以可以在其结果的 then 里调用新 promise 的 resolve
then(onFulfilled, onReject){// 保存前一个promise的thisconst self = this;return new MyPromise((resolve, reject) => {// 封装前一个promise成功时执行的函数let fulfilled = () => {try{const result = onFulfilled(self.value); // 承前return result instanceof MyPromise? result.then(resolve, reject) :resolve(result); //启后}catch(err){reject(err)}}// 封装前一个promise失败时执行的函数let rejected = () => {try{const result = onReject(self.reason);return result instanceof MyPromise? result.then(resolve, reject) :reject(result);}catch(err){reject(err)}}switch(self.status){case PENDING:self.onFulfilledCallbacks.push(fulfilled);self.onRejectedCallbacks.push(rejected);break;case FULFILLED:fulfilled();break;case REJECT:rejected();break;}})}
注意:
连续多个 then 里的回调方法是同步注册的,但注册到了不同的 callbacks 数组中,因为每次then 都返回新的 promise 实例(参考上面的例子和图)
- 注册完成后开始执行构造函数中的异步事件,异步完成之后依次调用 callbacks 数组中提前注册的回调
- 手写 Promise.all0次
1) 核心思路
1. 接收一个 Promise 实例的数组或具有 Iterator 接口的对象作为参数
2. 这个方法返回一个新的 promise 对象,
3. 遍历传入的参数,用Promise.resolve()将参数”包一层”,使其变成一个promise对象
4. 参数所有回调成功才是成功,返回值数组与参数顺序一致
5. 参数数组其中一个失败,则触发失败状态,第一个触发失败的 Promise 错误信息作为 Promise.all的错误信息。
2)实现代码
一般来说,Promise.all 用来处理多个并发请求,也是为了页面数据构造的方便,将一个页面所用到的在
不同接口的数据一起请求过来,不过,如果其中一个接口失败了,多个请求也就失败了,页面可能啥也
出不来,这就看当前页面的耦合程度了``javascript function promiseAll(promises) { return new Promise(function (resolve, reject) { if (!Array.isArray(promises)) { throw new TypeError(argument must be a array`); } var resolvedCounter = 0; var promiseNum = promises.length; var resolvedResult = []; for (let i = 0; i < promiseNum; i++) { Promise.resolve(promises[i]).then(
); } }); } // test let p1 = new Promise(function (resolve, reject) { setTimeout(function () { resolve(1); }, 1000); }); let p2 = new Promise(function (resolve, reject) { setTimeout(function () { resolve(2); }, 2000); }); let p3 = new Promise(function (resolve, reject) { setTimeout(function () { resolve(3); }, 3000); }); promiseAll([p3, p1, p2]).then((res) => { console.log(res); // [3, 1, 2] });(value) => {resolvedCounter++;resolvedResult[i] = value;if (resolvedCounter == promiseNum) {return resolve(resolvedResult);}},(error) => {return reject(error);}
7. 手写 Promise.race0次该方法的参数是 Promise 实例数组, 然后其 then 注册的回调方法是数组中的某一个 Promise 的状态变<br />为 fulfilled 的时候就执行. 因为 Promise 的状态只能改变一次, 那么我们只需要把 Promise.race 中产生<br />的 Promise 对象的 resolve 方法, 注入到数组中的每一个 Promise 实例中的回调函数中即可.```javascriptPromise.race = function (args) {return new Promise((resolve, reject) => {for (let i = 0, len = args.length; i < len; i++) {args[i].then(resolve, reject)}})}
8. 手写防抖函数1次
- 手写防抖函数函数防抖是指在事件被触发 n 秒后再执行回调,如果在这 n 秒内事件又被触发,则重新计时。这可以使
用在一些点击请求的事件上,避免因为用户的多次点击向后端发送多次请求。
// 函数防抖的实现function debounce(fn, wait) {let timer = null;return function () {let context = this,args = arguments;// 如果此时存在定时器的话,则取消之前的定时器重新记时if (timer) {clearTimeout(timer);timer = null;}// 设置定时器,使事件间隔指定事件后执行timer = setTimeout(() => {fn.apply(context, args);}, wait);};}
// 函数防抖的实现function debounce(fn, wait) {// 设置全局变量,记录setTimeout 得到的idlet timer = null;// 这里返回的函数是每次用户实际调用的防抖函数// 如果已经设定过定时器了就清空上一次的定时器// 开始一个定时器,延迟执行用户传入的方法return function () {// 保存函数调用时的thislet context = this,args = arguments;// console.log(this);// 如果此时存在定时器的话,则取消之前的定时器重新记时if (timer) {clearTimeout(timer);timer = null;}// 设置定时器,使事件间隔指定事件后执行timer = setTimeout(() => {// 更改回调函数的上下文对象// 将实际的this和参数传入用户实际调用的函数// console.log(this);fn.apply(context, args);}, wait);};}// 测试代码let count = 1;let container = document.getElementsByTagName("div")[0];function updateCount() {container.innerHTML = count++;}// container.addEventListener("mousemove", updateCount);container.addEventListener("mousemove", debounce(updateCount, 1000));
div {height: 200px;line-height: 200px;text-align: center;color: #fff;background-color: #444;font-size: 25px;border-radius: 3px;}
<!DOCTYPE html><html lang="en"><head><meta charset="UTF-8" /><meta http-equiv="X-UA-Compatible" content="IE=edge" /><meta name="viewport" content="width=device-width, initial-scale=1.0" /><title>Document</title><link rel="stylesheet" href="debounceCss.css" /></head><body><div id="container"></div><script src="debounce.js"></script></body></html>
关于事件监听中的this
普通的匿名函数中this指向触发事件的元素
箭头函数由于不会创建自己的this,它只能从作用域链的上层继承this,所以this指向全局对象window关于定时器
- 返回值是定时器ID
- 手写节流函数0次函数节流是指规定一个单位时间,在这个单位时间内,只能有一次触发事件的回调函数执行,如果在同
一个单位时间内某事件被触发多次,只有一次能生效。节流可以使用在 scroll 函数的事件监听上,通过
事件节流来降低事件调用的频率。// 函数节流的实现;function throttle(fn, delay) {let curTime = Date.now();return function() {let context = this,args = arguments,nowTime = Date.now();// 如果两次时间间隔超过了指定时间,则执行函数。if (nowTime - curTime >= delay) {curTime = Date.now();return fn.apply(context, args);}};}
算法code
三星算法
3. 无重复字符的最长子串2次串和数组
题解
var lengthOfLongestSubstring = function (s) {//声明所需变量:最小索引(所求子串的起点)minIndex,记录最长子串长度lenlet minIndex = 0;let maxLen = 0;for (let i = 0; i < s.length; i++) {/*遇到重复元素,判定条件是:当从i开始寻找s[i],返回的索引小于i,说明在i之前出现过s[i]元素,则从上一个重复元素的右边开始,继续向后累加不重复元素子串的长度总结:因为移动的是窗口的左侧minIndex,而右侧i只执行一次s的长度的循环,因此时间复杂度为O(n)——随着s的长度越大,执行时间越久比用2个循环的方式,运行时间上有长处*/if (s.indexOf(s[i], minIndex) < i) minIndex = s.indexOf(s[i], minIndex) + 1// 没有碰到重复元素时,minIndex没有变化,最长子串长度在增加else maxLen = Math.max(maxLen, i - minIndex + 1)}return maxLen;};

- 88. 合并两个有序数组串和数组 题解
- 88. 合并两个有序数组串和数组
- 合并两个有序数组 ```markdown 解题思路 暴力 没做过的第一个想法肯定是将num2放到num1后面,然后再一起进行排序
但这显然就用不到两个数组一开始就是有序的特征了
归并排序 复习一下归并排序的步骤:
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列; 设定两个指针,最初位置分别为两个已经排序序列的起始位置; 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置; 重复步骤 3 直到某一指针达到序列尾; 将另一序列剩下的所有元素直接复制到合并序列尾。 关键在于第三步~ 比较两个数组头元素然后将较小的推至最终数组,并将其从原数组中吐出去,不断循环,直到两个数组都为空
但值得注意的是 题目圆球 不返回一个新数组,而是存储再数组num1中,也就是要求原地修改,不能申请多的空间~ 为此,题目里说了 num1 的初始长度为 m+n,后n个元素为0
那么我们可以从后往前比较,从后面插入,先把较大的放进去即可,用三个指针模拟
cur:记录当前到那个位置 i:记录 num1 数组处理到哪里 j:记录 num2 数组处理到哪里 时间复杂度O(n) 空间复杂度O(1)
作者:okkjoo 链接:https://leetcode.cn/problems/merge-sorted-array/solution/88-he-bing-liang-ge-you-xu-shu-zu-by-okk-tjyl/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
- [415. 字符串相加](https://leetcode-cn.com/problems/add-strings)串和数组题解```javascriptvar addStrings = function(num1, num2) {let i = num1.length - 1, j = num2.length - 1, add = 0;const ans = [];while (i >= 0 || j >= 0 || add != 0) {const x = i >= 0 ? num1.charAt(i) - '0' : 0;const y = j >= 0 ? num2.charAt(j) - '0' : 0;const result = x + y + add;ans.push(result % 10);add = Math.floor(result / 10);i -= 1;j -= 1;}return ans.reverse().join('');};作者:LeetCode-Solution链接:https://leetcode.cn/problems/add-strings/solution/zi-fu-chuan-xiang-jia-by-leetcode-solution/来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
- 1. 两数之和串和数组
题解
var twoSum = function (nums, target) {let temp = 0;let ans = [];for (let i = 0; i < nums.length; i++) {temp = target - nums[i];if (nums.includes(temp) && nums.indexOf(temp) != i) {ans.push(i, nums.indexOf(temp));break;}}return ans;};//我自己的解法,空间占用少,但时间花费长
const twoSum = function(nums, target) {const len = nums.length;const map = new Map();for (let i = 0; i < len; i++) {const needNum = target - nums[i];if (map.has(needNum) && i !== map.get(needNum)) {return [i, map.get(needNum)];}// 边读边存map.set(nums[i], i);}}作者:lc_bug链接:https://leetcode.cn/problems/two-sum/solution/wo-de-shua-ti-si-lu-yi-liang-shu-zhi-he-93ue6/来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
20. 有效的括号1次串和数组
题解思路:
/*** @param {string} s* @return {boolean}*/var isValid = function (s) {// 如果串是奇数长度,不符合题目要求,直接falseif (s.length === 1) {return false;}// 用map保存括号对const pairs = new Map([[")", "("],["]", "["],["}", "{"],]);// 设置一个数组做栈,栈顶为stack[stack.length-1]let stack = [];for (const ch of s) {if(pairs.has(ch)){// 下面第一个判断:当前元素为右括号,而栈中没有元素。表明s中有偶数个没有配对的右括号“()}}{}{}{}”。// 第二个判断是:栈顶不是对应的左括号。ch为“)”,而栈顶是“[”。举例s:“[)”if(!stack.length|| stack[stack.length-1] !== pairs.get(ch)){return false;}stack.pop;}else{stack.push(ch);}}return !stack.length;};
- 70. 爬楼梯
- 46. 全排列
- 53. 最大子序和
- 206. 反转链表
- 102. 二叉树的层序遍历
- 141. 环形链表
- 补充题4. 手撕快速排序
- 704. 二分查找
- 94. 二叉树的中序遍历
- 剑指 Offer 22. 链表中倒数第K个节点
- 144. 二叉树的前序遍历
- 剑指 Offer 10- I. 斐波那契数列
- 剑指 Offer 10- II. 青蛙跳台阶
384. 打乱数组1次串和数组
题解思路:
关键点:理解n!种排列,以及数组每个位置上的概率如何计算(条件概率)。 ```javascript /**
- @param {number[]} nums */ var Solution = function (nums) { // 怎么把unms传给原型里的函数 this.nums = nums; this.original = nums.slice(); };
/**
- @return {number[]} */ Solution.prototype.reset = function () { this.nums = this.original.slice(); return this.nums; };
/**
- @return {number[]} / Solution.prototype.shuffle = function () { for (let i = 0; i < this.nums.length; i++) { let j = Math.floor(Math.random() (this.nums.length - i) + i); let temp = this.nums[i]; this.nums[i] = this.nums[j]; this.nums[j] = temp; } return this.nums; };
/**
- Your Solution object will be instantiated and called as such:
- var obj = new Solution(nums)
- var param_1 = obj.reset()
- var param_2 = obj.shuffle() */
---- [160. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists)- [509. 斐波那契数](https://leetcode-cn.com/problems/fibonacci-number)- [155. 最小栈](https://leetcode-cn.com/problems/min-stack)- [剑指 Offer 09. 用两个栈实队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof)- [349. 两个数组的交集](https://leetcode-cn.com/problems/intersection-of-two-arrays)- [429. N叉树的层序遍历](https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal)- [283. 移动零](https://leetcode-cn.com/problems/move-zeroes)- [232. 用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks)- [9. 回文数](https://leetcode-cn.com/problems/palindrome-number)- [148. 排序链表](https://leetcode-cn.com/problems/sort-list)- [67. 二进制求和](https://leetcode-cn.com/problems/add-binary)- [剑指 Offer 03. 数组中重复数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof)- [344. 反转字符串](https://leetcode-cn.com/problems/reverse-string)- [876. 链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list)- [1556. 千位分隔数](https://leetcode-cn.com/problems/thousand-separator)- [剑指 Offer 42. 连续子数组的最大和](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof)- [125. 验证回文串](https://leetcode-cn.com/problems/valid-palindrome)<a name="sC95t"></a>## 常用的方法1.> 实现数组的[浅拷贝](https://www.cnblogs.com/zhanghongkun/p/11535911.html),有2个可选参数(begin,end)> 返回值:一个新数组浅拷贝示例```javascriptvar nums = [1, 2, 3, 4, { name: "hello" }];var or = nums.slice();console.log(nums);or[4].name = "wuhu";console.log(or);//运行结果如下:改变or[4]对象中的name属性,结果nums的对象属性也被修改了,说明是浅拷贝,只拷贝了栈中的值//就是只拷贝了基础数据类型(存在栈中的数据),对于引用数据类型,拷贝了其地址值

判断数组中是否含有某元素,并返回该元素的下标,还可以指定开始查找的位置fromIndex(可选)。 返回值:首个被找到的元素在数组中的索引位置; 若没有找到则返回 -1
js内置的对象,常与数组一起使用 has(key) get(key)
创建循环的语句,可以把of后的迭代对象中的每一个元素赋给for后面的变量。
- 关于事件监听中的this
普通的匿名函数中this指向触发事件的元素 箭头函数由于不会创建自己的this,它只能从作用域链的上层继承this,所以this指向全局对象window
关于定时器
返回值是定时器ID
