# Medium 1
###### tags: `LeetCode`
https://leetcode.com/LiChenWei/

### 2. Add Two Numbers
:::warning
將兩個Linked list數值相加，考慮進位和signed integer

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
:::

**思路**:
- 先遍歷兩個Linked list，並將值相加後存為矩陣
- 若總和大於10做進位處理
- 若最後一位仍大於10，則分配新的記憶體空間(新節點)並做進位處理

/*
Runtime: 15 ms, faster than 81.59% of C online submissions for Add Two Numbers.
Memory Usage: 8 MB, less than 6.71% of C online submissions for Add Two Numbers.
*/
#define MAX(a, b) ((a) > (b) ? (a) : (b))
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int ret[102] = {0};
    int count = 0, max = 0;
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* result = temp;
    while (l1 || l2)
    {
        if(l1){
            ret[count] += l1->val;
            l1 = l1->next;
        }

        if(l2){
            ret[count] += l2->val;
            l2 = l2->next;
        }
        
        // 在此處理
        if(ret[count] >= 10){
            ret[count] -= 10;
            ret[count+1]+= 1;
        }

        temp->next = (struct ListNode*)malloc(sizeof(struct ListNode)); //理論最後一位值
        temp->val = ret[count];
        if(l1 || l2)temp = temp->next;
        count++;
        max++;
    }

    if(ret[max] == 1){
        temp->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp = temp->next;
        temp->val = 1;
        temp->next = NULL;
    }else{
        temp->next = NULL;
    }
    
    return result;
}

### 5. Longest Palindromic Substring

:::warning
找字串中的最長回文

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
:::

**思路**
- Brute force解一定會超時
- 使用 dp 矩陣紀錄已經確認過的字串是否回文
- i 由後至前，j 則遍歷i~結尾
- 若前後相等且[i+1][j-1]為true，則該[i][j]為true，則比較最大值並記錄


/*
Runtime: 444 ms, faster than 15.86% of C online submissions for Longest Palindromic Substring.
Memory Usage: 118.5 MB, less than 5.07% of C online submissions for Longest Palindromic Substring.
*/
char * longestPalindrome(char * s){
    int n = strlen(s);
    int max_length = 1;
    int x = 0, y = 0;

    // 初始化dp矩陣
    bool** dp = (bool**)malloc(sizeof(bool*) * n);
    for(int i = 0 ; i < n ; i++){
        dp[i] = (bool*)malloc(sizeof(bool) * n);
        memset(dp[i],false,n);
    }
    

    // 確認字串s中i~j的值是否為回文
    // 是則紀錄並比較最大長度
    for(int i = n - 1 ; i >= 0 ; i--){
        for(int j = i ; j <= n - 1 ; j++){
            if(i == j)dp[i][j] = true;
            else if(s[i] == s[j]){
                if(j - i == 1)
                    dp[i][j] = true;         // 相鄰字串一定為回文
                else
                    dp[i][j] = dp[i+1][j-1]; // 若非相鄰則dp檢查
            }

            if(dp[i][j] && j - i >= max_length){
                max_length = j - i + 1;
                x = i;
                y = j;
            }
        }
    }    

    // 分配記憶體以回傳結果
    char* ret = (char*)malloc(sizeof(char) * (max_length + 1));
    memcpy(ret, s+x, max_length);
    ret[max_length] = '\0';
    return ret;
}

### 7. Reverse Integer
:::warning
輸入整數，反轉該整數

Input: 123
Output: 321

Input: x = -123
Output: -321
:::
**思路**
- 注意 INT32_MAX 和 INT32_MIN
- 使用 long long 整數(8 bytes)來儲存值
- 最後檢查是否超過整數範圍 INT32_MAX & INT32_MIN

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Reverse Integer.
Memory Usage: 5.8 MB, less than 9.72% of C online submissions for Reverse Integer.
*/
int reverse(int x){
    if(x == INT32_MIN || x == INT32_MAX)return 0;
    long long ret = 0;
    int count = 0;
    int temp = (x >= 0) ? x : -x;
    while (temp >= 1)
    {
        count++;
        temp /= 10;
    }

    temp = (x >= 0) ? x : -x;
    while (temp >= 1)
    {
        ret += (temp % 10)*pow(10, count - 1);
        temp /= 10;
        count--;
    }

    if(ret > INT32_MAX || ret < INT32_MIN)return 0;
    return ((x >= 0)?(int)ret:-(int)ret);
}

---
**思路**
- 試圖減少空間複雜度(但沒改善)
- 透過每次迴圈提前檢查overflow條件來實作
- INT32_MAX = 2147483647 INT32_MIN = −2147483648

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Reverse Integer.
Memory Usage: 5.8 MB, less than 9.72% of C online submissions for Reverse Integer.
*/
int reverse(int x){
    int ret = 0;  //輸出結果
    while (x != 0)
    {
        if(ret > INT32_MAX/10 || ret < INT32_MIN/10)return 0;
        else if(ret == INT32_MAX/10 || ret == INT32_MIN/10){
            if(ret%10 == 7 || ret %10 < -8)return 0;
        }
        ret = ret*10 + x%10;

        x /= 10;
    }
    return ret;
}

### 8. String to Integer (atoi)

:::danger
根據以下規則

Input: s = "42"
Output: 42

Input: s = " -42"
Output: -42

Input: s = "4193 with words"
Output: 4193
:::

**思路**
- 以 ret 矩陣存入數值
- 以 num 矩陣紀錄符號
- 注意每個整數是否超過其大小
- 注意 testcase 的未說明邊界條件

int myAtoi(char * s){
    int left = 0;
    long long temp = 0;   //累積的值
    long long ret[200] = {0};
    int count = 0;

    int num[200] = {0};
    int sign = 0;

    int flag = 0,flag_dot = 0;
    for(int i = 0; i < strlen(s) ; i++){
        char c = s[i];
        if(c == ' ')continue;

        if(c == '.')flag_dot = 1;

        // 是個數字
        if((int)c >= 48 && (int)c <= 57 && flag_dot == 0){
            temp = temp*10 + (int)c - 48;
            flag = 1;
            if(left == 0)num[sign++] = 1;
        }else if(flag == 1 && flag_dot == 0){
            ret[count++] = temp;
            printf("%d %d\n",count,temp);
            temp = 0;
            flag = 0;
        }

        if(flag == 1 && i == strlen(s) - 1)ret[count++] = temp;

        if(c == '-'){
            if (!isdigit(s[i+1]))
                return 0;
            num[sign] = -1;
            sign++;
            flag_dot = 0;
        }else if(c == '+'){
            if (!isdigit(s[i+1]))
                return 0;
            num[sign] = 1;
            sign++;
            flag_dot = 0;
        }

        left = 1;
    }

    for(int i=0;i<10;i++)printf("%4d ",ret[i]);
    printf("\n");
    for(int i=0;i<10;i++)printf("%4d ",num[i]);
    printf("\n");

    long long sum = 0;
    for(int i = 0 ; i < count ; i++){
        if(num[i] == 0)return 0;

        if( ret[i] * num[i] > INT32_MAX){
            sum += INT32_MAX;
        }else if(ret[i] * num[i] < INT32_MIN){
            sum += INT32_MIN;
        }else{
            sum += ret[i] * num[i];
        }
    }

    if(sum > INT32_MAX || sum < INT32_MIN)return 0;
    return sum;
}

### 15. 3Sum

:::warning
回傳所有三元素加總為0的集合，集合不可以重複

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
:::

**思路**

- 先將矩陣由小至大進行 sort
- 遍歷矩陣，若該元素>0則搜尋結束
- 以第一個元素 i 為起始，後方集合使用left 和 right 夾擠配對
- 若 i 和上一個相同則跳過
- 若 left 和 right 和上一個相同也跳過

/*
Runtime: 204 ms, faster than 62.66% of C online submissions for 3Sum.
Memory Usage: 32.3 MB, less than 30.17% of C online submissions for 3Sum.
*/
static int _cmp(const int* a,const int* b){return (*a - *b);}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(numsSize * numsSize * sizeof(int));
    int** ret = (int**)malloc(sizeof(int*) * numsSize * numsSize);
    qsort(nums,numsSize,sizeof(int),_cmp);

    for(int i=0 ; i < numsSize - 2 ; i++){
        if(i>0 && nums[i-1] == nums[i]) continue;
        int left = i + 1, right = numsSize - 1;
        while (left < right)
        {
            if(nums[i] > 0)break;
            if(nums[i] + nums[left] + nums[right] == 0){
                ret[*returnSize] = (int*)malloc(sizeof(int) * 3);
                (*returnColumnSizes)[*returnSize] = 3;
                ret[*returnSize][0] = nums[i];
                ret[*returnSize][1] = nums[left];
                ret[*returnSize][2] = nums[right];
                *returnSize += 1;

                while (left < right && nums[left] == nums[left+1])
                {
                    left++;
                }

                while (left < right && nums[right] == nums[right - 1])
                {
                    right--;
                }
                
                left++;
                right--;

            }else if(nums[i] + nums[left] + nums[right] > 0)
                right--;
            else 
                left++;
        }
    }
    return ret;
}

### 16. 3Sum Closest

:::warning
3 sum 找最接近的值
:::

**思路**
- 先排序，然後以 i for 遍歷
- i 後面以左右指針遍歷，若更靠近更新值
- 每次找到新值後利用 while 去重複
- 左右指針更新依照目前總和距離 target 的正負，太小更新左值，太大更新右值

/*
Runtime: 154 ms, faster than 78.92% of C online submissions for 3Sum Closest.
Memory Usage: 6.5 MB, less than 65.06% of C online submissions for 3Sum Closest.
*/
int _cmp(const int *a, const int *b) {
    return (*a - *b);
}

int threeSumClosest(int* nums, int numsSize, int target){
    qsort(nums, numsSize, sizeof(int), _cmp);
    int ret = nums[0] + nums[1] + nums[2];
    for(int i = 0 ; i < numsSize - 2 ; i++){
        if(i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = numsSize - 1;
        while (left < right)
        {
            int sum = nums[i] + nums[left] + nums[right];
            if(sum == target) return target;
            if(abs(sum - target) < abs(ret - target)) {
                ret = sum;
                while (left < right && nums[left] == nums[left+1])
                {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1])
                {
                    right--;
                }
            }
            
            if(sum - target > 0) {
                right--;
            }
            else {
                left++;
            }
        }
    }

    return ret;
}

### 17. Letter Combinations of a Phone Number

:::warning
電話號碼的組合

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
:::

**思路**
- 暴力解
- 注意記憶體分配(要多分配一 bytes 給'\0')

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Letter Combinations of a Phone Number.
Memory Usage: 6.3 MB, less than 16.92% of C online submissions for Letter Combinations of a Phone Number.
*/
char ** letterCombinations(char * digits, int* returnSize){
    int n = strlen(digits);
    char **ret = (char**)malloc(sizeof(char*));
    if(n == 0){
        *returnSize = 0;
        return ret;
    }

    char temp[8][5] = {{'a','b','c','\0'},{'d','e','f','\0'},{'g','h','i','\0'},
                       {'j','k','l','\0'},{'m','n','o','\0'},{'p','q','r','s','\0'},
                       {'t','u','v','\0'},{'w','x','y','z','\0'}};

    int count = 0;                   
    if(n == 1){
        for(int i=0;temp[(int)digits[0] - 50][i]!='\0';i++){
            ret = (char**)realloc(ret,sizeof(char*)*(count+1));
            ret[count] = (char*)malloc(sizeof(char)*2);
            ret[count][0] = temp[(int)digits[0] - 50][count];
            ret[count][1] = '\0';
            //printf("%c ",temp[(int)digits[0] - 50][count]);
            count++;
        }
    }else if(n == 2){
        for(int i=0;temp[(int)digits[0] - 50][i]!='\0';i++){
            for(int j=0;temp[(int)digits[1] - 50][j]!='\0';j++){
                ret = (char**)realloc(ret,sizeof(char*)*(count+1));
                //printf("%c %c\n",temp[(int)digits[0] - 50][i],temp[(int)digits[1] - 50][j]);
                ret[count] = (char*)malloc(sizeof(char)*3);
                ret[count][0] = temp[(int)digits[0] - 50][i];
                ret[count][1] = temp[(int)digits[1] - 50][j];
                ret[count][2] = '\0';
                count++;
            }
        }
    }else if(n == 3){
        for(int i=0;temp[(int)digits[0] - 50][i]!='\0';i++){
            for(int j=0;temp[(int)digits[1] - 50][j]!='\0';j++){
                for(int k=0;temp[(int)digits[2] - 50][k]!='\0';k++){
                    ret = (char**)realloc(ret,sizeof(char*)*(count+1));
                    //printf("%c %c %c\n",temp[(int)digits[0] - 50][i],temp[(int)digits[1] - 50][j],temp[(int)digits[2] - 50][k]);
                    ret[count] = (char*)malloc(sizeof(char)*4);
                    ret[count][0] = temp[(int)digits[0] - 50][i];
                    ret[count][1] = temp[(int)digits[1] - 50][j];
                    ret[count][2] = temp[(int)digits[2] - 50][k];
                    ret[count][3] = '\0';
                    count++;
                }
            }
        }
    }else{
        for(int i=0;temp[(int)digits[0] - 50][i]!='\0';i++){
            for(int j=0;temp[(int)digits[1] - 50][j]!='\0';j++){
                for(int k=0;temp[(int)digits[2] - 50][k]!='\0';k++){
                    for(int l=0;temp[(int)digits[3] - 50][l]!='\0';l++){
                        ret = (char**)realloc(ret,sizeof(char*)*(count+1));
                        //printf("%c %c %c %c\n",temp[(int)digits[0] - 50][i],temp[(int)digits[1] - 50][j],temp[(int)digits[2] - 50][k],temp[(int)digits[3] - 50][l]);
                        ret[count] = (char*)malloc(sizeof(char)*5);
                        ret[count][0] = temp[(int)digits[0] - 50][i];
                        ret[count][1] = temp[(int)digits[1] - 50][j];
                        ret[count][2] = temp[(int)digits[2] - 50][k];
                        ret[count][3] = temp[(int)digits[3] - 50][l];
                        ret[count][4] = '\0';
                        count++;
                    }
                }
            }
        }
    }
    //printf("%c ",temp[(int)digits[0] - 50][count]);
    *returnSize = count;
    return ret;
}

