1. 數(shù)組與字符串：滑動(dòng)窗口
題目描述：
給定一個(gè)字符串 s，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。
示例 1：
輸入: s = "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。
示例 2：
輸入: s = "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。
JavaScript解決方案：
/**
* @param {string} s
* @return {number}
*/
function lengthOfLongestSubstring(s) {
// 使用Map存儲(chǔ)字符及其最后出現(xiàn)的位置
const charIndexMap = new Map();
let left = 0; // 滑動(dòng)窗口左邊界
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
const currentChar = s[right];
// 如果字符已在窗口內(nèi)，移動(dòng)左邊界
if (charIndexMap.has(currentChar) && charIndexMap.get(currentChar) >= left) {
left = charIndexMap.get(currentChar) + 1;
}
// 更新字符位置
charIndexMap.set(currentChar, right);
// 更新最大長(zhǎng)度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// 測(cè)試
console.log("最長(zhǎng)無重復(fù)子串:");
console.log('"abcabcbb" ->', lengthOfLongestSubstring("abcabcbb")); // 3
console.log('"bbbbb" ->', lengthOfLongestSubstring("bbbbb")); // 1
console.log('"pwwkew" ->', lengthOfLongestSubstring("pwwkew")); // 3
2. 鏈表：反轉(zhuǎn)鏈表
題目描述：
給你單鏈表的頭節(jié)點(diǎn) head，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
示例：
輸入: head = [1,2,3,4,5]
輸出: [5,4,3,2,1]
JavaScript解決方案：
/**
* 鏈表節(jié)點(diǎn)定義
*/
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
/**
* @param {ListNode} head
* @return {ListNode}
*/
function reverseList(head) {
let prev = null;
let current = head;
while (current !== null) {
const nextNode = current.next; // 暫存下一個(gè)節(jié)點(diǎn)
current.next = prev; // 反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)的指針
prev = current; // 移動(dòng)prev到當(dāng)前節(jié)點(diǎn)
current = nextNode; // 移動(dòng)current到下一個(gè)節(jié)點(diǎn)
}
return prev; // prev最終成為新的頭節(jié)點(diǎn)
}
// 輔助函數(shù)：創(chuàng)建鏈表
function createList(arr) {
if (arr.length === 0) return null;
const head = new ListNode(arr[0]);
let current = head;
for (let i = 1; i < arr.length; i++) {
current.next = new ListNode(arr[i]);
current = current.next;
}
return head;
}
// 輔助函數(shù)：打印鏈表
function printList(head) {
const result = [];
let current = head;
while (current !== null) {
result.push(current.val);
current = current.next;
}
return result;
}
// 測(cè)試
console.log("\n反轉(zhuǎn)鏈表:");
const head = createList([1, 2, 3, 4, 5]);
console.log("原始鏈表:", printList(head)); // [1,2,3,4,5]
const reversed = reverseList(head);
console.log("反轉(zhuǎn)后:", printList(reversed)); // [5,4,3,2,1]
3. 棧：有效的括號(hào)
題目描述：
給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判斷字符串是否有效。
有效字符串需滿足：
- 左括號(hào)必須用相同類型的右括號(hào)閉合。
- 左括號(hào)必須以正確的順序閉合。
- 每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類型的左括號(hào)。
示例 1：
輸入: s = "()"
輸出: true
示例 2：
輸入: s = "()[]{}"
輸出: true
示例 3：
輸入: s = "(]"
輸出: false
JavaScript解決方案：
/**
* @param {string} s
* @return {boolean}
*/
function isValid(s) {
const stack = [];
const bracketPairs = {
')': '(',
'}': '{',
']': '['
};
for (let i = 0; i < s.length; i++) {
const char = s[i];
// 如果是右括號(hào)
if (bracketPairs[char]) {
// 檢查棧頂元素是否匹配
const topElement = stack.length === 0 ? '#' : stack.pop();
if (topElement !== bracketPairs[char]) {
return false;
}
}
// 如果是左括號(hào)，壓入棧
else {
stack.push(char);
}
}
// 如果棧為空，說明所有括號(hào)都匹配
return stack.length === 0;
}
// 測(cè)試
console.log("\n有效的括號(hào):");
console.log('"()" ->', isValid("()")); // true
console.log('"()[]{}" ->', isValid("()[]{}")); // true
console.log('"(]" ->', isValid("(]")); // false
console.log('"([)]" ->', isValid("([)]")); // false
console.log('"{[]}" ->', isValid("{[]}")); // true
4. 哈希表：兩數(shù)之和
題目描述：
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值 target 的那兩個(gè)整數(shù)，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案，并且你不能使用同一個(gè)元素兩次。
你可以按任意順序返回答案。
示例 1：
輸入: nums = [2,7,11,15], target = 9
輸出: [0,1]
解釋: 因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
示例 2：
輸入: nums = [3,2,4], target = 6
輸出: [1,2]
JavaScript解決方案：
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
function twoSum(nums, target) {
// 使用Map存儲(chǔ)數(shù)字和對(duì)應(yīng)的索引
const numMap = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
// 檢查補(bǔ)數(shù)是否已在Map中
if (numMap.has(complement)) {
return [numMap.get(complement), i];
}
// 將當(dāng)前數(shù)字和索引存入Map
numMap.set(nums[i], i);
}
return []; // 根據(jù)題目描述，總會(huì)有一個(gè)解
}
// 測(cè)試
console.log("\n兩數(shù)之和:");
console.log("nums = [2,7,11,15], target = 9 ->", twoSum([2,7,11,15], 9)); // [0,1]
console.log("nums = [3,2,4], target = 6 ->", twoSum([3,2,4], 6)); // [1,2]
console.log("nums = [3,3], target = 6 ->", twoSum([3,3], 6)); // [0,1]
5. 二叉樹：二叉樹的最大深度
題目描述：
給定一個(gè)二叉樹 root，返回其最大深度。
二叉樹的最大深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。
示例：
3
/ \
9 20
/ \
15 7
輸入: root = [3,9,20,null,null,15,7]
輸出: 3
解釋: 最大深度為3，路徑為 3→20→7 或 3→20→15
JavaScript解決方案：
/**
* 二叉樹節(jié)點(diǎn)定義
*/
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* @param {TreeNode} root
* @return {number}
*/
function maxDepth(root) {
// 遞歸解法：深度優(yōu)先搜索
if (root === null) {
return 0;
}
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
// 廣度優(yōu)先搜索解法
function maxDepthBFS(root) {
if (root === null) return 0;
const queue = [root];
let depth = 0;
while (queue.length > 0) {
depth++;
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return depth;
}
// 創(chuàng)建測(cè)試二叉樹
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
// 測(cè)試
console.log("\n二叉樹的最大深度:");
console.log("遞歸解法:", maxDepth(root)); // 3
console.log("BFS解法:", maxDepthBFS(root)); // 3
6. 堆：數(shù)組中的第K個(gè)最大元素
題目描述：
給定整數(shù)數(shù)組 nums 和整數(shù) k，請(qǐng)返回?cái)?shù)組中第 k 個(gè)最大的元素。
請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。
示例 1：
輸入: nums = [3,2,1,5,6,4], k = 2
輸出: 5
解釋: 排序后數(shù)組是 [1,2,3,4,5,6]，第2個(gè)最大元素是5
示例 2：
輸入: nums = [3,2,3,1,2,4,5,5,6], k = 4
輸出: 4
JavaScript解決方案：
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
// 方法1：使用內(nèi)置排序（簡(jiǎn)單但效率較低）
function findKthLargestSort(nums, k) {
nums.sort((a, b) => b - a); // 降序排序
return nums[k - 1];
}
// 方法2：最小堆（推薦面試使用）
function findKthLargestHeap(nums, k) {
// 最小堆實(shí)現(xiàn)
class MinHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this._bubbleUp(this.heap.length - 1);
}
pop() {
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this._sinkDown(0);
}
return min;
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
_bubbleUp(index) {
const element = this.heap[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
const parent = this.heap[parentIndex];
if (element >= parent) break;
this.heap[parentIndex] = element;
this.heap[index] = parent;
index = parentIndex;
}
}
_sinkDown(index) {
const length = this.heap.length;
const element = this.heap[index];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let swap = null;
let leftChild, rightChild;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild < element) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && rightChild < element) ||
(swap !== null && rightChild < leftChild)
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
this.heap[swap] = element;
index = swap;
}
}
}
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.push(num);
// 保持堆的大小為k
if (minHeap.size() > k) {
minHeap.pop(); // 移除最小的元素
}
}
return minHeap.peek(); // 堆頂就是第k個(gè)最大元素
}
// 測(cè)試
console.log("\n數(shù)組中的第K個(gè)最大元素:");
const nums1 = [3,2,1,5,6,4];
console.log("排序方法:", findKthLargestSort([...nums1], 2)); // 5
console.log("最小堆方法:", findKthLargestHeap([...nums1], 2)); // 5
const nums2 = [3,2,3,1,2,4,5,5,6];
console.log("排序方法:", findKthLargestSort([...nums2], 4)); // 4
console.log("最小堆方法:", findKthLargestHeap([...nums2], 4)); // 4
7. 回溯：全排列
題目描述：
給定一個(gè)不含重復(fù)數(shù)字的數(shù)組 nums，返回其所有可能的全排列。你可以按任意順序返回答案。
示例 1：
輸入: nums = [1,2,3]
輸出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
輸入: nums = [0,1]
輸出: [[0,1],[1,0]]
JavaScript解決方案：
/**
* @param {number[]} nums
* @return {number[][]}
*/
function permute(nums) {
const result = [];
// 回溯函數(shù)
function backtrack(currentPermutation, used) {
// 如果當(dāng)前排列長(zhǎng)度等于原數(shù)組長(zhǎng)度，說明找到了一個(gè)排列
if (currentPermutation.length === nums.length) {
result.push([...currentPermutation]); // 深拷貝
return;
}
for (let i = 0; i < nums.length; i++) {
// 如果數(shù)字已使用，跳過
if (used[i]) continue;
// 選擇當(dāng)前數(shù)字
used[i] = true;
currentPermutation.push(nums[i]);
// 遞歸探索
backtrack(currentPermutation, used);
// 撤銷選擇（回溯）
currentPermutation.pop();
used[i] = false;
}
}
backtrack([], new Array(nums.length).fill(false));
return result;
}
// 測(cè)試
console.log("\n全排列:");
console.log("輸入: [1,2,3]");
console.log("輸出:", permute([1,2,3]));
console.log("\n輸入: [0,1]");
console.log("輸出:", permute([0,1]));
8. 分治：歸并排序
題目描述：
給你一個(gè)整數(shù)數(shù)組 nums，請(qǐng)你將該數(shù)組升序排列。
示例 1：
輸入: nums = [5,2,3,1]
輸出: [1,2,3,5]
示例 2：
輸入: nums = [5,1,1,2,0,0]
輸出: [0,0,1,1,2,5]
JavaScript解決方案：
/**
* @param {number[]} nums
* @return {number[]}
*/
function mergeSort(nums) {
// 分治法的典型應(yīng)用
if (nums.length <= 1) {
return nums;
}
// 1. 分：將數(shù)組分成兩半
const mid = Math.floor(nums.length / 2);
const left = nums.slice(0, mid);
const right = nums.slice(mid);
// 2. 治：遞歸排序左右兩半
const sortedLeft = mergeSort(left);
const sortedRight = mergeSort(right);
// 3. 合：合并兩個(gè)有序數(shù)組
return merge(sortedLeft, sortedRight);
}
/**
* 合并兩個(gè)有序數(shù)組
*/
function merge(left, right) {
const result = [];
let i = 0, j = 0;
// 比較兩個(gè)數(shù)組的元素，將較小的放入結(jié)果
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// 將剩余元素添加到結(jié)果
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
// 測(cè)試
console.log("\n歸并排序:");
console.log("輸入: [5,2,3,1]");
console.log("輸出:", mergeSort([5,2,3,1])); // [1,2,3,5]
console.log("\n輸入: [5,1,1,2,0,0]");
console.log("輸出:", mergeSort([5,1,1,2,0,0])); // [0,0,1,1,2,5]
9. BFS：二叉樹的層序遍歷
題目描述：
給你二叉樹的根節(jié)點(diǎn) root，返回其節(jié)點(diǎn)值的層序遍歷。（即逐層地，從左到右訪問所有節(jié)點(diǎn)）。
示例：
3
/ \
9 20
/ \
15 7
輸入: root = [3,9,20,null,null,15,7]
輸出: [[3],[9,20],[15,7]]
JavaScript解決方案：
/**
* @param {TreeNode} root
* @return {number[][]}
*/
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
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;
}
// 創(chuàng)建測(cè)試二叉樹
const tree = new TreeNode(3);
tree.left = new TreeNode(9);
tree.right = new TreeNode(20);
tree.right.left = new TreeNode(15);
tree.right.right = new TreeNode(7);
// 測(cè)試
console.log("\n二叉樹的層序遍歷:");
console.log("輸出:", levelOrder(tree)); // [[3],[9,20],[15,7]]
10. 動(dòng)態(tài)規(guī)劃：爬樓梯
題目描述：
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
示例 1：
輸入: n = 2
輸出: 2
解釋: 有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階
示例 2：
輸入: n = 3
輸出: 3
解釋: 有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階
JavaScript解決方案：
/**
* @param {number} n
* @return {number}
*/
function climbStairs(n) {
if (n <= 2) return n;
// dp[i] 表示爬到第i階樓梯的方法數(shù)
const dp = new Array(n + 1).fill(0);
dp[1] = 1; // 爬1階有1種方法
dp[2] = 2; // 爬2階有2種方法
for (let i = 3; i <= n; i++) {
// 狀態(tài)轉(zhuǎn)移方程：dp[i] = dp[i-1] + dp[i-2]
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 空間優(yōu)化版本
function climbStairsOptimized(n) {
if (n <= 2) return n;
let prev1 = 2; // dp[i-1]，從i=3開始，prev1=dp[2]=2
let prev2 = 1; // dp[i-2]，從i=3開始，prev2=dp[1]=1
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
// 測(cè)試
console.log("\n爬樓梯:");
console.log("n=1 ->", climbStairs(1)); // 1
console.log("n=2 ->", climbStairs(2)); // 2
console.log("n=3 ->", climbStairs(3)); // 3
console.log("n=4 ->", climbStairs(4)); // 5
console.log("n=5 ->", climbStairs(5)); // 8
console.log("\n空間優(yōu)化版本:");
console.log("n=5 ->", climbStairsOptimized(5)); // 8
11. 貪心算法：分發(fā)餅干
題目描述：
假設(shè)你是一位很棒的家長(zhǎng)，想要給你的孩子們一些小餅干。但是，每個(gè)孩子最多只能給一塊餅干。
對(duì)每個(gè)孩子 i，都有一個(gè)胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個(gè)尺寸 s[j]。如果 s[j] >= g[i]，我們可以將這個(gè)餅干 j 分配給孩子 i，這個(gè)孩子會(huì)得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值。
示例 1：
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個(gè)孩子和兩塊小餅干，3個(gè)孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1。
示例 2：
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個(gè)孩子和三塊小餅干，2個(gè)孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應(yīng)該輸出2。
JavaScript解決方案：
/**
* @param {number[]} g - 孩子的胃口值
* @param {number[]} s - 餅干的尺寸
* @return {number}
*/
function findContentChildren(g, s) {
// 貪心策略：用小餅干滿足小胃口的孩子
g.sort((a, b) => a - b); // 孩子按胃口排序
s.sort((a, b) => a - b); // 餅干按尺寸排序
let childIndex = 0;
let cookieIndex = 0;
let satisfiedCount = 0;
while (childIndex < g.length && cookieIndex < s.length) {
if (s[cookieIndex] >= g[childIndex]) {
// 當(dāng)前餅干可以滿足當(dāng)前孩子
satisfiedCount++;
childIndex++;
cookieIndex++;
} else {
// 當(dāng)前餅干太小，嘗試下一塊餅干
cookieIndex++;
}
}
return satisfiedCount;
}
// 測(cè)試
console.log("\n分發(fā)餅干:");
console.log("g=[1,2,3], s=[1,1] ->", findContentChildren([1,2,3], [1,1])); // 1
console.log("g=[1,2], s=[1,2,3] ->", findContentChildren([1,2], [1,2,3])); // 2
12. 雙指針：盛最多水的容器
題目描述：
給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 height。有 n 條垂線，第 i 條線的兩個(gè)端點(diǎn)是 (i, 0) 和 (i, height[i])。
找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
返回容器可以儲(chǔ)存的最大水量。
說明：你不能傾斜容器。
示例：
輸入: height = [1,8,6,2,5,4,8,3,7]
輸出: 49
解釋: 圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。
JavaScript解決方案：
/**
* @param {number[]} height
* @return {number}
*/
function maxArea(height) {
let left = 0;
let right = height.length - 1;
let maxWater = 0;
while (left < right) {
// 計(jì)算當(dāng)前容器的水量
const width = right - left;
const currentHeight = Math.min(height[left], height[right]);
const currentWater = width * currentHeight;
// 更新最大水量
maxWater = Math.max(maxWater, currentWater);
// 移動(dòng)較矮的指針，因?yàn)橐苿?dòng)較高的指針不會(huì)增加水量
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
// 測(cè)試
console.log("\n盛最多水的容器:");
const heights = [1,8,6,2,5,4,8,3,7];
console.log("height =", heights);
console.log("最大水量 =", maxArea(heights)); // 49
13. 排序：快速排序
題目描述：
給你一個(gè)整數(shù)數(shù)組 nums，請(qǐng)你將該數(shù)組升序排列。
示例 1：
輸入: nums = [5,2,3,1]
輸出: [1,2,3,5]
示例 2：
輸入: nums = [5,1,1,2,0,0]
輸出: [0,0,1,1,2,5]
JavaScript解決方案：
/**
* @param {number[]} nums
* @return {number[]}
*/
function quickSort(nums) {
if (nums.length <= 1) return nums;
// 選擇基準(zhǔn)元素
const pivotIndex = Math.floor(nums.length / 2);
const pivot = nums[pivotIndex];
// 分割數(shù)組
const left = [];
const right = [];
for (let i = 0; i < nums.length; i++) {
if (i === pivotIndex) continue;
if (nums[i] < pivot) {
left.push(nums[i]);
} else {
right.push(nums[i]);
}
}
// 遞歸排序并合并
return [...quickSort(left), pivot, ...quickSort(right)];
}
// 原地快速排序（更高效）
function quickSortInPlace(nums, left = 0, right = nums.length - 1) {
if (left >= right) return;
const pivotIndex = partition(nums, left, right);
quickSortInPlace(nums, left, pivotIndex - 1);
quickSortInPlace(nums, pivotIndex + 1, right);
return nums;
}
function partition(nums, left, right) {
// 選擇最后一個(gè)元素作為基準(zhǔn)
const pivot = nums[right];
let i = left - 1;
for (let j = left; j < right; j++) {
if (nums[j] <= pivot) {
i++;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
// 將基準(zhǔn)放到正確位置
[nums[i + 1], nums[right]] = [nums[right], nums[i + 1]];
return i + 1;
}
// 測(cè)試
console.log("\n快速排序:");
console.log("簡(jiǎn)單版本:");
console.log("[5,2,3,1] ->", quickSort([5,2,3,1])); // [1,2,3,5]
console.log("[5,1,1,2,0,0] ->", quickSort([5,1,1,2,0,0])); // [0,0,1,1,2,5]
console.log("\n原地排序版本:");
const arr1 = [5,2,3,1];
quickSortInPlace(arr1);
console.log("[5,2,3,1] ->", arr1); // [1,2,3,5]
const arr2 = [5,1,1,2,0,0];
quickSortInPlace(arr2);
console.log("[5,1,1,2,0,0] ->", arr2); // [0,0,1,1,2,5]
14. 二分查找
題目描述：
給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target，寫一個(gè)函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)，否則返回 -1。
示例 1：
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4
示例 2：
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1
JavaScript解決方案：
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
// 防止整數(shù)溢出
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// 二分查找變種：查找左邊界
function searchLeftBound(nums, target) {
let left = 0;
let right = nums.length; // 注意
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// 檢查left是否越界或找到target
if (left < 0 || left >= nums.length || nums[left] !== target) {
return -1;
}
return left;
}
// 測(cè)試
console.log("\n二分查找:");
const nums = [-1,0,3,5,9,12];
console.log("nums =", nums);
console.log("target = 9 ->", search(nums, 9)); // 4
console.log("target = 2 ->", search(nums, 2)); // -1
console.log("\n二分查找左邊界:");
const nums2 = [1,2,2,2,3,4,5];
console.log("nums =", nums2);
console.log("target = 2 ->", searchLeftBound(nums2, 2)); // 1
console.log("target = 6 ->", searchLeftBound(nums2, 6)); // -1
總結(jié)
現(xiàn)在每個(gè)算法題目都有了：
- 完整的題目描述 - 理解問題在問什么
- 清晰的示例 - 了解輸入輸出格式
- JavaScript解決方案 - 具體的實(shí)現(xiàn)代碼
- 測(cè)試代碼 - 驗(yàn)證解決方案的正確性
這些題目覆蓋了算法面試中最核心的14個(gè)知識(shí)點(diǎn)，掌握了這些題目，你就有了應(yīng)對(duì)大多數(shù)算法面試的基礎(chǔ)。記住，不僅要會(huì)寫代碼，更要理解算法背后的思想和原理！
