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)，查找变得慢。所以，哈希表适合用在冲突不太多的场景，或者你可以用更复杂的数据结构，比如平衡二叉树来处理冲突，提升查找效率。

然后呢？

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

Implementing a Priority Queue in TypeScript: A Step-by-Step Guide

Priority queues are essential data structures in computer science, especially when dealing with tasks that require ordering based on priority. In this blog post, we’ll explore how to implement a priority queue in TypeScript, which can help solve problems like LeetCode’s 215. Kth Largest Element in an Array.

Introduction

A priority queue is a special type of queue where each element is associated with a priority, and elements are served based on their priority. The higher the priority, the sooner the element is dequeued. We’ll implement a min-heap-based priority queue, which ensures that the element with the smallest value (highest priority) is always at the front.

Why TypeScript?

TypeScript adds static typing to JavaScript, providing better tooling and error checking at compile time. This makes our code more robust and maintainable.

Step 1: Define the Priority Queue Class

First, let’s create a PriorityQueue class that will hold our heap.

class PriorityQueue<T> {
  private heap: T[] = [];

  constructor(private comparator: (a: T, b: T) => number) {}
}

• heap: An array representing the binary heap.
• comparator: A function to compare two elements, defining the priority.

Step 2: Implement the Helper Methods

Swap Method

We need a method to swap two elements in the heap.

private swap(i: number, j: number): void {
  [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}

Parent and Child Index Methods

Calculate the indices of parent and child nodes.

private parentIndex(index: number): number {
  return Math.floor((index - 1) / 2);
}

private leftChildIndex(index: number): number {
  return 2 * index + 1;
}

private rightChildIndex(index: number): number {
  return 2 * index + 2;
}

Step 3: Implement the Push Method

Add a new element to the heap and reorder it to maintain the heap property.

push(item: T): void {
  this.heap.push(item);
  this.heapifyUp();
}

Heapify Up

Move the new element up to its correct position.

private heapifyUp(): void {
  let index = this.heap.length - 1;
  while (
    index > 0 &&
    this.comparator(this.heap[index], this.heap[this.parentIndex(index)]) < 0
  ) {
    this.swap(index, this.parentIndex(index));
    index = this.parentIndex(index);
  }
}

Step 4: Implement the Pop Method

Remove and return the element with the highest priority.

pop(): T | undefined {
  if (this.heap.length === 0) return undefined;
  if (this.heap.length === 1) return this.heap.pop();

  const item = this.heap[0];
  this.heap[0] = this.heap.pop() as T;
  this.heapifyDown();
  return item;
}

Heapify Down

Reorder the heap after removing the root element.

private heapifyDown(): void {
  let index = 0;
  const length = this.heap.length;

  while (this.leftChildIndex(index) < length) {
    let smallestChildIndex = this.leftChildIndex(index);
    const rightChildIdx = this.rightChildIndex(index);

    if (
      rightChildIdx < length &&
      this.comparator(this.heap[rightChildIdx], this.heap[smallestChildIndex]) < 0
    ) {
      smallestChildIndex = rightChildIdx;
    }

    if (
      this.comparator(this.heap[index], this.heap[smallestChildIndex]) <= 0
    ) {
      break;
    }

    this.swap(index, smallestChildIndex);
    index = smallestChildIndex;
  }
}

Step 5: Implement Peek and Size Methods

Get the element with the highest priority without removing it and get the size of the queue.

peek(): T | undefined {
  return this.heap[0];
}

size(): number {
  return this.heap.length;
}

Step 6: Implement the Update Method

Now, we’ll implement an update() method that allows us to update the priority of an element, either by its index or by its value.

Update by Index

updateAt(index: number, newValue: T): void {
  if (index < 0 || index >= this.heap.length) {
    throw new Error("Index out of bounds");
  }

  const oldValue = this.heap[index];
  this.heap[index] = newValue;

  if (this.comparator(newValue, oldValue) < 0) {
    this.heapifyUp(index);
  } else {
    this.heapifyDown(index);
  }
}

Explanation: We replace the value at the given index with the new value. Then, depending on how the new value compares to the old value, we either heapify up or heapify down to restore the heap property.

Update by Value

Since updating by value can be inefficient (as it may require searching the entire heap), we’ll implement it cautiously.

update(value: T, newValue: T): void {
  const index = this.heap.findIndex((element) => element === value);
  if (index === -1) {
    throw new Error("Value not found in heap");
  }
  this.updateAt(index, newValue);
}

Explanation: We find the index of the value in the heap and then call updateAt() to update it.

Remove and Remove By Index

  public remove(item: T): void {
    const index = this.heap.indexOf(item);
    if (index === -1) {
      throw new Error('item not found');
    }
    this.removeAtIndex(index);
  }

  private removeAtIndex(index: number): void {
    if (index < 0 || index >= this.heap.length) {
      throw new Error('index out of bounds');
    }
    if (index === this.heap.length - 1) {
      this.heap.pop();
    } else {
      this.heap[index] = this.heap.pop() as T;
      const parentIndex = this.parent(index);
      if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
        this.heapifyUp(index);
      } else {
        this.heapifyDown(index);
      }
    }
  }

Step 7: Implement the Heapify Function

We’ll add a heapify() method to build a heap from an existing array.

heapify(array: T[]): void {
  this.heap = array;
  for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
    this.heapifyDown(i);
  }
}

Step 8: Use the Priority Queue to Solve LeetCode 215

Now, let’s use our PriorityQueue to find the Kth largest element in an array.

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Solution

We’ll use a min-heap (priority queue) to keep track of the largest k elements.

function findKthLargest(nums: number[], k: number): number {
  const pq = new PriorityQueue<number>((a, b) => a - b);

  for (const num of nums) {
    pq.push(num);
    if (pq.size() > k) {
      pq.pop();
    }
  }

  return pq.peek() as number;
}

Comparator: (a, b) => a - b ensures a min-heap.

Logic: Maintain a heap of size k. The root will be the kth largest element.

Full Code Listing with small changes in variable names

class PriorityQueue<T> {
  private heap: T[];

  constructor(private compare: (a: T, b: T) => number) {
    this.heap = [];
  }

  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  private parent(i: number): number {
    return Math.floor((i - 1) / 2);
  }

  private left(i: number): number {
    return 2 * i + 1;
  }

  private right(i: number): number {
    return 2 * i + 2;
  }

  private heapifyUp(index: number): void {
   while (index > 0 && this.compare(this.heap[index], this.heap[this.parent(index)]) < 0) {
    this.swap(index, this.parent(index));
      index = this.parent(index);
    }
  }

  private heapifyDown(index: number): void {
    const length = this.heap.length;

    while (this.left(index) < length) {
      let smallest = this.left(index);
      const rightIndex = this.right(index);
      if (rightIndex < length && this.compare(this.heap[rightIndex], this.heap[smallest]) < 0) {
        smallest = rightIndex;
      }
      if (this.compare(this.heap[index], this.heap[smallest]) < 0) {
        break;
      }
      this.swap(index, smallest);
      index = smallest;
    }
  }

  public push(item: T): void {
    this.heap.push(item);
    this.heapifyUp(this.heap.length - 1);
  }

  public pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();

