2018年1月28日 星期日

[4] Median of Two Sorted Arrays (TBC)

兩個sorted array, 取其中位數.
還是array比較清新~
這題是hard難度倒是令人有點意外(?)
該不會我漏掉了什麼重要的東西XD?!

Median of Two Sorted Arrays
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
 
    int *sorted = malloc((sizeof(int))*(nums1Size+nums2Size));
    int i,j,k;
    int total = nums1Size+nums2Size;
    for (i=0,j=0,k=0;k<total;k++)
    {
        if(i<nums1Size && j<nums2Size)
            sorted[k] = (nums1[i]<nums2[j])?(nums1[i++]):(nums2[j++]);
        else if (i<nums1Size)
            sorted[k]=nums1[i++];
        else if (j<nums2Size)
            sorted[k]=nums2[j++];
    }

    if ((total)%2 == 0)
        return ((double)(sorted[(total)/2] + sorted[(total)/2-1])/2);
    else
        return (double)sorted[(total)/2];      
}
看看討論區果然搞錯了XD
what is O(log(M+N))  XD
O(M+N)不可以嗎XDDDDDDD
完全囧, 這題之後再回來寫吧 XD

[88] Merge Sorted Array

給兩個sorted array,
要把第二個merge進第一個,
讓第一個變成兩個組起來的sorted array.
可假定第一個array有足夠空間把第二個存進去.

寫完第一版, 看執行時間並不快,
想說難道是要把第二個先全部接到第一個的尾端,
然後再把新array丟去sort, 這樣會比較快嗎?!
明明我就看到兩個for XD 我還只有一個耶 !

後來發現LeetCoce上面寫的時間只能參考,
我copy執行 0ms的下來跑, 結果跑的比我的還慢啊= =
原來一切都是幻覺 QQ
那我就貼我的版本就好了cc
不用refine了反正我沒有天份~(奔入雨中)

Merge Sorted Array
void merge(int* nums1, int m, int* nums2, int n) {
    if (n==0)
        return;
     
    int i=m-1;
    int j=n-1;
    while(i>=0 && j>=0)
    {
        if(nums1[i] < nums2[j])
            nums1[i+j+1] = nums2[j--];
        else
            nums1[i+j+1] = nums1[i--];
    }
    if (i<0)
    {
        for(int q=0;q<=j;q++)
            nums1[q]=nums2[q];
        return;      
    }
    if (j<0)  //可以直接回傳了, 這段其實可以拿掉
    {
        return;
    }
}

[20250930更新]
嗯....所以我當年在寫什麼啊哈哈哈XD 看起來是一個當年比現在聰明的fu Orz
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int *idxs = calloc (m+n, sizeof (int));
int idx =0;
int i=0, j=0;
while (idx<(m+n) && i<m && j<n)
{
if (nums1[i]< nums2[j])
{
idxs[idx++]= nums1[i];
i++;
}
else
{
idxs[idx++]=nums2[j];
j++;
}
}
while (i<m)
idxs[idx++]= nums1[i++];
while (j<n)
idxs[idx++]= nums2[j++];

memcpy (nums1, idxs, sizeof (int) *(m+n));
return;
}

明天再來寫一次.
(隔日)結果只能寫這樣。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int i=m-1;
int j=n-1;
int idx = m+n-1;
while (idx>=0)
{
//printf("%d %d %d \n", idx, i,j);

if (i<0)
nums1[idx--]=nums2[j--];
else if (j<0)
nums1[idx--]=nums1[i--];
else if (nums1[i]> nums2[j])
nums1[idx--] = nums1[i--];
else
nums1[idx--] = nums2[j--];
}
return;
}

但看看別人,其實while 只需要看nums2的長度。當它跑完,如果nums1 還有剩,它會留在原地自動排好(?)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int i=m-1;
int j=n-1;
int idx = m+n-1;
while (j>=0)
{
if (i>=0 && nums1[i]> nums2[j])
nums1[idx--] = nums1[i--];
else
nums1[idx--] = nums2[j--];
}
return;
}

[20251104更新]
然後我一個月以後, 完全重覆了[20250930更新]的內容XDDDD