### 18. 4Sum

:::warning
3 sum 再進階版本
:::
**思路**

- 以類似 3 sum 作法遍歷存值
- 以 long 存 sum ，由於會有整數型態溢位問題

/*
Runtime: 62 ms, faster than 46.32% of C online submissions for 4Sum.
Memory Usage: 6.9 MB, less than 68.42% of C online submissions for 4Sum.
*/
int _cmp(const int *a, const int *b) {
    return (*a - *b);
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
    int**ret = malloc(sizeof(int*));
    *returnSize = 0;
    if(numsSize < 4)return ret;
    
    qsort(nums, numsSize, sizeof(int), _cmp);
    for(int i = 0 ; i < numsSize - 3 ; i++) {
        if(i > 0 && nums[i] == nums[i - 1]) continue;
        for(int j = i + 1 ; j < numsSize - 2 ; j++){
            if(j > i + 1 && nums[j] == nums[j - 1]) continue;
            int left = j + 1, right = numsSize - 1;
            while(left < right) {
                long sum = (long)nums[i] + (long)nums[j] + (long)nums[left] + (long)nums[right];
                if(sum == target) {
                    // 分配記憶體並存入
                    ret = realloc(ret, sizeof(int*) * (*returnSize + 1));
                    ret[*returnSize] = malloc(sizeof(int) * 4);
                    ret[*returnSize][0] = nums[i];
                    ret[*returnSize][1] = nums[j];
                    ret[*returnSize][2] = nums[left];
                    ret[*returnSize][3] = nums[right];
                    (*returnSize)++;

                    while (left < right && nums[left] == nums[left + 1])
                    {
                        left++;
                    }

                    while (left < right && nums[right] == nums[right - 1])
                    {
                        right--;
                    }
                }
                if(sum > target)
                    right--;
                else 
                    left++;
            }
        }
    }

    int* size = (int*)malloc((*returnSize)*sizeof(int));
    memset (size, 0, (*returnSize)*sizeof(int));
    for(int i = 0 ; i < (*returnSize) ; i++)
        size[i] = 4;
    *returnColumnSizes = (int*) realloc(size, (*returnSize) * sizeof(int));
    return ret;
}

### 19. Remove Nth Node From End of List

:::warning
從Linked List中移除倒數n的元素**

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
:::

**思路**
- 遍歷串列紀錄個數
- 按照要求移除，注意移除首元素為特例

/*
Runtime: 5 ms, faster than 40.91% of C online submissions for Remove Nth Node From End of List.
Memory Usage: 5.7 MB, less than 74.21% of C online submissions for Remove Nth Node From End of List. 
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* p = head;
    if(!head->next)return NULL;
    int count = 0;

    while (p != NULL)
    {
        count++;
        p = p->next;
    }

    // 移除首位元素直接回傳
    if(n == count)
        return head->next;


    p = head;
    int temp = 0;
    while (p != NULL)
    {
        if(temp == count - n - 1)
            p->next = p->next->next;
        temp++;
        p = p->next;
    }
    return head;
}

---

**思路**
- 創建left指向NULL，right指向head
- 讓left指標停在待刪除元素前一位
- 若left未移動則刪除第一位元素
- O(n)解法

/*
Runtime: 3 ms, faster than 64.79% of C online submissions for Remove Nth Node From End of List.
Memory Usage: 5.8 MB, less than 74.21% of C online submissions for Remove Nth Node From End of List.
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* left = NULL, *right = head;

    while (right != NULL)
    {
        if(left != NULL) left = left->next;
        if(n-- == 0) left = head;
        right = right->next;
    }

    //left從未移動，那就是第一個元素被刪除
    if(left == NULL)return head->next;  

    // 若移動，left會剛好停在刪除元素前面
    left->next = left->next->next;
    return head;
}

### 22. Generate Parentheses
:::warning
求所有可能組合

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
:::
**思路**
- 使用dfs，以base記下所有可能組合
- openCount一定會大於closeCount
- 注意雙指標在函式中的呼叫方法(&ret , char***)

void dfs(char* base, char*** ret,int* rs, int n,int openCount,int closeCount, int count){
    if(openCount == closeCount && closeCount == n)
    {
        // 配對成功，分配記憶體並按 base 填入 ret
        (*rs)++;
        (*ret) = realloc(*ret, sizeof(char*) * (*rs));
        (*ret)[(*rs) - 1] = calloc(1, sizeof(char) * (2 * n + 1));
        for(int i = 0 ; i <= 2*n ; i++)
        {
            (*ret)[(*rs) - 1][i] = base[i];
        }
        return;
    }
    else
    {
        // 尚未配對完全
        if(openCount < n){
            base[count] = '(';
            dfs(base, ret, rs, n, openCount + 1, closeCount, count+1);
            base[count] = '\0';
        }

        if(closeCount < openCount){
            base[count] = ')';
            dfs(base, ret, rs, n, openCount, closeCount + 1, count+1);
            base[count] = '\0';
        }
    }
}

char ** generateParenthesis(int n, int* returnSize){
    char** ret = (char**)calloc(1,sizeof(char*));
    char* base = calloc(2*n + 1,sizeof(char));
    *returnSize = 0;
    dfs(base, &ret, returnSize, n, 0 ,0 ,0);
    return ret;
}

### 24. Swap Nodes in Pairs
:::warning
交換串列鄰近節點
:::
**思路**
- 以快慢指針做交換
- O(N / 2)

struct ListNode* swapPairs(struct ListNode* head){
    if(!head) return NULL;
    if(!head->next) return head;

    struct ListNode* slow = head;
    struct ListNode* fast = head->next;

    while (fast)
    {
        int tmp = slow->val;
        slow->val = fast->val;
        fast->val = tmp;
        if(!fast->next) break;
        fast = fast->next->next;
        slow = slow->next->next;
    }
    return head;
}

### 33. Search in Rotated Sorted Array
:::warning
一漸增矩陣按 1 pivot 旋轉，以 log(n) 找到目標數值

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
:::
**思路**
- 觀察頭尾後，以中值向左右尋找
- for 迴圈那樣寫省一個整數的記憶體大小
- worst case : O(n)

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Search in Rotated Sorted Array.
Memory Usage: 6.1 MB, less than 29.95% of C online submissions for Search in Rotated Sorted Array.
*/
int search(int* nums, int numsSize, int target){
    if(target == nums[0])
        return 0;
    else if(target == nums[numsSize - 1])
        return numsSize - 1;
    else {
        for(int i = (numsSize % 2 == 0) ? numsSize/2 : (numsSize - 1)/2 + 1 ; i < numsSize ; i++)
            if(target == nums[i])
                return i;

        for(int i = (numsSize % 2 == 0) ? numsSize/2 : (numsSize - 1)/2 ; i > 0 ; i--)
            if(target == nums[i])
                return i;
    }
    return -1;
}

---

**思路**
- 每次找出 mid ，可以和最左最右判斷是否有序，其中一邊一定為有序數列
- Normal case : O(log n)

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Search in Rotated Sorted Array.
Memory Usage: 6.2 MB, less than 6.25% of C online submissions for Search in Rotated Sorted Array.
*/
int search(int* nums, int numsSize, int target){
    int left = 0, right = numsSize - 1;
    while (left <= right)   
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) return mid;

        if(nums[mid] < nums[right]) {
            // 中間小於最右，右半邊有序，判斷新邊界
            if(nums[mid] < target && nums[right] >= target) left = mid + 1;
            else right = mid - 1;
        }
        else {
            // 左半邊有序
            if(nums[mid] > target && nums[left] <= target) right = mid - 1;
            else left = mid + 1;
        }
    }
    return -1;
}

### 34. Find First and Last Position of Element in Sorted Array
:::warning
找出矩陣中指定元素頭尾出現位置

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
:::
**思路**
- 以 BS 找出第一個元素
- 以此元素做分界左右繼續用 BS 直至找不到元素
- 比較三個數，找出區間

/*
Runtime: 14 ms, faster than 48.85% of C online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 7.7 MB, less than 11.17% of C online submissions for Find First and Last Position of Element in Sorted Array.
*/
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

void binarySearch(int* nums, int left, int right, int target,bool* find, int* val) {
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            *val = mid;
            *find = true;
            break;
        }

        if(nums[mid] > target) {
            right = mid - 1;
        }

        if(nums[mid] < target) {
            left = mid + 1;
        }
    }
}

void binarySearch_left(int* nums, int left, int right, int target,bool find, int* val) {
    find = false;

    int mid;
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            *val = mid;
            find = true;
            break;
        }

        if(nums[mid] > target) {
            right = mid - 1;
        }

        if(nums[mid] < target) {
            left = mid + 1;
        }
    }
    if(find == false)return;
    binarySearch_left(nums, left, mid - 1, target, find, val);
}

void binarySearch_right(int* nums, int left, int right, int target,bool find, int* val) {
    find = false;

    int mid;
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if(nums[mid] == target) {
            *val = mid;
            find = true;
            break;
        }

        if(nums[mid] > target) {
            right = mid - 1;
        }

        if(nums[mid] < target) {
            left = mid + 1;
        }
    }
    if(find == false)return;
    binarySearch_right(nums, mid + 1, right, target, find, val);
}

int threeMAX(int a, int b, int c) {
    if(b == INT32_MIN && c == INT32_MIN)
        return a;

    if(b == INT32_MIN)
        return MAX(a,c);

    if(c == INT32_MIN) 
        return MAX(a,b);

    return MAX(a,MAX(b,c));
}

int threeMIN(int a, int b, int c) {
    if(b == INT32_MIN && c == INT32_MIN)
        return a;

    if(b == INT32_MIN)
        return MIN(a,c);
    
    if(c == INT32_MIN)
        return MIN(a,b);
    
    return MIN(a,MIN(b,c));
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int left = 0, right = numsSize - 1, mid;
    int* ret = (int*)malloc(sizeof(int) * 2);
    ret[0] = ret[1] = -1;
    *returnSize = 2;

    if(numsSize == 0)
        return ret;

    int tmp;
    bool find = false;

    binarySearch(nums, 0, numsSize - 1, target, &find, &tmp);

    if(!find)
        return ret;

    int first = INT32_MIN, second = INT32_MIN;

    binarySearch_left(nums, 0, tmp - 1, target, false, &first);
    binarySearch_right(nums, tmp + 1, numsSize - 1, target, false, &second);
    
    ret[0] = threeMIN(tmp,first,second);
    ret[1] = threeMAX(tmp,first,second);
    
    return ret;
}

