Kristina Somolyar

JavaScript中apply, bind, call 的区别

apply、bind 和 call 是 JavaScript 中的三个方法，都是用来控制函数的 this 指向的。它们有相似之处，但在传递参数和调用方式上有一些区别。我们可以逐一看看它们的定义和使用场景。

1. call 方法

语法：func.call(thisArg, arg1, arg2, ...)

• 作用：直接调用一个函数，并显式指定 this 的指向。
• 参数：thisArg 是我们希望 this 指向的对象，后面的 arg1, arg2, ... 是传递给函数的参数。
• 特点：立即执行函数。

示例

function greet(greeting, punctuation) {
    console.log(`${greeting}, ${this.name}${punctuation}`);
}

const person = { name: "Alice" };

greet.call(person, "Hello", "!"); // 输出: "Hello, Alice!"

在这里，call 方法将 this 设置为 person 对象，并将 "Hello" 和 "!" 作为参数传递给 greet 函数。

2. apply 方法

语法：func.apply(thisArg, [argsArray])

• 作用：与 call 类似，也用来指定 this 的指向并调用函数。
• 参数：thisArg 是 this 的指向，argsArray 是一个数组，表示传递给函数的参数。
• 特点：立即执行函数，但参数以数组形式传递。

示例

function greet(greeting, punctuation) {
    console.log(`${greeting}, ${this.name}${punctuation}`);
}

const person = { name: "Alice" };

greet.apply(person, ["Hello", "!"]); // 输出: "Hello, Alice!"

在这里，apply 的作用与 call 类似，但传递参数的方式不同。apply 使用一个数组来传递参数，而 call 使用的是一组独立的参数。

3. bind 方法

语法：func.bind(thisArg, arg1, arg2, ...)

• 作用：返回一个新的函数，并将 this 永久绑定为 thisArg。
• 参数：thisArg 是要绑定的 this 指向，arg1, arg2, ... 是可以预设的参数。
• 特点：不会立即调用函数，而是返回一个绑定了 this 的新函数，可供后续调用。

示例

function greet(greeting, punctuation) {
    console.log(`${greeting}, ${this.name}${punctuation}`);
}

const person = { name: "Alice" };

const boundGreet = greet.bind(person, "Hello");
boundGreet("!"); // 输出: "Hello, Alice!"

在这里，bind 创建了一个新函数 boundGreet，这个函数的 this 永远绑定为 person，并预设了第一个参数 "Hello"。当我们调用 boundGreet("!") 时，它会使用 this.name 和预设的 "Hello"，最终输出 "Hello, Alice!"。

主要区别总结

使用场景总结

• call：适用于需要立即调用函数，并且参数数量是已知、固定的情况。
• apply：适用于需要立即调用函数，且参数数量动态、以数组形式传递的情况。比如在函数调用参数不确定时，可以通过 apply 使用数组传参。
• bind：适用于需要创建一个函数并永久绑定 this，可以在稍后调用的情况。常见的例子是在事件回调、延迟函数中使用 bind 来确保 this 指向正确。

Unlocking the Lock: Solving the “Open the Lock” Problem with BFS

Today, we’re diving into a classic interview problem, Open the Lock. This problem requires us to use Breadth-First Search (BFS) to find the shortest path by simulating a lock mechanism with four wheels. Let’s walk through the problem step-by-step, analyze the solution, and cover key details in the code.

Problem Overview

The problem describes a lock with four rotating wheels, each numbered from 0 to 9. The lock starts at “0000”, and each wheel can be rotated up or down to the next number. For instance, “0” can rotate to “1” or “9”.

We have a list of deadend combinations. If we reach one of these, the lock stops, and we can’t proceed further from that position. Given these constraints, we need to find the minimum number of moves to turn the lock from “0000” to a target combination target. If it’s impossible, we return -1.

Approach

Since we’re trying to find the shortest path to the target, this problem is a perfect candidate for Breadth-First Search (BFS). BFS explores all paths level by level, ensuring we reach the target in the fewest moves possible.

Step-by-Step Solution Outline:

1. Initialization: Store all deadends in a Set for quick lookup.
2. BFS: Begin from “0000” and explore every possible combination by turning each wheel up or down.
3. Track Moves: Use a queue to store each combination and the current move count, increasing it by one each level.

Code Implementation with Comments

/**
 * @param {string[]} deadends - List of dead-end combinations
 * @param {string} target - Target combination
 * @return {number} - Minimum moves to reach target from "0000", or -1 if impossible
 */
