- 手写题
- 算法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的this
const 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 实例中的回调函数中即可.
```javascript
Promise.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 得到的id
let timer = null;
// 这里返回的函数是每次用户实际调用的防抖函数
// 如果已经设定过定时器了就清空上一次的定时器
// 开始一个定时器,延迟执行用户传入的方法
return function () {
// 保存函数调用时的this
let 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,记录最长子串长度len
let 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)串和数组
题解```javascript
var 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) {
// 如果串是奇数长度,不符合题目要求,直接false
if (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)
> 返回值:一个新数组
浅拷贝示例```javascript
var 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