Try   HackMD

Leetcode 紀錄 for C 語言

tags: C Leetcode

1. Two Sum - https://leetcode.com/problems/two-sum/
















/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    *returnSize = 2;
    int *ret = malloc(sizeof(int) * *returnSize);
    ret[0] = 0;
    ret[1] = 1;
    for (ret[0] = 0; ret[0] < numsSize - 1; ret[0]++) {
        for (ret[1] = ret[0] + 1; ret[1] < numsSize; ret[1]++)
            if ((*(nums + ret[0]) + *(nums + ret[1])) == target)
                return ret;
    }
    return ret;
}
  • 思路是
    1. 從第 1 個開始與第 2 ~ N 加看看
    2. 找到符合 target 的答案就 return
    3. 沒有的話就用下一個，直到 N - 1 為止

2. Add Two Numbers - https://leetcode.com/problems/add-two-numbers/



















































/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
        struct ListNode *out, *root;
        struct ListNode zero;
        zero.val = 0;
        zero.next = NULL;
        int acc;

        out = (struct ListNode*) malloc(sizeof(struct ListNode));
        root = out;
        acc = 0;

        while (!(l1  == &zero && l2 == &zero)) {
                acc = l1->val + l2->val + acc;
                out->val = acc % 10;
                acc /= 10;

                if (l1->next != NULL)
                    l1 = l1->next;
                else
                    l1 = &zero;
                if (l2->next != NULL)
                    l2 = l2->next;
                else
                    l2 = &zero;
                if (!(l1  == &zero && l2 == &zero)) {
                        out->next = (struct ListNode*) malloc(sizeof(struct ListNode));
                        out = out->next;
                } else {
                        out->next = NULL;
                }
        }
        
        if (acc > 0) {
                out->next = (struct ListNode*) malloc(sizeof(struct ListNode));
                out = out->next;
                out->val = acc % 10;
                out->next = NULL;
        }
    
        return root;
}
  • 思路是
    1. 用一個指標去紀錄開頭
    2. 另一個指標去做回傳結構體目前的位置
    3. l1 + l2 + 前一次的進位
    4. 只留下加減值的個位數存入
    5. 加減值除十獲得進位值給下一次使用
    6. 若有進位就在多加一位數

3. Longest Substring Without Repeating Characters - https://leetcode.com/problems/longest-substring-without-repeating-characters/




























#define ASCII_SIZE 256
int lengthOfLongestSubstring(char * s){
        char c_array[ASCII_SIZE], *cptr;
        int count, max, i, j;

        if (strlen(s) <= 1)
                return strlen(s);

        max = 0;
        for (i = 0; i < strlen(s); i++) {
                cptr = s + i;
                count = 0;
                memset(c_array, 0, ASCII_SIZE);
                while(*cptr != '\0') {
                        c_array[*cptr]++;
                        if (c_array[*cptr] > 1)
                                break;
                        count++;
                        cptr++;
                }
                if (max < count)
                        max = count;
        }
        return max;
}
  • 思路是
    1. 如果輸入字串小於等於一的話，回傳 0 或 1
    2. 從第一個開始看，如果遇到重複的字元結束，並計算該次的非重複字串長
    3. 往下一個再做一次，若比目前最長的長則更新
    4. 直到每個字串都被做過為止
    5. 最後回傳最長的

4. Median of Two Sorted Arrays - https://leetcode.com/problems/median-of-two-sorted-arrays/











































double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
        int arr[2000], arrSize;
        int i;
        double ret;

        arrSize = nums1Size + nums2Size;

        for (i = 0; i < arrSize; i++) {
                if (nums1Size > 0 && nums2Size > 0 && (*nums1 <= *nums2)) {
                        arr[i] = *nums1;
                        nums1++;
                        nums1Size--;
                } else if (nums1Size > 0 && nums2Size > 0 && (*nums1 > *nums2)) {
                        arr[i] = *nums2;
                        nums2++;
                        nums2Size--;
                } else if (nums1Size > 0 && nums2Size == 0) {
                        arr[i] = *nums1;
                        nums1++;
                        nums1Size--;
                } else if (nums1Size == 0 && nums2Size > 0) {
                        arr[i] = *nums2;
                        nums2++;
                        nums2Size--;
                }
        }

        if (arrSize == 1)
                ret = arr[0];
        else if (arrSize & 1)
                ret = arr[arrSize >> 1];
        else {
                ret = arr[arrSize >> 1] + arr[(arrSize >> 1) - 1];
                ret /= 2;
        }
        
        return ret;
}
  • 思路是
    1. 時間複雜度為 O(nums1Size + nums2Size)，所以只能用一個 for
    2. 一個個讀入放入陣列中，相當於做排序的過程，其規則如下：
      3. nums1 跟 nums2 都有內容，則拿小的進去陣列
      4. nums1 沒有了就放 nums2，反之亦然
    3. 最後算中位數
    • ps. 整個程式的時間複雜度有要求，所以就不在陣列組成的過程中去做運算後回傳，因為時間複雜度會變小。

8. String to Integer (atoi) - https://leetcode.com/problems/string-to-integer-atoi/

























































int myAtoi(char * s)
{
        int i, p, n, S, numed;
        long long out;
        // Serach '^'
        i = 0; p = 0; n = 0; S = 0; numed = 0;
        out = 0;
        while (*(s + i) != '\0') {
                if (*(s + i) != ' ')
                        break;
                i++;
        }

        // Serach '-' '+' '.'
        while (*(s + i) != '\0') {
                if (*(s + i) == '+') {
                        if (numed)
                                break;
                        p++;
                        S++;
                        i++;
                        continue;
                }
                if (*(s + i) == '-') {
                        if (numed)
                                break;
                        n++;
                        S++;
                        i++;
                        continue;
                }
                if (*(s + i) >= 'A' && *(s + i) <= 'Z' || *(s + i) >= 'a' && *(s + i) <= 'z' || *(s + i) == '.' || *(s + i) == ' ')
                        break;
                if (out > 2147483647 || out < -2147483648)
                        break;
                out *= 10;
                out += *(s + i) - '0';
                numed++;
                i++;
        }
        
        if (p > 1 || n > 1 || S > 1)
                return 0;
        if (n == 1)
                out *= -1;
        if (out > 2147483647)
                return 2147483647;
        if (out < -2147483648)
                return -2147483648;

        return out;
}
  • 思路是
    1. 先找出第一個非空白的字元
    2. 計算符號數量
    3. 檢查是不是數字
    4. 計算數字
    5. 檢查是不是有超出邊界
    6. 記得把負號放回去

