Qmonster吃喝玩樂大事記

typedef struct {
    int data[10000][2];
    int top;
} StockSpanner;


StockSpanner* stockSpannerCreate() {
    StockSpanner* stock = calloc (1, sizeof(StockSpanner));
    stock->top = -1;
    return stock;
}

int stockSpannerNext(StockSpanner* obj, int price) {
    int top = obj->top;
    int count=1;
    while (top>=0 && obj->data[top][0]<= price)
        count+= obj->data[top--][1];

    obj->top= ++top;
    obj->data[top][0]= price;
    obj->data[top][1]= count;
    return count;
}

void stockSpannerFree(StockSpanner* obj) {
    free(obj);
    return ; 
}

笨笨Q的慢速解XD （面試官表示：這麼直白的寫法誰不會啊～不錄用！！！XD）

typedef struct {
    int stock[10000];
    int top;
} StockSpanner;


StockSpanner* stockSpannerCreate() {
    StockSpanner* stock = malloc (sizeof( StockSpanner));
    stock->top = -1;
    return stock;
}

int stockSpannerNext(StockSpanner* obj, int price) {
    int top = obj->top;
    obj->stock[++top] = price;
    obj->top = top;
    int count=0;
    while (top>=0 && obj->stock[top--]<= price)
        count++;
    return count;
}

void stockSpannerFree(StockSpanner* obj) {
    free(obj);
    return ; 
}

/**
 * Your StockSpanner struct will be instantiated and called as such:
 * StockSpanner* obj = stockSpannerCreate();
 * int param_1 = stockSpannerNext(obj, price);
 
 * stockSpannerFree(obj);
*/

[72] Edit Distance

感覺是一個經典的題目。我怎麼會沒寫過呢？XD

繼續閱讀 »

2023年12月2日星期六

[2336] Smallest Number in Infinite Set (TBD)

扣掉蠢bug 應該是一次PASS的QQ 不過用C好像無法真的驗證Heap?!

真的用heap 下去寫反而更醜XD 但資料量大的時候大概無法用直覺的寫法偷吃步吧。

不管XD！它就放到TBD 裡吧 XD

繼續閱讀 »

[2215] Find the Difference of Two Arrays

竟然一次過了！！！我的眼淚都要流下來了 T——————T

（扣掉之前先把malloc 的部分寫好了的話 XD)

繼續閱讀 »

[2225] Find Players With Zero or One Losses

竟然沒有超時！！！真是不敢相信我的眼睛＠＠！！！

繼續閱讀 »

2023年12月1日星期五

[235] Lowest Common Ancestor of a Binary Search Tree

賺爛，寫一題賺兩題XD （比樓下）

繼續閱讀 »

[236] Lowest Common Ancestor of a Binary Tree

果然還是看解答省事 Orz 我真是沒有天份 Orz

繼續閱讀 »

[1926] Nearest Exit from Entrance in Maze(TBD)

ㄜ..........怎麼這麼麻煩的題目XD

說是 enqueue的時候就要把它改成不能通過了！

dequeue再做就太慢了！比方說一個超大的矩陣只有四邊是牆，中間全部都是可以走的，

那就會重覆enqueue了！所以 QQ

因為寫完好累了就先這樣吧Orz 先上個TBD 表示還沒有細看討論區XD！

typedef struct{
    int x;
    int y;
} Queue;

void printQ(Queue *q, int len)
{
    for (int i=0;i<len; i++)
        printf("q[%d] %d %d\n", i, q[i].x, q[i].y);
    
}

int enQueue(Queue *q, int x, int y, int tail)
{
    q[tail].x=x;
    q[tail].y=y;
    return tail +1;
}

int en_fourQ(char** maze, Queue *q, int x, int y, int m, int n, int tail)
{
    maze[x][y] = '+';
    if ((x-1>=0) && (maze[x-1][y])=='.')
    {
        tail = enQueue(q,x-1, y, tail);
        maze[x-1][y]= '+';
    }
    if ((x+1 < m) && (maze[x+1][y])=='.')
    {
        tail = enQueue(q,x+1, y, tail);
        maze[x+1][y]= '+';
    }

    if ((y-1>=0) && (maze[x][y-1])=='.')
    {
        tail = enQueue(q,x, y-1, tail);
        maze[x][y-1]= '+';

    }

    if ((y+1 < n) && (maze[x][y+1])=='.')
    {
        tail = enQueue(q,x, y+1, tail);
        maze[x][y+1]= '+';
    }
    return tail;
}


int nearestExit(char** maze, int mazeSize, int* mazeColSize, int* entrance, int entranceSize) {
    int thisround;
    int head = 0, tail = 0;
    int ret =0 ;
    int m= mazeSize, n= (*mazeColSize) ;
    Queue *myQ= calloc (40001, sizeof(Queue));
    tail = enQueue(myQ,entrance[0], entrance[1], tail);
    maze[entrance[0]][entrance[1]]='+';
    while (head < tail)
    {
        thisround=tail;
        for (int i=head; i<thisround;i++)
        {
            int _x= myQ[head].x;    //dequeue one , and add at most four in this round
            int _y= myQ[head].y;
            if ((_x==0 || _x==m-1 || _y==0 || _y==n-1)
                && !(_x == entrance[0] && _y == entrance[1]))
            {
                return ret;
            }
            else
                tail = en_fourQ(maze, myQ, _x, _y, m, n, tail);
            head++; 
        }
        ret++;
    }
    return (thisround >= 0)? (-1):ret;
}

2023年12月4日 星期一

2023年12月3日 星期日

2023年12月2日 星期六

2023年12月1日 星期五

2023年12月4日星期一

2023年12月3日星期日

2023年12月2日星期六

2023年12月1日星期五