# 编程题
# 方法库部分
# 实现防抖函数(debounce)
const debounce = (fn, delay) => {
let timer = null;
return (...args) => {
clearTimeout(timer);
timer = setTimeout(() => {
fn.apply(this, args);
}, delay);
};
};
underscore版本:
_.debounce = function(func, wait, immediate) {
var timeout, result;
var later = function(context, args) {
timeout = null;
if (args) result = func.apply(context, args);
};
var debounced = restArguments(function(args) {
if (timeout) clearTimeout(timeout);
if (immediate) {
var callNow = !timeout;
timeout = setTimeout(later, wait);
if (callNow) result = func.apply(this, args);
} else {
timeout = _.delay(later, wait, this, args);
}
return result;
});
debounced.cancel = function() {
clearTimeout(timeout);
timeout = null;
};
return debounced;
};
lodash版本
import isObject from './isObject.js'
import root from './.internal/root.js'
function debounce(func, wait, options) {
let lastArgs,
lastThis,
maxWait,
result,
timerId,
lastCallTime
let lastInvokeTime = 0
let leading = false
let maxing = false
let trailing = true
const useRAF = (!wait && wait !== 0 && typeof root.requestAnimationFrame === 'function')
if (typeof func !== 'function') {
throw new TypeError('Expected a function')
}
wait = +wait || 0
if (isObject(options)) {
leading = !!options.leading
maxing = 'maxWait' in options
maxWait = maxing ? Math.max(+options.maxWait || 0, wait) : maxWait
trailing = 'trailing' in options ? !!options.trailing : trailing
}
function invokeFunc(time) {
const args = lastArgs
const thisArg = lastThis
lastArgs = lastThis = undefined
lastInvokeTime = time
result = func.apply(thisArg, args)
return result
}
function startTimer(pendingFunc, wait) {
if (useRAF) {
root.cancelAnimationFrame(timerId)
return root.requestAnimationFrame(pendingFunc)
}
return setTimeout(pendingFunc, wait)
}
function cancelTimer(id) {
if (useRAF) {
return root.cancelAnimationFrame(id)
}
clearTimeout(id)
}
function leadingEdge(time) {
lastInvokeTime = time
timerId = startTimer(timerExpired, wait)
return leading ? invokeFunc(time) : result
}
function remainingWait(time) {
const timeSinceLastCall = time - lastCallTime
const timeSinceLastInvoke = time - lastInvokeTime
const timeWaiting = wait - timeSinceLastCall
return maxing
? Math.min(timeWaiting, maxWait - timeSinceLastInvoke)
: timeWaiting
}
function shouldInvoke(time) {
const timeSinceLastCall = time - lastCallTime
const timeSinceLastInvoke = time - lastInvokeTime
return (lastCallTime === undefined || (timeSinceLastCall >= wait) ||
(timeSinceLastCall < 0) || (maxing && timeSinceLastInvoke >= maxWait))
}
function timerExpired() {
const time = Date.now()
if (shouldInvoke(time)) {
return trailingEdge(time)
}
timerId = startTimer(timerExpired, remainingWait(time))
}
function trailingEdge(time) {
timerId = undefined
if (trailing && lastArgs) {
return invokeFunc(time)
}
lastArgs = lastThis = undefined
return result
}
function cancel() {
if (timerId !== undefined) {
cancelTimer(timerId)
}
lastInvokeTime = 0
lastArgs = lastCallTime = lastThis = timerId = undefined
}
function flush() {
return timerId === undefined ? result : trailingEdge(Date.now())
}
function pending() {
return timerId !== undefined
}
function debounced(...args) {
const time = Date.now()
const isInvoking = shouldInvoke(time)
lastArgs = args
lastThis = this
lastCallTime = time
if (isInvoking) {
if (timerId === undefined) {
return leadingEdge(lastCallTime)
}
if (maxing) {
timerId = startTimer(timerExpired, wait)
return invokeFunc(lastCallTime)
}
}
if (timerId === undefined) {
timerId = startTimer(timerExpired, wait)
}
return result
}
debounced.cancel = cancel
debounced.flush = flush
debounced.pending = pending
return debounced
}
export default debounce
# 实现节流函数(throttle)
const throttle = (fn, delay = 500) => {
let flag = true;
return (...args) => {
if (!flag) return;
flag = false;
setTimeout(() => {
fn.apply(this, args);
flag = true;
}, delay);
};
};
underscore版本:
_.throttle = function(func, wait, options) {
var timeout, context, args, result;
var previous = 0;
if (!options) options = {};
var later = function() {
previous = options.leading === false ? 0 : _.now();
timeout = null;
result = func.apply(context, args);
if (!timeout) context = args = null;
};
var throttled = function() {
var now = _.now();
if (!previous && options.leading === false) previous = now;
var remaining = wait - (now - previous);
context = this;
args = arguments;
if (remaining <= 0 || remaining > wait) {
if (timeout) {
clearTimeout(timeout);
timeout = null;
}
previous = now;
result = func.apply(context, args);
if (!timeout) context = args = null;
} else if (!timeout && options.trailing !== false) {
timeout = setTimeout(later, remaining);
}
return result;
};
throttled.cancel = function() {
clearTimeout(timeout);
previous = 0;
timeout = context = args = null;
};
return throttled;
};
lodash版本:
import debounce from './debounce.js'
import isObject from './isObject.js'
function throttle(func, wait, options) {
let leading = true
let trailing = true
if (typeof func !== 'function') {
throw new TypeError('Expected a function')
}
if (isObject(options)) {
leading = 'leading' in options ? !!options.leading : leading
trailing = 'trailing' in options ? !!options.trailing : trailing
}
return debounce(func, wait, {
leading,
trailing,
'maxWait': wait
})
}
export default throttle
# 实现lazy-load懒加载
let imgs=document.querySelectorAll('img');
let clientHeight=window.innerHeight || document.documentElement.clientHeight || document.body.clientHeight
function lazyLoad(){
let scrollTop=window.pageYOffset || document.documentElement.scrollTop || document.body.scrollTop;
for(let i=0;i<imgs.length;i++){
let x=clientHeight + scrollTop-imgs[i].offsetTop;
if(x>0 && x<clientHeight+imgs[i].height){
imgs[i].src=imgs[i].getAttribute('data')
}
}
}
# 实现拖拽
window.onload=function(){
let drag=document.getElementById('box');
drag.onmousedown=function(e){
let e = e || window.event;
let diffX=e.clientX-drag.offsetLeft;
let diffY=e.clientY-drag.offsetTop;
drag.onmousemove=function(e){
let left=e.clientX-diffX;
let top=e.clientY-diffY;
if(left<0){
left=0;
}else if(left>window.innerWidth-drag.offsetWidth){
left=window.innerWidth-drag.offsetWidth;
}
if(top<0){
top=0;
}else if(top>window.innerHeight-drag.offsetHeight){
top=window.innerHeight-drag.offsetHeight
}
drag.style.left=left+'px';
drag.style.top=top+'px';
}
drag.onmouseup=function(e){
this.onmousemove=null;
this.onmouseup=null;
}
}
}
# 实现基于Promise的ajax函数
function ajax(url,method,fn,type){
return new Promise((resolve,reject)=>{
var xhr=new XMLHttpRequest();
xhr.onreadystatechange=function(){
if(xhr.readyState==4){
if(xhr.status==200){
//var result=xhr.responseText;
//fn(result);
resolve(JSON.parse(xhr.responseText).count);
}
}
};
xhr.open(method,url+"?"+type,true);
if(method=="post"){
xhr.setRequestHeader("Content-Type","application/x-www-form-urlencoded");
}
if(method=="get"){
xhr.send(null);
}else if(method=="post"){
xhr.send(type);
}
}
)
}
# 实现一个浅克隆
function clone(obj){
let newObj={};
for(let key in obj){
newObj[key]=obj[key];
}
return newObj;
}
# 实现一个深克隆(deepclone)
简版：
function clone(obj){
if(obj===null){
return null
};
if({}.toString.call(obj)==='[object Array]'){
let newArr=[];
newArr=obj.slice();
return newArr;
};
let newObj={};
for(let key in obj){
if(typeof obj[key]!=='object'){
newObj[key]=obj[key];
}else{
newObj[key]=clone(obj[key]);
}
}
}
完整版：
const clone = parent => {
const isType = (obj, type) => {
if (typeof obj !== "object") return false;
const typeString = Object.prototype.toString.call(obj);
let flag;
switch (type) {
case "Array":
flag = typeString === "[object Array]";
break;
case "Date":
flag = typeString === "[object Date]";
break;
case "RegExp":
flag = typeString === "[object RegExp]";
break;
default:
flag = false;
}
return flag;
};
const getRegExp = re => {
var flags = "";
if (re.global) flags += "g";
if (re.ignoreCase) flags += "i";
if (re.multiline) flags += "m";
return flags;
};
const parents = [];
const children = [];
const _clone = parent => {
if (parent === null) return null;
if (typeof parent !== "object") return parent;
let child, proto;
if (isType(parent, "Array")) {
child = [];
} else if (isType(parent, "RegExp")) {
child = new RegExp(parent.source, getRegExp(parent));
if (parent.lastIndex) child.lastIndex = parent.lastIndex;
} else if (isType(parent, "Date")) {
child = new Date(parent.getTime());
} else {
proto = Object.getPrototypeOf(parent);
child = Object.create(proto);
}
const index = parents.indexOf(parent);
if (index != -1) {
return children[index];
}
parents.push(parent);
children.push(child);
for (let i in parent) {
child[i] = _clone(parent[i]);
}
return child;
};
return _clone(parent);
};
# 实现一个深冻结
function deepFreeze(object){
let propNames=Object.getOwnPropertyNames(object);
for(let name of propNames){
let value=object[name];
object[name]=value && typeof value === 'object' ?
deepFreeze(value) : value;
}
return Object.freeze(object);
}
# 实现一个深比较
function deepCompare(a,b){
if(a===null || typeof a!=='object' || b===null || typeof b!=='object'){
return a===b
}
const propsA=Object.getOwnPropertyDescriptors(a);
const propsB=Object.getOwnPropertyDescriptors(b);
if(Object.keys(propsA).length!==Object.keys(propsB).length){
return false
}
return Object.keys(propsA).every(
key=>deepCompare(a[key],b[key])
)
}
# 解析URL Params为对象
简版
function parseQueryString(url){
let search=url.split('?')[1];
let strs=search.split('&');
let params={};
for(let str of strs){
let arr=str.split('=');
params[arr[0]]=isNaN(arr[1])?arr[1]:Number(arr[1]);
}
return params;
}
完整版
function parseParam(url) {
const paramsStr = /.+\?(.+)$/.exec(url)[1];
const paramsArr = paramsStr.split('&');
let paramsObj = {};
paramsArr.forEach(param => {
if (/=/.test(param)) {
let [key, val] = param.split('=');
val = decodeURIComponent(val);
val = /^\d+$/.test(val) ? parseFloat(val) : val;
if (paramsObj.hasOwnProperty(key)) {
paramsObj[key] = [].concat(paramsObj[key], val);
} else {
paramsObj[key] = val;
}
} else {
paramsObj[param] = true;
}
})
return paramsObj;
}
考虑深度集合
function parse(str){
return str.split('&').reduce((o,kv)=>{
const [key,value]=kv.split('=');
if(!value){
return o
}
deep_set(o,key.split(/[\[\]]/g).filter(x=>x),value);
return o
},{})
}
function deep_set(o,path,value){
let i=0;
for(;i<path.length-1;i++){
if(o[path[i]]===undefined){
if(path[i+1].match(/^\d+$/)){
o[path[i]]=[]
}else{
o[path[i]]={}
}
}
o=o[path[i]]
}
o[path[i]]=decodeURIComponent(value)
}
# 为普通对象添加迭代属性
let obj={};
Object.defineProperty(obj,Symbol.iterator,{
enumerable:false,
writable:false,
configurable:true,
value:function(){
let o=this;
let idx=0;
let ks=Object.keys(o);
return {
next:function(){
return {
value:o[ks[idx++]],
done:(idx>ks.length)
}
}
}
}
})
# 输出字符串中字符的个数
推荐
let str='helloworld';
let dict={};
for(let i=0;i<str.length;i++){
if(dict[str[i]]===undefined){
dict[str[i]]=1;
}else{
dict[str[i]]+=1;
}
}
# 编写一个方法 求一个字符串的字节长度
function GetBytes(str){
var len = str.length;
var bytes = len;
for(var i=0; i<len; i++){
if (str.charCodeAt(i) > 255) bytes++;
}
return bytes;
}
# 查找字符串中出现最多的字符和个数
let str = "abcabcabcbbccccc";
let num = 0;
let char = '';
str = str.split('').sort().join('');
let re = /(\w)\1+/g;
str.replace(re,($0,$1) => {
if(num < $0.length){
num = $0.length;
char = $1;
}
});
console.log(`字符最多的是${char}，出现了${num}次`);
# 字符串查找
a='34';b='1234567'; // 返回 2
a='35';b='1234567'; // 返回 -1
a='355';b='12354355'; // 返回 5
isContain(a,b);
function isContain(a, b) {
for (let i in b) {
if (a[0] === b[i]) {
let tmp = true;
for (let j in a) {
if (a[j] !== b[~~i + ~~j]) {
tmp = false;
}
}
if (tmp) {
return i;
}
}
}
return -1;
}
# 实现字符串翻转
var arr=str.split('');
var newArr=[];
for(var i=0;i<arr.length;i++){
newArr[i]=arr[arr.length-i-1];
}
var newStr=newArr.join('')
console.log(str0);
var newStr='';
for(var i=0;i<str.length;i++){
newStr+=str.charAt(str.length-i-1);
}
console.log(newStr);
var newStr=str.split("").reverse().join("");
console.log(newStr);
var arr=str.split('');
var obj=Array.from(new Set([...arr]));
var newStr='';
for(i of obj){
newStr+=obj[arr.length-i];
}
console.log(newStr)
var arr=str.split('');
var newArr=[];
while(arr.length>0){
newArr.push(arr.pop())
};
var newStr=newArr.join("");
console.log(newStr)
# 实现字符串的散列函数
function h_str(str,M){
return [...str].reduce((hash,c)=>{
hash=(31*hash+c.charCodeAt(0))%M
return hash
},0)
}
# 实现数组去重
推荐
let dict={},
result=[],
j=0;
for(let i=0;i<arr.length;i++){
dict[arr[i]]=1;
}
for(result[j++] in dict);
var newArr=Array.from(new Set(arr));
console.log(newArr);
for(var i=0;i<arr.length;i++){
for(j=i+1;j<arr.length;j++){
if(arr[i]==arr[j]){
arr.splice(j,1);
j--;
}
}
}
console.log(arr);
var newArr=[];
for(var i=0;i<arr.length;i++){
if(newArr.indexOf(arr[i])===-1){
newArr.push(arr[i])
}
}
console.log(newArr);
var arr=arr.sort();
var newArr=[arr[0]];
for(var i=1;i<arr.length;i++){
if(arr[i]!==arr[i-1]){
newArr.push(arr[i])
}
}
console.log(newArr);
var newArr=[];
var obj={};
for(var i=0;i<arr.length;i++){
if(!obj[arr[i]]){
newArr.push(arr[i]);
obj[arr[i]]=1
}else{
obj[arr[i]]++
}
}
console.log(newArr);
var newArr=[];
for(var i=0;i<arr.length;i++){
if(!newArr.includes(arr[i])){//检测数组是否有某个值
newArr.push(arr[i]);
}
}
console.log(newArr);
var obj={};
var newArr=arr.filter((item,index,arr)=>{
return obj.hasOwnProperty(typeof item+item)?false:(obj[typeof item+item]=true)
})
console.log(arrM6);
arr.sort(function(a,b){
return a-b;
})
function loop(index){
if(index>=1){
if(arr[index]===arr[index-1]){
arr.splice(index,1);
}
loop(index-1)
}
}
loop(arr.length-1);
console.log(arr);
var map=new Map();
var newArr=[];
for(var i=0;i<arr.length;i++){
if(map.has(arr[i])){
map.set(arr[i],true);
}else{
map.set(arr[i],false);
newArr.push(arr[i]);
}
}
console.log(newArr);
arr=arr.reduce((prev,cur)=>prev.includes(cur)?prev:[...prev,cur],[]);
console.log(arr);
```
```
var newArr=[...new Set(arr)];
console.log(newArr);
# 实现合成函数compose
const compose =(...args)=>args.reduce((prev,current)=>(...values)=>prev(current(...values)));
# 实现旋转数组
function rotate(nums, k) {
for (let i = 0;i < k; i++) {
nums.unshift(nums.pop());
}
};
# 实现浮点数的散列函数
function binary_value(val){
const farr=new Float32Array(1)
farr[0]=val
const intBytes=new Int8Array(farr.buffer)
const view=new DataView(intBytes.buffer)
return view.getUnit32()
}
k=>binary_value(k)%M
# 实现千位分隔符
function parseToMoney(num) {
num = parseFloat(num.toFixed(3));
let [integer, decimal] = String.prototype.split.call(num, '.');
integer = integer.replace(/\d(?=(\d{3})+$)/g, '$&,');
return integer + '.' + (decimal ? decimal : '');
}
function parseToMoney(str){
let re = /(?=(?!\b)(\d{3})+$)/g;
return str.replace(re,',');
}
# 判断是否是电话号码
function isPhone(tel) {
var regx = /^1[34578]\d{9}$/;
return regx.test(tel);
}
# 验证是否是邮箱
function isEmail(email) {
var regx = /^([a-zA-Z0-9_\-])+@([a-zA-Z0-9_\-])+(\.[a-zA-Z0-9_\-])+$/;
return regx.test(email);
}
# 验证是否是身份证
function isCardNo(number) {
var regx = /(^\d{15}$)|(^\d{18}$)|(^\d{17}(\d|X|x)$)/;
return regx.test(number);
}
# 实现一个函数柯里化
const curry=(fn,arr=[])=>(...args)=>(
arg=>arg.length===fn.length
? fn(...arg)
: curry(fn,arg)
)([...arr,...args])
# 实现一个函数反柯里化
const unCurrying=(fn)=>{
return (...args)=>{
return fn.call(...args);
}
}
# 实现数组扁平化
递归
function flatten(arr){
return [].concat(
...arr.map(x=>Array.isArray(x)?flatten(x):x)
)
}
递归，可以用for去展平拿到想要的第几项，可以忽略后续的非展平项，保证性能
function *flatten(arr){
for(let i=0;i<arr.length;i++){
if(Array.isArray(arr[i])){
yield * flatten(arr[i])
}else{
yield arr[i]
}
}
}
堆栈实现非递归
function *flatten(arr){
let stack=arr.slice.reverse();
while(stack.length){
const item=stack.pop();
if(item.constructor===Array){
stack=stack.concat(item)
}else{
yield item
}
}
}
# 判断是否是回文数
function isPalindrome(str) {
str = str.replace(/\W/g, '').toLowerCase();
return (str == str.split('').reverse().join(''));
}
# 实现isArray()方法 判断是否为数组
Array.myIsArray=function(o){
return Object.prototype.toString.call(Object(o)) === '[object Array]'
}
# 实现isContain()方法，判断是否包含该字符串
function isContain(a, b) {
for (let i in b) {
if (a[0] === b[i]) {
let tmp = true;
for (let j in a) {
if (a[j] !== b[~~i + ~~j]) {
tmp = false;
}
}
if (tmp) {
return i;
}
}
}
return -1;
}
# 实现isNegZero函数
function isNegZero(n){
n=Number(n);
return (n === n) && (1/n === -Infinity)
}
# 实现Object.is()函数
Object.is=function(v1,v2){
if(v1===0 && v2===0){
return 1/v1 === 1/v2;
}
if(v1!==v1){
return v2!==v2;
}
return v1 === v2;
}
# 原理部分
# 实现Event(event bus)
class EventEmitter {
constructor() {
this._events = this._events || new Map();
this._maxListeners = this._maxListeners || 10;
}
}
EventEmitter.prototype.emit = function(type, ...args) {
let handler;
handler = this._events.get(type);
if (args.length > 0) {
handler.apply(this, args);
} else {
handler.call(this);
}
return true;
};
EventEmitter.prototype.addListener = function(type, fn) {
if (!this._events.get(type)) {
this._events.set(type, fn);
}
};
EventEmitter.prototype.emit = function(type, ...args) {
let handler;
handler = this._events.get(type);
if (Array.isArray(handler)) {
for (let i = 0; i < handler.length; i++) {
if (args.length > 0) {
handler[i].apply(this, args);
} else {
handler[i].call(this);
}
}
} else {
if (args.length > 0) {
handler.apply(this, args);
} else {
handler.call(this);
}
}
return true;
};
EventEmitter.prototype.addListener = function(type, fn) {
const handler = this._events.get(type);
if (!handler) {
this._events.set(type, fn);
} else if (handler && typeof handler === "function") {
this._events.set(type, [handler, fn]);
} else {
handler.push(fn);
}
};
EventEmitter.prototype.removeListener = function(type, fn) {
const handler = this._events.get(type);
if (handler && typeof handler === "function") {
this._events.delete(type, fn);
} else {
let position;
for (let i = 0; i < handler.length; i++) {
if (handler[i] === fn) {
position = i;
} else {
position = -1;
}
}
if (position !== -1) {
handler.splice(position, 1);
if (handler.length === 1) {
this._events.set(type, handler[0]);
}
} else {
return this;
}
}
};
简版
class EventEmitter{
constructor(){
this._events={};
}
on(type,listener){
let listeners=this._events[type];
if(listeners){
listeners.push(listener)
}else{
this._events[type]=[listener];
}
}
emit(type){
let listeners=this._events[type];
let args=Array.from(arguments).slice(1);
listeners.forEach(listener=>listener(...args));
}
}
# 实现一个Writable Stream?
var Writable = require('stream').Writable;
var util = require('util');
function MyWritable(options) {
Writable.call(this, options);
} // 构造函数
util.inherits(MyWritable, Writable); // 继承自Writable
MyWritable.prototype._write = function(chunk, encoding, callback) {
console.log("被写入的数据是:", chunk.toString()); // 此处可对写入的数据进行处理
callback();
};
process.stdin.pipe(new MyWritable()); // stdin作为输入源，MyWritable作为输出源
# 实现instanceOf
function instance_of(L, R) {
var O = R.prototype;
L = L.__proto__;
while (true) {
if (L === null) return false;
if (O === L)
return true;
L = L.__proto__;
}
}
# 实现一个new
function _new(P){
let o={};
let arg=Array.prototype.slice.call(arguments,1);
o.__proto__=P.prototype;
P.apply(o,arg);
return o;
}
# 实现一个const
var __const = function __const (data, value) {
window.data = value
Object.defineProperty(window, data, {
enumerable: false,
configurable: false,
get: function () {
return value
},
set: function (data) {
if (data !== value) {
throw new TypeError('Assignment to constant variable.')
} else {
return value
}
}
})
}
# 实现一个extends
function myExtends(sourceObj,targetObj){
for(let key in sourceObj){
if(!(key in targetObj)){
targetObj[key]=sourceObj[key];
}
}
return targetObj;
}
# 实现一个call
Function.prototype.myCall = function(context) {
context.fn = this;
let args = [];
for (let i = 1, len = arguments.length; i < len; i++) {
args.push(arguments[i]);
}
context.fn(...args);
let result = context.fn(...args);
delete context.fn;
return result;
};
# 实现一个apply
Function.prototype.myapply = function(context, arr) {
var context = Object(context) || window;
context.fn = this;
var result;
if (!arr) {
result = context.fn();
} else {
var args = [];
for (var i = 0, len = arr.length; i < len; i++) {
args.push("arr[" + i + "]");
}
result = eval("context.fn(" + args + ")");
}
delete context.fn;
return result;
};
# 实现bind
if (!Function.prototype.bind) {
Function.prototype.bind = function(oThis) {
if (typeof this !== 'function') {
throw new TypeError('Function.prototype.bind - what is trying to be bound is not callable');
}
var aArgs = Array.prototype.slice.call(arguments, 1),
fToBind = this,
fNOP = function() {},
fBound = function() {
return fToBind.apply(this instanceof fBound
? this
: oThis,
aArgs.concat(Array.prototype.slice.call(arguments)));
};
if (this.prototype) {
fNOP.prototype = this.prototype;
}
fBound.prototype = new fNOP();
return fBound;
};
}
# 模拟Object.create
function create(proto) {
function F() {}
F.prototype = proto;
return new F();
}
# 实现一个软绑定
if(!Function.prototype.softBind){
Function.prototype.softBind=function(obj){
let fn=this;
let curried=[].slice.call(arguments,1);
let bound=function(){
return fn.apply(
(!this || this===(window || global))?obj:this,
curried.concat.apply(curried,arguments)
);
};
bound.prototype=Object.create(fn.prototype);
return bound;
}
}
# 实现super关键字
Object.prototype.mysuper = function(){
var caller = arguments.callee.caller,
name;
for(var i in this){
if(this[i] === caller){
name = i;
break;
}
}
__proto = this.__proto__ || this.constructor.prototype;
try{
return __proto[name].apply(this, arguments);
}catch(e){
alert(name + ' is undefined.');
}
}
# 实现Object.create()
function create(proto) {
function F() {}
F.prototype = proto;
return new F();
}
# 实现类的继承
function Parent(name) {
this.parent = name
}
Parent.prototype.say = function() {
console.log(`${this.parent}: 你打篮球的样子像kunkun`)
}
function Child(name, parent) {
Parent.call(this, parent)
this.child = name
}
Child.prototype = Object.create(Parent.prototype);
Child.prototype.say = function() {
console.log(`${this.parent}好，我是练习时长两年半的${this.child}`);
}
Child.prototype.constructor = Child;
var parent = new Parent('father');
parent.say();
var child = new Child('cxk', 'father');
child.say();
# 实现rem原理
function setRem(){
let doc=document.documentElement;
let width=doc.getBoundingClientRect().width;
let rem=width/75;
doc.style.fontSize=rem+'px'
}
addEventListener('resize',setRem)
# 实现一个双向数据绑定
let arrayProto=Array.prototype;
let proto=Object.create(arrayProto);
['push','unshift','splice','reverse','sort','shift','pop'].forEach(method=>{
proto[method]=function(...args){
let inserted;
switch(method){
case 'push':
case 'unshift':
inserted=args
break;
case 'splice':
inserted = args.slice(2);
default:
break;
}
ArrayObserver(inserted);
arrayProto[method].call(this,...args)
}
})
function ArrayObserver(obj){
for(let i=0;i<obj.length;i++){
let item=obj[i];
observer(item);
}
}
function observer(obj){
if(typeof obj !== 'object' || obj == null){
return obj;
}
if(Array.isArray(obj)){
Object.setPrototypeOf(obj,proto)
ArrayObserver(obj);
}else{
for (let key in obj){
defineReactive(obj,key,obj[key])
}
}
}
function defineReactive(obj,key,value){
observer(value); // 递归创建
get(){
return value;
},
set(newValue){
if(value!==newValue){
observer(newValue);
value=newValue;
}
}
}
# 实现CommonJS模块化
const path=require('path');
const fs=require('fs');
const vm=require('vm');
function Module(id){
this.id=id;
this.exports={};//模块的结果
}
Module.wrapper=[
'(function(exports,module,require,__filename,__dirname){'
,
'})'
]
//静态方法
Module._extensions={
'.js'(module){//js需要将exports传给用户 用户自己解析
let script=fs.readFileSync(module.id,'utf8');
let fnStr=Module.wrapper[0]+script+Module.wrapper[1];
let fn=vm.runInThisContext(fnStr);//让字符串执行js代码
//第一个参数改变this指向 module module.exports
fn.call(module.exports,module,module.exports,req,module.id,path.dirname(module.id));
},
'.json'(module){
let script=fs.readFileSync(module.id,'utf8');
module.exports=JSON.parse(script)
}
}
//给你一个相对路径 解析成绝对路径
Module.resolveFileName=function(filename){
// 1) 把相对路径转化为绝对路径 默认会先判断一下是否是绝对路径
let absPath=path.resolve(__dirname,filename);
let flag=fs.existsSync(absPath);//判断文件是否存在 异步方法被废弃
let current=absPath; //默认是当前路径
if(!flag){
let keys=Object.keys(Module._extensions);
for(let i=0;i<keys.length;i++){
current=absPath+keys[i];//当前找到的文件路径
flag=fs.existsSync(current);
if(flag){
break;
}else{
current=null;
}
}
}
if(!current){ // 如果没有 说明加了后缀文件还是不存在
throw new Error('文件不存在')
}
return current;
}
Module.prototype.load=function(){
//模块加载就是读取文件的内容
let ext =path.extname(this.id);
Module._extensions[ext](this);//根据不同的路径处理不同的方法
}
Module._cache={};
function req(filename){
//自己实现了一个require方法
let current=Module.resolveFileName(filename);
if(Module._cache[current]){
return Module._cache[current].exports;
}
let module=new Module(current);
Module._cache[current]=module;
module.load();
return module.exports;
}
# 实现jwt
const crypto = require('crypto');
function encode(payload, key) {
let header = { type: 'JWT', alg: 'sha256' };//声明类型和算法
var segments = [];//声明一个数组
segments.push(base64urlEncode(JSON.stringify(header)));//对header进行base64
segments.push(base64urlEncode(JSON.stringify(payload)));//对负载进行base64
segments.push(sign(segments.join('.'), key));//加入签名
return segments.join('.');
}
function sign(input, key) {
return crypto.createHmac('sha256', key).update(input).digest('base64');
}
function decode(token, key) {
var segments = token.split('.');
var headerSeg = segments[0];
var payloadSeg = segments[1];
var signatureSeg = segments[2];
var header = JSON.parse(base64urlDecode(headerSeg));
var payload = JSON.parse(base64urlDecode(payloadSeg));
if (signatureSeg != sign([headerSeg, payloadSeg].join('.'), key)) {
throw new Error('verify failed');
}
if (payload.exp && Date.now() > payload.exp * 1000) {
throw new Error('Token expired');
}
return payload;
}
function base64urlEncode(str) {
return new Buffer(str).toString('base64');
}
function base64urlDecode(str) {
return new Buffer(str, 'base64').toString();
}
module.exports = {
encode,
decode
}
# 实现Redux
// bindActionCreator
export default function bindActionCreator(actions,dispatch){
let newActions={};
for(let key in actions){
newActions[key]=()=>dispatch(actions[key].apply(null,arguments));
}
return newActions;
}
// combineReducers
export default combineReducers=reducers=>(state={},action)=>Object.keys(reducers).reduce((currentState,key)=>{
currentState[key]=reducers[key](state[key],action);
return currentState;
},{});
// createStore
export default function createStore(reducer,enhancer){
if(typeof enhancer !== 'undefined'){
return enhancer(createStore)(reducer);
}
let state=null;
const listeners=[];
const subscribe=(listener)=>{
listeners.push(listener);
}
const getState=()=>state;
const dispatch=(action)=>{
state=reducer(state,action);
listeners.forEach((listener)=>listener())
};
dispatch({});
return {getState,dispatch,subscribe}
}
// applyMiddleware
export default function applyMiddleware(...middlewares){
return (createStore)=>(reducer)=>{
const store=createStore(reducer);
let dispatch=store.dispatch;
let chain=[];
const middlewareAPI={
getState:store.getState,
dispatch:(action)=>dispatch(action)
}
chain=middlewares.map(middleware=>middleware(middlewareAPI));
dispatch=compose(...chain)(store.dispatch);
return {
...store,
dispatch
}
}
}
// compose
export default function compose(...funcs){
return funcs.reduce((a,b)=>(...args)=>a(b(...args)));
}
# 实现一个简单路由
class Route{
constructor(){
this.routes={};
this.currentHash='';
this.freshRoute=this.freshRoute.bind(this);
window.addEventListener('load',this.freshRoute,false);
window.addEventListener('hashchange',this.freshRoute,false);
}
storeRoute(path,cb){
this.routes[path]=cb || function(){}
}
freshRoute(){
this.currentHash=location.hash.slice(1) || '/';
this.routes[this.currentHash]()
}
}
# 实现Promise
完整版
const PENDING='pending';
const FULFILLED='fulfilled';
const REJECTED='rejected';
function MyPromise(fn){
const self=this;
self.value=null;
self.error=null;
self.status=PENDING;
self.onFulfilledCallbacks=[];
self.onRejectedCallbacks=[];
function resolve(value){
if(value instanceof MyPromise){
return value.then(resolve,reject);
}
if(self.status===PENDING){
setTimeout(()=>{
self.status=FULFILLED;
self.value=value;
self.onFulfilledCallbacks.forEach((callback)=>callback(self.value));
},0)
}
}
function reject(error){
if(self.status===PENDING){
setTimeout(function(){
self.status=REJECTED;
self.error=error;
self.onRejectedCallbacks.forEach((callback)=>callback(self.error))
},0)
}
}
try{
fn(resolve,reject);
}catch(e){
reject(e);
}
}
function resolvePromise(bridgepromise,x,resolve,reject){
if(bridgepromise===x){
return reject(new TypeError('Circular reference'));
}
let called=false;
if(x instanceof MyPromise){
if(x.status===PENDING){
x.then(y=>{
resolvePromise(bridgepromise,y,resolve,reject)
},error=>{
reject(error);
})
}else{
x.then(resolve,reject)
}
}else if(x!=null && ((typeof x === 'object') || (typeof x === 'function'))){
try{
let then=x.then;
if(typeof then === 'function'){
then.call(x,y=>{
if(called) return;
called=true;
resolvePromise(bridgepromise,y,resolve,reject)
},error=>{
if(called) return;
called=true;
reject(error);
})
}else{
resolve(x);
}
}catch(e){
if(called) return;
called=true;
reject(e);
}
}else{
resolve(x);
}
}
MyPromise.prototype.then=function(onFulfilled,onRejected){
const self=this;
let bridgePromise;
onFulfilled=typeof onFulfilled==='function'?onFulfilled:value=>value;
onRejected=typeof onRejected==='function'?onRejected:error=>{throw error};
if(self.status===FULFILLED){
return bridgePromise=new MyPromise((resolve,reject)=>{
setTimeout(()=>{
try{
let x=onFulfilled(self.value);
resolvePromise(bridgePromise,x,resolve,reject);
}catch(e){
reject(e);
}
},0)
})
}
if(self.status===REJECTED){
return bridgePromise=new MyPromise((resolve,reject)=>{
setTimeout(()=>{
try{
let x=onRejected(self.error);
resolvePromise(bridgePromise,x,resolve,reject);
}catch(e){
reject(e);
}
},0)
})
}
if(self.status===PENDING){
return bridgePromise=new MyPromise((resolve,reject)=>{
self.onFulfilledCallbacks.push((value)=>{
try{
let x=onFulfilled(value);
resolvePromise(bridgePromise,x,resolve,reject)
}catch(e){
reject(e);
}
});
self.onRejectedCallbacks.push((error)=>{
try{
let x=onRejected(error);
resolvePromise(bridgePromise,x,resolve,reject);
}catch(e){
reject(e);
}
});
});
}
}
MyPromise.prototype.catch=function(onRejected){
return this.then(null,onRejected);
}
MyPromise.deferred=function(){
let defer={};
defer.promise=new MyPromise((resolve,reject)=>{
defer.resolve=resolve;
defer.reject=reject;
});
return defer;
}
try{
module.exports=MyPromise;
}catch(e){}
简版
function myPromise(constructor){
let self=this;
self.status='pending';
self.vlaue=undefined;
self.reason=undefined;
function resolve(value){
if(self.status==='pending'){
self.value=value;
self.status='resolved';
}
}
function reject(reason){
if(self.status==='pending'){
self.reason=reason;
self.status='rejected';
}
}
try{
constructor(resolve,reject);
}catch(e){
reject(e);
}
}
myPromise.prototype.then=function(onFullfilled,onRejected){
let self=this;
switch(self.status){
case 'resolved':
onFullfilled(self.value);
break;
case 'rejected':
onRejected(self.reason);
break;
default:
}
}
# 实现promise的生成器run方法
function run(gen){
let args=[].slice.call(arguments,1),
it;
it=gen.apply(this,args);
return Promise.resolve().then(function handleNext(value){
let next =it.next(value);
return (function handleResult(next){
if(next.done){
return next.value;
}else{
return Promise.resolve(next.value).then(
handleNext,
function handleErr(err){
return Promise.resolve(
if.throw(err)
).then(handleResult);
}
);
}
})(next);
})
}
# 实现promisify
function promisify(fn){
return function(...args){
return new Promise(function(resolve,reject){
fn(...args,function(err,data){
if(err){
reject(err)
}else{
resolve(data);
}
};
});
}
}
# 实现thunkify
function thunkify(fn){
let args=[].slice.call(arguments,1);
return function(cb){
args.push(cb);
return fn.apply(null,args);
}
}
# 使用setTimeout实现setInterval
setTimeout(function(){
setTimeout(arguments.callee,500)
},500)
# 实现JSON.parse
var json = '{"name":"cxk", "age":25}';
var obj = eval("(" + json + ")");
# 实现JSON.stringify
function jsonStringify(obj){
let type=typeof obj;
if(type !== 'object' || type === null){
if(/string|undefined|function/.test(type)){
obj='"'+obj+'"';
}
return String(obj);
}else{
let json=[];
arr=(obj && obj.constructor===Array);
for(let k in obj){
let v=obj[k];
let type=typeof v;
if(/string|undefined|function/.test(type)){
v='"'+v+'"';
}else if(type === 'object'){
v=jsonStringify(v);
}
json.push((arr ? "":'"'+k'":')+String(v));
}
return (arr ? "[" : "{" ) + String(json)+(arr ? "]" : "}" )
}
}
# 实现indexOf方法
function indexOf(arr,elem,fromi){
fromi=fromi||0;
for(var i=fromi;i<arr.length;i++){
if(elem===arr[i]){
return i;
}
}
return -1;
}
# 实现reduce方法
简版：
Array.prototype.myReduce=function(fn,initialValue){
if(this.length===0){
if(initialValue===undefined){
console.error("reduce of empty array with no initialValue")
}else{
return initialValue
}
}else{
let prev=initialValue !== undefined ? initialValue : this[0];
let startIndex = initialValue !== undefined ? 0 : 1;
for(let i=startIndex;i<this.length;i++){
prev = fn(prev,this[i]);
}
return prev;
}
}
完整版：
Array.prototype.myreduce=function reduce(callbackfn){
const o=this,
len=o.length;
let k=0,
accumulator=undefined,
kPresent=false,
initialValue=arguments.length>1?arguments[1]:undefined;
if(typeof callbackfn !== 'function'){
throw new TypeError(callbackfn+'is not a function');
}
if(len === 0 && arguments.length<2){
throw new TypeError('Reduce of empty array with no initial value');
}
if(arguments.length>1){
accumulator=initialValue;
}else{
accumulator=o[k];
++k;
}
while(k<len){
kPresent=o.hasOwnProperty(k);
if(kPresent){
const kValue=o[k];
accumulator=callbackfn.apply(undefined,[accumulator,kValue,k,o]);
}
++k;
}
return accumulator;
}
# 实现trim方法
function trim(str){
if(str && typeof str==='string'){
return str.replace(/^\s+l\s+$/g/,'')
}
}
# 实现join方法
function join(arr,connector){
let str='';
for(let i=0;i<arr.length;i++){
if(i>0){
str+=connector;
}
if(arr[i] !== undefined){
str+=arr[i];
}
}
return str;
}
# 实现一个模板引擎
function render(template, data) {
const reg = /\{\{(\w+)\}\}/;
if (reg.test(template)) {
const name = reg.exec(template)[1];
template = template.replace(reg, data[name]);
return render(template, data);
}
return template;
}
# 实现一个转驼峰方法camelCase
function camelCase(str){
return str.replace(/-\w/g,function(newStr){
return newStr.slice(1).toUpperCase();
})
}
# 实现Virtual Dom && Diff
// 实现一个utils方法库
const _ = exports
_.setAttr = function setAttr (node, key, value) {
switch (key) {
case 'style':
node.style.cssText = value
break;
case 'value':
let tagName = node.tagName || ''
tagName = tagName.toLowerCase()
if (
tagName === 'input' || tagName === 'textarea'
) {
node.value = value
} else {
// 如果节点不是 input 或者 textarea, 则使用 `setAttribute` 去设置属性
node.setAttribute(key, value)
}
break;
default:
node.setAttribute(key, value)
break;
}
}
_.slice = function slice (arrayLike, index) {
return Array.prototype.slice.call(arrayLike, index)
}
_.type = function type (obj) {
return Object.prototype.toString.call(obj).replace(/\[object\s|\]/g, '')
}
_.isArray = function isArray (list) {
return _.type(list) === 'Array'
}
_.toArray = function toArray (listLike) {
if (!listLike) return []
let list = []
for (let i = 0, l = listLike.length; i < l; i++) {
list.push(listLike[i])
}
return list
}
_.isString = function isString (list) {
return _.type(list) === 'String'
}
_.isElementNode = function (node) {
return node.nodeType === 1
}
// 实现一个 Element
import _ from './utils'
/**
* @class Element Virtrual Dom
* @param { String } tagName
* @param { Object } attrs Element's attrs, 如: { id: 'list' }
* @param { Array <Element|String> } 可以是Element对象，也可以只是字符串，即textNode
*/
class Element {
constructor(tagName, attrs, children) {
// 如果只有两个参数
if (_.isArray(attrs)) {
children = attrs
attrs = {}
}
this.tagName = tagName
this.attrs = attrs || {}
this.children = children
// 设置this.key属性，为了后面list diff做准备
this.key = attrs
? attrs.key
: void 0
}
render () {
let el = document.createElement(this.tagName)
let attrs = this.attrs
for (let attrName in attrs) { // 设置节点的DOM属性
let attrValue = attrs[attrName]
_.setAttr(el, attrName, attrValue)
}
let children = this.children || []
children.forEach(child => {
let childEl = child instanceof Element
? child.render() // 若子节点也是虚拟节点，递归进行构建
: document.createTextNode(child) // 若是字符串，直接构建文本节点
el.appendChild(childEl)
})
return el
}
}
function el (tagName, attrs, children) {
return new Element(tagName, attrs, children)
}
module.exports = el;
// 实现 diff 算法
/**
* Diff two list in O(N).
* @param {Array} oldList - 原始列表
* @param {Array} newList - 经过一些操作的得出的新列表
* @return {Object} - {moves: <Array>}
* - moves list操作记录的集合
*/
function diff (oldList, newList, key) {
let oldMap = getKeyIndexAndFree(oldList, key)
let newMap = getKeyIndexAndFree(newList, key)
let newFree = newMap.free
let oldKeyIndex = oldMap.keyIndex
let newKeyIndex = newMap.keyIndex
// 记录所有move操作
let moves = []
// a simulate list
let children = []
let i = 0
let item
let itemKey
let freeIndex = 0
// newList 向 oldList 的形式靠近进行操作
while (i < oldList.length) {
item = oldList[i]
itemKey = getItemKey(item, key)
if (itemKey) {
if (!newKeyIndex.hasOwnProperty(itemKey)) {
children.push(null)
} else {
let newItemIndex = newKeyIndex[itemKey]
children.push(newList[newItemIndex])
}
} else {
let freeItem = newFree[freeIndex++]
children.push(freeItem || null)
}
i++
}
let simulateList = children.slice(0)
// 移除列表中一些不存在的元素
i = 0
while (i < simulateList.length) {
if (simulateList[i] === null) {
remove(i)
removeSimulate(i)
} else {
i++
}
}
// i => new list
// j => simulateList
let j = i = 0
while (i < newList.length) {
item = newList[i]
itemKey = getItemKey(item, key)
let simulateItem = simulateList[j]
let simulateItemKey = getItemKey(simulateItem, key)
if (simulateItem) {
if (itemKey === simulateItemKey) {
j++
}
else {
// 如果移除掉当前的 simulateItem 可以让 item在一个正确的位置，那么直接移除
let nextItemKey = getItemKey(simulateList[j + 1], key)
if (nextItemKey === itemKey) {
remove(i)
removeSimulate(j)
j++ // 移除后，当前j的值是正确的，直接自加进入下一循环
} else {
// 否则直接将item 执行 insert
insert(i, item)
}
}
// 如果是新的 item, 直接执行 inesrt
} else {
insert(i, item)
}
i++
}
// if j is not remove to the end, remove all the rest item
// let k = 0;
// while (j++ < simulateList.length) {
// remove(k + i);
// k++;
// }
// 记录remove操作
function remove (index) {
let move = {index: index, type: 0}
moves.push(move)
}
// 记录insert操作
function insert (index, item) {
let move = {index: index, item: item, type: 1}
moves.push(move)
}
// 移除simulateList中对应实际list中remove掉节点的元素
function removeSimulate (index) {
simulateList.splice(index, 1)
}
// 返回所有操作记录
return {
moves: moves,
children: children
}
}
/**
* 将 list转变成 key-item keyIndex 对象的形式进行展示.
* @param {Array} list
* @param {String|Function} key
*/
function getKeyIndexAndFree (list, key) {
let keyIndex = {}
let free = []
for (let i = 0, len = list.length; i < len; i++) {
let item = list[i]
let itemKey = getItemKey(item, key)
if (itemKey) {
keyIndex[itemKey] = i
} else {
free.push(item)
}
}
// 返回 key-item keyIndex
return {
keyIndex: keyIndex,
free: free
}
}
function getItemKey (item, key) {
if (!item || !key) return void 0
return typeof key === 'string'
? item[key]
: key(item)
}
module.exports = diff
// 实现 patch，解析 patch 对象
function patch (rootNode, patches) {
let walker = { index: 0 }
walk(rootNode, walker, patches)
}
function walk (node, walker, patches) {
let currentPatches = patches[walker.index] // 从patches取出当前节点的差异
let len = node.childNodes
? node.childNodes.length
: 0
for (let i = 0; i < len; i++) { // 深度遍历子节点
let child = node.childNodes[i]
walker.index++
walk(child, walker, patches)
}
if (currentPatches) {
dealPatches(node, currentPatches) // 对当前节点进行DOM操作
}
}
function dealPatches (node, currentPatches) {
currentPatches.forEach(currentPatch => {
switch (currentPatch.type) {
case REPLACE:
let newNode = (typeof currentPatch.node === 'string')
? document.createTextNode(currentPatch.node)
: currentPatch.node.render()
node.parentNode.replaceChild(newNode, node)
break
case REORDER:
reorderChildren(node, currentPatch.moves)
break
case ATTRS:
setProps(node, currentPatch.props)
break
case TEXT:
if (node.textContent) {
node.textContent = currentPatch.content
} else {
// for ie
node.nodeValue = currentPatch.content
}
break
default:
throw new Error('Unknown patch type ' + currentPatch.type)
}
})
}
function setAttrs (node, props) {
for (let key in props) {
if (props[key] === void 0) {
node.removeAttribute(key)
} else {
let value = props[key]
_.setAttr(node, key, value)
}
}
}
function reorderChildren (node, moves) {
let staticNodeList = _.toArray(node.childNodes)
let maps = {} // 存储含有key特殊字段的节点
staticNodeList.forEach(node => {
// 如果当前节点是ElementNode，通过maps将含有key字段的节点进行存储
if (_.isElementNode(node)) {
let key = node.getAttribute('key')
if (key) {
maps[key] = node
}
}
})
moves.forEach(move => {
let index = move.index
if (move.type === 0) { // remove item
if (staticNodeList[index] === node.childNodes[index]) { // maybe have been removed for inserting
node.removeChild(node.childNodes[index])
}
staticNodeList.splice(index, 1)
} else if (move.type === 1) { // insert item
let insertNode = maps[move.item.key]
? maps[move.item.key] // reuse old item
: (typeof move.item === 'object')
? move.item.render()
: document.createTextNode(move.item)
staticNodeList.splice(index, 0, insertNode)
node.insertBefore(insertNode, node.childNodes[index] || null)
}
})
}
# 实现一个简版jQuery
(function(window,undefined){
let njQuery=function(){
return new njQuery.prototype.init();
}
njQuery.prototype={
constructor:njQuery
}
njQuery.prototype.init.prototype=njQuery.prototype;
window.njQuery=window.$=njQuery;
})(window)
# 算法部分
# 实现冒泡排序
function swap(A,i,j){
const t=A[i];
A[i]=A[j];
A[j]=t;
}
function buble_sort(A){
// |---未排序---|---已排序的最大值---|
// 初始 |------未排序------|i|
for(let i=A.length;i>0;i--){
for(let j=1;j<i;j++){
if(A[j]<A[j-1]){
swap(A,j,j-1)
}
}
// 循环不变式成立
}
return A
}
# 实现快速排序
// i指向最后一个小于支点的数字，j指向未确认的下一个数字 初始值 i=-1,j=0
function swap(A,i,j){
[A[i],A[j]]=[A[j],A[i]];
}
function divide(A,p,r){
const x=A[r-1];
let i=p-1;
for(let j=p;j<r-1;j++){
if(A[j]<x){
i++;
swap(A,i,j);
}
}
swap(A,i+1,r-1);
return i+1;
}
function quick_sort(A,p=0,r){
r = typeof r !== 'undefined' ? r : A.length;
if(p<r-1){
const q=divide(A,p,r);
quick_sort(A,p,q);
quick_sort(A,q+1,r)
}
}
# 实现插入排序
function insert_sort(A){
for(
let j=1;
j<A.length;
j++){
const key=A[j];
let i=j-1;
while(i>=0 && A[i]>key){
A[i+1]=A[i];
i--;
}
A[i+1]=key
}
}
# 实现归并排序
const SENTINEL=Number.MAX_SAFE_INTEGER;
function divide(p,r){
return Math.floor((p+r)/2)
}
function conquer(A,p,q,r){
const A1=A.slice(p,q);
const A2=A.slice(q,r);
A1.push(SENTINEL);
A2.push(SENTINEL);
for(let k=p,i=0,j=0;k<r;k++){
A[k]=A1[i]<A2[i]?A1[i++]:A2[j++]
}
}
function merge_sort(A,p=0,r){
r=r || A.length;
if(r-p===1){return}
if(r-p===2){
if(A[p]>A[r-1]){
[A[p],A[r-1]]=[A[r-1],A[p]]
}
return
}
const q=divide(p,r);
console.log('divide:'+q);
merge_sort(A,p,q)
merge_sort(A,q,r)
conquer(A,p,q,r)
}
# 实现桶排序
function bucket_sort(A,max){
const a=max;
const B=[...Array(a+1)].map(x=>[])
const indexFunc=(value)=>{
const key=Math.floor(value/a);
if(key>a){
return a
}
return key
}
A.forEach(value=>{
const idx=Math.floor(indexFunc(value))
if(!B[idx]){
throw new Error('桶脚标没有命中 index='+idx)
}
B[idx].push(value)
})
return [].concat(...B.map(bucket=>{
return bucket.sort((x,y)=>x-y)
}))
}
# 实现二分查找
function bsearch(A,x){
let l=0,
r=A.length-1,
guess;
while(l<=r){
guess=Math.floor((l+r)/2);
if(A[guess]===x){
return guess;
}else if(A[guess]>x){
r=guess-1;
}else{
l=guess+1
}
}
return -1;
}
# 实现红黑树
BinarySearchTree
import BinarySearchTreeNode from './BinarySearchTreeNode';
export default class BinarySearchTree {
/**
* @param {function} [nodeValueCompareFunction]
*/
constructor(nodeValueCompareFunction) {
this.root = new BinarySearchTreeNode(null, nodeValueCompareFunction);
// Steal node comparator from the root.
this.nodeComparator = this.root.nodeComparator;
}
/**
* @param {*} value
* @return {BinarySearchTreeNode}
*/
insert(value) {
return this.root.insert(value);
}
/**
* @param {*} value
* @return {boolean}
*/
contains(value) {
return this.root.contains(value);
}
/**
* @param {*} value
* @return {boolean}
*/
remove(value) {
return this.root.remove(value);
}
/**
* @return {string}
*/
toString() {
return this.root.toString();
}
}
RedBlackTree
import BinarySearchTree from '../binary-search-tree/BinarySearchTree';
// Possible colors of red-black tree nodes.
const RED_BLACK_TREE_COLORS = {
red: 'red',
black: 'black',
};
// Color property name in meta information of the nodes.
const COLOR_PROP_NAME = 'color';
export default class RedBlackTree extends BinarySearchTree {
/**
* @param {*} value
* @return {BinarySearchTreeNode}
*/
insert(value) {
const insertedNode = super.insert(value);
// if (!this.root.left && !this.root.right) {
if (this.nodeComparator.equal(insertedNode, this.root)) {
// Make root to always be black.
this.makeNodeBlack(insertedNode);
} else {
// Make all newly inserted nodes to be red.
this.makeNodeRed(insertedNode);
}
// Check all conditions and balance the node.
this.balance(insertedNode);
return insertedNode;
}
/**
* @param {*} value
* @return {boolean}
*/
remove(value) {
throw new Error(`Can't remove ${value}. Remove method is not implemented yet`);
}
/**
* @param {BinarySearchTreeNode} node
*/
balance(node) {
// If it is a root node then nothing to balance here.
if (this.nodeComparator.equal(node, this.root)) {
return;
}
// If the parent is black then done. Nothing to balance here.
if (this.isNodeBlack(node.parent)) {
return;
}
const grandParent = node.parent.parent;
if (node.uncle && this.isNodeRed(node.uncle)) {
// If node has red uncle then we need to do RECOLORING.
// Recolor parent and uncle to black.
this.makeNodeBlack(node.uncle);
this.makeNodeBlack(node.parent);
if (!this.nodeComparator.equal(grandParent, this.root)) {
// Recolor grand-parent to red if it is not root.
this.makeNodeRed(grandParent);
} else {
// If grand-parent is black root don't do anything.
// Since root already has two black sibling that we've just recolored.
return;
}
// Now do further checking for recolored grand-parent.
this.balance(grandParent);
} else if (!node.uncle || this.isNodeBlack(node.uncle)) {
// If node uncle is black or absent then we need to do ROTATIONS.
if (grandParent) {
// Grand parent that we will receive after rotations.
let newGrandParent;
if (this.nodeComparator.equal(grandParent.left, node.parent)) {
// Left case.
if (this.nodeComparator.equal(node.parent.left, node)) {
// Left-left case.
newGrandParent = this.leftLeftRotation(grandParent);
} else {
// Left-right case.
newGrandParent = this.leftRightRotation(grandParent);
}
} else {
// Right case.
if (this.nodeComparator.equal(node.parent.right, node)) {
// Right-right case.
newGrandParent = this.rightRightRotation(grandParent);
} else {
// Right-left case.
newGrandParent = this.rightLeftRotation(grandParent);
}
}
// Set newGrandParent as a root if it doesn't have parent.
if (newGrandParent && newGrandParent.parent === null) {
this.root = newGrandParent;
// Recolor root into black.
this.makeNodeBlack(this.root);
}
// Check if new grand parent don't violate red-black-tree rules.
this.balance(newGrandParent);
}
}
}
/**
* Left Left Case (p is left child of g and x is left child of p)
* @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
* @return {BinarySearchTreeNode}
*/
leftLeftRotation(grandParentNode) {
// Memorize the parent of grand-parent node.
const grandGrandParent = grandParentNode.parent;
// Check what type of sibling is our grandParentNode is (left or right).
let grandParentNodeIsLeft;
if (grandGrandParent) {
grandParentNodeIsLeft = this.nodeComparator.equal(grandGrandParent.left, grandParentNode);
}
// Memorize grandParentNode's left node.
const parentNode = grandParentNode.left;
// Memorize parent's right node since we're going to transfer it to
// grand parent's left subtree.
const parentRightNode = parentNode.right;
// Make grandParentNode to be right child of parentNode.
parentNode.setRight(grandParentNode);
// Move child's right subtree to grandParentNode's left subtree.
grandParentNode.setLeft(parentRightNode);
// Put parentNode node in place of grandParentNode.
if (grandGrandParent) {
if (grandParentNodeIsLeft) {
grandGrandParent.setLeft(parentNode);
} else {
grandGrandParent.setRight(parentNode);
}
} else {
// Make parent node a root
parentNode.parent = null;
}
// Swap colors of granParent and parent nodes.
this.swapNodeColors(parentNode, grandParentNode);
// Return new root node.
return parentNode;
}
/**
* Left Right Case (p is left child of g and x is right child of p)
* @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
* @return {BinarySearchTreeNode}
*/
leftRightRotation(grandParentNode) {
// Memorize left and left-right nodes.
const parentNode = grandParentNode.left;
const childNode = parentNode.right;
// We need to memorize child left node to prevent losing
// left child subtree. Later it will be re-assigned to
// parent's right sub-tree.
const childLeftNode = childNode.left;
// Make parentNode to be a left child of childNode node.
childNode.setLeft(parentNode);
// Move child's left subtree to parent's right subtree.
parentNode.setRight(childLeftNode);
// Put left-right node in place of left node.
grandParentNode.setLeft(childNode);
// Now we're ready to do left-left rotation.
return this.leftLeftRotation(grandParentNode);
}
/**
* Right Right Case (p is right child of g and x is right child of p)
* @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
* @return {BinarySearchTreeNode}
*/
rightRightRotation(grandParentNode) {
// Memorize the parent of grand-parent node.
const grandGrandParent = grandParentNode.parent;
// Check what type of sibling is our grandParentNode is (left or right).
let grandParentNodeIsLeft;
if (grandGrandParent) {
grandParentNodeIsLeft = this.nodeComparator.equal(grandGrandParent.left, grandParentNode);
}
// Memorize grandParentNode's right node.
const parentNode = grandParentNode.right;
// Memorize parent's left node since we're going to transfer it to
// grand parent's right subtree.
const parentLeftNode = parentNode.left;
// Make grandParentNode to be left child of parentNode.
parentNode.setLeft(grandParentNode);
// Transfer all left nodes from parent to right sub-tree of grandparent.
grandParentNode.setRight(parentLeftNode);
// Put parentNode node in place of grandParentNode.
if (grandGrandParent) {
if (grandParentNodeIsLeft) {
grandGrandParent.setLeft(parentNode);
} else {
grandGrandParent.setRight(parentNode);
}
} else {
// Make parent node a root.
parentNode.parent = null;
}
// Swap colors of granParent and parent nodes.
this.swapNodeColors(parentNode, grandParentNode);
// Return new root node.
return parentNode;
}
/**
* Right Left Case (p is right child of g and x is left child of p)
* @param {BinarySearchTreeNode|BinaryTreeNode} grandParentNode
* @return {BinarySearchTreeNode}
*/
rightLeftRotation(grandParentNode) {
// Memorize right and right-left nodes.
const parentNode = grandParentNode.right;
const childNode = parentNode.left;
// We need to memorize child right node to prevent losing
// right child subtree. Later it will be re-assigned to
// parent's left sub-tree.
const childRightNode = childNode.right;
// Make parentNode to be a right child of childNode.
childNode.setRight(parentNode);
// Move child's right subtree to parent's left subtree.
parentNode.setLeft(childRightNode);
// Put childNode node in place of parentNode.
grandParentNode.setRight(childNode);
// Now we're ready to do right-right rotation.
return this.rightRightRotation(grandParentNode);
}
/**
* @param {BinarySearchTreeNode|BinaryTreeNode} node
* @return {BinarySearchTreeNode}
*/
makeNodeRed(node) {
node.meta.set(COLOR_PROP_NAME, RED_BLACK_TREE_COLORS.red);
return node;
}
/**
* @param {BinarySearchTreeNode|BinaryTreeNode} node
* @return {BinarySearchTreeNode}
*/
makeNodeBlack(node) {
node.meta.set(COLOR_PROP_NAME, RED_BLACK_TREE_COLORS.black);
return node;
}
/**
* @param {BinarySearchTreeNode|BinaryTreeNode} node
* @return {boolean}
*/
isNodeRed(node) {
return node.meta.get(COLOR_PROP_NAME) === RED_BLACK_TREE_COLORS.red;
}
/**
* @param {BinarySearchTreeNode|BinaryTreeNode} node
* @return {boolean}
*/
isNodeBlack(node) {
return node.meta.get(COLOR_PROP_NAME) === RED_BLACK_TREE_COLORS.black;
}
/**
* @param {BinarySearchTreeNode|BinaryTreeNode} node
* @return {boolean}
*/
isNodeColored(node) {
return this.isNodeRed(node) || this.isNodeBlack(node);
}
/**
* @param {BinarySearchTreeNode|BinaryTreeNode} firstNode
* @param {BinarySearchTreeNode|BinaryTreeNode} secondNode
*/
swapNodeColors(firstNode, secondNode) {
const firstColor = firstNode.meta.get(COLOR_PROP_NAME);
const secondColor = secondNode.meta.get(COLOR_PROP_NAME);
firstNode.meta.set(COLOR_PROP_NAME, secondColor);
secondNode.meta.set(COLOR_PROP_NAME, firstColor);
}
}
# 实现分段树
import isPowerOfTwo from '../../../algorithms/math/is-power-of-two/isPowerOfTwo';
export default class SegmentTree {
/**
* @param {number[]} inputArray
* @param {function} operation - binary function (i.e. sum, min)
* @param {number} operationFallback - operation fallback value (i.e. 0 for sum, Infinity for min)
*/
constructor(inputArray, operation, operationFallback) {
this.inputArray = inputArray;
this.operation = operation;
this.operationFallback = operationFallback;
// Init array representation of segment tree.
this.segmentTree = this.initSegmentTree(this.inputArray);
this.buildSegmentTree();
}
/**
* @param {number[]} inputArray
* @return {number[]}
*/
initSegmentTree(inputArray) {
let segmentTreeArrayLength;
const inputArrayLength = inputArray.length;
if (isPowerOfTwo(inputArrayLength)) {
// If original array length is a power of two.
segmentTreeArrayLength = (2 * inputArrayLength) - 1;
} else {
// If original array length is not a power of two then we need to find
// next number that is a power of two and use it to calculate
// tree array size. This is happens because we need to fill empty children
// in perfect binary tree with nulls.And those nulls need extra space.
const currentPower = Math.floor(Math.log2(inputArrayLength));
const nextPower = currentPower + 1;
const nextPowerOfTwoNumber = 2 ** nextPower;
segmentTreeArrayLength = (2 * nextPowerOfTwoNumber) - 1;
}
return new Array(segmentTreeArrayLength).fill(null);
}
/**
* Build segment tree.
*/
buildSegmentTree() {
const leftIndex = 0;
const rightIndex = this.inputArray.length - 1;
const position = 0;
this.buildTreeRecursively(leftIndex, rightIndex, position);
}
/**
* Build segment tree recursively.
*
* @param {number} leftInputIndex
* @param {number} rightInputIndex
* @param {number} position
*/
buildTreeRecursively(leftInputIndex, rightInputIndex, position) {
// If low input index and high input index are equal that would mean
// the we have finished splitting and we are already came to the leaf
// of the segment tree. We need to copy this leaf value from input
// array to segment tree.
if (leftInputIndex === rightInputIndex) {
this.segmentTree[position] = this.inputArray[leftInputIndex];
return;
}
// Split input array on two halves and process them recursively.
const middleIndex = Math.floor((leftInputIndex + rightInputIndex) / 2);
// Process left half of the input array.
this.buildTreeRecursively(leftInputIndex, middleIndex, this.getLeftChildIndex(position));
// Process right half of the input array.
this.buildTreeRecursively(middleIndex + 1, rightInputIndex, this.getRightChildIndex(position));
// Once every tree leaf is not empty we're able to build tree bottom up using
// provided operation function.
this.segmentTree[position] = this.operation(
this.segmentTree[this.getLeftChildIndex(position)],
this.segmentTree[this.getRightChildIndex(position)],
);
}
/**
* Do range query on segment tree in context of this.operation function.
*
* @param {number} queryLeftIndex
* @param {number} queryRightIndex
* @return {number}
*/
rangeQuery(queryLeftIndex, queryRightIndex) {
const leftIndex = 0;
const rightIndex = this.inputArray.length - 1;
const position = 0;
return this.rangeQueryRecursive(
queryLeftIndex,
queryRightIndex,
leftIndex,
rightIndex,
position,
);
}
/**
* Do range query on segment tree recursively in context of this.operation function.
*
* @param {number} queryLeftIndex - left index of the query
* @param {number} queryRightIndex - right index of the query
* @param {number} leftIndex - left index of input array segment
* @param {number} rightIndex - right index of input array segment
* @param {number} position - root position in binary tree
* @return {number}
*/
rangeQueryRecursive(queryLeftIndex, queryRightIndex, leftIndex, rightIndex, position) {
if (queryLeftIndex <= leftIndex && queryRightIndex >= rightIndex) {
// Total overlap.
return this.segmentTree[position];
}
if (queryLeftIndex > rightIndex || queryRightIndex < leftIndex) {
// No overlap.
return this.operationFallback;
}
// Partial overlap.
const middleIndex = Math.floor((leftIndex + rightIndex) / 2);
const leftOperationResult = this.rangeQueryRecursive(
queryLeftIndex,
queryRightIndex,
leftIndex,
middleIndex,
this.getLeftChildIndex(position),
);
const rightOperationResult = this.rangeQueryRecursive(
queryLeftIndex,
queryRightIndex,
middleIndex + 1,
rightIndex,
this.getRightChildIndex(position),
);
return this.operation(leftOperationResult, rightOperationResult);
}
/**
* Left child index.
* @param {number} parentIndex
* @return {number}
*/
getLeftChildIndex(parentIndex) {
return (2 * parentIndex) + 1;
}
/**
* Right child index.
* @param {number} parentIndex
* @return {number}
*/
getRightChildIndex(parentIndex) {
return (2 * parentIndex) + 2;
}
}
# 实现字典树
TrieNode
import HashTable from '../hash-table/HashTable';
export default class TrieNode {
/**
* @param {string} character
* @param {boolean} isCompleteWord
*/
constructor(character, isCompleteWord = false) {
this.character = character;
this.isCompleteWord = isCompleteWord;
this.children = new HashTable();
}
/**
* @param {string} character
* @return {TrieNode}
*/
getChild(character) {
return this.children.get(character);
}
/**
* @param {string} character
* @param {boolean} isCompleteWord
* @return {TrieNode}
*/
addChild(character, isCompleteWord = false) {
if (!this.children.has(character)) {
this.children.set(character, new TrieNode(character, isCompleteWord));
}
const childNode = this.children.get(character);
// In cases similar to adding "car" after "carpet" we need to mark "r" character as complete.
childNode.isCompleteWord = childNode.isCompleteWord || isCompleteWord;
return childNode;
}
/**
* @param {string} character
* @return {TrieNode}
*/
removeChild(character) {
const childNode = this.getChild(character);
// Delete childNode only if:
// - childNode has NO children,
// - childNode.isCompleteWord === false.
if (
childNode
&& !childNode.isCompleteWord
&& !childNode.hasChildren()
) {
this.children.delete(character);
}
return this;
}
/**
* @param {string} character
* @return {boolean}
*/
hasChild(character) {
return this.children.has(character);
}
/**
* Check whether current TrieNode has children or not.
* @return {boolean}
*/
hasChildren() {
return this.children.getKeys().length !== 0;
}
/**
* @return {string[]}
*/
suggestChildren() {
return [...this.children.getKeys()];
}
/**
* @return {string}
*/
toString() {
let childrenAsString = this.suggestChildren().toString();
childrenAsString = childrenAsString ? `:${childrenAsString}` : '';
const isCompleteString = this.isCompleteWord ? '*' : '';
return `${this.character}${isCompleteString}${childrenAsString}`;
}
}
Tri
import TrieNode from './TrieNode';
// Character that we will use for trie tree root.
const HEAD_CHARACTER = '*';
export default class Trie {
constructor() {
this.head = new TrieNode(HEAD_CHARACTER);
}
/**
* @param {string} word
* @return {Trie}
*/
addWord(word) {
const characters = Array.from(word);
let currentNode = this.head;
for (let charIndex = 0; charIndex < characters.length; charIndex += 1) {
const isComplete = charIndex === characters.length - 1;
currentNode = currentNode.addChild(characters[charIndex], isComplete);
}
return this;
}
/**
* @param {string} word
* @return {Trie}
*/
deleteWord(word) {
const depthFirstDelete = (currentNode, charIndex = 0) => {
if (charIndex >= word.length) {
// Return if we're trying to delete the character that is out of word's scope.
return;
}
const character = word[charIndex];
const nextNode = currentNode.getChild(character);
if (nextNode == null) {
// Return if we're trying to delete a word that has not been added to the Trie.
return;
}
// Go deeper.
depthFirstDelete(nextNode, charIndex + 1);
// Since we're going to delete a word let's un-mark its last character isCompleteWord flag.
if (charIndex === (word.length - 1)) {
nextNode.isCompleteWord = false;
}
// childNode is deleted only if:
// - childNode has NO children
// - childNode.isCompleteWord === false
currentNode.removeChild(character);
};
// Start depth-first deletion from the head node.
depthFirstDelete(this.head);
return this;
}
/**
* @param {string} word
* @return {string[]}
*/
suggestNextCharacters(word) {
const lastCharacter = this.getLastCharacterNode(word);
if (!lastCharacter) {
return null;
}
return lastCharacter.suggestChildren();
}
/**
* Check if complete word exists in Trie.
*
* @param {string} word
* @return {boolean}
*/
doesWordExist(word) {
const lastCharacter = this.getLastCharacterNode(word);
return !!lastCharacter && lastCharacter.isCompleteWord;
}
/**
* @param {string} word
* @return {TrieNode}
*/
getLastCharacterNode(word) {
const characters = Array.from(word);
let currentNode = this.head;
for (let charIndex = 0; charIndex < characters.length; charIndex += 1) {
if (!currentNode.hasChild(characters[charIndex])) {
return null;
}
currentNode = currentNode.getChild(characters[charIndex]);
}
return currentNode;
}
}
# 使用堆栈简单的符号匹配
function match(n,c){
return (
c=='[' && n==']'
) ||
(
c=='(' && n==')'
)
}
function is_balance(str){
const [first,...others]=str;
const stack=[first];
while(others.length>0){
const c=stack[stack.length-1];
const n=others.shift();
if(!match(n,c)){
stack.push(n)
}else{
stack.pop()
}
}
return stack.length === 0;
}
# 实现广度优先遍历和深度优先遍历
堆栈实现深度优先遍历
function depth_first_search(node){
let stack=[node];
while(stack.length>0){
const item=stack.pop();
for(let i=item.length-1;i>0;i--){
stack.push(item.children[i])
}
}
}
队列实现广度优先搜索
function *breath_first_search(node){
let queue=[node];
while(queue.length>0){
const item=queue.pop();
yield item.tagName;
for(let i=item.length-1;i>0;i--){
queue.unshift(item.children[i])
}
}
}
# 实现n皇后问题
// 判断棋盘上两个皇后是否互相攻击
function compatible(p,q,n){
const [x1,y1]=[~~(p/n),p%n];
const [x2,y2]=[~~(q/n),q%n];
return (
x1 !== x2 && y1 !== y2 && Math.abs(x1-x2) !== Math.abs(y1-y2)
)
}
function queen(n,decisions=[]){
if(decisions.length===n){
return [decisions]
}
let r=[];
const start=decisions[decisions.length-1] || -1;
for(let i=start+1;i<n*n;i++){
if(decisions.indexOf(i)===-1){
if(decisions.every(j=>compatible(j,i,n))){
r=r.concat(queen(n,decisions.concat(i)))
}
}
}
return r;
}
# 实现翻转链表
class List{
...
reverse(p=this.head){
if(p.next){
this.reverse(p.next);
p.next.next=p;
p.next=null
}else{
this.head=p
}
}
}
# 实现最长公共子序列LCS
export default function longestCommonSubsequence(set1, set2) {
// Init LCS matrix.
const lcsMatrix = Array(set2.length + 1).fill(null).map(() => Array(set1.length + 1).fill(null));
// Fill first row with zeros.
for (let columnIndex = 0; columnIndex <= set1.length; columnIndex += 1) {
lcsMatrix[0][columnIndex] = 0;
}
// Fill first column with zeros.
for (let rowIndex = 0; rowIndex <= set2.length; rowIndex += 1) {
lcsMatrix[rowIndex][0] = 0;
}
// Fill rest of the column that correspond to each of two strings.
for (let rowIndex = 1; rowIndex <= set2.length; rowIndex += 1) {
for (let columnIndex = 1; columnIndex <= set1.length; columnIndex += 1) {
if (set1[columnIndex - 1] === set2[rowIndex - 1]) {
lcsMatrix[rowIndex][columnIndex] = lcsMatrix[rowIndex - 1][columnIndex - 1] + 1;
} else {
lcsMatrix[rowIndex][columnIndex] = Math.max(
lcsMatrix[rowIndex - 1][columnIndex],
lcsMatrix[rowIndex][columnIndex - 1],
);
}
}
}
// Calculate LCS based on LCS matrix.
if (!lcsMatrix[set2.length][set1.length]) {
// If the length of largest common string is zero then return empty string.
return [''];
}
const longestSequence = [];
let columnIndex = set1.length;
let rowIndex = set2.length;
while (columnIndex > 0 || rowIndex > 0) {
if (set1[columnIndex - 1] === set2[rowIndex - 1]) {
// Move by diagonal left-top.
longestSequence.unshift(set1[columnIndex - 1]);
columnIndex -= 1;
rowIndex -= 1;
} else if (lcsMatrix[rowIndex][columnIndex] === lcsMatrix[rowIndex][columnIndex - 1]) {
// Move left.
columnIndex -= 1;
} else {
// Move up.
rowIndex -= 1;
}
}
return longestSequence;
}
# 反转二叉树(阿里、头条、知乎)
function reverseBTree(node){
if(!node){
return
}
const tmp=node.left;
node.left=node.right;
node.right=tmp;
reverseBTree(node.left);
reverseBTree(node.right)
}
# 树的轮廓(头条)
/**
* 1
* 5 9
* 4 2 7 3
* 8
*/
// 求一个二叉树从左侧看的轮廓，如图，返回[1,5,4,8]？如果求每行最大值，返回[1,9,7,8]该如何做？
function leftoutlineTree(node,d=0,outline=[]){
if(!node){
return
}
if(!outline[d]){
outline[d]=node.value
}
leftoutlineTree(node.left,d+1,outline);
leftoutlineTree(node.right,d+1,outline);
return outline;
}
function maxOfLine(node,d=0,outline=[]){
if(!node){
return
}
outline[d]=Math.max(outline[d] || -1,node.value);
maxOfLine(node.left,d+1,outline);
maxOfLine(node.right,d+1,outline);
return outline;
}
# 两个栈实现一个队列(滴滴)
class Queue{
constructor({
this.s1=[];
this.s2=[];
}
enqueue(item){
this.s1.push(item)
}
dequeue(){
while(this.s1.length>0){
this.s2.push(this.s1.pop());
}
if(this.s2.length>0){
return this.s2.pop();
}
}
}
# 综合部分
# 实现一个无缝轮播图
- html部分
<div class="container" id="container">
<div id="btn-prev" class="btn-ctrl"><</div>
<div id="btn-next" class="btn-ctrl">></div>
<ul id="inner-list">
<li><img src="images/head1.jpeg" alt=""/></li>
<li><img src="images/head2.jpeg" alt=""/></li>
<li><img src="images/head3.jpeg" alt=""/></li>
</ul>
<ul id="dot-list">
</ul>
</div>
- js部分
window.onload = function(){
var eleInners = document.getElementById('inner-list'),
eleDots = document.getElementById('dot-list'),
liImgs = eleInners.getElementsByTagName('li'),
liDots = eleDots.children,
elePrev = document.getElementById('btn-prev'),
eleNext = document.getElementById('btn-next'),
LI_WIDTH = liImgs[0].offsetWidth,
TIME_DURATION = 3000,
interval = null,
index = 0,
circle = 0;
eleInners.appendChild(liImgs[0].cloneNode(true));
for(var i= 0,len = liImgs.length -1;i<len;i++){
var li = document.createElement('li');
li.innerHTML = i+1;
eleDots.appendChild(li)
};
liDots[0].className = 'cur';
function animate(obj,targetPlace){
clearInterval(obj.timer);
obj.timer = setInterval(function(){
var speed = obj.offsetLeft > targetPlace ? -15:15;
var result = targetPlace - obj.offsetLeft;
if(Math.abs(result) > Math.abs(speed)){
obj.style.left = obj.offsetLeft + speed +'px'
}else{
obj.style.left = targetPlace+'px';
clearInterval(obj.timer);
}
},10)
}
interval = setInterval(autoplay,3000)
function autoplay(){
index++;
if(index > liImgs.length -1){
eleInners.style.left = 0;
index = 1;
}
animate(eleInners, -index * LI_WIDTH);
circle++;
if(circle >= liImgs.length -1){
circle = 0;
}
for(var i= 0,len = liDots.length;i<len;i++){
liDots[i].className ='';
}
liDots[circle].className = 'cur';
}
function moveright(){
index--;
if(index <0){
eleInners.style.left = -(liImgs.length -2)* LI_WIDTH + 'px';
index = liImgs.length -2;
}
animate(eleInners, -index * LI_WIDTH);
circle --;
if(circle < 0){
circle = liImgs.length - 2;//circle回到最后一个点
}
for(var i= 0,len = liDots.length;i<len;i++){
liDots[i].className ='';
}
liDots[circle].className = 'cur'
}
eleInners.addEventListener('mouseenter',function(event){
clearInterval(interval)
});
eleInners.addEventListener('mouseleave',function(event){
interval = setInterval(autoplay,3000)
});
eleDots.addEventListener('click',function(event){
clearInterval(interval);
var target = event.target;
var currentTarget = event.currentTarget;
index = target.innerHTML - 0 - 1;
circle = index ;
for(var i= 0,len = liDots.length;i<len;i++){
liDots[i].className ='';
}
liDots[circle].className = 'cur';
animate(eleInners, - index * LI_WIDTH);
})
elePrev.addEventListener('click',function(event){
clearInterval(interval)
moveright();
interval = setInterval(autoplay,3000)
})
eleNext.addEventListener('click',function(event){
clearInterval(interval);
autoplay();
interval = setInterval(autoplay,3000);
})
}
# 写一个幻灯片（css加分）
- html部分：
<div class="myDiv"></div>
- css部分：
.myDiv{
width: 600px;
height: 400px;
margin: 20px auto;
background-size: over;
background-position: center;
animation-name:loop;
animation-duration: 20s;
animation-iteration-count: infinite;
}
@keyframes loop{
0% {background: url('图片1.jpg') no-repeat;}
25% {background: url('图片2.jpg') no-repeat;}
50% {background: url('图片3.jpg') no-repeat;}
75% {background: url('图片4.jpg') no-repeat;}
100% {background: url('图片5.jpg') no-repeat;}
}
# 如何用css实现瀑布流布局
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<style>
body {
margin: 0;
}
.waterfall-container {
/*分几列*/
column-count: 2;
width: 100%;
/* 列间距 */
column-gap: 10px;
}
.waterfall-item {
break-inside: avoid;
width: 100%;
height: 100px;
margin-bottom: 10px;
background: #ddd;
column-gap: 0;
text-align: center;
color: #fff;
font-size: 40px;
}
</style>
</head>
<body>
<div class="waterfall-container">
<div class="waterfall-item" style="height: 100px">1</div>
<div class="waterfall-item" style="height: 300px">2</div>
<div class="waterfall-item" style="height: 400px">3</div>
<div class="waterfall-item" style="height: 100px">4</div>
<div class="waterfall-item" style="height: 300px">5</div>
<div class="waterfall-item" style="height: 600px">6</div>
<div class="waterfall-item" style="height: 400px">7</div>
<div class="waterfall-item" style="height: 300px">8</div>
<div class="waterfall-item" style="height: 700px">9</div>
<div class="waterfall-item" style="height: 100px">10</div>
</div>
</body>
</html>
# 实现三栏布局有哪些方法, 分别描述一下
Flex 布局
<style>
.container{
display:flex;
justify-content: center;
height: 200px;
background: #eee;
}
.left {
width: 200px;
background-color: red;
height: 100%;
}
.main {
background-color: yellow;
flex: 1;
}
.right {
width: 200px;
background-color: green;
}
</style>
<div class="container">
<div class="left">1</div>
<div class="main">2</div>
<div class="right">3</div>
</div>
绝对定位布局
<style>
.container {
position: relative;
background:#eee;
height:200px;
}
.main {
height: 200px;
margin: 0 120px;
background-color: yellow;
}
.left {
position: absolute;
width: 100px;
height: 200px;
left: 0;
top: 0;
background-color: red;
}
.right {
position: absolute;
width: 100px;
height: 200px;
background-color: green;
right: 0;
top: 0;
}
</style>
<div class="container">
<div class="left">1</div>
<div class="main">2</div>
<div class="right">3</div>
</div>
双飞翼布局
<style>
.content {
float: left;
width: 100%;
}
.main {
height: 200px;
margin-left: 110px;
margin-right: 220px;
background-color: yellow;
}
.left {
float: left;
height: 200px;
width: 100px;
margin-left: -100%;
background-color: red;
}
.right {
width: 200px;
height: 200px;
float: right;
margin-left: -200px;
background-color: green;
}
</style>
<div class="content">
<div class="main"></div>
</div>
<div class="left"></div>
<div class="right"></div>
圣杯布局
<style>
.container {
margin-left: 120px;
margin-right: 220px;
}
.main {
float: left;
width: 100%;
height: 300px;
background-color: yellow;
}
.left {
float: left;
width: 100px;
height: 300px;
margin-left: -100%;
position: relative;
left: -120px;
background-color: blue;
}
.right {
float: left;
width: 200px;
height: 300px;
margin-left: -200px;
position: relative;
right: -220px;
background-color: green;
}
</style>
<div class="container">
<div class="main"></div>
<div class="left"></div>
<div class="right"></div>
</div>
# 一边固定宽度一边宽度自适应
<div class="wrap">
<div class="div1"></div>
<div class="div2"></div>
</div>
.wrap {
display: flex;
justify-content: space-between;
}
.div1 {
min-width: 200px;
}
.div2 {
width: 100%;
background: #e6e6e6;
}
html,
body,
div {
height: 100%;
margin: 0;
}
# 绘制一个等腰三角形
- html部分：
<canvas id="canvas" width="300px" height="300px"></canvas>
- script部分：
let ctx=document.getElementById('canvas').getContext('2d');
ctx.beginPath();
ctx.moveTo(0,150);
ctx.lineTo(150,0);
ctx.lineTo(300,150);
ctx.closePath();
ctx.strokeStyle='#666';
ctx.lineWidth=3;
ctx.stroke();
# 文本超出部分显示省略号
单行
overflow: hidden;
text-overflow:ellipsis;
white-space: nowrap;
多行
display: -webkit-box;
-webkit-box-orient: vertical;
-webkit-line-clamp: 3; // 最多显示几行
overflow: hidden;
# 利用伪元素画三角
.info-tab {
position: relative;
}
.info-tab::after {
content: '';
border: 4px solid transparent;
border-top-color: #2c8ac2;
position: absolute;
top: 0;
}
# 已知父级盒子的宽高，子级img宽高未知，想让img铺满父级盒子且图片不能变形
div {
width: 200px;
height: 200px;
}
img {
object-fit: cover;
width: 100%;
height: 100%;
}
# css3实现0.5px的细线
<style>
.line {
position: relative;
}
.line:after {
content: "";
position: absolute;
left: 0;
top: 0;
width: 100%;
height: 1px;
background-color: #000000;
-webkit-transform: scaleY(.5);
transform: scaleY(.5);
}
</style>
<div class="line"></div>
# 用JavaScript实现斐波那契数列函数，返回第n个斐波那切数。fib(1)=1,fib(2)=1,fib(3)=2等
递归
function fib(n) {
return fib(n) = n > 2 ?
fib(n - 1) + fib(n - 2) :
1
}
尾递归
function fib(n,a=1,b=1){
if(n<=1) return b;
return fib(n-1,b,a+b);
}
非递归 动态规划
function fib(n){
let a=1,
b=1;
for(let i=2;i<n;i++){
const t=b;
b=a+b;
a=t
}
return b
}
非递归 生成器
function *fib(){
let a=1,b=1;
yield a;
yield b;
while(true){
const t=b;
b=a+b;
a=t;
yield b
}
}
递归 reduce流
function fib(n){
return Array(n).fill().reduce(([a,b],_)=>{
return [b,a+b]
},[0,1])[0]
}
非递归 堆栈
function fib(n){
let stack=[n]
while(stack.length){
const item=stack.pop();
if(item===1 || item===2){
stack.push(1)
}else{
stack.push(item-1);
stack.push(item-2);
}
}
}
# 判断一个数是否是素数
function is_prime(n){
if(n<=1){return false}
const N=Math.floor(Math.sqrt(n));
let is_prime=true
for(let i=2;i<=N;i++){
if(n%i===0){
is_prime=false;
break;
}
}
return is_prime;
}
# 获取n以内所有的素数
function *sieve_primes(n){
let numbers=Array.from({length:n-2},(_,i)=>i+2);
let p=null;
while((p=numbers.shift())){
yield p;
numbers=numbers.filter(t=>t%p!==0)
}
}
# 删除数组arr第一个元素。不要直接修改数组arr，结果返回新的数组。
function insert(arr, item, index) {
return arr.slice(0,index).concat(item,arr.slice(index));
}
function insert(arr, item, index) {
var newArr=arr.concat();
newArr.splice(index,0,item);
return newArr;
}
function insert(arr, item, index) {
var newArr=arr.slice(0);
newArr.splice(index,0,item);
return newArr;
}
function insert(arr, item, index) {
var newArr=[];
[].push.apply(newArr, arr);
newArr.splice(index,0,item);
return newArr;
}
# 实现一个打点计时器，要求：(1)从start到end（包含start和end），每隔100毫秒console.log一个数字，每次数字增幅为1；(2)返回的对象中需要包含一个cancel方法，用于停止定时操作；(3)第一个数需要立即输出
function count(start, end) {
console.log(start)
var timer = setInterval(
function(){
if(start<end) console.log(start+=1);
},100)
return {cancel:function(){clearInterval(timer)}}
}
# sort方法将数组内的对象进行排序
function compare(propertyName, index) {
return function(a, b) {
let value1 = a[propertyName];
let value2 = b[propertyName];
if (vm.reverse[index]) {
return value2 - value1;
} else {
return value1 - value2;
}
};
}
# 查找字符串中出现最多的字符和个数
let num=0;
let char='';
let str = str.split('').sort().join('');
str.replace(/(\w)\1+/g,($0,$1) => {
if(num < $0.length){
num = $0.length;
char = $1;
}
});
console.log(`字符最多的是${char}，出现了${num}次`);
# 实现一个方法，随机打乱一个数组
function shuffle_simple(arr){
return arr.sort(()=>Math.random()- .5)
}
或
function fisher_yates_shuffle(arr){
for(let i=0;i<arr.length-1;i++){
const j=i+Math.floor(Math.random()*(arr.length-1));
[arr[i],[arr[j]]]=[arr[j],arr[i]]
}
return arr
}
或
function shuffle(arr){
const m=[];
const N=arr.length*arr.length*arr.length;
for(let i=0;i<arr.length-1;i++){
m[i]=Math.floor(Math.random(1,N))
}
return arr.sort((i,j)=>m[i]-m[j])
}
# 用jq实现一个类似百度搜索框的模糊查询
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
<style>
#div_main {
margin: 0 auto;
width: 300px;
height: 400px;
border: 1px solid black;
margin-top: 50px;
}
#div_txt {
position: relative;
width: 200px;
margin: 0 auto;
margin-top: 40px;
}
#txt1 {
width: 99%;
}
#div_items {
position: relative;
width: 100%;
height: 200px;
border: 1px solid #66afe9;
border-top: 0px;
overflow: auto;
display: none;
}
.div_item {
width: 100%;
height: 20px;
margin-top: 1px;
font-size: 13px;
line-height: 20px;
}
</style>
</head>
<body>
<div id="div_main">
<!--表单的autocomplete="off"属性设置可以阻止浏览器默认的提示框-->
<form autocomplete="off">
<div id="div_txt">
<!--要模糊匹配的文本框-->
<input type="text" id="txt1" />
<!--模糊匹配窗口-->
<div id="div_items">
<div class="div_item">周杰伦</div>
<div class="div_item">周杰</div>
<div class="div_item">林俊杰</div>
<div class="div_item">林宥嘉</div>
<div class="div_item">林妙可</div>
<div class="div_item">唐嫣</div>
<div class="div_item">唐家三少</div>
<div class="div_item">唐朝盛世</div>
<div class="div_item">奥迪A4L</div>
<div class="div_item">奥迪A6L</div>
<div class="div_item">奥迪A8L</div>
<div class="div_item">奥迪R8</div>
<div class="div_item">宝马GT</div>
</div>
</div>
</form>
</div>
<script src="./jquery.min.js"></script>
<script type="text/javascript">
//弹出列表框
$("#txt1").click(function () {
$("#div_items").css('display', 'block');
return false;
});
//隐藏列表框
$("body").click(function () {
$("#div_items").css('display', 'none');
});
//移入移出效果
$(".div_item").hover(function () {
$(this).css('background-color', '#1C86EE').css('color', 'white');
}, function () {
$(this).css('background-color', 'white').css('color', 'black');
});
//文本框输入
$("#txt1").keyup(function () {
$("#div_items").css('display', 'block');//只要输入就显示列表框
if ($("#txt1").val().length <= 0) {
$(".div_item").css('display', 'block');//如果什么都没填，跳出，保持全部显示状态
return;
}
$(".div_item").css('display', 'none');//如果填了，先将所有的选项隐藏
for (var i = 0; i < $(".div_item").length; i++) {
//模糊匹配，将所有匹配项显示
if ($(".div_item").eq(i).text().substr(0, $("#txt1").val().length) == $("#txt1").val()) {
$(".div_item").eq(i).css('display', 'block');
}
}
});
//项点击
$(".div_item").click(function () {
$("#txt1").val($(this).text());
});
</script>
</body>
</html>
# 实现页面整屏切换
<!DOCTYPE html>
<html>
<head lang="ch">
<meta charset="UTF-8">
<meta name=”viewport” content="width=device-width, user-scalable=no, initial-scale=1.0">
<title></title>
<style>
body, html{
padding: 0;
margin: 0;
}
body, html {
height: 100%;
overflow: hidden;
}
#container, .section {
height: 100%;
}
.section {
background-color: #000;
background-size: cover;
background-position: 50% 50%;
}
#section0 {
background-color: #83af9b;
}
#section1 {
background-color: #764d39;
}
#section2 {
background-color: #ff9000;
}
#section3 {
background-color: #380d31;
}
</style>
</head>
<body>
<div id="container">
<div class="section" id="section0"></div>
<div class="section" id="section1"></div>
<div class="section" id="section2"></div>
<div class="section" id="section3"></div>
</div>
<script src="http://code.jquery.com/jquery-latest.js"></script>
<script>
var curIndex = 0;
var container = $("#container");
var sumCount = $(".section").length;
var $window = $(window);
var duration = 500;
//时间控制
var aniTime = 0;
var scrollFunc = function (e) {
//如果动画还没执行完，则return
if(new Date().getTime() < aniTime + duration){
return;
}
e = e || window.event;
var t = 0;
if (e.wheelDelta) {//IE/Opera/Chrome
t = e.wheelDelta;
if (t > 0 && curIndex > 0) {
//上滚动
movePrev();
} else if (t < 0 && curIndex < sumCount - 1) {
//下滚动
moveNext();
}
} else if (e.detail) {//Firefox
t = e.detail;
if (t < 0 && curIndex > 0) {
//上滚动
movePrev();
} else if (t > 0 && curIndex < sumCount - 1) {
//下滚动
moveNext();
}
}
};
function moveNext(){
//获取动画开始时的时间
aniTime = new Date().getTime();
container.css("transform", "translate3D(0, -" + (++curIndex) * $window.height() + "px, 0)");
}
function movePrev(){
//获取动画开始时的时间
aniTime = new Date().getTime();
container.css("transform", "translate3D(0, -" + (--curIndex) * $window.height() + "px, 0)");
}
function init(){
/*注册事件*/
if (document.addEventListener) {
document.addEventListener('DOMMouseScroll', scrollFunc, false);
}//W3C
window.onmousewheel = document.onmousewheel = scrollFunc;//IE/Opera/Chrome
container.css({
"transition": "all 0.5s",
"-moz-transition": "all 0.5s",
"-webkit-transition": "all 0.5s"
});
}
init();
</script>
</body>
</html>
# 实现一个瀑布流效果
var left_top=$(".left_div>div:last-child").offset().top
var right_top=$(".right_div>div:last-child").offset().top
if(left_top<=right_top){
$(".left_div").append(img_info)
}else{
$(".right_div").append(img_info)
}
# 实现一个树组件
# 实现一个购物车动效
# 实现函数找到DOM的绝对位置
function get_layout(ele){
const layout={
width:ele.offsetWidth,
height:ele.offsetHeight,
left:ele.offsetLeft,
top:ele.offsetTop
}
if(ele.offsetParent){
const parentLayout=get_layout(ele.offsetParent);
layout.left+=parentLayout.left;
layout.top+=parentLayout.top;
}
return layout;
}
# 子数组整除：写一个函数，给定一个数组，判断数组中某一项，或者任意多项的和，是否被另一个整数整除。比如：solve([3,5,8],13)=true;solve([3,9],15)=false;solve([7,8,2],7)=true;solve([1,2,3],6)=true
function solve(arr,N){
const s=new Set([arr.shift()%N]);
while(arr.length>0){
const ak=arr.shift();
const items=[...s];
items.forEach(x=>{
s.add((x+ak)%N);
})
s.add(ak)
}
return s.has(0);
}
# 实现一段脚本，使得点击对应链接alert出响应的编号
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<body>
<a href="#">第一个链接</a></br>
<a href="#">第二个链接</a></br>
<a href="#">第三个链接</a></br>
<a href="#">第四个链接</a></br>
</body>
<script>
let aGroup=document.getElementsByTagName('a');
let i=0;
for(let a of aGroup){
a.onclick=(function(i){
return function(){
alert(i);
}
})(++i)
}
</script>
# 用纯JS实现，点击一个列表时，输出对应的索引？
方式一：
for(let i = 0,
len = lis.length;
i < len; i++){
lis[i].addEventListener('click',
function () {
console.log(i);
}, false);
}
方式二：
for(var i = 0,
len = lis.length;
i < len; i++) {
(function (i) {
lis[i].addEventListener
('click', function () {
console.log(i);
}, false);
})(i)
}
方式三：
let ul = document.querySelector('ul');
let lis = document.querySelectorAll('ul li');
ul.addEventListener('click',
function (e) {
let target = e.target;
if(target.nodeName.toLowerCase() === 'li') {
console.log([].indexOf.call(lis, target));
}
}, false);
# 点击按钮发出ajax请求，如何防止用户在此请求方式返回之前再次点击?
// 点击提交按钮的时候，
// 把这个提交这个处理函数给解绑掉，
// 请求完成的时候在绑定回来
function clickHandler(){
$(this).unbind('click', clickHandler);
$.ajax({
url : 'url',
dataType : 'json',
type : 'post',
success : function (data) {
if (data.success) {
//提交成功做跳转处理
} else {
//处理失败，重新绑定点击事件
$(self).click(clickHandler);
}
}
});
}
$('#itlike').click(clickHandler);
// 可以点击后让按钮不可用,
// 如果提交失败可以再次设置为可用
// 1.让按钮不可用
$("#itlike").attr("disabled","disabled");
$.ajax({
url : 'url',
dataType : 'json',
type : 'post',
success : function (data) {
if (data.success) {
// 提交成功做跳转处理
} else {
// 处理失败，重新绑定点击事件
// 2. 让按钮可用
$("#itlike").removeAttr("disabled");
}
}
});
# iOS safari 如何阻止“橡皮筋效果”？
$(document).ready(function(){
var stopScrolling = function(event) {
event.preventDefault();
}
document.addEventListener('touchstart', stopScrolling, false);
document.addEventListener('touchmove', stopScrolling, false);
});
# N个数字和为M的问题(今日头条)
// 给定一个不重复的正整数集合，从中取N个数字，使得它们的和为M，写一个函数，求这N个数字。如有多个，只需要返回一个
function sumN(A,n,m,i=0,decisions=[]){
if(m===0){
return decisions
}
if(i===A.length || n===0 || m<0){
return null
}
return sumN(A,n-1,m-A[i],i+1,decisions.concat(A[i])) || sumN(A,n,m,i+1,decisions)
}
优化
function sumN(A,n,m){
// 最终结果
let r=null;
// 决策
const decisions=[];
function inner(i=0,n,m){
// 如果已有结果，终止递归
if(r){return}
// 如果m=0，找到一个解
if(m===0){
r=decisions.slice();
return
}
// 没有找到解的情况
if(i===A.length || n===0 || m<0){
return
}
decisions.push(A[i]);
inner(i+1,n-1,m-A[i]);
decisions.pop(A[i]);
inner(i+1,n,m)
}
inner(0,n,m);
return r;
}
利用位运算
function sumByBinaryCode(A,code){
const max=1 << A.length;
const p=[];
let sum=0;
for(let i=0;i<A.length;i++){
if(code & (1<<i)){
sum+=A[i];
p.push(A[i])
}
}
return {sum,p}
}
function sumN(A,n,m){
const max=1 << A.length;
for(let i=0;i<max;i++){
const {sum,p}=sumByBinaryCode(A,i);
if(sum===m){
return p
}
}
return null;
}
# 火车车厢重排问题(今日头条)
// 给定一列火车，利用左侧的环状铁轨对火车车厢进行重新排序，给定初始顺序和排序后的顺序，写一个函数，判断这样是否可行？
function isTrans(o,t){
const q=[];
for(let x of t){
if(q[q.length-1]===x){
q.pop()
}
let y=null;
while(o.length >0 && (y=o.shift()) !== x){
q.unshift(y);
}
}
return q.length === 0;
}
优化
function isTrans(o,t){
const q=new Queue();
for(let x of t){
if(q.peek()===x){
q.dequeue()
}
let y=null;
while(o.size()>0 && (y=o.dequeue()) !== x){
q.enqueue(y)
}
}
return q.size()===0
}
# 数网格中的路径(阿里、美团)
// 小虫子从A到B，只能沿着网格走，每次只能向右或向下。求有多少种走法？
function f(x,y){
if(x>0 && y>0){
return f(x-1,y)+f(x,y-1)
}else if(x>0){
return f(x-1,y)
}else if(y>0){
return f(x,y-1)
}else{
return 1
}
}
优化
function f(x,y,dp=[]){
if(!dp[y]){
dp[y]=[]
}
if(dp[y][x] !== undefined){
return dp[y][x]
}
if(x>0 && y>0){
dp[y][x]= f(x-1,y,dp)+f(x,y-1,dp)
}else if(x>0){
dp[y][x]= f(x-1,y,dp)
}else if(y>0){
dp[y][x]= f(x,y-1,dp)
}else{
dp[y][x]= 1
}
return dp[y][x]
}
# 使用Object.defineProperty()模拟实现Vue的绑定原理
题目：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
</head>
<body>
<h1>Welcome</h1>
<h2>积分:<span>{{score}}</span></h2>
<h1>用户名:<span>{{uname}}</span></h1>
<h2>积分:<span>{{score}}</span></h2>
<script>
var data={
uname:'dingding',
score:3000
}
</script>
</body>
</html>
答案：