20. Valid Parentheses - https://leetcode.com/problems/valid-parentheses/




















































bool isValid(char * s){
	char *sptr = s;
	char stack[5000];
	int top = 0;

	while (*sptr != '\0') {
		switch(*sptr) {
			case '(':
			case '[':
			case '{':
				stack[top] = *sptr;
				top++;
				break;
			case ')':
				if(top==0)
						return 0;
				else if(stack[top-1] == '('){
						top--;
				}
				else{
						return 0;
				}
				break;
			case ']':
				if(top==0)
						return 0;
				else if(stack[top-1] == '['){
						top--;
				}
				else{
						return 0;
				}
				break;
			case '}':
				if(top==0)
						return 0;
				else if(stack[top-1] == '{'){
						top--;
				}
				else{
						return 0;
				}
				break;
		}
		sptr++;
	}
	if(top != 0)
		return 0;

	return 1;
}
  • 思路是
    1. 成對的括號，數量一定是偶數
    2. ASCII 的符號會差一或差二，調整為全部差一
    3. 計算差值是否等於數量除二
    4. 如果數量是奇數或是差值不等於數量除二的話就回傳 False，反之回傳 True
    5. 用 Stack 去做先進後出

21. Merge Two Sorted Lists - https://leetcode.com/problems/merge-two-sorted-lists
















































/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
        struct ListNode* ret;
        int tmp;
        int len;
        int i,j;
        
        // Null Check
        if (list1 == NULL)
            return list2;
        if (list2 == NULL)
            return list1;
            
        // Merge two to one
        ret = list1;
        while(ret->next != NULL)
            ret = ret->next;
        ret->next = list2;
        
        // Sort
        ret = list1;
        len = 0;
        while(ret != NULL) {
            ret = ret->next;
            len++;
        }
        for (i = 0; i < len; i++) {
            ret = list1;
            for (j = 0; j < len - i - 1; j++) {
                if (ret->val > ret->next->val) {
                    tmp = ret->val;
                    ret->val = ret->next->val;
                    ret->next->val = tmp;
                }
                ret = ret->next;
            }
        }
        return list1;
}
  • 思路是
    1. Null 檢查
    2. 把兩個接再一起
    3. 氣泡排序整個

226. Invert Binary Tree - https://leetcode.com/problems/invert-binary-tree/



























/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* invertTree(struct TreeNode* root){
        struct TreeNode* tmp;
        
        // NULL Check
        if (root == NULL) return root;
        
        // Change
        tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        
        // Next node
        invertTree(root->left);
        invertTree(root->right);
        return root;
}
  • 思路是
    1. 檢查 NULL
    2. 交換左右樹 Pointer
    3. 利用遞迴做下一層的交換至結束

242. Valid Anagram - https://leetcode.com/problems/valid-anagram/























bool isAnagram(char * s, char * t)
{
        int c[26];
        
        if (strlen(s) != strlen(t))
                return 0;

        for (int i = 0; i < 26; i++)
                c[i] = 0;
        
        for (int i = 0; i < strlen(s); i++) {
                c[*(s + i) - 'a']++;
                c[*(t + i) - 'a']--;
        }

        for (int i = 0; i < 26; i++) {
                if (c[i] != 0)
                        return 0;
        }

        return 1;
}
  • 思路是
    1. 檢查 t & s 長度是否一致
    2. 計數 a-z 每個字母總和是否為 0

704. Binary Search - https://leetcode.com/problems/binary-search/


























int search(int* nums, int numsSize, int target){
        int i;
        
        if (numsSize == 1) {
                if (target == *(nums))
                        return 0;
                else
                        return -1;
        }
        
        for (i = 0; i < numsSize - 1; i ++) {
                if (target == *(nums + i))
                        return i;
                else if (target == *(nums + i + 1))
                        return i + 1;
                else if ((target > *(nums + i)) && (target < *(nums + i + 1)))
                        return -1;
        }
        
        return -1;
}
  • 思路是
    1. 如果 nums 等於左邊回傳左邊的 index，等於右邊回傳右邊的 index
    2. 介於中間回傳 -1

235. Lowest Common Ancestor of a Binary Search Tree - https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

































/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
        int index;
        
        if (p == q)
                return p;
        
        if ((root->val > p->val && root->val < q->val) ||
            (root->val < p->val && root->val > q->val))
                return root;
        
        if (root->val == p->val)
                return p;
        if (root->val == q->val)
                return q;
        
        if (root->val > p->val && root->val > q->val)
                return lowestCommonAncestor(root->left, p, q);
        
        if (root->val < p->val && root->val < q->val)
                return lowestCommonAncestor(root->right, p, q);
        
        return NULL;
}
  • 思路是
    1. 如果 p 等於 q 則回傳任一
    2. 如果 p 跟 q 位於 root 的兩側，則回傳 root
    3. 如果 root 等於 p 則回傳 p，等於 q 則回傳 q
    4. root 比 p, q 大的話往左找，反之往右找

125. Valid Palindrome - https://leetcode.com/problems/valid-palindrome/







































bool isPalindrome(char * s){
        char tmp_s[200000];
        int len, i;
        char *ptr, *tmp_ptr;
        
        ptr = s;
        tmp_ptr = tmp_s;
        while(*ptr != '\0') {
                if (*ptr >= 'a' && *ptr <= 'z') {
                        *tmp_ptr = *ptr;
                        tmp_ptr++;
                }
                if (*ptr >= '0' && *ptr <= '9') {
                        *tmp_ptr = *ptr;
                        tmp_ptr++;
                }
                if (*ptr >= 'A' && *ptr <= 'Z') {
                        *tmp_ptr = *ptr - 'A' + 'a';
                        tmp_ptr++;
                }
                ptr++;
                if (*ptr == '\0')
                        *tmp_ptr = *ptr;
        }
        len = strlen(tmp_s);
        if (len == 2)
                if (tmp_s[0] != tmp_s[1])
                        return 0;
        for (i = 0; i < len / 2; i++) {
                if (tmp_s[i] != tmp_s[len - i - 1])
                        return 0;
        }
        return 1;
}
  • 思路是
    1. 先保留字母跟數字
    2. 從頭跟尾比，一樣就繼續比，不一樣就回傳 False

141. Linked List Cycle - https://leetcode.com/problems/linked-list-cycle/




















/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
        int max_numbers = 10001, i;
        struct ListNode *tmp;
        
        tmp = head;
        for(i = 0; i < max_numbers; i++) {
               if (tmp == NULL)
                       return 0;
                tmp = tmp->next;
        }
        return 1;
}
  • 思路是
    1. 走訪如果走了 10001 個點後看到 NULL，代表沒有 loop

