[217] Contains Duplicate

給一個數字的array
判斷裡面是否有重覆的數字
不多說, qsort給它開下去啊!
然後好像也可以用hash做吧.
用hash做code就變得很長
為什麼要這樣虐待自己呢 XD～

Contains Duplicate
int compare(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}

bool containsDuplicate(int* nums, int numsSize) {
    qsort(nums,numsSize,sizeof(int), compare);  
    for (int i=0;i<numsSize-1;i++)
        if (nums[i]== nums[i+1])
            return true;
    return false;
}

[344] Reverse String

字串反轉
做為年假完恢復信心的題目(?)
題目沒寫要在同一個array內完成,
於是..............
XD?!

Reverse String
char* reverseString(char* s) {
    int length = strlen(s);
    if (length < 2)
        return s;
    char *ret = malloc(sizeof(char)*(length+1));
    for (int i = 0; i< length; i++)
        ret[i] = s[length-1-i];
    ret[length]=0;
    return ret;
}

寫在同一個array好像也挺快
是真正的easy XD
多了內建的swap即可.

char* reverseString(char* s) {
    int length = strlen(s);
    if (length < 2)
        return s;
    for (int i = 0; i< (length/2); i++)
    {
        char tmp;
        tmp = s[length-1-i];
        s[length-1-i] = s[i];
        s[i] = tmp;
    }
    return s;
}

20230617 更新

看來這題目也有更新了！輸入參數多了字串長度。

把迴圈裡算尾巴index的部分也先指定起來， j - - 減減之後速度似乎有變快。

不用先去讀 i 的值再來減？！

void reverseString(char* s, int sSize){
    char tmp;
    int middle = sSize/2;
    for (int i=0, j=sSize-i-1;i<middle;i++,j--)
    {
        tmp=s[i];
        s[i]=s[j];
        s[j]=tmp;
    }
}

20260206 更

沒想到～我又回來寫了XD

void swap(char* a, char* b){

char tmp = *a;

*a = *b;

*b = tmp;

}

void reverseString(char* s, int sSize) {

for (int i=0; i<sSize/2; i++)

{

swap ( &s[i], &s[sSize-1-i]);

}

return;

}

[20260226 再再更]

原來不能用strlen(s) 之後再去printf 它！

因為事實上compiler 直接忽略它了QQ 改成以前從來沒懂過使用時機的volatile 就會發現！

volatile int len = strlen(s); 

這樣一行就會runtime error了. 也就是s傳進來的時候有可能沒有自帶結束自元 \0

strlen 的寫法是一直讀到\0 為止 , 沒加printf 就沒錯是因為被優化了！根本沒去執行啊啊啊

這種本來就知道的事情竟然到了2026年真的寫到才看到問題Orz 感覺有什麼地方怪怪的Orz

Gemini 建議用pointer 寫法=_=

void reverseString(char* s, int sSize) {

int l=0;

int r=sSize-1;

while (l<r){

char tmp = s[l];

s[l++]= s[r];

s[r--]= tmp;

// l++;

// r--;

}

}

[136] Single Number

有一個array裡面的每個數字都出現兩次, 只有一個只出現一次,
找出那個只出現一次的數字,
而且時間複雜度要求是linear , 並且不要使用額外的memory
想半天, 想說不能多用memory, 又要線性時間內解決,
以為通通加起來, 加一半再減一半應該會剩下那個單獨的數字,
結果不是XD
遇到有負數的就始亡 XD
先全部變成正數也不行, 因為可能會把單獨的負數也變正了,
那答案也不會對.
看了討論原來要用XOR !!!
瞬間覺得沒意思= =
不喜歡這種考bit operation的小tricky
就是前面抱怨過的code會完全看不懂啊啊啊
知道這種小tricky了不起啊～（捏碎滑鼠）
（不好意思, 人家就是比妳了不起啊哈哈哈哈哈奔入雨中）

