---
# System prepended metadata

title: Leetcode(1~100)

---

# Leetcode 1~90(c++資結演算法)
~~~~
紅色=Hard, 黃色=Medium, 綠色=Easy
~~~~
###  <font color="c1ab0c">2. Linked list</font>

#### [題目：Add Two Numbers](https://leetcode.com/problems/add-two-numbers/description/)
內建ListNode存有當前位的數字及指向下位的地址。
1. 建一個虛擬頭節點 dummy，以及一個指標 curr 指向它。(移動curr去完成dummy)
1. 建立一個變數 carry = 0。
1. 用 while 迴圈遍歷 l1 和 l2，直到都為空且 carry = 0。
1. 每次迴圈取出 l1 和 l2 當前的值（若為 nullptr 則為 0），加上 carry。
1. 計算當前位數 sum % 10，以及更新進位 carry = sum / 10。
1. 把該位數加入新 list，curr = curr->next。
1. 返回 dummy->next 即為答案。
```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* curr = dummy;
        int carry = 0;
        while(l1!=nullptr || l2!=nullptr || carry!=0){
            int x = (l1!=nullptr)? l1->val : 0;//若為空 則=0
            int y = (l2!=nullptr)? l2->val : 0;//若為空 則=0
            int sum= x + y + carry;
            carry=sum/10;
            curr->next = new ListNode(sum%10);
            curr = curr->next;
            //l1 l2如果目前不是空的就繼續前進
            if(l1) l1=l1->next;
            if(l2) l2=l2->next;
        }
        return dummy->next;
    }
};
```
---
###  <font color="c1ab0c">3. Sliding window</font>

#### [題目：Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/description/)
用字元會自動轉換成ASCII編碼的特性，開一個128大小的陣列去存每個字元最後一次出現的位置+1，例如'a'=97，index[97]=3，意思是字符 'a' 在位置 2，那麼下次遇到 'a' 時，left 應該跳到位置 3。
```cpp=
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int index[128] = {0}; // 初始化為 0
        int maxLen = 0, left = 0;
        
        for (int right = 0; right < s.size(); right++) {
            left = max(left, index[s[right]]);
            int currentLen = right - left + 1;
            if (currentLen > maxLen) maxLen = currentLen;
            index[s[right]] = right + 1;
        }
        return maxLen;
    }
};
```
---
###  <font color="FF5151">4. Array </font>

#### [題目：Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/description/)
難點：O(log(m+n))
核心思路：**二分搜索**
我們需要找到一個分割點，將兩個數組分成左右兩部分，使得：

左半部分的元素個數 = 右半部分的元素個數（或相差1）
左半部分的最大值 ≤ 右半部分的最小值
```cpp=
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 確保 nums1 是較短的數組，減少搜索空間
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.size();
        int n = nums2.size();
        int total = m + n;
        int half = (total + 1) / 2;  // 左半部分應有的元素個數
        
        int left = 0, right = m;
        
        while (left <= right) {
            // 在 nums1 中的分割點
            int cut1 = (left + right) / 2;
            // 在 nums2 中的分割點
            int cut2 = half - cut1;
            
            // 左半部分的最大值
            int maxLeft1 = (cut1 == 0) ? INT_MIN : nums1[cut1 - 1];
            int maxLeft2 = (cut2 == 0) ? INT_MIN : nums2[cut2 - 1];
            int maxLeft = max(maxLeft1, maxLeft2);
            
            // 右半部分的最小值
            int minRight1 = (cut1 == m) ? INT_MAX : nums1[cut1];
            int minRight2 = (cut2 == n) ? INT_MAX : nums2[cut2];
            int minRight = min(minRight1, minRight2);
            
            // 找到正確的分割點
            if (maxLeft <= minRight) {
                if (total % 2 == 0) {
                    // 偶數個元素，返回中間兩個的平均值
                    return (maxLeft + minRight) / 2.0;
                } else {
                    // 奇數個元素，返回左半部分的最大值
                    return maxLeft;
                }
            }
            // nums1 的分割點太靠右了
            else if (maxLeft1 > minRight2) {
                right = cut1 - 1;
            }
            // nums1 的分割點太靠左了
            else {
                left = cut1 + 1;
            }
        }
        
        return -1; // 理論上不會到達這裡
    }
};
```
---
###  <font color="c1ab0c">5. 迴文子字串</font>

#### [題目：Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)
遍歷以第i個位元為中心的迴文子字串，分別檢查偶字數中心跟奇字數中心(往兩邊字判斷是否相同)，   start = i - (cur_maxlen-1) / 2，是因為EX:aba時，i在b，cur_maxlen=3，起始點為i-1;
EX:abba時，i在第一個b，cur_maxlen=4，起始點為i-1。(3/2=1)

```cpp=
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length()==0) return "";
        int start=0,maxlen=0;
        for(int i=0;i<s.length();i++){
            //奇數中心 
            int len1 = cal(s,i,i); //aba 中心是b
            //偶數中心
            int len2 = cal(s,i,i+1); //abba 中心是bb

            int cur_maxlen=max(len1,len2); //i這個位置最大的回文長度
            if(cur_maxlen>maxlen){
                maxlen = cur_maxlen;
                start = i- (cur_maxlen-1)/2;
            }
        }
        return s.substr(start, maxlen);
    }
    int cal(string s,int left,int right){
        while(left>=0 && right<s.length() && s[left]==s[right]){
            left--;
            right++;
        }
        return right-left-1;
    }
};
```
---
###  <font color="c1ab0c">6. 之字形重組字串</font>

#### [題目：Zigzag Conversion](https://leetcode.com/problems/zigzag-conversion/description/)
用一個陣列來儲存每一行的字元，然後模擬這個鋸齒形填充過程：

1. 建立 numRows 個字串陣列，每個代表一行
1. 用一個變數 cnt 追蹤目前行
1. 用一個變數 dir 表示目前是向下還是向上移動
1. 遍歷字串，將每個字元加到對應行
1. 當到達頂部或底部時，改變方向

```cpp=
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;

        vector<string> rows(numRows);
        int dir=0;//0代表往下數 1代表往上數
        int cnt=0; //走到哪row
        for(char c:s){
            rows[cnt]+=c;
            if(dir==0) cnt++;
            else cnt--;

            if(cnt==(numRows-1) || cnt==0){
                if(dir==0) dir=1;
                else dir=0;
            }
        }
        string result;
        for(string row : rows){
            result+=row;
        }
        return result;
    }
};
```
---
###  <font color="c1ab0c">7. 翻轉整數</font>

#### [題目： Reverse Integer](https://leetcode.com/problems/reverse-integer/description/)
1. 逐位取出最後一位數字
1. 在將新數字加入結果前，檢查是否會溢位
1. 溢位條件：
如果 result > INT_MAX/10，那麼 result*10 就已經超過 INT_MAX 了
如果 result == INT_MAX/10，還要檢查加上 digit 後是否超過 INT_MAX
```cpp=
class Solution {
public:
    int reverse(int x) {
        int result=0;
        while(x!=0){
            int digit=x%10;
            x=x/10;
            //正溢位
            if(result>INT_MAX/10 || (result==INT_MAX/10 && digit>INT_MAX%10)){
                return 0;
            }

            //負溢位
            if(result<INT_MIN/10 || (result==INT_MIN/10 && digit<INT_MIN%10)){
                return 0;
            }

            result=result*10+digit;
        }
        return result;
    }
};
```
---
###  <font color="c1ab0c">8. 字串to數字</font>

#### [題目： String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/description/)


```cpp=
class Solution {
public:
    int myAtoi(string s) {
        if(s.empty()) return 0; //空的直接回傳
        int i=0;
        int n=s.length();
        while(i<n&&s[i]==' '){ //略過空白字元
            i++;
        }
        if(i==n){//全空白直接回傳
            return 0;
        }

        int sign=1;
        if(s[i]=='+'||s[i]=='-'){ //處理sign
            if(s[i]=='-'){
                sign=-1;
            }
            i++;
        }
        long long result=0;
        while (i < n && isdigit(s[i])) {
            int digit = s[i] - '0';
            result = result * 10 + digit;
            
            // 提前檢查溢出，避免 long long 也溢出
            if (sign == 1 && result > INT_MAX) {
                return INT_MAX;
            }
            if (sign == -1 && result > (long long)INT_MAX + 1) {
                return INT_MIN;
            }
            
            i++;
        }

        // 步驟 4: 應用正負號
        result *= sign;
        
        // 最終範圍檢查（雙重保險）
        if (result < INT_MIN) {
            return INT_MIN;
        }
        if (result > INT_MAX) {
            return INT_MAX;
        }
        
        return (int)result;
    }
};
```
---
###  <font color="green">9. 迴文判斷(數字)</font>

#### [題目： Palindrome Number](https://leetcode.com/problems/palindrome-number/description//)
1. 負數和以0結尾的數字必不是迴文
2. 反轉一半位數，根據位數奇偶性判斷是否一樣

```cpp=
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return false;
        else if((x%10==0&&x!=0)) return false;

        int reverse_half=0;
        while(x>reverse_half){
            reverse_half=reverse_half*10+x%10;
            x/=10;
        }
        //奇數個位數 x=reverse_half/10 去掉中間位
        //偶數個位數 x=reverse_half
        return x==reverse_half||x==reverse_half/10;
    }
};
```
---
###  <font color="FF5151">10. 動態規劃</font>

#### [題目： Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/description/)
DP 狀態定義：
*       dp[i][j] = true 表示字串 s[0...i-1] 能夠匹配模式 p[0...j-1]

```cpp=
class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.length();
        int n=p.length();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));

        //初始化基礎情況
        dp[0][0]=true; //空字串配空模式

        //空字串與含有*
        for(int j=2;j<=n;j++){
            if(p[j-1]=='*'){
                dp[0][j]=dp[0][j-2];
            }
        }

        //填充dp
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                char sc=s[i-1];
                char pc=p[j-1];

                if(pc=='*'){
                    // *匹配前面的字符
                    char prechar = p[j-2];

                    //兩種情況
                    //1.忽略x*
                    dp[i][j]=dp[i][j-2];
                    //2.如果前面字符匹配，使用x*模式
                    if(prechar=='.'||prechar==sc){
                        dp[i][j]=dp[i][j]||dp[i-1][j];
                    }
                }else if(pc=='.'||pc==sc){
                    dp[i][j]=dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
};
```
---
###  <font color="c1ab0c">11. 兩指標</font>