### 36. Valid Sudoku
::: warning
檢查是否符合九宮格規範

:::
**思路**
- 直接 brutal force

/*
Runtime: 11 ms, faster than 88.09% of C online submissions for Valid Sudoku.
Memory Usage: 5.7 MB, less than 98.17% of C online submissions for Valid Sudoku.
*/
bool isValidSudoku(char** board, int boardSize, int* boardColSize){
    int sum = 0;    // 用來記錄值
    int tmp[9] = {0};
    
    //  先針對橫行觀察
    for(int i = 0 ; i < 9 ; i++)
    {
        
        memset(tmp, 0 , sizeof(tmp));
        for(int j = 0 ; j < 9 ; j++){
            if(board[i][j] == '.')continue;
            tmp[board[i][j] - 49]++;
            if(tmp[board[i][j] - 49] > 1)return false;
        }
    }
    // 直行
    printf("\n");
    for(int i = 0 ; i < 9 ; i++)
    {
        memset(tmp, 0 , sizeof(tmp));
        for(int j = 0 ; j < 9 ; j++){
            if(board[j][i] == '.')continue;
            tmp[board[j][i] - 49]++;
            if(tmp[board[j][i] - 49] > 1)return false;
        }
    }
    
    printf("\n");
    for(int i = 0 ; i < 3 ; i++)
    {
        for(int j = 0 ; j < 3 ; j++)
        {
            memset(tmp, 0 , sizeof(tmp));
            for(int a = i*3 ; a < i*3 + 3 ; a++)
            {
                for(int b = j*3 ; b < j*3 + 3;b++)
                {
                    if(board[a][b] == '.')continue;
                    tmp[board[a][b] - 49]++;
                    if(tmp[board[a][b] - 49] > 1)return false;
                }
            }

        }
    }
    

    return true;
}

### 39. Combination Sum
:::warning
給定目標求組合，可重複

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
:::

**思路**
- 使用 dfs進行去重
- C 比 C++ 快太多了吧

/*
Runtime: 27 ms, faster than 46.40% of C online submissions for Combination Sum.
Memory Usage: 17.9 MB, less than 13.73% of C online submissions for Combination Sum.
*/
void dfs(int *nums, int numsSize, int* returnSize,int target,int** ret, int idx,int sum,int count,int arr[],int *size) {
    if(sum > target) return;
    if(idx >= numsSize) return;
    if(sum == target) {
        // 去重 ?
        bool flag = false;
        for(int i = 0 ; i < *returnSize ; i++) {
            if(size[i] != count) continue;
            flag = true;
            for(int j = 0 ; j < count ; j++) {
                if(ret[i][j] != arr[j])
                    flag = false;
            }
            if(flag) return;
        }
        ret[*returnSize] = calloc(count, sizeof(int));
        for(int i = 0 ; i < count ; i++) 
            ret[*returnSize][i] = arr[i];
        size[(*returnSize)] = count;
        (*returnSize)+=1;
        return;
    }
    // not choose this val
    dfs(nums, numsSize, returnSize, target, ret, idx + 1, sum, count, arr, size);
    // choose same val
    arr[count] = nums[idx];
    dfs(nums, numsSize, returnSize, target, ret, idx, sum + nums[idx],count + 1,arr,size);
    // choose this val and move to next val
    dfs(nums, numsSize, returnSize, target, ret, idx + 1, sum + nums[idx],count + 1,arr,size);
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize,int** returnColumnSizes){
    int** ret = malloc(sizeof(int*) * 50000);
    int arr[1000];
    int *size = malloc(sizeof(int) * 50000);
    *returnSize = 0;
    dfs(candidates,candidatesSize,returnSize,target,ret, 0, 0, 0, arr, size);
    (*returnColumnSizes) = calloc((*returnSize),sizeof(int));
    for(int i = 0 ; i < (*returnSize) ; i++) {
        (*returnColumnSizes)[i] = size[i];
    }
    return ret;
}

### 40. Combination Sum II
:::danger
求目標子矩陣，不能重複使用
:::

**思路**
- 使用 dfs 產生 Time Limit Exceed

void dfs(int *nums, int numsSize, int* returnSize,int target,int** ret, int idx,int sum,int count,int arr[],int *size) {
    if(sum > target) return;
    if(sum == target) {
        // 去重 ?
        bool flag = false;
        for(int i = 0 ; i < *returnSize ; i++) {
            if(size[i] != count) continue;
            flag = true;
            for(int j = 0 ; j < count ; j++) {
                if(ret[i][j] != arr[j])
                    flag = false;
            }
            if(flag) return;
        }
        ret[*returnSize] = calloc(count, sizeof(int));
        for(int i = 0 ; i < count ; i++) 
            ret[*returnSize][i] = arr[i];
        size[(*returnSize)] = count;
        (*returnSize)+=1;
        return;
    }
    if(idx >= numsSize) return;
    // not choose this val
    dfs(nums, numsSize, returnSize, target, ret, idx + 1, sum, count, arr, size);
    
    arr[count] = nums[idx];
    // choose this val and move to next val
    dfs(nums, numsSize, returnSize, target, ret, idx + 1, sum + nums[idx],count + 1,arr,size);
}

int _cmp(const int *a, const int *b) {
    return *a - *b;
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize,int** returnColumnSizes){
    qsort(candidates,candidatesSize,sizeof(int),_cmp);
    int** ret = malloc(sizeof(int*) * 10000);
    int arr[150];
    int *size = malloc(sizeof(int) * 10000);
    *returnSize = 0;
    dfs(candidates,candidatesSize,returnSize,target,ret, 0, 0, 0, arr, size);
    (*returnColumnSizes) = calloc((*returnSize),sizeof(int));
    for(int i = 0 ; i < (*returnSize) ; i++) {
        (*returnColumnSizes)[i] = size[i];
    }
    return ret;
}

---
**思路**
- 改為使用 dfs 加上 backtracking
- 實在不懂，變相進行選或不選，注意 i = idx 的時機再看看

void dfs(int *nums, int numsSize, int* returnSize,int target,int** ret, int idx,int sum,int count,int arr[],int *size) {
    if(idx >= numsSize) return;
    for(int i = idx ; i < numsSize ; i++) {
        if(i > idx) {
            while (i < numsSize && nums[i] == nums[i - 1]){
                i++;
            }
            if(i == numsSize)
                return;
        }
        if(sum + nums[i] > target){
            return;
        }
        else if(sum + nums[i] < target){
            arr[count] = nums[i];
            dfs(nums, numsSize, returnSize, target, ret, i + 1, sum + nums[i],count + 1,arr,size);
        }
        else{
            arr[count] = nums[i];
            ret[*returnSize] = calloc(count+1, sizeof(int));
            for(int j = 0 ; j <= count ; j++) 
                ret[*returnSize][j] = arr[j];
            size[(*returnSize)] = count + 1;
            (*returnSize)+=1;
            return;  
        }
    }
}

int _cmp(const int *a, const int *b) {
    return *a - *b;
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize,int** returnColumnSizes){
    qsort(candidates,candidatesSize,sizeof(int),_cmp);
    int** ret = malloc(sizeof(int*) * 100);
    int arr[150];
    int *size = malloc(sizeof(int) * 100);
    *returnSize = 0;
    dfs(candidates,candidatesSize,returnSize,target,ret, 0, 0, 0, arr, size);
    (*returnColumnSizes) = calloc((*returnSize),sizeof(int));
    for(int i = 0 ; i < (*returnSize) ; i++)
        (*returnColumnSizes)[i] = size[i];
    return ret;
}

### 43. Multiply Strings
:::warning
給數字字串回傳相乘結果
:::
**思路**
- 相乘存入矩陣
- 做進位後分配記憶體

char * multiply(char * num1, char * num2){
    if(num1[0] == '0' || num2[0] == '0') return "0";
    int tmp[40005] = {0};
    int count;
    int idx = 0;
    
    //  相乘存入矩陣
    for(int i = strlen(num1) - 1 ; i >= 0  ; i--) {
        int count = 40004 - idx;
        for(int j = strlen(num2) - 1 ; j >= 0 ; j--) {
            int n1 = num1[i] - 48;
            int n2 = num2[j] - 48;
            int mul = n1 * n2;
            if(mul < 10) {
                tmp[count--] += mul;
            }
            else {
                tmp[count--] += mul % 10;
                tmp[count] += (mul / 10);
            }
        }
        idx++;
    }

    // 做進位
    for(int i = 40004 ; i > 0 ; i--) {
        if(tmp[i] < 10) continue;
        else {
            tmp[i - 1] += tmp[i] / 10;
            tmp[i] %= 10;
        }
    }

    // 做合法遍歷
    bool flag = false;
    char* ret = NULL;
    int cnt = 0;
    for(int i = 0 ; i < 40005 ; i++) {
        if(flag){
            ret[cnt++] = tmp[i] + '0';
        }    
        else {
            if(tmp[i] != 0) {
                ret = calloc(40004 - i + 2,sizeof(char));
                ret[cnt++] = tmp[i] + '0';
                flag = true;
            }
        }
    }
    ret[cnt] = '\0';
    return ret;
}

### 46. Permutations
:::warning
任意排序

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
:::
**思路**
- 使用 dfs
- 每次進入都從頭遍歷，並分為添加此數或尚未添加此數的 flag 矩陣

/*
Runtime: 10 ms, faster than 90.91% of C online submissions for Permutations.
Memory Usage: 7.6 MB, less than 26.26% of C online submissions for Permutations.
*/
void getPermute(int **ret, int *nums, int numsSize, int *rs,int *buff, int index, bool *flag) {
        /* 到值則分配記憶體儲存 */
    if(index == numsSize) {
        ret[(*rs)] = (int *)calloc(numsSize,sizeof(int));
        memcpy(ret[(*rs)], buff, sizeof(int) * numsSize);
        (*rs)++;
        return;
    }

        /* 每次遍歷所有元素，並分為添加此數在此位置與否 */
    for(int i = 0 ; i < numsSize ; i++) {
        if(flag[i] == false) {
            flag[i] = true;
            buff[index] = nums[i];
            getPermute(ret,nums,numsSize,rs,buff,index + 1,flag);
            flag[i] = false;
        }
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    
    int **ret = (int **)calloc(1024, sizeof(int *)); 
    int *buff = (int *)calloc(numsSize, sizeof(int));
    bool *flag = (bool *)calloc(numsSize, sizeof(bool));
    int rs = 0;

    getPermute(ret, nums, numsSize, &rs, buff, 0, flag);

    *returnSize = rs;
    (*returnColumnSizes) = calloc((*returnSize),sizeof(int*));
    for(int i = 0 ; i < (*returnSize) ; i++) {
        (*returnColumnSizes)[i] = numsSize;
    }
    
    return ret;
}

### 47. Permutations II
:::warning
排序數列，但會有重複值

Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
:::
**思路**
- 使用 dfs 搭配 arr 矩陣紀錄是否用過
- 結果輸出時去重複

/*
Runtime: 1450 ms, faster than 6.52% of C online submissions for Permutations II.
Memory Usage: 9.7 MB, less than 45.65% of C online submissions for Permutations II.
*/
void permute(int* nums, int numsSize, int *rs, int** ret, int arr[8], int box[], int cnt) {
    if(cnt > numsSize) return;
    if(cnt == numsSize) {
        // 存放時去順序完全重複的
        for(int i = 0 ; i < *rs ; i++) {
            bool find = true;
            for(int j = 0 ; j < numsSize ; j++) {
                if(box[j] != ret[i][j])
                    find = false;
            }
            if(find) return;
        }

        // 分配記憶體並存放
        ret[*rs] = calloc(numsSize,sizeof(int));
        memcpy(ret[*rs], box, sizeof(int) * numsSize);
        (*rs)++;
        return;
    }
    for(int i = 0 ; i < numsSize ; i++) {
        if(arr[i] == 0) {
            arr[i] = 1;
            box[cnt] = nums[i];
            permute(nums, numsSize, rs, ret, arr, box, cnt+1);
            arr[i] = 0;
        }
    }

}

int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    int tmp[8] = {0};
    int box[8];
    int** ret = malloc(sizeof(int*) * 10000);
    permute(nums, numsSize, returnSize, ret, tmp, box, 0);

    (*returnColumnSizes) = calloc(*returnSize, sizeof(int));
    for(int i = 0 ; i < *returnSize ; i++)
        (*returnColumnSizes)[i] = numsSize;
    return ret;
}

### 48. Rotate Image

