找最小的深度，和找最深的差別在於，
當深度是0 (就沒有child的時候）需要return 另一個child的長度
舉例為，一個root 一路往右長，root-> left == NULL 的情況
2023年12月13日 星期三
[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;
}
[1582] Special Positions in a Binary Matrix
總覺得這題要考的，反而是直覺解法嗎？！
就是在雙迴圈裡面，當matrix[i][j] 是1的時候，再分別跑它的 row 跟column 回圈，
看別人是不是都是零！但總而言之Orz 別人有給厲害的解法，我們就來寫一寫 XD
然後就發現 int array 初始值好像還是用 calloc or memset 去寫好了 orz
2023年12月12日 星期二
2023年12月11日 星期一
[1248] Count Number of Nice Subarrays
經過了前面幾題滑窗戶的荼毒之後，想當然耳這題也是用atMost 的滑窗戶解決
但是Hint 有提示，可以把奇數設成1，偶數設成0，然後再用prefix sum ???!!!
2023年12月10日 星期日
2023年12月9日 星期六
2023年12月7日 星期四
2023年12月6日 星期三
2023年12月5日 星期二
[872] Leaf-Similar Trees
果然是easy的歡樂題(?) 看來是沒有什麼厲害的解法了 （？）
有一個是用string 去存，最後strcmp 這樣。
感覺string 一直長大讓人很不安心！
還是用一個array 存int 們好了 XD
最後的for 迴圈原來也可以用memcpy 搞定，以上。
2023年12月4日 星期一
[2300] Successful Pairs of Spells and Potions
沒有錯！！！直覺寫法當然是overflow了 QQ
看在這題是藥水跟咒語和哈利波特有點關係，我只好繼續寫下去了QQ
(又不是面試霍格華茲魔法學院QQ) (順便學英文是不QQ)
2023年12月3日 星期日
[901] Online Stock Span
想的太簡單了！！！當然每次都塞進去然後一個一個往前算 沒有不行XD
就是很慢而已XD 先把阿Q作法列在最後QQ
stack的精神是～～～多一個欄位去紀錄該stock price 所累積的span 數字是多少
當有item要被pop出來的時候，span就累積給把它pop出來的那個人！！！
(真的是會錯在一些很愚蠢的地方Orz 像是copy paste 順手把++ 或-- 又多做了一次之類的= =)
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);
*/
2023年12月2日 星期六
[2336] Smallest Number in Infinite Set (TBD)
扣掉蠢bug 應該是一次PASS的QQ 不過用C好像無法真的驗證Heap?!
真的用heap 下去寫反而更醜XD 但資料量大的時候大概無法用直覺的寫法偷吃步吧。
不管XD！ 它就放到TBD 裡吧 XD
2023年12月1日 星期五
[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;
}
訂閱：
文章 (Atom)