Qmonster吃喝玩樂大事記

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);
*/

2023年12月13日星期三

[111] Minimum Depth of Binary Tree

嗯 ....好吧其實我覺得我現在無法思考中囧

找最小的深度，和找最深的差別在於，

當深度是0 (就沒有child的時候）需要return 另一個child的長度

舉例為，一個root 一路往右長，root-> left == NULL 的情況

繼續閱讀 »

[110] Balanced Binary Tree

如果兩邊的樹有高度相差超過1的就return false

嗯.....感覺不是很能馬上想到Orz

先回去"感覺"了一下單純求最深的那題（104. Maximum Depth of Binary Tree）

然後就照著抄了一下XD 偷偷塞了一個 &ans 進去，一旦它途中有相差超過一，就直接return了，

（return 的高度不重要，反正它已經是false了！！！而且ans 已經偷偷藏在裡面了！）

那就降Orz

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int height(struct TreeNode* root, int h, bool *ans)
{
    if (root == NULL)
        return h;
    int left = height(root->left, h+1, ans);
    int right = height(root->right, h+1, ans);
    if  (abs(left-right)>1)
    {
        *ans = false;
        return 0;
    }

    return (left> right)? left:right;
}

bool isBalanced(struct TreeNode* root) {
    bool ret = true;
    height(root, 1, &ret);
    return ret;
}