Qmonster吃喝玩樂大事記: 2024

判斷是不是一個二分圖：在一個無方向graph 裡，如果每一個edge相接的兩個node 分屬不同group，那就是一個二分圖。可以用對node塗色的概念來想！一開始大家都沒有顏色，選一個起始點塗上紅色，和它有edge連接的都塗上綠色。接著往外塗去，如果遇到已經有人上色了的，若是顏色相同，表示這不是一個二分圖。

[404] Sum of Left Leaves

暖身題也搞了好半天Orz tree真難ToT

2024年5月26日星期日

[1791] Find Center of Star Graph

感覺不出來哪裡還可以更快的一題（？）

[2497] Maximum Star Sum of a Graph

ㄜ.......果然會超過memory （嗎）

先貼個runtime error 版....

2024年2月19日星期一

[637] Average of Levels in Binary Tree

有一陣子沒寫tree，很意外竟然自己寫出來XD （所以人家是easy XD!）

對於tree的深度沒有考慮清楚，如果是超級不balance那可能很歪，以上。

2024年2月18日星期日

[707] Design Linked List

算是基本的linked list 觀念題吧

雖說可以用雙向linked list，但我沒有覺得有太多優點XD

因為如果加上長度的紀錄，每次要delete 或add時可以選擇從頭或從尾去找到index，

從尾巴算回來的感覺容易錯XDDD（對啦我就是廢QQ）

那就單向的開到底好了 XD 雖然比以前寫完linked list 要快了，但還是漏掉一些頭尾的特殊case啊～～～慎之。

[2279] Maximum Bags With Full Capacity of Rocks

又是一個沒什麼人用C寫的題目XD

2024年2月16日星期五

[2401] Longest Nice Subarray

竟然栽在括號上！！！太煩了吧！！！（國劇甩頭）

但好吧其實我也沒辦法推出這麼一步到位的結論QQ

傷心啊XD

2024年2月7日星期三

[445] Add Two Numbers II

竟然是這題！！！！！！

幸好我還有想到reverse 這件事Orz

但reverse 完卻忘記reverse 回來真是太悲了 Orz

[2966] Divide Array Into Arrays With Max Difference (TBD)

ㄜ... 寫出來似乎並沒有很快！

看了一下別人的寫法，好像用counting sort 去算每個數字出現幾次，也可以解決這題？！

2024年2月2日星期五

[2074] Reverse Nodes in Even Length Groups

這個算是group reverse linked list 系列吧

雖然對於一次要反轉幾個有點卡住

想說要先算起來還是怎樣的，但先弄起來反而就知道要把reverse 塞在哪兒了吧。

2024年1月29日星期一

[2078] Two Furthest Houses With Different Colors

這題目是不是太無聊了Orz C只有兩個人寫？！囧

雖然怪怪的～但也懶的再優化了Orz

2024年1月28日星期日

[2367] Number of Arithmetic Triplets

本來想說暴力下去解一定會超時，結果竟然沒有XD

但比較奇怪的是，C的solution 裡面大家都沒有用break！奇怪XD

2024年1月27日星期六

[128] Longest Consecutive Sequence

怪怪der ?! 囧

要找出連續數字的最長長度。數字有可能重覆，但是重覆的不會多算長度。

所以就先sorting 完，把重覆的拿掉，再去求解。

但是看起來不符合題目要求的O(n) XDDDDDD

2024年1月17日星期三

[697] Degree of an Array

咦竟然是這題XD！

我還以為是sliding window！原來不是嗎XD（笑我自己廢）

2024年1月15日星期一

[146] LRU Cache

雖然以前寫過了（？）但是很值得為它重開一篇！！！

以前的寫法，不知道為什麼現在已經compile 不過了 XD

當時用了一個假timer 去紀錄時間，而我現在想不起來我為什麼要把它宣告成static !!!

(比較厲害嗎？XD）

總之就是據說要有一個雙向linked list，這樣它新增刪除會比較快，

另外也最好有hash table去存，這樣找人也比較快！！！

因為題意的key最多10001種，所以直接拿它當hash key !!!

在一直滾來滾去然後各種拖延之後，沒有debug很久就pass了！！！（感動落淚）

看來linked list 已經可以了吧(自己說)

速度看起來不快XD 不過至少沒有超時，我可以接受XD（誰理妳XD）

在get和put的時候，如果已有同樣的key存在，我的作法是先把它delete掉，

再加進去，求個"感覺上"的乾淨俐落XD 但我不確定如果只有更新重新排序的方法會不會比較快XD 以上兒～～～～～

#define MAX_KEYS 10001

struct myNode{
    int key;
    int val;
    struct myNode *next;
    struct myNode *pre;
};

typedef struct {
    struct myNode *head;
    struct myNode *tail;
    int size;
    int count;
    struct myNode *queue[MAX_KEYS];
} LRUCache;

void debugPrint(LRUCache* obj)
{
printf("===debugPrint===\n");
    struct myNode *ptr= obj->head;
    while (ptr != NULL)
    {
        printf("key %d val %d\n",ptr->key, ptr->val);
        ptr = ptr->next;
    }
printf("===End debugPrint===\n");
}

LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* LRU = calloc (1, sizeof (LRUCache));
    LRU-> size= capacity;
    LRU-> count = 0;
    LRU->head = NULL;
    LRU->tail = NULL;
    return LRU;
}

