[85] Maximal Rectangle

跟前一題類似, 但是找正方形改成找矩形,
變很難
半放棄狀態
背答案要緊 囧

Maximal Rectangle
int max(int a, int b){
    return (a>b)? a: b;
}

int min(int a, int b){
    return (a<b)? a: b;
}
int maximalRectangle(char** matrix, int matrixRowSize, int matrixColSize) {
    if (matrixRowSize < 1 || matrixColSize < 1)
        return 0;
//    printf("%d x %d\n",matrixRowSize,matrixColSize);
    int height[matrixColSize];
    int left[matrixColSize];
    int right[matrixColSize];
    memset(height,0, sizeof(int)*matrixColSize);
    memset(left,0, sizeof(int)*matrixColSize);

    int i,j, area=0;
#if 1
    for (i=0;i<matrixColSize; i++)
    {
        right[i]= matrixColSize;
    }
#endif
    for (i=0;i<matrixRowSize; i++)
    {
        int tmpleft = 0;
        int tmpright = matrixColSize;

        for (j=matrixColSize-1; j>=0;j--)
        {
            matrix[i][j] = matrix[i][j] -'0';

       
            if (matrix[i][j]==1)
            {
                right[j] = min(right[j],tmpright);
            }
            else
            {  
                right[j] = matrixColSize;
                tmpright = j;
            }          
        }

        for (j=0;j<matrixColSize;j++)
        {

            if (matrix[i][j]==1)
            {
                height[j] = height[j] +1;
                left[j] = max(tmpleft, left[j]);
            }
            else
            {  
                height[j] = 0;
                left[j] = 0;
                tmpleft = j+1;
            }          

            int new = (right[j]-left[j])*height[j];
            if(new > area)
                area = new;

        }
    }
    return area;
}

[221] Maximal Square

不知道該說什麼QQ
反正是很沮喪的一天 QQ
先這樣吧QQ

找0,1矩陣裡最大的正方形
偷吃步的改了input
但是關鍵的傳值一直沒寫對
原來要用min QQ
感覺總是差那個最重要的臨門一腳
覺得傷心QQ

Maximal Square
int findmin(int a, int b, int c)
{
    if (a <= b && a <= c)
        return a;
    if (b <= a && b <= c)
        return b;
    if (c <= a && c <= b)
        return c;
    return a;
}

int maximalSquare(char** matrix, int matrixRowSize, int matrixColSize) {
    if (matrixColSize < 1 || matrixRowSize < 1)
        return 0;

    int i,j,max;
    for(i=0;i<matrixRowSize;i++)
        for(j=0;j<matrixColSize;j++)
        {          
            matrix[i][j] = matrix[i][j] - '0';
            if (i==0 || j==0)
                continue;

            if (matrix[i][j] > 0)
            {
                if (matrix[i-1][j-1] > 0 && matrix[i-1][j] > 0 && matrix[i][j-1] > 0)
                {    
                    int min = findmin(matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1]);
                    matrix[i][j] = min+1;
                }
            }
        }
    max = 0;
    for(i=0;i<matrixRowSize;i++)
        for(j=0;j<matrixColSize;j++)
            if (matrix[i][j] > max)
                max = matrix[i][j];
    return (max*max);
 
}

[5] Longest Palindromic Substring(TBC)

雖然是一個很慢的解法但是不管呵
是自己寫出來的而且通過測資>///<
還是中等難度>///<
無論如何就是開心！！！

找最長的回文substring
Longest Palindromic Substring
int isPalindrome(char* s, int len)
{
    for (int i = 0; i<len/2;i++)
    {
        if (s[i] != s[len-1-i])
            return 0;
    }
    return len;
}

char* longestPalindrome(char* s) {
    if (s==NULL)
        return s;
    int len = strlen(s);
    int index = -1;
    int tarLen = 0;
    int i,j,tmp;

    for(i=0; i<len;i++)
    {
        int pre = 0;
        for(j=0;j<i; j++)
        {
            tmp = isPalindrome(s+j,i-j+1);
            if (pre > tmp)
                break;
         
            if (tmp > tarLen)
            {
                tarLen = tmp;
                index = j;
                break;
            }
            pre = tmp;          
        }
    }

    if (tarLen == 0 && index<0)
    {
        tarLen = 1;
        index = 0;
    }
    char *ret = malloc(sizeof(char)*(tarLen+1));
    strncpy(ret,s+index,tarLen);
    ret[tarLen] = 0;
    return ret;
}
明天天亮再看心情要不要去看別人的超高速解法XD
先放個TBC~~~ccc~~~~
see this : Manacher’s algorithm