110. Balanced Binary Tree - https://leetcode.com/problems/balanced-binary-tree/






































/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void deepCalc(struct TreeNode* root, int *count) {
        if (root == NULL) return;
        if (root != NULL) *count += 1;
        if (root->left == NULL && root->right == NULL) return;
        if (root->left != NULL && root->right == NULL) deepCalc(root->left, count);
        if (root->left == NULL && root->right != NULL) deepCalc(root->right, count);
        if (root->left != NULL && root->right != NULL) {
                int l, r;
                l = 0; r = 0;
                deepCalc(root->left, &l);
                deepCalc(root->right, &r);
                if (l > r) *count += l;
                else *count += r;
        }
        return;
}

bool isBalanced(struct TreeNode* root){
        int left = 0, right = 0;
        
        if (root == NULL) return 1;
        
        deepCalc(root->left, &left);
        deepCalc(root->right, &right);
        
        printf("left = %d, right = %d\n", left, right);
        if (left - right < 2 && left - right > -2 && isBalanced(root->left) && isBalanced(root->right)) return 1;
        return 0;
}
  • 思路是
    1. 判斷樹根是否為 NULL，是的話為平衡樹
    2. 計算左右子樹各別的深度
    3. 若深度差小於二且子樹也是平衡樹的話回傳 True，反之為 False

278. First Bad Version - https://leetcode.com/problems/first-bad-version/

















// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) {
                int mid = left + (right - left) / 2;
                if (isBadVersion(mid)) {
                        right = mid;
                } else {
                        left = mid + 1;
                }
        }
        return left;
}
  • 思路是
    1. 從版本 1 到 n 中間開始找
    2. 如果 mid 為 true，則右邊更新為壞的，為 false，則最後好的為 mid，因此將 left 更新為 mid + 1
    3. 最後回傳 left 就可以了

17. Letter Combinations of a Phone Number - https://leetcode.com/problems/letter-combinations-of-a-phone-number





































class Solution(object):
        def addStr(self, stra, strb):
                ret = []
                for i in stra:
                        for j in strb:
                                ret.append(str(i) + str(j))
                return ret
        
        def letterCombinations(self, digits):
                """
                :type digits: str
                :rtype: List[str]
                """
                ret = [""]
                if len(digits) == 0:
                        return digits

                for i in digits:
                        if i == '2':
                                ret = self.addStr(ret, ['a', 'b', 'c'])
                        if i == '3':
                                ret = self.addStr(ret, ['d', 'e', 'f'])
                        if i == '4':
                                ret = self.addStr(ret, ['g', 'h', 'i'])
                        if i == '5':
                                ret = self.addStr(ret, ['j', 'k', 'l'])
                        if i == '6':
                                ret = self.addStr(ret, ['m', 'n', 'o'])
                        if i == '7':
                                ret = self.addStr(ret, ['p', 'q', 'r', 's'])
                        if i == '8':
                                ret = self.addStr(ret, ['t', 'u', 'v'])
                        if i == '9':
                                ret = self.addStr(ret, ['w', 'x', 'y', 'z'])

                return ret
  • 思路是
    1. 空的直接回傳
    2. 其餘的做字串串接後回傳，直到全部結束為止

67. Add Binary - https://leetcode.com/problems/add-binary/









class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        return bin(int(a, 2) + int(b, 2)).replace("0b", "")
  • 思路是
    1. add they after bin to dex
    2. dex to bin after added

206. Reverse Linked List - https://leetcode.com/problems/reverse-linked-list/



























/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* prev = NULL;
struct ListNode* next = NULL;
struct ListNode* reverseList(struct ListNode* head){
        struct ListNode* tmp;
        
        tmp = head;
        prev = NULL;
        next = NULL;
        
        if (head == NULL) return head;
        while (tmp != NULL) {
                next = tmp->next; // 先把下一個記起來
                tmp->next = prev; // 將自己反過來指向前一個
                prev = tmp;
                tmp = next;
        }
        
        return prev;
}
  • 思路是
    1. 記住當前的 Address 與 Next 的 Address
    2. Next 設定為前一個的 Address

169. Majority Element - https://leetcode.com/problems/majority-element/



















int majorityElement(int* nums, int numsSize){
        int res, cnt, i;
        res = nums[0];
        cnt = 1;
        
        // Boyer-Moore Voting Algorithm
        for (i = 1; i < numsSize; i++) {
            if (res == nums[i])
                cnt++;
            else if (cnt > 0)
                cnt--;
            else {
                res = nums[i];
                cnt++;
            }
        }
        return res;
}
  • 思路是
    1. Boyer–Moore majority vote algorithm(摩爾投票算法)
    2. 先記住第一開始投票結果
    3. 如果投的是不一樣的則減一，反之加一
    4. 當 cnt == 0 時，且投票結果不同時，則更換投票結果

733. Flood Fill - https://leetcode.com/problems/flood-fill
























void DFS(int** image, int x, int y, int old, int new, int r, int c)
{
	if (image[x][y] == old) {
		image[x][y] = new;
		if(x > 0)
			DFS(image, x - 1, y, old, new, r, c);
		if(x < r - 1)
			DFS(image, x + 1, y, old, new, r, c);
		if(y > 0)
			DFS(image, x, y - 1, old, new, r, c);
		if(y < c - 1)
			DFS(image, x, y + 1, old, new, r, c);
	}
}

int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int color, int* returnSize, int** returnColumnSizes){
	*returnSize = imageSize;
	*returnColumnSizes = imageColSize;
	if(image[sr][sc] == color)
		return image;
	DFS(image, sr, sc, image[sr][sc], color, imageSize, *imageColSize);
	return image;
}
  • 思路是
    1. 如果新顏色跟舊顏色一樣就不用改了
    2. 修改該位置的顏色
    3. 看看它的上下左右一個位置的點是不是原本也是同顏色，如果是的話，就改顏色
    4. 往周圍擴張到沒有為止

383. Ransom Note - https://leetcode.com/problems/ransom-note























bool canConstruct(char * ransomNote, char * magazine){
        long long Count[26] = {0};
        char *tmp;

        tmp = ransomNote;
        while (*tmp != '\0')
        {
                Count[*tmp - 'a']--;
                tmp++;
        }
        tmp = magazine;
        while (*tmp != '\0')
        {
                Count[*tmp - 'a']++;
                tmp++;
        }

        for (int i = 0; i < 26; i++)
                if (Count[i] < 0) return 0;

        return 1;
}
  • 思路是
    1. 總共只有 26 個字母
    2. 如果該字母出現在 ransomNote 中，就減一
    3. 如果該字母出現在 magazine 中，就加一
    4. 最後看每個字母的數量，如果為負表示 ransomNote 中的某個字母數量比 magazine 中多，則回傳 False