    const root = this.heap[0];
    this.heap[0] = this.heap.pop() as T;
    this.heapifyDown(0);
    return root;
  }

  public peek(): T | undefined {
    return this.heap[0];
  }

  public size(): number {
    return this.heap.length;
  }

  public updateAtIndex(index: number, newItem: T): void {
    if (index < 0 || index >= this.heap.length) {
      throw new Error('index out of bounds');
    }
    this.heap[index] = newItem;
    if (this.compare(newItem, this.heap[this.parent(index)]) < 0) {
      this.heapifyUp(index);
    } else {
      this.heapifyDown(index);
    }
  }

  public update(item: T, newItem: T): void {
    const index = this.heap.indexOf(item);
    if (index === -1) {
      throw new Error('item not found');
    }
    this.updateAtIndex(index, newItem);
  }

  public remove(item: T): void {
    const index = this.heap.indexOf(item);
    if (index === -1) {
      throw new Error('item not found');
    }
    this.removeAtIndex(index);
  }

  private removeAtIndex(index: number): void {
    if (index < 0 || index >= this.heap.length) {
      throw new Error('index out of bounds');
    }
    if (index === this.heap.length - 1) {
      this.heap.pop();
    } else {
      this.heap[index] = this.heap.pop() as T;
      const parentIndex = this.parent(index);
      if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
        this.heapifyUp(index);
      } else {
        this.heapifyDown(index);
      }
    }
  }

  public isEmpty(): boolean {
    return this.heap.length === 0;
  }

  public heapify(array: T[]): void {
    this.heap = array;
    for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) {
      this.heapifyDown(i);
    }
  }
}

Testing the Solution

Let’s test our implementation with an example.

const nums = [3, 2, 1, 5, 6, 4];
const k = 2;

const result = findKthLargest(nums, k);
console.log(`The ${k}th largest element is ${result}`); // Output: 5

Testing the Update and Heapify Methods

Using heapify() to Build a Heap from an Array

typescriptCopy codeconst nums = [3, 2, 1, 5, 6, 4];
const pq = new PriorityQueue<number>((a, b) => a - b);
pq.heapify(nums);

console.log(pq.peek()); // Output: 1

Rewriting the findKthLargest Function Using heapify()

We can optimize our earlier findKthLargest function by using heapify().

function findKthLargest(nums: number[], k: number): number {
  const pq = new PriorityQueue<number>((a, b) => b - a); // Max-heap

  pq.heapify(nums);

  for (let i = 0; i < k - 1; i++) {
    pq.pop();
  }

  return pq.peek() as number;
}

Why Use heapifyDown() in heapify()?

That’s a great question! In the heapify() method, we use heapifyDown() instead of heapifyUp() because when building a heap from an existing array, we need an efficient way to ensure the heap property is maintained throughout the structure.

When constructing a heap from an unordered array, the most efficient method is to start from the last non-leaf node and move upwards, performing heapifyDown() on each node. This process is known as the heapify algorithm or build heap.

Reasons:

1. Higher Efficiency:
   • Lower Time Complexity: Using heapifyDown(), the overall time complexity of building the heap is O(n). If we were to use heapifyUp(), the time complexity would increase to O(n log n) in the worst case.
   • Fewer Node Movements: heapifyDown() can fix all violations of the heap property from the current node down to the leaves in one pass, whereas heapifyUp() might require multiple passes for each node.
2. Suitable for Building the Entire Heap:
   • heapifyDown() is more appropriate when you need to adjust the heap starting from the internal nodes downwards.
   • heapifyUp() is typically used when inserting a new element into an already built heap.

Detailed Explanation

When building a heap, our goal is to ensure that every parent node satisfies the heap property with respect to its children (for a min-heap, each parent node is less than or equal to its children). To achieve this efficiently, we start from the last non-leaf node because leaf nodes are already valid heaps by themselves.

heapify(array: T[]): void {
  this.heap = array;
  for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
    this.heapifyDown(i);
  }
}

• Calculating the Starting Index: Math.floor(this.heap.length / 2) - 1
  • This formula gives us the index of the last non-leaf node.
  • In a binary heap, nodes with indices from Math.floor(n/2) to n - 1 are all leaf nodes.
• Why Not Use heapifyUp()?
  • heapifyUp() is suitable for situations where you’re adding a single new element to the heap and need to adjust its position.
  • Using heapifyUp() during the heap construction process would result in higher time complexity because each node might need to be moved up multiple levels.
  • In contrast, heapifyDown() can adjust the subtree rooted at a node in one pass.

An Example

Suppose we have an array [3, 2, 1, 5, 6, 4] and we want to build a min-heap.

1. Initialize the Heap:typescriptCopy codethis.heap = [3, 2, 1, 5, 6, 4];
2. Start from the Last Non-Leaf Node:
   • The array length is 6, so the index of the last non-leaf node is Math.floor(6 / 2) - 1 = 2.
3. Perform heapifyDown() on Index 2:
   • The node at index 2 has a value 1, and its children are out of bounds, so no action is needed.
4. Perform heapifyDown() on Index 1:
   • The node at index 1 has a value 2, with left child 5 and right child 6.
   • Since 2 is less than its children, no action is needed.
5. Perform heapifyDown() on Index 0:
   • The node at index 0 has a value 3, with left child 2 and right child 1.The right child 1 is the smallest, so we swap 3 with 1.
   • The heap now looks like [1, 2, 3, 5, 6, 4].
6. Continue heapifyDown() on the Swapped Node:
   • The node at index 2 (now with value 3) has a left child 4, but since 3 is less than 4, no further action is needed.

Summary

• Using heapifyDown():
  • Ideal for building a heap from an array.
  • Overall time complexity is O(n).
• Using heapifyUp():
  • Suitable for inserting a single element into an existing heap.
  • Each insertion has a time complexity of O(log n).

Therefore, in the heapify() method, we choose heapifyDown() to efficiently build a valid heap from the bottom up.

Additional Notes

• Why Not Use heapifyUp()?
  • If we used heapifyUp() on each node starting from the root, each node might have to move up several levels, leading to higher overall time complexity.
  • heapifyDown() allows us to fix violations of the heap property starting from each internal node down to the leaves in a single pass.
• Time Complexity Comparison:
  • Using heapifyDown(): Total time complexity is O(n).
  • Using heapifyUp(): Total time complexity is O(n log n).

Conclusion

We’ve successfully implemented a priority queue in TypeScript using a min-heap and applied it to solve a common algorithm problem. This implementation can be extended or modified for other use cases, such as max-heaps or custom priority criteria.

References

• TypeScript Official Website
• Heap Data Structure
• LeetCode Problem 215

使用TypeScript实现优先队列 (Priority Queue)

前言

大家好！今天我想和大家分享如何使用TypeScript实现一个优先队列（Priority Queue），并利用它来解决LeetCode第215题——数组中的第K个最大元素。在算法面试中，优先队列是一个非常常用的数据结构，理解并能熟练实现它对我们解决一系列问题都有帮助。

问题描述

LeetCode第215题：数组中的第K个最大元素

给定一个未排序的整数数组 nums，找到其中第 k 个最大的元素。

示例：

输入: nums = [3,2,1,5,6,4], k = 2
输出: 5

输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 ≤ k ≤ nums.length ≤ 10^4
• -10^4 ≤ nums[i] ≤ 10^4

解题思路

要找到第 k 个最大的元素，我们可以采用多种方法：

