LeetCode 演算法解題筆記
1. Palindrome Number (回文數字)
題目描述
判斷一個整數是否為回文數字（正讀反讀都相同）
解題思路
- 方法1: 轉成字串後反轉比較
- 方法2: 數學方法反轉數字
JavaScript 實作
我的寫法（轉回數字比較）
function isPalindrome(x) {
if(x < 0)
return false;
let reversed = String(x).split('').reverse().join('');
reversed = Number(reversed);
return x === reversed;
}
方法1: 字串反轉
function isPalindrome(x) {
if (x < 0) return false;
const str = x.toString();
return str === str.split('').reverse().join('');
}
方法2: 數學反轉（更省空間）
function isPalindrome(x) {
if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
let reversed = 0;
let original = x;
while (original > reversed) {
reversed = reversed * 10 + original % 10;
original = Math.floor(original / 10);
}
return original === reversed || original === Math.floor(reversed / 10);
}
時間複雜度
- 時間: O(log n)
- 空間: O(1) (數學方法)
2. Two Sum (HashMap)
題目描述
在陣列中找出兩個數字，使其和等於目標值，返回索引
解題思路
- 暴力法: 兩層迴圈檢查所有配對組合
- HashMap 法: 使用 HashMap 儲存已遍歷的數字及其索引，一次遍歷即可找到答案
JavaScript 實作
方法1: 暴力法（兩層迴圈）
function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) { // 從 i+1 開始
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
i= 目前位置j= 目前位置 + 1
方法2: HashMap 法
function twoSum(nums, target) {
let obj = {}; // { 數字: 索引}
for(let i = 0; i < nums.length; i++) {
let currentNum = nums[i];
let complement = target - currentNum;
if(complement in obj) {
return [obj[complement], i];
}
obj[currentNum] = i;
}
return [];
}
方法3: HashMap 法（使用 Map）
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 [];
}
方法比較
| 方法 | 時間複雜度 | 空間複雜度 | 優缺點 |
|---|---|---|---|
| 暴力法 | O(n²) | O(1) | ❌ 效率低，但容易理解 |
| HashMap | O(n) | O(n) | ✅ 最優解，效能最佳 |
HashMap 核心概念
- 目標: 避免重複遍歷，將「尋找配對」變成 O(1) 查找
- 技巧: 儲存
數字 → 索引的映射關係 - 邏輯: 當遍歷到
nums[i]時，檢查target - nums[i]是否已經出現過
3. Valid Parentheses (Stack)
題目描述
判斷字串中的括號是否有效配對（包含 (), [], {}）
解題思路
使用 Stack 結構，遇到左括號推入，遇到右括號檢查是否匹配
JavaScript 實作
我的寫法
function isValid () {
let stack = [];
let pairs = {
')': '(',
'}': '{',
']': '['
}
for(let i = 0; i < s.length; i++) {
let char = s[i];
if(char === '(' || char === '{' || char === '[') {
stack.push(char);
} else if (char === ')' || char === '}' || char === ']') {
if(stack.length === 0) {
return false;
}
let top = stack.pop();
if(pairs[char] !== top) {
return false;
}
}
}
return stack.length === 0;
}
方法一
function isValid(s) {
const stack = [];
const pairs = {
')': '(',
']': '[',
'}': '{'
};
for (let char of s) {
if (char === '(' || char === '[' || char === '{') {
stack.push(char);
} else if (char === ')' || char === ']' || char === '}') {
if (stack.length === 0 || stack.pop() !== pairs[char]) {
return false;
}
}
}
return stack.length === 0;
}
時間複雜度
- 時間: O(n)
- 空間: O(n)
4. Remove Element (Two Pointers)
題目描述
移除陣列中所有等於指定值的元素，返回新長度。 有效元素後的系統不會檢查。
解題思路
使用雙指針技巧，慢指針記錄有效位置，快ㄏ指針遍歷陣列
JavaScript 實作
function removeElement(nums, val) {
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
slow代表的是「下一個要放置的位置」，故回傳不用 +1
時間複雜度
- 時間: O(n)
- 空間: O(1)
5. Search Insert Position (Binary Search)
題目描述
在排序陣列中找到目標值的插入位置
解題思路
使用二分搜尋法，在 O(log n) 時間內找到正確位置
JavaScript 實作
function searchInsert(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
時間複雜度
- 時間: O(log n)
- 空間: O(1)
6. Best Time to Buy and Sell Stock (Min Tracking)
題目描述
找出買賣股票的最大利潤（只能交易一次）
解題思路
追蹤最低買入價格，計算當前價格賣出的最大利潤
JavaScript 實作
我的寫法
function maxProfit(prices) {
let minPrice = prices[0];
let maxProfit = 0;
for(let i = 1; i < prices.length; i++) {
if(minPrice > prices[i]) {
minPrice = prices[i];
} else {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
}
return maxProfit;
}
方法: Min Tracking
function maxProfit(prices) {
let minPrice = prices[0];
let maxProfit = 0;
for(let i = 1; i < prices.length; i++) {
// 每天都計算如果今天賣出的利潤
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
// 每天都檢查是否有新的最低價格
minPrice = Math.min(minPrice, prices[i]);
}
return maxProfit;
}
時間複雜度
- 時間: O(n)
- 空間: O(1)
7. Longest Substring Without Repeating Characters (Sliding Window)
題目描述
找出字串中最長的無重複字元子字串長度
解題思路
使用滑動視窗技巧，維護一個無重複字元的視窗
JavaScript 實作
方法1: 使用 Set
function lengthOfLongestSubstring(s) {
const charSet = new Set();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
charSet.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
方法2: 使用 Object
function lengthOfLongestSubstring(s) {
const charObj = {};
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
while (s[right] in charObj) {
delete charObj[s[left]];
left++;
}
charObj[s[right]] = true; // 或者存入索引位置
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
時間複雜度
- 時間: O(n)
- 空間: O(min(m, n))，m 是字元集大小
演算法技巧總結
| 技巧 | 適用情境 | 時間複雜度 | 空間複雜度 |
|---|---|---|---|
| HashMap | 快速查找、配對問題 | O(1) 查找 | O(n) |
| Stack | 括號匹配、後進先出 | O(1) 操作 | O(n) |
| Two Pointers | 排序陣列、原地操作 | O(n) | O(1) |
| Binary Search | 排序陣列搜尋 | O(log n) | O(1) |
| Min Tracking | 追蹤最值、動態規劃 | O(n) | O(1) |
| Sliding Window | 子字串、子陣列問題 | O(n) | O(k) |
解題心得
- 選擇合適的資料結構：HashMap 用於快速查找，Stack 用於配對問題
- 善用雙指針：可以減少空間複雜度，適合排序陣列
- 二分搜尋：排序陣列的利器，能將 O(n) 降到 O(log n)
- 滑動視窗：處理連續子序列問題的高效方法
- 貪心思維：如股票問題，局部最優解導向全域最優解