js算法面試題十道

1. 兩數之和

題目：給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那兩個整數，并返回他們的數組下標。

function twoSum(nums, target) {const map = new Map();for (let i = 0; i < nums.length; i++) {const complement = target - nums[i];if (map.has(complement)) {return [map.get(complement), i];}map.set(nums[i], i);}return [];
}

2. 反轉字符串

題目：給你一個字符串 s，請你將它反轉成一個新的字符串。

function reverseString(s) {return s.split('').reverse().join('');
}

3. 最長公共子序列

題目：給定兩個字符串 text1 和 text2，返回這兩個字符串的最長公共子序列的長度。

function longestCommonSubsequence(text1, text2) {const m = text1.length;const n = text2.length;const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));for (let i = 1; i <= m; i++) {for (let j = 1; j <= n; j++) {if (text1[i - 1] === text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];
}

4. 合并兩個有序數組

題目：給你兩個有序整數數組 nums1 和 nums2，請你將它們合并成一個的新數組。你可以假設這個新數組的長度一定小于或等于 nums1.length + nums2.length。

function mergeTwoArrays(nums1, nums2) {const result = [];let i = 0;let j = 0;while (i < nums1.length && j < nums2.length) {if (nums1[i] < nums2[j]) {result.push(nums1[i]);i++;} else {result.push(nums2[j]);j++;}}return result.concat(nums1.slice(i)).concat(nums2.slice(j));
}

5. 三數之和

題目：給你一個包含 n 個整數的數組 nums，判斷是否可以通過在數組中選擇一個起始點，然后向后選擇兩個整數，使得這三個整數的和等于目標值。

function threeSum(nums, target) {const result = [];nums.sort((a, b) => a - b);for (let i = 0; i < nums.length - 2; i++) {if (i > 0 && nums[i] === nums[i - 1]) continue;const left = i + 1;const right = nums.length - 1;while (left < right) {const sum = nums[i] + nums[left] + nums[right];if (sum === target) {result.push([nums[i], nums[left], nums[right]]);left++;right--;while (left < right && nums[left] === nums[left - 1]) left++;while (left < right && nums[right] === nums[right + 1]) right--;} else if (sum < target) {left++;} else {right--;}}}return result;
}

6. 四數之和

題目：給你一個包含 n 個整數的數組 nums，判斷是否可以使用其中的四個數來組成一個矩形。如果可以，返回 true；否則，返回 false。

function fourSum(nums, target) {const result = [];nums.sort((a, b) => a - b);for (let i = 0; i < nums.length - 3; i++) {if (i > 0 && nums[i] === nums[i - 1]) continue;for (let j = i + 1; j < nums.length - 2; j++) {if (j > i + 1 && nums[j] === nums[j - 1]) continue;const left = j + 1;const right = nums.length - 1;while (left < right) {const sum = nums[i] + nums[j] + nums[left] + nums[right];if (sum === target) {result.push([nums[i], nums[j], nums[left], nums[right]]);left++;right--;while (left < right && nums[left] === nums[left - 1]) left++;while (left < right && nums[right] === nums[right + 1]) right--;} else if (sum < target) {left++;} else {right--;}}}}return result;
}

7. 兩數之和 II - 輸入有序數組

題目：給定一個已排序的整數數組 nums，找出兩個數滿足它們的和等于目標值 target。你只能使用每個元素一次。

function twoSumSorted(nums, target) {const map = new Map();for (let i = 0; i < nums.length; i++) {const complement = target - nums[i];if (map.has(complement)) {return [map.get(complement), i];}map.set(nums[i], i);}return [];
}

8. 最大矩形面積

題目：給定一個二維數組 heights，其中 heights[i] 表示第 i 行的高度，返回能夠勾勒出的最大矩形面積。

function largestRectangleArea(heights) {const stack = [];heights.push(0);let maxArea = 0;for (let i = 0; i < heights.length; i++) {while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {const height = heights[stack.pop()];const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;maxArea = Math.max(maxArea, height * width);}stack.push(i);}return maxArea;
}

9. 盛最多水的容器

題目：給定 n 個非負整數 a1、a2、…、an，請計算連乘這些整數所得到的積，并以字符串形式輸出。

function multiply(nums) {let result = '1';for (const num of nums) {result = BigInt(result) * BigInt(num);}return result.toString();
}

10. 單詞拆分 II

題目：給定一個非空字符串 s 和一個定義好的分隔符集合 nonWordChars，返回所有可能的句子排列。句子是由空格分隔的單詞組成的。換句話說，要生成所有可能的句子，可以使用回溯算法進行求解。

function wordBreak(s, wordDict) {const result = [];const memo = new Map();function backtrack(start) {if (memo.has(start)) {return memo.get(start);}if (start === s.length) {result.push('');return;}for (let end = start + 1; end <= s.length; end++) {if (wordDict.has(s.slice(start, end))) {backtrack(end);if (end !== start + 1) {const sentences = result.pop();result.push(sentences + ' ' + s.slice(start, end));} else {result.push(s.slice(start, end));}}}memo.set(start, result);return result;}backtrack(0);return result;
}

再來十道經典面試題

以下是幾個經典的 JavaScript 算法題和它們的詳細答案：

1. 冒泡排序
   問題：請用 JavaScript 實現一個冒泡排序算法。

function bubbleSort(arr) {let len = arr.length;for (let i = 0; i < len - 1; i++) {for (let j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j + 1]) {let temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}return arr;
}

2. 二分查找
   問題：請用 JavaScript 實現一個二分查找算法。

function binarySearch(arr, target) {let left = 0;let right = arr.length - 1;while (left <= right) {let mid = Math.floor((left + right) / 2);if (arr[mid] === target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;
}

3. 深度優先搜索
   問題：請用 JavaScript 實現一個深度優先搜索算法，用于遍歷圖或樹。

function dfs(graph, start, visited = []) {visited.push(start);console.log(start);for (let next of graph[start]) {if (!visited.includes(next)) {dfs(graph, next, visited);}}
}

4. 廣度優先搜索
   問題：請用 JavaScript 實現一個廣度優先搜索算法，用于遍歷圖或樹。

function bfs(graph, start, visited = []) {const queue = [start];while (queue.length > 0) {const node = queue.shift();if (!visited.includes(node)) {visited.push(node);console.log(node);for (const next of graph[node]) {queue.push(next);}}}
}

5. 歸并排序
   問題：請用 JavaScript 實現一個歸并排序算法。

function mergeSort(arr) {if (arr.length <= 1) return arr;const mid = Math.floor(arr.length / 2);const left = mergeSort(arr.slice(0, mid));const right = mergeSort(arr.slice(mid));return merge(left, right);  // 合并兩個有序數組，產生一個新的有序數組。需要額外實現 merge 函數。}function merge(left, right) {let result = [];let i = 0;let j = 0;while (i < left.length && j < right.length) {if (left[i] < right[j]) {result.push(left[i]);i++;} else {result.push(right[j]);j++;}}// 如果左邊數組還有剩余元素，將其全部加入結果數組while (i < left.length) {result.push(left[i]);i++;}// 如果右邊數組還有剩余元素，將其全部加入結果數組while (j < right.length) {result.push(right[j]);j++;}return result;
}

在這個實現中，我們首先創建一個空的結果數組。然后我們使用兩個指針 i 和 j 分別指向左數組和右數組的第一個元素。我們比較兩個指針所指的元素，并將較小的元素推入結果數組。這個過程一直持續到我們遍歷完左數組和右數組的所有元素。然后，我們將剩余的元素（如果有的話）添加到結果數組中。最后，我們返回結果數組。

6. 快速排序
   問題：請用 JavaScript 實現一個快速排序算法。
   答案：

function quickSort(arr) {if (arr.length <= 1) return arr;const pivot = arr[0];const left = [];const right = [];for (let i = 1; i < arr.length; i++) {if (arr[i] < pivot) {left.push(arr[i]);} else {right.push(arr[i]);}}return [...quickSort(left), pivot, ...quickSort(right)];
}

7. 插入排序
   問題：請用 JavaScript 實現一個插入排序算法。
   答案：

function insertionSort(arr) {let i = 1;while (i < arr.length) {let key = arr[i];let j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;i++;}return arr;
}

8. 選擇排序
   問題：請用 JavaScript 實現一個選擇排序算法。
   答案：

function selectionSort(arr) {let len = arr.length;for (let i = 0; i < len - 1; i++) {let minIndex = i;for (let j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex != i) {[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // Swap arr[i] and arr[minIndex]}}return arr; // 返回排序后的數組，從小到大排序。
}

9. Fibonacci序列：問題：請用JavaScript實現一個函數，計算Fibonacci序列的第n個數字。答案：

function fibonacci(n) {if (n <= 1) {return n;}return fibonacci(n - 1) + fibonacci(n - 2);
}

10. 二分查找改進版：問題：請用JavaScript實現一個函數，在有序數組中查找特定元素，并返回其索引。如果元素不存在，則返回-1。答案：

function binarySearch(arr, target) {let left = 0;let right = arr.length - 1;while (left <= right) {let mid = Math.floor((left + right) / 2);if (arr[mid] === target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;
}