# 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;
}
};
```
---
Sign in with Wallet
Connect another wallet