70. Climbing Stairs - https://leetcode.com/problems/climbing-stairs











int climbStairs(int n) {
    int arr[n], i;

    if (n < 2) return n;
    arr[0] = 1;
    arr[1] = 2;
    for (i = 2; i < n; i++)
        arr[i] = arr[i - 1] + arr[i - 2];
    return arr[i-1];
}
  • 思路是
    1. 每次只能走 1 or 2 步
    2. 所以 n 是 1或2 時，只有 1 或 1+1、2 = 2 兩種
    3. n = 3 開始是 (n - 2) 走兩步 跟 (n - 1) 走一步 的和
    4. 回傳最終點的走法

409. Longest Palindrome - https://leetcode.com/problems/longest-palindrome























int longestPalindrome(char* s) {
    int arr[52] = {0};
    int i, o, g;

    while (*s != '\0') {
        if ((*s >= 'a') && (*s <= 'z')) arr[*s - 'a']++;
        if ((*s >= 'A') && (*s <= 'Z')) arr[*s - 'A' + 26]++;
        s++;
    }

    o = 0; g = 0;
    for (i = 0; i < 52; i++) {
        if (arr[i] % 2) {
            g = 1;
            o += arr[i] - 1;
        } else {
            o += arr[i];
        }
    }

    return o + g;
}
  • 思路是
    1. 計數所有的字元數量
    2. 如果是偶數數量就全部保留
    3. 如果是奇數數量就留 N - 1 個，且記錄有奇數出現
    4. 最後回傳被留下的數量 + 是否有奇數出現

121. Best Time to Buy and Sell Stock - https://leetcode.com/problems/best-time-to-buy-and-sell-stock














int maxProfit(int* prices, int pricesSize){
        int i, j, min, max;

        max = 0;
        min = 2147483647;
        for (i = 0; i < pricesSize; i++) {
            if (*(prices + i) < min) min = *(prices + i);

            if ((*(prices + i) - min) > max) max = (*(prices + i) - min);
        }

        return max;
}
  • 思路是
    1. 紀錄最小的股票價格
    2. 當下賣掉的價格賺的比之前多的話，紀錄該賺的價值
    3. 最後回傳最大價值

53. Maximum Subarray - https://leetcode.com/problems/maximum-subarray

















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

    arr[0] = *nums;
    max = *nums;
    for (i = 1; i < numsSize; i++) {
        if ((arr[i - 1] + *(nums + i)) > *(nums + i))
            arr[i] = arr[i - 1] + *(nums + i);
        else
            arr[i] = *(nums + i);
        if (arr[i] > max) max = arr[i];
    }

    return max;
}
  • 思路是
    1. 首先先將 Max 設為 0
    2. 如果當前的數字比先前的總和 + 當前數字大，那就從當前數字開始重新計算
    3. 記住過程中最大的總和並回傳

876. Middle of the Linked List - https://leetcode.com/problems/middle-of-the-linked-list























/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* arr[100];
    int i = 0;

    if (head->next == NULL) return head;
    if (head->next->next == NULL) return head->next;

    for (;head->next != NULL; head = head->next) {
        arr[i] = head;
        i++;
    }

    i--;
    return arr[i/2 + 1];
}
  • 思路是
    1. ListNode Len 為 1 或 2 時，會抓到 Arr 中相對的位置，但後面結尾會錯
    2. 紀錄每個 ListNode 的 pointer 到 Arr 中，然後回傳數量/2的 Arr 位置

26. Remove Duplicates from Sorted Array - https://leetcode.com/problems/remove-duplicates-from-sorted-array
















int removeDuplicates(int* nums, int numsSize) {
    int c = 0;
    int i;
    int now = -101;

    for (i = 0; i < numsSize; i++) {
        if (*(nums + i) > now) {
            now = *(nums + i);
            *(nums + c) = *(nums + i);
            c++;
        }
    }

    return c;
}
  • 思路是
    1. Input 是已經 Sort 過的 Array
    2. Input 最小是 -100
    3. 如果目前的數字跟前一個不同的話，更新數字，且將數字填入陣列
    4. 過程中計數有多少個不同的數字

359. Logger Rate Limiter - https://leetcode.com/problems/logger-rate-limiter














































#define MAX_HASH_SIZE 2048

unsigned long hash(unsigned char *str)
{
  int c;
  unsigned long hash = 1234;
  while (c = *str++) {
    hash = (hash << 1) + hash + c;
  }

  return hash%MAX_HASH_SIZE;
}


typedef struct {
    int ts_last[MAX_HASH_SIZE];
} Logger;


Logger* loggerCreate() {
    Logger *obj = malloc(sizeof(Logger));
    for (int i=0; i < MAX_HASH_SIZE; i++)
      obj->ts_last[i] = -1000;
    return obj;
}

bool loggerShouldPrintMessage(Logger* obj, int timestamp, char* message) {
    if (obj->ts_last[hash(message)] + 10 <= timestamp) {
      obj->ts_last[hash(message)] = timestamp;
      return 1;
    }
    return 0;
}

void loggerFree(Logger* obj) {
    free(obj);
}

/**
 * Your Logger struct will be instantiated and called as such:
 * Logger* obj = loggerCreate();
 * bool param_1 = loggerShouldPrintMessage(obj, timestamp, message);
 
 * loggerFree(obj);
*/
  • 思路是
    1. 建立 Hash Table
    2. 設定 Hash Table Size
    3. 如果目前的時間比 前一次 + 10 大就回傳 True，並且更新時間
    4. 反之則回傳 False

7. Reverse Integer - https://leetcode.com/problems/reverse-integer
















#define INT_MAX 2147483647
#define INT_MIN -2147483648

int reverse(int x){
    int out;

    out = 0;
    while (x != 0) {
        if (out > INT_MAX/10 || out < INT_MIN/10) return 0;
        out = out * 10;
        out += x % 10;
        x /= 10;
    }
    return out;
}
  • 思路是
    1. 一個位數一個位數的移動
    2. 如果下一個數值添加進去會超過 INT 上限的話，回傳 0

190. Reverse Bits - https://leetcode.com/problems/reverse-bits










uint32_t reverseBits(uint32_t n) {
    char i;
    uint32_t out = 0;
    for (i = 0; i < 32; i++) {
        out = out << 1 | n & 1;
        n = n >> 1;
    }
    return out;
}
  • 思路是
    1. 一個位元一個位元的移動
    2. 移完 32 個位元後回傳

