编程基本能力

Array.js

/// flatten array
// 1. absolute flatten, no depth param
// [[1,[2,[[3]]]],4,[5,[[[6]]]]] => [1,2,3,4,5,6]
const flatten = list => list.reduce(
	(a, b) => a.concat(Array.isArray(b) ? flatten(b) : b), []
)

// recursive
function flatten(arr, result = []) {
    arr.forEach(item => {
        if (Object.prototype.toString.call(item) === '[object Array]') {
            result = result.concat(flatter(item, []))
        } else {
            result.push(item)
        }
    })
    return result
}

// 2. with depth param
function flatten(arr, depth = Infinity) {
	return arr.reduce((newArr, nextArr) => {
		return newArr.concat(
			depth > 1 && Array.isArray(nextArr) ?
			 flatten(nextArr, depth - 1) :
			  nextArr), []
	})
}

/// compose
// 可以传多个参数进去
/**
 * github: https://github.com/reduxjs/redux/blob/master/src/compose.js
 * @params {...function} [funcs] 函数
 */
function compose(...funcs) {
	if (funcs.length === 0) {
		return arg => arg
	}
	if (funcs.length === 1) {
		return funcs[0]
	}
	return funcs.reduce((a, b) => (...args) => a(b(...args)))
}
// 分解
let fn = compose(
	returnC,
	returnB,
	returnA
)
fn('D')
// core 
[returnC, returnB, returnA].reduce((fn, nextFn) => {
	return (...args) => fn(nextFn(...args))
})
// 最后嵌套的函数
fn = (...args) => returnC(returnB(returnA(...args)))
const returnA = letter => {
	console.log(letter)
	return 'A'
}
const returnB = letter => {
	console.log(letter)
	return 'B'
}
const returnC = letter => {
	console.log(letter)
	return 'C'
}
let lastLetter = compose(
	returnC,
	returnB,
	returnA
)('D')
console.log(lastLetter) // C
// output: D A B C

/// Building-blocks to use for composition
const double = x => x + x;
const triple = x => 3 * x;
const quadruple = x => 4 * x;

// Function composition enabling pipe functionality
// 与compose函数相比，除了调用顺序是反过来，还有一个就是传参的问题了
// pipe只能传一个参数进来, 跟管道的形象也是很相符的
const pipe = (...functions) => input => functions.reduce(
    (acc, fn) => fn(acc),
    input
);

/// reduce mock
// https://github.com/lodash/lodash/blob/master/.internal/arrayReduce.js
function arrayReduce(array, iteratee, accumulator) {
	let index = -1
	const length = array == null ? 0 : array.length
  
	if (arguments.length < 3 && length) {
	  accumulator = array[++index]
	}
	while (++index < length) {
	  accumulator = iteratee(accumulator, array[index], index, array)
	}
	return accumulator
  }
	
// 迭代
// recusive， 不支持reducer的第三四个参数即index, array
// acc === accumulate(累积)
function reduce(arr, acc, callback) {
	if (arr.length === 0) {
		return acc
	}
	let [head, ...rest] = arr
	return reduce(rest, callback(acc, head), callback)
}

// loop
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce
Object.defineProperty(Array.prototype, 'reduce', {
	value: function (callback) {
		var o = Object(this);
		var len = o.length >>> 0;
		var k = 0;
		var value;

		if (arguments.length >= 2) {
			value = arguments[1];
		} else {
			while (k < len && !(k in o)) {
				k++;
			}

			if (k >= len) {
				throw new TypeError('Reduce of empty array ' +
					'with no initial value');
			}
			value = o[k++];
		}

		while (k < len) {
			if (k in o) {
				value = callback(value, o[k], k, o);
			}
			k++;
		}

		return value;
	}
})

//判断是否是数组
var is_array = function (value) {
	/*return value&&
		typeof value === "object"&&
		value.constructor === Array;*/ //得value所在的window对象跟当前的window是同一个。不同的页面框架(frames)有不同的Window对象
	return Object.prototype.toString.call(value) === "[object Array]";
};
//数组的初始化构造
new Array(num);