[20260710更新]
所以我又寫了什麼! 回頭看最佳解發現不用檢查m !!!
原來leetcode 還可以越寫越退步的嗎...........
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int len = nums1Size-1;
if (m==0)
{
for (int i=0; i<nums2Size; i++)
nums1[i]=nums2[i];
return;
}
while (m>0 && n>0)
{
if (nums1[m-1]> nums2[n-1])
nums1[len--] = nums1[--m];
else
nums1[len--] = nums2[--n];
}
if (n>0)
while (n>0)
nums1[len--] = nums2[--n];
return;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int len = nums1Size-1;
while (m>0 && n>0)
{
if (nums1[m-1]> nums2[n-1])
nums1[len--] = nums1[--m];
else
nums1[len--] = nums2[--n];
}
if (n>0)
while (n>0)
nums1[len--] = nums2[--n];
return;
}

[278] First Bad Version

說真的我不知道我在寫什麼........
怎麼會弱成這樣呢 ?!(哭倒萬里長城)
為什麼我寫的跟別人寫的都長的不一樣XD
難道我是百年難得一見的蓋世奇才(x)世紀大笨蛋(o)嗎?!
用了超多次的isBadVersion, 但是竟然沒有超過執行時間啊哈哈哈
一定是哪裡搞錯了, 我要去複習一下binary search......(倒)

假設1到n的版本號, 原本都是正確的, 某一版改壞了,
需找出第一個被改壞的版本, 改壞之後的版本也會全部都是壞的,
提供isBadVersion這支API來檢查版本是對的還是錯的.

以下我的版本太丟臉了,  懇請大家關掉視窗不要看(遮眼睛)
我自己都不忍卒睹啊啊啊啊啊啊啊~~~~(崩潰)
是不是要改一下try&error的試誤法的習慣,
好好的想想題目到底要妳幹嘛呢 ?!傷心QQ

First Bad Version
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

bool needReturn(int n)
{
    if(isBadVersion(n) && !isBadVersion(n-1))
        return true;
    return false;
}  

int findIndex(int start, int end)
{
    if (needReturn(end))
        return end;
    if (start==end)
        return -1;

    int diff =  end-start+1;
    int index = start+((diff%2==0)?diff/2: diff/2+1)-1;
    if (needReturn(index))
        return index;
 
    if(isBadVersion(index))
        return findIndex(start, index);
    else
        return findIndex(index,end);
}

int firstBadVersion(int n) {
    if (n<1)
        return -1;
    else if (n==1 && isBadVersion(n))
        return n;
    return findIndex(1,n);
}

改良版....................
我的腦子一定是壞了............
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

int firstBadVersion(int n) {
    int start= 1;
    int end = n;
    int mid;
    while (start < end)
    {
        mid = start + (end-start) /2;
        if (isBadVersion(mid))
            end = mid;
        else
            start = mid+1;
    }
//    if (isBadVersion(start))
        return start;
//    return -1;
}
最後面直接retuen start也是可以的......(為什麼呢XD 難道不用再檢查一下嗎XD)

[2] Add Two Numbers

繼續覺得自己廢= =+
Add Two Numbers
有兩個數字
每個數字用倒過來的linked list表示,
比方說 23二十三就是 先3 -> 2
然後要把這兩個數字相加,
加完再存成一個倒過來的linked list
要注意的是10的進位部份
和兩個list長度不同的時候~~~
舉例來說,
12+ 23 = 35,
輸入是 2->1 跟 3-> 2
輸出是 5->3
輸入是5,5的話, 輸出是 0->1
(我真的需要寫這麼細嗎XD~)

