每日前端手写题--day4
第四天要刷的手写题如下：
- 手写一个函数，实现柯里化功能
- 手写一个函数，实现数组扁平化的功能
- 手写一个函数，实现数组去重的功能
下面是我自己写的答案：
1. 手写一个函数，实现柯里化功能
分析： 柯里化的本质是**收集到一定数量的参数（称为生产资料更为合适）**之后才去执行既定的函数，如果参数的数目小于既定函数执行所需要的个数则不执行，而是继续收集参数。
如果用代码来表示，可以设既定函数为f，柯里化之后映射成为函数g，g在执行的时候会对积累到的参数的数目进行判断，如果数目是足够的，则返回f的执行结果（相当于执行了f），如果参数的数目不够，则将此次调用传入的参数累积起来，然后返回函数g'，等待下一次调用。**返回的g'函数和g具有相同的德行。
根据上面的分析，首先需要一个私有域存储已经收集到了的参数，这就需要用到闭包了；而执行既定函数的参数数目可以直接从既定函数上获取：f.length表示函数需要的形参数目。
现在尝试性的写一下：
function _G (f) {
if(typeof f !== "function") throw new Error('f must be a function!');
return function (...rest) {
const currentParams = [...rest];
const currentLength = currentParams.length;
if(currentLength >= f.length) return f.apply(this, currentParams);
// return _G(f); ???
}
}
这里无法处理参数不够的时候如何返回一个g'的问题。上面分析到g'和g性质相同，所以g'和g都是由_G产生的，所以问题出在_G没有设计好，一个参数根本无法区分g'和g。
于是，需要增加一个形参，表示目前g类已经收集到的参数：
function _G (f, alreadyCollectedParams = []) {
if(typeof f !== "function") throw new Error('f must be a function!');
return function (...rest) {
const currentParams = [...alreadyCollectedParams, ...rest];
const currentLength = currentParams.length;
if(currentLength >= f.length) return f.apply(this, currentParams);
return _G(f, currentParams);
}
}
function add (a,b,c) {
return a+b+c;
}
const c_add = _G(add);
console.log(c_add(1)(2)(3)); // 6
console.log(c_add(1, 2)(3)); // 6
console.log(c_add(1)(2, 3)); // 6
console.log(c_add(1, 2, 3)); // 6
使用ES6创建极简版：
// 极简版
// const __G = (f, alreadyCollectedParams = []) => (...rest) => [...alreadyCollectedParams, ...rest].length >= f.length ? f.apply(this, [...alreadyCollectedParams, ...rest]) : _G(f, currentParams);
const __G = (f, a = []) => (...r) => (_ = [...a, ...r], _.length >= f.length ? f.apply(this, _) : __G(f, _));
2. 手写一个函数，实现数组扁平化的功能
所谓数组扁平化指的就是如果数组中的元素依然是数组，则将内嵌数组中的元素拿出来直接放到上层数组中即可。
2.1 方法一：forEach 和 push
一个最基本的想法就是，创建一个_flat方法用来遍历这个数组，然后再在历过程中对数组中的每一个元素进行判断；如果元素的类型不是数组则直接push到记录数组中去，如果元素的类型是数组，则对此内嵌数组递归调用_flat; 这样相当于对任何一级的数组的每一个元素都进行了遍历，也就是使用深度遍历算法。
function _flat (targetArray, container = []) {
if(!Array.isArray(targetArray)) return container;
targetArray.forEach(
item => {
if (!Array.isArray(item)) {
container.push(item);
} else {
_flat(item, container);
}
}
)
return container;
}
const rst = _flat([[[[[[1],2],3],4],5,6],7]);
// const rst = _flat('[[[[[[1],2],3],4],5,6],7]');
console.log('rst: ', rst);
2.2 方法二: Array.prototype.flat
ES6中Array的原型上增加了一个名为flat的方法，其作用就是将嵌套数组拆包一次；显然没拆一次，整个数组的元素数目是（非严格）单调递增的；根据这个性质，使用while循环一直对其拆包，直到某两次拆完之后元素数目相等.
function _flat2 (targetArray) {
if(!Array.isArray(targetArray)) return [];
let _loop = targetArray;
while(1){
const beforeFlat = _loop.length;
const _Arr = _loop.flat();
const afterFlat = _Arr.length;
if(beforeFlat == afterFlat) return _Arr;
_loop = _Arr;
}
}
const rst2 = _flat2([[[[[[1],2],3],4],5,6],7]);
console.log('rst2: ', rst2);
2.3 方法三: findIndex 和 splice
如果在遍历之前就知道为内嵌数组元素的序列号就好了，这样只需要到对应的位置上找到并将其展开就可以了；这个过程一直持续到原数组中再也找不到内嵌数组元素就停止下来。 这种方法是在原来的数组上直接操作的，会改变原数组的内容
function _flat3 (targetArray) {
if(!Array.isArray(targetArray)) return [];
while(1){
const arrItemIndex = targetArray.findIndex(
item => Array.isArray(item)
)
if(arrItemIndex === -1) return targetArray;
targetArray.splice(arrItemIndex, 1, ...targetArray[arrItemIndex]);
}
}
const rst3 = _flat3([[[[[[1],2],3],4],5,6],7]);
console.log('rst3: ', rst3);
2.4 方法四: stack
- 使用栈这种数据结果，其本质上和递归的算法是完全相同的；但是使用栈来理解的话，会极大的减小心智负担
- 使用两个栈a和b，开始的时候将原始数组整体放入到a栈中去，此时b栈为空；
- 然后对a栈执行下面的动作，直到a栈为空：
- 弹栈->判断弹出元素是否是数组，如果不是，则进入栈b，如果是则拆包一次，再重新进入栈a
- 最后输出栈b即可
function _flat4 (targetArray) {
if(!Array.isArray(targetArray)) return [];
// 原始数组全部入a栈
const a = [...targetArray];
const b = [];
while(a.length){
const _tmp = a.pop();
if (Array.isArray(_tmp)) {
a.push(..._tmp); // 这里不要遍历push，显得很low，a.concat(_tmp)也可
} else {
b.push(_tmp);
}
}
return b;
}
const rst4 = _flat4([[[[[[1],2],3],4],5,6],7]);
console.log('rst4: ', rst4);
不行了，太多方法了，写不过来了，有兴趣的话写在评论去吧~
3. 手写一个函数，实现数组去重的功能
就是字面意思，不难理解！
3.1 利用set对象的机制，将数组先变成set然后将set再变成数组
// 一行搞定
const unique = (array) => [...newSet(array)];
3.2 继续使用两个栈
- 继续使用两个栈a和b，a执行下面的动作直到空栈
- 弹栈->判断弹出元素在b栈中是否存在，如果存在丢弃，如果不存在进入栈b
const unique2 = (array) => {
if(!Array.isArray(array)) return [];
const a = [...array];
const b = [];
while(a.length){
const item = a.pop();
// const item = a.shift();
if(b.includes(item)) continue;
b.push(item);
}
return b;
}
可以将pop改成shift有利于保证顺序
3.3 3.2改进版本
对上面的实现方式进行优化，因为数组通过内容查询元素的效率实在是太低了，所以将b从栈改成字典，字典一般是使用hash表实现的，在根据查找方面比数组要快
const unique3 = (array) => {
if(!Array.isArray(array)) return [];
const a = [...array];
const b = new Map();
while(a.length){
const item = a.pop();
// const item = a.shift();
b.set(item,1);
}
return [...b.keys()];
}
console.log(unique3([1,1,1,1,2,3,4,345,345]));