#### [題目： Container With Most Water](https://leetcode.com/problems/container-with-most-water/description/)

容器的水量 = 寬度 × 高度
* 寬度 = 兩條線之間的距離
* 高度 = 兩條線中較短的那條（因為水會從短的那邊溢出）

為什麼要移動較短的線？
假設當前左指標指向較短的線：

如果移動右指標，寬度減少，高度仍受左邊較短線限制 → 面積必定變小
如果移動左指標，雖然寬度減少，但可能找到更高的線 → 有機會增加面積

```cpp=
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0,right=height.size()-1,ans=0,cur_high;
        while(left<right){
            cur_high=min(height[left],height[right]);
            ans=max(ans, cur_high*(right-left));
            if(cur_high==height[right]) right--;
            else left++;
        }
        return ans;
    }
};
```
---
###  <font color="c1ab0c">12. 貪心算法</font>

#### [題目： Integer to Roman](https://leetcode.com/problems/integer-to-roman/description/)

預處理映射表：將所有可能的羅馬數字組合（包括減法表示法）按數值大小排序
貪心策略：總是優先使用最大可能的羅馬數字組合
特殊情況處理：

* IV(4), IX(9), XL(40), XC(90), CD(400), CM(900) 這些減法表示法
* 避免出現 IIII, XXXX, CCCC 等超過3個重複的情況


演算法流程：

1. 遍歷映射表中的每個數值-符號對
1. 計算當前數值可以被整除多少次
1. 將對應次數的符號加入結果
1. 更新剩餘數值
```cpp=
class Solution {
public:
    std::string intToRoman(int num) {
        // 定義所有可能的羅馬數字組合，按數值從大到小排列
        // 包含減法表示法：CM(900), CD(400), XC(90), XL(40), IX(9), IV(4)
        std::vector<std::pair<int, std::string>> valueSymbols = {
            {1000, "M"},  {900, "CM"}, {500, "D"},  {400, "CD"},
            {100, "C"},   {90, "XC"},  {50, "L"},   {40, "XL"},
            {10, "X"},    {9, "IX"},   {5, "V"},    {4, "IV"},
            {1, "I"}
        };
        
        std::string result = "";
        
        // 貪心算法：從最大的數值開始處理
        for (const auto& pair : valueSymbols) {
            int value = pair.first;
            const std::string& symbol = pair.second;
            
            // 計算當前數值可以使用多少次
            int count = num / value;
            
            // 將對應的羅馬數字符號加入結果
            for (int i = 0; i < count; i++) {
                result += symbol;
            }
            
            // 更新剩餘的數值
            num %= value;
            
            // 如果已經處理完畢，可以提前結束
            if (num == 0) break;
        }
        
        return result;
    }
};
```
---
###  <font color="green">13. 上題的逆向</font>

#### [題目： 13. Roman to Integer](https://leetcode.com/problems/roman-to-integer/description/)

```cpp=
class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int>romanMap={
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };

        int result=0;
        int preValue=0;
        // 從右到左遍歷字符串
        for (int i = s.length() - 1; i >= 0; i--) {
            int currentValue = romanMap[s[i]];
            
            // 如果當前值小於前一個值，表示是減法情況
            if (currentValue < preValue) {
                result -= currentValue;
            } else {
                result += currentValue;
            }
            
            preValue = currentValue;
        }
        
        return result;
    }
};
```
---
###  <font color="green">14. 相同字串前綴</font>

#### [題目： 13. Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/description/)

1. 找出最短字串
2. i=目前比較位置字元，j遍歷每個strs內的字串

```cpp=
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int minlen=strs[0].length();
        for(const string& str:strs){
            minlen=min(minlen,(int)str.length());
        }
        for(int i=0;i<minlen;i++){
            for(int j=1;j<strs.size();j++){
                if(strs[0][i]!=strs[j][i]) return strs[0].substr(0,i);
            }
        }
        return strs[0].substr(0,minlen);
    }
};
```
---
###  <font color="c1ab0c">15. 兩指標</font>

#### [題目： 3Sum](https://leetcode.com/problems/3sum/description/)

先排序，i遍歷每一個元素(做為第一個元素)，利用left right找出剩下符合的兩個元素，太大把右邊往左移，太小則把左邊往右移

```cpp=
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            //跳過重複的第一位
            if(i>0&&nums[i]==nums[i-1]) continue;
            //雙指針
            int left=i+1;
            int right=nums.size()-1;
            while(left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum==0){
                    ans.push_back({nums[i],nums[left],nums[right]});

                    while(left<right&&nums[left]==nums[left+1]){//左邊跳過重複的
                        left++;
                    }
                    while(left<right&&nums[right]==nums[right-1]){//右邊跳過重複的
                        right--;
                    }
                    left++;
                    right--;
                }else if(sum>0){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ans;
    }
};
```
---
###  <font color="c1ab0c">16. 兩指標</font>

#### [題目： 3Sum Closest](https://leetcode.com/problems/3sum-closest/description/)

先排序，i遍歷每一個元素(做為第一個元素)，利用left right找出剩下最接近target的兩個元素，太大把右邊往左移，太小則把左邊往右移
```cpp=
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        //初始化
        int closest=nums[0]+nums[1]+nums[2];
        int minDiff=abs(target-closest);

        for(int i=0;i<nums.size();i++){
            //跳過重複的第一位
            if(i>0&&nums[i]==nums[i-1]) continue;
            //雙指針
            int left=i+1;
            int right=nums.size()-1;
            while(left<right){
                int sum=nums[i]+nums[left]+nums[right];
                int curDiff=abs(target-sum);
                if(curDiff<minDiff){
                    closest=sum;
                    minDiff=curDiff; 
                }
                
                if(sum==target){
                    return target;
                }else if(sum>target){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return closest;
    }
};
```
---
###  <font color="c1ab0c">17. 字串組合</font>

#### [題目： Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/)
* 核心思想：
從空字串開始，對每個數字的每個字母進行擴展
每次處理一個數字，將現有的所有組合與新字母結合

執行過程（以 "23" 為例）：
初始: [""]
處理 '2': ["a", "b", "c"]
處理 '3': ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
```cpp=
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        vector<string> ans={""};
        unordered_map<char, string> mapping = {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, 
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };

        for(const char& digit:digits){
            vector<string> temp;
            string letters=mapping[digit];
            for(const string& combination:ans){
                for(char letter:letters){
                    temp.push_back(combination+letter);
                }
            }
            ans=temp;
        }
        return ans;
    }
};
```
---
###  <font color="c1ab0c">18. 兩指標</font>

#### [題目： 4Sum](https://leetcode.com/problems/3sum-closest/description/)

1. 排序 + 雙指針法：
先將陣列排序，這樣可以使用雙指針技巧
使用四層結構：兩層迴圈固定前兩個數字，雙指針找後兩個數字
2. 避免重複解：
在每一層都跳過重複的數字
當找到一組解後，移動指針時也要跳過重複值
3. 處理溢位問題：
使用 long long 來避免整數溢位
特別是在計算 target - nums[i] - nums[j] 時
```cpp=
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        int n = nums.size();
        
        // 如果陣列長度小於4，無法形成四元組
        if (n < 4) return result;
        sort(nums.begin(), nums.end());
        
        // 第一層迴圈：固定第一個數字
        for (int i = 0; i < n - 3; i++) {
            // 跳過重複的第一個數字
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            // 第二層迴圈：固定第二個數字
            for (int j = i + 1; j < n - 2; j++) {
                // 跳過重複的第二個數字
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                
                // 使用雙指針找剩下的兩個數字
                int left = j + 1;
                int right = n - 1;
                
                // 計算目標值（注意溢位問題）
                long long target2 = (long long)target - nums[i] - nums[j];
                
                while (left < right) {
                    long long sum = (long long)nums[left] + nums[right];
                    
                    if (sum == target2) {
                        // 找到一組解
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        
                        // 跳過重複的左指針值
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        // 跳過重複的右指針值
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        
                        left++;
                        right--;
                    }
                    else if (sum < target2) {
                        left++;
                    }
                    else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
};
```
---
###  <font color="c1ab0c">19. 兩指標+Linked list</font>

#### [題目： Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/)

這個方法的思路如下：

1. 設定虛擬節點 (Dummy Node)：在鏈結串列的頭部 head 前面創建一個虛擬的 dummy 節點。這個節點的目的是為了簡化邊界情況，特別是當要被移除的節點正好是原始的頭部節點時，虛擬節點可以確保每個節點（包括頭部）都有一個前驅節點，讓刪除操作的邏輯保持一致。

1. 初始化快慢指標：我們使用兩個指標，fast（快指標）和 slow（慢指標），兩者一開始都指向這個 dummy 節點。

1. 拉開指標間距：讓 fast 指標先向前移動 n + 1 步。這樣做會在 fast 和 slow 指標之間創造一個 n 個節點的「窗口」或「間距」。

1. 同步移動指標：接著，同時移動 fast 和 slow 指標，每次都向前一步。持續這個過程，直到 fast 指標到達鏈結串列的末尾（即 fast 變為 nullptr）。

1. 定位與刪除：當 fast 指標到達終點時，由於它們之間固定的 n 個節點的間距，slow 指標此時會正好停在要被刪除節點的前一個節點上。

1. 執行刪除：要刪除目標節點，我們只需要修改 slow 指標的 next 指向，讓它跳過目標節點，直接指向目標節點的下一個節點即可 (slow->next = slow->next->next;)。同時，為了防止記憶體洩漏，最好將被刪除的節點釋放掉。

1. 返回結果：最後，返回 dummy->next。這就是修改後的新鏈結串列的頭部。
```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next=head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;

        for(int i=0;i<=n;i++){
            fast=fast->next;
        }
        while(fast!=nullptr){
            fast=fast->next;
            slow=slow->next;
        }
        ListNode* temp=slow->next;
        slow->next=slow->next->next;
        delete temp;
        return dummy->next;
    }
};
```
---
###  <font color="c1ab0c">20. Stack</font>

#### [題目： Valid Parentheses](https://leetcode.com/problems/valid-parentheses/description/)

