Qmonster吃喝玩樂大事記

2018年2月13日星期二

[104] Maximum Depth of Binary Tree

找binary tree的最高深度(?) 也就是height（嗎）
（各種問號 & 各種不精確XD）

Maximum Depth of Binary Tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int maxDepth(struct TreeNode* root) {
if (root == NULL)
return 0;
// if (root->left == NULL && root->right == NULL)
// return 1;

int left, right;
// if (root->left != NULL && root->right != NULL)
{
left = 1+maxDepth(root->left);
right = 1+maxDepth(root->right);
return (left > right) ? left : right;
}
#if 0
if ((ptr = root->left) != NULL)
{
return 1 + maxDepth(ptr);
}

if ((ptr = root->right) != NULL)
{
return 1 + maxDepth(ptr);
}

return 1;
#endif
}
結果還多寫了很多判斷囧
顯示為根本沒搞懂........唉

「20231213 更新」

稍微有比較懂了"使用遞迴去處理tree的問題"

但好像還是不是很漂亮？！

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

int maxDepth(struct TreeNode* root) {
    return height(root, 0);    
}

[215] Kth Largest Element in an Array

寫到這一題之後不知道為什麼認真的累了XD
然後就頹廢了兩天QQ
這禮拜應該要開始大量的看題目和解答,
沒時間慢慢想慢慢寫了...(傷心)

給一個unsorted array,
回傳它的第k大的值.
第一個當然是先用qsort解決它XD
不過聽說有更快的方法Orz
還看到了沒看過的algo !!
Blum-Floyd-Pratt-Rivest-Tarjan algorithm
以上 Orz

Kth Largest Element in an Array
int *compare(const void *a , const void *b){
return (*(int*)b - *(int*)a);
}

int findKthLargest(int* nums, int numsSize, int k) {
qsort(nums,numsSize,sizeof(int),compare);
return nums[k-1];
}

[20251031 更新]

奇怪～我寫的是quick selection 嗎......

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}

void q_select(int *nums, int left, int right, int k)
{
    int l = left, r=right;
    int mid = l+(r-l)/2;
    int pivot= nums[mid];
    while (l<=r)
    {
        while (nums[l]< pivot)
            l++;
        while (nums[r]> pivot)
            r--;
        if (l<=r)
        {
            swap(&nums[l], &nums[r]);
            l++;
            r--;
        }
    }
    if (k<=r)
        q_select(nums, left, r , k);
    if (l<=k)
        q_select(nums, l, right , k);
}

int findKthLargest(int* nums, int numsSize, int k) {
   q_select(nums,0, numsSize-1, numsSize-k);
   return nums[numsSize-k];    
}

「20250927更新」

嗯........用linked list 硬幹了一場應該是對的

但是很可惜超時了XDDDDDD

把它留在這裡以滋紀念, 我還是覺得我有進步啊~(大笑)

據說要用quick selection 是嗎晚點再寫寫看

struct ListNode* head;
struct ListNode* create(int val)
{
    struct ListNode* ret = calloc (1, sizeof(struct ListNode));
    ret->val = val;
    ret->next = NULL;
    return ret;
}

void insertHeap(int val)
{
    struct ListNode* ret;
    ret = create(val);

    if (head->val <= val) // new head
    {
        ret->next = head;
        head = ret;
    }
    else
    {
        struct ListNode* ptr;
        ptr = head;
        while (ptr->next != NULL && (ptr->next->val > val))
            ptr = ptr->next;

        if (ptr->next != NULL)
        {
            ret->next = ptr->next;
            ptr->next = ret;
        }
        else    // add to tail
            ptr->next = ret;
    }

    return;
}

int findKthLargest(int* nums, int numsSize, int k) {
    head = create(nums[0]);
    for (int i=1; i<numsSize; i++)
        insertHeap(nums[i]);

    struct ListNode* ptr = head;
    for (int i=1; i<k; i++)
    {
//printf("%d\n", ptr->val);
        ptr = ptr->next;
    }
    return ptr->val;

}