[234] Palindrome Linked List

判斷linked list 是不是回文
這個我覺得學生時代我應該會QQ
現在完全不會XDDDD 看了別人寫法萬般看不懂～～～
一個一個印出來看才比較懂了一點QQ
桑心啊XD

雖然不是自己寫的, 純紀錄用.

漂亮解法長這樣, 使用遞迴:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* tmp;
bool check(struct ListNode* p)
{
    if (NULL == p)
        return true;

    bool isPal = check(p->next) & (tmp->val == p->val);
    tmp = tmp->next;
    return isPal;
}

bool isPalindrome(struct ListNode* head) {
    tmp = head;
    return check(head);
}

遞迴的意思是有一個pointer 指著head, 然後另一個會移動的就遞迴下去, 一直往後next 直到null (也就是最後一個node) 此時就可以比較兩個pointer 是不是一樣, 接著

(1) 原本指著head 的的pointer 指向下一個node

(2)已經遞迴到tail 的那個這時可以return回上一層, 也就是tail 的前一個node

在此時又去比較(1)和(2), 一樣的話就表示目前還是回文, 繼續repeat, 一個往後一個往前 (遞迴的那個return 回去就是移回上一個)

如此這邊就可以頭尾夾擊(?) 沿路判斷是不是相等 a.k.a 是不是回文了

比較簡單的是先找到中間mid ,
然後reverse其中一半,
再比看看兩半是不是一樣,
就可以確定是不是回文.

[673] Number of Longest Increasing Subsequence

衍伸題來了～（比樓下）
其實我還是覺得我不太懂XD
不過算了好了 XD.............

673. Number of Longest Increasing Subsequence
int findNumberOfLIS(int* nums, int numsSize) {
    int i , j;
    int *len = malloc(sizeof(int)*numsSize);
    int *count = malloc(sizeof(int)*numsSize);
    int max = 0, max_count=0;


    for(i=0;i<numsSize;i++)
    {
        len[i] = 1;
        count[i] = 1;
        for(j=0;j<i;j++)
        {
            if(nums[i]>nums[j])
            {
                if (len[i]==len[j]+1)
                    count[i]+=count[j];
                if (len[i] < len[j]+1)
                {
                    len[i] = len[j]+1;  
                    count[i] = count [j];
                }
            }
        }    
        if (len[i] > max)
            max = len[i];

    }
    for(i=0;i<numsSize;i++)
        if(max == len[i])
            max_count += count[i];
    return max_count;
}

[300] Longest Increasing Subsequence

其實是先寫它的衍伸題(但是不會寫XD)才看到這題
難怪我會把衍伸題弄成找長度(因為比較直覺QQ)
不過微慌張所以其實沒想很懂就看解法了
真是各種奧義QQ
只寫了 O(n^2), 據說可以弄成O(nlogn)
是每次存所有item裡的最小到最大(當時)
它其實不會是真正的subarray, 但是長度會是這題要的 LIS
且最後一個item也會是真正LIS時的最後結束的item
真是太玄了太玄了我沒時間了我們往下一題吧
(說是沒有時間但是慌張的來回跺步吃東西看電視消除焦慮神來也麻將試試手氣倒是有不少時間......)

Longest Increasing Subsequence
int lengthOfLIS(int* nums, int numsSize) {
    int i , j;
    int *len = malloc(sizeof(int)*numsSize);
    for(i=0;i<numsSize;i++)
    {
        len[i] = 1;
        for(j=0;j<i;j++)
        {
            if(nums[i]>nums[j])
            {
                if (len[i] < len[j]+1)
                    len[i] = len[j]+1;
            }
        }      
    }
    int max = 0;
    for(i=0;i<numsSize;i++)
    {
        if (len[i] > max)
            max = len[i];
    }
    return max;
}
這個解法是用一個array去存每個item可以有的LIS長度
一次用一往上加.
總覺得好像有寫過很類似的,
糾竟是哪題呢?!