1. 排序法：将数组排序，然后取第 k 个最大的元素。时间复杂度为 O(n log n)。
2. 基于堆的优先队列：使用一个大小为 k 的最小堆来维护当前最大的 k 个元素。时间复杂度为 O(n log k)。
3. 快速选择算法：类似快速排序的分区思想，平均时间复杂度为 O(n)。

在这篇文章中，我们重点介绍使用最小堆实现的优先队列，因为它在实际应用中非常高效，且实现相对简单。

什么是优先队列？

优先队列是一种特殊的队列，元素按照优先级进行出入队操作。常用的实现方式是堆，根据堆的性质，可以快速地获取当前的最值（最大值或最小值）。

在我们的问题中，我们需要维护一个大小为 k 的最小堆，堆顶元素就是当前第 k 个最大的元素。

TypeScript中实现最小堆

堆的基本操作

1. 插入元素（insert）：将新元素添加到堆的末尾，然后向上调整位置（上浮）。
2. 删除堆顶元素（extractMin）：移除堆顶元素，将末尾元素放到堆顶，然后向下调整位置（下沉）。
3. 查看堆顶元素（getMin）：获取堆顶元素的值。
4. 获取堆的大小（size）：返回堆中元素的数量。

实现代码

class MinHeap {
    private heap: number[] = [];

    insert(val: number): void {
        this.heap.push(val);
        this.bubbleUp();
    }

    private bubbleUp(): void {
        let index = this.heap.length - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[index] >= this.heap[parentIndex]) break;
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    extractMin(): number | undefined {
        if (this.heap.length === 0) return undefined;
        const min = this.heap[0];
        const end = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown();
        }
        return min;
    }

    private sinkDown(): void {
        let index = 0;
        const length = this.heap.length;
        const element = this.heap[0];

        while (true) {
            let leftChildIdx = 2 * index + 1;
            let rightChildIdx = 2 * index + 2;
            let swapIdx: number | null = null;

            if (leftChildIdx < length) {
                if (this.heap[leftChildIdx] < element) {
                    swapIdx = leftChildIdx;
                }
            }

            if (rightChildIdx < length) {
                if (
                    (swapIdx === null && this.heap[rightChildIdx] < element) ||
                    (swapIdx !== null && this.heap[rightChildIdx] < this.heap[leftChildIdx])
                ) {
                    swapIdx = rightChildIdx;
                }
            }

            if (swapIdx === null) break;
            [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
            index = swapIdx;
        }
    }

    getMin(): number | undefined {
        return this.heap[0];
    }

    size(): number {
        return this.heap.length;
    }
}

代码解释

• insert(val: number)：将元素添加到堆末尾，然后调用 bubbleUp 进行上浮操作，保持最小堆性质。
• bubbleUp()：从新添加的元素开始，与父节点比较，如果小于父节点则交换位置，直到满足最小堆性质。
• extractMin()：移除并返回堆顶元素，将堆末尾元素放到堆顶，然后调用 sinkDown 进行下沉操作。
• sinkDown()：从堆顶开始，与子节点比较，如果大于子节点则交换位置，直到满足最小堆性质。
• getMin()：返回堆顶元素，不修改堆。
• size()：返回堆中元素的数量。

利用最小堆解决第K个最大元素问题

实现思路

1. 创建一个大小为 k 的最小堆。
2. 遍历数组，将元素逐一插入堆中。
3. 当堆的大小超过 k 时，移除堆顶元素（最小值）。
4. 遍历完成后，堆顶元素就是第 k 个最大元素。

实现代码

function findKthLargest(nums: number[], k: number): number {
    const minHeap = new MinHeap();

    for (const num of nums) {
        minHeap.insert(num);
        if (minHeap.size() > k) {
            minHeap.extractMin();
        }
    }

    return minHeap.getMin()!;
}

代码解释

• 遍历数组：将每个元素插入到最小堆中。
• 维护堆的大小：如果堆的大小超过 k，则移除堆顶元素，确保堆中始终只包含当前最大的 k 个元素。
• 返回结果：遍历结束后，堆顶元素即为第 k 个最大元素。

测试代码

const nums1 = [3, 2, 1, 5, 6, 4];
const k1 = 2;
console.log(findKthLargest(nums1, k1)); // 输出: 5

const nums2 = [3, 2, 3, 1, 2, 4, 5, 5, 6];
const k2 = 4;
console.log(findKthLargest(nums2, k2)); // 输出: 4

时间复杂度分析

• 插入和移除操作：每次操作的时间复杂度为 O(log k)。
• 总时间复杂度：对于长度为 n 的数组，总的时间复杂度为 O(n log k)，当 k 远小于 n 时，效率较高。

空间复杂度分析

• 空间复杂度：使用了额外的堆空间，最大为 O(k)。

总结

通过使用最小堆实现的优先队列，我们可以高效地找到数组中的第 k 个最大元素。这种方法在处理大规模数据时非常实用，因为我们不需要对整个数组进行排序，只需维护一个大小为 k 的堆即可。

优点

• 高效性：时间复杂度为 O(n log k)，比直接排序的 O(n log n) 更优。
• 适用性强：当需要实时处理数据流并获取第 k 个最大元素时，此方法非常适用。

缺点

• 实现复杂度：相比内置排序函数，手动实现堆需要更多的代码和调试。

后记

希望这篇文章能帮助大家理解如何在TypeScript中实现优先队列，并应用于实际问题。如果有任何疑问或改进建议，欢迎在评论区与我交流！

参考资料

• LeetCode 第215题 – 数组中的第K个最大元素
• 堆（Heap）数据结构详解

感谢阅读！如果觉得有帮助，请点赞支持。

430. Flatten a Multilevel Doubly Linked List

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

 

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Example 3:

Input: head = []
Output: []
Explanation: There could be empty list in the input.

 

Constraints:

• The number of Nodes will not exceed 1000.
• 1 <= Node.val <= 105

 

How the multilevel linked list is represented in test cases:

We use the multilevel linked list from Example 1 above:

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1,    2,    3, 4, 5, 6, null]
             |
[null, null, 7,    8, 9, 10, null]
                   |