但我現在有點懶得寫啊哈哈哈（乾笑）

想說要寫一個quick sort 但好像寫出了奇怪的東西?!

感覺也沒錯啊QQ 但是超時了Orz 是在瞎忙什麼哈哈哈（崩潰）

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}

void myqsort(int *nums, int left, int right)
{
    if (left>=right)
        return;

    if (right -left <2)
    {
        if (nums[left]> nums[right])
            swap(&nums[left], &nums[right]);
        return;            
    }
    int pivot = nums[left];
    int l = left+1;
    int r = right;
    while (l<r)
    {
        while (r>left && nums[r]>=pivot)
            r--;
        while (l<right && nums[l]< pivot)
            l++;
        if (l<r)
            swap(&nums[l], &nums[r]);
        else
        {
            swap(&nums[left], &nums[r]);
            myqsort(nums,left,r-1);
            myqsort(nums,r+1,right);
        }
    }
    //myqsort(nums,left,r-1);
    //myqsort(nums,r+1,right);
}
int comp(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}

int findKthLargest(int* nums, int numsSize, int k) {
    myqsort(nums,0, numsSize-1);
//    qsort(nums, numsSize, sizeof(int), comp);
for (int i=0; i<numsSize;i++)
printf("%d %d\n", i , nums[i]);
    return nums[numsSize-k];    
}

沒想到自己以前存的qqsort竟然可以PASS = =+

難道要拿出婷婷教授的筆記回來看了嗎囧

看來要過兩天再回來寫一次了Orz

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}

void myqsort(int *nums, int left, int right)
{
    int l=left, r=right;
    int mid = (l+r)/2;
    int pivot= nums[mid];
    while (l<=r)
    {
        while (nums[l]< pivot)
            l++;
        while (nums[r]>pivot)
            r--;
        if (l<=r)
        {
            swap(&nums[l],&nums[r]);
            l++;
            r--;
        }
    }
    if (left<r)
        myqsort(nums,left,r);
    if (l<right)    
        myqsort(nums,l,right);

}

int findKthLargest(int* nums, int numsSize, int k) {
    myqsort(nums,0, numsSize-1);
    return nums[numsSize-k];    
}

2018年2月11日星期日

[14] Longest Common Prefix

找出一群array裡面, 最長的共同prefix, 回傳這個共同prefix.
看大家好像都直接以第一個為基準去比別人,
但總覺得不同長度會有點麻煩?!
就萬一最長共同字串剛好就是長度最短的那個人,
降子在比較的時候, 勢必會比到結束字元, 然後感覺會爆炸
所以我一開始是先全部跑一遍找到最短的字串, 移到第一個, 當我的基準
因為不是太複雜的題目所以速度也沒有爆炸慢,
那就讓我們先找最短字串出來當基準吧呵呵呵～～～（櫻花樹下奔跑）

另外就是其實不必每次都跑到字串長度
雖然也是都會在不符合的時候就break了啦,
但總之可以設定最長為當下的max prefix length就可以了
反正前面已經有人只match到這裡, 不可能再長了.
以上.

Longest Common Prefix
void swap(char** a, char** b){
char *tmp;
tmp = *a;
*a=*b;
*b=tmp;
}

char* longestCommonPrefix(char** strs, int strsSize) {
if (strs== NULL || strsSize ==0)
return "";
if (strsSize==1)
return strs[0];
int i=0;
int minIndex=0;
for(i=0;i<strsSize;i++)
{
if (strlen(strs[i])< strlen(strs[minIndex]))
minIndex = i;
}

swap(strs[0],strs[minIndex]);
int preLength=0, max = strlen(strs[0]);
for(i=1;i<strsSize;i++)
{
for(preLength =0; preLength < max/*strlen(strs[0])*/; preLength++)
if(strs[0][preLength]!=strs[i][preLength])
break;
max = (preLength < max)? (preLength) : max;
}
char *ret = malloc(sizeof(char)*(max+1));
memset(ret,0,max+1);
strncpy(ret, strs[0], max);
return ret;
}

2018年2月10日星期六

