找最小的深度，和找最深的差別在於，
當深度是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;
}
2023年11月30日 星期四
[875] Koko Eating Bananas
算是轉了一個彎的binary search，但是還要考慮integer overflow的問題，不喜歡XD
怎麼可能吃那麼多香蕉！！！ 要考到overflow那就不要用香蕉當例子！（妳真囉唆XD）
所以就先這樣吧Orz
2023年11月29日 星期三
2023年11月28日 星期二
2023年11月27日 星期一
2023年11月26日 星期日
2023年11月25日 星期六
2023年11月24日 星期五
2023年11月23日 星期四
2023年11月22日 星期三
2023年11月20日 星期一
2023年11月19日 星期日
[6] Zigzag Conversion
除了搞了一個小烏龍之外，其實算是一次PASS吧 XD
然後就得意忘形了～想要忽略掉其實跑的很慢的事實 XD
應該是可以不要用到二維，直接用各種算位置的方法去把它求出來吧
2023年9月28日 星期四
2023年9月26日 星期二
2023年9月25日 星期一
2023年9月24日 星期日
2023年9月23日 星期六
2023年9月22日 星期五
[209] Minimum Size Subarray Sum
漏看了題意了XD subarray sum 需要找的是連續的subarray，
所以一開始想說就sort 開下去就好了是大錯特錯哈哈哈!!!
2023年9月10日 星期日
2023年9月9日 星期六
2023年9月7日 星期四
2023年9月6日 星期三
2023年9月4日 星期一
2023年9月3日 星期日
2023年9月2日 星期六
[138] Copy List with Random Pointer
微妙的題目......
以為跟deep copy linked list 差不多，但多了巧妙的地方XD
而重點就是那個，我應該自己想不到的，巧妙的地方XD
2023年9月1日 星期五
2023年8月25日 星期五
2023年8月24日 星期四
2023年8月23日 星期三
[162] Find Peak Element
感覺有點莫名的題目
要找peak，這也可以用binary search ?!
反正binary search就是強是吧(攤手)
但因為回傳任一peak都可以，就覺得不用硬扯binary search 吧
好啦是我沒有慧根啦(自暴自棄)
2023年8月21日 星期一
2023年8月19日 星期六
2023年8月15日 星期二
2023年8月11日 星期五
2023年8月10日 星期四
2023年8月7日 星期一
2023年8月4日 星期五
2023年8月3日 星期四
2023年8月2日 星期三
[435] Non-overlapping Intervals
找出 最多start & end的時間區間，需要刪除的最小次數
就很多個start & end 的schedule，你要留下最多次的行程，把重疊的刪掉，問最少要刪掉幾個
（是不是很繞口）
2023年8月1日 星期二
2023年7月31日 星期一
2023年7月30日 星期日
2023年7月28日 星期五
[907] Sum of Subarray Minimums (TBD)
算一個array裡面的 "連續subarray" 的最小值相加
就是 (1,2,3,4) 的話, subarray 是1,2,3,4 跟 (1,2) (2,3) (3,4) (1,2,3) (2,3,4) (1,2,3,4)
(1,3)跟(2,4)這種因為不連續所以不在這裡定義的subarray.
2023年7月27日 星期四
2023年7月26日 星期三
[1456] Maximum Number of Vowels in a Substring of Given Length
寫錯了XD 還以為要找母音連續的 " 小於k 的最大值" (還真繞口)
看來要重寫 Orz
先貼一下錯的版本 XD
2023年7月25日 星期二
2023年7月24日 星期一
2023年7月21日 星期五
[1433] Check If a String Can Break Another String
判斷兩個字串的任意字母排列組合(permutation)是不是可以其中一個break另一個
break的意思是說 字串A 的 char[i] 都一定會 大於等於 字串B的char[i] (或是反之)
2023年7月20日 星期四
[889] Construct Binary Tree from Preorder and Postorder Traversal
在malloc的地方搞錯了之外 XD
竟然可以無痛PASS !!! 覺得感動！！！
2023年7月19日 星期三
[207] Course Schedule
呃啊～～～～（拔頭髮）
選課之間的先後關係～可以看成是檢查 graph 裡面有沒有loop
如果有loop就是無法完成選課～（修A之前要先修B，修B之前要先修A)
2023年7月18日 星期二
[118] Pascal's Triangle
覺得感人 QQ 記得當年(?)寫不出來 XD
這次竟然可以一次KO (加上一點偷看XD)
但是從第一步到寫好花的時間太久了bar 哈哈哈哈哈!!!
為何周遭的干擾總是這麼多QQ
2023年7月16日 星期日
2023年7月14日 星期五
2023年7月13日 星期四
[137] Single Number II
雖然不知道為什麼負數最小值無法被qsort 處理（？）
（可能是最後的相減會爆掉？！）
雖然先sorting 好像也不符合題目要求（？！）
但總之先來一個不會過的版本 XD
2023年7月11日 星期二
[148] Sort List （TBD）
Linked list 的sorting ！感覺就是要用bubble sort啊！！！XD（誰規定的XD）
用bubble sort可以單純使用 int的swap就好，而不需要swap node (thinking 圖)
不出所料的超時了XD （附在最後面）
2023年7月10日 星期一
2023年7月9日 星期日
2023年7月8日 星期六
2023年7月7日 星期五
2023年6月16日 星期五
2023年5月29日 星期一
2023年5月13日 星期六
傳說中的聯盟行銷?! booking版
booking.com 破題(?)兼幫自己存連結 XD
是滴～經過多年好不容易google adsense 通過並且可以投放廣告之後，
除了覺得廣告很礙眼之外XD 聽聞朋友說其實收益並不高，去後台看了一下的確如此，
（不過妳這網站有流量嗎？XD）
2023年4月3日 星期一
我才不想看鯨魚呢！！！（大喊）
會選擇從Andenes進羅弗敦群島的理由很簡單，因為機票比較便宜XD 若是我選擇從Tromso飛Narvik的話，其實飛機也是會先飛到Andenes，放一些人下來載一些人走，再飛去Narvik，真是太不直覺了我不喜歡XP 於是我便開始搜尋Andenes 有什麼景點可以看，說是可以坐RIB去看鯨魚！！！說冬天鯨魚離Andenes很近！！！（RIB是一種船的專有名詞，wiki是翻 剛性充氣艇）
2023年2月21日 星期二
2023年1月11日 星期三
訂閱：
文章 (Atom)