[            null, 11, 12, null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Problem Explanation

The goal is to flatten a multilevel doubly linked list. Each node has next, prev, and child pointers. The child pointer points to another doubly linked list, which might have its own child pointers. We need to flatten this structure into a single-level doubly linked list.

Approach

1. Traverse the linked list using a pointer current.
2. Whenever we encounter a node with a child, we need to:
   • Temporarily store the next node.
   • Flatten the child list recursively.
   • Insert the flattened child list between the current node and the next node.
   • Update all the necessary pointers (next and prev).
   • Ensure the child pointer is set to null.
3. Continue this process until the entire list is flattened.

Code with Detailed Comments

var flatten = function(head) {
    if (head === null) return null;

    // Start traversing from the head node
    let current = head;
    
    // Traverse the entire linked list
    while (current !== null) {
        // If the current node has a child, we need to flatten it
        if (current.child !== null) {
            // Store the next node temporarily
            let next = current.next;
            
            // Recursively flatten the child list
            let child = flatten(current.child);

            // Insert the flattened child list
            current.next = child;
            child.prev = current;
            
            // Find the tail of the flattened child list
            while (child.next !== null) {
                child = child.next;
            }

            // Connect the tail of the flattened child list to the next node
            if (next !== null) {
                next.prev = child;
            }
            child.next = next;
            
            // Remove the child pointer
            current.child = null;
        }
        
        // Move to the next node
        current = current.next;
    }
    
    return head;
};

Step-by-Step Explanation

1. Initialization:
   • Check if head is null. If it is, return null immediately.
   • Initialize current to start from the head node.
2. Traversal:
   • Use a while loop to traverse the entire linked list.
3. Handling the child:
   • If current has a child, perform the following steps:
     • Temporarily store the next node (current.next).
     • Recursively flatten the child list by calling flatten(current.child).
     • Insert the flattened child list between the current node and the next node:
       • Set current.next to the head of the flattened child list.
       • Update the prev pointer of the flattened child list head to point to current.
     • Find the tail of the flattened child list by iterating through it until child.next is null.
     • Connect the tail of the flattened child list to the next node:
       • Set next.prev to the tail of the flattened child list (if next is not null).
       • Set the next pointer of the tail of the flattened child list to next.
     • Set current.child to null as it is now flattened and integrated into the main list.
4. Continue Traversal:
   • Move current to the next node (current.next) and repeat the process until the end of the list is reached.

Complexity Analysis

• Time Complexity: O(n), where n is the total number of nodes in the list. Each node is processed once, and the child lists are flattened and inserted in linear time.
• Space Complexity: O(d), where d is the maximum depth of the multilevel list. This space is used by the recursion stack due to the depth-first search approach.

This approach ensures that all pointers are correctly updated, maintaining the doubly linked structure while flattening the multilevel list into a single-level list.

TypeScript Data Structure: Implementing a Doubly Linked List

用Typescript实现一个双向链表

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Analysis of Doubly Linked List Implementation

In computer science, linked lists are a fundamental data structure, and a doubly linked list is a variation that allows traversal in both directions—forward and backward. Each node in a doubly linked list contains a reference to both the next and the previous node, providing flexibility and efficiency for operations that require frequent access to both ends of the list.

Requirements Analysis

In this task, the goal is to implement a doubly linked list with basic functionalities such as:

• Retrieving the value of the node at a specific index.
• Inserting a node at the beginning of the list.
• Inserting a node at the end of the list.
• Inserting a new node at a specified position in the list.
• Deleting a node at a specified index.

Thought Process and Algorithm Implementation

1. Initialization

We start by defining a Node class, which will have three properties: val (the value stored in the node), next (a reference to the next node), and prev (a reference to the previous node). We also define a MyLinkedList class to manage these nodes, including properties for the head (the first node), tail (the last node), and size (the length of the list).

class Node {
    val: number;
    next: Node | null;
    prev: Node | null;

    constructor(val: number) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

2. Retrieving a Node Value

The get method straightforwardly traverses the list from the head to the desired index. It’s important to handle invalid indices by returning -1 if the index is out of bounds.

get(index: number): number {
    if (index < 0 || index >= this.size) return -1;
    let current = this.head;
    for (let i = 0; i < index; i++) {
        current = current.next;
    }
    return current.val;
}

3. Adding a Node at the Head

When adding at the head, we create a new node and adjust the head pointer to point to this new node. If the list is not empty, we also need to update the previous head’s prev to reference the new node. If the list is empty, the new node also becomes the tail.

addAtHead(val: number): void {
    const newNode = new Node(val);
    if (this.size === 0) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
    }
    this.size++;
}

4. Adding a Node at the Tail

Adding at the tail involves creating a new node and adjusting the tail pointer. The new node’s prev points to the current tail, and if the list is empty, the new node will serve as both the head and tail.

addAtTail(val: number): void {
    const newNode = new Node(val);
    if (this.size === 0) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
    }
    this.size++;
}

5. Inserting a Node at a Specified Position

This operation is more complex, as it involves handling several cases:

• Inserting at index 0, which is equivalent to addAtHead.
• Inserting at index size, equivalent to addAtTail.
• For other positions, find the node before the desired position and insert the new node accordingly.

addAtIndex(index: number, val: number): void {
    if (index < 0 || index > this.size) return;
    if (index == 0) {
        this.addAtHead(val);
    } else if (index == this.size) {
        this.addAtTail(val);
    } else {
        let prev = this.head;
        for (let i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        const newNode = new Node(val);
        newNode.next = prev.next;
        newNode.prev = prev;
        if (prev.next) {
            prev.next.prev = newNode;
        }
        prev.next = newNode;
        this.size++;
    }
}

6. Deleting a Node at a Specified Position

Deletion requires careful pointer adjustments. Special attention is needed when deleting the head or tail node to update the head and tail pointers accordingly.

deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) return;
    if (index === 0) {
        this.head = this.head.next;
        if (this.head) {
            this.head.prev = null;
        } else {
            this.tail = null; // list became empty
        }
    } else {
        let prev = this.head;
        for (let i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        const toDelete = prev.next;
        prev.next = toDelete.next;
        if (prev.next) {
            prev.next.prev = prev;
        } else {
            this.tail = prev; // deleting the last node
        }
    }
    this.size--;
}

Conclusion

This analysis not only illustrates how to implement each fundamental operation of a doubly linked list but also discusses handling edge cases and special conditions. Understanding these operations is key to mastering the linked list data structure. Hopefully, this breakdown will help you gain a deeper understanding of the implementation and application of doubly linked lists.

双向链表的实现分析

在计算机科学中，链表是一种常用的数据结构，双向链表是链表的一种变形，其中每个节点除了有指向下一个节点的指针next外，还包含一个指向上一个节点的指针prev。这种结构提供了向前和向后两种遍历方式，使得某些操作更为高效。

需求分析

在这个题目中，需要实现一个双向链表，包括以下基本操作：

• 获取链表中第index个节点的值。
• 在链表头部插入一个节点。
• 在链表尾部插入一个节点。
• 在链表中的第index个位置插入一个新节点。
• 删除链表中的第index个节点。

思维过程与算法实现

1. 初始化

首先，我们需要一个Node类来定义节点，包括val（节点存储的值），next（指向下一个节点的引用）和prev（指向上一个节点的引用）。其次，定义MyLinkedList类来管理这些节点，包括head（头节点），tail（尾节点），以及size（链表长度）。

class Node {
    val: number;
    next: Node | null;
    prev: Node | null;

    constructor(val: number) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

2. 获取节点值

获取节点值的操作相对直接，从head开始，遍历链表直到到达指定的index位置。需要注意的是，如果index无效（即超出链表范围），则返回-1。

get(index: number): number {
    if (index < 0 || index >= this.size) return -1;
    let current = this.head;
    for (let i = 0; i < index; i++) {
        current = current.next;
    }
    return current.val;
}

3. 添加节点到头部

在头部添加节点时，需要创建一个新节点，并将其next指针指向当前的head。同时，如果链表本身不为空，更新原有头节点的prev指向新节点。如果链表为空，则同时更新tail。

addAtHead(val: number): void {
    const newNode = new Node(val);
    if (this.size === 0) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
    }
    this.size++;
}

4. 添加节点到尾部

尾部添加类似于头部添加，但是新节点的prev将指向当前的tail，并更新tail的next。

addAtTail(val: number): void {
    const newNode = new Node(val);
    if (this.size === 0) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
    }
    this.size++;
}

