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

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

面试问题编码的常见策略

两个指针

两个指针技术经常被用来有效地解决数组相关的问题。它涉及使用两个指针,它们要么朝彼此移动,要么朝同一方向移动。

示例:在排序数组中查找总和为目标值的一对数字。

/** * 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 < right) {    console.log(`checking pair: ${arr[left]} and ${arr[right]}`);    // calculate the sum of the current pair    const sum = arr[left] + arr[right];    if (sum === target) {      // if the sum equals the target, we've found our pair      console.log(`found pair: ${arr[left]} + ${arr[right]} = ${target}`);      return [arr[left], arr[right]];    } else if (sum < target) {      // if the sum is less than the target, we need a larger sum      // so, we move the left pointer to the right to increase the sum      console.log(`sum ${sum} is less than target ${target}, moving left pointer`);      left++;    } else {      // if the sum is greater than the target, we need a smaller sum      // so, we move the right pointer to the left to decrease the sum      console.log(`sum ${sum} is greater than target ${target}, moving right pointer`);      right--;    }  }  // if we've exhausted all possibilities without finding a pair, return null  console.log("no pair found");  return null;}// example usageconst sortedarray = [1, 3, 5, 7, 9, 11];const targetsum = 14;findpairwithsum(sortedarray, targetsum);

登录后复制

滑动窗口

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

示例:查找大小为 k 的子数组的最大和。

/** * 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 < k) {    console.log("array length is less than k");    return null;  }  let maxsum = 0;  let windowsum = 0;  // calculate sum of first window  for (let i = 0; i < k; i++) {    windowsum += arr[i];  }  maxsum = windowsum;  console.log(`initial window sum: ${windowsum}, window: [${arr.slice(0, k)}]`);  // slide the window and update the maximum sum  for (let i = k; i  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 usageconst 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 usageconst inputstring = "aabccdeff";firstnonrepeatingchar(inputstring);

登录后复制

这些策略展示了解决常见编码面试问题的有效方法。每个示例中的详细日志记录有助于理解算法的逐步过程,这在面试中解释您的思维过程至关重要。

这是一个代码块,演示如何使用映射来更好地理解其中一些操作:

// create a new mapconst fruitinventory = new map();// set key-value pairsfruitinventory.set('apple', 5);fruitinventory.set('banana', 3);fruitinventory.set('orange', 2);console.log('initial inventory:', fruitinventory);// get a value using a keyconsole.log('number of apples:', fruitinventory.get('apple'));// check if a key existsconsole.log('do we have pears?', fruitinventory.has('pear'));// update a valuefruitinventory.set('banana', fruitinventory.get('banana') + 2);console.log('updated banana count:', fruitinventory.get('banana'));// delete a key-value pairfruitinventory.delete('orange');console.log('inventory after removing oranges:', fruitinventory);// iterate over the mapconsole.log('current inventory:');fruitinventory.foreach((count, fruit) => {  console.log(`${fruit}: ${count}`);});// get the size of the mapconsole.log('number of fruit types:', fruitinventory.size);// clear the entire mapfruitinventory.clear();console.log('inventory after clearing:', fruitinventory);

登录后复制

此示例演示了各种 map 操作:

创建新地图使用 添加键值对使用 检索值使用 检查密钥是否存在更新值使用 删除键值对使用 迭代地图获取地图的大小清除整个地图 这些操作与firstnonrepeatingchar函数中使用的操作类似,我们使用map来统计字符出现的次数,然后搜索计数为1的第一个字符。

动态规划教程

动态编程是一种强大的算法技术,用于通过将复杂问题分解为更简单的子问题来解决复杂问题。让我们通过计算斐波那契数的示例来探讨这个概念。

/** * 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 <= n; i++) {    fib[i] = fib[i - 1] + fib[i - 2];    console.log(`f(${i}) = ${fib[i]}`);  }  return fib[n];}// example usageconst n = 10;console.log(`the ${n}th fibonacci number is:`, fibonacci(n));

登录后复制

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

二分查找教程

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

/** * 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 <= right) {    const mid = math.floor((left + right) / 2);    console.log(`searching in range [${left}, ${right}], mid = ${mid}`);    if (arr[mid] === target) {      console.log(`target ${target} found at index ${mid}`);      return mid;    } else if (arr[mid] < target) {      console.log(`${arr[mid]}  ${target}, searching left half`);      right = mid - 1;    }  }  console.log(`target ${target} not found in the array`);  return -1;}// example usageconst sortedarray = [1, 3, 5, 7, 9, 11, 13, 15];const target = 7;binarysearch(sortedarray, target);

登录后复制

此实现展示了二分搜索如何在每次迭代中有效地将搜索范围缩小一半,使其比大型排序数组的线性搜索快得多。

深度优先搜索(dfs)广度优先搜索(bfs)堆(优先级队列)trie(前缀树)并查(不相交集)拓扑排序

深度优先搜索 (dfs)

深度优先搜索是一种图遍历算法,在回溯之前沿着每个分支尽可能地探索。以下是表示为邻接列表的图的示例实现:

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 usageconst 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'));

登录后复制

广度优先搜索 (bfs)

bfs 会探索当前深度的所有顶点,然后再移动到下一个深度级别的顶点。这是一个实现:

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] < this.heap[this.getparentindex(currentindex)]) {      this.swap(currentindex, this.getparentindex(currentindex));      currentindex = this.getparentindex(currentindex);    }  }  extractmin() {    if (this.heap.length === 0) return null;    if (this.heap.length === 1) return this.heap.pop();    const min = this.heap[0];    this.heap[0] = this.heap.pop();    this.heapifydown(0);    return min;  }  heapifydown(i) {    let smallest = i;    const left = this.getleftchildindex(i);    const right = this.getrightchildindex(i);    if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {      smallest = left;    }    if (right < this.heap.length && this.heap[right]  minheap.insert(num));console.log(minheap.heap);console.log(minheap.extractmin());console.log(minheap.heap);

登录后复制

trie(前缀树)

trie 是一种高效的信息检索数据结构,常用于字符串搜索:

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 usageconst trie = new trie();['apple', 'app', 'apricot', 'banana'].foreach(word => trie.insert(word));trie.search('app');trie.search('application');trie.startswith('app');trie.startswith('ban');

登录后复制

并查集(不相交集)

union-find 是一种数据结构,用于跟踪被分成一个或多个不相交集合的元素:

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] < this.rank[rooty]) {      [rootx, rooty] = [rooty, rootx];    }    this.parent[rooty] = rootx;    if (this.rank[rootx] === this.rank[rooty]) {      this.rank[rootx]++;    }    this.count--;    console.log(`united ${x} and ${y}`);  }  connected(x, y) {    return this.find(x) === this.find(y);  }}// example usageconst uf = new unionfind(10);uf.union(0, 1);uf.union(2, 3);uf.union(4, 5);uf.union(6, 7);uf.union(8, 9);uf.union(0, 2);uf.union(4, 6);uf.union(0, 4);console.log(uf.connected(1, 5)); // should print: trueconsole.log(uf.connected(7, 9)); // should print: false

登录后复制

拓扑排序

拓扑排序用于对具有依赖关系的任务进行排序。这是使用 dfs 的实现:

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) => {      visited[vertex] = true;      this.adjacencyList[vertex].forEach(neighbor => {        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 usageconst graph = new Graph();['A', 'B', 'C', 'D', 'E', 'F'].forEach(vertex => 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());

登录后复制

这些实现为在编码面试和实际应用中理解和使用这些重要的算法和数据结构提供了坚实的基础。

以上就是编码面试中解决问题的终极指南的详细内容,更多请关注【创想鸟】其它相关文章!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至253000106@qq.com举报,一经查实,本站将立刻删除。

发布者:PHP中文网,转转请注明出处:https://www.chuangxiangniao.com/p/2668461.html

(0)
上一篇 2025年3月7日 12:32:00
下一篇 2025年2月24日 02:38:06

AD推荐 黄金广告位招租... 更多推荐

相关推荐

  • 每个开发人员都应该了解的高级 JavaScript 概念

    javascript 是许多开发人员日常使用的语言,但其生态系统中存在许多隐藏的瑰宝,即使是经验丰富的开发人员也可能不熟悉。本文探讨了一些鲜为人知的 javascript 概念,它们可以显着提高您的编程技能。我们将介绍诸如 代理、符号、生成…

    2025年3月7日
    200
  • JavaScript 是同步还是异步,是单线程还是多线程? JavaScript代码是如何执行的?

    javascript 是一种同步、单线程语言,一次只能执行一个命令。仅当当前行执行完毕后,才会移至下一行。但是,javascript 可以使用事件循环、promises、async/await 和回调队列执行异步操作(javascript …

    2025年3月7日
    200
  • 如何为 TypeScript 项目自定义 tsconfig.json 文件

    tsconfig.json 文件是一个功能强大的工具,允许您自定义 TypeScript 编译器的行为以满足项目的特定需求。通过调整此配置文件中的编译器选项,您可以根据项目的要求定制 TypeScript,从而更好地控制类型检查、模块解析和…

    2025年3月7日
    200
  • [Leetcode] 对象是否为空

    问题链接:https://leetcode.com/problems/is-object-empty/description/ [问题陈述] 给定一个对象或数组,如果为空则返回。 空对象不包含键值对。空数组不包含任何元素。 您可以假设对象或…

    2025年3月7日
    200
  • extjs API 查询参数示例

    api 查询 参数是附加到 api 请求的 url 的键值对,用于向服务器发送附加信息。它们允许客户端(例如网络浏览器或应用程序)在向服务器发出请求时指定某些条件或传递数据。 查询参数添加到 url 末尾的问号 (?) 后面。每个参数都是一…

    2025年3月7日
    200
  • typescript的数据类型

    TypeScript 提供了强类型安全性,强制执行变量和表达式的明确数据类型。它支持基本类型(数字、字符串、布尔值、空值和未定义值)和引用类型(数组、对象和函数),以及枚举类型、联合类型、类型别名和类型断言,从而提高了代码的可维护性、可读性…

    2025年3月7日
    200
  • typescript定义数据类型

    TypeScript 中的数据类型用于指定变量存储的值的类型,从而确保代码类型安全和防止运行时错误。这些数据类型包括:基本数据类型:number、string、boolean、null 和 undefined复合数据类型:数组、对象和 en…

    2025年3月7日
    200
  • typescript的数据类型有哪些

    TypeScript 是强类型语言,数据类型包括:原始数据类型:number、string、boolean、null、undefined结构化数据类型:array、object、tuple、enum函数数据类型:function、arrow…

    2025年3月7日
    200
  • Javascript重要概念||重要的 JavaScript 概念

    逐步使用代码示例来帮助您更好地理解每个概念。 1. js简介 javascript 是一种多功能语言,可以在浏览器或服务器上运行(使用 node.js)。它用于使网页具有交互性。 hello, javascript! click me fu…

    2025年3月7日
    200
  • js如何定义对象

    JavaScript 中,对象是一种键值对数据结构,使用花括号定义,键值对以冒号分隔,键值对之间以逗号分隔。可以通过点符号或方括号访问和修改属性,还可以添加或删除属性。对象可以嵌套其他对象,通过点符号访问嵌套属性。 如何在 JavaScri…

    2025年3月7日
    200

发表回复

登录后才能评论