var openLock = function(deadends, target) {
    // Initialize a Set for deadends for quick lookup
    const seen = new Set(deadends);
    
    // Handle edge cases: if "0000" or target is in deadends, we can't proceed
    if (seen.has(target) || seen.has('0000')) return -1;
    
    // If the start is already the target, no moves are needed
    if (target === '0000') return 0;
    
    // Initialize BFS queue and moves counter
    const queue = ["0000"];
    seen.add("0000"); // Mark "0000" as visited
    let steps = 0;

    // Main BFS loop
    while (queue.length > 0) {
        // Number of nodes in the current level
        let size = queue.length;
        
        // Process each node in the current level
        while (size > 0) {
            const current = queue.shift(); // Remove the first element in queue
            
            // If we've reached the target, return the steps taken
            if (current === target) return steps;
            
            // Generate all possible next moves and add to queue
            const comb = generateComb(current);
            for (const next of comb) {
                if (!seen.has(next)) { // Only add unvisited nodes
                    queue.push(next);  // Add new combination to queue
                    seen.add(next);     // Mark new combination as visited
                }
            }
            size--; // Decrement level size
        }
        steps++; // Move to the next level (increment moves)
    }
    
    // If BFS completes without finding target, return -1
    return -1;
};

/**
 * generateComb - Generates all possible next moves for a given lock state
 * @param {string} input - Current lock state
 * @return {string[]} - Returns all possible next moves
 */
var generateComb = function(input) {
    const combinations = [];
    
    // Loop through each of the four wheels
    for (let i = 0; i < 4; i++) {
        // Get the current digit of the wheel
        const digit = parseInt(input[i]);
        
        // Roll the digit up by one (wrap around from 9 to 0)
        const up = input.slice(0, i) + ((digit + 1) % 10) + input.slice(i + 1);
        combinations.push(up); // Add the new combination to the result array
        
        // Roll the digit down by one (wrap around from 0 to 9)
        const down = input.slice(0, i) + ((digit - 1 + 10) % 10) + input.slice(i + 1);
        combinations.push(down); // Add the new combination to the result array
    }
    
    return combinations;
};

Detailed Code Explanation

1. Main Function openLock:
   • The seen set stores all visited states to prevent revisiting deadends and previous combinations.
   • We initialize a queue to store each combination and mark “0000” as visited to prevent reprocessing.
   • The BFS loop processes nodes level by level, allowing us to find the shortest path to target.
2. Combination Generator generateComb:
   • For each digit in the 4-digit lock, we generate two new states: one by rolling the digit up and one by rolling it down.
   • Each new combination is added to the result array, which is then returned to the BFS loop for further processing.
3. Core Logic:
   • BFS systematically expands from the start state, checking all possible next moves.
   • The algorithm uses steps to count levels, ensuring that when we reach target, it’s in the minimum moves.
   • If BFS finishes without finding target, we return -1, as it’s impossible to reach.

Example Walkthrough

Consider the case where deadends = ["0201","0101","0102","1212","2002"] and target = "0202":

• Initial State: queue = ["0000"], steps = 0
• First Level (step = 1): From “0000”, we expand to “1000”, “9000”, “0100”, “0900”… adding all valid moves to the queue.
• Subsequent Levels: We keep expanding outward, avoiding deadends and marking visited states.
• Final Steps: Eventually, we reach “0202” in the minimum moves and return the step count.

Conclusion

This problem is an excellent example of BFS’s utility in finding shortest paths. Key takeaways include:

• Using BFS: For shortest path problems where each move has equal weight, BFS provides an efficient approach.
• Tracking Visited States: By storing visited states, we avoid deadends and reduce redundant processing.
• Generating Moves: By iterating through each digit and generating moves, we simulate all possible paths from a given state.

By practicing with problems like this, you’ll improve your understanding of BFS and how to apply it to real-world scenarios!

简单易懂的TypeScript哈希表教程

用TypeScript写个哈希表——说白了就是“找东西利器”

哈希表这个东西呢，跟生活中找钥匙差不多。想象一下，你每次出门都乱丢钥匙，回家要用半小时才能找到它。如果有个哈希表，那你一秒就能知道钥匙放哪了。所以今天我们来用TypeScript写个哈希表，别担心，跟朋友聊天一样简单。

什么是哈希表？

哈希表就像给你的钥匙分配了个专属抽屉，你把钥匙往哈希表里一丢，它自己找个抽屉放好，等你要用的时候，你直接问它：“我的钥匙在哪呢？” 它马上告诉你在哪个抽屉里，秒找。是不是很方便？那咱现在就来动手写一个。