Array.dim = function (dimention, initial) {
	var a = [],
		i;
	for (i = 0; i < dimention; i += 1) {
		a[i] = initial;
	}
	return a;
};
var a5 = Array.dim(5, 0);


//Array.prototype.reduce && Array.prototype.reduceRight
var dupArray = [
	[1, 3],
	[2, 4],
	[5, 7]
];
var ret2 = dupArray.reduce(function (memory, value) {
	return memory.concat(value);
}, [9]);
console.log("ret2: ", ret2);
//=> [9, 1, 3, 2, 4, 5, 7]

clone.js

/// deep copy
var target = {
    field1: 1,
    field2: undefined,
    field3: {
        child: 'child'
    },
    field4: [2, 4, 8],
    field5: /39023\w9/
};
target.target = target;

// 使用weakMap来防止内存溢出
// https://blog.nowcoder.net/n/217d7a3f7b25417793e8546cd4ae9087
// lodash cloneDeep: https://github.com/lodash/lodash/blob/master/.internal/baseClone.js
// 1、null/date/regexp值的处理，对于date是new Date()深复制
// 2、使用子weakMap来存储循环引用
// 3、复制对象的原型链，new target.constructor()
function clone(target, map = new WeakMap()) {
  if (target === null) return null
  if (target instanceof RegExp) {
    const newTarget = new RegExp(target.source, target.flags)
    newTarget.lastIndex = target.lastIndex
    return newTarget
  }
  if (target instanceof Date) return new Date(target.getTime())
  if (typeof target !== 'object') return new Ctor(target)
  if (map.has(target)) return map.get(target)
  if (Array.isArray(target)) return target.map(item => clone(item, map))

  // const cloneTarget = new Ctor()
  const cloneTarget = Object.create(Object.getPrototypeOf(target))
  // 实现了对象引用自身，在cloneTarget返回之前就赋值
  map.set(target, cloneTarget);
  return Object.getOwnPropertyNames(target).reduce((o, p)=> {
    Object.defineProperty(o, p, Object.getOwnPropertyDescriptor(o, p))
    o[p] = clone(target[p], map)
    return o
  }, cloneTarget)
}

let clone1 = clone(target)
console.log(clone1)

Date.js

// new Date('2019/01/02')时的标准格式
// http://www.ecma-international.org/ecma-262/5.1/#sec-15.9.1.15
// 等同于2019-01-02T08:00:00z YYYY-MM-DD 这种是标准格式，默认是带当前时区的，也就是GMT+8。
new Date('2019-01-02')
// 其他格式的datestring， 解析后不会有当前时区,
// 以下的都等同于2019-01-02T00:00:00
new Date('2019-01-2')
new Date('2019-1-02')
new Date('2019/01/02')

Express.md

MiddlerMire(中间件)

http://expressjs.com/zh-cn/guide/using-middleware.html

模拟实现

let express = function () {
    let pipelines = []
    let app = (req, res) => {
        let i = 0

        function next () {
            let pipeline = pipelines[i++]
            if (!pipeline) return
            pipeline(req, res, next)
        }
        next()
    }
    app.use = (middleware) => {
        pipelines.push(middleware)
    }

    return app
}

let app = express()
app.use((req, res, next) => {
    console.log('middleware1')
    req.teal = 'foo'
    next()
})
app.use((req, res, next) => {
    console.log('middleware2')
    res.end(req.teal)
})
app.use((req, res, next) => {
    // 这里还是会执行，在expressjs里不会
    console.log('middleware3')
})

require('http').createServer(app).listen(3000)

Function.js

'use strict'

/// 柯里化(curry)
// 把函数当作参数，返回另外一个函数
function curry(fn, params) {
    let slice = Array.prototype.slice
    let args = slice.call(params)

    return function () {
        return fn.apply(null, args.concat(slice.call(arguments)))
    }
}

/**
 * 记忆(memorize)
 * @param {function} fn
 * @param {function} hasher 用于生成cache的key值，因为缓存对象的key值得是字符串
 * @returns function
 */
