Qmonster吃喝玩樂大事記: 2月 2018

2018年2月26日星期一

[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);

}

2018年2月25日星期日

[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;
}

2018年2月24日星期六

[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;
}

2018年2月23日星期五

[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;
}

[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;

}

[141] Linked List Cycle

來啦～Linked List cycle的判斷我來啦～～～
經過重覆數字的判斷以後（龜兔賽跑演算法）, 就照做就好了
一塊蛋糕
只是我的蛋糕好像長的比別人的醜XD
為什麼又有多做很多判斷的感覺QQ

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

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 false;
two = two->next;
if (one->val == two->val)
return true;
}
return false;
}

然後又發現別人有偷吃步的方法！！！
這真是不可取 XD！
就是如果可以確定linked list裡面的值會是某些類別的話
（比方說一定是正數, 或是介於oo和 xx之間）
那就可以遍歷這個linked list (這個用語感覺不是我會用的詞XD）
每次將value 設成一個不在範圍內的值（比方說-1, 只要你的其它linked list不會有這個value即可）,那麼繼續往下走, 如果走到一個node的value是你設的這個只有你知道的值（這個世界上只有三個人知道, 一個是linked list, 一個是我, 另一個我不能說!）（冷）, 那麼就表示你回到一個你曾經走過的node了, cycle存在！！！

20230616 更新為了練習linked list 又寫了一次

看起來沒什麼不一樣 XD 寫題目的果然是同一個我 XDDDDD

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode *pSlow, *pFast;
    pSlow= head;
    pFast= head;
    while (pSlow != NULL && pFast !=NULL)
    {
        pSlow=pSlow->next;
        pFast=pFast->next;
        if (pFast !=NULL)
            pFast=pFast->next;
        else
            return false;
        if (pSlow == pFast)
            return true;
    }
    return false;
}

[387] First Unique Character in a String

剛好昨天寫的一個在一開始的準備步驟有點像的
所以很快KO (?)
找出一個array裡面, 第一個"只出現一次的字母"的index
可以假定字母都是小寫.
原本用兩個for想暴力法比完, 結果完全想錯Orz
開始寫之前實在是要再細想一下,
不能老是用結果去回推啊啊啊啊～～～～（戳自己太陽穴）

First Unique Character in a String
int firstUniqChar(char* s) {
int i,j;
int len = strlen(s);
if(len==1)
return 0;
int letters[26] = {0};
for (i=0;i<len;i++)
letters[s[i] - 'a']++;
for(i=0;i<len;i++)
if(letters[s[i] - 'a'] == 1)
return i;
return -1;
}