5. 在指定位置添加节点

这是一个稍微复杂的操作，需要分多种情况处理：

• 如果index等于0，相当于addAtHead。
• 如果index等于size，相当于addAtTail。
• 其他情况，需要找到第index-1个节点，然后在其后插入新节点。

addAtIndex(index: number, val: number): void {
    if (index < 0 || index > this.size) return;
    if (index === 0) {
        this.addAtHead(val);
    } else if (index === this.size) {
        this.addAtTail(val);
    } else {
        let prev = this.head;
        for (let i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        const newNode = new Node(val);
        newNode.next = prev.next;
        newNode.prev = prev;
        prev.next.prev = newNode;
        prev.next = newNode;
        this.size++;
    }
}

6. 删除指定位置的节点

删除操作需要更新prev和next指针。特别要注意当删除的是头节点或尾节点时，还需要更新head或tail。

deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) return;
    if (index === 0) {
        this.head = this.head.next;
        if (this.size === 1) {
            this.tail = null;
        } else {
            this.head.prev = null;
        }
    } else {
        let prev = this.head;
        for (let i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        const toDelete = prev.next;
        prev.next = toDelete.next;
        if (prev.next) {
            prev.next.prev = prev;
        } else {
            this.tail = prev;
        }
    }
    this.size--;
}

总结

通过逐步解析每个操作，我们不仅展示了如何实现双向链表的各个基本功能，还深入讨论了边界情况和特殊情况的处理。理解这些基本操作是掌握链表数据结构的关键。希望这篇分析可以帮助你更好地理解双向链表的实现和应用。

Full Code, this code can also be used at Leetcode 707. Design Linked List

class Node {
    val: number;
    next: Node;
    prev: Node;