:::warning
:::

**思路**
- 沿主對角線反轉，再垂直軸反轉

/*
Runtime: 8 ms, faster than 24.81% of C online submissions for Rotate Image.
Memory Usage: 6.2 MB, less than 68.89% of C online submissions for Rotate Image.
*/
void swap(int *a, int *b){
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}
void rotate(int** matrix, int matrixSize, int* matrixColSize){
    
    // 沿對角線做反轉
    for(int i=0;i<matrixSize;i++){
        for(int j=i;j<matrixSize;j++){
            if(i == j)continue;
            swap(&matrix[i][j], &matrix[j][i]);
        }
    }

    // 垂直軸反轉
    for(int i=0;i<matrixSize;i++){
        int left = 0, right = matrixSize - 1;

        while (left < right)
        {
            swap(&matrix[i][left],&matrix[i][right]);
            left++;
            right--;
        }
    }

    *matrixColSize = matrixSize;
    
}

### 49. Group Anagrams
:::warning
相同元素的分組回傳

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
:::
**思路**
- 先對每個 string 按 char 大小 sort
- 以第一個元素為首，和後方比較是否相同，若相同則分配記憶體並標記，往後直接忽略

/*
Runtime: 1621 ms, faster than 5.04% of C online submissions for Group Anagrams.
Memory Usage: 40.9 MB, less than 69.19% of C online submissions for Group Anagrams.
*/
int key_cmp(void* a, void*b){
    return *((char*)a) - *((char*)b);
}
char *** groupAnagrams(char ** strs, int strsSize , int* returnSize, int** returnColumnSizes){ 
    char** key = calloc(10000,sizeof(char*));           // sort後的矩陣
    bool* use = (bool*)malloc(sizeof(bool) * strsSize); // 已經被排序與否
    char*** ret = calloc(10000,sizeof(char**));         // 返回矩陣
    int* index = calloc(10000, sizeof(int));            // 用來記錄returnColumn
    memset(use,false,strsSize);
    int count = 0, count_num;

    // 針對字串進行按大小排序
    for(int i = 0 ; i < strsSize ; i++)
    {
        key[i] = malloc((strlen(strs[i])+ 1) * sizeof(char));
        strcpy(key[i], strs[i]);
        qsort(key[i], strlen(key[i]), sizeof(char), key_cmp);
    }
        
    // 以首位為標記向後尋找，有的話就分配記憶體並標記
    for(int i = 0 ; i < strsSize ; i++){
        count_num = 0;
        if(use[i])continue;
        ret[count] = (char**)malloc(sizeof(char*) * (count_num + 1));
        ret[count][count_num] = (char*)malloc(sizeof(char) * (strlen(strs[i]) + 1));
        strcpy(ret[count][count_num], strs[i]);
        count_num ++;

        for(int j = i + 1 ; j < strsSize ; j++)
        {
            if(use[j])continue;
            if(strcmp(key[i],key[j]) != 0)continue;

            // 符合的對象
            ret[count] = (char**)realloc(ret[count],sizeof(char*) * (count_num + 1));
            ret[count][count_num] = (char*)malloc(sizeof(char) * (strlen(strs[i]) + 1) );
            strcpy(ret[count][count_num] , strs[j]);
            use[j] = true;
            count_num++;
        }
        index[count] = count_num;
        count++;
    }
    
    *returnSize = count;
    *returnColumnSizes = calloc((*returnSize),sizeof(int));
    for (int i = 0; i < *returnSize; i++)   
		returnColumnSizes[0][i] = index[i];
    return ret;
}

### 50. Pow(x, n)
:::warning
實作pow

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
:::

**思路**
- 使用指數遞增法(n*n)，超過則除回來
- 注意n為 **INT32_MAX~INT32_MIN** ， 使用 long long 避免邊界問題

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Pow(x, n).
Memory Usage: 5.5 MB, less than 84.67% of C online submissions for Pow(x, n).
*/
double myPow(double x, int n){
    if(n == 0)return 1;
    if(x == 1)return 1;
    x = (n > 0) ? x : 1 / x;

    double ret = x;
    long long note = n;
    note = (note < 0) ? -note : note;

    long long count = 1;
    double tmp;

    while (count < note)
    {
        tmp = ret * ret;
        ret = tmp;
        count = count * 2;
    }

    for(long long i = note ; i < count ; i++){
        tmp = ret / x;
        ret = tmp;
    }    
    
    return ret;
}

### 53. Maximum Subarray

:::warning
找出矩陣內連續且總和最大的串

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
:::

**思路**
- dp解
- 以max紀錄最大值
- tmp累加，若大於max則更新最大值，小於0則重新開始尋找更大值

int maxSubArray(int* nums, int numsSize){
    int max = nums[0], tmp = 0;

    for(int i = 0; i < numsSize ; i++){
        tmp += nums[i];
        if(tmp > max)max = tmp;

        // tmp小於0為重新尋找能讓值變大的數
        if(tmp < 0)tmp = 0; 
    }

    return max;
}

---

**思路**
- 以maxEnd紀錄累進值，若**目前總和加上下一數**仍比**下一數**大，則不重新開始

#define MAX(a, b) ((a) > (b) ? (a) : (b))
int maxSubArray(int* nums, int numsSize){
    int max = nums[0], maxEnd = nums[0];

    for(int i = 1 ; i < numsSize ; i++){
        // 若目前總和加上下一數仍比下一數大，則不重新開始
        maxEnd = MAX(maxEnd + nums[i], nums[i]);
        max = MAX(max, maxEnd);
    }

    return max;
}

### 54. Spiral Matrix
::: warning

:::

**思路**
- 向左邊開始，遇到邊界就轉向
- O(N+M)

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Spiral Matrix.
Memory Usage: 5.8 MB, less than 43.33% of C online submissions for Spiral Matrix.
*/
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
    *returnSize = matrixSize * (*matrixColSize);
    int* ret = calloc(*returnSize, sizeof(int));
    int count = 0, direction = 1, num;   // 1r, 2d, 3l, 4u
    int i = 0, j = 0, flag = 1;
    while (count < (*returnSize))
    {
        switch (direction)
        {
        case 1:
            if(j + 1 == (*matrixColSize)) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                direction++;
                i++;
            }else if(matrix[i][j + 1] == -101) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                direction++;
                i++;
            }
            else if(j < (*matrixColSize)) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                j++;
            }
            break;
        case 2:
            if(i + 1 == matrixSize) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                direction++;
                j--;               
            }else if(matrix[i+1][j] == -101){
                num = matrix[i][j];
                matrix[i][j] = -101;
                direction++;
                j--;
            }
            else if(i < (matrixSize)) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                i++;
            }
            flag = 0;
            break;

        case 3:
            if(j == 0) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                direction++;
                i--;
            } else if (matrix[i][j - 1] == -101) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                direction++;
                i--;
            }
            else if(j >= 0) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                j--;
            }
            break;

        case 4:
            if(matrix[i - 1][j] == -101) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                direction++;
                j++;
            }
            else if(i >= 0) {
                num = matrix[i][j];
                matrix[i][j] = -101;
                i--;
            }
            break;
        }
        ret[count] = num;
        count++;
        if(direction == 5)direction = 1;
    }
    return ret;
}

### 55. Jump Game

::: info
跳格子

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
:::
**思路**
- 使用 dfs 但 **Time Limit Exceed**

void dfs(int *nums, int numsSize, bool* find,int count){
    if(count > numsSize - 1)
    {
        return;
    }
    else if(count == numsSize - 1)
    {
        *find = true;
    }
    else
    {
        int n = nums[count];

        while (n != 0)
        {
            dfs(nums, numsSize, find,count+n);
            n--;
        }
    }
    return;
}

bool canJump(int* nums, int numsSize){
    bool find = false;
    dfs(nums, numsSize, &find, 0);
    return find;
}

---

**思路**
- 用貪婪法
- 紀錄最遠可達距離max，遍歷過程中若 max 小於指標則無解

bool canJump(int* nums, int numsSize) {
    int max = 0;
    for(int i = 0 ; i < numsSize - 1 ; i++)
    {
        max = ((i + nums[i]) > max) ? (i + nums[i]) : max;
        if(max < i + 1)return false;
    }
    return true;
}

### 56. Merge Intervals

:::warning
確認區間並合併

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
:::

**思路**
- 先針對二維矩陣的 left 進行排序
- 以 right 和下一組 left 比較，大於則重新排序，小於則分配記憶體儲存

/*
Runtime: 54 ms, faster than 99.11% of C online submissions for Merge Intervals.
Memory Usage: 28.4 MB, less than 8.28% of C online submissions for Merge Intervals.
*/
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int _cmp(const void *a, const void *b)
{
    int **a1 = (int **)a;
    int **b1 = (int **)b;
    
    if (a1[0][0] != b1[0][0]) {
        return a1[0][0] - b1[0][0];
    } else {
        return a1[0][1] - b1[0][1];
    }
}
int** merge(int** intervals, int intervalsSize , int* intervalsColSize, int* returnSize, int** returnColumnSizes){
    // 定義左右，若右區間小於下一值左區間則分配記憶體
    if(intervalsSize == 1)return intervals;
    qsort(intervals, intervalsSize, sizeof(intervals[0]), _cmp);
    int** ret = (int**)calloc(10000,sizeof(int*));
    
    int left = intervals[0][0], right = intervals[0][1], count = 0;
    
    for(int i = 0 ; i < intervalsSize - 1 ; i++)
    {
        if(right < intervals[i+1][0])
        {
            //分配記憶體
            ret[count] = (int*)realloc(ret[count],sizeof(int) * 2);
            ret[count][0] = left;
            ret[count][1] = right;
            left = intervals[i+1][0];
            right = intervals[i+1][1];
            count++;
        }
        else
        {
            // 有交集重新定義左右界
            left = MIN(left, intervals[i+1][0]);
            right = MAX(right, intervals[i+1][1]);
        }
    }
    ret[count] = (int*)realloc(ret[count],sizeof(int) * 2);
    ret[count][0] = left;
    ret[count][1] = right;
    count++;
    
    *intervalsColSize = 2;
    *returnSize = count;
    returnColumnSizes[0]=(int*)malloc((*returnSize)*sizeof(int));
    for(int i = 0 ; i < (*returnSize) ; i++)
        returnColumnSizes[0][i]=2;
    return ret;
}

### 57. Insert Interval
:::warning
插入元素至正確區間

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
:::

**思路**
- O(N) 作法遍歷即可，注意邊界條件

/*
Runtime: 14 ms, faster than 97.14% of C online submissions for Insert Interval.
Memory Usage: 10.2 MB, less than 7.14% of C online submissions for Insert Interval.
*/
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    int** ret = calloc(1000,sizeof(int*));
    bool flag = false, flag2 = false;
    int new_first, new_last; // 新首數和新尾數
    
    // 特殊情況
    if(intervalsSize == 0) {
        ret[*returnSize] = calloc(2,sizeof(int));
        memcpy(ret[*returnSize],newInterval,sizeof(int) * 2);
        (*returnSize)++;
    }
    if(newIntervalSize == 0) {
        return intervals;
    }
    
    for(int i = 0 ; i < intervalsSize ; i++) {
        if(flag2) {
            ret[*returnSize] = calloc(2,sizeof(int));
            memcpy(ret[*returnSize],intervals[i],sizeof(int) * 2);
            (*returnSize)++;
            continue;
        }

        // 不在尋找狀態且找到中空位置
        if(newInterval[1] < intervals[i][0] && flag == false) {
            ret[*returnSize] = calloc(2,sizeof(int));
            memcpy(ret[*returnSize],newInterval,sizeof(int) * 2);
            (*returnSize)++;
            flag2 = true;
            i--;
            continue;   
        }

        // 不在尋找狀態且繼續不尋找
        if(newInterval[0] > intervals[i][1] && flag == false) {
            ret[*returnSize] = calloc(2,sizeof(int));
            memcpy(ret[*returnSize],intervals[i],sizeof(int) * 2);
            (*returnSize)++;
            continue;
        }

        // 不在尋找狀態但切換到尋找狀態了
        if(newInterval[0] <= intervals[i][1] && flag == false) {
            flag = true;
            new_first = MIN(intervals[i][0], newInterval[0]);
        }

        if(flag) {
            // 最後一組還在排就特別處置
            if(i == intervalsSize - 1) {
                flag2 = true;
                new_last = MAX(newInterval[1], intervals[i][1]);
                ret[*returnSize] = calloc(2,sizeof(int));
                ret[*returnSize][0] = new_first;
                ret[*returnSize][1] = new_last;
                (*returnSize)++;
                continue;
            }
            // 若插入值小於下一組頭
            if(newInterval[1] < intervals[i+1][0]) {
                new_last = MAX(newInterval[1], intervals[i][1]);
                flag = false;
                flag2 = true;
                ret[*returnSize] = calloc(2,sizeof(int));
                ret[*returnSize][0] = new_first;
                ret[*returnSize][1] = new_last;
                (*returnSize)++;
            }
            else if(newInterval[1] == intervals[i+1][0]) {
                flag = false;
                flag2 = true;
                new_last = intervals[i+1][1];
                ret[*returnSize] = calloc(2,sizeof(int));
                ret[*returnSize][0] = new_first;
                ret[*returnSize][1] = new_last;
                (*returnSize)++;
                i++;
            }
        }
    }

    // 都沒有找到的話就插在最後面
    if(!flag2 && intervalsSize != 0) {
        ret[*returnSize] = calloc(2,sizeof(int));
        memcpy(ret[*returnSize],newInterval,sizeof(int) * 2);
        (*returnSize)++;
    }


    (*returnColumnSizes) = calloc(*returnSize, sizeof(int));
    for(int i = 0 ; i < *returnSize ; i++)
        (*returnColumnSizes)[i] = 2;
    
    return ret;
}