然後發現可以加速一咪咪XD!!!!
喜歡把事情拆開一步一步做難道錯了嗎～～～～～～
int lengthOfLIS(int* nums, int numsSize) {
    int i , j;
    int max = 0;
    int *len = malloc(sizeof(int)*numsSize);
    for(i=0;i<numsSize;i++)
    {
        len[i] = 1;
        for(j=0;j<i;j++)
        {
            if(nums[i]>nums[j])
            {
                if (len[i] < len[j]+1)
                    len[i] = len[j]+1;  
            }
        }      
        if (len[i] > max)
            max = len[i];
    }
    return max;
}

[347] Top K Frequent Elements

感人！！！
我竟然寫出來惹  XDDDD
（又不是什麼世界難的題目, 感動屁XD）
（何況妳好像沒有達到題目要求的 O(nlogn) 吧 XD）
（不管啦可是我跑出來時間很快耶XD）
（重點是我有寫出來就偷笑啦還管什麼Time Complexity啊！）
（但那就是人家要考的東西啊妳XD）
（跳一下）（根本是跳很多下）
這題就是說要找出出現次數最多次的前k 個
比方說1,1,1,2,2,3 要找 k = 2 的話就是 1跟2 因為它們出現三次跟兩次是最多次的前兩組
一開始想亂寫用兩個hash先hash過來再hash回去
發現那如果出現次數一樣的話, 它就消失了XD（magic ~~~~~）
才知道原來又要使用到bucket sort 了 QQ
要記住若是排序的根據有兩個, 就要用bucket sort呀記起來好嗎～～～～～～
比方說撲克牌要照花色大小排列, 那就是bucket sort的使用時機惹～～～
像這題就是....（咦？！XD）

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

typedef struct _BucketArray
{
    int value;
    int count;
}BucketArray;  

void addBucket(BucketArray *bucket,int size, int count, int num){
//    printf("count %d num %d\n", count, num);
    for (int i =0 ; i<size; i++)
    {
        if (count > bucket[i].count)
        {
            if (bucket[i].count != 0)
                for (int j=size-1;j>i; j--)
                {
                    bucket[j].value = bucket[j-1].value;
                    bucket[j].count = bucket[j-1].count;
                }
            bucket[i].value = num;
            bucket[i].count = count;
            break;
        }
    }
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
    int *ret = malloc(sizeof(int)*k);
    *returnSize = k;
    int max = INT_MIN;
    int min = INT_MAX;
    int i,j;
    for(i=0; i<numsSize;i++)
    {
        if(nums[i] > max)
            max = nums[i];
        if(nums[i] < min)
            min = nums[i];
    }
//index + min
//hash = 出現次數  
    int hashSize= max-min+1;
    int *hash = malloc(sizeof(int)*(hashSize));
    memset(hash,0,sizeof(int)*hashSize);

    for(i=0; i<numsSize;i++)
        hash[nums[i]-min]++;

    BucketArray *bucket= malloc(sizeof(BucketArray)*k);
    memset(bucket,0,sizeof(BucketArray)*k);
    for (i=0;i<hashSize;i++)
    {
        addBucket(bucket,k, hash[i], i+min);
    }
    for (i=0;i<k;i++)
        ret[i] = bucket[i].value;
    return ret;
}
[20251029]更新

其實我看不懂當年我在寫什麼 囧 先來個qsort 版本

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

struct hash{

int val;

int freq;

};

int comp(void const *a, void const *b){

return ((*(struct hash**)b)->freq -(*(struct hash**)a)->freq );

}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {

struct hash **myHash = calloc (20001 , sizeof(struct hash*));

for (int i=0; i<20001; i++)

myHash[i]= calloc (1, sizeof(struct hash));

for (int i=0; i<numsSize; i++)

{

int idx = nums[i]+10000;

myHash[idx]->freq ++;

myHash[idx]->val = nums[i];

}

qsort((void *)myHash,20001, sizeof(struct hash*),comp);

int *ret= calloc(k, sizeof(int));

for (int i=0; i<k; i++)

ret[i]= myHash[i]->val;

*returnSize =k;

return ret;

}