349. Intersection of Two Arrays - https://leetcode.com/problems/intersection-of-two-arrays























/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int counter1[1001] = {0};
    int counter2[1001] = {0};
    int i;

    *returnSize = 0;
    for (i = 0; i < nums1Size; i++)
        counter1[*(nums1 + i)]++;

    for (i = 0; i < nums2Size; i++)
        counter2[*(nums2 + i)]++;

    for (i = 0; i < 1001; i++)
        if (counter1[i] && counter2[i]) {
            nums1[*returnSize] = i;
            *returnSize = *returnSize + 1;
        }
    return nums1;
}
  • 思路是
    1. 紀錄兩個 array 中出現了那些數字
    2. 如果兩的都有共同數字的話，就紀錄該數字
    3. 最後回傳數量跟陣列

2119. A Number After a Double Reversal - https://leetcode.com/problems/a-number-after-a-double-reversal






bool isSameAfterReversals(int num) {
    if (num == 0) return 1;
    if (num % 10 == 0) return 0;
    return 1;
}
  • 思路是
    1. 只有一個 0 可以反轉
    2. 只要結尾不為 0 反轉就一定一樣長

1038. Binary Search Tree to Greater Sum Tree - https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree


























/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int sum;
struct TreeNode* bstToGst(struct TreeNode* root) {
    sum = 0;
    traverse(root);
    return root;
}
void traverse(struct TreeNode* root) {
    if (root) {
    printf("Now is %d\n", root->val);
        traverse(root->right);
        sum += root->val;
        root->val = sum;
        traverse(root->left);
    printf("\tNew is %d\n", root->val);
    printf("\t\t Return\n");
    }
}
  • 思路是
    1. 找到最右末的節點，然後開始往回加
    2. root val = curr max + right val
    3. left val = curr max + left val

12. Integer to Roman - https://leetcode.com/problems/integer-to-roman






















































































char* intToRoman(int num) {
    char *string, *ptr;
    string = (char*)malloc(100);
    ptr = string;
    while (num > 0) {
        if (num / 1000) {
            num -= 1000;
            *ptr = 'M';
            ptr++;
        } else if (num / 900) {
            num -= 900;
            *ptr = 'C';
            ptr++;
            *ptr = 'M';
            ptr++;
        } else if (num / 500) {
            num -= 500;
            *ptr = 'D';
            ptr++;
        } else if (num / 400) {
            num -= 400;
            *ptr = 'C';
            ptr++;
            *ptr = 'D';
            ptr++;
        } else if (num / 100) {
            num -= 100;
            *ptr = 'C';
            ptr++;
        } else if (num / 90) {
            num -= 90;
            *ptr = 'X';
            ptr++;
            *ptr = 'C';
            ptr++;
        } else if (num / 50) {
            num -= 50;
            *ptr = 'L';
            ptr++;
        } else if (num / 40) {
            num -= 40;
            *ptr = 'X';
            ptr++;
            *ptr = 'L';
            ptr++;
        } else if (num / 10) {
            num -= 10;
            *ptr = 'X';
            ptr++;
        } else if (num / 9) {
            num -= 9;
            *ptr = 'I';
            ptr++;
            *ptr = 'X';
            ptr++;
        } else if (num / 8) {
            num -= 8;
            *ptr = 'V'; ptr++;
            *ptr = 'I'; ptr++;
            *ptr = 'I'; ptr++;
            *ptr = 'I'; ptr++;
        } else if (num / 7) {
            num -= 7;
            *ptr = 'V'; ptr++;
            *ptr = 'I'; ptr++;
            *ptr = 'I'; ptr++;
        } else if (num / 6) {
            num -= 6;
            *ptr = 'V'; ptr++;
            *ptr = 'I'; ptr++;
        } else if (num / 5) {
            num -= 5;
            *ptr = 'V'; ptr++;
        } else if (num / 4) {
            num -= 4;
            *ptr = 'I'; ptr++;
            *ptr = 'V'; ptr++;
        } else if (num / 1) {
            num -= 1;
            *ptr = 'I'; ptr++;
        }
    }
    *ptr = 0;
    return string;
}
  • 思路是
    1. 列舉出所有可以用的組合並列印

13. Roman to Integer - https://leetcode.com/problems/roman-to-integer






































int romanToInt(char* s) {
    char *ptr = s;
    int sum = 0;

    while (*ptr) {
        if (*ptr == 'M') {
            sum += 1000;
        } else if (*ptr == 'D') {
            sum += 500;
        } else if (*ptr == 'C') {
            if (*(ptr + 1) == 'D' || *(ptr + 1) == 'M') {
                sum -= 100;
            } else {
                sum += 100;
            }
        } else if (*ptr == 'L') {
            sum += 50;
        } else if (*ptr == 'X') {
            if (*(ptr + 1) == 'L' || *(ptr + 1) == 'C') {
                sum -= 10;
            } else {
                sum += 10;
            }
        } else if (*ptr == 'V') {
            sum += 5;
        } else if (*ptr == 'I') {
            if (*(ptr + 1) == 'V' || *(ptr + 1) == 'X') {
                sum -= 1;
            } else {
                sum += 1;
            }
        }
        ptr++;
    }
    
    return sum;
}
  • 思路是：
    1. 列舉所有可能性

9. Palindrome Number - https://leetcode.com/problems/palindrome-number













bool isPalindrome(int x) {
    char nums[20], len, i;
    if (x < 0) return 0;
    sprintf(nums, "%d", x);
    len = strlen(nums);
    for (i = 0; i < len / 2; i++) {
        if (nums[i] != nums[len - i - 1])
            return 0;
    }
    printf("%s - %d\n", nums, len);
    return 1;
}
  • 思路是：
    1. 找出數值長度
    2. 頭尾比對
    3. 回傳結果

14. Longest Common Prefix - https://leetcode.com/problems/longest-common-prefix
























char* longestCommonPrefix(char** strs, int strsSize) {
    int len, i, j;
    char* cptr, rs;
    if (strsSize <= 0) return "";
    len = 200;
    for (i = 0; i < strsSize; i++) {
        if (strlen(strs[i]) < len) len = strlen(strs[i]);
    }
    cptr = (char*) malloc(len + 1);

    for (i = 0; i < len; i++) {
        rs = strs[0][i];
        for (j = 1; j < strsSize; j++) {
            if(strs[j][i] != rs) {
                cptr[i] = '\0';
                return cptr;
            }
        }
        cptr[i] = rs;
    }
    cptr[i] = '\0';
    return cptr;
}
  • 思路是：
    1. 找出最短長度
    2. 然後用最短長度開始做滑動視窗
    3. 找出相輔的內文後回傳