[373] Find K Pairs with Smallest Sums （TBC）

結果寫不出來囧
放棄囧
用C寫的人真的那麼少嗎！！！
因為用C去寫heap感覺太花時間了
找好久找到一個不用implement heap的解法
想說先commit成功後看看有沒有其他比較漂亮的寫法
結果沒有XD!
一方面是送C的commit很少(吧)
另一方面用C寫heap真的是超級落落長啊啊啊啊啊～～～
先記下別人的寫法(沒有用heap的)
但其實也是用c++寫的, 還要翻譯XD！

給兩個已經排序好的array, 要回傳前k個相加最少的倆倆一組index
這真的很囉唆(而且還只是medium難度我哭!)
有可能有一樣大小的數字,
另外k 有可能大於最多可能的pair
總言之言總之
交叉來回比真是太麻煩了(抱怨again)
找到的不用heap的解法是, 用另外一個array去記錄nums1裡每個item 比對到了nums2的哪一個
在我的腦袋爆炸的同時LeetCode網站也爆炸了 XD
維修了兩個半小時XD
另外一定要記得init !要記得init ! 要記得init !
清空它們！！！
還有不要以為memset 就清空了, 妳可能傳了錯的值啊啊啊啊啊～～～～（奔入雨中）
最後雖然列了一個 TBC, 但我感覺我回來寫它的機率很低, 以上 Orz

Find K Pairs with Smallest Sums
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/

int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int** columnSizes, int* returnSize) {
if(nums1 == NULL || nums2==NULL || nums2Size ==0 || nums1Size==0)
{
*returnSize = 0;
return NULL;
}

int i,j;
*returnSize = k;

int **matrix = malloc(sizeof(int*)*(nums1Size * nums2Size));
int **ret = malloc(sizeof(int*)*(*returnSize));
*columnSizes = malloc(sizeof(int*)*(*returnSize));

for (i=0;i<nums2Size;i++)
{
matrix[i] = malloc(sizeof(int)*nums1Size);
for(j=0;j<nums1Size;j++)
{
matrix[i][j] = nums1[j]+nums2[i];
//printf("i %d j %d %d + %d = %d\n", i,j,nums1[i],nums2[j],matrix[i][j]);
}
}

for (i=0;i<(*returnSize);i++)
{
(*columnSizes)[i]= 2;
ret[i] = malloc(sizeof(int*)*2);

}
//////////////////////
{
int size = (k< nums1Size*nums2Size)? k:nums1Size*nums2Size;
int selected = 0;
int* index = malloc(sizeof(int)*(nums1Size));
int minVal;

*returnSize = size;

for(i=0;i<nums1Size;i++)
index[i]=0;

for(int t=0;t<size;t++)
{
minVal = INT_MAX;
for(int i=0; i<nums1Size; i++)
{
if(index[i]==nums2Size)
continue;

if(nums1[i] + nums2[index[i]] < minVal)
{
minVal = nums1[i] + nums2[index[i]];
ret[t][0] = nums1[i];
ret[t][1] = nums2[index[i]];
selected = i;
}
if(index[i]==0)
break;
}
index[selected]++;
}

return ret;
}
/////////////////////
return ret;
}

[55] Jump Game

其實真的想不太出來Orz
是不是被它分類在DP給限制住了呢 Orz
笨笨的QQ

給一個array 存大於等於0的數值,
每個數字代表最多可以前進幾格,
問能不能走到最後一格

Jump Game
bool canJump(int* nums, int numsSize) {
if (numsSize == 1)
return true;
else if (nums[0] == 0)
return false;

int *check = malloc(sizeof(int)*numsSize);
memset(check,0,sizeof(int)*numsSize);
int i,j;
for(i=0;i<numsSize-1;i++)
{
for (j=nums[i]; j>0; j--)
if(i+j <numsSize)
check[i+j]++;
}
for(i=1;i<numsSize;i++)
{
if (check[i]==0)
return false;
}
return (check[numsSize-1]>0)?true:false;

}
結果超級慢的哈哈哈(欲哭無淚)
好像只要這樣就好了QQ
bool canJump(int* nums, int numsSize) {
if (numsSize == 1)
return true;

int i,maxJump=0;
for(i==0;i<numsSize-1;i++)
{
if(i>maxJump)
return false;
maxJump = (maxJump > (nums[i] + i))? maxJump: (nums[i] + i);
}
return (maxJump>=numsSize-1)?true:false;
}