之後再來個heap 版本 ？！

[20251111] 失敗了 XD 不想寫heap XD

用了先sort , 再依序把出現次數算出來，再丟去一個二維array, index是出現次數，若有相同出現次數的則往後長 

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int comp(const void *a, const void *b){

return (*(int*)a-*(int*)b);

}

struct freq{

int val;

int count;

};

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {

qsort(nums, numsSize, sizeof(int), comp);

struct freq *hash = calloc (numsSize, sizeof(struct freq));

int idx = 0;

int max = INT_MIN;

for (int i=0; i<numsSize; i++)

{

int count =1;

while (i<numsSize-1 && nums[i]==nums[i+1]){

count++;

i++;

}

hash[idx].count=count;

hash[idx].val=nums[i];

if (hash[idx].count>max)

max = hash[idx].count;

idx++;

}

int **queue = calloc (max+1, sizeof(int *));

int *q_idxs=calloc (max+1, sizeof (int));

for (int i=0; i< max+1; i++){

queue[i]= calloc (numsSize, sizeof (int));

}

for (int i=0; i<idx; i++){

int tmp = hash[i].count;

queue[tmp][q_idxs[tmp]]= hash[i].val;

q_idxs[hash[i].count]++;

}

*returnSize = 0;

int *ret = calloc (numsSize, sizeof (int));

for (*returnSize =0; *returnSize < k;){

//find index

for (int j=0; j< q_idxs[max]; j++)

ret[(*returnSize)++]= queue[max][j];

max--; // we have used one max count

while (max>=0 && q_idxs[max]==0)

max--;

}

return ret;

}

[242] Valid Anagram

寫多了就上手～～～（嗎XD)
判斷兩個字串是不是異位構詞
這個我最喜歡的例子當然就是哈利波特囉!!!

----引用分隔線引用分隔線-------
"Tom Marvolo Riddle" = "I am Lord Voldemort"
(湯姆·魔佛羅·瑞斗 = 我是佛地魔)
----引用分隔線結束分隔線引用分隔線結束分隔線-------

雖然一次commit就過了, 不過發現別人(每次都是接這句XD)有更省memory的作法啊啊啊啊啊為什麼我又沒想到呢為什麼?! (搥心肝)

用兩個hash (?) 來存, 其實也可以只用一個, 讓它們加加減減,

意思是一樣的. 結束 XD

Valid Anagram
bool isAnagram(char* s, char* t) {
    int src[26]={0};
    int dst[26]={0};
    int i;
    int src_len = strlen(s);
    int dst_len = strlen(t);
   
    for (i=0;i<src_len;i++)
        src[s[i]-'a']++;
    for (i=0;i<dst_len;i++)
        dst[t[i]-'a']++;

    for (i=0;i<26;i++)
        if (src[i]!= dst[i])
            return false;
   
    return true;  
}

「20231123更新」

又寫了一次，沒太大的不一樣，就降  XD

bool isAnagram(char* s, char* t) {

int lenS = strlen(s);

int lenT= strlen(t);

if (lenS != lenT)

return false;

int *countS = calloc (26, sizeof(int));

int *countT = calloc (26, sizeof(int));

for (int i=0;i<lenS;i++)

{

countS[s[i]-'a']++;

countT[t[i]-'a']++;

}

for (int i=0;i<26; i++)

if (countS[i]!=countT[i])

return false;

return true;

}

[20251101更新]

又又又寫了一次，因為瞄到別人的寫法所以這次不太一樣 ？！XD

不過也可以在第一次的迴圈加加減減，在第二個迴圈檢查hash是不是有人不等於零，是一個感覺比較美麗的寫法？！速度可能要看是字串的長度比較大，還是hash要檢查的長度比較大！

A

bool isAnagram(char* s, char* t) {

int s_len = strlen(s);

int t_len = strlen(t);

if (s_len != t_len)

return false;

int *hash = calloc(26 , sizeof(int));

for (int i=0; i<s_len; i++)

hash[s[i]-'a']++;

for (int i=0; i<t_len; i++)

{

hash[t[i]-'a']--;

if (hash[t[i]-'a']<0)

return false;

}

return true;

}