### 59. Spiral Matrix II
:::warning
求出順時鐘螺旋賦值矩陣

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
:::

**思路**
- 使用 dfs 給邊界條件轉向

/*
Runtime: 3 ms, faster than 72.54% of C online submissions for Spiral Matrix II.
Memory Usage: 6.3 MB, less than 35.92% of C online submissions for Spiral Matrix II.
*/
void dfs(int n, int** ret, int dir, int i, int j, int cnt) {
    if(cnt > n*n) return;
    // 碰到 0 或邊界轉彎
    ret[i][j] = cnt;
    int I = i, J =j;
    switch (dir)
    {
    case 0:
        /* 向右中 */
        if(j + 1 == n || (j < n - 1 && ret[i][j + 1] != 0)){
            dir++;
            I++;
        }else{
            J++;
        }
        break;

    case 1:
        /* 向下中 */
        if(i + 1 == n || (i < n - 1 && ret[i + 1][j] != 0)) {
            dir++;
            J--;
        }else{
            I++;
        }
        break;

    case 2:
        /* 向左中 */
        if(j - 1 < 0 || (j > 0 && ret[i][j - 1] != 0)) {
            dir++;
            I--;
        }
        else{
            J--;
        }
        break;

    case 3:
        /* 向上中 */
        if(i - 1 < 0 || (i > 0 && ret[i - 1][j] != 0)){
            dir++;
            J++;
        }
        else{
            I--;
        }
        break;
    
    default:
        break;
    }
    dfs(n, ret, dir % 4, I, J, cnt + 1);
}
    
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
    int** ret = calloc(n, sizeof(int*));
    for(int i = 0 ; i < n ; i++){
        ret[i] = calloc(n, sizeof(int));
        memset(ret[i], 0, sizeof(int) * n);
    }
    dfs(n, ret, 0, 0, 0, 1);
    
    *returnSize = n;
    (*returnColumnSizes) = calloc(n, sizeof(int));
    for(int i = 0 ; i < n ; i++)
        (*returnColumnSizes)[i] = n;
    return ret;
}

### 61. Rotate List
:::warning
將串列元素按指定位置顛倒
:::
**思路**
- 以多個指針進行記錄
- 以 k % sum 除去多餘的步數

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Rotate List.
Memory Usage: 6.1 MB, less than 77.84% of C online submissions for Rotate List.
*/
struct ListNode* rotateRight(struct ListNode* head, int k){
    if(!head)return head;
    struct ListNode *ptr = head; // 遍歷指針
    int sum = 0;
    while (ptr)
    {
        sum++;
        ptr = ptr->next;
    }
    
    ptr = head;
    int cnt = 0;
    int num = k % sum;
    if(num == 0) return head;

    struct ListNode *newHead;
    struct ListNode *last;
    
    while (ptr)
    {
        cnt++;
        if(cnt == sum - num){
            newHead = ptr->next;
            last = ptr;
        }
        if(!ptr->next){
            ptr->next = head;
            break;
        }
        ptr = ptr->next;
    }
    last->next = NULL;
    return newHead;
}

---
**思路**
- 以快指針進一步省下 N/2 的遍歷時間

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Rotate List.
Memory Usage: 6.2 MB, less than 34.28% of C online submissions for Rotate List.
*/
struct ListNode* rotateRight(struct ListNode* head, int k){
    if(!head)return head;
    struct ListNode *ptr = head; // 遍歷指針
    struct ListNode *fast = head;
    int sum = 1;
    int cnt = 0;
    while (fast && fast->next)
    {
        if(!fast->next->next)
            sum+=1;
        else
            sum+=2;
        fast = fast->next->next;
    }
    int num = sum - k % sum;
    printf("%d",num);
    sum = k % sum;
    if(sum == 0) return head;
    struct ListNode* newHead;
    struct ListNode* newEnd;
    while (ptr)
    {
        cnt++;
        if(cnt == num) {
            newHead = ptr->next;
            newEnd = ptr;
        }
        if(!ptr->next) {
            ptr->next = head;
            break;
        }
        ptr = ptr->next;
    }
    newEnd->next = NULL;

    return newHead;
}

### 62. Unique Paths

:::warning
找路徑
:::

**思路**
- 使用 dp 疊加每次路線的可能性

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Unique Paths.
Memory Usage: 5.4 MB, less than 98.45% of C online submissions for Unique Paths.
*/
int uniquePaths(int m, int n){
    int arr[m][n];

    for(int i = 0 ; i < m ; i ++) {
        for(int j = 0 ; j < n ; j++){
            if(i == 0 || j == 0)arr[i][j] = 1;
            else arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
        }
    }

    return arr[m - 1][n - 1];
}

### 63. Unique Paths II
:::warning
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
:::
**思路**
- 使用 dfs
- 答案對但 Time Limit Exceed

void dfs(int **nums, int row, int col, int i, int j, int* cnt) {
    // 邊界條件
    if(i >= row || j >= col)
        return;
    
    // 碰到障礙物條件
    if(nums[i][j] == 1)
        return;

    // 到底計算輸出
    if(i == row - 1 && j == col - 1){
        (*cnt)++;
        return;
    }

    // 朝下或右邊 dfs
    dfs(nums,row,col,i,j+1,cnt);
    dfs(nums,row,col,i+1,j,cnt);
}

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    int cnt = 0;
    dfs(obstacleGrid, obstacleGridSize, *obstacleGridColSize, 0, 0, &cnt);
    return cnt;
}

---
**思路**
- 使用迷宮題特有的組合計算方式
- O(N^2) 時間複雜度，no extra space

/*
Runtime: 4 ms, faster than 63.37% of C online submissions for Unique Paths II.
Memory Usage: 6 MB, less than 85.15% of C online submissions for Unique Paths II.
*/
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    for(int i = 0 ; i < obstacleGridSize ; i++) {
        for(int j = 0 ; j < *obstacleGridColSize ; j++){
            // 若遍歷時該處為 1 ，則轉為 0 繼續
            if(obstacleGrid[i][j] == 1){
                obstacleGrid[i][j] = 0;
                continue;
            }
            
            // 起始賦值為 1
            if(i == 0 && j == 0){
                obstacleGrid[i][j] = 1;
                continue;
            }

            // 若非 0 且在邊界上，加上值或左值
            if(i == 0)
                obstacleGrid[i][j] += obstacleGrid[i][j - 1];
            else if(j == 0)
                obstacleGrid[i][j] += obstacleGrid[i - 1][j];
            else 
                obstacleGrid[i][j] += obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
        }
    }
    return obstacleGrid[obstacleGridSize - 1][*obstacleGridColSize - 1];
}

### 64. Minimum Path Sum

:::warning

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
:::

**思路**
- 使用迷宮動態規劃解法
- 差別在非邊界決策時選擇較小的路徑加

/*
Runtime: 10 ms, faster than 94.24% of C online submissions for Minimum Path Sum.
Memory Usage: 7.3 MB, less than 82.20% of C online submissions for Minimum Path Sum.
*/
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int minPathSum(int** grid, int gridSize, int* gridColSize){
    for(int i = 0 ; i < gridSize ; i++) {
        for(int j = 0 ; j < *gridColSize ; j++) {
            // 特殊原點
            if(i == 0 && j == 0)
                continue;
            
            if(i == 0)
                grid[i][j] += grid[i][j - 1];
            else if(j == 0)
                grid[i][j] += grid[i - 1][j];
            else
                grid[i][j] += MIN(grid[i][j - 1],grid[i - 1][j]);
        }
    }
    return grid[gridSize - 1][*gridColSize - 1];
}

### 73. Set Matrix Zeroes
:::warning

:::

**思路**
- 先遍歷找出 0 位置
- 再遍歷位置 memset 為 0

/*
Runtime: 62 ms, faster than 56.28% of C online submissions for Set Matrix Zeroes.
Memory Usage: 19.1 MB, less than 22.95% of C online submissions for Set Matrix Zeroes.
*/
void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
    int** tmp = (int*)calloc(40000, sizeof(int*)); // 標記為0位置
    int count = 0;
    for(int i = 0 ; i < matrixSize ; i++) {
        for(int j = 0 ; j < (*matrixColSize) ; j++) {
            if(matrix[i][j] == 0) {
                tmp[count] = calloc(2,sizeof(int));
                tmp[count][0] = i;
                tmp[count][1] = j;
                count++;
            }
        }
    }

    // 將直行橫行化為0
    for(int i = 0 ; i < count ; i++) {
        memset(matrix[tmp[i][0]], 0 , sizeof(int) * (*matrixColSize));

        for(int j = 0 ; j < matrixSize ; j++) {
            matrix[j][tmp[i][1]] = 0;
        }
    }
}

---
**思路**
- 以一 tmp 複製矩陣紀錄所有 0 變動，最後再賦值回去
- 節省了一點記憶體，效能沒有顯著改善

/*
Runtime: 81 ms, faster than 25.14% of C online submissions for Set Matrix Zeroes.
Memory Usage: 11.3 MB, less than 22.95% of C online submissions for Set Matrix Zeroes.
*/
void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
    int** tmp = (int**)calloc(matrixSize,sizeof(int*));
    int i_note[200] = {0};
    int j_note[200] = {0};
    for(int i = 0 ; i < matrixSize ; i++) {
        tmp[i] = (int*)calloc(*matrixColSize, sizeof(int));
        memcpy(tmp[i],matrix[i],*matrixColSize * sizeof(int));
    }

    for(int i = 0 ; i < matrixSize ; i++) {
        for(int j = 0 ; j < *matrixColSize ; j++) {
            if(matrix[i][j] == 0)
            {

                if(i_note[i] == 0)memset(tmp[i], 0 , *matrixColSize * sizeof(int)); // 橫為0
                if(j_note[j] == 0) {
                    for(int l = 0 ; l < matrixSize ; l++)tmp[l][j] = 0;
                }
                i_note[i] = 1;
                j_note[j] = 1;
            }
        }
    }

    for(int i = 0 ; i < matrixSize ; i++) {
        memcpy(matrix[i],tmp[i],*matrixColSize * sizeof(int));
    }
}

### 74. Search a 2D Matrix
:::warning
找 sort 矩陣中是否存在 target

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
:::

**思路**
- 先以 column 確定目標是否存在區間
- 確認存在再以 binary search 找是否存在
- 再加一些邊界條件增加搜尋到機率，避免進行 Binary Search
- Average case : O( logN ) , Best case : O( N )

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Search a 2D Matrix.
Memory Usage: 6.1 MB, less than 82.24% of C online submissions for Search a 2D Matrix.
*/
bool binarySearch(int* nums, int left, int right, int target) {
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return true;
        else if(nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return false;
}

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    // 先遍歷 j 找小於的，可能在內部再用BS尋找
    for(int i = 0; i < matrixSize ; i++){
        if(matrix[i][0] > target)
            break;
        if(target >= matrix[i][0] && target <= matrix[i][*matrixColSize - 1]){
            int mid = (*matrixColSize) / 2;
            if(target == matrix[i][0] || target == matrix[i][*matrixColSize - 1] || target == matrix[i][mid])
                return true;
            return binarySearch(matrix[i], 0, *matrixColSize - 1, target);
        }
    }
    return false;
}