用直覺的寫完以後,
發現不用 - 'a' 也可以！！！
減a 會讓它變慢！！！
天！！！
真是太偷吃步了
想不到這種加速法應該是因為我很正直吧(誤)
開個256的hash的話就可以少算很多次減a
但若是要求memory的時候, 只開26個就比256個少很多了吧哼 (其實根本沒差多少 XD）
總之更快的方法在下面:
int firstUniqChar(char* s) {
int i,j;
int len = strlen(s);
if(len==1)
return 0;
int letters[256] = {0};
for (i=0;i<len;i++)
letters[s[i]]++;
for(i=0;i<len;i++)
if(letters[s[i]] == 1)
return i;
return -1;
}
是否要大家來找碴一下XD 感覺很好找雖然它們長的真的很像QQ
前往下一題gogo~~~

2018年2月22日星期四

[378] Kth Smallest Element in a Sorted Matrix

當妳迷惘的時候
就用qsort啊 (?)
只要qsort開下去
就算不知道病因, 病也好了一半
比看醫生還有效
江湖郎中Q術士如是說.

Kth Smallest Element in a Sorted Matrix
int compare(const void *a, const void *b)
{
return (*(int*)a - *(int*)b);
}

int kthSmallest(int** matrix, int matrixRowSize, int matrixColSize, int k) {
int i,size= matrixRowSize*matrixColSize;
int *new = malloc(sizeof(int)*size);
for (i=0;i<size;i++)
{
new[i] = matrix[i/matrixColSize][i%matrixColSize];
//printf("new[%d]\n", new[i]);
}
qsort(new,size,sizeof(int),compare);
return new[k-1];
}

只是想必題目少寫了：不可以另外copy成新的array吧 XD
現在memory那麼大, 開給我用有什麼關係XD
於是就看到很多heap啦 , priority queue啦這些 C 沒有內建的東西
據說是要用binary search 這樣.
哎唷二維的sorted array search起來感覺好麻煩歐
為什麼要用二維喇一維不好嗎? (妳意見也太多 XD)
就不貼別人的code了...

大意是說matrix[0][0]一定是最小值, matrix[n-1][n-1] 一定是最大值
相加除以二（或是 small + (big-small)/2 , 但這不是一樣嗎XD
可是寫後者的人多多多的多, 大概是怕overflow吧我猜.....)
於是我們有了一個中間值mid
接下來每行掃過去, i跟 j 都要逐個做, 因為可能下一行還有比較小的值
並且同一行可能只會有 n-x個人大於 mid
算是一個算左上角有多少人小於mid 的概念
算完看這個值有沒有大於 k (k是題目要找的第k小數目)
超過k的話表示k 在左半, 我們把big 改成 mid
反之則把small改成mid, 去找右半
雖然這樣, 下一輪還是要從i, j 等於0 開始從頭掃起
若是k 很大的話就是左上角的範圍越來越大
(感覺一直在做一樣的事好像很笨?!)
(就說用一維qsort很好嘛)
(好了我時間不多了(要去哪)既然有想過了我們就跳過這一題吧)
然後就可以找到第k小的數目了...The End XD

[316] Remove Duplicate Letters

其實不太知道自己在幹嘛Orz
這個算是對照著別人的code寫的
神秘的是 strlen(s) 先存起來就從timeout變成4ms !!!
怎麼可能！！！
amazing !!!

給一個字串要把重覆的字拿掉,
但是順序上必須是" smallest in lexicographical order among all possible results."
其實根本不知道是什麼意思Orz
照著例子看就是需要和它在原本字串出現的順序一樣
但又要最好從 abcde....依序排列
所以如果給 ccbabc
回傳的是 abc 這樣. (感覺古怪的規定 QQ)

雖然不是自己想的
但還是貼上來紀錄一下 QQ
Remove Duplicate Letters
void myRemoveDupLetters(char* s, char *ret, int* size) {
int len = strlen(s);

if(len<=0)
return;

int letters[26] = {0};
int i;
for (i=0;i<len;i++)
letters[s[i]-'a']++;

int small=0;
for (i=0;i<len;i++)
{
if (s[i] < s[small])
small = i;
if (--letters[s[i]-'a'] ==0)
break;
}
char c = s[small];
*size +=1;
ret[*size -1] = c;
int index =0;
for (i=small+1; i<len; i++)
{
if (s[i]!= c)
s[index++] = s[i];
}
s[index] = '\0';
myRemoveDupLetters(s, ret, size);
}

char* removeDuplicateLetters(char* s) {
char *ret = malloc(sizeof(char)*27);
int retSize = 0;
myRemoveDupLetters(s,ret, &retSize);
ret[retSize]= '\0';
return ret;
}

[20220610 update]

沒想到事隔多年我又刷到了同樣這一題而且完全沒有發現這件事XD

然後發現當年沒搞懂果然現在也沒搞懂啊哈哈哈哈哈(奔入雨中)

但有個好消息是現在有不用recursive的解法了(?)

雖然沒有一個一個印出來之前我還是不知道它在幹嘛,

但至少比recursive 來的簡單一點Orz

#include <string.h>