B

bool isAnagram(char* s, char* t) {

int s_len = strlen(s);

int t_len = strlen(t);

if (s_len != t_len)

return false;

int *hash = calloc(26 , sizeof(int));

for (int i=0; i<s_len; i++)

{

hash[s[i]-'a']++;

hash[t[i]-'a']--;

}

for (int i=0; i<26; i++)

{

if (hash[i]!=0)

return false;

}

return true;

}

[198] House Robber （20221125 更新）

給一個array代表每間房子的$$數目
若相鄰的房子都被搶了會引起警報系統報警
所以只能間隔著搶 (好爛的警報系統XD)
請找出搶劫（還是偷竊啊其實一樣吧總之題目是用rob, 雖然這根本不是重點, 現在是在考 DP不是在考英文啊啊啊~~~~~~）並且不引發警報系統的前提之下可以搶到多少錢（真是教壞囝仔大小啊~）（是說有人知道囝這個字怎麼唸嗎?! 給你三秒鐘～～～～一～～～二～～～三～～～唸簡！！！這真是太神奇了寫程式長知識～寫程式的小孩不會變壞喔啾咪 >. ^ ）（只會變得不太正常）（是否不應該繼續離題）

感謝 這個作者 （leetcode網站）的說明
他寫的好清楚啊啊啊啊滾向東又滾向西
XX公司想要hire的就是這種人吧
我去XX公司掃樓梯就好了我應徵什麼RD呢～（哭）

每一個item都有 搶 跟 不搶 的選項（根本就不應該有搶的選項啊啊啊教壞囝仔大小）
搶的話, yes 會等於 這間的錢 加上 前一間不搶的錢 (一路搶下來)
不搶的話, no 會等於 前一間搶 或是 前一間不搶 取大的那一個
一路算下去, 再回傳yes 或 no 的最大值.
其中tmp 是用來紀錄 "前一次的yes" (或是拿來紀錄no也可以)
沒用tmp存的話, 它會算成這一次的yes (或no)
就是這樣了！（擊掌）

House Robber
#define max(a, b) ((a)>(b)?(a):(b))

int rob(int* nums, int numsSize) {
    int yes=0,no =0,i;
    for(i=0;i<numsSize;i++)
    {
        int tmp = yes;
        yes = nums[i] + no;
        no = max(tmp,no);
    }
    return max(yes,no);
}

20221125 更新

感覺我快要參透DP了 ！！！

#define MAX(A,B) ((A>B)?(A):(B))

int rob(int* nums, int numsSize){

if (numsSize<2)

return nums[0];

int *money=calloc(numsSize,sizeof(int));

money[0]=nums[0];

money[1]=MAX(nums[0],nums[1]);

for (int i=2;i<numsSize;i++)

money[i]= MAX(money[i-1] ,nums[i]+money[i-2] );

return MAX(money[numsSize-1],money[numsSize-2]);

}

[142] Linked List Cycle II

於是第二塊蛋糕來了
但有點奇怪QQ
原本是用val來比的
但是會錯 O.o
只好改成pointer比
但是為什麼呢?(沉思)

Linked List Cycle II
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL)
        return NULL;

    struct ListNode *one, *two;
    one = two = head;
    while (one->next != NULL && two->next != NULL)
    {
        one = one -> next;
        two = two->next;
        if (two->next == NULL)
            return NULL;
        two = two->next;
        if (one == two)
        {
            two = head;
            while (one!=two)
            {
                one = one->next;
                two = two->next;
            }
            return one;
        }  
    }
    return NULL;

}

20240807 更新

為了複習重寫了，果然已經忘記為什麼它可以這樣跑了XD（大笑）

但現在的寫法已經有系統多了，可喜可賀。

struct ListNode *detectCycle(struct ListNode *head) {

struct ListNode *pfast , *pslow;

pfast = head;

pslow = head;

while (pfast != NULL && pfast->next != NULL)

{

pslow = pslow->next;

pfast = pfast->next;

pfast = pfast->next;

if (pslow == pfast)

{

pfast = head;

while (pslow != pfast)

{

pslow = pslow->next;

pfast = pfast->next;

}

return pslow;

}

}

return NULL;

}