leetcode for js

简单题

2695. 包装数组 ⭐⭐⭐⭐⭐

描述：
创建一个名为 ArrayWrapper 的类，它在其构造函数中接受一个整数数组作为参数。该类应具有以下两个特性：

• 当使用 + 运算符将两个该类的实例相加时，结果值为两个数组中所有元素的总和。
• 当在实例上调用 String() 函数时，它将返回一个由逗号分隔的括在方括号中的字符串。例如，[1,2,3] 。

示例：

输入：nums = [[1,2],[3,4]], operation = "Add"
输出：10
解释：
const obj1 = new ArrayWrapper([1,2]);
const obj2 = new ArrayWrapper([3,4]);
obj1 + obj2; // 10

思路：
主要考察 JavaScript 的隐式类型转换，即对对象进行运算和字符串操作时会尝试调用对象的 valueOf 和 toString 方法.

解法：

var ArrayWrapper = function(nums) {
    this.nums = nums;
};
ArrayWrapper.prototype.valueOf = function() {
    return this.nums.reduce((a, b) => a + b);
};
ArrayWrapper.prototype.toString = function() {
    return '[' + this.nums.join(',') + ']';
};

2677. 分块数组

描述：
给定一个数组 arr 和一个块大小 size ，返回一个 分块 的数组。分块 的数组包含了 arr 中的原始元素，但是每个子数组的长度都是 size 。如果 arr.length 不能被 size 整除，那么最后一个子数组的长度可能小于 size 。

示例：

输入：arr = [1,2,3,4,5], size = 1
输出：[[1],[2],[3],[4],[5]]
解释：数组 arr 被分割成了每个只有一个元素的子数组

解法：

var chunk = function(arr, size) {
  const ans = []
  for (let i = 0; i < arr.length; i += size) {
    ans.push(arr.slice(i, i + size))
  }
  return ans
};

2666. 只允许一次函数调用

描述：
给定一个函数 fn ，它返回一个新的函数，返回的函数与原始函数完全相同，只不过它确保 fn 最多被调用一次。

• 第一次调用返回的函数时，它应该返回与 fn 相同的结果。
• 第一次后的每次调用，它应该返回 undefined 。

示例：

输入：fn = (a,b,c) => (a + b + c), calls = [[1,2,3],[2,3,6]]
输出：[{"calls":1,"value":6}]
解释：
const onceFn = once(fn);
onceFn(1, 2, 3); // 6
onceFn(2, 3, 6); // undefined, fn 没有被调用

解法：

// 闭包
var once = function(fn) {
  let called = false
  let ans
  return function(...args) {
    if (!called) {
      called = true
      ans = fn(...args)
    }
    return ans
  }
};

// finally新特性
var once = function(fn) {
    return function(...args){
        try{
            return fn(...args);
        }
        // finally的内容会在return后执行
        finally{
            fn = () => {}
        }
    }
}

2665. 计数器 II

描述：
请你写一个函数 createCounter. 这个函数接收一个初始的整数值 init  并返回一个包含三个函数的对象。
这三个函数是：

• increment() 将当前值加 1 并返回。
• decrement() 将当前值减 1 并返回。
• reset() 将当前值设置为 init 并返回。
  示例

输入：init = 5, calls = ["increment","reset","decrement"]
输出：[6,5,4]
解释：
const counter = createCounter(5);
counter.increment(); // 6
counter.reset(); // 5
counter.decrement(); // 4

解法：

var createCounter = function(init) {
    let value = init;
    const increment = () => {
        value += 1;
        return value;
    };
    const decrement = () => {
        value -= 1;
        return value;
    };
    const reset = () => {
        value = init;
        return value;
    };
    return {increment, decrement, reset};
};

2648. 生成斐波那契数列 ⭐⭐⭐⭐⭐

描述：
请你编写一个生成器函数，并返回一个可以生成 斐波那契数列 的生成器对象。斐波那契数列 的递推公式为 Xn = Xn-1 + Xn-2 。这个数列的前几个数字是 0, 1, 1, 2, 3, 5, 8, 13 。
示例：

输入：callCount = 5
输出：[0,1,1,2,3]
解释：
const gen = fibGenerator();
gen.next().value; // 0
gen.next().value; // 1
gen.next().value; // 1
gen.next().value; // 2
gen.next().value; // 3

解法：

// 闭包
var fibGenerator = function() {
    let a = 0, b = 1;
    return {
        next: function() {
            const value = a;
            a = b;
            b = value + b;
            return {value};
        }
    };
};