char * removeDuplicateLetters(char * s){

int length = strlen(s);

int allChar[26]={0,};

int choose[26]={0,};

int i,j;

int retCount=0;

for (i=0; i<length;i++)

{

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

if (allChar[s[i]-'a']==1)

retCount++;

}

char *retStr = malloc(sizeof(char)* (retCount+1));

memset(retStr,0,retCount+1);

for (i=0,j=0;i<length;i++)

{

allChar[s[i]-'a']--;

if (choose[s[i]-'a']) //already choose

continue;

while(j>0 && s[i] < retStr[j-1] && allChar[retStr[j-1]-'a'] > 0)

{

choose[retStr[j - 1] - 'a']=0;

j--;

}

retStr[j++]=s[i];

choose[s[i]-'a']=1;

}

retStr[retCount]='\0';

return retStr;

}

[287] Find the Duplicate Number

還以為要用XOR, 結果不用XD
一整個想太多XDDDDDD
但是不能更改輸入的array,
又要求只能有O(1)的extra space
感覺很難！（就說是hard了啊XD)

先來個暴力法
Find the Duplicate Number
int findDuplicate(int* nums, int numsSize) {
int i,j;
for (i=0;i< numsSize-1;i++)
for (j=i+1;j<numsSize;j++)
if (nums[i] == nums[j])
return nums[i];
return -1;
}

想當然時間很慢.
看了討論原來這是有名的龜兔賽跑演算法 ! （Tortoise and Hare Algorithm）
也叫做 Floyd’s cycle detection algorithm
證明太複雜了我也不確定我有沒有懂
用來找出一個linked list裡面有沒有cycle , cycle的長度, cycle的起點.
說是讓烏龜一次走一步, 兔子一次走兩步, 若走完整個linked list都沒有相遇,
表示裡面沒有環.
若有環, 它們走一走一定會在環裡面相遇.
相遇時, 假設烏龜走了 k 步, 兔子走了 2k 步,
這個k 一定是環的長度的整數倍, 若環的長度是 r , 也就是 k = nr
(因為兔子比烏龜多走了環的倍數步, 也就是 2k - k = k 可推知 k = nr )

難後呢！（已經昏）（昏的是我不是烏龜也不是兔子）（沒人誤會！）
龜兔重逢後讓兔子留在原地, 烏龜一次一步往前走, 下一次牠們再相遇,
這次烏龜走的步數就是環的長度. （這部分感覺容易理解！）

又然後, 建立在上面的推論, 設linked list的起點走到環的起點是 s 步,
再假設龜兔相遇的地方是環開始後的第 m 步,
我們剛剛說烏龜在k 處和兔子相遇,
所以 s + m = k = nr
這時讓烏龜（或兔子也可以 whatever）回到起點,
另一隻留在相遇處m
讓兩隻都同時前進, 一次前進一步,
這次兩隻相遇的地方就會是環的起點！！！（到底為什麼）
有一個說法是留在原地的因為是在環的裡面繞, 所以是 nr
回到起點的會再走 s + m 步 (感覺也是廢話) s+m = nr (這剛剛好像講過XD）
那跟牠們相遇的地方是不是環的起點到底有什麼關係XD (對啦我沒天份)
s+m = nr
s = nr -m
s = (n-1) r + r - m
然後呢！！！為什麼可以取n = 1 然後就變成 s = r - m ?! 囧
好吧放棄XD 反正證明就是這樣
感覺我應該寫在找 linked list cycle的地方
那我為什麼不呢？！因為我還沒寫它啊哈哈哈哈哈～～～～

更驚人的就是
為什麼找出重覆的數字, 會讓你聯想到龜兔賽跑演算法呢為什麼～～～～（搖想出來的人的肩膀）（各種抱怨）（結果寫到這裡肚子餓了, 弄個早餐先XD）

***吃完早餐分隔線吃完早餐分隔線***
結果雖然勉強搞懂linked list的 cycle,
套到這題: 找重覆數字又覺得很奇怪XD
為什麼這裡的一步兩步, 不是指index的加一跟加二呢?!
而是指拿array 裡的數字出來當它的步數
這樣還是一步兩步嗎?! （請說中文啊XD～～～～）
總之code 長這樣:
int findDuplicate(int* nums, int numsSize) {
int one=nums[0];
int two=nums[nums[0]];
while (one != two)
{
one = nums[one];
two = nums[nums[two]];
}
two = 0;
while (one!=two)
{
one = nums[one];
two = nums[two];
}
return one;
}
這意思就是說如果array長的是 {4,1,2,2,3}
那我的一步one 就是 nums[0] = 4
兩步two 是 nums[nums[0]] = 3
how come!!!!!!
這跟龜兔賽跑的一步兩步為什麼看起來一點關係都沒有！！！
是一個取總長的概念嗎！！！
演算法真是太難了（難的好像是數學）
我還是回家吃自己吧呵呵呵(煮過期泡麵ing)

聽說是一個移動距離會怎樣怎樣的概念
然後這是一個例子 : leetcode discusstion
但是用例子來看我還是不懂它們為什麼要這樣寫
啊..............(倒地)

2018年2月21日星期三

[206] Reverse Linked List

linked list反轉
其實真的是很基本的題目 QQ
不過我寫的好像贅步很多啊奇怪XD
別人的迴圈怎麼只要四行呢 XD
但是這次submit 之後竟然是0ms 吶擊敗全部人的速度吶
雖然明知是bugXD 也沒有比較的意義XD
還是存檔紀念一下哈哈哈
(果然第二次跑就要4ms了噗)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL)
return head;
struct ListNode *p0, *p1, *p2;
p0 = NULL;
p1 = head;
p2 = p1->next;
while (p2 != NULL)
{
struct ListNode* tmp;
tmp = p2->next;
p1->next = p0;
p2->next = p1;
p0 = p1;
p1 = p2;
p2 = tmp;
}
p1->next = p0;
return p1;
}