29. Divide Two Integers - https://leetcode.com/problems/divide-two-integers











int divide(int dividend, int divisor) {
    long num;
    if (dividend == 0) return 0;
    if (dividend == divisor) return 1;
    if (dividend < 0 && divisor < 0){
        dividend++;
    }
    num = dividend / divisor;
    return num;
}
  • 思路是如果是負數的頂的話，除完會是最大值（Connor case)
  • 之後直接除（但這樣不符合條件，因為不能用 long、除法、乘法、取餘數）

66. Plus One - https://leetcode.com/problems/plus-one
























int* plusOne(int* digits, int digitsSize, int* returnSize) {
    // Allocate memory for the result array
    int* result = (int*)malloc((digitsSize + 1) * sizeof(int));
    int carry = 1;  // Start with the plus one carry

    // Traverse the digits array from the last element
    for (int i = digitsSize - 1; i >= 0; i--) {
        int sum = digits[i] + carry;
        result[i + 1] = sum % 10;
        carry = sum / 10;
    }

    // If there's a carry left, we need to place it at the start of the result array
    if (carry) {
        result[0] = carry;
        *returnSize = digitsSize + 1;
        return result;
    } else {
        *returnSize = digitsSize;
        // Shift result by one to the right since there was no carry overflow
        return result + 1;
    }
}
  • 思路是：
    • 從最末位開始計算，每十進位，最後看有沒有進位決定要回傳第零個還是第一個

3110. Score of a String - https://leetcode.com/problems/score-of-a-string












int scoreOfString(char* s) {
    char *ptr;
    int sum;
    sum = 0;
    ptr = s;
    while (*(ptr + 1) > 0) {
        sum += abs(*(ptr + 1) - *(ptr + 0));
        ptr++;
    }
    return sum;
}
  • 思路是：
    1. 將前後兩個的距離加總起來

2379. Minimum Recolors to Get K Consecutive Black Blocks - https://leetcode.com/problems/minimum-recolors-to-get-k-consecutive-black-blocks






























int minimumRecolors(char* blocks, int k) {
    int count = 0;
    int min_recolors = k;  // 初始化为最大的可能值，即 k
    int current_recolors = 0;
    char *ptr = blocks;

    // 初始化第一个窗口的白色块数
    for (int i = 0; i < k; i++) {
        if (blocks[i] == 'W') {
            current_recolors++;
        }
    }
    min_recolors = current_recolors;

    // 使用滑动窗口遍历整个字符串
    for (int i = k; blocks[i] != '\0'; i++) {
        if (blocks[i - k] == 'W') {
            current_recolors--;
        }
        if (blocks[i] == 'W') {
            current_recolors++;
        }
        if (current_recolors < min_recolors) {
            min_recolors = current_recolors;
        }
    }

    return min_recolors;
}
  • 思路是：
    1. 開一個滑動視窗
    2. 滑過去

543. Diameter of Binary Tree - https://leetcode.com/problems/diameter-of-binary-tree































/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// Helper function to calculate depth and update diameter
int deep(struct TreeNode* root, int* diameter) {
    if (root == NULL) return 0;

    int leftDepth = deep(root->left, diameter);
    int rightDepth = deep(root->right, diameter);

    // Update the diameter
    if (leftDepth + rightDepth > *diameter) {
        *diameter = leftDepth + rightDepth;
    }

    // Return the depth of the current node
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

int diameterOfBinaryTree(struct TreeNode* root) {
    int diameter = 0;
    deep(root, &diameter);
    return diameter;
}
  • 思路是：
    1. 如果該節點是空的就回傳 0
    2. 一路找到最深的左右子樹合後記錄最大的

448. Find All Numbers Disappeared in an Array - https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array





























/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
    int* array = (int*)malloc((numsSize + 1) * sizeof(int));  // Allocate memory for array
    int* ret = (int*)malloc(numsSize * sizeof(int));
    int* ptr = ret;
    memset(array, 0, (numsSize + 1) * sizeof(int));  // Initialize the array with 0s

    // Mark the numbers that appear in the array
    for (int i = 0; i < numsSize; i++) {
        array[nums[i]]++;
    }

    *returnSize = 0;

    // Find the numbers that did not appear in the array
    for (int i = 1; i <= numsSize; i++) {
        if (array[i] == 0) {
            *ptr = i;
            ptr++;
            (*returnSize)++;
        }
    }

    free(array);  // Free the allocated memory for array
    return ret;
}
  • 思路是：
    1. 用 hash table 去紀錄 1 ~ n 有哪些出現過
    2. 在把缺的找出來

118. Pascal's Triangle - https://leetcode.com/problems/pascals-triangle


























/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
    int i, j;
    int **ret;

    *returnSize = numRows;
    ret = (int**)malloc(sizeof(int*) * numRows);
    *returnColumnSizes = (int*)malloc(sizeof(int) * numRows);

    for (i = 0; i < numRows; i++) {
        (*returnColumnSizes)[i] = i + 1;
        ret[i] = (int*)malloc(sizeof(int) * (i + 1));
        ret[i][0] = 1;
        ret[i][i] = 1;
        for (j = 1; j < i; j++) {
            ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
        }
    }

    return ret;
}
  • 思路是：
    1. 頭尾都是一
    2. 每多一層就多一個
    3. 中間的數值是上一層的鄰近兩個的和
    4. 回傳陣列

509. Fibonacci Number - https://leetcode.com/problems/fibonacci-number
























// Sol 1
int arr[31];
int fib(int n){
    arr[0] = 0;
    arr[1] = 1;
    for (int i = 2; i < n + 1; i++) {
        arr[i] = arr[i - 2] + arr[i - 1];
    }
    return arr[n];
}

// Sol 2
int fib(int n) {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default:
            return fib(n - 1) + fib(n - 2);
    }
    return 0;
}
  • 思路是：
    1. 從第二個開始都是前兩個的和
    2. 因為該提是 DP 所以用這樣子算 - sol 1
    3. 可以用遞迴 - sol 2

1190. Reverse Substrings Between Each Pair of Parentheses - https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses

















































// 反转字符串的子串 [start, end)
void reverseSubstring(char* s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
}

// 删除字符串中的特定字符
void removeChar(char* s, char c) {
    char* read = s;
    char* write = s;
    while (*read) {
        if (*read != c) {
            *write = *read;
            write++;
        }
        read++;
    }
    *write = '\0';
}