代码部分——慢慢来，不急

我们来一步步写哈希表，代码都标注好，解释清楚，放心不会扯得太远。

class HashTable<T> {
  // 创建一个桶数组，桶就是个小抽屉，里面装着key-value对
  private buckets: Array<Array<[string, T]>>;

  // 哈希表的大小，也就是有多少个抽屉
  private size: number;

  constructor(size: number) {
    this.size = size;
    // 创建一个指定大小的桶数组，初始每个位置是个空数组
    this.buckets = new Array(size).fill(null).map(() => []);
    // 为啥要fill(null)？TypeScript不允许你直接在空数组上map，得先填充一波。
  }

  // 哈希函数，负责把key变成数字，这样才能找到对应的桶
  private hash(key: string): number {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      // 计算哈希值，用ASCII码+位置的算法，最后取模，得到抽屉位置
      hash = (hash + key.charCodeAt(i) * i) % this.size;
    }
    return hash;  // 这个数字就是抽屉的索引
  }

  // 插入或更新键值对
  set(key: string, value: T): void {
    const index = this.hash(key);  // 通过哈希函数找到抽屉
    const bucket = this.buckets[index];  // 拿到对应的抽屉

    // 先看看抽屉里有没有相同的key
    for (let i = 0; i < bucket.length; i++) {
      const pair = bucket[i];
      if (pair[0] === key) {
        // 找到了，就更新value
        pair[1] = value;
        return;
      }
    }

    // 没找到？那就直接把新的key-value对扔进去
    bucket.push([key, value]);
  }

  // 查找键值对
  get(key: string): T | undefined {
    const index = this.hash(key);  // 先找到抽屉
    const bucket = this.buckets[index];  // 拿出这个抽屉

    // 遍历抽屉里的东西，看看有没有这个key
    for (const pair of bucket) {
      if (pair[0] === key) {
        return pair[1];  // 找到了，直接返回value
      }
    }

    return undefined;  // 没找到，给你个undefined，你懂的
  }

  // 删除键值对
  remove(key: string): boolean {
    const index = this.hash(key);  // 一样先找到抽屉
    const bucket = this.buckets[index];  // 取出这个抽屉

    // 遍历抽屉，找到要删的key
    for (let i = 0; i < bucket.length; i++) {
      const pair = bucket[i];
      if (pair[0] === key) {
        bucket.splice(i, 1);  // 找到后直接删掉
        return true;  // 成功删除，返回true
      }
    }

    return false;  // 没找到就返回false，删除失败
  }
}

说点需要注意的

1. 构造函数那点事儿
   为啥得先 fill(null)？TypeScript不让直接在空数组上 map()，所以你得先用 fill(null) 把它填满，再通过 map() 每个位置给它创建一个空的抽屉。不这样搞，TypeScript就会给你脸色看（直接报错）。
2. 哈希函数到底在干嘛？
   你可能好奇这 hash() 函数到底干啥。其实它就是把字符串变成一个数字，方便找到你想要的抽屉。这里我们用了每个字符的ASCII码乘以它在字符串里的位置，最后对哈希表的大小取模。简单、暴力、够用！但别想太复杂，咱写这个不是为了拿诺贝尔奖，能用就行。
3. 冲突咋处理？
   冲突是难免的，两个 key 哈希到同一个位置就叫冲突。这里我们用了“链地址法”来处理冲突，简单来说就是一个桶可以存多个键值对，每次冲突时就往同一个桶里塞。不过，这种方式容易导致某些桶变得过于拥挤，性能就可能下降。如果你想避免这种情况，可以试试“开放地址法”（Open Addressing）。它的原理是，如果一个桶已经有数据了，哈希表会去找下一个空的桶来放新数据。总的来说，两种方法各有优缺点，你可以根据实际需求选择。
4. 时间复杂度
   哈希表的优势是大多数操作都是 O(1) 时间复杂度，也就是速度快！不过当冲突多了，桶里东西多了，链地址法会退化成 O(n)，查找变得慢。所以，哈希表适合用在冲突不太多的场景，或者你可以用更复杂的数据结构，比如平衡二叉树来处理冲突，提升查找效率。

然后呢？

好了，你已经有了一个能插入、查找、删除数据的哈希表了。接下来如果你想进一步优化，我们可以聊聊其他的冲突处理方式，比如“开放地址法”——这玩意儿可以让你别再往一个抽屉里塞太多东西。另外呢，像红黑树这种高级结构，也可以用来提升性能，后面有机会我们再详细聊。