遇到閉括號 → 查字典找對應的開括號
檢查堆疊頂端是否匹配
匹配就彈出，不匹配就返回 false
```cpp=
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> closeToOpen = {
            {')', '('},
            {'}', '{'},
            {']', '['}
        };
        
        stack<char> st;
        
        for (char c : s) {
            // 如果是閉括號
            if (closeToOpen.find(c) != closeToOpen.end()) {
                // 檢查堆疊是否為空，或頂端是否匹配
                if (st.empty() || st.top() != closeToOpen[c]) {
                    return false;
                }
                st.pop();
            }
            // 如果是開括號，直接推入堆疊
            else {
                st.push(c);
            }
        }
        
        return st.empty();
    }
};
```
---
###  <font color="green">21. Linked list合併</font>

#### [題目： Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/)
這個問題的關鍵是雙指標技巧：

1. 用兩個指標分別指向兩個已排序的鏈結串列
1. 比較當前節點值，選擇較小的連接到結果中
1. 移動對應指標，重複過程

```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur=dummy;
        while(list1!=nullptr&&list2!=nullptr){
            if(list1->val<=list2->val){
                cur->next=list1;
                list1=list1->next;
            }else{
                cur->next=list2;
                list2=list2->next;
            }
            cur=cur->next;
        }
        
        //處理較長的list還沒被加入的部分
        if(list1!=nullptr){
            cur->next=list1;
        }else if(list2!=nullptr){
            cur->next=list2;
        }
        
        return dummy->next;
    }
};
```
---
###  <font color="c1ab0c">22. 遞迴</font>

#### [題目： Generate Parentheses](https://leetcode.com/problems/generate-parentheses/description/)


```cpp=
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        cal(result,"",n,0,0);
        return result;
    }
    void cal(vector<string>& result,string cur,int n,int open,int close){
        // 終止條件：當字串長度等於 2 * n，表示找到一個有效組合
        if(open+close==2*n){
            result.push_back(cur);
            return;
        }
        // 規則一：如果左括號的數量還沒達到上限 n，就可以添加一個左括號
        if(open<n) cal(result,cur+"(",n,open+1,close);
        // 規則二：如果右括號的數量小於左括號，就可以添加一個右括號以進行匹配
        if(open>close) cal(result,cur+")",n,open,close+1);
    }
};
```
---
###  <font color="c1ab0c">23. Priority queue + Linked list</font>

#### [題目： Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/description/)
核心思想：使用優先佇列(最小堆)來追蹤每個鏈表的當前最小節點

時間複雜度：O(N log k)，其中 N 是所有節點總數
空間複雜度：O(k)，堆的大小
優點：效率高，容易理解

工作原理：

1. 將每個鏈表的第一個節點放入最小堆
1. 每次從堆中取出最小值節點，加入結果鏈表
1. 如果該節點有下一個節點，將下一個節點加入堆
1. 重複直到堆為空

```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return{};
        auto compare = [](ListNode* a, ListNode* b) {
            return a->val > b->val;//使最小的在最前面
        };
        
        priority_queue<ListNode*, vector<ListNode*>, decltype(compare)>
            minHeap(compare);
        for(ListNode* list:lists){
            if(list!=nullptr) minHeap.push(list);
        }

        ListNode* dummy = new ListNode(0);
        ListNode* cur=dummy;
        while(!minHeap.empty()){
            //目前最小
            ListNode* minNode=minHeap.top();
            minHeap.pop();
            cur->next=minNode;
            cur=cur->next;
            //如果目前最小還有下一個就更新
            if(minNode->next!=nullptr){
                minHeap.push(minNode->next);
            }
        }
        return dummy->next;
    }
};
```
---
###  <font color="c1ab0c">24. Linked List</font>

#### [題目： Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
1. 用prev指針追蹤當前要交換的節點對的前一個節點
1. 逐對交換節點

```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy =  new ListNode(0);
        ListNode* prev=dummy;
        dummy->next=head;
        while(prev->next!=nullptr && prev->next->next!=nullptr){//還有兩個可以交換
            ListNode* first=prev->next;
            ListNode* sec=prev->next->next;
            //交換
            prev->next=sec;
            first->next=sec->next;
            sec->next=first;
            //移動prev
            prev=first;
        }
        return dummy->next;
    }
};
```
---
###  <font color="FF5151">25. Linked List反轉(難)</font>

#### [題目： Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/description/)


```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(!head||k==1) return head;
        ListNode* dummy =new ListNode(0);
        dummy->next=head;
        ListNode* prev=dummy;
        int length=getLength(head);
        //確保剩下的長度還超過k即要處理
        while(length>=k){
            //目前組的開始和結束位置
            ListNode* start=prev->next;
            ListNode* end=start;
            for(int i=1;i<k;i++){
                end=end->next;
            }
            //下一組開始處理
            ListNode* nextStart=end->next;

            reverseGroup(start,end);
            // 連接反轉後的組
            // 注意：反轉後 end 變成了組的開頭，start 變成了組的結尾
            prev->next = end;
            start->next = nextStart;
            
            // 更新指針，準備處理下一組
            prev = start;
            length -= k;
        }
        return dummy->next;
    }
    void reverseGroup(ListNode* start,ListNode* end){
        ListNode* prev = end->next;  // 這將成為反轉後第一個節點的 next
        ListNode* curr = start;
        
        // 反轉過程，直到處理完 end 節點
        while (prev != end) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
    }
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            length++;
            head = head->next;
        }
        return length;
    }
};
```
---
###  <font color="green">26. 移除重複</font>

#### [題目： Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/)

```cpp=
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0;
        int cur=1;
        for(int num:nums){
            if(num!=nums[cur-1]){
                nums[cur]=num;
                cur++;
            }
        }
        return cur;
    }
};
```
---
###  <font color="green">27. 移除指定的數字</font>

#### [題目： Remove Element](https://leetcode.com/problems/remove-element/description/)

```cpp=
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
       int cur=0;
       for(int num:nums){
            if(num!=val){
                nums[cur]=num;
                cur++;
            }
       } 
       return cur;
    }
};
```
---
###  <font color="green">28. 找第二個字串是否有出現在第一個字串中</font>

#### [題目：Find the Index of the First Occurrence in a String](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)

```cpp=
class Solution {
public:
    int strStr(string haystack, string needle) {
        for(int i=0;i<haystack.length();i++){
            if(haystack[i]==needle[0]){ //出現第二個字的開頭
                if(cal(haystack,needle,i,needle.length())) return i;
            }
        }
        return -1;
    }
    bool cal(string& haystack,string& neddle,int cur,int len){
        for(int i=0;i<len;i++){ //檢查到第二個字的長度 是否都相同
            if(haystack[i+cur]!=neddle[i]) return false;
        }
        return true;
    }
};
```
---
###  <font color="c1ab0c">29. 除法</font>

#### [題目： Divide Two Integers](https://leetcode.com/problems/divide-two-integers/description/)
為什麼用負數？

INT_MIN = -2147483648
INT_MAX = 2147483647
abs(INT_MIN) = 2147483648 → 無法用int表示！
但所有正數都可以轉換為負數
* 算法邏輯（負數環境）
轉換：將所有數轉為負數
比較：absDividend <= absDivisor（都是負數）
倍增：tempDivisor += tempDivisor（相當於乘以2）
quotient=商

```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy =  new ListNode(0);
        ListNode* prev=dummy;
        dummy->next=head;
        while(prev->next!=nullptr && prev->next->next!=nullptr){//還有兩個可以交換
            ListNode* first=prev->next;
            ListNode* sec=prev->next->next;
            //交換
            prev->next=sec;
            first->next=sec->next;
            sec->next=first;
            //移動prev
            prev=first;
        }
        return dummy->next;
    }
};
```
---
###  <font color="FF5151">25. 子字串(sliding window)</font>

#### [題目： Substring with Concatenation of All Words](https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/)
解題思路：

1. 預處理：統計 words 陣列中每個單詞的出現頻率
1. 滑動窗口：由於所有單詞長度相同，我們只需要嘗試從 0 到 wordLen-1 的起始位置
1. 向右擴展窗口，每次加入一個單詞
1. 如果單詞有效（存在於 words 中），將其加入窗口頻率表
1. 如果某個單詞出現次數過多，從左側縮小窗口
1. 如果遇到無效單詞，重置整個窗口


有效性檢查：當 validWords 等於 wordCount 時，找到一個有效的連接
i為何只需從0到len-1：
假設 wordLen = 3，字串 s = "abcdefghijklmno"
我們可以將字串按照以下方式分組：
* 起始位置 0：
位置: 0   3   6   9   12
     abc def ghi jkl mno
     ↑   ↑   ↑   ↑   ↑
* 起始位置 1：
位置: 1   4   7   10  13
     bcd efg hij klm ...
     ↑   ↑   ↑   ↑
* 起始位置 2：
位置: 2   5   8   11  14
     cde fgh ijk lmn ...
     ↑   ↑   ↑   ↑
* 起始位置 3：
位置: 3   6   9   12
     def ghi jkl mno
     ↑   ↑   ↑   ↑
    
可發現3=0往右一個單詞(重複)
```cpp=
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        if (s.empty() || words.empty()) return result;
        
        int wordLen = words[0].length();           // 每個單詞的長度
        int wordCount = words.size();              // 單詞的總數量
        int totalLen = wordLen * wordCount;        // 所有單詞連接後的總長度
        
        if (s.length() < totalLen) return result;
        
        // 統計每個單詞出現的頻率
        unordered_map<string, int> wordFreq;
        for (const string& word : words) {
            wordFreq[word]++;
        }
        
        // 嘗試從每個可能的起始位置開始（0到wordLen-1）
        for (int i = 0; i < wordLen; i++) {
            int left = i;                          // 滑動窗口左邊界
            int right = i;                         // 滑動窗口右邊界
            unordered_map<string, int> windowFreq; // 當前窗口中單詞的頻率
            int validWords = 0;                    // 當前窗口中有效單詞的數量
            
            while (right + wordLen <= s.length()) {
                // 取出下一個單詞
                string word = s.substr(right, wordLen);
                right += wordLen;
                
                if (wordFreq.count(word)) {
                    windowFreq[word]++;
                    validWords++;
                    
                    // 如果某個單詞出現次數超過要求，從左側縮小窗口
                    while (windowFreq[word] > wordFreq[word]) {
                        string leftWord = s.substr(left, wordLen);
                        windowFreq[leftWord]--;
                        validWords--;
                        left += wordLen;
                    }
                    
                    // 如果窗口中的有效單詞數量正好等於要求的數量
                    if (validWords == wordCount) {
                        result.push_back(left);
                    }
                } else {
                    // 如果遇到不在words陣列中的單詞，重置窗口
                    windowFreq.clear();
                    validWords = 0;
                    left = right;
                }
            }
        }
        
        return result;
    }
};
```
---
###  <font color="c1ab0c">31. 找下個字典排序</font>

