# Leetcode 紀錄 for C 語言
###### tags: `C` `Leetcode`
## 1. Two Sum - https://leetcode.com/problems/two-sum/
```c=
/**
* 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/
* https://onlinegdb.com/q5CPY2Qrl
```c=
/**
* 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/
```c=
#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/
```c=
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，反之亦然
5. 最後算中位數
* ps. 整個程式的時間複雜度有要求，所以就不在陣列組成的過程中去做運算後回傳，因為時間複雜度會變小。
## 8. String to Integer (atoi) - https://leetcode.com/problems/string-to-integer-atoi/
```c=
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/
```c=
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
```c=
/**
* 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/
```c=
/**
* 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/
```c=
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/
```c=
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/
```c=
/**
* 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/
```c=
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/
```c=
/**
* 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/
```c=
/**
* 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/
```c=
// 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
```c=
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/
```c=
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/
```c=
/**
* 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/
```c=
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
```c=
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
```c=
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
```c=
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
```c=
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
```c=
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
```c=
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
```c=
/**
* 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
```c=
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
```c=
#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
```c=
#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
```c=
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
```c=
/**
* 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
```c=
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
```c=
/**
* 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
```c=
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
```c=
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
```c=
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
```c=
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
```c=
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
```c=
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
```c=
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
```c=
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
```c=
/**
* 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
```c=
/**
* 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
```c=
/**
* 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
```c=
// 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
```c=
// 反转字符串的子串 [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
```c=
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
```c=
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
```c=
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
```c=
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
```c=
/**
* 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
```c=
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
```c=
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
```c==
/**
* 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
```c=
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/
```c=
// 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
```c=
/**
* 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
```c=
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
```c=
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
```c=
/**
* 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
```c=
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
```c=
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
```c=
/**
* 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.
```c=
```
* 思路是
1.
Sign in with Wallet
Connect another wallet