小廢廢我的版本:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* createNode(int val)
{
    struct ListNode *node = malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

void appendQList(struct ListNode **head, struct ListNode *node)
{
    if (*head == NULL)
    {
        (*head) = node;
        return;
    }
    struct ListNode *tmp = (*head);
    for (tmp = *head;tmp->next!=NULL;tmp=tmp->next)
        ;
    tmp->next = node;
    return;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *result=NULL,*p1,*p2;
    bool tenflag = 0;
    for(p1=l1,p2=l2;(p1 != NULL || p2 != NULL);)
    {
        int v1 = (p1== NULL)? 0:p1->val;
        int v2 = (p2== NULL)? 0:p2->val;    
        int sum = v1+v2 + tenflag;
        tenflag = (sum < 10) ? 0:1;
        sum = (tenflag)? sum - 10: sum;
        appendQList(&result,createNode(sum));

        if(p1!=NULL)
            p1=(p1->next ==NULL)? NULL:(p1->next);
        if(p2!=NULL)
            p2=(p2->next ==NULL)? NULL:(p2->next);
     
    }
 
    if (tenflag)
    {
        appendQList(&result,createNode(tenflag));
        tenflag = 0;
    }

    return result;
}

寫完看了一下別人的, 覺得進位的地方似乎有更好的寫法
但是懶得想了 XD 先這樣吧QQ 我要前進下一題屋屋.
一開始在appendList的地方卡好久
完全就是call by address和call by value沒學好QQ
順便附上兩年前複習的時候的內心吶喊吧哈哈哈哈哈
====================================================
1.剛剛才發現,原來call by address和call by reference 是不一樣的。
2.我一直以為只有call by value和 call by reference兩種 囧
3.我根本不知道C沒有call by reference,C++才有。 (!)
4.拿出C語言課本想證明我的記憶沒有錯,發現相關章節的標題旁邊,我本人的字跡寫著:「C沒有call by reference」(WTF XD)

5.有一種根本沒寫過C++的fu,我吃屎好了我面試個屁 T—T(大哭奔入雨中)


[20240608 update]
啊...............真是全新的世界啊XD 原來我的linked list 還是一直沒有學好 XD

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* insertNode(int val)
{
struct ListNode *ptr = calloc (1, sizeof(struct ListNode));
ptr->val = val;
ptr->next = NULL;
return ptr;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode *p1 = l1;
struct ListNode *p2 = l2;
struct ListNode head;
head.next = NULL;
struct ListNode *tail = &head;
int overflow=0;
while (p1 != NULL || p2 != NULL || overflow)
{
int v1=0, v2=0, add=0;
if (p1!=NULL)
{
v1 = p1->val;
p1 = p1->next;
}
if (p2!= NULL)
{
v2 = p2->val;
p2 = p2->next;
}

add = v1+v2 + overflow;
if (add >= 10)
{
overflow = 1;
add-=10;
}
else
overflow = 0;

tail->next = insertNode(add);
tail = tail->next;
}
return head.next;
}
沒什麼差別的更新版 (?)

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* insertNode(int val)
{
struct ListNode *ptr = calloc (1, sizeof(struct ListNode));
ptr->val = val;
ptr->next = NULL;
return ptr;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode *p1 = l1;
struct ListNode *p2 = l2;
struct ListNode *head = NULL;
struct ListNode *tail = NULL;

int overflow=0;
while (p1 != NULL || p2 != NULL || overflow)
{
int v1=0, v2=0, add=0;
if (p1!=NULL)
{
v1 = p1->val;
p1 = p1->next;
}
if (p2!= NULL)
{
v2 = p2->val;
p2 = p2->next;
}

add = v1+v2 + overflow;
if (add >= 10)
{
overflow = 1;
add-=10;
}
else
overflow = 0;

if (head == NULL)
{
head = insertNode(add);
tail = head;
}
else
{
tail->next = insertNode(add);
tail = tail->next;
}
}
return head;
}

[20250821]
再次更新?! 嗯.....終於把多出來的insert node 塞進去了(嗎)
好笨QQ 感覺要來把dummy pointer 學起來了/_\

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

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    if (l1==NULL)
        return l2;
    if (l2==NULL)
        return l1;
    struct ListNode *head = NULL;
    struct ListNode *tail = NULL;
    int plus1= 0;
    while (l1 != NULL || l2 !=NULL || plus1>0)
    {
        int sum = plus1;
        if (l1 == NULL && l2 == NULL)
            sum = plus1;
        else if (l1 == NULL)
            sum += l2->val;
        else if (l2 == NULL)
            sum += l1->val;
        else 
            sum += (l1->val + l2->val);

        if (sum > 9)
        {
            plus1 = 1;
            sum -= 10;
        }
        else
            plus1 = 0;
        struct ListNode *new = calloc (1, sizeof (struct ListNode)); 
        if (head == NULL)
            head = new;
        else
            tail->next = new;
        new->val = sum;
        new->next = NULL;
        tail = new;
        if (l1 != NULL)
            l1 = l1->next;
        if (l2 != NULL)
            l2= l2->next;
    }

    return head;
}

2018年1月27日 星期六

[21] Merge Two Sorted Lists

真是世界廢Orz
初版長這樣
晚點再想怎麼修... Orz