// 生成器
var fibGenerator = function*() {
    const dp = Array(51);
    dp[0] = 0;
    dp[1] = 1;
    for(let i=2;i<51;i++)
        dp[i] = dp[i-1] + dp[i-2];
    while(dp.length){
        yield dp.shift();
    }
};

2626. 数组归约运算 - reduce

描述：
请你编写一个函数，它的参数为一个整数数组 nums 、一个计算函数 fn 和初始值 init 。返回一个数组 归约后 的值。
你可以定义一个数组 归约后 的值，然后应用以下操作： val = fn(init, nums[0]) ， val = fn(val, nums[1]) ， val = fn(val, nums[2]) ，… 直到数组中的每个元素都被处理完毕。返回 val 的最终值。
如果数组的长度为 0，它应该返回 init 的值。

示例：

输入：
nums = [1,2,3,4]
fn = function sum(accum, curr) { return accum + curr; }
init = 0
输出：10
解释：
初始值为 init=0 。
(0) + nums[0] = 1
(1) + nums[1] = 3
(3) + nums[2] = 6
(6) + nums[3] = 10
Val 最终值为 10。

解法：

var reduce = function(nums, fn, init) {
    let ans = init;
    for(let i=0;i<nums.length;i++)
        ans = fn(ans, nums[i]);
    return ans;
};

2635. 转换数组中的每个元素 - map

描述：
编写一个函数，这个函数接收一个整数数组 arr 和一个映射函数  fn ，通过该映射函数返回一个新的数组。返回数组的创建语句应为 returnedArray[i] = fn(arr[i], i) 。
示例：

输入：arr = [1,2,3], fn = function plusone(n) { return n + 1; }
输出：[2,3,4]
解释： 
const newArray = map(arr, plusone); // [2,3,4]
此映射函数返回值是将数组中每个元素的值加 1。

解法：

var map = function(arr, fn) {
    return arr.reduce((pre, cur, index) => {
        pre.push(fn(cur, index));
        return pre;
    }, []);
};

2634. 过滤数组中的元素 - filter

描述：
给定一个整数数组 arr 和一个过滤函数 fn，并返回一个过滤后的数组 filteredArr 。
fn 函数接受一个或两个参数：

• arr[i] - arr 中的数字
• i - arr[i] 的索引
  filteredArr 应该只包含使表达式 fn(arr[i], i) 的值为 真值 的 arr 中的元素。真值 是指 Boolean(value) 返回参数为 true 的值。
  示例：

输入：arr = [0,10,20,30], fn = function greaterThan10(n) { return n > 10; }
输出： [20,30]
解释：
const newArray = filter(arr, fn); // [20, 30]
过滤函数过滤掉不大于 10 的值

解法：

var filter = function(arr, fn) {
    let newArr = []
    arr.forEach((item,index)=>{
        if(fn(item,index)) newArr.push(item)
    })
    return newArr
};

2637. 有时间限制的 Promise 对象 ⭐⭐⭐⭐⭐

描述：
请你编写一个函数，它接受一个异步函数 fn 和一个以毫秒为单位的时间 t。它应根据限时函数返回一个有 限时 效果的函数。函数 fn 接受提供给 限时 函数的参数。
限时 函数应遵循以下规则：

• 如果 fn 在 t 毫秒的时间限制内完成，限时 函数应返回结果。
• 如果 fn 的执行超过时间限制，限时 函数应拒绝并返回字符串 “Time Limit Exceeded” 。
  示例：

输入：
fn = async (n) => { 
  await new Promise(res => setTimeout(res, 100)); 
  return n * n; 
}
inputs = [5]
t = 50
输出：{"rejected":"Time Limit Exceeded","time":50}
解释：
const limited = timeLimit(fn, t)
const start = performance.now()
let result;
try {
   const res = await limited(...inputs)
   result = {"resolved": res, "time": Math.floor(performance.now() - start)};
} catch (err) {
   result = {"rejected": err, "time": Math.floor(performance.now() - start)};
}
console.log(result) // 输出结果
提供的函数设置在 100ms 后执行完成，但是设置的超时时间为 50ms，所以在 t=50ms 时拒绝因为达到了超时时间。

解法：

var timeLimit = function(fn, t) {
	return async function(...args) {
        const p = new Promise((resolve, reject) => {
            setTimeout(()=>{
                reject('Time Limit Exceeded');
            }, t);
        });
        return await Promise.race([p, fn.apply(this, args)]);
    }
};