function memorize(fn, hasher, initObj = {}) {
    let memorize = function (key) {
        let address = '' + (hasher ? hasher.apply(this, arguments) : key)
        let cache = memorize.cache
        if (!cache.hasOwnProperty(address)) {
            cache[address] = fn.apply(this, arguments)
        }
        return cache[address]
    }
    memorize.cache = initObj
    return memorize
}

/// region throttle & debounce & requestAnimateRequest
// 操作演示：https://css-tricks.com/the-difference-between-throttling-and-debouncing/

/// 节流(throttle)
// 一段时间内限制函数!!至多调用一次!!
// `requestAnimationFrame`，浏览器内置的节流工具(https://jinlong.github.io/2016/04/24/Debouncing-and-Throttling-Explained-Through-Examples/)

function throttle(fn, wait) {
    let timeout, context, args, result;
    let previous = 0;

    var later = function () {
        previous = 0;
        timeout = null;
        result = func.apply(context, args);
        if (!timeout) context = args = null;
    };

    var throttled = function () {
        var now = Date.now();
        if (!previous) previous = now;
        var remaining = wait - (now - previous);
        context = this;
        args = arguments;

        if (remaining <= 0) {
            if (timeout) {
                clearTimeout(timeout);
                timeout = null;
            }
            previous = now;
            result = func.apply(context, args);
            if (!timeout) context = args = null;
        } else if (!timeout) {
            timeout = setTimeout(later, remaining);
        }
        return result
    };

    throttled.cancel = function () {
        clearTimeout(timeout);
        previous = 0;
        timeout = context = args = null;
    };

    return throttled;
}


/**
 * 函数防抖动debounce
 * 保证两次函数之间调用时间间隔不小于某一阀值
 * 场景：对用户输入的结果进行ajax请求、page resize、drag
 * underscore@1.8.3版本函数中，实现了调用时立即执行的参数`immediate`
 *
 * ！！触发时机由调用方决定
 *
 * @param fn
 * @param delay        时间段内只允许调用一次
 * @returns {Function}
 */
function debounce(fn, delay = 50) {
    let timer = null
    let debounced = function () {
        let context = this,
            args = arguments

        clearTimeout(timer)
        timer = setTimeout(function () {
            fn.apply(context, args)
        }, delay)
    }
    debounced.cancel = function () {
        clearTimeout(timer)
        timer = null
    }

    return debounced
}
/**
 * 增加mustRunTime参数，有些场景需要调用下，不然函数一直不执行。比如拖动元素时，一下子到另一个点，没有中间状态
 * 增加了mustRunTime的版本，可能减少了内存回收的次数，因为没有频繁的创建定时器
 *
 * @param mustRunTime  时间段内必须调用一次()
 */
function debouncePlus(fn, delay = 50, mustRunTime) {
    let timer = null
    let lastInvokeTimeStamp

    return function () {
        let args = arguments
        let context = this

        clearTimeout(timer)

        lastInvokeTimeStamp = lastInvokeTimeStamp || +new Date()
        let now = +new Date()
        if (now - lastInvokeTimeStamp >= mustRunTime) {
            fn.apply(context, args)
            lastInvokeTimeStamp = now
        } else {
            timer = setTimeout(function () {
                fn.apply(context, args)
            }, delay)
        }
    }
}
/// endregion

linked-list1.js

let plainData = {
    h1: {
        parent: 'h0',
        name: 'h1'
    },
    h6: {
        parent: 'h5',
        name: 'h6'
    },
    h4: {
        parent: 'h3',
        name: 'h4'
    },
    h2: {
        parent: 'h1',
        name: 'h2'
    },
    h0: {
        parent: '',
        name: 'h0'
    },
    h5: {
        parent: 'h4',
        name: 'h5'
    },
    h3: {
        parent: 'h2',
        name: 'h3'
    },
}
let outData = {
    h0: {
        parent: '',
        name: 'h1',
        h1: {
            parent: 'h0',
            name: 'h1',
            h2: {
                parent: 'h1',
                name:'h2',
                h3: {
                    //...
                }
            }
        }
    }
}