改了一下, 也可以四行處理完了, 開薰!!!
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL || head->next == NULL)
return head;
struct ListNode *p0, *p1, *p2;
p0 = NULL;
p1 = head;
p2 = p1->next;
while (p2 != NULL)
{
p1->next = p0;
p0 = p1;
p1 = p2;
p2 = p2->next;
}
p1->next = p0;
return p1;
}

20230617 更新

與時俱進～發現有更精簡的寫法XD

之一是要處理最後一步，如果是上面的寫法，在離開迴圈後要記得把最後一個pointer 再往前指；如果是下面的寫法，因為往回指的部份已經寫在迴圈裡了，那就變成回傳的ptr會變成前中後的前，因為他們已經往後shift 了！！！真是眉角很多啊QQ

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* p1, *p2, *p3;
    if (head == NULL || head->next==NULL)
        return head;
    p1=NULL;
    p2=head;
    p3=NULL;
    while(p2 != NULL)
    {
        p3=p2->next;
        p2->next=p1;
        p1=p2;
        p2=p3;
    }
    return p1;
}

20230816 再次更新

面試又GG了，竟然還是忘記把最後一根往回指XD 我真的是對我自己很失望T—T

改成 pre , cur, 跟next 的寫法，感覺比較容易看懂？！

struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL)
        return head;
    struct ListNode *pre , *cur, *next;
    pre = NULL;
    cur = head;
    next = head->next;
    while (next != NULL)
    {
        cur->next = pre;
        pre = cur;
        cur = next;
        next=next->next;
    }    
    cur->next = pre;
    return cur;
}

（每次回圈裡處理QQ）

struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL)
        return head;
    struct ListNode *pre , *cur, *next;
    pre = NULL;
    cur = head;
    next = head->next;
    while (cur != NULL)
    {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }    
    return pre;
}

「20240130再再次更新」

不得了，我已經可以越寫越少行了XD 我真是對我自己的進步感到很感動(痛哭流涕)

雖然厲害的offer還是都無法到我身邊啊嗚嗚嗚嗚嗚

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *pre, *curr, *next;
    pre = NULL;
    curr = head;
    while (curr != NULL)
    {
        next = curr->next;
        curr->next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

訂閱：文章 (Atom)

2018年2月26日 星期一

2018年2月25日 星期日

2018年2月24日 星期六

2018年2月23日 星期五

2018年2月22日 星期四

2018年2月21日 星期三