HackerRank 演算法解題筆記

2025年07月13日

Easy 題目

1. ⭐️ Minimum Absolute Difference in an Array

題目描述

找出陣列中任意兩個元素之間的最小絕對差值

解題思路

1. 排序法: 先將陣列排序，相鄰元素的差值就是可能的最小值
2. 關鍵觀察: 排序後，最小差值必定出現在相鄰元素之間

JavaScript 實作

function minimumAbsoluteDifference(arr) {
    // 先排序陣列
    arr.sort((a, b) => a - b);
    
    let minDiff = Infinity;
    
    // 檢查所有相鄰元素的差值
    for (let i = 0; i < arr.length - 1; i++) {
        const diff = arr[i + 1] - arr[i];
        minDiff = Math.min(minDiff, diff);
    }
    
    return minDiff;
}

時間複雜度

• 時間: O(n log n) - 排序的時間複雜度
• 空間: O(1) - 不需要額外空間

---

2. ⭐️ Caesar Cipher

題目描述

實作凱撒密碼加密，將字母按照指定位移量進行移位

解題思路

1. 字元處理: 只對英文字母進行移位，保持大小寫
2. 模運算: 使用 % 26 處理超出 z 的情況
3. ASCII 轉換: 利用字元的 ASCII 值進行計算

JavaScript 實作

function caesarCipher(s, k) {
    let result = '';
    k = k % 26; // 處理 k 大於 26 的情況
    
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        
        if (char >= 'a' && char <= 'z') {
            // 小寫字母
            const shifted = ((char.charCodeAt(0) - 'a'.charCodeAt(0) + k) % 26);
            result += String.fromCharCode(shifted + 'a'.charCodeAt(0));
        } else if (char >= 'A' && char <= 'Z') {
            // 大寫字母
            const shifted = ((char.charCodeAt(0) - 'A'.charCodeAt(0) + k) % 26);
            result += String.fromCharCode(shifted + 'A'.charCodeAt(0));
        } else {
            // 非字母字元保持不變
            result += char;
        }
    }
    
    return result;
}

時間複雜度

• 時間: O(n) - 遍歷字串一次
• 空間: O(n) - 儲存結果字串

---

3. Strong Password

題目描述

判斷一個密碼需要多少次修改才能變成強密碼（至少6個字元，包含大寫、小寫、數字、特殊字元）

解題思路

1. 檢查條件: 長度、大寫字母、小寫字母、數字、特殊字元
2. 計算策略: 優先透過新增字元來同時滿足多個條件

JavaScript 實作

function minimumNumber(n, password) {
    let missingTypes = 0;
    
    // 檢查是否包含各種字元類型
    const hasLower = /[a-z]/.test(password);
    const hasUpper = /[A-Z]/.test(password);
    const hasDigit = /[0-9]/.test(password);
    const hasSpecial = /[!@#$%^&*()+-]/.test(password);
    
    if (!hasLower) missingTypes++;
    if (!hasUpper) missingTypes++;
    if (!hasDigit) missingTypes++;
    if (!hasSpecial) missingTypes++;
    
    // 如果長度不足 6，需要新增字元
    if (n < 6) {
        return Math.max(6 - n, missingTypes);
    }
    
    // 長度已足夠，只需要滿足字元類型要求
    return missingTypes;
}

時間複雜度

• 時間: O(n) - 檢查字串內容
• 空間: O(1) - 只用常數空間

---

4. Marc's Cakewalk

題目描述

Marc 想要吃完所有蛋糕，但每吃一塊蛋糕後，下一塊蛋糕的卡路里會加倍。找出最小總卡路里。

解題思路

1. 貪心策略: 先吃卡路里最高的蛋糕，這樣後面的倍數影響較小
2. 排序: 將蛋糕按卡路里由高到低排序
3. 計算: 第 i 塊蛋糕的實際卡路里為 calories[i] × 2^i

JavaScript 實作

function marcsCakewalk(calorie) {
    // 按卡路里由高到低排序
    calorie.sort((a, b) => b - a);
    
    let totalMiles = 0;
    
    for (let i = 0; i < calorie.length; i++) {
        // 第 i 塊蛋糕的實際卡路里
        totalMiles += calorie[i] * Math.pow(2, i);
    }
    
    return totalMiles;
}

時間複雜度

• 時間: O(n log n) - 排序的時間複雜度
• 空間: O(1) - 原地排序

---

Medium 題目

5. ⭐️ Special Palindrome Again

題目描述

計算字串中有多少個子字串是「特殊回文」（所有字元相同，或除了中間字元外都相同）

解題思路

1. 類型1: 所有字元都相同的子字串 (如 "aaa")
2. 類型2: 除了中間字元外都相同的子字串 (如 "aba")
3. 計算連續相同字元: 對於 n 個連續相同字元，有 n*(n+1)/2 個子字串

JavaScript 實作

function substrCount(n, s) {
    let count = 0;
    
    // 類型1: 計算所有連續相同字元的子字串
    let i = 0;
    while (i < n) {
        let j = i;
        // 找到連續相同字元的結束位置
        while (j < n && s[j] === s[i]) {
            j++;
        }
        
        // 連續字元的長度
        let len = j - i;
        // n 個連續字元可以形成 n*(n+1)/2 個子字串
        count += (len * (len + 1)) / 2;
        
        i = j;
    }
    
    // 類型2: 形如 "aba" 的回文（中間字元不同）
    for (let center = 1; center < n - 1; center++) {
        let left = center - 1;
        let right = center + 1;
        
        // 檢查中心兩側的字元是否相同，且與中心字元不同
        while (left >= 0 && right < n && 
               s[left] === s[right] && 
               s[left] !== s[center]) {
            count++;
            left--;
            right++;
        }
    }
    
    return count;
}

優化版本（更清晰的邏輯）

function substrCount(n, s) {
    let count = n; // 每個單字元都是回文
    
    // 類型1: 連續相同字元的組合
    for (let i = 0; i < n; i++) {
        let j = i + 1;
        while (j < n && s[j] === s[i]) {
            count++;
            j++;
        }
    }
    
    // 類型2: 形如 "aba" 的回文
    for (let center = 1; center < n - 1; center++) {
        let left = center - 1;
        let right = center + 1;
        
        while (left >= 0 && right < n && 
               s[left] === s[right] && 
               s[left] !== s[center]) {
            count++;
            left--;
            right++;
        }
    }
    
    return count;
}

時間複雜度

• 時間: O(n²) - 最壞情況下需要檢查所有可能的中心點
• 空間: O(1) - 只使用常數空間

---

HackerRank 解題技巧總結

技巧	適用情境	常見題型	時間複雜度
排序 + 貪心	最優選擇問題	Minimum Difference, Cakewalk	O(n log n)
字串處理	字元操作、編碼	Caesar Cipher	O(n)
正則表達式	模式匹配、驗證	Strong Password	O(n)
雙指針 + 中心擴展	回文檢測	Special Palindrome	O(n²)
數學計算	組合計數	Special Palindrome	O(1)

解題心得

1. HackerRank vs LeetCode：

   • HackerRank 更注重實際應用場景
   • 題目描述通常更貼近現實問題
   • 測試案例更多樣化

2. 常見陷阱：

   • 注意邊界條件（空字串、單字元等）
   • 處理大數值時考慮溢出問題
   • 字串操作時注意大小寫敏感性

3. 優化策略：

   • 排序通常是第一步優化手段
   • 善用數學公式減少重複計算
   • 考慮時間與空間的取捨

4. 除錯技巧：

   • 先用簡單測試案例驗證邏輯
   • 分步驟檢查中間結果
   • 注意輸出格式要求