function transData (data) {
    let ret = {}
    for (let key in data) {
        if (data.hasOwnProperty(key)) {
            let item = data[key]
            if (item.parent === '') {
                ret = item
            } else {
                // linked list  链表
                data[item.parent][key] = item
            }
        }
    }

    return ret
}

linked-list2.js

let areaData = [{
    "province": "浙江",
    "city": "杭州",
    "name": "西湖"
}, {
    "province": "四川",
    "city": "成都",
    "name": "锦里"
}, {
    "province": "四川",
    "city": "成都",
    "name": "方所"
}, {
    "province": "四川",
    "city": "阿坝",
    "name": "九寨沟"
}]

const transAreaData = function (data, keys) {
    let res = [], hash = {}
    for(let item of data) {
        let arr = res, cur = hash
        for (let j= 0, k = keys.length; j <k ;j++) {
            let key = keys[j], field = item[key]
            if (!cur[field]) {
                let pusher = {
                    value: field,
                }, tmp
                if (j < k-1) {
                    tmp = []
                    pusher.children = tmp
                }
                cur[field] = {$: arr.push(pusher) - 1}
                cur = cur[field]
                arr = tmp
            } else {
                cur = cur[field]
                arr = arr[cur.$].children
            }
        }
    }
    return res
}

let areaOutData = [
    {
        value: '浙江',
        children: [
            {
                value: '杭州',
                children: [
                    '西湖'
                ]
            }
        ]
    },
    {
        value: '四川',
        children: [
            {
                value: '成都',
                children: [
                    '锦里',
                    '方所'
                ]
            },
            {
                value: '阿坝',
                children:[
                    '九寨沟'
                ]
            }
        ]
    }
]

tree1.js

/**
 * 联系人列表的排序
 * 字典序
 * lexicographical order
 */

// input data, 客户列表，已按首字母排好序了
var inputData = [
  {
    firstSpell: "A",
    name: "adobe"
  },
  {
    firstSpell: "A",
    name: "alpha"
  },
  {
    firstSpell: "B",
    name: "before"
  }
];
// out data, 按首字母分组
var outData = [
  {
    key: "A",
    values: [
      {
        firstSpell: "A",
        name: "adobe"
      },
      {
        firstSpell: "A",
        name: "alpha"
      }
    ]
  },
  {
    key: "B",
    values: [
      {
        firstSpell: "B",
        name: "before"
      }
    ]
  }
];
/**
 *
 * 'A' => unicode 65
 * @param {array} input
 */
function convert1(input) {
  let charCodeOfA = "A".charCodeAt(0),
    c = charCodeOfA;
  let ret = Array.apply(null, { length: 26 }).map(v => {
    return {
      key: String.fromCharCode(c++),
      values: []
    };
  });
  console.log(ret);
  for (let item of input) {
    let key = item.firstSpell.charCodeAt(0) - charCodeOfA;
    ret[key].values.push(item);
  }
  return ret;
}

console.log(convert1(inputData));

// expolit 20171025
function convert2() {
  // ['A', 'B']
  var alphaList = [];
  var lists = {};
  inputData.forEach(item => {
    let firstSpell = item.firstSpell.toUpperCase();
    if (!lists[firstSpell]) {
      // 在这里就合数据了
      alphaList.push(firstSpell);
      lists[firstSpell] = [];
    }
    lists[firstSpell].push(item);
  });

  // [{key: 'A', values: []}]
  return alphaList.reduce((ans, alpha) => {
    ans.push({
      key: alpha,
      values: lists[alpha]
    });
    return ans;
  }, []);
}

tree2.js

let nodes = [{
    name: '一',
    id: 1,
    childs: [{
        name: '一一',
        id: 11,
        pid: 1,
        childs: [{
          name: '一一一',
          id: 111,
          pid: 11,
        }]
      },
      {
        name: '一二',
        id: 12,
        pid: 1,
        childs: [{
          name: '一二一',
          id: 121,
          pid: 12,
        }]
      }
    ]
  },
  {
    name: '二',
    id: 2,
    childs: [{
      name: '二一',
      id: 21,
      pid: 2,
      childs: [{
        name: '二一一',
        id: 211,
        pid: 21
      }]
    }]
  }
]