    constructor(val: number) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class MyLinkedList {
    
    size: number;
    head: Node;
    tail: Node;
    
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    get(index: number): number {
        if (index < 0 || index >= this.size ) return -1;
        let curr = this.head;
        while (index > 0) {
            curr = curr.next;
            index--;
        }
        return curr.val;
    }

    addAtHead(val: number): void {
        let newHead = new Node(val);
        if (this.size === 0) {
            this.head = newHead;
            this.tail = newHead;
        } else {
            this.head.prev = newHead;
            newHead.next = this.head;
            this.head = newHead;
        }
        this.size++;
    }

    addAtTail(val: number): void {
        let newTail = new Node(val);
        if (this.size === 0) {
            this.head = newTail;
            this.tail = newTail;
        } else {
            this.tail.next = newTail;
            newTail.prev = this.tail;
            this.tail = newTail;
        }
        this.size++;
    }

    addAtIndex(index: number, val: number): void {
        if (index < 0 || index > this.size) return;
        if (index === 0) {
            this.addAtHead(val);
        } else if (index === this.size) {
            this.addAtTail(val);
        } else {
            let newNode = new Node(val);
            let prev = this.head;
            while (index - 1 > 0) {
                prev = prev.next;
                index--;
            }
            newNode.prev = prev;
            newNode.next = prev.next;
            prev.next.prev = newNode;
            prev.next = newNode;
            this.size++;
        }
    }

    deleteAtIndex(index: number): void {
        if (index < 0 || index >= this.size) return;
        if (index === 0) {
            this.head = this.head.next;
            if (this.size === 1) {
                this.tail = null;
            }
            this.size--;
        } else {
            let prev = this.head;
            while (index - 1 > 0) {
                prev = prev.next;
                index--;
            }
            prev.next = prev.next.next;
            if (prev.next) { // tail 不变
                prev.next.prev = prev;
            } else {
                this.tail = prev;
            }
            this.size--;   
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

Typescript Data Structures: Linked List

In the vast expanse of data structures available to developers, the LinkedList holds a unique place. Known for its efficiency in insertion and deletion operations, it’s a staple in algorithm design and application development. This post explores how to implement a LinkedList in TypeScript, bringing together the efficiency of this data structure with the strong typing and object-oriented features of TypeScript.

Understanding LinkedLists

Before diving into the code, let’s grasp the basics of a LinkedList. At its core, a LinkedList is a collection of nodes, where each node contains data and a reference (or a pointer) to the next node in the sequence. This structure allows for efficient additions and deletions as it avoids the necessity of reindexing elements, a common performance bottleneck in array manipulations.

Implementing Nodes in TypeScript

The foundation of our LinkedList is the node. Each node will store a value and a pointer to the next node. Here’s how we define it in TypeScript:

class Node {
    val: number;
    next: Node | null;

    constructor(val: number) {
        this.val = val; // The value stored in the node
        this.next = null; // Pointer to the next node, initially null
    }
}

This Node class is straightforward: it initializes with a value and sets the pointer to the next node as null.

The MyLinkedList Class

With our nodes defined, we next construct the LinkedList class, MyLinkedList. This class will manage our nodes and provide methods to interact with the list.

Constructor and Properties

class MyLinkedList {
    head: Node | null;
    tail: Node | null;
    size: number;

    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

Our LinkedList starts empty, signified by a null head and tail, with a size of 0.

Adding Elements

We provide three methods to add elements to our list: at the head, at the tail, and at a specific index.

• addAtHead(val: number): Inserts a new node with the provided value at the beginning of the list.
• addAtTail(val: number): Appends a new node with the provided value at the end of the list.
• addAtIndex(index: number, val: number): Inserts a new node at the specified index.

Each method updates the head, tail, and size properties accordingly to maintain the integrity of the list.

Retrieving and Deleting Elements

• get(index: number): Returns the value of the node at the specified index.
• deleteAtIndex(index: number): Removes the node at the specified index.

These methods ensure our LinkedList is dynamic, allowing retrieval and modification post-initialization.

Conclusion

Implementing a LinkedList in TypeScript is a rewarding exercise that deepens our understanding of both TypeScript and fundamental data structures. This guide has walked you through creating a flexible, type-safe LinkedList, suitable for various applications requiring efficient insertions and deletions. Whether you’re building a complex application or brushing up on data structures, the combination of TypeScript and LinkedLists is a powerful tool in your development arsenal.

Next Steps

Now that you’ve implemented a basic LinkedList, consider extending its functionality. Try adding methods to reverse the list, detect cycles, or merge two sorted lists. Each addition will not only improve your understanding of LinkedLists but also enhance your problem-solving skills in TypeScript.

Full Code

class Node {
    val: number;
    next: Node | null;

    constructor(val: number) {
        this.val = val; // The value stored in the node
        this.next = null; // Pointer to the next node, initially null
    }
}

class MyLinkedList {
    head: Node | null;
    tail: Node | null; // Pointer to the last node
    size: number; // The number of nodes in the list

    constructor() {
        this.head = null; // Initialize the head to null for an empty list
        this.tail = null; // Likewise for the tail
        this.size = 0; // Start with a list size of 0
    }

    // Adds a node at the front of the list
    addAtHead(val: number): void {
        const newNode = new Node(val);
        newNode.next = this.head;
        this.head = newNode;
        if (this.size === 0) {
            this.tail = newNode; // If the list was empty, this new node is also the tail
        }
        this.size++;
    }

    // Adds a node at the end of the list
    addAtTail(val: number): void {
        const newNode = new Node(val);
        if (this.size === 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.size++;
    }

    // Adds a node at the specified index
    addAtIndex(index: number, val: number): void {
        if (index < 0 || index > this.size) return; // Check for valid index
        if (index === 0) {
            this.addAtHead(val);
            return;
        }
        if (index === this.size) {
            this.addAtTail(val);
            return;
        }

        const newNode = new Node(val);
        let current = this.head;
        for (let i = 0; i < index - 1; i++) { // Iterate to the node before the desired index
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
        this.size++;
    }

    // Gets the value of the node at the specified index
    get(index: number): number {
        if (index < 0 || index >= this.size) return -1; // Check for valid index
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next;
        }
        return current.val;
    }

    // Deletes the node at the specified index
    deleteAtIndex(index: number): void {
        if (index < 0 || index >= this.size) return; // Check for valid index
        if (index === 0) {
            this.head = this.head.next;
            if (index === this.size - 1) { // If there was only one node, update tail to null
                this.tail = null;
            }
        } else {
            let current = this.head;
            for (let i = 0; i < index - 1; i++) {
                current = current.next;
            }
            current.next = current.next.next;
            if (index === this.size - 1) { // If deleting the last node, update tail
                this.tail = current;
            }
        }
        this.size--;
    }
}

Also this one can let you pass the Leetcode question: 707. Design Linked List

这个博客讲的就是TypeScript的单链表的实现方法啦，可以看看 抄抄，这个能让你直接通过Leetcode的第707题

在Bonaire岸潜 及Rescue Diver救援潜水员攻略

去年八月，我因为一直对潜水有着浓厚的兴趣，决定探索世界上不同的潜点，体验海底世界的多样性。考虑到上个月我刚从墨西哥回来，这次我想寻找一个与众不同的地方，于是选择了Bonaire——一个被誉为岸潜天堂的地方。我的目的一方面是为了考取PADI Rescue Diver证书，另一方面，也希望和朋友们一起尝试在没有潜水指导的情况下进行岸潜（Shore Dive)。

为什么选择博奈尔Bonaire

首先，对于持有H1B签证的旅行者来说，Bonaire是一个无需额外签证的目的地，省去了许多与签证相关的繁琐程序和不确定性。这个小小的便利，对于我们这些想要简化出行流程的人来说，简直是巨大的福音。

其次，从经济角度来看，Bonaire的性价比非常高。这里的气瓶租赁政策实在是太给力了—你可以以极其合理的价格享受无限次的气瓶换取服务。想象一下，一整天下来，只需要花费几十美元，你就可以尽情潜水，探索海底世界。而且，如果你持有高氧混合气体潜水证书，还可以享受到更高氧含量的气瓶，这对于深潜爱好者来说，无疑是个巨大的加分项。潜店的人会说：

只要你扛得动，就能带走

Bonaire当地使用美金消费，无需额外换汇，对于从美国出发的人来说挺友好便利的。

接下来要说的，是让Bonaire真正与众不同的原因——这里的水温通常维持在舒适的29度左右，非常适合长时间潜水。而且，Bonaire的珊瑚礁状态保持得相当好，生物多样性丰富，给潜水者们提供了极致的视觉享受。除此之外，岛上众多的潜点，包括美丽的珊瑚礁、各种各样的海洋生物以及引人入胜的沉船点，都为潜水爱好者提供了广泛的探索选项。

最后，岸潜的便利性是Bonaire另一个不可忽视的亮点。与需要乘坐船只出海才能到达潜点的其他潜水地区不同，Bonaire的许多潜点都可以直接从岸边进入，这意味着你可以根据自己的计划和节奏，随时享受潜水的乐趣，无需等待或依赖其他人的安排。

综上所述，Bonaire不仅为持有H1B签证的旅行者提供了便利，也以其经济的潜水成本、温暖的海水、保存良好的珊瑚礁以及多样的潜点，成为了潜水者心中的天堂。如果你是潜水爱好者，寻找一个既方便又充满探索乐趣的地方，那么Bonaire无疑值得一游。

下图是我和我小伙伴两人一天的气瓶数，一天只要45美金。

当天我乘坐的航班到达Bonaire, 降落的时候拍的小视频, 让我来看看是谁又来海岛🏝️度假啦～～

博奈尔的特色：毛驴

除了潜水，博奈尔还有一大特色就是岛上的毛驴。这些毛驴是岛上的一大标志，历史可以追溯到几百年前，当时它们被引入来作为工作动物。现在，虽然它们不再被用于劳动，但你可以在Donkey Sanctuary Bonaire——一个专门为这些毛驴提供庇护所的地方——见到它们。在这里，毛驴们被照顾得很好，游客还可以与它们互动，给它们喂食，这成为了游客们除了潜水之外的另一个亮点。

这是我在开车的时候遇到的小毛驴们～

住宿方面，我们选择了一个可以直接从房间下到海里的民宿，景色很好，晚上能躺在躺椅上看星星，上岸后在院子里直接又淋浴可以冲洗自己的设备。唯一要吐槽的一点就是，房间里有蟑螂！

岛上吃的很神奇的地方是，有很多中餐馆，可惜我们去的时候，有一家中餐馆关门了，我记得叫Jasmine Garden。另外有一点注意的是，岛上有一家KFC，味道和国内的KFC味道一样，有时间一定可以去尝尝！

Rescue Dive 是怎么上课的

首先，PADI的课程在每个地方每个潜店可能操作都不一样，就我的个人经历来说。我们是要分别在PADI的e-learning上面上两个课程， 一个是急救课程（陆地上的），一个才是真正的Rescue Diver的相关知识。

陆地上我们当时是上了两天，就是学习一些急救知识，简单的包扎，如何进行心肺复苏 CPR，这样的东西，不难，最后的考试就是，潜店会有员工模拟各种场景，让你去扮演急救人员，看你能不能正确排除危险。只有这个课程过了之后，才会给你进行接下来的水里的课程。

第三天我们开始下水了，在水里会教你如何正确的呼救，如何判断某个人需不需要救援，在水下如何把这个人安全的带到水面上，如何把溺水者拖拽到岸边，如何把人背到岸上，救援的先后顺序。学习了两天之后，最后的考试，也是情景模拟：

会有一个人扮演求救者，一个人扮演溺水者（真的在水底下呆着），求救者会过来说，Help me, my buddy just went missing! 然后她会给你指一个大概的方向，你需要保持方向感游出去大概几十米，然后采用水面（水下）搜寻的方式，找到这个溺水者，然后你需要下潜下去，确认他是否真的溺水，然后采用正确的姿势把他带出水面，注意升水的速度，到达水面后，你需要用一系列正确的顺序（给他的BCD充气，你的BCD充气，取下溺水者的眼罩，呼吸器，丢弃他的配重，你的配重，确认他是否有自主呼吸，没有的话，你需要在水面上把他拖拽到岸边，同时在确保他的头不沉到水里的情况下，每三秒钟给他进行一次人工呼吸。接近岸边的时候，要采用背的形式，把他背到岸上，同时每20秒进行一次人工呼吸，直到到了安全的地方，你要给溺水者带上氧气面罩，呼吸纯氧，然后不停的给溺水者做心肺复苏，直到救援人员到场）。整个考试下来，其实挺累的，因为，把一个人拖拽着游100米，再背上岸，再做两分钟心肺复苏，我是累的不行了反正。。。

接下来就能够获得心仪已久的救援潜水员（Rescue Diver）证书啦，持有这个证书，就可以去考潜水长（Dive Master）啦！走上职业道路～～

接下来的几天，我们就在博奈尔进行了很多次的岸潜（Shore Dive). 几个比较有名的潜点推荐：

1. 1000 Steps
   尽管名字听起来让人望而却步，但实际上从停车场到海边只有大约67个台阶。这个潜点因其清澈的水和丰富的海洋生物而受到潜水者的喜爱。这里是观察海龟、热带鱼和美丽珊瑚的绝佳地点。
2. Hilma Hooker (强烈推荐！！！！）
   这是一艘在1984年沉没的货船，现在成为了海底的一个人工礁，吸引了大量的海洋生物。沉船位于18至30米的水下，适合中级和高级潜水者探索。这里可以看到色彩斑斓的珊瑚、海绵以及各种鱼类。
3. Salt Pier
   这个潜点因其独特的景观而闻名——一系列庞大的支柱支撑着用于盐矿业务的码头。水下的柱子被各种珊瑚和海绵覆盖，是摄影爱好者的天堂。在这里，潜水者经常可以看到大型的糖尿病鱼、章鱼和偶尔的鹰瑶。

这只是众多潜点中的一些我们去过的，接下来请大家欣赏我拍的水下视频吧～！包括了1，2，3哦～～

448. Find All Numbers Disappeared in an Array

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Input: nums = [1,1]
Output: [2]

Problem Analysis: The task is to find all the numbers missing from 1 to n in a given array, which might contain duplicate numbers and should be solved without using extra space (except for the output).

Solution Approach: We can leverage the array itself by marking the presence of numbers. Specifically, we traverse the array and turn the number at the index corresponding to each encountered number into negative as a mark. Since the numbers in the array are all supposed to be between 1 and n, we can directly use the number value as the array index.

Time and Space Complexity Analysis: The time complexity is O(n), as we only need to traverse the array twice. The space complexity is O(1), as no extra space is used apart from the output.

Conclusion: This method effectively utilizes the structure of the array itself to mark the presence of numbers, thereby identifying the missing ones, while avoiding the use of extra space.

题目分析： 这个问题要求我们找出在1到n之间但没有出现在给定数组中的所有数字。数组中可能有重复数字，且没有额外空间使用（除了输出结果之外）。

解题思路： 我们可以利用数组自身，通过标记已存在的数字来找出缺失的数字。具体来说，我们可以遍历数组，并将出现的数字对应位置上的数值变为负数，作为标记。因为数组中的数字都应该在1到n之间，所以可以直接用数字值作为数组索引。

代码实现：

function findDisappearedNumbers(nums: number[]): number[] {
    let res = [];
    for (let num of nums) {
        let index = Math.abs(num) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            res.push(i + 1);
        }
    }
    return res;
}

时间和空间复杂度分析： 时间复杂度为O(n)，因为我们只需要遍历数组两次。空间复杂度为O(1)，因为除了输出结果外，我们没有使用额外的空间。

测试用例：

console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // 输出 [5,6]

总结： 这个方法有效地利用了数组本身的结构来标记存在的数字，从而找出缺失的数字，同时避免了额外的空间使用。

414. Third Maximum Number

Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.

Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

Approach 1:

Three pointers

Problem Analysis: LeetCode problem 414 “Third Maximum Number” asks us to find the third largest number in an array. If it doesn’t exist, return the largest number. While this could be solved by sorting, we aim for a more efficient approach.

Solution Approach:

1. Use three variables to track the first, second, and third largest numbers.
2. Iterate through the array, updating these variables as needed.
3. Pay attention to duplicates and special cases.

Time and Space Complexity Analysis:

• Time Complexity: O(n), as we only need to pass through the array once.
• Space Complexity: O(1), as we use a fixed amount of extra space.

题目分析： LeetCode问题414 “Third Maximum Number” 要求我们在数组中找到第三大的数。如果不存在，返回最大的数。这个问题可以通过排序来解决，但是我们希望找到一种更有效的方法。

解题思路：

1. 使用三个变量来追踪第一大、第二大和第三大的数。
2. 遍历数组，更新这三个变量。
3. 注意去重和特殊情况处理。

时间和空间复杂度分析：

• 时间复杂度：O(n)，我们只需要遍历一次数组。
• 空间复杂度：O(1)，我们只用到有限的额外空间。

function thirdMax(nums: number[]): number {
    // Initialize three variables to track the largest, second largest, and third largest numbers
    let first = Number.MIN_SAFE_INTEGER, second = Number.MIN_SAFE_INTEGER, third = Number.MIN_SAFE_INTEGER;
    for (let num of nums) {
        // Skip duplicate numbers
        if (num === first || num === second || num === third) continue;
        if (num > first) { // Update the first, second, and third largest numbers
            [third, second, first] = [second, first, num];
        } else if (num > second) {
            [third, second] = [second, num];
        } else if (num > third) {
            third = num;
        }
    }
    return third !== Number.MIN_SAFE_INTEGER ? third : first;
}

487. Max Consecutive Ones II

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

Input: nums = [1,0,1,1,0,1]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones.
The max number of consecutive ones is 4.

题目分析： 这道题目要求我们找出在最多可以翻转一个0的情况下，最长的连续1的长度。这是一个典型的滑动窗口问题，也涉及到了数组的遍历。

解题思路：

1. 初始化两个指针left和right，用于标记窗口的左右边界，以及一个变量zeros来记录窗口中0的数量。
2. 移动right指针扩展窗口，如果遇到0，则zeros增加。
3. 当窗口内的0的数量超过1时，移动left指针以缩小窗口，直到窗口内再次只有一个0或没有0。
4. 在每一步中，如果窗口内的0的数量不超过1，更新最大长度。

**时间复杂度：**O(n)，其中n是数组的长度，因为每个元素只被访问一次。

**空间复杂度：**O(1)，只使用了固定的额外空间。

Problem Analysis: This problem asks us to find the maximum length of consecutive 1s that can be achieved by flipping at most one 0. This is a classic sliding window problem, also involving array traversal.

Solution Approach:

1. Initialize two pointers, left and right, to mark the boundaries of the window, and a variable zeros to count the number of zeros within the window.
2. Move the right pointer to expand the window, increase zeros if encountering a 0.
3. When the number of zeros within the window exceeds one, move the left pointer to reduce the window until there is only one or no zero within it again.
4. At each step, if the number of zeros within the window does not exceed one, update the maximum length.

Time Complexity: O(n), where n is the length of the array, as each element is visited only once.

Space Complexity: O(1), as only a fixed amount of extra space is used.

function findMaxConsecutiveOnes(nums: number[]): number {
    if (nums.length === 1) return 1;
    let left = 0, right = 0, zeros = 0;
    let max = 0;
    for (; right < nums.length; right++) {
        if (nums[right] === 0) {
            zeros++;
        }
        if (zeros <= 1) { // valid, continue
            max = Math.max(max, right - left + 1);
        } else {
            // Move left until it escapse a 0
            while (nums[left] !== 0) {
                left++;
            }
            left++;
            zeros--;
        }
    }
    return max;
};

905. Sort Array By Parity

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Input: nums = [0]
Output: [0]

题目分析： 题目要求我们按奇偶排序数组，所有的偶数应该在所有的奇数之前。这是一个很常见的数组操作问题，可以通过双指针的方法来解决。

解题思路：

1. 设置两个指针，left和right，其中left从数组的开始处向后移动，right从数组的末尾向前移动。
2. 当left指向偶数，left++，向右移动；当right指向奇数，right--，向左移动。
3. 如果left指向奇数且right指向偶数，则交换这两个元素。
4. 重复上述过程，直到left >= right。

时间和空间复杂度分析：

**时间复杂度：**这个算法的时间复杂度是O(n)，其中n是数组的长度。这是因为我们使用两个指针从数组的两端向中间扫描，每个元素最多被访问一次。

**空间复杂度：**这个算法的空间复杂度是O(1)，因为我们只是在原数组上进行交换操作，没有使用额外的数组或数据结构。

为什么双指针方法在此问题上有效：

双指针方法之所以有效，是因为它利用了问题的特性：我们需要将偶数和奇数分开。通过设置两个指针，一个从开始处向后扫描寻找奇数，另一个从末尾向前扫描寻找偶数，我们可以有效地在一次遍历中将偶数和奇数分到数组的两边。

这种方法之所以高效，是因为它直接在原数组上进行操作，减少了额外的内存分配和移动，同时确保了每个元素都只被查看和移动一次。因此，它是对数组进行分类的一种快速而内存高效的方法。

Problem Analysis: The task is to sort an array by parity, with all even elements preceding all odd ones. This is a common array manipulation issue that can be addressed using the two-pointers technique.

Solution Idea:

1. Set two pointers, left and right, where left moves forward from the start of the array and right moves backward from the end of the array.
2. Move left forward when it points to an even number; move right backward when it points to an odd number.
3. If left points to an odd number and right points to an even number, swap these two elements.
4. Repeat the above steps until left >= right.

Time and Space Complexity Analysis:

Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the array. This is because we use two pointers to scan from both ends of the array towards the center, with each element being visited at most once.

Space Complexity: The space complexity of this algorithm is O(1), as we are merely swapping elements within the original array without using any additional arrays or data structures.

Why the Two-Pointer Approach is Effective for this Problem:

The two-pointer approach is effective for this problem because it leverages the specific nature of the task: separating even and odd numbers. By setting one pointer to scan forward from the beginning for odd numbers and another to scan backward from the end for even numbers, we can efficiently separate the evens and odds within the array in a single pass.

This method is efficient because it operates directly on the original array, reducing extra memory allocation and movement while ensuring that each element is only examined and moved once. Therefore, it is a fast and memory-efficient method for partitioning an array.

TypeScript代码：

function sortArrayByParity(nums: number[]): number[] {
    let l = 0, r = nums.length - 1;
    while (l < r) {
        while (l < r && nums[l] % 2 === 0) l++;
        while (l < r && nums[r] % 2 !== 0) r--;
        if (l < r) {
            [nums[l], nums[r]] = [nums[r], nums[l]];
            l++;
            r--;
        }
    }
    return nums;
};

Check If N and Its Double Exist

Input: arr = [10,2,5,3]
Output: true
Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Input: arr = [3,1,7,11]
Output: false
Explanation: There is no i and j that satisfy the conditions.

题目 1346. “Check If N and Its Double Exist” 要求我们检查一个给定的整数数组中是否存在某个数 N 以及其值的两倍存在。换句话说，我们需要检查是否存在两个不同的索引 i 和 j，使得 arr[i] == 2 * arr[j] 或 arr[j] == 2 * arr[i]。

1. Initialization: Create a hash set to store each element of the array for quick checking whether a number or its double exists.
2. Traverse the Array: Iterate through the given integer array. For each element n, we do the following:
   • Check if the double of n or n / 2 (when n is even) exists in the hash set. If yes, return true as we have found a pair satisfying the condition.
   • Add n to the hash set for future lookup.
3. Return the Result: If we have traversed the entire array without finding any satisfying pair, then return false.
   

为什么这个代码可以满足i != j？

我们确保了i != j的条件通过以下方式得到满足：

当我们遍历数组 arr 中的每个元素时，我们检查当前元素的两倍或当前元素的一半是否已经存在于seen这个集合中。这里的关键是，在我们将当前元素添加到seen集合之前，我们会先进行检查。

这意味着，如果我们发现当前元素的两倍或一半已经在seen中，那么这两个数字一定是来自数组中的不同位置。为什么呢？因为我们还没有将当前元素加入到seen集合中，所以seen集合中的任何元素都是之前遍历过的，也就是说，它们来自当前元素的前面的数组索引。

因此，当我们在seen集合中找到当前元素的两倍或一半时，这相当于说我们找到了数组中的另一个元素（即之前遍历过的，索引比当前元素小的元素），它满足了题目中的条件，同时也确保了这两个元素（arr[i] 和 arr[j]）是不同的元素（因为它们位于数组的不同位置）。

在逻辑上，我们始终是在检查当前索引之前的元素（通过集合seen），所以当找到匹配项时，这个匹配必然来源于一个不同的索引，即满足了i != j的条件。

function checkIfExist(arr: number[]): boolean {
    const seen: Set<number> = new Set();
    for (const num of arr) {
        if (seen.has(2 * num) || (num % 2 === 0 && seen.has(num / 2))) {
            return true;
        }
        seen.add(num);
    }
    return false;

};

3. Longest Substring Without Repeating Characters

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

The Best Ways to Do Market Research For Your Business Plan.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

First, solve the problem. Then write the code.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

A programming language is for thinking about programs, not for expressing programs you’ve already thought of. It should be a pencil, not a pen.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commodo .

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

The Easiest Way to Become a Successful Writer and Authors.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

First, solve the problem. Then write the code.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

A programming language is for thinking about programs, not for expressing programs you’ve already thought of. It should be a pencil, not a pen.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commodo .

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

The Quickest Way to Deliver Your Message? Make It Visual.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

First, solve the problem. Then write the code.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

A programming language is for thinking about programs, not for expressing programs you’ve already thought of. It should be a pencil, not a pen.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commodo .

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Why We Don’t Have Technical Interviews for Technical Roles at Buffer.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

First, solve the problem. Then write the code.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

A programming language is for thinking about programs, not for expressing programs you’ve already thought of. It should be a pencil, not a pen.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commodo .

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Why Successful People Wear The Same Thing Every Day.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

First, solve the problem. Then write the code.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

A programming language is for thinking about programs, not for expressing programs you’ve already thought of. It should be a pencil, not a pen.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commodo .

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

What I Learned From Being a Broke, Unemployed Graduate.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks.

First, solve the problem. Then write the code.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

A programming language is for thinking about programs, not for expressing programs you’ve already thought of. It should be a pencil, not a pen.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Quis ipsum suspendisse ultrices gravida. Risus commodo .

There are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injected humour, or randomised words which don’t look even slightly believable. If you are going to use a passage of Lorem Ipsum. You need to be sure there isn’t anything embarrassing hidden in the middle of text. All the Lorem Ipsum generators on the Internet tend toitrrepeat predefined chunks. Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lorem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.

Necessary, making this the first true generator on the Internet. It re are many variations of passages of Lo rem Ipsum available, but the majority have suffered alteration in some form, by injectedeed eedhumour, or randomised words which don’t look even slightly believable.