2018年2月9日星期五

[397] Integer Replacement

嗯.......... 嗯?! XD
給一個數字, 如果它可以整除2, 就除, (怎麼好像廢話XD)
不行的話, 可以加一或減一 (隨便你～)(其實不是隨便你, 因為要選最後次數小的)
加一或減一之後就可以整除2了(廢話again)那就除2 (贅詞超多XD)
要問經過幾次之後這個數會等於1 ?
要算最小的次數

看完題目就會想說,又可以加一又可以減一,
那應該是加一跟減一出來的結果一樣吧(才不是)不然幹嘛這麼隨意
結果竟然真的有差呢呵呵 (戳自己太陽穴)

Integer Replacement
int integerReplacement(int n) {
if (n==1)
return 0;

int count = 1;
if (n==2)
return 1;
if (n==3)
return 2;
int t1,t2;
//printf("%d count[%d]\n",n, count);
if (n%2==0)
count = count + integerReplacement((unsigned int)n /2);
else
{
t1 = integerReplacement((unsigned int)(n+1));
t2 = integerReplacement((unsigned int)(n-1));
count = count + ((t1 < t2) ? t1 : t2);
}
return count;
}
是說因為它規定是正整數,
所以不會有世界大的測資進來
再怎麼跑也是最久xx ms 那樣
所以看不出來我的運算時間如何(其實應該是很慢)
看了別人的解法有一些小技巧 (which is 我一向覺得很機歪, 誰曉得啊啊啊啊啊)
比方說整除二要怎麼寫呢?
直覺就是 n%2 == 0 嘛 , %是取餘數的意思 (該不會只有我的直覺長這樣)
不過原來可以寫 n&1 , 是1那就是奇數, 是0就是偶數,
會這樣寫的人是不是腦海中都有一個bit mapping的表呀是不是
不然為什麼會想到這樣寫?!
讓我想到之前工作的時後要弄一個加密的東西, 必須算它是不是某個數的倍數,
我寫完直觀寫法之後, code review完就變成一串 << && >> 左移右移and然後or 的東西
今天如果那code不是我寫的, 我又沒有內建bit運算的 mapping表(有這種東西嗎)的話
那我怎麼知道它是在幹嘛啊啊啊啊啊啊啊啊(左手背拍右手心)
(跳一下)
另外一個小技巧是,
可以用加一之後整除4的話 , 會比選擇減一來的快
為什麼你們會知道呢為什麼～～～～～（搖演算法奇才們的肩膀）
你們生下來就知道嗎
還是你們列了幾千幾萬個資料後確定是這樣呢？
是一個歸納法是不是
歸納出來的結論一定是Qmonster世紀無敵超級笨吧屋屋屋屋屋
打完收工.....(是在順便偷偷抱怨什麼喇XD!)

[116] Populating Next Right Pointers in Each Node

感動！！！
我覺得我的pointer真的有進步！！！ Orz

一般的binary tree, 除了left & right child之外,
左小孩指到右小孩, 右小孩指到parent的sibling的左小孩
(妳還是說中文吧)
沒想到很快就寫完了我真的要哭了（奔入雨中）（這樣也要奔入雨中XD?!）