2629. 复合函数 - compose ⭐⭐⭐⭐⭐

描述：
请你编写一个函数，它接收一个函数数组 [f1, f2, f3，…， fn] ，并返回一个新的函数 fn ，它是函数数组的 复合函数 。
[f(x)， g(x)， h(x)] 的 复合函数 为 fn(x) = f(g(h(x))) 。
一个空函数列表的 复合函数 是 恒等函数 f(x) = x 。
你可以假设数组中的每个函数接受一个整型参数作为输入，并返回一个整型作为输出。
示例：

输入：functions = [x => x + 1, x => x * x, x => 2 * x], x = 4
输出：65
解释：
从右向左计算......
Starting with x = 4.
2 * (4) = 8
(8) * (8) = 64
(64) + 1 = 65

解法：

var compose = function(functions) {
	return function(x) {
        let len = functions.length
        let res = x
        for(let i = len -1;i>=0;i--){
            res = functions[i](res)
        }
        return res
    }
};

// reduceRight
var compose = function(functions) {
	return function(x) {
        // reduceRight() 方法的功能和 reduce() 功能是一样的，不同的是 reduceRight() 从数组的末尾向前将数组中的数组项做累加。
        return functions.reduceRight((pre, cur)=>{
            return cur(pre);
        }, x);
    }
};

2619. 数组原型对象的最后一个元素

描述：
请你编写一段代码实现一个数组方法，使任何数组都可以调用 array.last() 方法，这个方法将返回数组最后一个元素。如果数组中没有元素，则返回 -1 。
示例：

输入：nums = [null, {}, 3]
输出：3
解释：调用 nums.last() 后返回最后一个元素： 3。

解法：

// this数组
Array.prototype.last = function() {
    return this.length ? this[this.length-1] : -1;
};

2621. 睡眠函数

描述：
请你编写一个异步函数，它接收一个正整数参数 millis ，并休眠这么多毫秒。要求此函数可以解析任何值。
示例：

输入：millis = 100
输出：100
解释：
在 100ms 后此异步函数执行完时返回一个 Promise 对象
let t = Date.now();
sleep(100).then(() => {
  console.log(Date.now() - t); // 100
});

解法：

var sleep = function(millis) {
    return new Promise((resolve, reject) => {
        setTimeout(() => {
            resolve(millis);
        }, millis);
    });
};

2620. 计数器

描述：
请你编写并返回一个 计数器 函数，它接收一个整型参数 n 。这个 计数器 函数最初返回 n，每次调用它时返回前一个值加 1 的值 ( n ,  n + 1 ,  n + 2 ，等等)。
示例：

输入：
n = 10 
["call","call","call"]
输出：[10,11,12]
解释：
counter() = 10 // 第一次调用 counter()，返回 n。
counter() = 11 // 返回上次调用的值加 1。
counter() = 12 // 返回上次调用的值加 1。

解法：

var createCounter = function(n) {
    let num = n;
    return function() {
        return num++;
    };
};

2715. 执行可取消的延迟函数 ⭐⭐⭐⭐⭐

描述： （看不懂）
现给定一个函数 fn ，一个参数数组 args 和一个以毫秒为单位的超时时间 t ，返回一个取消函数 cancelFn 。
在经过 t 毫秒的延迟后，除非 先调用 cancelFn ，否则 fn 应该以 args 作为参数被调用。并且在这种情况下，fn 不应该被调用。
示例：

输入：fn = (x) => x * 5, args = [2], t = 20, cancelTime = 50
输出：[{"time": 20, "returned": 10}]
解释：
const cancel = cancellable(fn, [2], 20); // // 在 t=20ms 时调用 fn(2)
setTimeout(cancel, 50);
cancelTime（50ms）在延迟时间（20ms）之后，所以 fn(2) 应该在 t=20ms 时调用。fn 的返回值是 10。

解法：

var cancellable = function(fn, args, t) {
    let timer = setTimeout(() => {
        fn.apply(this, args);
    }, t);
    return function cancelFn(){
        if(timer){
            clearTimeout(timer);
            timer = null;
        }
    };
};

2727. 判断对象是否为空

描述：
给定一个对象或数组，判断它是否为空。

• 一个空对象不包含任何键值对。
• 一个空数组不包含任何元素。
  示例：