Merge Two Sorted Lists
題意就是字面上的意思XD
請不要問我為什麼那個head好像有點多餘
我也說不上來啊啊啊啊啊啊~~~~
我還是喝西北風吧(奔入雨中)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;
    struct ListNode* new, *head;
    if (p1 == NULL)
        return p2;
    if (p2 == NULL)
        return p1;
 
    if (p1->val < p2->val)
    {
        head = p1;
        p1 = p1->next;
    }
    else
    {
        head = p2;
        p2 = p2->next;
    }
    new = head;
    for(;;)
    {
        if (p1 == NULL)
        {
            new->next= p2;
            break;
        }
        if (p2 == NULL)
        {
            new->next= p1;
            break;
        }      

     
        if (p1->val < p2->val)
        {
            new->next = p1;
            p1 = p1->next;
            new = new->next;
        }
        else
        {
            new->next = p2;
            p2 = p2->next;
            new = new->next;
        }      
    }  
 
    return head;
}

update:
看到別人說可以用recursive寫法
但是比較慢啊XD
降子有比較好嗎@__@?!
update 2:
後來發現我多做了幾步贅步XD
其實根本沒想懂吧哈哈哈哈哈哈哈(奔入雨中)
但是有跑過recursive快也有慢的時候,
是個快慢很看系統的寫法?! (sensitive~~~~~)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head, *tmp;
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;
#if 0        //別人的簡潔版
    if (l1->val < l2->val)
    {
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;
    }
    else
    {
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
#else    //我的贅步版XD
    if (l1->val < l2->val)
    {
        head = l1;
        tmp = mergeTwoLists(l1->next,l2);
    }
    else
    {
        head = l2;
        tmp = mergeTwoLists(l1,l2->next);      
    }
    head->next = tmp;
    return head;
#endif  
}

20230829 再次更新
沒想到被考這題XD 總覺得開頭的head 很贅步,想把它加進while 裡,
發現加進去以後的code 也是蠻醜的 XD 
好吧那我比較想要把它擺在開頭,有種 initialize 的感覺!!!

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if (list1== NULL)
return list2;
if (list2==NULL)
return list1;
struct ListNode *p1,*p2, *head,*ptr;
head = NULL;
p1=list1;
p2=list2;
while (p1!=NULL && p2 != NULL)
{
if (p1->val < p2->val)
{
if (head == NULL)
{
head = p1;
ptr = p1;
}
else
{
ptr->next = p1;
ptr=ptr->next;
}
p1=p1->next;
}
else
{
if (head == NULL)
{
head = p2;
ptr = p2;
}
else
{
ptr->next =p2;
ptr=ptr->next;
}
p2=p2->next;
}
}
if (p1==NULL)
ptr->next=p2;
else
ptr->next=p1;
return head;
}

20230901 更新
最終~過了兩天再寫了一次revursive版本XD
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if (list1 ==NULL)
return list2;
if (list2 == NULL)
return list1;

if (list1->val < list2->val)
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}

[28] Implement strStr()

嗯~這個題目~
可以用strstr()嗎? (被打)
但還是偷偷用了strncmp XDDDDDD
後來良心不安再寫了一個沒有用strncmp的版本
但看討論好像跟什麼KMP有關 (不是KMT國民黨XD)
好懶得動腦喔可以不要管它嗎~~(滾來滾去滾來滾去)

Implement strStr()
int strStr(char* haystack, char* needle) {
    if (haystack == NULL || needle == NULL)
        return -1;

    int length = strlen(haystack);
    int lengthIn = strlen(needle);

    if(length < lengthIn)
        return -1;
    else if (length == 0 && lengthIn ==0)
        return 0;
     
    int i;
    for(i=0;i<=length - lengthIn;i++)
    {
        printf("[%d][%s]\n",i,haystack+i);
#if 1      
        int j;
        for (j=0;j<lengthIn;j++)
        {
// printf("[%d][%d][%c][%c]\n",i,j,haystack[i+j],needle[j]);
            if(haystack[i+j]!=needle[j])
                break;
        }
        if (j==lengthIn)
            return i;
#else
        if (strncmp(haystack+i,needle,lengthIn)==0)
            return i;
#endif
    }
    return -1;
}


[20260713更新]
姆襪哈哈哈哈哈哈哈完全看不懂以前的自己在寫什麼!!!!!
而且最佳解寫的好漂亮! 討厭XD!!!

int strStr(char* haystack, char* needle) {
int l1 = strlen(haystack);
int l2 = strlen(needle);
// if (l2>l1)
// return -1;
int i=0;
while (l1-i >= l2)
{
int j=0;
while (i<l1 && haystack[i]!= needle[j])
i++;
int ret = i;
while (i<l1 && j<l2 && (haystack[i]== needle[j]))
{
i++;
j++;
}
if (j==l2)
return ret;
else
i= ret+1;
}
return -1;
}

