编码面试中解决问题的终极指南

/**
 * finds a pair of numbers in a sorted array that sum up to a target value.
 * uses the two-pointer technique for efficient searching.
 * 
 * @param {number[]} arr - the sorted array of numbers to search through.
 * @param {number} target - the target sum to find.
 * @returns {number[]|null} - returns an array containing the pair if found, or null if not found.
 */
function findpairwithsum(arr, target) {
  // initialize two pointers: one at the start and one at the end of the array
  let left = 0;
  let right = arr.length - 1;

  // continue searching while the left pointer is less than the right pointer
  while (left 



<h2>
  
  
  滑动窗口
</h2>

<p>滑动窗口技术对于解决涉及数组或字符串中连续序列的问题非常有用。</p>

<p>示例：查找大小为 k 的子数组的最大和。<br></p>

<pre class="brush:php;toolbar:false">/**
 * finds the maximum sum of a subarray of size k in the given array.
 * @param {number[]} arr - the input array of numbers.
 * @param {number} k - the size of the subarray.
 * @returns {number|null} the maximum sum of a subarray of size k, or null if the array length is less than k.
 */
function maxsubarraysum(arr, k) {
  // check if the array length is less than k
  if (arr.length  maxsum) {
      maxsum = windowsum;
      console.log(`new max sum found: ${maxsum}, window: [${arr.slice(i - k + 1, i + 1)}]`);
    }
  }

  console.log(`final max sum: ${maxsum}`);
  return maxsum;
}

// example usage
const array = [1, 4, 2, 10, 23, 3, 1, 0, 20];
const k = 4;
maxsubarraysum(array, k);

/**
 * finds the first non-repeating character in a given string.
 * @param {string} str - the input string to search.
 * @returns {string|null} the first non-repeating character, or null if not found.
 */
function firstnonrepeatingchar(str) {
  const charcount = new map();

  // count occurrences of each character
  for (let char of str) {
    charcount.set(char, (charcount.get(char) || 0) + 1);
    console.log(`character ${char} count: ${charcount.get(char)}`);
  }

  // find the first character with count 1
  for (let char of str) {
    if (charcount.get(char) === 1) {
      console.log(`first non-repeating character found: ${char}`);
      return char;
    }
  }

  console.log("no non-repeating character found");
  return null;
}

// example usage
const inputstring = "aabccdeff";
firstnonrepeatingchar(inputstring);

// create a new map
const fruitinventory = new map();

// set key-value pairs
fruitinventory.set('apple', 5);
fruitinventory.set('banana', 3);
fruitinventory.set('orange', 2);

console.log('initial inventory:', fruitinventory);

// get a value using a key
console.log('number of apples:', fruitinventory.get('apple'));

// check if a key exists
console.log('do we have pears?', fruitinventory.has('pear'));

// update a value
fruitinventory.set('banana', fruitinventory.get('banana') + 2);
console.log('updated banana count:', fruitinventory.get('banana'));

// delete a key-value pair
fruitinventory.delete('orange');
console.log('inventory after removing oranges:', fruitinventory);

// iterate over the map
console.log('current inventory:');
fruitinventory.foreach((count, fruit) => {
  console.log(`${fruit}: ${count}`);
});

// get the size of the map
console.log('number of fruit types:', fruitinventory.size);

// clear the entire map
fruitinventory.clear();
console.log('inventory after clearing:', fruitinventory);

/**
 * calculates the nth fibonacci number using dynamic programming.
 * @param {number} n - the position of the fibonacci number to calculate.
 * @returns {number} the nth fibonacci number.
 */
function fibonacci(n) {
  // initialize an array to store fibonacci numbers
  const fib = new array(n + 1);

  // base cases
  fib[0] = 0;
  fib[1] = 1;

  console.log(`f(0) = ${fib[0]}`);
  console.log(`f(1) = ${fib[1]}`);

  // calculate fibonacci numbers iteratively
  for (let i = 2; i 



<p>此示例演示了动态编程如何通过存储先前计算的值并将其用于将来的计算来有效地计算斐波那契数。</p>

<h2>
  
  
  二分查找教程
</h2>

<p>二分搜索是一种在排序数组中查找元素的有效算法。这是带有详细日志记录的实现：<br></p>

<pre class="brush:php;toolbar:false">/**
 * performs a binary search on a sorted array.
 * @param {number[]} arr - the sorted array to search.
 * @param {number} target - the value to find.
 * @returns {number} the index of the target if found, or -1 if not found.
 */
function binarysearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left  ${target}, searching left half`);
      right = mid - 1;
    }
  }

  console.log(`target ${target} not found in the array`);
  return -1;
}

// example usage
const sortedarray = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 7;
binarysearch(sortedarray, target);

class graph {
  constructor() {
    this.adjacencylist = {};
  }

  addvertex(vertex) {
    if (!this.adjacencylist[vertex]) this.adjacencylist[vertex] = [];
  }

  addedge(v1, v2) {
    this.adjacencylist[v1].push(v2);
    this.adjacencylist[v2].push(v1);
  }

  dfs(start) {
    const result = [];
    const visited = {};
    const adjacencylist = this.adjacencylist;

    (function dfshelper(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      console.log(`visiting vertex: ${vertex}`);

      adjacencylist[vertex].foreach(neighbor => {
        if (!visited[neighbor]) {
          console.log(`exploring neighbor: ${neighbor} of vertex: ${vertex}`);
          return dfshelper(neighbor);
        } else {
          console.log(`neighbor: ${neighbor} already visited`);
        }
      });
    })(start);

    return result;
  }
}

// example usage
const graph = new graph();
['a', 'b', 'c', 'd', 'e', 'f'].foreach(vertex => graph.addvertex(vertex));
graph.addedge('a', 'b');
graph.addedge('a', 'c');
graph.addedge('b', 'd');
graph.addedge('c', 'e');
graph.addedge('d', 'e');
graph.addedge('d', 'f');
graph.addedge('e', 'f');

console.log(graph.dfs('a'));

class graph {
  // ... (same constructor, addvertex, and addedge methods as above)

  bfs(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    visited[start] = true;

    while (queue.length) {
      let vertex = queue.shift();
      result.push(vertex);
      console.log(`visiting vertex: ${vertex}`);

      this.adjacencylist[vertex].foreach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
          console.log(`adding neighbor: ${neighbor} to queue`);
        } else {
          console.log(`neighbor: ${neighbor} already visited`);
        }
      });
    }

    return result;
  }
}

// example usage (using the same graph as in dfs example)
console.log(graph.bfs('a'));

class minheap {
  constructor() {
    this.heap = [];
  }

  getparentindex(i) {
    return math.floor((i - 1) / 2);
  }

  getleftchildindex(i) {
    return 2 * i + 1;
  }

  getrightchildindex(i) {
    return 2 * i + 2;
  }

  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }

  insert(key) {
    this.heap.push(key);
    this.heapifyup(this.heap.length - 1);
  }

  heapifyup(i) {
    let currentindex = i;
    while (this.heap[currentindex]  minheap.insert(num));
console.log(minheap.heap);
console.log(minheap.extractmin());
console.log(minheap.heap);

class trienode {
  constructor() {
    this.children = {};
    this.isendofword = false;
  }
}

class trie {
  constructor() {
    this.root = new trienode();
  }

  insert(word) {
    let current = this.root;
    for (let char of word) {
      if (!current.children[char]) {
        current.children[char] = new trienode();
      }
      current = current.children[char];
    }
    current.isendofword = true;
    console.log(`inserted word: ${word}`);
  }

  search(word) {
    let current = this.root;
    for (let char of word) {
      if (!current.children[char]) {
        console.log(`word ${word} not found`);
        return false;
      }
      current = current.children[char];
    }
    console.log(`word ${word} ${current.isendofword ? 'found' : 'not found'}`);
    return current.isendofword;
  }

  startswith(prefix) {
    let current = this.root;
    for (let char of prefix) {
      if (!current.children[char]) {
        console.log(`no words start with ${prefix}`);
        return false;
      }
      current = current.children[char];
    }
    console.log(`found words starting with ${prefix}`);
    return true;
  }
}

// example usage
const trie = new trie();
['apple', 'app', 'apricot', 'banana'].foreach(word => trie.insert(word));
trie.search('app');
trie.search('application');
trie.startswith('app');
trie.startswith('ban');

class unionfind {
  constructor(size) {
    this.parent = array(size).fill().map((_, i) => i);
    this.rank = array(size).fill(0);
    this.count = size;
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    let rootx = this.find(x);
    let rooty = this.find(y);

    if (rootx === rooty) return;

    if (this.rank[rootx] 



<h2>
  
  
  拓扑排序
</h2>

<p>拓扑排序用于对具有依赖关系的任务进行排序。这是使用 dfs 的实现：<br></p>

<pre class="brush:php;toolbar:false">class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
  }

  topologicalSort() {
    const visited = {};
    const stack = [];

    const dfsHelper = (vertex) =&gt; {
      visited[vertex] = true;
      this.adjacencyList[vertex].forEach(neighbor =&gt; {
        if (!visited[neighbor]) {
          dfsHelper(neighbor);
        }
      });
      stack.push(vertex);
      console.log(`Added ${vertex} to stack`);
    };

    for (let vertex in this.adjacencyList) {
      if (!visited[vertex]) {
        dfsHelper(vertex);
      }
    }

    return stack.reverse();
  }
}

// Example usage
const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F'].forEach(vertex =&gt; graph.addVertex(vertex));
graph.addEdge('A', 'C');
graph.addEdge('B', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');

console.log(graph.topologicalSort());