面试问题编码的常见策略
两个指针
两个指针技术经常被用来有效地解决数组相关的问题。它涉及使用两个指针，它们要么朝彼此移动，要么朝同一方向移动。
示例：在排序数组中查找总和为目标值的一对数字。
/**
* 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 usage
const 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 < arr.length; i++) {
// remove the first element of the previous window and add the last element of the new window
windowsum = windowsum - arr[i - k] + arr[i];
console.log(`new window sum: ${windowsum}, window: [${arr.slice(i - k + 1, i + 1)}]`);
// update maxsum if the current window sum is greater
if (windowsum > 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);
此示例演示了各种 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 usage
const 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 right half`);
left = mid + 1;
} else {
console.log(`${arr[mid]} > ${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);
此实现展示了二分搜索如何在每次迭代中有效地将搜索范围缩小一半，使其比大型排序数组的线性搜索快得多。
- 深度优先搜索（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 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'));
广度优先搜索 (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] < this.heap[smallest]) {
smallest = right;
}
if (smallest !== i) {
this.swap(i, smallest);
this.heapifydown(smallest);
}
}
}
// example usage
const minheap = new minheap();
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5].foreach(num => 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 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');
并查集（不相交集）
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 usage
const 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: true
console.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 usage
const 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());
这些实现为在编码面试和实际应用中理解和使用这些重要的算法和数据结构提供了坚实的基础。