[48] 好的開始?!Rotate Image

嗯~雖然它本來不是給我這樣用的XD
但是估且用之吧XD
今天的題目是Rotate Image
沒有要追求最佳解
所以認真魔人不要砲我XD
純粹方便記錄, The End.

Rotate Image:矩陣轉90度,不能直接alloc一個全新的塞進去(可惡XD!)

一開始的想法是這樣(哪樣 XD),沒想到index完全大錯亂 囧
最後花了一整天才寫好 = =+
雖然中間有去吃飯鬼混抱怨咖啡店的隔壁桌太吵之類的  XD

從最外圈往裡面一層一層轉進去, 每次需要搬四個item,它們會形成A要搬去B,B要搬去C, C要搬去 D, D要搬去A的迴路,最難的大概是找每個對應item的index (其實是因為我太廢了屋屋屋)
花了我一天精神時光屋, 明明用講的都很簡單, 哭

void rotate(int** matrix, int matrixRowSize, int *matrixColSizes) {
    int i,j,tmp,range;
    range = matrixRowSize;
    for(i=0; i<matrixRowSize/2; i++)
    {
        range = matrixRowSize-2*i;
        for(j=i;j<i+range-1;j++)
        {
            tmp = matrix[i][j];
            matrix[i][j] = matrix[matrixRowSize-j-1][i];
            matrix[matrixRowSize-j-1][i] = matrix[matrixRowSize - i -1][matrixRowSize-j-1];
            matrix[matrixRowSize - i -1][matrixRowSize-j-1] =matrix[j][matrixRowSize - i -1];
            matrix[j][matrixRowSize - i -1] = tmp;
        }
    }
}

中間一度崩潰有去偷看了一下別人的解法
說可以先反轉再swap, 為什麼可以想到這種兩步偷吃步的方法呢為什麼!
但是不得不說知道IDEA 之後就沒什麼難度了,
大概幾分鐘就KO掉了 QQ
(最難的就是那個IDEA啊啊啊啊啊啊~~~~~抱頭)

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

void rotate(int** matrix, int matrixRowSize, int *matrixColSizes)
{
    int i , j , tmp;
    for (i = 0; i<matrixRowSize/2 ; i++)
    {
        for(j=0; j<matrixRowSize; j++)
        {
            swap(&matrix[i][j], &matrix[matrixRowSize-i-1][j]);
        }
     
    }
 
    for (i = 0; i<matrixRowSize ; i++)
    {
        for(j=i;j<matrixRowSize;j++)
                swap(&matrix[i][j],&matrix[j][i]);      
    }
}

但總而言之第一天開始LeetCode, 至少有解出來 (要被各方大神笑死了屋屋屋)
用24小時解一題,我看我還是喝西北風好了哈哈哈哈哈哈.........

2018年1月16日 星期二

[?/365] what the...

寫了幾天之後覺得頓失靈感 XD
雖然硬擠好像也可以擠出一點什麼
但是有意義嗎XD
改成隨意update好啦~(或者根本就cancel不是更快嗎 hahaha)

就這樣吧
(快逃)

2018年1月11日 星期四

[11/365] 天窗

哎呀!開天窗真是一件容易達成的事呀XD
睏意來襲的時候
一扇天窗已為您敞開?! XD
上帝為你開一扇天窗,就會再開另外一扇,
天窗們相連到天邊~~~(搭肩搖)

好累
沒做什麼事卻覺得極累
連吃太飽也累XD
what should I say today ?
讓我們點播一首
Let it be ~~~~~~

2018年1月10日 星期三

[9/365] 好的開始?!

什麼?我還有一個東西叫做365嗎?XD

回家包便當的感覺真是溫馨
雖然媽媽應該覺得很困擾吧哈哈哈
猜拳輸的洗碗結果我輸了
哭
下次還是直接推給別人洗吧噗

中午跑去找阿思玩
順便在星巴克買了外帶的荷蘭小鬆餅
感覺不錯!
但是附贈的焦糖醬為什麼在快吃光了的時候才浮現在杯底呢威什麼~~~
不甘心沒完整吃到它只好硬食焦糖醬
覺得甜XD
明天直接去內用好了(誤)(是嫌錢太多嗎一份90ㄟXD)

今天還聽說了驚人的消息
時機未到暫時不提
咱們下次見