### 75. Sort Colors
:::warning
對矩陣進行排序
:::

**思路**
- 使用 qsort
- O(N logN)

/*
Runtime: 2 ms, faster than 75.05% of C online submissions for Sort Colors.
Memory Usage: 6.3 MB, less than 22.87% of C online submissions for Sort Colors.
*/
static int _cmp(const int *a, const int *b) {
    return (*a - *b);
}

void sortColors(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), _cmp);
}

---
**思路**
- 使用 selection sort
- O(N2)

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Sort Colors.
Memory Usage: 5.8 MB, less than 93.76% of C online submissions for Sort Colors.
*/
void swap(int *a, int *b){
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

void sortColors(int* nums, int numsSize){
    for(int i = 0 ; i < numsSize ; i++) {
        for(int j = i + 1 ; j < numsSize ; j++) {
            if(nums[i] > nums[j]) swap(&nums[i] , &nums[j]);
        }
    }
}

---
**思路**
- 使用 merge sort
- O(n logN)

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Sort Colors.
Memory Usage: 6.2 MB, less than 22.87% of C online submissions for Sort Colors.
*/
void merge(int *nums, int l, int m, int r) {
    int i,j,k;
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1],R[n2];

    // L1 和 L2 為左右矩陣
    for (i = 0; i < n1; i++)
        L[i] = nums[l + i];
    for (j = 0; j < n2; j++)
        R[j] = nums[m + 1 + j];

    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray

    // 最後依序賦值回去
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            nums[k] = L[i];
            i++;
        }
        else {
           nums[k] = R[j];
            j++;
        }
        k++;
    }
  
    /* Copy the remaining elements of L[], if there
    are any */
    while (i < n1) {
        nums[k] = L[i];
        i++;
        k++;
    }
  
    /* Copy the remaining elements of R[], if there
    are any */
    while (j < n2) {
        nums[k] = R[j];
        j++;
        k++;
    }    
}

void mergesort(int ** nums,int l,int r) {
    if(l < r) {
        int mid = l + (r - l) / 2;
        mergesort(&(*nums), l, mid);
        mergesort(&(*nums), mid + 1, r);
        merge(&(*nums), l, mid ,r);
    }
}
void sortColors(int* nums, int numsSize){
    mergesort(&nums, 0 , numsSize - 1);
}

### 77. Combinations
:::warning
做限定個數的排列組合

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
:::

**思路**
- 使用遞歸型 DFS ，搭配 start 變數動態改變每次 dfs 起始值，如此可以避免重複

/*
Runtime: 79 ms, faster than 70.93% of C online submissions for Combinations.
Memory Usage: 13.6 MB, less than 30.23% of C online submissions for Combinations.
*/
void dfs(int n, int k, int idx, int **ret,int *rs, int *box, int start) {
    if(idx > k) return;
    if(idx > n)return;

    if(idx == k){
        ret[*rs] = malloc(sizeof(int) * k);
        memcpy(ret[*rs], box, sizeof(int) * k);
        (*rs)++;
        return;
    }
    /*
     *  start 為起始值
     *  動態改變後續的起始位置，以 i + 1 傳遞
     *  即可避免遍歷重複元素
     */
    for(int i = start ; i <= n ; i++) {
        box[idx] = i;
        dfs(n,k,idx+1,ret,rs,box,i+1);
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
    int **ret = malloc(sizeof(int*) * 10000);
    *returnSize = 0;
    int *box = malloc(sizeof(int)*20);
    
    dfs(n, k, 0, ret, returnSize, box, 1);
    
    free(box);

    (*returnColumnSizes) = malloc((*returnSize) * sizeof(int*));
    for(int i = 0; i < *returnSize ; i++)
        (*returnColumnSizes)[i] = k;
    return ret;
}

### 78. Subsets
:::warning
做 power set

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
:::

**思路**
- 個數不多，使用 dfs
- 注意空矩陣和 returnColumnSize 的關係

/*
Runtime: 4 ms, faster than 94.06% of C online submissions for Subsets.
Memory Usage: 9.8 MB, less than 8.91% of C online submissions for Subsets.
*/
void dfs(int *nums, int **ret, int base[10], int n,int i, int count, int *idx, int **rc) {
    if(i == n)
        return;

    // 分三種: 存此值並繼續，不存此值繼續，分配記憶體存目前base
    // 不存此值繼續
    dfs(nums, ret, base, n, i + 1, count, idx, rc);

    // 存此值繼續
    base[count] = nums[i];
    dfs(nums, ret, base, n, i + 1, count + 1, idx, rc);
    
    // 存目前值
    ret[(*idx)] = calloc(count + 1,sizeof(int));
    memcpy(ret[(*idx)] , base, sizeof(int) * (count + 1));
    (*rc)[(*idx)] = count + 1;
    (*idx)++;
    return;
}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int** ret = calloc(2000, sizeof(int*));
    (*returnColumnSizes) = (int *)malloc(2000*sizeof(int));

    /* 先存入空矩陣 */
    ret[0] = calloc(1,sizeof(int));
    ret[0] = NULL;
    *returnColumnSizes[0] = 0;
    
    int base[10];
    int idx = 1;  // count為個別矩陣元素個數，idx則為總矩陣數，i為第幾個遍歷(以index)
    dfs(nums, ret, base, numsSize, 0, 0, &idx, returnColumnSizes);

    *returnSize = idx;
    return ret;
}

### 79. Word Search
:::info

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
:::
**思路**
- 由棋盤中每個值當起始元素
- 若 word 指到底則找到對應值
- 走過的先將元素刪除，避免往回走的情況
- 最後再設回原先的值 (backTrack)

void dfs(char **board, int boardSize, int boardColSize, int i, int j,char *word, bool *find) {

    if(*word == '\0')
        (*find) = true;
    if(i < 0 || i >= boardSize || j < 0 || j >= boardColSize)
        return;
    if(board[i][j] != *word)
        return;
    
    char backTrack = board[i][j];
    board[i][j] = ' ';
    
    dfs(board,boardSize, boardColSize, i - 1, j, word + 1, find);
    dfs(board,boardSize, boardColSize, i + 1, j, word + 1, find);
    dfs(board,boardSize, boardColSize,i , j - 1, word + 1, find);
    dfs(board,boardSize, boardColSize,i , j + 1, word + 1, find);

    board[i][j] = backTrack;

    return;   
}

bool exist(char** board, int boardSize, int* boardColSize, char * word){
    bool find = false;
    for(int i = 0 ; i < boardSize ; i++) {
        for(int j = 0 ; j < (*boardColSize) ; j++) {
            if(board[i][j] == *word)
                dfs(board, boardSize, *boardColSize, i , j, word, &find);
        }
    }
    return find;
}

### 80. Remove Duplicates from Sorted Array II

:::warning
修剪矩陣中重複元素，並修剪矩陣大小

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
:::
**思路**
- 使用 hashmap 紀錄元素，再遍歷修正位置

struct hash
{
    int id;
    int val;
    UT_hash_handle hh;
};

int removeDuplicates(int* nums, int numsSize){
    struct hash* map = NULL;
    int cnt = numsSize;
    for(int i = 0 ; i < numsSize ; i++) {
        struct hash* tmp;
        HASH_FIND_INT(map, &nums[i], tmp);
        if(tmp == NULL) {
            tmp = malloc(sizeof(struct hash));
            tmp->id = nums[i];
            tmp->val = 1;
            HASH_ADD_INT(map,id,tmp);
        }else if(tmp->val >= 2){
            nums[i] = INT32_MIN;
            cnt--;
        }else {
            tmp->val++;
        }
    }
    
    // 重新排序
    int count = 0;
    for(int i = 0 ; i < numsSize; i++) {
        if(nums[i] == INT32_MIN){
            count++;
            continue;
        }
        nums[i - count] = nums[i];
    }
    return cnt;
}

---
**思路**
- hashmap 消耗額外記憶體以及分配時間
- 使用矩陣紀錄亦消耗大量額外記憶體
- 因其漸增特性，使用 DP 動態更新數字以及出現次數，再同步進行位置移動
- Time : O( N ) , Memory : O( 1 )

/*
Runtime: 10 ms, faster than 93.33% of C online submissions for Remove Duplicates from Sorted Array II.
Memory Usage: 6.6 MB, less than 64.17% of C online submissions for Remove Duplicates from Sorted Array II.
*/
int removeDuplicates(int* nums, int numsSize){
    int cnt = numsSize;
    int count = 0;
    int time = 1;
    int ptr = nums[0];
    for(int i = 1 ; i < numsSize ; i++) {
        if(ptr == nums[i]){
            time++;
            if(time > 2){
                count++;
                cnt--;
                continue;
            }
        }else{
            ptr = nums[i];
            time = 1;
        }
        nums[i - count] = nums[i];
    }
    return cnt;
}

### 81. Search in Rotated Sorted Array II

:::warning
尋找旋轉後矩陣目標元素

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
:::

**思路**
- sort 後使用二元搜尋法
- O( NlogN )

/*
Runtime: 3 ms, faster than 97.50% of C online submissions for Search in Rotated Sorted Array II.
Memory Usage: 6.1 MB, less than 65.00% of C online submissions for Search in Rotated Sorted Array II.
*/
int _cmp(const int *a, const int *b) {
    return *a - *b;
}
bool search(int* nums, int numsSize, int target){
    qsort(nums,numsSize,sizeof(int),_cmp);
    int left = 0, right = numsSize - 1;
    while (left <= right)
    {
        int mid = left + (right - left)/2;
        if(nums[mid] == target){
            return true;
        }else if(nums[mid] < target) {
            left = mid +1;
        }else{
            right = mid - 1;
        }
    }
    return false;
}

### 82. Remove Duplicates from Sorted List II

:::warning
Linked list 移除重複元素

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
:::

**思路**
- 以快慢指針(差一位)遍歷，若元素相同為重複更新tmp值，並將 ptr 標記
- 若是被標記元素則整合時跳過，注意全被標記和 fast 邊界條件
- 時間複雜度 : O( N )

/*
Runtime: 4 ms, faster than 83.74% of C online submissions for Remove Duplicates from Sorted List II.
Memory Usage: 6.4 MB, less than 65.95% of C online submissions for Remove Duplicates from Sorted List II.
*/
struct ListNode* deleteDuplicates(struct ListNode* head){
    if(!head) return head;
    struct ListNode *ptr = head;
    struct ListNode *ret = NULL;
    struct ListNode *fast = head->next;
    int tmp = INT32_MAX; // 紀錄 fast 元素
    if(!head->next) return head;
    while (fast)
    {
        if(fast->val == ptr->val) tmp = fast->val;
        if(ptr->val == tmp) ptr->val = -200;
        if(!fast->next && fast->val == tmp) fast->val = -200;
        

        if(ptr->val != -200){
            if(!ret){
                ret = ptr;
                head = ret;
            }else{
                ret->next = ptr;
                ret = ret->next;
            }
        }
        
        if(!fast->next && fast->val == -200){
            if(ret) ret->next = NULL;
        }
        if(!fast->next && fast->val != -200) {
            if(ret) ret->next = fast;
            else{
                ret = fast;
                head = ret;
            }
        }
        
        ptr = ptr->next;
        fast = fast->next;
    }
    return (ret) ? head : ret;
}

### 86. Partition List

:::warning
Linked list 內元素將其與 x 大小比較後左右排

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
:::