void addqueue(LRUCache* obj, int key, int value) {
    obj->queue[key] = calloc (1 , sizeof (struct myNode));
    obj->queue[key]-> pre = obj->tail;
    obj->queue[key]-> next = NULL;
    if (obj->tail != NULL)
        obj->tail->next = obj->queue[key];
    obj->tail = obj->queue[key];
    obj->queue[key]->val = value;
    obj->queue[key]->key = key;
    if (obj->head == NULL)
        obj->head = obj->queue[key];
    obj->count ++;

}

void removequeue(LRUCache* obj, int key) {
    struct myNode *ptr= obj->queue[key];
    struct myNode *ptr_pre = obj->queue[key]->pre;
    struct myNode *ptr_next = obj->queue[key]->next;
    if (ptr_pre == NULL)//head
    {
        obj->head = ptr_next;
        if (ptr_next != NULL)
            ptr_next->pre = NULL;
    }
    else
        ptr_pre->next = ptr_next;
    
    if (ptr_next == NULL) // tail
    {
        obj->tail = ptr_pre;
        if (ptr_pre != NULL)
            ptr_pre->next = NULL;
    }
    else
        ptr_next->pre = ptr->pre;

    ptr_pre=NULL;
    ptr_next = NULL;
    obj->queue[key] = NULL;
    free (obj->queue[key]);
    obj->count --;
}

int lRUCacheGet(LRUCache* obj, int key) {
    if (obj->queue[key] == NULL)
        return -1;

    int value = obj->queue[key]->val;
    removequeue(obj,key);
    addqueue(obj,key, value);
    return obj->queue[key]->val;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    if (obj->queue[key]!= NULL)
        removequeue(obj,key);
    else if (obj->count == obj-> size)
        removequeue(obj,obj->head->key);

    addqueue(obj,key, value);
//debugPrint(obj);
}

void lRUCacheFree(LRUCache* obj) {
    for (int i=0; i< MAX_KEYS; i++)
        free(obj->queue[i]);
    free(obj);
}

/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);
 
 * lRUCachePut(obj, key, value);
 
 * lRUCacheFree(obj);
*/

2024年10月5日 星期六

2024年10月3日 星期四

2024年9月28日 星期六

2024年9月13日 星期五

2024年8月13日 星期二

2024年8月11日 星期日

2024年8月6日 星期二

2024年8月4日 星期日

2024年8月1日 星期四

2024年7月31日 星期三

2024年7月30日 星期二

2024年7月27日 星期六

2024年7月25日 星期四

2024年7月24日 星期三

2024年7月13日 星期六

2024年7月12日 星期五

2024年7月3日 星期三

2024年7月2日 星期二

2024年6月30日 星期日

2024年6月24日 星期一

2024年6月22日 星期六

2024年6月19日 星期三

2024年6月18日 星期二

2024年6月16日 星期日

2024年6月12日 星期三

2024年6月10日 星期一

2024年6月9日 星期日

2024年6月8日 星期六

2024年6月7日 星期五

2024年5月31日 星期五

2024年5月30日 星期四

2024年5月28日 星期二

2024年5月27日 星期一

2024年5月26日 星期日

2024年2月19日 星期一

2024年2月18日 星期日

2024年2月16日 星期五

2024年2月7日 星期三

2024年2月2日 星期五

2024年1月29日 星期一

2024年1月28日 星期日

2024年1月27日 星期六

2024年1月17日 星期三

2024年1月15日 星期一

2024年10月5日星期六

2024年10月3日星期四

2024年9月28日星期六

2024年9月13日星期五

2024年8月13日星期二

2024年8月11日星期日

2024年8月6日星期二

2024年8月4日星期日

2024年8月1日星期四

2024年7月31日星期三

2024年7月30日星期二

2024年7月27日星期六

2024年7月25日星期四

2024年7月24日星期三

2024年7月13日星期六

2024年7月12日星期五

2024年7月3日星期三

2024年7月2日星期二

2024年6月30日星期日

2024年6月24日星期一

2024年6月22日星期六

2024年6月19日星期三

2024年6月18日星期二

2024年6月16日星期日

2024年6月12日星期三

2024年6月10日星期一

2024年6月9日星期日

2024年6月8日星期六

2024年6月7日星期五

2024年5月31日星期五

2024年5月30日星期四

2024年5月28日星期二

2024年5月27日星期一