输入：obj = {"x": 5, "y": 42}
输出：false
解释：The object has 2 key-value pairs so it is not empty.

解法：

var isEmpty = function(obj) {
    return Object.keys(obj).length === 0;
};

// o(1)解法: 利用for in 遍历对象的特点，一旦进入循环则不是空对象，否则就是空对象。
var isEmpty = function(obj) {
    for(let i in obj) {
        return false;
    }
    return true;
};

中等题

2623. 记忆函数 ⭐⭐⭐⭐⭐

描述：
请你编写一个函数，它接收另一个函数作为输入，并返回该函数的 记忆化 后的结果。
记忆函数 是一个对于相同的输入永远不会被调用两次的函数。相反，它将返回一个缓存值。
你可以假设有 3 个可能的输入函数：sum 、fib 和 factorial 。

• sum 接收两个整型参数 a 和 b ，并返回 a + b 。
• fib 接收一个整型参数 n ，如果 n <= 1 则返回 1，否则返回 fib (n - 1) + fib (n - 2)。
• factorial 接收一个整型参数 n ，如果 n <= 1 则返回  1 ，否则返回 factorial(n - 1) * n 。
  示例：

输入：
"sum"
["call","call","getCallCount","call","getCallCount"]
[[2,2],[2,2],[],[1,2],[]]
输出：
[4,4,1,3,2]
解释：
const sum = (a, b) => a + b;
const memoizedSum = memoize(sum);
memoizedSum (2, 2);// 返回 4。sum() 被调用，因为之前没有使用参数 (2, 2) 调用过。
memoizedSum (2, 2);// 返回 4。没有调用 sum()，因为前面有相同的输入。
//总调用数： 1
memoizedSum(1、2);// 返回 3。sum() 被调用，因为之前没有使用参数 (1, 2) 调用过。
//总调用数： 2

解法：

// 需要注意的是，并不是比较前后两次参数是否相同，而是在输入相同参数的情况下，输出缓存结果。
var memoize = function(func) {
    let cache = {};
    return function(...args) {
        let key = JSON.stringify(args);
        if(cache[key]) {
            return cache[key];
        }
        let res = func.apply(this, args);
        cache[key] = res;
        return res;
    };
};

2631. 分组 - groupBy ⭐⭐⭐⭐⭐

描述：
请你编写一个函数，它接收一个数组和一个函数作为输入，并根据给定的函数对数组元素进行分组。
示例：

输入：
array = [
  {"id":"1"},
  {"id":"1"},
  {"id":"2"}
], 
fn = function (item) { 
  return item.id; 
}
输出：
{ 
  "1": [{"id": "1"}, {"id": "1"}],   
  "2": [{"id": "2"}] 
}
解释：
输出来自函数 array.groupBy(fn)。
分组选择方法是从数组中的每个项中获取 "id" 。
有两个 "id" 为 1 的对象。所以将这两个对象都放在第一个数组中。
有一个 "id" 为 2 的对象。所以该对象被放到第二个数组中。

解法：

// 普通写法，会超时
var groupBy = function(array, fn) {
    let res = {};
    array.forEach(item => {
        let key = fn(item);
        if(!res[key]) {
            res[key] = [];
        }
        res[key].push(item);
    });
    return res;
};

// 使用reduce
var groupBy = function(array, fn) {
    return array.reduce((pre, cur) => {
        (pre[fn(cur)] ??= []).push(cur);
        return pre;
    }, {});
};

flatten

var flat = function(arr, n){
    if(n <= 0){
        return arr;
    }
    return arr.reduce((pre, cur) => {
        if(Array.isArray(cur)){
            pre.push(...flat(cur, n-1));
        }else{
            pre.push(cur);
        }
    }, []);
}

2624. 蜗牛排序

描述
请你编写一段代码为所有数组实现  snail(rowsCount，colsCount) 方法，该方法将 1D 数组转换为以蜗牛排序的模式的 2D 数组。无效的输入值应该输出一个空数组。当 rowsCount * colsCount !==nums.length 时。这个输入被认为是无效的。
蜗牛排序从左上角的单元格开始，从当前数组的第一个值开始。然后，它从上到下遍历第一列，接着移动到右边的下一列，并从下到上遍历它。将这种模式持续下去，每列交替变换遍历方向，直到覆盖整个数组。例如，当给定输入数组  [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15] ，当 rowsCount = 5 且 colsCount = 4 时，需要输出矩阵如下图所示。注意，矩阵沿箭头方向对应于原数组中数字的顺序
示例：