**思路**
- 以額外記憶體紀錄較大的元素
- O( N )

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Partition List.
Memory Usage: 5.8 MB, less than 97.47% of C online submissions for Partition List.
*/
struct ListNode* partition(struct ListNode* head, int x){
    if(!head || !head->next)return head;
    struct ListNode *ptr = head;
    struct ListNode *box[200] = {NULL};
    struct ListNode *tmp = NULL;
    struct ListNode *ret = tmp;
    int cnt = 0; // for box
    while (ptr)
    {
        if(ptr->val < x) {
            if(!tmp){
                tmp = ptr;
                ret = tmp;
            }    
            else {
                tmp->next = ptr;
                tmp = tmp->next;
            }
        }else{
            box[cnt] = ptr;
            cnt++;
        }
        ptr = ptr->next;
    }
    for(int i = 0 ; i < cnt ; i++) {
        box[i]->next = NULL;
        if(!tmp){
            tmp = box[i];
            ret = tmp;
            continue;
        }
        tmp->next = box[i];
        tmp = box[i];
    }
    return

### 91. Decode Ways

**思路**
- 使用 DFS 搭配指針移動遍歷
- **Time Limit Exceed**

void dfs(char *s, int sum, int *count) {
    if(*s == '\0') {
        (*count)++;
        return;
    }

    if(*s == '0' && sum == 0)// no leading zero
        return; 

    sum = sum*10 + (*s - 48);
    
    if(sum > 26)
        return;

    // 已經加兩次了
    if(sum >= 10 && sum < 27) {
        dfs(s+1,0,count);

    }else if(sum < 10){
        if(*(s+1) != '\0')dfs(s+1,sum,count);
        dfs(s+1,0,count);
    }
}

int numDecodings(char * s){
    int count = 0;
    dfs(s, 0, &count);
    return count;
}

---

- 尚未搞懂的算法

https://blog.csdn.net/hsk6543210/article/details/106862833

/*
1.如果第一個字符为0，不存在解碼方法

2. 考察前一字符是否為 0 ，若不為 0 則加入前一字符累積值

3. 考察前前字符和前字符是否能組合(介於 26 內)，若能則加入 dp[i - 2]
*/
int numDecodings(char * s){
    if(s[0] == '0')return 0;
    int len = strlen(s);
    if(s[0] == '0' || len == 0) {
        return 0;
    }
    int dp[105];
    dp[0] = 1;
    for(int i = 1 ; i <= len ; i++) {
        dp[i] = s[i - 1] == '0' ? 0 : dp[i - 1];
        if(i > 1) {
            if(s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')){
                dp[i] += dp[i - 2];
            }
        }
    }
    return dp[len];
}

### 98. Validate Binary Search Tree

::: warning
確認樹是否為 BST
:::

**思路**
- 使用遞歸左右子樹來查找
- 每次設定上下界來指示子節點範圍

/*
Runtime: 18 ms, faster than 15.18% of C online submissions for Validate Binary Search Tree.
Memory Usage: 8.6 MB, less than 82.79% of C online submissions for Validate Binary Search Tree.
*/
bool checkValid(struct TreeNode* root, long low, long high) {
    if(!root)return true;
    if(root->val <= low || root->val >= high)return false;
    return checkValid(root->left,low,root->val)&&checkValid(root->right,root->val,high);
}

bool isValidBST(struct TreeNode* root){
    if(!root)return false;
    return checkValid(root->left, LONG_MIN, root->val) && checkValid(root->right,root->val,LONG_MAX);
}

### 102. Binary Tree Level Order Traversal
:::warning
對樹元素同階層做分類

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
:::

**思路**
- 遞歸遍歷
- 遍歷中記錄階層和各階層累積元素以分配正確記憶體

/*
Runtime: 6 ms, faster than 74.87% of C online submissions for Binary Tree Level Order Traversal.
Memory Usage: 8.2 MB, less than 53.89% of C online submissions for Binary Tree Level Order Traversal.
*/
void traverse(struct TreeNode* root, int** ret, int level, int *idx) {
    if(!root)return;

    // 若還沒有值則分配一個記憶體，若有值則重新分配記憶體
    if(idx[level] == 0)
        ret[level] = calloc(1, sizeof(int));
    else
        ret[level] = realloc(ret[level],sizeof(int) * (idx[level] + 1));
    ret[level][idx[level]] = root->val;
    idx[level]++;

    traverse(root->left, ret, level + 1, idx);
    traverse(root->right, ret, level + 1, idx);
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int** ret = calloc(2000,sizeof(int*));
    int idx[2000] = {0};     // 告知現在特定深度的值有幾個了
    traverse(root, ret, 0, idx);

    *returnSize = 0;
    for(int i = 0 ; i < 2000 ; i++) {
        if(idx[i] == 0)
            break;
        (*returnSize)++;
    }

    (*returnColumnSizes) = calloc((*returnSize),sizeof(int));
    for(int i = 0 ; i < (*returnSize) ; i++) {
        (*returnColumnSizes)[i] = idx[i];
    }

    return ret;
}

### 103. Binary Tree Zigzag Level Order Traversal

::: warning
以蛇行分類二元樹

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
:::

**思路**
- 同 102 ，使用遞歸先找出正順序的排序
- 再對後續矩陣進行各層排序處理，若奇數層則整個顛倒過來

/*
Runtime: 7 ms, faster than 45.35% of C online submissions for Binary Tree Zigzag Level Order Traversal.
Memory Usage: 7.8 MB, less than 22.09% of C online submissions for Binary Tree Zigzag Level Order Traversal.
*/
void traverse(struct TreeNode* root, int** ret, int level, int *idx) {
    if(!root)return;

    // 若還沒有值則分配一個記憶體，若有值則重新分配記憶體
    if(idx[level] == 0)
        ret[level] = calloc(1, sizeof(int));
    else
        ret[level] = realloc(ret[level],sizeof(int) * (idx[level] + 1));
    ret[level][idx[level]] = root->val;
    idx[level]++;

    traverse(root->left, ret, level + 1, idx);
    traverse(root->right, ret, level + 1, idx);
}

void swap(int *a, int *b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    int** ret = calloc(2000,sizeof(int*));
    int idx[2000] = {0};     // 告知現在特定深度的值有幾個了
    traverse(root, ret, 0, idx);

    
    *returnSize = 0;
    for(int i = 0 ; i < 2000 ; i++) {
        if(idx[i] == 0)
            break;
        (*returnSize)++;
    }
    
    // 奇數層進行順序對調
    for(int i = 0 ; i < (*returnSize); i++) {
        if(i % 2 == 0) 
            continue;
        else {
            int left = 0, right = idx[i] - 1;
            while (left < right)
            {
                swap(&ret[i][left],&ret[i][right]);
                left++;
                right--;
            }
        }
    }

    (*returnColumnSizes) = calloc((*returnSize),sizeof(int));
    for(int i = 0 ; i < (*returnSize) ; i++) {
        (*returnColumnSizes)[i] = idx[i];
    }

    return ret;
}

### 116. Populating Next Right Pointers in Each Node

::: danger

:::
**思路**
- 遍歷串列，透過一二維 Linked List 紀錄同一階層尚未連接的節點
- 注意 memset 第二個參數的賦值

void traverse(struct Node* root, int level, struct Node** heads) {
    if(!root)return;

    if(heads[level] != NULL)
        heads[level]->next = root;

    heads[level] = root;
    root->next = NULL;

    traverse(root->left,level + 1, heads);
    traverse(root->right,level + 1,heads);
}

struct Node* connect(struct Node* root) {
    if(!root)return NULL;
    struct Node* heads[12];
    memset(heads, 0, 12 * sizeof(struct Node*)); // 這裡依然不懂為何賦值
    traverse(root,0,&heads);
    return root;
}

### 122. Best Time to Buy and Sell Stock II

:::warning
找出股票買賣最大收益，但可以無限次買入賣出
:::

**思路**
- 可以無限次，則每次有機會就考慮賣出並累積收益

/*
Runtime: 5 ms, faster than 84.88% of C online submissions for Best Time to Buy and Sell Stock II.
Memory Usage: 6.9 MB, less than 37.52% of C online submissions for Best Time to Buy and Sell Stock II.
*/
int maxProfit(int* prices, int pricesSize){
    int totalProfit = 0;

    for(int i = 0 ; i < pricesSize - 1 ; i++) {
        if(prices[i] < prices[i + 1])
            totalProfit += prices[i + 1] - prices[i];
    }

    return totalProfit;
}

### 128. Longest Consecutive Sequence
:::warning
印出矩陣中最大連續數列數量

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
:::
**思路**
- 先將數列排序
- 使用 dp 追蹤最大連續值
- 若不連續則重新計數，若數字和前一相同則不重新

/*
Runtime: 68 ms, faster than 97.66% of C online submissions for Longest Consecutive Sequence.
Memory Usage: 12.4 MB, less than 76.04% of C online submissions for Longest Consecutive Sequence.
*/
#define MAX(a, b) ((a) > (b) ? (a) : (b))

static int _cmp(const int *l,const int *r){
    return (*l - *r);
}

int longestConsecutive(int* nums, int numsSize){
    if(numsSize == 0)return 0;

    qsort(nums, numsSize, sizeof(int), _cmp);

    int count = 1, max = 1;
    for(int i = 1 ; i < numsSize ; i++) {
        if(nums[i] == nums[i - 1])continue;
        if(nums[i] - nums[i - 1] == 1) {
            count++;
        } else {
            max = MAX(count, max);
            count = 1;
        }
    }
    
    max = MAX(count, max);
    return max;
}

### 130. Surrounded Regions

:::warning
找出完全被包圍的位置
:::

**思路**
- 只有和邊界相連才算不被包圍
- 由四邊 dfs ，相連則將 O 改為臨時記號 1
- 最後將全部 1 改為 O ，而原先為 O 的改為 X (沒有出口)

/*
Runtime: 43 ms, faster than 60.34% of C online submissions for Surrounded Regions.
Memory Usage: 11.2 MB, less than 34.48% of C online submissions for Surrounded Regions.
*/
void check(char ** board, int row, int col, int x, int y) {
    if(x < 0 || y < 0 || x >= row || y >= col || board[x][y] == 'X')
        return;
    if(board[x][y] == 'O') {
        board[x][y] = '1';
        check(board, row, col, x + 1, y);
        check(board, row, col, x - 1, y);
        check(board, row, col, x, y + 1);
        check(board, row, col, x, y - 1);
    }
}

void solve(char** board, int boardSize, int* boardColSize){
    for(int i = 0 ; i < boardSize ; i++) {
        if(board[i][0] == 'O')
            check(board, boardSize, *boardColSize, i, 0);
        if(board[i][(*boardColSize) - 1] == 'O')
            check(board, boardSize, *boardColSize, i, (*boardColSize) - 1);
    }

    for(int j = 1 ; j < (*boardColSize) - 1 ; j++) {
        if(board[0][j] == 'O')
            check(board,boardSize,*boardColSize,0, j);
        if(board[boardSize - 1][j] == 'O')
            check(board,boardSize, *boardColSize, boardSize - 1, j);
    }

    for(int i = 0 ; i < boardSize ; i++) {
        for(int j = 0 ; j < *boardColSize ; j++)
        {
            if(board[i][j] == '1')
                board[i][j] = 'O';
            else
                board[i][j] = 'X';
        }
    }
}

### 134. Gas Station

:::warning
找到一可以環狀遍歷的加油點

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
:::

**思路**
- 查看每個位置的油量變化
- 若出現負數，則起始到該處皆不能作為起點使用

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    
    int total = 0, sum = 0, start = 0;
    for(int i = 0; i < gasSize ; i++) {
        total += gas[i] - cost[i];
        sum += gas[i] - cost[i];
        if(sum < 0) {
            sum = 0;
            start = i + 1;
        }
    }
    
    return (total < 0) ? -1 : start;
}

### 138. Copy List with Random Pointer

::: warning
回傳一包含 random pointer 的 Linked List
:::

**思路**
- 先在每個節點後方新增一複製節點
- 依次賦予新節點隨機指針
- 最後斷開原先 Linked list

struct Node* copyRandomList(struct Node* head) {
    if(!head)return NULL;
	struct Node* ptr = head;

    // 先在每個節點後方新增一複製節點
    while (ptr)
    {
        struct Node* new = (struct Node*)malloc(sizeof(struct Node));
        new->random = NULL;
        new->val = ptr->val;
        new->next = ptr->next;
        ptr->next = new;
        ptr = new->next;
    }

    ptr = head;
    // 添加隨機指針
    while (ptr)
    {
        if(ptr->random)ptr->next->random = ptr->random->next;
        ptr = ptr->next->next;
    }

    ptr = head;
    struct Node* res = head->next;
    // 斷開原先節點
    while (ptr)
    {
        struct Node* tmp = ptr->next;
        ptr->next = tmp->next;
        if(tmp->next)tmp->next = tmp->next->next;
        ptr = ptr->next;
    }
    
    return res;
}

### 148. Sort List

:::warning
排序 Linked List
:::

**思路**
- 以矩陣儲存每個值後使用 quick sort
- 不斷使用 realloc 會超時，考慮一次性分配記憶體

/*
Runtime: 80 ms, faster than 100.00% of C online submissions for Sort List.
Memory Usage: 20.1 MB, less than 57.83% of C online submissions for Sort List.
*/
static int _cmp(const int *a, const int *b) {
    return (*a - *b);
}