#### [題目：Next Permutation](https://leetcode.com/problems/next-permutation/description/)

```cpp=
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
       int n = nums.size();
        
        // 步驟 1: 從右往左找到第一個 nums[i] < nums[i+1] 的位置
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        // 步驟 2: 如果找到了這樣的 i，從右往左找第一個比 nums[i] 大的數
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // 步驟 3: 交換 nums[i] 和 nums[j]
            swap(nums[i], nums[j]);
        }
        
        // 步驟 4: 將 i+1 到末尾的部分反轉
        reverse(nums.begin() + i + 1, nums.end()); 
    }
};
```
---
###  <font color="FF5151">32. 子字串(sliding window)</font>

#### [題目： Substring with Concatenation of All Words](https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/)
狀態定義：dp[i] 表示以索引 i 結尾的最長有效括號子字串長度
狀態轉移：

只有當 s[i] == ')' 時才可能形成有效括號
情況1：s[i-1] == '(' 直接配對 () 
* dp[i] = dp[i-2] + 2

情況2:
當我們遇到連續的 '))' 時，需要找到與當前 ')' 匹配的 '('。
關鍵公式解析：
cppint matchIndex = i - dp[i-1] - 1;
為什麼這樣計算？

i = 當前 ')' 的位置
dp[i-1] = 前一個位置結尾的有效括號長度
i - dp[i-1] = 跳過前面已經配對的括號部分
i - dp[i-1] - 1 = 再往前一位，這就是可能與當前 ')' 配對的 '(' 位置
```cpp=
class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.length();
        if(n<=1) return 0;
        //dp[i] 表示以索引 i 結尾的最長有效括號子字串長度
        vector<int> dp(n,0);
        int maxlen=0;
        for(int i=1;i<n;i++){
            if(s[i]==')'){
                if(s[i-1]=='('){
                    dp[i]=(i>2? dp[i-2]:0)+2;
                }else if(dp[i-1]>0){
                    int matchindex=i-dp[i-1]-1;
                    if(matchindex>=0&&s[matchindex]=='('){
                        dp[i] = dp[i-1] + 2 + (matchindex > 0 ? dp[matchindex-1] : 0);
                    }
                }
            }
            maxlen=max(maxlen,dp[i]);
        }
        return maxlen;
    }
};
```
---
###  <font color="c1ab0c">33. 二分搜</font>

#### [題目：Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/description/)
在旋轉的排序陣列中，對於任意中點，左半部分或右半部分至少有一邊是完全有序的。
```cpp=
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target) return mid;
            if(nums[left]<=nums[mid]){//左半部分有序
                if(nums[left]<=target && target<nums[mid]){
                    right=mid-1; //往左搜
                }else{
                    left=mid+1; //往右搜
                }
            }else{//右半部分有序
                if(nums[mid]<target && target<=nums[right]){
                    left=mid+1; //往右搜
                }else{
                    right=mid-1; //往左搜
                }
            }
        }
        return -1;
    }
};
```
---
###  <font color="green">35. 二分搜</font>

#### [題目： Search Insert Position](https://leetcode.com/problems/search-insert-position/description/)

```cpp=
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid]>target) right=mid-1;
            else left=mid+1;
        }
        return left;
    }
};
```
---
###  <font color="c1ab0c">36. 數獨</font>

#### [題目：Valid Sudoku](https://leetcode.com/problems/valid-sudoku/description/)
使用三個二維布林陣列分別記錄行、列、子盒中數字的出現狀況
子盒編號計算公式：(i/3) * 3 + (j/3)
```cpp=
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //開3個二維陣列分別記錄行/列/3*3box出現過的數字0~9
        vector<vector<bool>> rows(9,vector<bool>(10,false));
        vector<vector<bool>> columns(9,vector<bool>(10,false));
        vector<vector<bool>> boxs(9,vector<bool>(10,false));

        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                char c=board[i][j];
                if(c=='.') continue;
                int boxindex=(i/3)*3+(j/3);
                int num=c-'0'; //轉成數字
                if(rows[i][num]||columns[j][num]||boxs[boxindex][num]){
                    return false;
                }

                rows[i][num]=true;
                columns[j][num]=true;
                boxs[boxindex][num]=true;
            }
        }
        return true;
    }
};
```
---
###  <font color="FF5151">37. 解數獨</font>

#### [題目： Sudoku Solver](https://leetcode.com/problems/sudoku-solver/description/)
1. **主要策略**
使用遞歸和回溯的方法
逐一處理每個空格子（標記為 '.'）
對每個空格子嘗試放入數字 1-9
如果某個數字符合規則，就放入並繼續求解
如果發現無解，就回溯並嘗試下一個數字

2. **關鍵函數**
* solve(board)：
找到第一個空格子
嘗試放入數字 1-9
遞歸求解剩餘部分
如果無解則回溯

* isValid(board, row, col, num)：
檢查在指定位置放入數字是否符合數獨規則
檢查同一行是否有重複
檢查同一列是否有重複
檢查同一 3x3 子方格是否有重複
```cpp=
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
    bool solve(vector<vector<char>>& board) {
        // 找到第一個空的格子
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.') {
                    // 嘗試放入數字 1-9
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num;
                            
                            // 遞歸求解剩餘部分
                            if (solve(board)) {
                                return true;
                            }
                            
                            // 回溯：如果當前選擇導致無解，則撤銷選擇
                            board[row][col] = '.';
                        }
                    }
                    // 如果數字 1-9 都不能放入此位置，返回 false
                    return false;
                }
            }
        }
        // 所有格子都已填滿，求解成功
        return true;
    }
    bool isValid(vector<vector<char>>& board, int row, int col, char num) {
        // 檢查行
        for (int j = 0; j < 9; j++) {
            if (board[row][j] == num) {
                return false;
            }
        }
        
        // 檢查列
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num) {
                return false;
            }
        }
        
        // 檢查 3x3 子方格
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == num) {
                    return false;
                }
            }
        }
        
        return true;
    }
};
```
---
###  <font color="c1ab0c">38. 遞迴</font>

#### [題目：Count and Say](https://leetcode.com/problems/count-and-say/description/)
用cur紀錄當前要看的字串，記得最後處理最後一組。

```cpp=
class Solution {
public:
    string countAndSay(int n) {
        if(n == 1) return "1";
        
        string cur = countAndSay(n-1);
        int cnt = 1;
        string ans;
        
        for(int i = 1; i < cur.length(); i++) {
            if(cur[i] == cur[i-1]) {
                cnt++;
            } else {
                ans += to_string(cnt); 
                ans += cur[i-1];
                cnt = 1;
            }
        }
        
        // 處理最後一組
        ans += to_string(cnt);
        ans += cur[cur.length()-1];
        
        return ans;
    }
};
```
---
###  <font color="c1ab0c">39. 回溯</font>

#### [題目：Combination Sum](https://leetcode.com/problems/combination-sum/description/)

核心概念

狀態空間樹：每個節點代表一個決策點（選擇或不選擇某個數字）
剪枝優化：當當前數字大於剩餘目標時，直接跳出循環
避免重複：通過start參數確保只考慮當前位置及之後的候選數字

算法步驟

1. 排序：先對候選數組排序，便於剪枝

1. 遞歸探索：
如果target == 0，找到一個有效組合
否則嘗試每個候選數字
由於可以重複使用，遞歸時start保持為當前索引i


1. 回溯：撤銷當前選擇，嘗試下一個可能性

```cpp=
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> current;
        sort(candidates.begin(),candidates.end());
        backtrack(candidates, target, 0, current, result);
        return result;
    }
    void backtrack(vector<int>& candidates, int target, int start, 
                   vector<int>& current, vector<vector<int>>& result){
        
        // 基礎情況：如果目標為0，找到一個有效組合
        if (target == 0) {
            result.push_back(current);
            return;
        }
        for(int i=start;i<candidates.size();i++){
            // 剪枝：如果當前數字大於剩餘目標，後面的數字也不可能            
            if (candidates[i] > target) {
                break;
            }
            // 選擇當前數字
            current.push_back(candidates[i]);
            
            // 遞歸：注意這裡start仍為i，因為可以重複使用同一個數字
            backtrack(candidates, target - candidates[i], i, current, result);
            
            // 回溯：撤銷選擇
            current.pop_back();
        }
    }
};
```
---
###  <font color="c1ab0c">40. 回溯</font>

#### [題目：Combination Sum II](https://leetcode.com/problems/combination-sum-ii/description//)
邏輯同上題

```cpp=
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> cur;
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, cur, ans);
        return ans;
    }
    
    void backtrack(vector<int>& candidates, int target, 
                   int start, vector<int>& cur, vector<vector<int>>& ans) {
        
        if (target == 0) {
            ans.push_back(cur);
            return;
        }
        
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > target) break;
            
            //刪除重複
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;
            }
            
            cur.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, cur, ans);
            cur.pop_back();
        }
    }
};
```
---
###  <font color="FF5151">41. Cyclic Sort</font>

#### [題目： first-missing-positive](https://leetcode.com/problems/first-missing-positive/description/)
**演算法步驟：**

重新排列陣列：將每個正整數 i 放到索引 i-1 的位置

只考慮範圍在 [1, n] 內的數字
使用 while 迴圈確保每個數字都放到正確位置


尋找缺失的數字：遍歷陣列，找到第一個不等於 i+1 的位置

關鍵點：

時間複雜度：O(n) - 雖然有嵌套迴圈，但每個元素最多被移動一次
空間複雜度：O(1) - 只使用常數額外空間
交換條件：nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]

數字必須是正數且在有效範圍內
目標位置的數字不能已經是正確的數字（避免無限迴圈）



範例追蹤：
對於 [3,4,-1,1]：