/**
 * 给node添加深度属性
 * @param {array} nodes 
 * @param {number} initialDeep 
 */
function markDeep(nodes, initialDeep = 0) {
  for (let node of nodes) {
    let deep = initialDeep
    node.deep = deep
    markDeep(node.childs || [], ++deep)
  }
}

markDeep(nodes)

/**
 * 使节点变成扁平的
 * @param {array} nodes 
 */
function flattenNodes(nodes) {
  let stack = [].concat(nodes),
    ret = []
  while (stack.length) {
    // 可以考虑使用stack.pop()，也不会出现下面的子节点在父节点前面
    let node = stack.shift()
    ret.push(node)
    if (node.childs) {
      // 这样会导致子节点在父节点前面
      stack = node.childs.concat(stack)
    }
    delete node.childs
  }
  return ret
}

/**
 * 返回flatNodes指定节点的上一个deep为t的节点 ? 
 * @param {array} flatNodes
 * @param {number} t
 * @return {object}
 */
function getPrevPrimaryNode(flatNodes, t) {
  let node = null
  for (let n = flatNodes[t].deep > 0 ? 2 : 1; n--; n > 0)
    do {
      node = flatNodes[--t]
    } while (node && node.deep > 0);
  return t < 0 ? null : node
}

/**
 * 扁平数据，结构化，成为树的结构
 * 
 * 下面的解法用了对象的引用
 * nodes里的每个节点都被父节点引用(除了root node)，操作引用节点，父节点也就改变了
 * @param {array} flatNodes 
 */
function structureNodes(flatNodes) {
  let ret = flatNodes[0],
    reverseNodes = flatNodes.reverse()
  for (let node of reverseNodes) {
    let pid = node.pid
    let target = reverseNodes.find(v => v.id === pid)
    // root node have no pid, so target===undefined
    if (target) {
      target.childs = target.childs || []
      target.childs.push(node)
    }
  }
  return ret
}

let flatNodes = flattenNodes(nodes)
console.log(flatNodes)
console.log(JSON.stringify(structureNodes(flatNodes)))

trie.js

/**
 * 前缀树/字符串树
 *
 * 可以用来Autocomplete查找搜索词匹配，对字典省空间
 * 时间复杂度：O(m) m为单词长度
 * 空间复杂度：O(1)
 *
 * Demo: 
 * let trie = new Trie()
 * trie.insert(['app', 'apple', 'origin', 'crossorigin', 'pjpeg'])
 * console.dir(JSON.stringify(trie.data))
 * console.log(trie.search('pjpeg'))
 * console.log(trie.startsWith('app'))
 * 
 * video: https://www.youtube.com/watch?v=f48wGD-MuQw
 * practice: https://leetcode.com/problems/implement-trie-prefix-tree/description/
 */

class Trie {
    constructor () {
        this.data = {}
    }

    /**
     * 插入一个单词
     * @param word
     */
    insert (words) {
        if (typeof words === 'string') {
            words = [words]
        }

        for (let word of words) {
            let d = this.data
            for (let c of word) {
                if (!d[c]) {
                    d[c] = {
                        $: false,  //是否是单词的最后一个
                    }
                }
                d = d[c]
            }
            d.$ = true
        }

        return this
    }

    /**
     * 最大程度找到单词在树中最后一个字符位置
     * @param word string
     * @returns Object
     */
    find (word) {
        let d = this.data
        for(let i of word) {
            if (!d[i]) {
                return null
            }
            d = d[i]
        }
        return d
    }

    /**
     * 查看单词是否出现
     * @param word String
     * @returns {boolean}
     */
    search (word) {
        let match = this.find(word)

        return !!(match && match.$)
    }

    /**
     * 查看单词中，是否有prefix的前缀
     * @param prefix string
     * @returns {boolean}
     */
    startsWith (prefix) {
        let match = this.find(prefix)

        return !!match
    }

}

module.exports = Trie