
面試問題編碼的常見策略
兩個指針
兩個指標技術經常被用來有效地解決數組相關的問題。它涉及使用兩個指針,它們要么朝彼此移動,要么朝同一方向移動。
範例:在排序數組中找出總和為目標值的一對數字。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
function findPairWithSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
console.log(`Checking pair: ${arr[left]} and ${arr[right]}`);
const sum = arr[left] + arr[right];
if (sum === target) {
console.log(`Found pair: ${arr[left]} + ${arr[right]} = ${target}`);
return [arr[left], arr[right]];
} else if (sum < target) {
console.log(`Sum ${sum} is less than target ${target}, moving left pointer`);
left++;
} else {
console.log(`Sum ${sum} is greater than target ${target}, moving right pointer`);
right--;
}
}
console.log( "No pair found" );
return null;
}
const sortedArray = [1, 3, 5, 7, 9, 11];
const targetSum = 14;
findPairWithSum(sortedArray, targetSum);
|
登入後複製
滑動視窗
滑動視窗技術對於解決涉及陣列或字串中連續序列的問題非常有用。
範例:找出大小為 k 的子陣列的最大和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
function maxSubarraySum(arr, k) {
if (arr.length < k) {
console.log( "Array length is less than k" );
return null;
}
let maxSum = 0;
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
console.log(`Initial window sum: ${windowSum}, Window: [${arr.slice(0, k)}]`);
for (let i = k; i < arr.length; i++) {
windowSum = windowSum - arr[i - k] + arr[i];
console.log(`New window sum: ${windowSum}, Window: [${arr.slice(i - k + 1, i + 1)}]`);
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;
}
const array = [1, 4, 2, 10, 23, 3, 1, 0, 20];
const k = 4;
maxSubarraySum( array , k);
|
登入後複製
哈希表
雜湊表非常適合解決需要快速尋找或計算出現次數的問題。
範例:尋找字串中的第一個不重複字元。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
function firstNonRepeatingChar(str) {
const charCount = new Map();
for (let char of str) {
charCount.set(char, (charCount.get(char) || 0) + 1);
console.log(`Character ${char} count : ${charCount.get(char)}`);
}
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;
}
const inputString = "aabccdeff" ;
firstNonRepeatingChar(inputString);
|
登入後複製
這些策略展示了解決常見編碼面試問題的有效方法。每個範例中的詳細日誌記錄有助於理解演算法的逐步過程,這在面試中解釋您的思考過程至關重要。
這是一個程式碼區塊,示範如何使用映射來更好地理解其中一些操作:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | const fruitInventory = new Map();
fruitInventory.set( 'apple' , 5);
fruitInventory.set( 'banana' , 3);
fruitInventory.set( 'orange' , 2);
console.log( 'Initial inventory:' , fruitInventory);
console.log( 'Number of apples:' , fruitInventory.get( 'apple' ));
console.log( 'Do we have pears?' , fruitInventory.has( 'pear' ));
fruitInventory.set( 'banana' , fruitInventory.get( 'banana' ) + 2);
console.log( 'Updated banana count:' , fruitInventory.get( 'banana' ));
fruitInventory. delete ( 'orange' );
console.log( 'Inventory after removing oranges:' , fruitInventory);
console.log( 'Current inventory:' );
fruitInventory.forEach(( count , fruit) => {
console.log(`${fruit}: ${ count }`);
});
console.log( 'Number of fruit types:' , fruitInventory.size);
fruitInventory.clear();
console.log( 'Inventory after clearing:' , fruitInventory);
|
登入後複製
此範例示範了各種 Map 操作:
- 建立新地圖
- 使用
新增鍵值對
- 使用
檢索值
- 使用
檢查金鑰是否存在
- 更新值
- 使用
刪除鍵值對
- 使用
迭代地圖
- 取得地圖的大小
- 清除整個地圖
這些操作與firstNonRepeatingChar函數中使用的操作類似,我們使用Map來統計字元出現的次數,然後搜尋計數為1的第一個字元。
動態規劃教程
動態程式設計是一種強大的演算法技術,用於透過將複雜問題分解為更簡單的子問題來解決複雜問題。讓我們透過計算斐波那契數的範例來探討這個概念。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
function fibonacci(n) {
const fib = new Array(n + 1);
fib[0] = 0;
fib[1] = 1;
console.log(`F(0) = ${fib[0]}`);
console.log(`F(1) = ${fib[1]}`);
for (let i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
console.log(`F(${i}) = ${fib[i]}`);
}
return fib[n];
}
const n = 10;
console.log(`The ${n}th Fibonacci number is:`, fibonacci(n));
|
登入後複製
此範例示範了動態程式設計如何透過儲存先前計算的值並將其用於將來的計算來有效地計算斐波那契數。
二分查找教程
二分搜尋是一種在排序數組中尋找元素的有效演算法。這是帶有詳細日誌記錄的實作:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
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;
}
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 7;
binarySearch(sortedArray, target);
|
登入後複製
此實作展示了二分搜尋如何在每次迭代中有效地將搜尋範圍縮小一半,使其比大型排序數組的線性搜尋快得多。
- 深度優先搜尋(DFS)
- 廣度優先搜尋(BFS)
- 堆(優先權隊列)
- Trie(字首樹)
- 並查(不相交集)
- 拓樸排序
深度優先搜尋 (DFS)
深度優先搜尋是一種圖遍歷演算法,在回溯之前沿著每個分支盡可能地探索。以下是表示為鄰接清單的圖表的範例實作:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | 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;
}
}
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 會探索目前深度的所有頂點,然後再移動到下一個深度等級的頂點。這是一個實作:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Graph {
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;
}
}
console.log(graph.bfs( 'A' ));
|
登入後複製
堆(優先隊列)
堆是一種滿足堆性質的特殊的基於樹的資料結構。這是最小堆的簡單實作:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | 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);
}
}
}
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 是一種高效率的資訊檢索資料結構,常用於字串搜尋:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | 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;
}
}
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 是一種資料結構,用於追蹤被分成一個或多個不相交集合的元素:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | 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);
}
}
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));
console.log(uf.connected(7, 9));
|
登入後複製
拓撲排序
拓樸排序用於對具有依賴關係的任務進行排序。這是使用 DFS 的實作:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | 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();
}
}
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());
|
登入後複製
這些實作為在編碼面試和實際應用中理解和使用這些重要的演算法和資料結構提供了堅實的基礎。
以上是程式設計面試中解決問題的終極指南的詳細內容。更多資訊請關注PHP中文網其他相關文章!