Single Number
int singleNumber(int* nums, int numsSize) {
    int i,ret=0;
    for (i=0;i<numsSize;i++)
        ret ^= nums[i];
    return ret;
}

[20251005]

只是想更一下我有看完XOR 說明之後再自己寫一次XD

[283] Move Zeroes

給一個array
把零都向右堆
非零的向前排列
本來以為跟bubble sort 一樣
做完發現如果第一輪的第一個item還是0,
它就永遠做不到了XD
笨QQ
改採掃到第一個零之後, 就往後找第一個非零, 跟它換

Move Zeroes
swap版:
(奇怪別人怎麼都只要一到三行, 我的卻長這麼醜 囧)
void swap(int *a, int *b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
   
}

void moveZeroes(int* nums, int numsSize) {
    int i, j ;
    int zerocount = 0;

    for (i=0; i<numsSize-1; i++)
    {
        if (nums[i]==0)
        {
            for(j=i+1;j<numsSize;j++)
                if(nums[j]!=0)
                {
                    swap(&nums[i],&nums[j]);
                    break;
                }
        }          
    }
}

抄別人的版本: 囧
void moveZeroes(int* nums, int numsSize) {
    int i, idx=0;
    for(int i = 0; i < numsSize; i++)
    {
        if(nums[i] != 0)
            nums[idx++] = nums[i];
    }
    for(int i = idx; i < numsSize; i++)
        nums[i] = 0;

}
原本怎麼想都不懂Orz 我是不是腦殘 Orz
用另一個index來記錄目前的非零值,
也就是說第一輪掃過去, 把非零的從頭開始填進去
反正最後面只要全部塞零就好
為什麼一開始我看不懂呢T_T
豪 ～～～～～～笨啊~~~~~~~~~~~~~~~(奔入暴雨中)

[20240714 更新]

哦！！！我竟然又感覺到自己的進步了！！！

（雖然一開始錯的地方一模模一樣樣 XD）

寫出了，以前的我，抄別人的那個版本，也就是說，我變成被抄的那個人了嗎姆襪哈哈哈哈哈哈！！！！！

void moveZeroes(int* nums, int numsSize) {

int l=0;

for (int i=0;i<numsSize; i++)

{

if (nums[i]!= 0)

nums[l++]= nums[i];

}

for (int j=l;j<numsSize;j++)

nums[j] = 0;

return;

}

[20251101 更新]

哦原本想要跳著寫～結果一場悲劇。先寫了個暴力法，結果跟hint 講的一樣，寫完暴力法就知道解答了~__~

void moveZeroes(int* nums, int numsSize) {

int idx = 0 ;

for (int i=0 ; i<numsSize; i++)

if (nums[i]!= 0)

nums[idx++]=nums[i];

while (idx <numsSize)

nums[idx++]=0;

}

[20251106] 沒想到又更了

看到室友寫了swap版本, 覺得不行我也要參透一下XD 所以

void swap (int *a, int *b)

{

int tmp = *a;

*a = *b;

*b=tmp;

}

void moveZeroes(int* nums, int numsSize) {

int l=0;

for (int r=0; r<numsSize; r++)

{

if (nums[r]!=0)

swap(&nums[l++], &nums[r]);

}

return;

}

[204] Count Primes

雖說也是先看了找質數的演算法的說明才寫的
但速度還是有點快的驚人 囧
是已經太習慣超級慢寫法了嗎 XD
點一, 只要找平方根以內的就好
（為什麼呢～數學真難參透啊）
點二, 先弄一個全部設成true的array
然後從2, 3,.....開始, 將質數的倍數都設成false
最後再找出這個array裡面有幾個true, 也就是有幾個質數
The End.


