算法
排序算法
Bubble Sort 冒泡排序 (Time: O(n^2), Space(1))
function bubbleSort(arr){
var i, j;
var l = arr.length;
for(i=0; i<l; i++){
for(j=0; j<l-1-i; j++){
if(arr[j]>arr[j+1]){
let t = arr[j];
arr[j] = arr[j+1];
arr[j+1] = t;
}
}
}
return arr;
}
Insertion Sort 插入排序 (Time: O(n^2), Space(1)）
([ <= pivot ], pivot, [ >= pivot ]); Recursion
function insertionSort(arr){
let len = arr.length;
let i, current, prevIdx;
for(i=1; i<len; i++){
prevIdx = i-1;
current = arr[i];
while(prevIdx >= 0 && current < arr[prevIdx]){
arr[prevIdx+1] = arr[prevIdx];
prevIdx--;
}
arr[prevIdx+1] = current;
}
return arr;
}
Quick Sort 快速排序 (Time: O(n^2), Space(logn)
([ <= pivot ], pivot, [ >= pivot ]); Recursion
function quicksort(arr){
var len = arr.length;
if(len <= 1){ //
return arr;
}
var pivot = arr[Math.floor(Math.random()*len + 0)];
var left = [];
var right = [];
var mid = [];
var i;
for(i=0; i<len; i++){
if(arr[i]< pivot)
left.push(arr[i]);
else if(arr[i]> pivot){
right.push(arr[i]);
}else{
mid.push(arr[i]);
}
}
return quicksort(left).concat(mid, quicksort(right));
}
Merge Sort 合并排序 (Time: O(nlogn), Space: O(n) worst)
function mergeSort(arr){
let len = arr.length;
if(len<=1){
return arr;
}else{
let mid = Math.floor(len/2);
let left = arr.slice(0, mid);
let right = arr.slice(mid, len);
return merge(mergeSort(left), mergeSort(right));
}
}
function merge(left, right){
let res = [];
while(left.length && right.length){
if(left[0]<right[0]){
res.push(left.shift());
}else{
res.push(right.shift());
}
}
return res.concat(left, right);
}
递归与动态规划
斐波那契数列实现
1，1，2，3，5，8...
- 递归法
function fibonacci(n) {
if(n<=0) return;
if(n<3) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
- 动态规划法: 子问题函数记录结果直接使用
p[n] = p[n-1] + p[n-2]
function fibonacciDP(n) {
if(n<=0) return;
const p = [1,1];
if(n<=2) return p[n-1];
for(let i=2; i<n; i++){
p[i] = p[i-1] + p[i-2];
}
return p[n-1];
}
数据结构
树
- BFS输出
/*function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
var levelOrder = function(root) {
if(root === null) return [];
let output = [];
let data = [root];
while(data.length !== 0){
let current = data.shift();
output.push(current.val);
if(current.left){
data.push(current.left);
}
if(current.right){
data.push(current.right);
}
}
return output;
};
JS前端技术
原生Ajax
function ajaxRequest(method, data, withCookie){
let xhr = new XMLHttpRequest();
if(!!withCookie){ //允许发送Cookie
xhr.withCredentials = true;
}
let res;
//httpRequest.readyState:
/*0 - UNSENT 代理创建，尚未调用open();
1 - OPENED open()已调用;
2 - HEADERS_RECEIVED send()已调用，获得头部状态;
3 - LOADING 下载中;
4 - DONE 下载完成，responseText属性数据完整.*/
xhr.onreadystatechange = function(e){
if(this.readyState == 4 && this.status == 200){
console.log("success");
res = this.responseText;
}
}
if(method.toLowerCase() === "get"){
xhr.open("get", "http://XXX.XXX.com/", true);
xhr.send();
}
if(method.toLowerCase() === "post"){
xhr.open("post", "http://XXX.XXX.com/", true);
xhr.send(data); //data为"key=value&key2=value2"
}
return res;
}
Jsonp跨域请求
<script type="text/javascript">
let temp = document.createElement("script");
temp.type = "text/javascript";
const callback = function(res){
alert(res);
}
temp.src = "http://XXX.XXX.com/YYY?callback=callback";
</script>
数组去重
const arr = [1,1,1,2,2,3];
//1. Set转array
const arr1 = [... new Set(arr)];
//2. Array.from
const arr2 = Array.from(new Set(arr));
//3.循环加入新数组: 判断 arr3.includes(); arr3.indexOf()===-1 [time: O(n), space: O(n)]
function noDup1(arr){
let res = [];
arr.forEach((item)=>{
if(!res.includes(item)){
res.push(item);
}
});
return res;
}
//4. sort()比较相邻元素，在原数组删除 arr.splice(start, 1) [time: O(n), space: O(1)]
function noDup2(arr){
arr = arr.sort();
let i = 0;
while(i<arr.length-1){
if(arr[i]===arr[i+1]){
arr.splice(i, 1);
}else{
i++;
}
}
}
数组扁平化 flatten
/**
forEach遍历数组所有项添加到新的数组
嵌套数组递归
*/
function flatten(arr){
const res = [];
arr?.forEach((item)=>{
if(Array.isArray(item)){
res = res.push(...flatten(item));
}else{
res.push(item);
}
});
return res;
}
/**
ES2019新增flat方法: 性能最佳
flat(depth), 默认depth=1, depth为原数组（维度-1），不明确深度可用Infinity
*/
array.flat(Infinity);
/**
ES2019新增flatMap((item)=>item)
扁平化二维数组，不改变原数组
*/
arr.flatMap((item)=>item);
判断两个对象是否相同
function isEqualObj2(obj1, obj2) {
// 排除非object的值
if (typeof obj1 !== 'object' || typeof obj2 !=='object') return false;
// 两个null的情况 （typeof null === ‘object'）
if (obj1 === null && obj2 === null) return true;
// 两个object的key数量不等就直接false
if (Object.keys(obj1).length !== Object.keys(obj2).length) return false;
for (key in obj1) {
// 嵌套对象递归处理
if (typeof obj1[key] === 'object' && !!obj1[key]) {
if (typeof obj2[key] === 'object' && !!obj2[key]) {
return isEqualObj2(obj1[key], obj2[key]);
}
return false;
}
if (obj1[key] !== obj2[key]) return false;
}
return true;
}
关于JSON.stringify
JSON格式
简单值：字符串、数值（十进制）、布尔值和null（NaN, Infinity, -Infinity和undefined都会被转为null）
复合值：符合JSON格式的嵌套对象和数组
JSON内所有属性名和字符串都用双引号“”，每个对象或数组最后一个值后不能有逗号
JSON.stringify (JSON序列化)
- undefined 值、函数、Symbol值会被忽略(为null)
- 正则对象会被转化为空对象"{}"
- 忽略对象的不可遍历的属性（Enumerable为false的忽略）
第二个参数 - 传入一个数组，包含需要被转为字符串的属性名
- 传入一个方法，参数为（key, value）可对value进行处理后输出
a) 对多级嵌套进行递归处理, (参数2的方法也是递归执行)
b) 如果处理函数返回undefined或没有返回值，则该属性会被忽略
第三个参数：改善输出字符串的可读性 - 传入整数：每行属性前的空格数<= 10
- 传入字符串：每行属性前的字符串 <= 10个
给对象添加toJSON方法，JSON.stringify前会先执行对象的toJSON转换再转成字符串
特别注意：JSON.stringify() 解析循环对象的时候，会报错！需要try catch！！
对象深拷贝 deepClone
//循环拷贝
function deepClone(obj){
if(typeof obj != "object"){
return obj;
}else{
let newObj={};
for(let k in obj){
if(typeof obj[k] != "object"){
newObj[k] = obj[k];
}else{
newObj[k] = deepClone(obj[k]);
}
}
return newObj;
}
}
//JSON转换：将object序列化为string, 再反序列化为新的object
// 保证obj 没有循环引用问题，obj内的值不设计JSON.stringify说明的那些问题
let objClone = JSON.parse(JSON.stringify(obj));
防抖 debounce (一段时间不触发事件才执行一次handle函数)
function debounce(fn, wait = 1000){
let timer = null;
return function(){
let _this = this;
if(timer){
timer = null;
}
timer = setTimeout(()=>{
fn.apply(_this, arguments);
}, wait);
}
}
引申：clearTimeout(timer) 只是停止了回调函数定期执行，timer依旧存在，if(timer) 内依旧执行； 而timer = null释放了内存， (timer) 为false。
节流 throttle（一段时间内只执行一次handle函数）
function throttle(fn, wait = 1000){
let canRun = true;
return function(){
let _this = this;
if(canRun){
setTimeout(()=>{
fn.apply(_this, arguments);
canRun = true;
}, wait);
canRun = false;
}
}
}
按秒输出0，1，2，3，4，5
//1: let 块级独立作用域
for(let i=0; i<=5; i++){
setTimeout(()=>{
console.log(i);
}, i * 1000);
}
//2：立即执行闭包函数，定义后立即执行，将变量包裹成局部变量。
for(var i=0; i<=5; i++){
(function (j){
setTimeout(()=>{
console.log(j);
}, j*1000)
})(i)
}
//3: setTimeout第三个参数，作为中间函数执行时的参数
for(var i=0; i<=5; i++){
setTimeout((j)=>{
console.log(j);
}, i*1000, i);
}
函数柯里化curryadd(1)(2)(3)
function curryadd(a){
return function(b){
return function(c){
return a+b+c;
}
}
}
new实现:
- 新建空对象
- proto指向构造函数的prototype
- 新对象this绑定为构造函数的this
- 执行构造函数返回对象。**
function newFn(fn){
if(typeof fn !== "function"){
throw "第一个参数要为function";
}else{
let newObj = {};
newObj._proto_ = fn.prototype;
let args = [...arguments].slice(1);
let result = fn.apply(newObj, args);
const isObj = typeof result === "object" && result !== null;
const isFunc = typeof result === "function";
return isObj || isFunc ? result : newObj;
}
}
instanceof 实现：
typeof原理：根据JS底层机器码前三位来获取类型信息
000：对象
010：浮点数
100：字符串
110：布尔
1：整数
null在JS设计之初定为全0，因此typeof根据前三位000，判断null为"object"
typeof 可以判断基本类型number, string, boolean, symbol, bigint, undefined 和object, function (class也是function)
介于typeof无法判断具体的object类型，只能用Object.prototype.toString.call()来获取具体的object类型
incetanceof 原理
A instanceof B：检查A的原型链上是否存在B.prototype, 向上查找A的原型链，直到null。
const myInstanceof = (left, right) => {
// 首先得满足left有__proto__属性，right为callable的函数
if ((typeof left !== "object" && typeof left !== "function")
|| left === null
|| typeof right !== "function") {
return false;
}
const rightPrototype = right.prototype;
let leftProto= left.__proto__;
while(true) {
if(leftProto === null) {
return false;
}
if(leftProto === rightPrototype) {
return true;
}
leftProto = leftProto.__proto__;
}
}
改变原方法中的this指向：call、apply、bind
call实现
- 接收一个以上任意数量的参数
- 第一个参数是函数想要作用的对象
Function.prototype.call2 = function (ctx) {
if (typeof this !== 'function') {
throw new Error('Function undefined');
}
ctx = ctx || window;
ctx.fn = this;
const args = [...arguments].slice(1);
const res = ctx.fn(...args);
delete ctx.fn;
return res;
}
apply实现
- 接收一到两个参数
- 第一个参数是函数想要作用的对象
- 第二个参数是包含所有剩余参数的Array
Function.prototype.apply2 = function(target, arr){
var tar = (target===null) ? window : target;
tar.fn = this;
var result;
if(!arr){
result = tar.fn();
}else{
result = tar.fn(...arr);
}
delete tar.fn;
return result;
};
bind实现
- 接收一个以上任意数量的参数
- 第一个参数是函数的目标作用对象
- call和apply直接返回调用函数的结果，bind只返回改变作用对象后的函数
Function.prototype.bind2 = function (ctx) {
const fn = this;
const args = [...arguments].slice(1);
const F = function () {};
const fBind = function () {
return fn.apply(this instanceof fBind ? this : ctx, args.concat(...arguments))
};
if (fn.prototype) {
F.prototype = fn.prototype;
}
fBind.prototype = new F();
return fBind;
}