struct ListNode* sortList(struct ListNode* head){
    struct ListNode *ptr = head;
    int count = 0;
    int nums[50005];
    while (ptr)
    {
        nums[count++] = ptr->val;   
        ptr = ptr->next;
    }

    qsort(nums,count,sizeof(int),_cmp);
    
    ptr = head;
    count = 0;
    while (ptr)
    {
        ptr->val = nums[count++];
        ptr = ptr->next;
    }
    return head;
}

---

**思路**
- 在 Linked List 實作 MergeSort
- 以快慢指針將 list 分成兩半，再分別套用 MergeSort 排列
https://www.codeleading.com/article/83811129128/

struct ListNode* Merge(struct ListNode* left, struct ListNode* right) {
    if(!left) return right;
    if(!right) return left;
    if(left->val <= right->val) {
        left->next = Merge(left->next,right);
        return left;
    }
    else {
        right->next = Merge(right->next,left);
        return right;
    }
}

struct ListNode* MergeSort(struct ListNode* node) {
    if(!node || !node->next) return node;

    struct ListNode* fast = node;
    struct ListNode* slow = node;
    struct ListNode* pre = node;

    while (fast != NULL && fast->next != NULL)
    {
        pre = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    pre->next = NULL;

    struct ListNode* left = MergeSort(node);
    struct ListNode* right = MergeSort(slow);

    return Merge(left,right);
}

struct ListNode* sortList(struct ListNode* head){
    if(head == NULL || head->next == NULL) return head;
    return MergeSort(head);
}

### 155. Min Stack
:::warning
以 C 實作 stack
:::

**思路**
- 利用矩陣和 idx 來實作動態分配記憶體的 stack

typedef struct {
    int* arr;
    int size;
} MinStack;


MinStack* minStackCreate() {
    MinStack* obj = malloc(sizeof(MinStack));
    obj->arr = NULL;
    obj->size = 0;
    return obj;
}

void minStackPush(MinStack* obj, int val) {
    obj->size++;
    obj->arr = realloc(obj->arr, (obj->size) * sizeof(int));
    obj->arr[obj->size - 1] = val;
}

void minStackPop(MinStack* obj) {
    obj->size--;
}

int minStackTop(MinStack* obj) {
    return obj->arr[obj->size -  1];
}

int minStackGetMin(MinStack* obj) {
    int min = (*obj).arr[0];
    for(int i = 0 ; i < obj->size ; i++)
        if(obj->arr[i] < min)
            min = obj->arr[i];
    return min;
}

void minStackFree(MinStack* obj) {
    free(obj->arr);
    free(obj);
}

### 162. Find Peak Element
:::warning
找出大於鄰居的極值，回傳 index

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
:::

**思路**
- 線性遍歷，注意邊界條件
- 最差狀況 O(N)

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Find Peak Element.
Memory Usage: 5.9 MB, less than 48.20% of C online submissions for Find Peak Element.
*/
int findPeakElement(int* nums, int numsSize){
    if(numsSize == 1)return 0;
    if(numsSize == 2) return (nums[0] > nums[1]) ? 0 : 1;
    
    for(int i = 1 ; i< numsSize - 1 ; i++)
        if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
            return i;

    if(nums[1] < nums[0]) return 0;
    if(nums[numsSize - 2] < nums[numsSize - 1]) return numsSize - 1;
    return 0;
}

---
**思路**
- 使用 binary search 遍歷
- O(log N)

/*
Runtime: 2 ms, faster than 90.91% of C online submissions for Find Peak Element.
Memory Usage: 5.8 MB, less than 75.26% of C online submissions for Find Peak Element.
*/
void func(int* nums, int numsSize, int left, int right,int *idx) {
    int mid = left + (right - left) / 2;

    if(mid < 0 || mid >= numsSize)return;
    // 邊界條件
    if(mid == 0 && nums[1] < nums[0]) {
        *idx = 0;
        return;
    }
    if(mid == numsSize - 1 && nums[numsSize - 2] < nums[numsSize - 1]) {
        *idx = numsSize - 1;
        return;
    }
    // 不在邊界但賦值
    if(mid >= 1 && mid <= numsSize - 2)
        if(nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
            *idx = mid;
            return;
        }
    if(mid > right || mid < left) return;
    func(nums,numsSize,left, mid - 1, idx);
    func(nums,numsSize,mid + 1, right,idx);
}

int findPeakElement(int* nums, int numsSize){
    if(numsSize == 1)return 0;
    if(numsSize == 2) return (nums[0] > nums[1]) ? 0 : 1;
    if(nums[1] < nums[0])return 0;
    if(nums[numsSize - 2] < nums[numsSize - 1])return numsSize - 1;

    int idx = 0;
    func(nums,numsSize,0,numsSize - 1,&idx);
    return idx;
}

### 172. Factorial Trailing Zeroes
:::warning
回傳 n ! 數值尾數 0 個數
:::

**思路**
- 硬乘會溢位
- 將中間 5 和 2 因數出現個數累積，回傳 MIN

/*
Runtime: 10 ms, faster than 16.00% of C online submissions for Factorial Trailing Zeroes.
Memory Usage: 5.6 MB, less than 34.67% of C online submissions for Factorial Trailing Zeroes.
*/
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int trailingZeroes(int n){
    int num_two = 0, num_five = 0;
    while (n > 0)
    {
        int tmp = n;
        //  檢驗 5 成分
        while (tmp % 5 == 0) {
            num_five++;
            tmp /= 5;
        }

        //  檢驗 2 成分
        while (tmp % 2 == 0) {
            num_two++;
            tmp /= 2;
        }
        
        n--;
    }
    return MIN(num_two,num_five);
}

---
**思路**

- 只需考慮 5 出現次數即可，因為對於所有 5 一定有足夠的 2 湊成 10

/*
Runtime: 10 ms, faster than 16.00% of C online submissions for Factorial Trailing Zeroes.
Memory Usage: 5.4 MB, less than 100.00% of C online submissions for Factorial Trailing Zeroes.
*/
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int trailingZeroes(int n){
    int num_five = 0;
    while (n > 0)
    {
        int tmp = n;
        //  檢驗 5 成分
        while (tmp % 5 == 0) {
            num_five++;
            tmp /= 5;
        }
        
        n--;
    }
    return num_five;
}

---
**思路**
- 透過除法找出含有 5 倍數的個數
- 本題的最佳解

/*
Runtime: 0 ms, faster than 100.00% of C online submissions for Factorial Trailing Zeroes.
Memory Usage: 5.5 MB, less than 64.00% of C online submissions for Factorial Trailing Zeroes.
*/
int trailingZeroes(int n){
    return n/5 + n/25 + n/125 + n/625 + n/3125; 
}

### 179. Largest Number
:::warning
給實數矩陣，找出最大的組合值

Input: nums = [10,2]
Output: "210"

Input: nums = [3,30,34,5,9]
Output: "9534330"
:::
**思路**
- 將矩陣進行排序
- 排序法為將兩數分別組合成新值然後比較大小

/*
Runtime: 8 ms, faster than 54.17% of C online submissions for Largest Number.
Memory Usage: 8.2 MB, less than 8.33% of C online submissions for Largest Number.
*/
void swap(int *a, int *b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

char * largestNumber(int* nums, int numsSize){
    int size_a, size_b;
    for(int i = 0 ; i < numsSize ; i++) {
        for(int j = i + 1 ; j < numsSize ; j++){
            int one = nums[i]; size_a = 0;
            int two = nums[j]; size_b = 0;
            if(one == 0)size_a = 1;
            if(two == 0)size_b = 1;
            while (one >= 1){
                size_a++;
                one /= 10;
            }
            while (two >= 1){
                size_b++;
                two /= 10;
            }

            one = nums[i];
            two = nums[j];
            
                // 將兩數以 long long 兩順序排一起比大小
            long long a  = (long long)one;
            long long b = (long long)two;
            a = a * pow(10, size_b) + (long long)two;
            b = b * pow(10, size_a) + (long long)one;
            if(a < b)
                swap(&nums[i],&nums[j]);
        }
    }

    char* ret = calloc(1,sizeof(char));

        // 返回結果，若首位元素為0則返回0矩陣
    if(nums[0] == 0) {
        ret = realloc(ret, sizeof(char) * 2);
        ret[0] = '0';
        ret[1] = '\0';
        return ret;
    }
    int count = 0;
    int size_tmp, tmp[10];
    for(int i = 0 ; i < numsSize ; i++) {
        int n = nums[i];
        size_tmp = 0;
        if(n == 0)
            tmp[size_tmp++] = 0;
        while (n >= 1){
            tmp[size_tmp++] = n % 10;
            n /= 10;
        }
        size_tmp--;
        while (size_tmp >= 0)
        {
            ret = realloc(ret, sizeof(char) * (count + 1));
            ret[count++] = tmp[size_tmp] + '0';
            size_tmp--;
        }
    }
    ret = realloc(ret, sizeof(char) * (count + 1));
    ret[count] = '\0';
    return ret;
}

### 240. Search a 2D Matrix II
:::warning
給定兩邊都排序後的矩陣，求是否存在目標元素

:::

**思路**
- 使用 i 先確認區間，再以 binary search 過程中動態確認 right 值邊界(逐漸縮小)
- 可能是本題最佳解， Avg : O( N )

/*
Runtime: 123 ms, faster than 59.96% of C online submissions for Search a 2D Matrix II.
Memory Usage: 9.1 MB, less than 63.02% of C online submissions for Search a 2D Matrix II.
*/
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    // 先遍歷 i 找特定區間，在遍歷 j 的過程中逐步縮減 right_max 值
    int left = 0, right = * matrixColSize;
    for(int i = 0; i < matrixSize ; i++){
        if(matrix[i][0] > target)
            break;
        if(target >= matrix[i][0] && target <= matrix[i][*matrixColSize - 1]){
            left = 0;
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if(matrix[i][mid] == target)
                    return true;
                else if(matrix[i][mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
    }
    return false;
}

### 454. 4Sum II
:::warning
4 Sum 但矩陣分開
:::

**思路**
- 使用 hashmap 將時間複雜度從 O(N^4) 降到 O(N^2)

/*
Runtime: 177 ms, faster than 45.45% of C online submissions for 4Sum II.
Memory Usage: 11.6 MB, less than 63.64% of C online submissions for 4Sum II.
*/
struct hash
{
    int id;
    int val;
    UT_hash_handle hh;
};

int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size, int* nums3, int nums3Size, int* nums4, int nums4Size){
    // 先分別建立兩個組合矩陣，時間 2 * n ^２
    // 列表 1 放入 hashmap 中以供查找
    struct hash* map = NULL;
    for(int i = 0 ; i < nums1Size ; i++) {
        for(int j = 0 ; j < nums2Size ; j++) {
            struct hash *tmp;
            int sum = nums1[i] + nums2[j];
            HASH_FIND_INT(map, &sum, tmp);
            if(tmp == NULL) {
                tmp = (struct hash*)malloc(sizeof(struct hash));
                tmp->id = sum;
                tmp->val = 1;
                HASH_ADD_INT(map,id,tmp);
            }else {
                tmp->val++;
            }
        }
    }
    int cnt = 0;
    for(int i = 0 ; i < nums3Size ; i++) {
        for(int j = 0 ; j < nums4Size ; j++) {
            struct hash* tmp2;
            int sum2 = - (nums3[i] + nums4[j]);
            HASH_FIND_INT(map,&sum2,tmp2);
            if(tmp2 != NULL) {
                cnt += tmp2->val;
            }
        }
    }
    return cnt;
}

tmp[count++] = nums1[left1];
left1++;
continue;
}

if(nums1[left1] > nums2[left2])
{
tmp[count++] = nums2[left2];
left2 ++;
}
else if(nums1[left1] < nums2[left2])
{
tmp[count++] = nums1[left1];
left1 ++;
}
else
{
tmp[count++] = nums1[left1];
tmp[count++] = nums2[left2];
left1++;
left2++;
}
}

if((nums1Size + nums2Size) % 2 == 0)
{
// 中位數為 (nums1Size + nums2Size)/2 & (nums1Size + nums2Size)/2 - 1
return ((double)tmp[(nums1Size + nums2Size)/2] + (double)tmp[(nums1Size + nums2Size)/2 - 1] ) / 2;
}
else
{
// 中位數為 (nums1Size + nums2Size)/2
return (double)tmp[(nums1Size + nums2Size)/2];
}
}