// 反转每对括号之间的子字符串
char* reverseParentheses(char* s) {
    int len = strlen(s);
    int* stack = (int*)malloc(len * sizeof(int));
    int top = -1;

    // 遍历字符串并处理括号
    for (int i = 0; i < len; i++) {
        if (s[i] == '(') {
            stack[++top] = i;
        } else if (s[i] == ')') {
            reverseSubstring(s, stack[top] + 1, i - 1);
            top--;
        }
    }

    // 移除所有括号
    removeChar(s, '(');
    removeChar(s, ')');

    free(stack);
    return s;
}
  • 思路是
    1. 記得反轉的位址
    2. 反轉
    3. 移除括號

2108. Find First Palindromic String in the Array - https://leetcode.com/problems/find-first-palindromic-string-in-the-array



















char isR(char* s) {
    int l = strlen(s);
    int i;
    for (i = 0; i < l/2; i++) {
        if (*(s + i) != *(s + l - 1 - i)) return 0;
    }
    return 1;
}

char* firstPalindrome(char** words, int wordsSize) {
    int i;
    char *ptr;
    for (i = 0; i < wordsSize; i++) {
        ptr = *(words + i);
        if(isR(ptr)) return ptr;
    }
    return "";
}
  • 思路是：
    1. 找反轉的字串回傳函數一個
    2. 如果都沒找到就回傳空 “”

1119. Remove Vowels from a String - https://leetcode.com/problems/remove-vowels-from-a-string































char * removeVowels(char * s){
    int l;
    char* ret;
    char* ptr;
    char* ptrr;
    ptr = s;
    l = strlen(s);
    ret = malloc(sizeof(char) * (l + 1));
    ptrr = ret;
    while (*ptr != 0) {
        switch(*ptr) {
            case 'a':
            case 'e':
            case 'i':
            case 'o':
            case 'u':
                ptr++;
                continue;
        }
        *ptrr = *ptr;
        ptr++;
        ptrr++;
    }
    *ptrr = *ptr;
    return ret;
}
  • 思路是：
    1. 掃過去，如果是 aeiou 就跳過不複製

231. Power of Two - https://leetcode.com/problems/power-of-two











bool isPowerOfTwo(int n) {
    int count;
    count = 0;
    while (n > 0) {
        count += n & 1;
        n = n >> 1;
    }
    if (count == 1) return 1;
    return 0;
}
  • 思路是：
    1. 只能有一個 bit 是 1

268. Missing Number - https://leetcode.com/problems/missing-number







int missingNumber(int* nums, int numsSize) {
    int sum = (numsSize * (numsSize + 1)) / 2;
    for (int i = 0; i < numsSize; i++)
        sum -= *(nums + i);
    return sum;
}
  • 思路是：
    1. 算出和，然後把已經有的數字減掉
    2. 回傳差

100. Same Tree - https://leetcode.com/problems/same-tree


















/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL) return 1;
    if (p != NULL && q == NULL) return 0;
    if (p == NULL && q != NULL) return 0;
    if (p->val == q->val) {
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
    return 0;
}
  • 思路是：
    1. 一個節點一個節點的比
    2. 不同就回傳 false
    3. 相同就 true

997. Find the Town Judge - https://leetcode.com/problems/find-the-town-judge






















int findJudge(int n, int** trust, int trustSize, int* trustColSize) {
    int trustMe[n + 1], trustOthers[n + 1];     //Hash tables
    int ans = -1;

    for(int i = 0; i < n + 1; i++){ //Initialize hash tables to all zeros
        trustMe[i] = 0;
        trustOthers[i] = 0;
    }

    for(int i = 0; i < trustSize; i++){ //ai trusts bi
        trustMe[trust[i][1]]++;     //Count the number that others trust me
        trustOthers[trust[i][0]]++; //Count the number that I trust others
    }

    //Find the town judge
    for(int i = 1; i < n + 1; i++){
        if(trustMe[i] == n - 1 && trustOthers[i] == 0)  //Everybody trusts me but I trust nobody
            ans = i;
    }
    return ans;
}
  • 思路是
    1. 計算相信的，如果都相信就回傳
    2. 如果沒有都相信就 -1

2864. Maximum Odd Binary Number - https://leetcode.com/problems/maximum-odd-binary-number

  • 思路是：
    1. 奇數一定最後一個 bit 為一
    2. 剩下的一補前面

389. Find the Difference - https://leetcode.com/problems/find-the-difference













char findTheDifference(char* s, char* t) {
    int ret, i;
    ret = 0;
    for (i = 0; i < strlen(s); i++) {
        ret += *(s + i);
    }

    for (i = 0; i < strlen(t); i++) {
        ret -= *(t + i);
    }
    return abs(ret);
}
  • 思路是：
    1. 因為只會有一個字元不一樣，所以算出兩字串差回傳即可

1740. Find Distance in a Binary Tree - https://leetcode.com/problems/find-distance-in-a-binary-tree

















































/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// Function to find the Lowest Common Ancestor (LCA) of two given nodes
struct TreeNode* findLCA(struct TreeNode* root, int p, int q) {
    if (root == NULL || root->val == p || root->val == q)
        return root;

    struct TreeNode* leftLCA = findLCA(root->left, p, q);
    struct TreeNode* rightLCA = findLCA(root->right, p, q);

    if (leftLCA && rightLCA)
        return root;

    return (leftLCA != NULL) ? leftLCA : rightLCA;
}

// Function to find the distance from the root to a given node
int findDistanceFromRoot(struct TreeNode* root, int val, int distance) {
    if (root == NULL)
        return -1;

    if (root->val == val)
        return distance;

    int leftDistance = findDistanceFromRoot(root->left, val, distance + 1);
    if (leftDistance != -1)
        return leftDistance;

    return findDistanceFromRoot(root->right, val, distance + 1);
}

// Function to find the distance between two given nodes
int findDistance(struct TreeNode* root, int p, int q) {
    struct TreeNode* lca = findLCA(root, p, q);
    if (lca == NULL)
        return -1;

    int distanceP = findDistanceFromRoot(lca, p, 0);
    int distanceQ = findDistanceFromRoot(lca, q, 0);

    return distanceP + distanceQ;
}
  • 思路是：
    1. 找出 root 介於 p q 之間的 root
    2. 從新的 root 開始算到 p q 個別的長度相加

414. Third Maximum Number - https://leetcode.com/problems/third-maximum-number