1. 將 3 放到索引 2：[-1,4,3,1]
1. 將 4 放到索引 3：[-1,1,3,4]
1. 將 1 放到索引 0：[1,-1,3,4]
1. 檢查：索引 1 的值是 -1，不等於 2，所以答案是 2
```cpp=
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            // 數字 i 應該放在索引 i-1 的位置
            while(nums[i]>0&&nums[i]<=n&&nums[i]!=nums[nums[i]-1]){
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return n+1;
    }
};
```
---
###  <font color="FF5151">4２. 兩指針</font>

#### [題目： Trapping rain water](https://leetcode.com/problems/trapping-rain-water/)
太難了不知道怎麼解釋
[看別人的解](https://englishandcoding.pixnet.net/blog/post/31607785)
```cpp=
class Solution {
public:
    int trap(vector<int>& height) {
        int max_left=0,max_right=0;
        int i=0,j=height.size()-1,water=0;
        while(i<j){
            max_left=max(height[i],max_left);
            max_right=max(height[j],max_right);

            if(max_left<max_right){
                water+=min(max_left,max_right)-height[i];
                i++;
            }else{
                water+=min(max_left,max_right)-height[j];
                j--;
            }
        }
        return water;
    }
};
```
---
###  <font color="c1ab0c">43. 字串乘法(不能直接轉數字)</font>

#### [題目：multiply-strings](https://leetcode.com/problems/multiply-strings/description/)
核心思路
* 位置映射：對於 num1[i] 和 num2[j] 的乘積，結果會影響到位置 i+j 和 i+j+1
* 逐位相乘：從右到左遍歷兩個字符串，計算每一位的乘積
* 處理進位：將乘積加到對應位置，並處理進位

詳細步驟

    初始化：創建長度為 m+n 的結果數組（兩個數相乘最多產生 m+n 位）
雙重循環：

外層循環遍歷 num1（從右到左）
內層循環遍歷 num2（從右到左）


計算乘積：

mul = (num1[i] - '0') * (num2[j] - '0')
位置 p1 = i + j（高位），p2 = i + j + 1（低位）


處理進位：

    sum = mul + result[p2]（加上之前的結果）
    result[p2] = sum % 10（當前位）
    result[p1] += sum / 10（進位）

```cpp=

class Solution {
public:
    string multiply(string num1, string num2) {
        // 處理特殊情況
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        
        int m = num1.size();
        int n = num2.size();
        vector<int> ans(m + n, 0);
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int p1 = i + j;        // 高位位置
                int p2 = i + j + 1;    // 低位位置
                
                int sum = ans[p2] + mul;
                ans[p2] = sum % 10;     // 設置當前位
                ans[p1] += sum / 10;    // 累加進位到高位
            }
        }
        
        string result = "";
        for (int i = 0; i < ans.size(); i++) {
            // 跳過前導零
            if (!(result.empty() && ans[i] == 0)) {
                result += to_string(ans[i]);
            }
        }
        
        return result.empty() ? "0" : result;
    }
};
```
---
###  <font color="FF5151">44. dp</font>

#### [題目： wildcard-matching](https://leetcode.com/problems/wildcard-matching/description/)
動態規劃狀態定義：

dp[i][j] 表示字串 s 的前 i 個字符是否能匹配模式 p 的前 j 個字符


狀態轉移：

1. 如果 p[j-1] == '*'：
* 可以匹配空序列：dp[i][j] = dp[i][j-1]
* 可以匹配任何字符：dp[i][j] = dp[i-1][j]


2. 如果 p[j-1] == '?' 或 p[j-1] == s[i-1]：
* 字符匹配：dp[i][j] = dp[i-1][j-1]

邊界條件：

dp[0][0] = true（空字串匹配空模式）
處理模式開頭的連續 * 字符
```cpp=
class Solution {
public:
    bool isMatch(string s, string p) {
        //dp[i][j] 是指s的前i個字是否匹配p的前j模式
        vector<vector<bool>> dp(s.length()+1,vector<bool>(p.length()+1,false));
        //空字串匹配空模式
        dp[0][0]=true;
        //空字串匹配連續*
        for(int i=1;i<=p.length();i++){
            if(p[i-1]=='*'){
                dp[0][i]=dp[0][i-1];
            }
        }        
        for(int i=1;i<=s.length();i++){
            for(int j=1;j<=p.length();j++){
                if(p[j-1]=='*'){
                    dp[i][j]=dp[i-1][j]||dp[i][j-1];
                }else if(p[j-1]=='?'||p[j-1]==s[i-1]){
                    dp[i][j]=dp[i-1][j-1];
                }
            }
        }
        return dp[s.length()][p.length()];
    }
};
```
---
###  <font color="c1ab0c">45. 貪心</font>

#### [題目：Jump game II](https://leetcode.com/problems/jump-game-ii/description/)
這個算法的關鍵是理解「跳躍邊界」的概念：

currentEnd 代表當前跳躍次數下能到達的最遠位置
farthest 代表如果再跳一次能到達的最遠位置
當我們到達 currentEnd 時，必須進行下一次跳躍
```cpp=
class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        if(n<=1) return 0;
        int jump=0; //跳幾次
        int currentEnd=0; //目前可跳最遠
        int farthest=0; //下次跳最遠

        //不需要檢查最後一個，因為已經到了
        for(int i=0;i<n-1;i++){
            farthest=max(farthest,i+nums[i]);
            //如果到達目前可跳最遠
            if(i==currentEnd){
                jump++;
                currentEnd=farthest;
                //如果已經能到達最後一個位置就提前結束
                if(currentEnd>=n-1){
                    break;
                }
            }
        }
        return jump;
    }
};
```
---
###  <font color="c1ab0c">46. 回溯</font>

#### [題目：Permutations](https://leetcode.com/problems/permutations/description/)
遞歸情況：

* 遍歷所有數字
* 跳過已使用的數字
* 選擇未使用的數字，標記為已使用
* 遞歸生成剩餘位置的排列
* 回溯：撤銷選擇，標記為未使用
```cpp=
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<bool> used(nums.size(),false);
        vector<int> cur;
        backtrack(nums,cur,used,ans); 
        return ans;
    }
    void backtrack(vector<int>& nums, vector<int>& cur, 
                   vector<bool>& used, vector<vector<int>>& ans){
        //長度一樣加到結果
        if(cur.size()==nums.size()){
            ans.push_back(cur);
            return;
        }
        for(int i=0;i<nums.size();i++){
            //已用過就跳過
            if(used[i]) continue;

            cur.push_back(nums[i]);
            used[i]=true;
            backtrack(nums,cur,used,ans);
            //撤銷選擇
            cur.pop_back();
            used[i]=false;
        }
        return;
    }
};
```
---
###  <font color="c1ab0c">47. 回溯</font>

#### [題目：Permutations II](https://leetcode.com/problems/permutations-ii/description/)
邏輯同上題，但需要確保相同的數字照順序使用，才不會有重複。
```cpp=
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<bool> used(nums.size(),false);
        vector<int> cur;
        sort(nums.begin(),nums.end());
        backtrack(nums,cur,used,ans); 
        return ans;
    }
    void backtrack(vector<int>& nums, vector<int>& cur, 
                   vector<bool>& used, vector<vector<int>>& ans){
        //長度一樣加到結果
        if(cur.size()==nums.size()){
            ans.push_back(cur);
            return;
        }
        for(int i=0;i<nums.size();i++){
            //已用過就跳過
            if(used[i]) continue;
            
            // 如果當前元素與前一個元素相同，且前一個元素未被使用，則跳過
            // 這確保同一層級中相同的數字按順序使用，避免重複排列
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
                continue;
            }
            cur.push_back(nums[i]);
            used[i]=true;
            backtrack(nums,cur,used,ans);
            //撤銷選擇
            cur.pop_back();
            used[i]=false;
        }
        return;
    }
};
```
---
###  <font color="c1ab0c">48. 翻轉矩陣</font>

#### [題目：Rotate Image](https://leetcode.com/problems/rotate-image/description/)
先轉置再反轉每一行
```cpp=
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        // 步驟1：轉置矩陣 (沿主對角線翻轉)
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
        // 步驟2：反轉每一行
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
        return ;
    }
};
```
---
###  <font color="c1ab0c">49. 字串分組</font>

#### [題目：Group Anagrams](https://leetcode.com/problems/group-anagrams/description/)
原理： 對每個字串進行排序，重新排列字母的字串排序後會相同
步驟：

1. 對每個字串排序作為鍵值
1. 使用雜湊表 (hash map) 將具有相同排序鍵值的字串分組
1. 收集所有分組作為結果
```cpp=
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> groups;
        for(string str:strs){
            string key=str;
            sort(key.begin(),key.end());
            groups[key].push_back(str);
        }
        vector<vector<string>> ans;
        for(auto& a:groups){
            ans.push_back(a.second);
        }
        return ans;
    }
};
```
---
###  <font color="c1ab0c">50. 次方</font>

#### [題目：Pow(x, n)](https://leetcode.com/problems/powx-n/description/)
```cpp=
class Solution {
public:
    double myPow(double x, int n) {
        // 處理邊界情況
        if (n == 0) return 1.0;
        if (x == 0) return 0.0;
        if (x == 1) return 1.0;
        if (x == -1) return (n % 2 == 0) ? 1.0 : -1.0;
        
        // 將 n 轉換為 long long 以避免整數溢出
        long long longN = n;
        
        // 如果 n 是負數，將問題轉換為 1/x^(-n)
        if (longN < 0) {
            x = 1.0 / x;
            longN = -longN;
        }
        
        return fastPow(x, longN);
    }
    double fastPow(double x, long long n) {
        if (n == 0) return 1.0;
        
        double half = fastPow(x, n / 2);
        
        if (n % 2 == 0) {
            // n 是偶數: x^n = (x^(n/2))^2
            return half * half;
        } else {
            // n 是奇數: x^n = x * (x^(n/2))^2
            return x * half * half;
        }
    }
};
```
---
###  <font color="FF5151">51. 回溯</font>

#### [題目： N-Queens](https://leetcode.com/problems/n-queens/)
皇后可以攻擊同一行、同一列、同一對角線上的位置
* 對角線索引計算：
主對角線（左上到右下）：row - col + n - 1
副對角線（右上到左下）：row + col
回溯遞歸：

逐列嘗試放置皇后
檢查當前位置是否安全
如果安全，放置皇后並遞歸處理下一列
如果到達最後一列，記錄解決方案
回溯時移除皇后
```cpp=
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));

        //檢查攻擊
        vector<bool> col(n,false);
        vector<bool> diag1(2*n-1,false);//左上到右下
        vector<bool> diag2(2*n-1,false);//右上到左下
        backtrack(result, board, 0, n, col, diag1, diag2);
        return result;         
    }
    void backtrack(vector<vector<string>>& result, vector<string>& board, 
                   int row, int n, vector<bool>& cols, 
                   vector<bool>& diag1, vector<bool>& diag2){

        if(row==n){
            result.push_back(board);
            return ;
        }
        // 嘗試在當前列的每一行放置皇后
        for (int col = 0; col < n; col++) {
            // 計算對角線索引
            int d1 = row - col + n - 1;  // 主對角線索引
            int d2 = row + col;          // 副對角線索引
            
            // 檢查是否安全（沒有攻擊）
            if (cols[col] || diag1[d1] || diag2[d2]) {
                continue; // 這個位置不安全，嘗試下一個
            }
            
            // 放置皇后
            board[row][col] = 'Q';
            cols[col] = true;
            diag1[d1] = true;
            diag2[d2] = true;
            
            // 遞歸處理下一列
            backtrack(result, board, row + 1, n, cols, diag1, diag2);
            
            // 回溯：移除皇后
            board[row][col] = '.';
            cols[col] = false;
            diag1[d1] = false;
            diag2[d2] = false;
        }
    }
};
```
---
###  <font color="FF5151">52. 回溯</font>

#### [題目： N-Queens II](https://leetcode.com/problems/n-queens-ii/description/)
同上題，只是改成傳數量而已
```cpp=
class Solution {
public:
    int totalNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));

        //檢查攻擊
        vector<bool> col(n,false);
        vector<bool> diag1(2*n-1,false);//左上到右下
        vector<bool> diag2(2*n-1,false);//右上到左下
        backtrack(result, board, 0, n, col, diag1, diag2);
        return result.size(); 
    }
    void backtrack(vector<vector<string>>& result, vector<string>& board, 
                   int row, int n, vector<bool>& cols, 
                   vector<bool>& diag1, vector<bool>& diag2){

        if(row==n){
            result.push_back(board);
            return ;
        }
        // 嘗試在當前列的每一行放置皇后
        for (int col = 0; col < n; col++) {
            // 計算對角線索引
            int d1 = row - col + n - 1;  // 主對角線索引
            int d2 = row + col;          // 副對角線索引
            
            // 檢查是否安全（沒有攻擊）
            if (cols[col] || diag1[d1] || diag2[d2]) {
                continue; // 這個位置不安全，嘗試下一個
            }
            
            // 放置皇后
            board[row][col] = 'Q';
            cols[col] = true;
            diag1[d1] = true;
            diag2[d2] = true;
            
            // 遞歸處理下一列
            backtrack(result, board, row + 1, n, cols, diag1, diag2);
            
            // 回溯：移除皇后
            board[row][col] = '.';
            cols[col] = false;
            diag1[d1] = false;
            diag2[d2] = false;
        }
    }
};
```
---
###  <font color="c1ab0c">53. dp</font>

#### [題目：Maximum Subarray](https://leetcode.com/problems/maximum-subarray/description/)
核心思想：
對於每個位置 i，我們決定是否要包含前面的子陣列：

如果 currentSum < 0，則從當前元素重新開始
否則，將當前元素加到現有的子陣列中
```cpp=
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int curSum=nums[0],ans=nums[0];
        for(int i=1;i<nums.size();i++){
            curSum=max(nums[i],curSum+nums[i]);
            ans=max(ans,curSum);
        }
        return ans;
    }
};
```
---
###  <font color="c1ab0c">54. 順時鐘遍歷矩陣</font>

#### [題目：Spiral Matrix](https://leetcode.com/problems/spiral-matrix/description//)
從左到右遍歷上邊界，然後上邊界下移
從上到下遍歷右邊界，然後右邊界左移
從右到左遍歷下邊界，然後下邊界上移
從下到上遍歷左邊界，然後左邊界右移

重要細節：

在步驟3和4之前要檢查是否還有行/列需要遍歷
避免在奇數維度矩陣中重複遍歷
```cpp=
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if (matrix.empty() || matrix[0].empty()) {
            return ans;
        }
        int top=0,down=matrix.size()-1;
        int left=0,right=matrix[0].size()-1;
        
        while(top<=down&&left<=right){
            //右
            for(int j=left;j<=right;j++){
                ans.push_back(matrix[top][j]);
            }
            top++;//上邊界下移

            //下
            for(int i=top;i<=down;i++){
                ans.push_back(matrix[i][right]);
            }
            right--;
            //右邊界左移

            //左
            if(top<=down){
                for(int j=right;j>=left;j--){
                    ans.push_back(matrix[down][j]);
                }
                down--;//下邊界上移
            }

            //上
            if(left<=right){
                for(int i=down;i>=top;i--){
                    ans.push_back(matrix[i][left]);
                }
                left++;
                //左邊界右移
            }
            
        }
        return ans;
    }
};
```
---
###  <font color="c1ab0c">55. 是否能到達最後一格</font>

#### [題目：Jump Game](https://leetcode.com/problems/jump-game/description/)

```cpp=
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int curReach=0;
        for(int i=0;i<nums.size();i++){
            if(curReach>=i) curReach=max(curReach,i+nums[i]);
        }
        if(curReach>=nums.size()-1) return true;
        else return false;
    }
};
```
---
###  <font color="c1ab0c">56. 合併重疊區間</font>

#### [題目：Merge Intervals](https://leetcode.com/problems/merge-intervals/description/)
- 兩種情況
  - 如果當前區間的結束點 < 新區間的起始點
說明兩個區間不重疊，可以把當前區間加入結果
然後開始處理新的區間
  - 如果兩個區間重疊，就合併它們
左邊界不變（因為已經排序，新區間的起始點 ≥ 當前起始點）
右邊界取較大值
```cpp=
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, 
                const vector<int>& b) {
            return a[0] < b[0]; // 升序排列
        });
        vector<vector<int>> ans;
        int curMin=intervals[0][0],curMax=intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            //如果目前最大比intervals[i]的起始還小，就往下格存
            if(curMax<intervals[i][0]){
                ans.push_back({curMin,curMax});
                curMin=intervals[i][0];
                curMax=intervals[i][1];
            }
            //起始在目前範圍內，但結尾較大
            if(curMax<intervals[i][1]){
                curMax=intervals[i][1];
            }
        }
        //最後一個
        ans.push_back({curMin,curMax});
        return ans;
    }
};
```
---
###  <font color="c1ab0c">57. 插入區間</font>

#### [題目：Insert Interval](https://leetcode.com/problems/insert-interval/description/)
分三階段處理
```cpp=
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& 
                               newInterval) {
        
        vector<vector<int>> ans;
        // 處理空數組的情況
        if(intervals.size() == 0) {
            ans.push_back(newInterval);
            return ans;
        }
        int i=0;
        // 第一階段：添加所有在 newInterval 之前且不重疊的區間
        while(i < intervals.size() && intervals[i][1] < newInterval[0]) {
            ans.push_back(intervals[i]);
            i++;
        }
        
        // 第二階段：合併所有與 newInterval 重疊的區間
        int mergeStart = newInterval[0];
        int mergeEnd = newInterval[1];
        
        while(i < intervals.size() && intervals[i][0] <= newInterval[1]) {
            mergeStart = min(mergeStart, intervals[i][0]);
            mergeEnd = max(mergeEnd, intervals[i][1]);
            i++;
        }
        
        ans.push_back({mergeStart, mergeEnd});
        
        // 第三階段：添加所有在 newInterval 之後且不重疊的區間
        while(i < intervals.size()) {
            ans.push_back(intervals[i]);
            i++;
        }
        return ans;
    }
};
```
---
###  <font color="green">58. 判斷最後一個字長度</font>

#### [題目：Length of Last Word](https://leetcode.com/problems/length-of-last-word/description/)
從後面數回來，記得先跳過最後的0
```cpp=
class Solution {
public:
    int lengthOfLastWord(string s) {
        int cnt=0;
        //跳過倒數一開始就遇到的0
        int start=s.length()-1;
        while(s[start]==' '){
            start--;
        }

        for(int i=start;i>=0;i--){
            if(s[i]==' ') break;
            cnt++;
        }
        return cnt;
    }
};
```
---
###  <font color="c1ab0c">59. 逆時鐘擺矩陣</font>

#### [題目：Spiral Matrix II](https://leetcode.com/problems/spiral-matrix-ii/description/)
邏輯同54題，cnt是現在要放的值
```cpp=
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n,vector<int>(n,0));
        int left=0,right=n-1;
        int top=0,down=n-1;
        int cnt=1;
        while(left<=right && top<=down){
            //右
            for(int j=left;j<=right;j++){
                ans[top][j]=cnt;
                cnt++;
            }
            top++;

            //下
            for(int i=top;i<=down;i++){
                ans[i][right]=cnt;
                cnt++;
            }
            right--;

            //左
            if(top<=down){
                for(int j=right;j>=left;j--){
                ans[down][j]=cnt;
                cnt++;
                }
                down--;
            }
            
            //上
            if(left<=right){
                for(int i=down;i>=top;i--){
                    ans[i][left]=cnt;
                    cnt++;
                }
                left++;
            }
        }
        return ans;
    }
};
```
---
###  <font color="FF5151">60. 排列序列</font>

#### [題目： Permutation Sequence](https://leetcode.com/problems/permutation-sequence/description/)
分組思想：第一位數字確定後，剩下的位置有 (n-1)! 種排列
數學計算：通過除法確定當前位置選哪個數字，通過取餘更新剩餘的k值
~~~~
所有排列：123, 132, 213, 231, 312, 321
要找第3個：213 (n=3,k=3)

1. 第1位：k=2, 每組大小=2!, 索引=2/2=1, 選numbers[1]=2
2. 第2位：k=0, 每組大小=1!, 索引=0/1=0, 選numbers[0]=1  
3. 第3位：k=0, 每組大小=0!, 索引=0/1=0, 選numbers[0]=3
結果：213
~~~~
```cpp=
class Solution {
public:
    string getPermutation(int n, int k) {
        // 預計算階乘值
        vector<int> factorial(n);
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i-1] * i;
        }
        
        // 建立可用數字列表 [1, 2, 3, ..., n]
        vector<int> numbers;
        for (int i = 1; i <= n; i++) {
            numbers.push_back(i);
        }
        
        string result = "";
        k--; // 轉換為0-based index
        
        // 逐位確定每個位置的數字
        for (int i = 0; i < n; i++) {
            // 計算當前位置應該選擇第幾個數字
            int index = k / factorial[n-1-i];
            
            // 將選中的數字加入結果
            result += to_string(numbers[index]);
            
            // 從可用數字中移除已選的數字
            numbers.erase(numbers.begin() + index);
            
            // 更新k值
            k %= factorial[n-1-i];
        }
        
        return result;
    }
};
```
---
###  <font color="c1ab0c">61. 逆時鐘擺矩陣</font>

#### [題目：Rotate List](https://leetcode.com/problems/rotate-list/description/)

```cpp=
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        // 邊界情況處理
        if (!head || !head->next || k == 0) {
            return head;
        }
        
        // 1. 計算鏈表長度並找到尾節點
        ListNode* tail = head;
        int length = 1;
        while (tail->next) {
            tail = tail->next;
            length++;
        }
        
        // 2. 計算實際需要旋轉的步數
        k = k % length;
        if (k == 0) {
            return head; // 不需要旋轉
        }
        
        // 3. 找到新的尾節點（從頭開始第 length-k 個節點）
        ListNode* newTail = head;
        for (int i = 0; i < length - k - 1; i++) {
            newTail = newTail->next;
        }
        
        // 4. 新的頭節點是新尾節點的下一個
        ListNode* newHead = newTail->next;
        
        // 5. 斷開新尾節點的連接
        newTail->next = nullptr;
        
        // 6. 將原來的尾節點連接到原來的頭節點
        tail->next = head;
        
        return newHead;
    }
};
```
---
###  <font color="c1ab0c">62. dp</font>

#### [題目：Unique Paths](https://leetcode.com/problems/unique-paths/description/)
邊界只能直走因此都是1，其他位置都只可能從上方或左方到達(=兩者和)
```cpp=
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        return dp[m-1][n-1];
    }
};
```
---
###  <font color="c1ab0c">63. dp</font>

#### [題目：Unique Paths II](https://leetcode.com/problems/unique-paths-ii/description/)
```cpp=
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        // 特殊情況：起點或終點是障礙物
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }
        
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // === 邊界處理 ===
        // 第一列：只要遇到障礙物，後面都無法到達
        dp[0][0] = 1;
        for(int j = 1; j < n; j++) {
            if(obstacleGrid[0][j] == 1) {
                dp[0][j] = 0;  // 障礙物，無法到達
            } else {
                dp[0][j] = dp[0][j-1];  // 繼承前一個位置的值
            }
        }
        
        // 第一行：只要遇到障礙物，下面都無法到達
        for(int i = 1; i < m; i++) {
            if(obstacleGrid[i][0] == 1) {
                dp[i][0] = 0;  // 障礙物，無法到達
            } else {
                dp[i][0] = dp[i-1][0];  // 繼承上一個位置的值
            }
        }
        
        // === 狀態轉移 ===
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;  // 障礙物，路徑數為 0
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        
        return dp[m-1][n-1];
    }
};
```
---
###  <font color="c1ab0c">64. dp</font>

#### [題目：Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/description/)
```cpp=
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // === 邊界處理 ===
        // 第一列
        dp[0][0] = grid[0][0];
        for(int j = 1; j < n; j++) {
            dp[0][j]=dp[0][j-1]+grid[0][j];
        }
        
        // 第一行
        for(int i = 1; i < m; i++) {
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        
        // === 狀態轉移 ===
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                int prevMin=min(dp[i-1][j],dp[i][j-1]);
                dp[i][j]=prevMin+grid[i][j];
            }
        }
        
        return dp[m-1][n-1];
    }
};
```
---
###  <font color="FF5151">65. 狀態機</font>

#### [題目： Valid Number](https://leetcode.com/problems/valid-number/description/)

```cpp=
class Solution {
public:
    bool isNumber(string s) {
        enum State {
            START,          // 開始狀態
            SIGN,           // 遇到正負號
            DIGIT,          // 遇到數字
            DOT,            // 遇到小數點
            DIGIT_AFTER_DOT, // 小數點後的數字
            EXP,            // 遇到指數符號
            EXP_SIGN,       // 指數後的正負號
            EXP_DIGIT       // 指數後的數字
        };
        
        State state = START;
        
        for (char c : s) {
            switch (state) {
                case START:
                    if (c == '+' || c == '-') {
                        state = SIGN;
                    } else if (isdigit(c)) {
                        state = DIGIT;
                    } else if (c == '.') {
                        state = DOT;
                    } else {
                        return false;
                    }
                    break;
                    
                case SIGN:
                    if (isdigit(c)) {
                        state = DIGIT;
                    } else if (c == '.') {
                        state = DOT;
                    } else {
                        return false;
                    }
                    break;
                    
                case DIGIT:
                    if (isdigit(c)) {
                        state = DIGIT;
                    } else if (c == '.') {
                        state = DIGIT_AFTER_DOT;
                    } else if (c == 'e' || c == 'E') {
                        state = EXP;
                    } else {
                        return false;
                    }
                    break;
                    
                case DOT:
                    if (isdigit(c)) {
                        state = DIGIT_AFTER_DOT;
                    } else {
                        return false;
                    }
                    break;
                    
                case DIGIT_AFTER_DOT:
                    if (isdigit(c)) {
                        state = DIGIT_AFTER_DOT;
                    } else if (c == 'e' || c == 'E') {
                        state = EXP;
                    } else {
                        return false;
                    }
                    break;
                    
                case EXP:
                    if (c == '+' || c == '-') {
                        state = EXP_SIGN;
                    } else if (isdigit(c)) {
                        state = EXP_DIGIT;
                    } else {
                        return false;
                    }
                    break;
                    
                case EXP_SIGN:
                    if (isdigit(c)) {
                        state = EXP_DIGIT;
                    } else {
                        return false;
                    }
                    break;
                    
                case EXP_DIGIT:
                    if (isdigit(c)) {
                        state = EXP_DIGIT;
                    } else {
                        return false;
                    }
                    break;
            }
        }
        
        // 檢查最終狀態是否為有效狀態
        return state == DIGIT || state == DIGIT_AFTER_DOT || state == EXP_DIGIT;
    }
};
```
---
###  <font color="green">66.手動加法</font>

#### [題目：Add Binary](https://leetcode.com/problems/add-binary/)
從最後一位往前處理進位
```cpp=
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i=digits.size()-1;i>=0;i--){
            // 如果當前位小於 9，直接加 1 並返回
            if(digits[i]!=9){
                digits[i]++;
                return digits;
            }else{
                // 如果當前位是 9，設為 0 並繼續處理進位
                digits[i]=0;
            }
        }
        // 如果所有位都是 9，需要在前面加一個 1
        digits.insert(digits.begin(),1);
        return digits;
    }
};
```
---
###  <font color="green">67.二進制加法</font>

#### [題目：Add Binary](https://leetcode.com/problems/add-binary/description/)
從最後一位往前處理進位
```cpp=
class Solution {
public:
    string addBinary(string a, string b) {
        int i=a.length()-1;
        int j=b.length()-1;
        string ans="";
        int carry=0;

        while(i>=0 || j>=0 || carry){
            int sum=carry;
            // 加上 a 的當前位
            if (i >= 0) {
                sum += a[i] - '0';
                i--;
            }
            
            // 加上 b 的當前位
            if (j >= 0) {
                sum += b[j] - '0';
                j--;
            }

            // 計算當前位的結果和進位
            ans = char(sum % 2 + '0') + ans;
            carry = sum / 2;
        }
        return ans;
    }
};
```
---
###  <font color="FF5151">68. 文本格式化</font>
~~屎題~~
#### [題目： Text Justification](https://leetcode.com/problems/text-justification/description/)

```cpp=
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;
        int i = 0;
        
        while (i < words.size()) {
            // 找到當前行能容納的單詞
            vector<string> currentLine;
            int totalLength = 0;
            
            while (i < words.size()) {
                // 檢查是否能加入下一個單詞
                int neededLength = totalLength + words[i].length() +
                    currentLine.size();
                
                if (neededLength <= maxWidth) {
                    currentLine.push_back(words[i]);
                    totalLength += words[i].length();
                    i++;
                } else {
                    break;
                }
            }
            
            // 格式化當前行
            bool isLastLine = (i == words.size());
            string line = formatLine(currentLine, totalLength, maxWidth,
                                     isLastLine);
            result.push_back(line);
        }
        
        return result;
    }
    
private:
    string formatLine(vector<string>& words, int totalLength, int maxWidth,
                      bool isLastLine) {
        if (words.size() == 1 || isLastLine) {
            // 單個單詞或最後一行：左對齊
            return leftJustify(words, maxWidth);
        } else {
            // 多個單詞：完全對齊
            return fullJustifyLine(words, totalLength, maxWidth);
        }
    }
    
    // 左對齊：單詞間只有一個空格，末尾補空格
    string leftJustify(vector<string>& words, int maxWidth) {
        string result = "";
        for (int i = 0; i < words.size(); i++) {
            result += words[i];
            if (i < words.size() - 1) {
                result += " ";
            }
        }
        
        // 末尾補空格
        while (result.length() < maxWidth) {
            result += " ";
        }
        
        return result;
    }
    
    // 完全對齊：均勻分配空格
    string fullJustifyLine(vector<string>& words, int totalLength, int maxWidth){
        int gaps = words.size() - 1;  // 單詞間的空隙數
        int totalSpaces = maxWidth - totalLength;  // 需要分配的總空格數
        int extraSpaces = totalSpaces % gaps;  // 需要額外分配的空格數
        int avgSpaces = totalSpaces / gaps;    // 每個空隙的平均空格數
        
        string result = "";
        
        for (int i = 0; i < words.size(); i++) {
            result += words[i];
            
            if (i < words.size() - 1) {  // 不是最後一個單詞
                // 計算當前空隙應該放多少空格
                int spacesForThisGap = avgSpaces;
                if (extraSpaces > 0) {
                    spacesForThisGap++;  // 左邊的空隙多分配一個空格
                    extraSpaces--;
                }
                
                // 添加空格
                for (int j = 0; j < spacesForThisGap; j++) {
                    result += " ";
                }
            }
        }
        
        return result;
    }
};
```
---
###  <font color="green">69. 開根號</font>

#### [題目：Sqrt(x)](https://leetcode.com/problems/sqrtx/description/)
```cpp=
class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        
        int left = 1, right = x;
        int result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //本來是mid * mid <= x
            // 使用除法避免溢位：mid <= x / mid
            if (mid <= x / mid) {
                result = mid;  // 記錄可能的答案
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
};
```
---
###  <font color="green">70. 爬樓梯</font>

#### [題目：Climbing Stairs](https://leetcode.com/problems/climbing-stairs/description/)
費氏數列的概念
```cpp=
class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        
        vector<int> memo(n+1, 0);
        memo[1] = 1;
        memo[2] = 2;
        
        for(int i = 3; i <= n; i++) {
            memo[i] = memo[i-1] + memo[i-2];
        }
        
        return memo[n];
    }
};
```
---
###  <font color="c1ab0c">71. stack</font>

#### [題目：Simplify Path](https://leetcode.com/problems/simplify-path/description/)
```cpp=
class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stack;
        string current = "";
        
        // 在路徑末尾加一個'/'，方便處理最後一個目錄
        path += '/';
        
        for (int i = 0; i < path.length(); i++) {
            if (path[i] == '/') {
                if (current == "..") {
                    // 返回上一級目錄
                    if (!stack.empty()) {
                        stack.pop_back();
                    }
                } else if (current != "" && current != ".") {
                    // 普通目錄名，加入堆疊
                    stack.push_back(current);
                }
                current = ""; // 重置當前目錄名
            } else {
                current += path[i];
            }
        }
        
        // 構建結果
        string result = "";
        for (const string& dir : stack) {
            result += "/" + dir;
        }
        
        return result.empty() ? "/" : result;
    }
};
```
---
###  <font color="c1ab0c">72. dp</font>

#### [題目：Edit Distance](https://leetcode.com/problems/edit-distance/description/)
```cpp=
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();

        //dp[i][j]表示word1[0...i-1]變成word2[0...j-1]最少步驟數
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i=0;i<=m;i++){
            dp[i][0]=i; //變成空字串需刪除i次
        }
        for(int j=0;j<=n;j++){
            dp[0][j]=j; //插入j次
        }

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i][j]=dp[i-1][j-1];//不需操作
                }else {
                    // 字符不同，選擇最小的操作數
                    dp[i][j] = 1 + min({
                        dp[i-1][j],     // 刪除 word1[i-1]
                        dp[i][j-1],     // 插入 word2[j-1]
                        dp[i-1][j-1]    // 替換 word1[i-1] 為 word2[j-1]
                    });
                }
                
            }
        }
        return dp[m][n];
    }
};
```
---
###  <font color="c1ab0c">73. 矩陣</font>

#### [題目：Set Matrix Zeroes](https://leetcode.com/problems/set-matrix-zeroes/)
用第一行和第一列紀錄是否那行/列變0
需額外處理第一行和第一列本身
```cpp=
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        // 用第一行和第一列作為標記
        // 但需要額外變量記錄第一行和第一列本身是否有0
        bool firstRowZero = false;
        bool firstColZero = false;
        //檢查第一行有沒有0
        for(int i=0;i<m;i++){
            if(matrix[i][0]==0){
                firstColZero=true;
            }
        }
        //檢查第一列有沒有0
        for(int j=0;j<n;j++){
            if(matrix[0][j]==0){
                firstRowZero=true;
            }
        }
        // 用第一行和第一列標記其他位置的0
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        //根據標記設置0（從第二行第二列開始）
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[0][j]==0||matrix[i][0]==0){
                    matrix[i][j]=0;
                }
            }
        }
        //處理第一行
        for(int i=0;i<m;i++){
            if(firstColZero){
                matrix[i][0]=0;
            }
        }
        //處理第一列
        for(int j=0;j<n;j++){
            if(firstRowZero){
                matrix[0][j]=0;
            }
        }
        return;
    }
};
```
---
###  <font color="c1ab0c">74. 矩陣</font>

#### [題目：Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)
先找可能在哪列，在遍歷這列看有沒有在裡面
```cpp=
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size();
        int n=matrix[0].size();
        int row=1;
        //先找出在哪列
        for(;row<m;row++){
            if(matrix[row][0]>target) break;
        }    
        //在matrix[row-1]這列
        for(int j=0;j<n;j++){
            if(matrix[row-1][j]==target) return true;
        }
        //不在陣列裡
        return false;
    }
};
```
---
###  <font color="c1ab0c">75. 矩陣</font>

#### [題目：Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)
先統計在填入
```cpp=
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count0 = 0, count1 = 0, count2 = 0;
        
        // 統計每種顏色的數量
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 0) count0++;
            else if(nums[i] == 1) count1++;
            else count2++;
        }
        
        // 按順序填充數組
        int idx = 0;
        for(int i = 0; i < count0; i++) nums[idx++] = 0;
        for(int i = 0; i < count1; i++) nums[idx++] = 1;
        for(int i = 0; i < count2; i++) nums[idx++] = 2;
    }
};
```
---
###  <font color="FF5151">76. 雙指針</font>
#### [題目： Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/description/)

```cpp=
class Solution {
public:
    string minWindow(string s, string t) {
        if(s.empty()||t.empty()) return"";
        //統計t的字
        unordered_map<char,int> tCount;
        for(char c:t){
            tCount[c]++;
        }    
        int required = tCount.size(); // t 中不重複字符的數量
        int formed = 0; // 當前窗口中滿足頻率要求的不重複字符數量
        // 窗口中字符的計數
        unordered_map<char, int> windowCount;
        // 記錄最小窗口的信息
        int minLen = INT_MAX;
        int minLeft = 0;
        // 左右指針
        int l = 0, r = 0;
        while(r<s.length()){
            // 將右指針的字符加入窗口
            char c = s[r];
            windowCount[c]++;
            
            // 如果當前字符的頻率達到了 t 中的要求，則 formed 加 1
            if (tCount.count(c) && windowCount[c] == tCount[c]) {
                formed++;
            }

            // 嘗試收縮窗口，直到它不再滿足條件
            while (l <= r && formed == required) {
                // 更新最小窗口
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    minLeft = l;
                }
                
                // 將左指針的字符移出窗口
                char leftChar = s[l];
                windowCount[leftChar]--;
                if (tCount.count(leftChar) && 
                    windowCount[leftChar] < tCount[leftChar]) {
                    formed--;
                }
                
                l++; // 左指針向右移動
            }
            r++;
        }
        return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);

    }
};
```
---
###  <font color="c1ab0c">77. 回溯</font>

#### [題目：Combination](https://leetcode.com/problems/combinations/)
回溯法（Backtracking）
- 核心思想：

  - 使用遞歸的方式逐步構建組合
每次選擇一個數字，然後遞歸處理剩餘的選擇
當組合大小達到 k 時，將其加入結果
```cpp=
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> cur;
        backtrack(ans,cur,n,k,1);
        return ans;
    }
    void backtrack(vector<vector<int>> &ans,vector<int> &cur,int n,int k,int start){
        // 基本情況：如果當前組合的大小等於 k，加入結果       
        if(cur.size()==k){
            ans.push_back(cur);
            return;
        }
        // 從 start 開始遍歷到 n
        for(int i=start;i<=n;i++){
            // 選擇當前數字
            cur.push_back(i);
            // 遞歸處理下一個位置，注意 start 變為 i + 1
            backtrack(ans,cur,n,k,i+1);
            // 回溯：移除當前數字
            cur.pop_back();
        }
    }
};
```
---
###  <font color="c1ab0c">78. 回溯</font>

#### [題目：Subsets](https://leetcode.com/problems/subsets/description/)
對於每個元素，我們有兩種選擇：包含或不包含
```cpp=
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> cur;
        backtrack(nums,ans,cur,0);   
        return ans;     
    }
    void backtrack(vector<int>& nums,vector<vector<int>> &ans,
                   vector<int> &cur,int start){
        ans.push_back(cur);
        for(int i=start;i<nums.size();i++){
            cur.push_back(nums[i]);
            backtrack(nums,ans,cur,i+1);
            cur.pop_back(); 
        }
    }
};
```
---
###  <font color="c1ab0c">79. 回溯</font>
#### [題目：Subsets](https://leetcode.com/problems/subsets/description/)
每個位子都試試看當開頭往四邊找
```cpp=
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty() || word.empty()) {
            return false;
        }
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(cal(board,word,i,j,0)) return true;
            }
        }
        return false;
    }
    bool cal(vector<vector<char>>& board, string word,int i,int j,int index){
        // 先檢查邊界
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
            return false;
        }
        
        // 檢查當前字符是否匹配
        if (board[i][j] != word[index]) {
            return false;
        }
        
        // 終止條件
        if (index == word.length() - 1) {
            return true;
        }
        
        // 防止重複使用同一個格子
        char temp = board[i][j];
        board[i][j] = '#';  // 標記已使用
        
        // 四個方向搜索
        bool found = cal(board, word, i + 1, j, index + 1) ||  // 向下
                     cal(board, word, i - 1, j, index + 1) ||  // 向上
                     cal(board, word, i, j + 1, index + 1) ||  // 向右
                     cal(board, word, i, j - 1, index + 1);    // 向左
        
        // 回溯
        board[i][j] = temp;
        
        return found;
    }
};
```
---
###  <font color="c1ab0c">80. 雙指針</font>
#### [題目：Remove Duplicates from Sorted Array II](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/)
因為可以重複兩次，所以從第三格開始檢查
```cpp=
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 2) {
            return nums.size();
        }
       int ans=2; //結果組的目前位置，前兩個位置一定有
       for(int i=2;i<nums.size();i++){
            //檢查是否重複超過兩次
            if(nums[i]!=nums[ans-2]){
                nums[ans]=nums[i];
                ans++;
            }
       }
       return ans;
    }
};
```
---
###  <font color="c1ab0c">81. 二分搜</font>
#### [題目：Search in Rotated Sorted Array II](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/)
```cpp=
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid = left + (right - left) / 2;
            if(nums[mid]==target) return true;
            else if(nums[mid]>target) right=mid-1;
            else left=mid+1;
        }
        return false;        
    }
};
```
---