// Two Pointers - In-place array modification
const modifyArray = (arr) => {
let writePointer = 0;
for (let readPointer = 0; readPointer < arr.length; readPointer++) {
if (/* condition */) {
[arr[writePointer], arr[readPointer]] = [arr[readPointer], arr[writePointer]];
writePointer++;
}
}
return writePointer; // Often returns new length or modified position
};
// Fast and Slow Pointers (Floyd's Cycle Detection)
const hasCycle = (head) => {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
};
// Sliding Window - Fixed Size
const fixedSlidingWindow = (arr, k) => {
let sum = 0;
// Initialize first window
for (let i = 0; i < k; i++) {
sum += arr[i];
}
let maxSum = sum;
// Slide window
for (let i = k; i < arr.length; i++) {
sum = sum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, sum);
}
return maxSum;
};
// Sliding Window - Variable Size
const varSlidingWindow = (arr, target) => {
let start = 0, sum = 0, minLen = Infinity;
for (let end = 0; end < arr.length; end++) {
sum += arr[end];
while (sum >= target) {
minLen = Math.min(minLen, end - start + 1);
sum -= arr[start];
start++;
}
}
return minLen === Infinity ? 0 : minLen;
};
// BFS - Level Order Traversal
const levelOrder = (root) => {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
};
// DFS - Recursive Template
const dfs = (root) => {
const result = [];
const traverse = (node) => {
if (!node) return;
// Pre-order
result.push(node.val);
traverse(node.left);
// In-order would be here
traverse(node.right);
// Post-order would be here
};
traverse(root);
return result;
};
// Backtracking Template
const backtrack = (nums) => {
const result = [];
const bt = (path, choices) => {
if (/* ending condition */) {
result.push([...path]);
return;
}
for (let i = 0; i < choices.length; i++) {
// Make choice
path.push(choices[i]);
// Recurse
bt(path, /* remaining choices */);
// Undo choice
path.pop();
}
};
bt([], nums);
return result;
};
// Dynamic Programming - Bottom Up Template
const dpBottomUp = (n) => {
const dp = new Array(n + 1).fill(0);
dp[0] = 1; // Base case
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
dp[i] += dp[j] * /* some calculation */;
}
}
return dp[n];
};
// Dynamic Programming - Top Down Template
const dpTopDown = (n) => {
const memo = new Map();
const dp = (n) => {
if (n <= 1) return 1;
if (memo.has(n)) return memo.get(n);
let result = 0;
for (let i = 0; i < n; i++) {
result += dp(i) * /* some calculation */;
}
memo.set(n, result);
return result;
};
return dp(n);
};
// Monotonic Stack Template
const monotonicStack = (arr) => {
const stack = []; // [index, value]
const result = new Array(arr.length).fill(-1);
for (let i = 0; i < arr.length; i++) {
while (stack.length && stack[stack.length - 1][1] > arr[i]) {
const [prevIndex, _] = stack.pop();
result[prevIndex] = i - prevIndex;
}
stack.push([i, arr[i]]);
}
return result;
};
// Prefix Sum
const prefixSum = (arr) => {
const prefix = [0];
for (let i = 0; i < arr.length; i++) {
prefix.push(prefix[prefix.length - 1] + arr[i]);
}
// Sum of range [i, j] = prefix[j + 1] - prefix[i]
return prefix;
};
// Binary Search Variations
const binarySearchLeftmost = (arr, target) => {
let left = 0, right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return left;
};
const binarySearchRightmost = (arr, target) => {
let left = 0, right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] <= target) left = mid + 1;
else right = mid;
}
return left - 1;
};
// Trie Operations
class TrieNode {
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
search(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) return false;
node = node.children.get(char);
}
return node.isEndOfWord;
}
startsWith(prefix) {
let node = this.root;
for (const char of prefix) {
if (!node.children.has(char)) return false;
node = node.children.get(char);
}
return true;
}
}
// Union Find (Disjoint Set)
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
union(x, y) {
let rootX = this.find(x);
let rootY = this.find(y);
if (rootX !== rootY) {
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]++;
}
}
}
}
// O(1) - Constant Array.push(), Array.pop(), Map.set(), Map.get() // O(log n) - Logarithmic Binary Search, Balanced BST operations // O(n) - Linear Array traversal, Linear Search // O(n log n) - Linearithmic Efficient sorting (Array.sort()) // O(n²) - Quadratic Nested loops, Simple sorting algorithms // O(2ⁿ) - Exponential Recursive solutions without memoization
以上是JavaScript 面試備忘單 - 第 2 部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！