int thirdMax(int* nums, int numsSize) {
    long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == first || nums[i] == second || nums[i] == third) {
            continue;
        }
        
        if (nums[i] > first) {
            third = second;
            second = first;
            first = nums[i];
        } else if (nums[i] > second) {
            third = second;
            second = nums[i];
        } else if (nums[i] > third) {
            third = nums[i];
        }
    }
    
    return (third == LONG_MIN) ? first : third;
}
  • 思路是：
    1. 如果有比較大的就往後移，然後取代
    2. 回傳第三大的

2418. Sort the People - https://leetcode.com/problems/sort-the-people/































// Swap function to swap elements in the heights and names arrays
void swap(int *a, int *b, char **s1, char **s2) {
    int temp = *a;
    *a = *b;
    *b = temp;

    char *temp_str = *s1;
    *s1 = *s2;
    *s2 = temp_str;
}

char** sortPeople(char** names, int namesSize, int* heights, int heightsSize, int* returnSize) {
    if (namesSize != heightsSize) {
        // If the sizes do not match, return NULL
        *returnSize = 0;
        return NULL;
    }

    // Bubble sort to sort names and heights based on heights in descending order
    for (int i = 0; i < heightsSize - 1; i++) {
        for (int j = 0; j < heightsSize - i - 1; j++) {
            if (heights[j] < heights[j + 1]) {
                swap(&heights[j], &heights[j + 1], &names[j], &names[j + 1]);
            }
        }
    }

    *returnSize = namesSize;
    return names;
}
  • 思路是
    1. 氣泡排序

3173. Bitwise OR of Adjacent Elements - https://leetcode.com/problems/bitwise-or-of-adjacent-elements













/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* orArray(int* nums, int numsSize, int* returnSize) {
    int i;
    *returnSize = numsSize - 1;
    int* ret = (int*)malloc(sizeof(int) * *returnSize);
    for (i = 0; i < numsSize - 1; i++) {
        ret[i] = nums[i] | nums[i + 1];
    }
    return ret;
}
  • 思路是：
    1. 長度一定是 n - 1
    2. 然後兩個兩個進行 OR 運算即可

2220. Minimum Bit Flips to Convert Number - https://leetcode.com/problems/minimum-bit-flips-to-convert-number











int minBitFlips(int start, int goal) {
    int a, c;
    a = start ^ goal;
    c = 0;
    while (a > 0) {
        c += (a & 1);
        a = a >> 1;
    }
    return c;
}
  • 思路是：
    1. 把需要轉換的 bit 抓出來
    2. 計算數量

58. Length of Last Word - https://leetcode.com/problems/length-of-last-word











int lengthOfLastWord(char* s) {
    char *now, *past;

    now = strtok(s, " ");
    while (now != NULL) {
        past = now;
        now = strtok(NULL, " ");
    }
    return strlen(past);
}
  • 思路是
    1. 用空白隔開
    2. 印出最後一個字串長度

101. Symmetric Tree - https://leetcode.com/problems/symmetric-tree







































/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

long sum_L(struct TreeNode* root, int w) {
    long ret = 0;
    ret = root->val;
    if (root->left == NULL && root->right == NULL) return ret;
    if (root->left != NULL)
        ret += root->left->val * (w+2) + sum_L(root->left, w + 1) + 1;
    if (root->right != NULL)
        ret += root->right->val * (w+4) + sum_L(root->right, w + 2) + 2;
    return ret;
}
long sum_R(struct TreeNode* root, int w) {
    long ret = 0;
    ret = root->val;
    if (root->left == NULL && root->right == NULL) return ret;
    if (root->left != NULL)
        ret += root->left->val * (w+4) + sum_R(root->left, w + 2) + 2;
    if (root->right != NULL)
        ret += root->right->val * (w+2) + sum_R(root->right, w + 1) + 1;
    return ret;
}
bool isSymmetric(struct TreeNode* root) {
    if (root->left == NULL && root->right == NULL) return 1;
    if (root->left == NULL && root->right != NULL) return 0;
    if (root->left != NULL && root->right == NULL) return 0;
    // calc total
    printf("L:%ld, R:%ld\n", sum_L(root->left, 1), sum_R(root->right, 1));
    if (sum_L(root->left, 1) == sum_R(root->right, 1)) return 1;
    return 0;
}
  • 思路是
    1. 計算左右子樹總和，並且給予左右邊不同的權重
    2. 比較總和後，相等為鏡像樹

28. Find the Index of the First Occurrence in a String - https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string


































int strStr(char* haystack, char* needle) {
    if (*needle == '\0') { // 如果 needle 是空字符串，返回 0
        return 0;
    }

    char *ptr_h = haystack;
    char *ptr_n = needle;
    int len = 0; // 记录当前位置

    while (*ptr_h != '\0') {
        // 如果当前字符匹配 needle 的首字符，尝试匹配整个字符串
        if (*ptr_h == *ptr_n) {
            char *start_h = ptr_h; // 保存 haystack 开始匹配的位置
            char *start_n = ptr_n; // 保存 needle 开始匹配的位置

            // 开始逐字符匹配
            while (*start_h != '\0' && *start_n != '\0' && *start_h == *start_n) {
                start_h++;
                start_n++;
            }

            // 如果 needle 全部匹配完，返回匹配的起始位置
            if (*start_n == '\0') {
                return len;
            }
        }

        ptr_h++; // 前进到 haystack 的下一个字符
        len++;   // 记录当前的索引
    }

    return -1; // 没有找到匹配，返回 -1
}
  • 思路是
    1. 找尋開頭
    2. 如果找完了就可以看是否成立

35. Search Insert Position - https://leetcode.com/problems/search-insert-position










int searchInsert(int* nums, int numsSize, int target) {
    int i;

    if (target <= *nums) return 0;
    for (i = 1; i < numsSize; i++) {
        if ((target > *(nums + i - 1)) && (target <= *(nums + i))) return i;
    }
    return i;
}
  • 思路是
    1. 走訪一次，直接插入

83. Remove Duplicates from Sorted List - https://leetcode.com/problems/remove-duplicates-from-sorted-list






















/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL) return head;
    if (head->next == NULL) return head;
    struct ListNode* ptr;

    ptr = head;
    while (ptr != NULL) {
        if (ptr->next == NULL) {ptr = NULL; continue;}
        if (ptr->val == ptr->next->val) ptr->next = ptr->next->next;
        else
           ptr = ptr->next;
    }
    return head;
}
  • 思路是
    1. 如果下一個跟當前的一樣，把當前的下一個改為下下個
    2. 若改完之後，還是一樣就重複 1
    3. 若不同就在往後做

ex.
  • 思路是
    1.
Last changed by 
 
小春
0
1457
Published on HackMD