输入：
nums = [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15]
rowsCount = 5
colsCount = 4
输出：
[
 [19,17,16,15],
 [10,1,14,4],
 [3,2,12,20],
 [7,5,18,11],
 [9,8,6,13]
]

解法：

// 普通解法
Array.prototype.snail = function(rowsCount, colsCount) {
    if(rowsCount * colsCount !== this.length){
        return [];
    }
    let res = new Array(rowsCount).fill([]).map(()=>new Array(colsCount));
    let flag = true;
    let count = 0;
    for(let j=0;j<colsCount;j++){
        if(flag){
            for(let i=0;i<rowsCount;i++){
                res[i][j] = this[count++];
            }
            flag = false;
        }else{
            for(i=rowsCount-1;i>=0;i--){
                res[i][j] = this[count++];
            }
            flag = true;
        }
    }
    return res;
}

// 模拟
Array.prototype.snail = function(rowsCount, colsCount) {
    if(rowsCount * colsCount !== this.length){
        return [];
    }
    let i = 0;
    let c = 0;
    let r = 0;
    let res = new Array(rowsCount).fill([]).map(()=>new Array(colsCount));
    while(i<this.length){
        while(r<rowsCount){
            res[r++][c] = this[i++];
        }
        c++;
        while(r>0 && i<this.length){
            res[--r][c] = this[i++];
        }
        c++;
    }
    return res;
}

2649. 嵌套数组生成器

描述：
现给定一个整数的 多维数组 ，请你返回一个生成器对象，按照 中序遍历 的顺序逐个生成整数。多维数组 是一个递归数据结构，包含整数和其他 多维数组。中序遍历 是从左到右遍历每个数组，在遇到任何整数时生成它，遇到任何数组时递归应用 中序遍历 。
示例：

输入：arr = [[[6]],[1,3],[]]
输出：[6,1,3]
解释：
const generator = inorderTraversal(arr);
generator.next().value; // 6
generator.next().value; // 1
generator.next().value; // 3
generator.next().done; // true

解法：

function* inorderTraversal(arr: MultidimensionalArray): Generator<number, void, unknown> {
    for(let item of arr){
        if(Array.isArray(item)){
            yield* inorderTraversal(item);
        }else{
            yield item;
        }
    }
};

call ⭐⭐⭐⭐⭐

解法：

// 经典解法，但是无法通过function keys() { return Object.keys(this); }这个测试样例
Function.prototype.callPolyfill = function (context, ...args) {
  context ||= window;
  context.fn = this;
  const result = context.fn(...args);
  delete context.fn;
  return result;
};

Function.prototype.callPolyfill = function(context, ...args) {
    let ctx = context || window;
    Object.defineProperty(ctx, 'fn', {
        enumerable: false,
        writable: false,
        value: this
    });
    return context['fn'](...args);
}

2705. 精简对象 ⭐⭐⭐⭐⭐

描述：
现给定一个对象或数组 obj，返回一个 精简对象 。精简对象 与原始对象相同，只是将包含 假 值的键移除。该操作适用于对象及其嵌套对象。数组被视为索引作为键的对象。当 Boolean(value) 返回 false 时，值被视为 假 值。
示例：

输入：obj = [null, 0, false, 1]
输出：[1]
解释：数组中的所有假值已被移除。

输入：obj = {"a": null, "b": [false, 1]}
输出：{"b": [1]}
解释：obj["a"] 和 obj["b"][0] 包含假值，因此被移除。

解法：

// copilot
function compactObject(obj: any): any {
    if(Array.isArray(obj)){
        return obj.filter(item=>Boolean(item)).map(item=>compactObject(item));
    }else if(typeof obj === 'object'){
        let res = {};
        for(let key in obj){
            if(Boolean(obj[key])){
                res[key] = compactObject(obj[key]);
            }
        }
        return res;
    }else{
        return obj;
    }
};

var compactObject = function(obj) {
    if(typeof obj === 'string' || typeof obj === 'boolean' || typeof obj === 'number')
        return obj;
    if(Array.isArray(obj)){
        const res = [];
        for(let item of obj){
            if(Boolean(item)){
                res.push(compactObject(item));
            }
        }
        return res;
    }else{
        const res = {};
        Object.keys(obj).forEach(key=>{
            if(Boolean(obj[key])){
                res[key] = compactObject(obj[key]);
            }
        });
        return res;
    }
};