Populating Next Right Pointers in Each Node
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* struct TreeLinkNode *left, *right, *next;
* };
*
*/
void connect_recursive(struct TreeLinkNode *ptr) {

if (ptr->left == NULL)
return;
ptr->left->next = ptr->right;
if (ptr->next != NULL)
ptr->right->next = ptr->next->left;
else
ptr->right->next = NULL;
connect_recursive(ptr->left);
connect_recursive(ptr->right);

}
void connect(struct TreeLinkNode *root) {
if (root == NULL)
return;
root->next = NULL;
if(root->left ==NULL)
return;

root->left->next = root->right;
root->right->next = NULL;
connect_recursive(root->left);
connect_recursive(root->right);
}
雖然別人寫起來好像更美呢哈哈哈哈哈
算了Orz
就是說先一層一層走完, 左到右, (因為有next, 所以可以直接往右)
走完一層再給它的left 往下一層走
用兩個 while 完成.

20230725更新

重寫一次，recursive 變漂亮了呢。這也算是一種進步吧XD

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *left;
 *     struct Node *right;
 *     struct Node *next;
 * };
 */

struct Node* connect(struct Node* root) {
    if (root==NULL)
        return NULL;
    if (root->left==NULL)
        return root;
    root->left->next=root->right;
    if (root->next !=NULL)
        root->right->next=root->next->left;
    connect(root->left);
    connect(root->right);
    return root;
}

2018年2月8日星期四

[164] Maximum Gap

紀念我開始寫LeetCode 以來
第一次一commit就過的感人時刻ToT
當然照例我又忽略了題意上的"Try to solve it in linear time/space."
明明那個才是重點Orz
但是不管啦不管啦不管啦～～～～（在地上打滾）

給一個沒有sort的array,
回傳它sort好以後兩兩相鄰的最大差值.

Maximum Gap
int compare(const void* a, const void* b){
return (*(int*)a-*(int*)b );
}

