手写题

10 offer收割机之手写代码篇.pdf

总结

js基础

  1. 手写 instanceof方法 (在js中是个操作符)2次instanceof 运算符用于判断构造函数的 prototype 属性是否出现在对象的原型链中的任何位置。
    实现步骤:
    1. 首先获取类型的原型
    2. 然后获得对象的原型
    3. 然后一直循环判断对象的原型是否等于类型的原型,直到对象原型为 null ,因为原型链最终为null
    具体实现:
    1. function myInstanceof(left, right) {
    2. let proto = Object.getPrototypeOf(left), // 获取对象的原型
    3. prototype = right.prototype; // 获取构造函数的 prototype 对象
    4. // 判断构造函数的 prototype 对象是否在对象的原型链上
    5. while (true) {
    6. if (!proto) return false;
    7. if (proto === prototype) return true;
    8. proto = Object.getPrototypeOf(proto);
    9. }
    10. }
  1. function myInstanceOf(left, right) {
  2. // 判断对象是不是某个类
  3. // left.__proto__ === right.prototype;
  4. // 获取对象的隐式原型和构造函数的显式原型
  5. let proto = Object.getPrototypeOf(left);
  6. prototype = right.prototype;
  7. while (true) {
  8. // 左边不是对象的情况,隐式原型链判断到null,
  9. // 说明不是该构造函数的实例
  10. if (!proto) return false;
  11. // 隐式原型链上有显式原型,是该类的实例
  12. if (proto === prototype) return true;
  13. // 继续沿着隐式原型链,进入循环判断
  14. proto = Object.getPrototypeOf(proto);
  15. }
  16. }
  1. 手写 new 操作符2次在调用 new 的过程中会发生以上四件事情:
    (1)首先创建了一个新的空对象
    (2)设置原型,将对象的原型设置为函数的 prototype 对象。
    (3)让函数的 this 指向这个对象,执行构造函数的代码(为这个新对象添加属性)
    (4)判断函数的返回值类型,如果是值类型,返回创建的对象。如果是引用类型,就返回这个引用类型
    的对象。
    1. function objectFactory() {
    2. let newObject = null;
    3. //取实参的第一项
    4. let constructor = Array.prototype.shift.call(arguments);
    5. let result = null;
    6. // 判断参数是否是一个函数
    7. if (typeof constructor !== "function") {
    8. console.error("type error");
    9. return;
    10. }
    11. // 新建一个空对象,对象的原型为构造函数的 prototype 对象
    12. newObject = Object.create(constructor.prototype);
    13. // 将 this 指向新建对象,并执行函数//也就是让新对象调用构造函数,获得实例属性
    14. result = constructor.apply(newObject, arguments);
    15. // 判断返回对象
    16. let flag = result && (typeof result === "object" || typeof result ===
    17. "function");
    18. // 判断返回结果
    19. return flag ? result : newObject;
    20. }
    21. // 使用方法
    22. objectFactory(构造函数, 初始化参数);
  1. function myNew() {
  2. // 初始化参数,构造函数赋值
  3. let newObject = null,
  4. result = null,
  5. constructor = Array.prototype.shift.apply(arguments);
  6. // 判断参数是否是函数
  7. if (typeof constructor !== "function") {
  8. console.error("type error");
  9. return;
  10. }
  11. // 创建一个新对象,对象的原型是构造函数的原型
  12. newObject = Object.create(constructor.prototype);
  13. //将构造函数的this,挂载到对象上
  14. result = constructor.apply(newObject, arguments);
  15. // 完整处理返回值的情况
  16. let flag =
  17. result &&
  18. (typeof result === "object" || typeof result === "function");
  19. return flag ? result : newObject;
  20. }
  1. 手写 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); } };
  2. 手写 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

    1. then(onFulfilled, onReject){
    2. // 保存前一个promise的this
    3. const self = this;
    4. return new MyPromise((resolve, reject) => {
    5. // 封装前一个promise成功时执行的函数
    6. let fulfilled = () => {
    7. try{
    8. const result = onFulfilled(self.value); // 承前
    9. return result instanceof MyPromise? result.then(resolve, reject) :
    10. resolve(result); //启后
    11. }catch(err){
    12. reject(err)
    13. }
    14. }
    15. // 封装前一个promise失败时执行的函数
    16. let rejected = () => {
    17. try{
    18. const result = onReject(self.reason);
    19. return result instanceof MyPromise? result.then(resolve, reject) :
    20. reject(result);
    21. }catch(err){
    22. reject(err)
    23. }
    24. }
    25. switch(self.status){
    26. case PENDING:
    27. self.onFulfilledCallbacks.push(fulfilled);
    28. self.onRejectedCallbacks.push(rejected);
    29. break;
    30. case FULFILLED:
    31. fulfilled();
    32. break;
    33. case REJECT:
    34. rejected();
    35. break;
    36. }
    37. })
    38. }

    注意:

  • 连续多个 then 里的回调方法是同步注册的,但注册到了不同的 callbacks 数组中,因为每次then 都返回新的 promise 实例(参考上面的例子和图)

  • 注册完成后开始执行构造函数中的异步事件,异步完成之后依次调用 callbacks 数组中提前注册的回调
  1. 手写 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(
    1. (value) => {
    2. resolvedCounter++;
    3. resolvedResult[i] = value;
    4. if (resolvedCounter == promiseNum) {
    5. return resolve(resolvedResult);
    6. }
    7. },
    8. (error) => {
    9. return reject(error);
    10. }
    ); } }); } // 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] });
  1. 7. 手写 Promise.race0次该方法的参数是 Promise 实例数组, 然后其 then 注册的回调方法是数组中的某一个 Promise 的状态变<br />为 fulfilled 的时候就执行. 因为 Promise 的状态只能改变一次, 那么我们只需要把 Promise.race 中产生<br />的 Promise 对象的 resolve 方法, 注入到数组中的每一个 Promise 实例中的回调函数中即可.
  2. ```javascript
  3. Promise.race = function (args) {
  4. return new Promise((resolve, reject) => {
  5. for (let i = 0, len = args.length; i < len; i++) {
  6. args[i].then(resolve, reject)
  7. }
  8. })
  9. }

8. 手写防抖函数1次

  1. 手写防抖函数函数防抖是指在事件被触发 n 秒后再执行回调,如果在这 n 秒内事件又被触发,则重新计时。这可以使
    用在一些点击请求的事件上,避免因为用户的多次点击向后端发送多次请求。
  1. // 函数防抖的实现
  2. function debounce(fn, wait) {
  3. let timer = null;
  4. return function () {
  5. let context = this,
  6. args = arguments;
  7. // 如果此时存在定时器的话,则取消之前的定时器重新记时
  8. if (timer) {
  9. clearTimeout(timer);
  10. timer = null;
  11. }
  12. // 设置定时器,使事件间隔指定事件后执行
  13. timer = setTimeout(() => {
  14. fn.apply(context, args);
  15. }, wait);
  16. };
  17. }

  1. // 函数防抖的实现
  2. function debounce(fn, wait) {
  3. // 设置全局变量,记录setTimeout 得到的id
  4. let timer = null;
  5. // 这里返回的函数是每次用户实际调用的防抖函数
  6. // 如果已经设定过定时器了就清空上一次的定时器
  7. // 开始一个定时器,延迟执行用户传入的方法
  8. return function () {
  9. // 保存函数调用时的this
  10. let context = this,
  11. args = arguments;
  12. // console.log(this);
  13. // 如果此时存在定时器的话,则取消之前的定时器重新记时
  14. if (timer) {
  15. clearTimeout(timer);
  16. timer = null;
  17. }
  18. // 设置定时器,使事件间隔指定事件后执行
  19. timer = setTimeout(() => {
  20. // 更改回调函数的上下文对象
  21. // 将实际的this和参数传入用户实际调用的函数
  22. // console.log(this);
  23. fn.apply(context, args);
  24. }, wait);
  25. };
  26. }
  27. // 测试代码
  28. let count = 1;
  29. let container = document.getElementsByTagName("div")[0];
  30. function updateCount() {
  31. container.innerHTML = count++;
  32. }
  33. // container.addEventListener("mousemove", updateCount);
  34. container.addEventListener("mousemove", debounce(updateCount, 1000));
  1. div {
  2. height: 200px;
  3. line-height: 200px;
  4. text-align: center;
  5. color: #fff;
  6. background-color: #444;
  7. font-size: 25px;
  8. border-radius: 3px;
  9. }
  1. <!DOCTYPE html>
  2. <html lang="en">
  3. <head>
  4. <meta charset="UTF-8" />
  5. <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  6. <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  7. <title>Document</title>
  8. <link rel="stylesheet" href="debounceCss.css" />
  9. </head>
  10. <body>
  11. <div id="container"></div>
  12. <script src="debounce.js"></script>
  13. </body>
  14. </html>
  • 关于事件监听中的this

    普通的匿名函数中this指向触发事件的元素
    箭头函数由于不会创建自己的this,它只能从作用域链的上层继承this,所以this指向全局对象window

  • 关于定时器

    • 返回值是定时器ID
  1. 手写节流函数0次函数节流是指规定一个单位时间,在这个单位时间内,只能有一次触发事件的回调函数执行,如果在同
    一个单位时间内某事件被触发多次,只有一次能生效。节流可以使用在 scroll 函数的事件监听上,通过
    事件节流来降低事件调用的频率。
    1. // 函数节流的实现;
    2. function throttle(fn, delay) {
    3. let curTime = Date.now();
    4. return function() {
    5. let context = this,
    6. args = arguments,
    7. nowTime = Date.now();
    8. // 如果两次时间间隔超过了指定时间,则执行函数。
    9. if (nowTime - curTime >= delay) {
    10. curTime = Date.now();
    11. return fn.apply(context, args);
    12. }
    13. };
    14. }

算法code

三星算法

3. 无重复字符的最长子串2次串和数组

题解

  1. var lengthOfLongestSubstring = function (s) {
  2. //声明所需变量:最小索引(所求子串的起点)minIndex,记录最长子串长度len
  3. let minIndex = 0;
  4. let maxLen = 0;
  5. for (let i = 0; i < s.length; i++) {
  6. /*
  7. 遇到重复元素,判定条件是:
  8. 当从i开始寻找s[i],返回的索引小于i,
  9. 说明在i之前出现过s[i]元素,则从上一个重复元素的右边开始,
  10. 继续向后累加不重复元素子串的长度
  11. 总结:因为移动的是窗口的左侧minIndex,而右侧i只执行一次s的长度的循环,
  12. 因此时间复杂度为O(n)
  13. ——随着s的长度越大,执行时间越久
  14. 比用2个循环的方式,运行时间上有长处
  15. */
  16. if (s.indexOf(s[i], minIndex) < i) minIndex = s.indexOf(s[i], minIndex) + 1
  17. // 没有碰到重复元素时,minIndex没有变化,最长子串长度在增加
  18. else maxLen = Math.max(maxLen, i - minIndex + 1)
  19. }
  20. return maxLen;
  21. };

image.png


  1. 合并两个有序数组 ```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) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  1. - [415. 字符串相加](https://leetcode-cn.com/problems/add-strings)串和数组
  2. 题解```javascript
  3. var addStrings = function(num1, num2) {
  4. let i = num1.length - 1, j = num2.length - 1, add = 0;
  5. const ans = [];
  6. while (i >= 0 || j >= 0 || add != 0) {
  7. const x = i >= 0 ? num1.charAt(i) - '0' : 0;
  8. const y = j >= 0 ? num2.charAt(j) - '0' : 0;
  9. const result = x + y + add;
  10. ans.push(result % 10);
  11. add = Math.floor(result / 10);
  12. i -= 1;
  13. j -= 1;
  14. }
  15. return ans.reverse().join('');
  16. };
  17. 作者:LeetCode-Solution
  18. 链接:https://leetcode.cn/problems/add-strings/solution/zi-fu-chuan-xiang-jia-by-leetcode-solution/
  19. 来源:力扣(LeetCode)
  20. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
  • 1. 两数之和串和数组 题解
    1. var twoSum = function (nums, target) {
    2. let temp = 0;
    3. let ans = [];
    4. for (let i = 0; i < nums.length; i++) {
    5. temp = target - nums[i];
    6. if (nums.includes(temp) && nums.indexOf(temp) != i) {
    7. ans.push(i, nums.indexOf(temp));
    8. break;
    9. }
    10. }
    11. return ans;
    12. };
    13. //我自己的解法,空间占用少,但时间花费长

  1. const twoSum = function(nums, target) {
  2. const len = nums.length;
  3. const map = new Map();
  4. for (let i = 0; i < len; i++) {
  5. const needNum = target - nums[i];
  6. if (map.has(needNum) && i !== map.get(needNum)) {
  7. return [i, map.get(needNum)];
  8. }
  9. // 边读边存
  10. map.set(nums[i], i);
  11. }
  12. }
  13. 作者:lc_bug
  14. 链接:https://leetcode.cn/problems/two-sum/solution/wo-de-shua-ti-si-lu-yi-liang-shu-zhi-he-93ue6/
  15. 来源:力扣(LeetCode
  16. 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

20. 有效的括号1次串和数组

题解思路:

  1. /**
  2. * @param {string} s
  3. * @return {boolean}
  4. */
  5. var isValid = function (s) {
  6. // 如果串是奇数长度,不符合题目要求,直接false
  7. if (s.length === 1) {
  8. return false;
  9. }
  10. // 用map保存括号对
  11. const pairs = new Map([
  12. [")", "("],
  13. ["]", "["],
  14. ["}", "{"],
  15. ]);
  16. // 设置一个数组做栈,栈顶为stack[stack.length-1]
  17. let stack = [];
  18. for (const ch of s) {
  19. if(pairs.has(ch)){
  20. // 下面第一个判断:当前元素为右括号,而栈中没有元素。表明s中有偶数个没有配对的右括号“()}}{}{}{}”。
  21. // 第二个判断是:栈顶不是对应的左括号。ch为“)”,而栈顶是“[”。举例s:“[)”
  22. if(!stack.length|| stack[stack.length-1] !== pairs.get(ch)){
  23. return false;
  24. }
  25. stack.pop;
  26. }else{
  27. stack.push(ch);
  28. }
  29. }
  30. return !stack.length;
  31. };

  • @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() */
  1. ---
  2. - [160. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists)
  3. - [509. 斐波那契数](https://leetcode-cn.com/problems/fibonacci-number)
  4. - [155. 最小栈](https://leetcode-cn.com/problems/min-stack)
  5. - [剑指 Offer 09. 用两个栈实队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof)
  6. - [349. 两个数组的交集](https://leetcode-cn.com/problems/intersection-of-two-arrays)
  7. - [429. N叉树的层序遍历](https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal)
  8. - [283. 移动零](https://leetcode-cn.com/problems/move-zeroes)
  9. - [232. 用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks)
  10. - [9. 回文数](https://leetcode-cn.com/problems/palindrome-number)
  11. - [148. 排序链表](https://leetcode-cn.com/problems/sort-list)
  12. - [67. 二进制求和](https://leetcode-cn.com/problems/add-binary)
  13. - [剑指 Offer 03. 数组中重复数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof)
  14. - [344. 反转字符串](https://leetcode-cn.com/problems/reverse-string)
  15. - [876. 链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list)
  16. - [1556. 千位分隔数](https://leetcode-cn.com/problems/thousand-separator)
  17. - [剑指 Offer 42. 连续子数组的最大和](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof)
  18. - [125. 验证回文串](https://leetcode-cn.com/problems/valid-palindrome)
  19. <a name="sC95t"></a>
  20. ## 常用的方法
  21. 1.
  22. > 实现数组的[浅拷贝](https://www.cnblogs.com/zhanghongkun/p/11535911.html),有2个可选参数(begin,end
  23. > 返回值:一个新数组
  24. 浅拷贝示例```javascript
  25. var nums = [1, 2, 3, 4, { name: "hello" }];
  26. var or = nums.slice();
  27. console.log(nums);
  28. or[4].name = "wuhu";
  29. console.log(or);
  30. //运行结果如下:改变or[4]对象中的name属性,结果nums的对象属性也被修改了,说明是浅拷贝,只拷贝了栈中的值
  31. //就是只拷贝了基础数据类型(存在栈中的数据),对于引用数据类型,拷贝了其地址值

image.png


  1. 判断数组中是否含有某元素,并返回该元素的下标,还可以指定开始查找的位置fromIndex(可选)。 返回值:首个被找到的元素在数组中的索引位置; 若没有找到则返回 -1


  1. js内置的对象,常与数组一起使用 has(key) get(key)


  1. 创建循环的语句,可以把of后的迭代对象中的每一个元素赋给for后面的变量。


  1. 关于事件监听中的this

普通的匿名函数中this指向触发事件的元素 箭头函数由于不会创建自己的this,它只能从作用域链的上层继承this,所以this指向全局对象window


  1. 关于定时器

    返回值是定时器ID