Count Primes
int countPrimes(int n) {
    if (n<=2)
        return 0;
    bool *isPrime = malloc(sizeof(bool)*(n+1));
    memset(isPrime, true, n);
    isPrime[0] = isPrime[1] = false;
    int i,j;
    for (i=2;i<sqrt(n);i++)
        if(isPrime[i])
            for (j=i*i;j<n;j+=i)
                isPrime[j]=false;
    int count =1;
    for(i=3;i<n;i+=2)
        if (isPrime[i]==true)
            count++;
   return count;
}

20230925 update

時隔多年，寫出了奇怪的東西？！果不其然，忘記可以用 sqrt 來加速了

但好像因為想用count 直接紀錄，而不是最後再去算沒被clear掉的有幾個(等於質數個數）

所以變的怪怪的XD 先降子好了XDDDD(光速逃）

int countPrimes(int n){

if (n==0 || n==1)

return 0;

int *check =calloc (n+1, sizeof(int));

int count=0;

for (int i=2; i<n+1;i++)

{

if (check[i]== 0)

{

if (i==n)

break;

count++;

int j=i;

for (int j=i; j<n+1;j+=i)

check[j]= -1;

}

}

return count;

}

[62] Unique Paths

腦袋裝漿糊.........
完全不會DP的精神了 囧
給一個m跟n 象徵 m x n 的棋盤格
若起始點在最左上角(比方說0,0)
只能向右或是向下走,
問走到最右下角(比方說m,n)的走法共有幾種不同走法
注意之一是m,n 是從1開始,
和C的array從0 開始不同;
注意之二就是......
應該要存前一個round算出來的步數啊啊啊
雖然我知道但是怎麼一直想到費伯那器,
然後就在那邊 steps(m-1, n) + steps(m, n-1)
遞迴到天荒地老啊啊啊啊啊
到底我有沒有搞懂DP呢感覺沒有啊XD~

Unique Paths
int uniquePaths(int m, int n) {
    int *res = malloc(sizeof(int)*n);
    int i,j;
    for(j=0;j<n;j++)
        res[j]=1;

    for(i=1;i<m; i++)
        for(j=1;j<n;j++)
            res[j] = res[j-1] + res[j];
    return res[n-1];  
}

[53] Maximum Subarray

給一個array, 回傳subarray裡面的相加最大值
一開始想的覺得沒什麼大問題
寫出來卻一直不對
看了一下別人的寫法, 好像差不多啊XD
結果就差在一個先加還是後加, 結果就天差地遠QQ
唉
沒有時間自怨自艾了前往下一題吧Orz
int maxSubArray(int* nums, int numsSize) {

    int i, sum,max;
    sum =max = nums[0];
    for (i=1;i<numsSize;i++)
    {
        sum+=nums[i];
        sum = (sum>nums[i])?sum:nums[i];
        if (sum > max)
            max = sum;
    }
    return max;
}

[121] Best Time to Buy and Sell Stock

暴力法世界無敵慢 XD （廢話XD）
讓我想想 DP 可以怎麼寫 QQ
給一個array代表每天的股價
請找出最賺錢的賣法
也就是先出現的數字是買的價格, 後面賣的價格相減之後要達到最大.

Best Time to Buy and Sell Stock

int maxProfit(int* prices, int pricesSize) {

    int i,j, max = 0;

    

    for (i=0; i<pricesSize-1;i++)

        for(j=i+1;j<pricesSize;j++)

            if (prices[j]-prices[i] > max)

                max = prices[j]-prices[i];

    return max;

}

加上了一點點的判斷當然也是快不到哪裡去 XD

因為並沒有使用到DP的精神QQ

int maxProfit(int* prices, int pricesSize) {

    int i,j, max = 0;

    int min = INT_MAX;

    for (i=0; i<pricesSize-1;i++)

    {   

        if (prices[i]< min)

            min = prices[i];

        else 

            continue;

        for(j=i+1;j<pricesSize;j++)

            if (prices[j]-prices[i] > max)

                max = prices[j]-prices[i];

    }

    return max;

}

最後還是偷看了別人的解法XD

原來要這樣寫Orz

int maxProfit(int* prices, int pricesSize) {

    int i,j, max = 0;

    int min = INT_MAX;

    for (i=0; i<pricesSize;i++)

    {   

        if (prices[i]< min)

            min = prices[i];

        if (prices[i]-min > max)

            max = prices[i]-min;

    }

    return max;

}

順便記下最小值, 如果比之前小, 就更新min

畢竟往後出現的若是可以更大, 一定是減去min才最大的

若是前面的差值比較大, 那後面的差值減去min 還是小於差值, 那就不會被更新

像是 20, 100, 1, 10

雖然 1小於20

但後面的差沒有大於80的話就不會被更新

若是20, 100, 1, 90

89會被更新為最大差值.

[20231122 更新]

時隔數年～這個寫法跑起來已經是幾十 ms，完全不是當年的 6或8ms 啊 XD

測資不知道是多了多少？！

#define max(A,B) ((A>B)?(A):(B))

#define min(A,B) ((A<B)?(A):(B))

int maxProfit(int* prices, int pricesSize) {

int profit =0, price= 100000;

for (int i=0;i<pricesSize;i++)

{

profit = max (profit , prices[i]-price);

price = min(price, prices[i]);

}

return (price > 10000)? 0: profit;

}

[104] Maximum Depth of Binary Tree

找binary tree的最高深度(?) 也就是height（嗎）
（各種問號 & 各種不精確XD）

Maximum Depth of Binary Tree
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root) {
    if (root == NULL)
        return 0;
//    if (root->left == NULL && root->right == NULL)
//        return 1;

    int left, right;
 //   if (root->left != NULL && root->right != NULL)
    {
        left = 1+maxDepth(root->left);      
        right = 1+maxDepth(root->right);
        return (left > right) ? left : right;
    }
#if 0
    if ((ptr = root->left) != NULL)
    {
        return 1 + maxDepth(ptr);
    }
     
    if ((ptr = root->right) != NULL)
    {
        return 1 + maxDepth(ptr);
    }

    return 1;
#endif
}
結果還多寫了很多判斷 囧
顯示為根本沒搞懂........唉

「20231213 更新」

稍微有比較懂了"使用遞迴去處理tree的問題"

但好像還是不是很漂亮？！

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

int height(struct TreeNode* root, int h)

{

if (root == NULL)

return h;

int left = height(root->left, h+1);

int right = height(root->right, h+1);

return (left> right)? left:right;

}

int maxDepth(struct TreeNode* root) {

return height(root, 0);

}

[215] Kth Largest Element in an Array

寫到這一題之後不知道為什麼認真的累了XD
然後就頹廢了兩天QQ
這禮拜應該要開始大量的看題目和解答,
沒時間慢慢想慢慢寫了...(傷心)

給一個unsorted array,
回傳它的第k大的值.
第一個當然是先用qsort解決它XD
不過聽說有更快的方法Orz
還看到了沒看過的algo !!
Blum-Floyd-Pratt-Rivest-Tarjan algorithm
以上 Orz

Kth Largest Element in an Array
int *compare(const void *a , const void *b){
    return (*(int*)b - *(int*)a);
}

int findKthLargest(int* nums, int numsSize, int k) {
    qsort(nums,numsSize,sizeof(int),compare);
    return nums[k-1];
}

[20251031 更新]

奇怪～我寫的是quick selection 嗎......

void swap(int *a, int *b)

{

int tmp = *a;

*a = *b;

*b = tmp;

return;

}

void q_select(int *nums, int left, int right, int k)

{

int l = left, r=right;

int mid = l+(r-l)/2;

int pivot= nums[mid];

while (l<=r)

{

while (nums[l]< pivot)

l++;

while (nums[r]> pivot)

r--;

if (l<=r)

{

swap(&nums[l], &nums[r]);

l++;

r--;

}

}

if (k<=r)

q_select(nums, left, r , k);

if (l<=k)

q_select(nums, l, right , k);

}

int findKthLargest(int* nums, int numsSize, int k) {

q_select(nums,0, numsSize-1, numsSize-k);

return nums[numsSize-k];

}

「20250927更新」

嗯........用linked list 硬幹了一場應該是對的

但是很可惜超時了XDDDDDD

把它留在這裡以滋紀念, 我還是覺得我有進步啊~(大笑)

據說要用quick selection 是嗎晚點再寫寫看

struct ListNode* head;

struct ListNode* create(int val)

{

struct ListNode* ret = calloc (1, sizeof(struct ListNode));

ret->val = val;

ret->next = NULL;

return ret;

}

void insertHeap(int val)

{

struct ListNode* ret;

ret = create(val);

if (head->val <= val) // new head

{

ret->next = head;

head = ret;

}

else

{

struct ListNode* ptr;

ptr = head;

while (ptr->next != NULL && (ptr->next->val > val))

ptr = ptr->next;

if (ptr->next != NULL)

{

ret->next = ptr->next;

ptr->next = ret;

}

else // add to tail

ptr->next = ret;

}

return;

}

int findKthLargest(int* nums, int numsSize, int k) {

head = create(nums[0]);

for (int i=1; i<numsSize; i++)

insertHeap(nums[i]);

struct ListNode* ptr = head;

for (int i=1; i<k; i++)

{

//printf("%d\n", ptr->val);

ptr = ptr->next;

}

return ptr->val;

}

但我現在有點懶得寫啊哈哈哈（乾笑）

想說要寫一個quick sort 但好像寫出了奇怪的東西?!

感覺也沒錯啊QQ 但是超時了Orz 是在瞎忙什麼哈哈哈 （崩潰）

void swap(int *a, int *b)

{

int tmp = *a;

*a = *b;

*b = tmp;

return;

}

void myqsort(int *nums, int left, int right)

{

if (left>=right)

return;

if (right -left <2)

{

if (nums[left]> nums[right])

swap(&nums[left], &nums[right]);

return;

}

int pivot = nums[left];

int l = left+1;

int r = right;

while (l<r)

{

while (r>left && nums[r]>=pivot)

r--;

while (l<right && nums[l]< pivot)

l++;

if (l<r)

swap(&nums[l], &nums[r]);

else

{

swap(&nums[left], &nums[r]);

myqsort(nums,left,r-1);

myqsort(nums,r+1,right);

}

}

//myqsort(nums,left,r-1);

//myqsort(nums,r+1,right);

}

int comp(const void *a, const void *b)

{

return (*(int*)a - *(int*)b);

}

int findKthLargest(int* nums, int numsSize, int k) {

myqsort(nums,0, numsSize-1);

// qsort(nums, numsSize, sizeof(int), comp);

for (int i=0; i<numsSize;i++)

printf("%d %d\n", i , nums[i]);

return nums[numsSize-k];

}

沒想到自己以前存的qqsort竟然可以PASS = =+

難道要拿出婷婷教授的筆記回來看了嗎 囧

看來要過兩天再回來寫一次了Orz

void swap(int *a, int *b)

{

int tmp = *a;

*a = *b;

*b = tmp;

return;

}

void myqsort(int *nums, int left, int right)

{

int l=left, r=right;

int mid = (l+r)/2;

int pivot= nums[mid];

while (l<=r)

{

while (nums[l]< pivot)

l++;

while (nums[r]>pivot)

r--;

if (l<=r)

{

swap(&nums[l],&nums[r]);

l++;

r--;

}

}

if (left<r)

myqsort(nums,left,r);

if (l<right)

myqsort(nums,l,right);

}

int findKthLargest(int* nums, int numsSize, int k) {

myqsort(nums,0, numsSize-1);

return nums[numsSize-k];

}