int maximumGap(int* nums, int numsSize) {
if(numsSize<2)
return 0;
int i;
int maxDiff=0;
qsort(nums,numsSize,sizeof(int),compare);
for(i=1;i<numsSize;i++)
{
if (nums[i]-nums[i-1] > maxDiff)
maxDiff = nums[i]-nums[i-1];
}
return maxDiff;
}
但聽說應該要用Bucket Sort或是Radix Sort XDDDD
明天醒來如果沒有挑戰hard的精神就來看看這個吧QQ
然後再順便看一下Pigeon hole principle XD
(要看的東西是不是越積越多, 然後都沒有清掉啊啊啊啊啊～～～～～～）
(再度陷入鬼叫模式）

update:
看完以後用bucket sort的概念,
結果果然沒想懂, 完全弄反Orz
為什麼還是覺得好浪費生命啊啊啊啊啊啊～～～～～
先找出最大值跟最小值, 因為已知個數,
所以排序以後的倆倆差值不會小於 gap = (max-min) /(size-1)
(據說就會講到Pigeon hole principle Orz）
於是使用 size個bucket, 存 min. min + gap , min+gap*2 ....的屬於這個bucket的值
也就是說同個bucket內任兩個數的差值不會大於 gap
然後只要存這個bucket內的最大跟最小值
把bucket處裡完以後, 再從頭掃一次bucket,
看相鄰的最大值跟最小值差, 取最大的（頭昏了Orz）
如果某個中間的bucket是空的, 把差值加上gap, 繼續看下一個 bucket;
或者是可以存上一次的有值bucket最大值 (昏again）
因為原本就設計bucket在 min和max中間,
所以可以確定第一個和最後一個bucket一定有至少一個item
而每個bucket如果只有一個item,它的最大值會等於最小值
(當然嘛, 自己跟自己, 最大最小都是自己)
結束..........(倒在地上口吐白沫ing )

int maximumGap(int* nums, int numsSize) {
if(numsSize<2)
return 0;
else if (numsSize==2)
return abs(nums[1]-nums[0]);
int i,max = 0;
int min = nums[0];
for (i==0;i< numsSize; i++)
{
if (nums[i]> max)
max = nums[i];
if(nums[i]<min)
min = nums[i];
}
int gap = (max - min) / (numsSize -1) +1;
int *minBucket = malloc(sizeof(int)*(numsSize));
int *maxBucket = malloc(sizeof(int)*(numsSize));
memset(minBucket, -1 , sizeof(int)*numsSize);
memset(maxBucket, 0 , sizeof(int)*numsSize);
for(i=0;i < numsSize; i++)
{
int index = (nums[i]-min)/gap;
if(minBucket[index]== -1 || minBucket[index] > nums[i])
minBucket[index] = nums[i];
if(maxBucket[index]<nums[i])
maxBucket[index]=nums[i];
}

int diff = 0;
int base = maxBucket[0];
for(i=1; i< numsSize;i++)
{
if(minBucket[i] < 0)
continue;

if((minBucket[i]-base) > diff)
diff = minBucket[i]-base;
base = maxBucket[i];
}
return diff;
}

[73] Set Matrix Zeroes

給一個矩陣,
零的item必須把它的行跟列全部都設成0
存回原本的矩陣回傳
被改成0的部分不適用"行跟列全部都設成0"的規則
也就是說改成0的規則不必生生不息的往下傳遞這樣.
感覺不是一個好的解法,
但執行時間好像沒有慢到哪裡去啊（？）
那就這樣好了哈哈哈哈哈(顯示為忽略題意上的space問題)

void setZeroes(int** matrix, int matrixRowSize, int matrixColSize) {
int r = 0;
int c = 0;
int Rarray[matrixRowSize];
int RCount=0;
int Carray[matrixColSize];
int CCount=0;

int i,k;
for(r=0;r<matrixRowSize; r++)
{
for (c=0;c<matrixColSize;c++)
{
if (matrix[r][c]==0)
{
Rarray[RCount++] = r;
break;
}
}
}

for (c=0;c<matrixColSize;c++)
{
for(r=0;r<matrixRowSize; r++)
{
if (matrix[r][c]==0)
{
Carray[CCount++] = c;
break;
}
}
}

for(k=0;k<RCount;k++)
for (i=0;i<matrixColSize;i++)
matrix[Rarray[k]][i] = 0;
for(k=0;k<CCount;k++)
for (i=0;i<matrixRowSize;i++)
matrix[i][Carray[k]] = 0;
}
據說可以在讀到零的時候把該row和該column的第一個設成0
也就是和我拿Carray 和Rarray來存一樣意思,
但是不需要另外的space, 而是用原本的matrix空間
hmm~ brilliant.

[75] Sort Colors

增加信心用Orz
(還是其實是打擊呢哈哈 XD)
有0, 1, 2 三種顏色存在array裡
把它們依照0,1,2排列
產生 00000 11111 2222 這樣的array.
一開始還以為要產生 012012012的
沒想到不是Orz
再度想難了是嗎Orz

Sort Colors
void sortColors(int* nums, int numsSize) {
int i,numsI=0;
int count[3] = {0,0,0};
for (i=0;i<numsSize;i++)
count[nums[i]]++;

for (i=0;i<3;i++)
for (int k = 0; k< count[i];k++)
nums[numsI++]= i;
}

據說是可以只跑一次,
把0都掃到左邊, 2都掃到右邊, 中間自然留下1 這樣.
唉覺得好累
今天進度超級少QQ
傷心

20221126 更新

說是有一個algorithm 叫做 Dutch national flag problem: https://en.wikipedia.org/wiki/Dutch_national_flag_problem

然後重新用這個演算法寫了一遍兒～～～

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a=*b;
    *b=tmp;
}
void sortColors(int* nums, int numsSize){
    int low, mid,high;
    low=0;
    mid=0;
    high=numsSize-1;
    while (mid<=high)
    {
        if (nums[mid]==1)
        {
            mid++;
        }
        else if (nums[mid]==2)
        {
            swap(&nums[mid], &nums[high]);
            high--;
        }
        else //nums[mid]==0
        {
            swap(&nums[low], &nums[mid]);
            low++;
            mid++;
        }

    }

}

訂閱：文章 (Atom)

2018年2月13日 星期二

2018年2月11日 星期日

2018年2月10日 星期六

2018年2月9日 星期五

2018年2月8日 星期四

2018年2月13日星期二

2018年2月11日星期日

2018年2月10日星期六

2018年2月9日星期五

2018年2月8日星期四