Qmonster吃喝玩樂大事記: 2018

2018年4月16日星期一

[67] Add Binary

吸加加的string好方便QQ
不過還是寫的很醜
sign

Add Binary
class Solution {
public:
string addBinary(string a, string b) {
int lenA = a.length();
int lenB = b.length();
string ret;
int i,j, flag = 0;
for(i=lenA,j=lenB;(i>0 || j>0);i--,j--)
{
int anum = 0,bnum = 0;
if (i>0)
anum = a[i -1] - '0';
if (j>0)
bnum = b[j -1] - '0';

int tmp = flag + anum + bnum;
if (tmp > 1)
{
flag = 1;
tmp -=2;
}
else
flag = 0;
ret = to_string(tmp) + ret;

}
if (flag>0)
ret = "1" + ret;

return ret;
}
};

2018年4月14日星期六

[35] Search Insert Position

給一個sorted array和一個數字,
回傳這個數字在array裡的index
如果不存在, 則回傳依大小把它加進去的話它應該是多少index
吸加加到底是什麼
我現在好迷惘啊～～～（滾來滾去滾來滾去）

Search Insert Position
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int i, len = nums.size();
for (i=0;i<len;i++)
if (nums[i] >= target)
break;
return i;
}
};

[20251025 更]

什麼原來我當時是用C++寫嗎~_~

結果還是搞不懂return value 應該是什麼啊啊啊啊啊～（抱頭）

在這個題目裡, 兩種return 是一樣的。

while 給它等於, mid 給它加減一。

int searchInsert(int* nums, int numsSize, int target) {
    int l=0;
    int r = numsSize-1;
    while(l<=r)
    {
        int mid = l+(r-l)/2;
        if (nums[mid]== target)
            return mid;
        if (nums[mid]<target)
            l=mid+1;
        if (nums[mid]>target)
            r=mid-1;
    }    
    return l;
    return r+1;
}

2018年3月9日星期五

[94] Binary Tree Inorder Traversal

難得寫的還算精準
一回神發現題目還有一行:
Note: Recursive solution is trivial, could you do it iteratively?
真是討厭呢XD
不管～以後再說吧Orz
據說要用iterative的方法要用stack這樣.
你知道用C寫stack 且內容物是linked list 有多麻煩嗎有多麻煩嗎!!!(逼近出題者)
（啊不就是要考你嗎XD）
（啊網路上現成的lib 那麼多, 是威什麼一定要我在面試的短短幾十分鐘之內寫一份出來啦!!! 你上班難道都不用copy paste嗎有現成的難道你不用而硬要自己寫一個嗎?!）(是在抱怨什麼辣XD）（我絕對不是因為剛剛吃了一個難吃的煎鍋鬆餅等了超久花我兩百五結果超難吃而在遷怒.）（分明就是XD!）

Binary Tree Inorder Traversal
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
void getValue(int* ret, int *size, struct TreeNode* ptr){
if (ptr==NULL)
return;
getValue(ret, size, ptr->left);
ret[(*size)++] = ptr->val;
getValue(ret, size, ptr->right);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = 0;
if (root==NULL)
return NULL;
int* ret = malloc(sizeof(int)*(10000));
int retSize = 0;
struct TreeNode* ptr = root;
getValue(ret, &retSize, ptr);
*returnSize = retSize;
return ret;
}

20241007 update 覺得自己不會寫扣了QQ

int func(struct TreeNode* root, int *ret , int idx)

{

if (root == NULL)

return idx;

idx = func(root->left, ret, idx);

ret[idx++]=root->val;

idx = func(root->right, ret, idx);

return idx;

}

int* inorderTraversal(struct TreeNode* root, int* returnSize){

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

*returnSize = func(root, ret, 0);;

return ret;

}

2018年3月7日星期三

[78] Subsets

更新吸加加版本:
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ret(1,vector<int>());
for (auto &i : nums)
{
int len = ret.size();
for (int j=0;j < len;j++)
{
ret.push_back(ret[j]);
ret.back().push_back(i);
}
}
return ret;
}
};
太久沒寫吸加加, 原來我其實不會吸加加QQ
vector 是什麼QQ vector of vector 是什麼 QQ
auto也是第一次看到, 我是上古時代的人嗎XD
想嘗試用auto, 怎麼一直寫不粗乃!
原來第二個for有新增element , 長度會改變,
需要在動它之前記錄原本長度才刻以
以上.

＊＊＊更新分隔線更新分隔線＊＊＊

給一個array列出它所有subset的可能
是一個用講的很簡單, 用C寫卻半天寫不出來的東西(該不會只有我XD！)
弄半天才發現自己malloc的觀念還是亂七八糟的Orz
然後感覺calloc 很好用啊為什麼我以前都沒用呢（？）（問誰呢 XD）
看來之前幾題用到int ** columnSizes的大概都用錯了 QQ
哭哭～這幾天趕快來複習修正一下QQ

Subsets
/**
* 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** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {
int retSize = pow(2,numsSize);

*returnSize = retSize;
int** ret = malloc(sizeof(int*)* (retSize));
int curSize = 0,i,j;
for (i=0;i<retSize;i++)
{
ret[i] = malloc(sizeof(int)*(numsSize+1));
#if 1
*columnSizes = malloc(sizeof(int)*retSize);
memset(*columnSizes,0,sizeof(int)*retSize);
#else
*columnSizes = calloc(retSize, sizeof(int));
#endif
}
curSize++;
if (retSize>1)
ret[curSize++][(*columnSizes)[1]++] = nums[0];

for (i=1;i<numsSize;i++)
{
int nowSize = curSize;
for(j=0;j<nowSize;j++)
{
memcpy(ret[nowSize+j],ret[j],sizeof(int) * (*columnSizes)[j]);
(*columnSizes)[nowSize+j] = (*columnSizes)[j];
ret[curSize++][(*columnSizes)[nowSize+j]++] = nums[i];
}
}
return ret;
}

2018年3月6日星期二

[130] Surrounded Regions

我覺得我沒懂囧
真是神秘的題目
給一個只有X跟O的矩陣
如果O都有被X包圍住, 把O改成X
邊界的O屬於沒有被包住, 維持O.

大家都提到了BFS跟DFS
我只有掃過來掃過來還是各種漏掉囧
總之如果O沒有被包住, 都是從邊界來的 ;
所以重點就是從邊界開始, 如果有O , 先把它改成別的例如Y
並且檢查它的上下左右如果也有O, 一樣改成Y
如果那個O要被改成Y了, 新的Y的上下左右也要檢查,
有微遞迴的fu .

最後再把剩下的O全部改成X , 被改成Y的再全部改回O
就會是答案了..............
真是囉哩囉唆呀～唉
（重點是為什麼我都想不到也寫不對呢～？！QQ）

void check(char** board,int i,int j,int row,int col){
if (i<0 || j<0 || i+1 >row || j+1 > col)
return;
if(board[i][j]=='O')
{
board[i][j]='0';
check(board,i-1,j,row,col);
check(board,i,j-1,row,col);
check(board,i+1,j,row,col);
check(board,i,j+1,row,col);
}
}

void solve(char** board, int boardRowSize, int boardColSize) {
int i,j;
for(j=0;j<boardColSize; j++)
{
check(board,0,j,boardRowSize,boardColSize);
check(board,boardRowSize-1,j,boardRowSize,boardColSize);
}

for(i=0; i<boardRowSize;i++)
{
check(board,i,0,boardRowSize,boardColSize);
check(board,i,boardColSize-1,boardRowSize,boardColSize);
}
for(i=0; i<boardRowSize;i++)
for(j=0;j<boardColSize; j++)
{
if (board[i][j]=='O')
{
board[i][j] = 'X';
}
}
for(i=0; i<boardRowSize;i++)
for(j=0;j<boardColSize; j++)
{
if (board[i][j]=='0')
{
board[i][j] = 'O';
}
}
}

2018年3月5日星期一

[16] 3Sum Closest

和下面那題差不多 (比樓下)
只是把三個加起來等於零的部分,
改成給一個target值, 要找出相加最接近這個target 值的 3sum
把比對條件改一改就寫完了
算是寫一題賺兩題的概念 XD

3Sum Closest
int compare(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}

int threeSumClosest(int* nums, int numsSize, int target) {
if (numsSize < 2)
return NULL;
qsort(nums,numsSize,sizeof(int),compare);
int i,j,k;
int ret = target;
int closet = INT_MAX;
for(i=0;i<numsSize;i++)
{
if(i>0 && nums[i]==nums[i-1])
continue;
for(j=i+1,k=numsSize-1;j<k;)
{
int sum = nums[i]+nums[j]+nums[k] ;
int diff = abs(sum - target);
if (diff < closet)
{
closet = diff;
ret = sum;
}
if (sum == target)
return sum;
else if(sum < target)
{
while(j<k && nums[j]==nums[j+1])
j++;
j++;
}
else if (sum > target)
{
while(j<k && nums[k]==nums[k-1])
k--;
k--;
}
}
}
return ret;
}

[15] 3Sum

找加起來等於零
且不可重覆
非常醜我知道囧
但總之還是先放個初版Orz

3Sum
/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int compare(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
if (numsSize < 2)
return NULL;
qsort(nums,numsSize,sizeof(int),compare);
int i,j,k;

int **ret = malloc(sizeof(int *) * (numsSize*30));
*returnSize = 0;
for(i=0;i<numsSize;i++)
{
for(j=i+1,k=numsSize-1;j<k;)
{
int sum = nums[i]+nums[j]+nums[k] ;
if(sum < 0)
j++;
else if (sum > 0)
k--;
else
{
int index = *returnSize;
bool same = false;
for(int check = index-1; check >=0; check--)
{
if (nums[i]<ret[check][0])
break;
if (nums[i]==ret[check][0] && nums[j]==ret[check][1] && nums[k]==ret[check][2])
{
same = true;
break;
}
}
if (same)
{
j++;
k--;
continue;
}
ret[index] = malloc (sizeof(int)*3);
ret[index][0] = nums[i];
ret[index][1] = nums[j];
ret[index][2] = nums[k];
*returnSize += 1;
j++;
k--;
}
}
}
return ret;
}

但很奇怪後來看別人和我的笨版本差不多意思的卻快很多
為什麼呢 XD
不想研究了 XD
但總之重覆的可以跳過
不曉得為什麼一開始我把重覆的跳過一直不對
所以才弄了笨方法
唉感覺沒天份
以下是跳過重覆的版本
/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int compare(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
if (numsSize < 2)
return NULL;
qsort(nums,numsSize,sizeof(int),compare);
int i,j,k;

int **ret = malloc(sizeof(int *) * (numsSize*30));
*returnSize = 0;
for(i=0;i<numsSize;i++)
{
if(i>0 && nums[i]==nums[i-1])
continue;
for(j=i+1,k=numsSize-1;j<k;)
{
int sum = nums[i]+nums[j]+nums[k] ;
if(sum < 0)
{
while(j<k && nums[j]==nums[j+1])
j++;
j++;
}
else if (sum > 0)
{
while(j<k && nums[k]==nums[k-1])
k--;
k--;
}
else
{
int index = *returnSize;
ret[index] = malloc (sizeof(int)*3);
ret[index][0] = nums[i];
ret[index][1] = nums[j];
ret[index][2] = nums[k];
*returnSize += 1;
while(j<k && nums[j]==nums[j+1])
j++;
j++;
while(j<k && nums[k]==nums[k-1])
k--;
k--;
}
}
}
return ret;
}

結果修了一下比對的順序, "等於"先做,
然後就笨方法也可以得到很快的結果了 = =
覺得瞎XD
int compare(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
if (numsSize < 2)
return NULL;
qsort(nums,numsSize,sizeof(int),compare);
int i,j,k;

int **ret = malloc(sizeof(int *) * (numsSize*10));
*returnSize = 0;
for(i=0;i<numsSize;i++)
{
for(j=i+1,k=numsSize-1;j<k;)
{
int sum = nums[i]+nums[j]+nums[k] ;
if (sum==0)
{
int index = *returnSize;
bool same = false;

for(int check = index-1; check >=0; check--)
{
if (nums[i]>ret[check][0])
break;
else if (nums[i]==ret[check][0] && nums[j]==ret[check][1] && nums[k]==ret[check][2])
{
same = true;
break;
}
}
if (same)
{
j++;
k--;
continue;
}
ret[index] = malloc (sizeof(int)*3);
ret[index][0] = nums[i];
ret[index][1] = nums[j];
ret[index][2] = nums[k];
*returnSize += 1;
j++;
k--;
}
else if(sum < 0)
j++;
else if (sum > 0)
k--;
}
}
return ret;
}

2018年3月4日星期日

[146] LRU Cache (TBC)

神秘！！！
竟然又過了!!!
當然效能並不是太好
但似先這樣就好XD
我這個人最不強求了！！！
（問題是別人要求呀哭哭XD）

設計一個 LRU Cache
讓先被insert進去的會最先被取代
如果它有被touch過, 則時間要更新
另外key可以改掉value , 也就是key 1 可以先設個2 , 再 key 1 設個 3,
這時get key 1會得到3而不是2 (感覺很像廢話 XD）
TBC here~ 大概要弄個 first in first out的 queue
讓時間最前面的在head (或linked list）
降子拿掉的時候只要 O(1)
不過時間更新的時候需要重排(麻煩XD)
又似乎需要弄個hash again
（假裝沒看見題目上寫的: Could you do both operations in O(1) time complexity?)
反正今天先這樣XD 收工!

LRU Cache
typedef struct {
int key;
int value;
int time;
} LRUCache;
static unsigned int size = 0;
static unsigned long time = 0;
LRUCache* lRUCacheCreate(int capacity) {
size = capacity;
LRUCache* myCache = malloc (sizeof (LRUCache) * capacity);
for(int i=0;i<size;i++)
{
myCache[i].key = -1;
}
return myCache;
}

int lRUCacheGet(LRUCache* obj, int key) {
for(int i=0;i<size;i++)
{
if(obj[i].key == key)
{
obj[i].time = time++;
return obj[i].value;
}
}
return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
int time_min = INT_MAX;
int drop_index = -1;
for(int i=0;i<size;i++)
{
if(obj[i].key < 0 || obj[i].key == key)
{
obj[i].key = key;
obj[i].value = value;
obj[i].time = time++;
return;
}
else if (time_min > obj[i].time)
{
time_min = obj[i].time;
drop_index = i;
}
}

obj[drop_index].key = key;
obj[drop_index].value = value;
obj[drop_index].time = time++;

}

void lRUCacheFree(LRUCache* obj) {
free(obj);
}

/**
* Your LRUCache struct will be instantiated and called as such:
* struct LRUCache* obj = lRUCacheCreate(capacity);
* int param_1 = lRUCacheGet(obj, key);
* lRUCachePut(obj, key, value);
* lRUCacheFree(obj);
*/

[3] Longest Substring Without Repeating Characters

不敢相信！！！
竟然沒寫很久就Accepted了！！！
感人！！！
找一個字串裡面, 不重覆字元的最長子字串的長度
substring 不等於 subsequence
所以 pababcd 最長是 abcd長度 4
而不是 pabcd長度 5
因為 pabcd 只是subsequence而已, 並不是 substring

Longest Substring Without Repeating Characters

int max (int a, int b){

return (a>b)? a: b;

}

int lengthOfLongestSubstring(char* s) {

int len = strlen(s);

if (len<=1)

return len;

int ascii[128];

int i,tmp, ret=0, start=0, end=len;

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

ascii[i]= -1;

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

{

if (ascii[s[i]] >= 0)

{

end = i;

tmp = end - start;

if (tmp > ret)

ret = tmp;

start = max(ascii[s[i]] +1 , start);

}

ascii[s[i]] = i;

}

end = len-1;

tmp = end - start + 1;

if (tmp > ret)

ret = tmp;

return ret;

}

結果我2022年11月13號回來寫了一個什麼呢？ XD

int lengthOfLongestSubstring(char * s){
    int hash[128];
    int ret=0;
    for (int i=0;i<strlen(s);i++)
    {
        memset(hash,0, sizeof(int)*128);
        hash[s[i]]++;
        int count=1;
        for (int j=i+1; j<strlen(s);j++)
        {
            if (hash[s[j]] >0)
                break;
            else
            {
                hash[s[j]]++;
                count++;
            }
        }
        if (count > ret)
            ret = count;
    }
    return ret ;
}


[20240216]
沒想到2024年又回來寫了XD 漫漫長路啊～（痛哭）
2022年寫的算是暴力解（吧）這次寫的算是sliding window還是two pointers呢?!
雖然好像有長進但其實寫不出來 XD 考慮不周啊QQ
當右邊出現"已出現過的字元"，左邊的index 要一直移動到該字元只剩一個為止！
而不是只移動一個！冷靜想想也是QQ 我很笨～屋屋屋

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

int lengthOfLongestSubstring(char* s) {
    int *hash = calloc (128, sizeof(int));
    int len = strlen(s);
    if (len <=1)
        return len;

    int l=0,r=1;
    hash[s[0]-' ']++;
    int ret = 1;
    while (r<len)
    {
        hash[s[r]-' ']++;
        while (hash[s[r]-' ']>1)
        {
            hash[s[l]-' ']--;
            l++;
        }
        ret = max(ret,r-l+1);
//printf("ret: %d %d %d\n",l,r, ret);
        r++;
    }
    return ret;
}


[20250930]
雖然是過了....但是我退步了吧Orz 又寫出了垃圾啊屋屋屋

int lengthOfLongestSubstring(char* s) {
    int len = strlen(s);
    if (len <=1)
        return len;
    int l=0; 
    int r = l+1;
    int ret=0;
    int *hash = calloc (128, sizeof(int));
    hash[s[l]]++;
    while (r<len)
    {
//printf("%d %d\n", l,r);
        if (hash[s[r]]==0)
        {
            hash[s[r++]]++;
            if (r-l >ret)
                ret= (r-l);
        }
        else
        {
            while (s[l]!=s[r])
            {
                hash[s[l]]--;
                l++;
            }
            hash[s[l]]--;
            l++;
        }
    }
    return ret;
}

[84] Largest Rectangle in Histogram

找柱狀圖的最大面積
其實我的腦中一片空白囧
我連暴力法都不會寫了Orz
大意是整個array跑一遍, 每次找出它的第一個比它小的左邊, 跟第一個比它小的右邊,
將右減左減一當做寬,它自己當做高, 算出它可以擁有的最大面積,
每個item都算出自己的最大面積之後, 再回傳全部裡面的最大的.

看起來是可以用的, 不過不夠快：
Largest Rectangle in Histogram
int largestRectangleArea(int* heights, int heightsSize) {
if (heights==NULL || heightsSize<1)
return 0;
else if (heightsSize == 1)
return heights[0];
int right[heightsSize];
int left[heightsSize];
int i,j, k, max =INT_MIN;

for(i=0;i<heightsSize;i++)
{
left[i]=-1;
for(j=i;j>=0;j--)
{
if(heights[j]<heights[i])
{
left[i]=j;
break;
}
}

right[i]=heightsSize;
for(k=i;k<heightsSize;k++)
if(heights[k]<heights[i])
{
right[i]=k;
break;
}

int area = (right[i]-left[i]-1)*heights[i];
if (area > max)
max = area;
}

return max;
}

然後就是說用同樣的精神,
只是在找出左邊的第一個最小和右邊的第一個最小的這個部分,
用stack來完成.
每一個item會進去stack一次,
如果stack是空的, push進去;
如果目前的item 比stack的top 大, 也push進去;
如果目前的item 比stack的top 小, 那目前item的index可以當做右邊第一個最小,
stack的top 的value是我們的高, stack top的前一個的index 是左邊第一個做小,
如此可以算出stack top 可以有的最大面積.
算完把它pop掉, stack的top會更新, 用新的top來看目前的item 要被push進去,
還是要來算新的top的面積, 直到做完.

typedef struct _stack{
int value;
int index;
} stack;

int largestRectangleArea(int* heights, int heightsSize) {
if (heights==NULL || heightsSize<1)
return 0;
stack myStack[heightsSize];
int i, head=-1, max = INT_MIN;

for(i=0;i<heightsSize;i++)
{
if (head < 0 || heights[i] >= myStack[head].value)
{
myStack[++head].value = heights[i];
myStack[head].index = i;
}
else
{
while(head >= 0 && heights[i]<myStack[head].value)
{
int index = (head-1)>=0 ? (myStack[head-1].index) : -1;
int area = (i- index -1) * myStack[head--].value;
if (area > max)
max= area;
}
myStack[++head].value = heights[i];
myStack[head].index = i;

}
}
while(head >= 0)
{
int index = (head-1)>=0 ? (myStack[head-1].index) : -1;
int area = (i- index -1) * myStack[head--].value;
if (area > max)
max= area;
}
return max;
}
這一題可以拿來做[85] Maximal Rectangle (比樓下樓下樓下)
每行row 先往上算出它的 height (在這行row當做基底時, 每一個column往上看有幾個連續的 1 )
如此每行row 都可以套用Largest Rectangle in Histogram 找出它當下的最大面積
最後再回傳每行row最大面積的最大面積(跳針XD).

2018年3月3日星期六

[535] Encode and Decode TinyURL

寫的很卡的一題囧
總覺得不知道哪裡怪怪的
真危險吶我吶
HAHAHA（笑著流淚）
還以為要對長網址做一些encode
結果原來不是？！
那和0~9, a~z, A~Z的 62個字元有什麼關係呢 ?___?
我只要用26個也是可以的是吧?! 囧 (就測資來說是可以的)
這世界真複雜啊～～～～～～（流淚again）

Encode and Decode TinyURL
/** Encodes a URL to a shortened URL. */
char maps[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
static long db_id = 0;

struct _database{
char *s;
}database[1024];

char* encode(char* longUrl) {
long id = -1;
int i;
int len = strlen(longUrl);

if (longUrl == NULL || len <1)
return longUrl;

for(i=0;i<db_id;i++)
if(strcmp(database[i].s,longUrl)==0)
{
id = i;
break;
}

if(id < 0)
{
database[db_id].s = malloc(sizeof(char)*(len+1));
strncpy(database[db_id].s, longUrl, len);
database[db_id].s[len] = '\0';
id = db_id++;
}

char *shortS = malloc(sizeof(char)*7);
for(i=0;i<6;i++)
{
shortS[i] = maps[id%62];
id/=62;
}
shortS[i] = '\0';
return shortS;
}

/** Decodes a shortened URL to its original URL. */
char* decode(char* shortUrl) {
int len = strlen(shortUrl);
if (shortUrl == NULL || len < 1)
return shortUrl;
int id=0;
for(int i=len-1; i>=0; i--)
{
int now =0;
printf("now %c = %d\n", shortUrl[i], shortUrl[i]);

if (shortUrl[i] >= 'a')
now = 10 + shortUrl[i]-'a';
else if (shortUrl[i] >= 'A')
now = 10 + 26 + shortUrl[i]-'A';
else
now = shortUrl[i]-'0';
id = id*62 + now;
}
return database[id].s;
}

// Your functions will be called as such:
// char* s = encode(s);
// decode(s);

2018年3月1日星期四

[380] Insert Delete GetRandom O(1)

要死了寫了我兩天半！！！
雖然還包括了慌張的痛哭跟跑去象山沉澱心靈
但是C沒有內建的hash叫我寫這個真是太殘忍啦！！！
但是寫出來啦！！！
20ms 是網站上的最快啊啊啊啊啊啊！！！
雖然網站上根本只有不超過五個人submit過C吧我看！！！
原本最快的那個還偷吃步用別人寫好的hash library
這樣還叫做implement嗎可以的話我也要用lib啊啊啊啊啊啊啊
要是面試出這個我就直接說你fire我吧我是庸才（結果人家根本沒聘妳XD)
反正就是非常想飆髒話的現在啊啊啊啊啊啊啊
為什麼都沒有人寫C !!! 為什麼！！！！！！

題目是說要有一個資料結構是insert , remove和getRandom 隨意取一個值用O(1)完成
這對C來講有多難你知道嗎你知道嗎（逼近出題的人）
數字不可重覆, 細節不多說了我被這題搞的好累(痛哭)

Insert Delete GetRandom O(1)
#define HASH_SIZE 997
typedef struct HashNodes{
int value;
int pos;
struct HashNodes *next;
} HashNodes;

typedef struct {
int size;
int nums[10000];
HashNodes **hashTable;
} RandomizedSet;

/** Initialize your data structure here. */
RandomizedSet* randomizedSetCreate() {
RandomizedSet* myArray = malloc(sizeof (RandomizedSet));
myArray->size = 0;
// memset(myArray->nums , sizeof(int), 10000);
myArray->hashTable = malloc(sizeof(HashNodes*)*HASH_SIZE);
for (int i=0;i<HASH_SIZE; i++)
myArray->hashTable[i] = NULL;
return myArray;
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool randomizedSetInsert(RandomizedSet* obj, int val) {
int index = abs(val % HASH_SIZE);
HashNodes *ptr = obj->hashTable[index];
HashNodes *pre = NULL;
pre = ptr;

while(ptr != NULL)
{
if (ptr->value == val)
return false;

pre = ptr;
ptr = ptr->next;
}
obj->nums[obj->size] = val;
ptr = malloc(sizeof(HashNodes));
if (obj->hashTable[index]== NULL)
obj->hashTable[index] = ptr;

if (pre!=NULL)
pre->next = ptr;

ptr->pos = obj->size++;
ptr->value = val;
ptr->next = NULL;
return true;
}

void updateIndex(RandomizedSet* obj, int target, int newIndex)
{
int index = abs(target % HASH_SIZE);
HashNodes *ptr = obj->hashTable[index];
while(ptr != NULL)
{
if (ptr->value == target)
{
ptr->pos = newIndex;
break;
}
ptr = ptr->next;
}
return;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
bool randomizedSetRemove(RandomizedSet* obj, int val) {
int index = abs(val % HASH_SIZE);
HashNodes *ptr = obj->hashTable[index];
HashNodes *pre = NULL;
pre = ptr;

while(ptr != NULL)
{
if (ptr->value == val)
{
updateIndex(obj, obj->nums[obj->size-1], ptr->pos);
obj->nums[ptr->pos] = obj->nums[--obj->size];

if (pre != ptr)
pre->next = ptr->next;
else//head
obj->hashTable[index] = ptr->next;
free(ptr);
ptr = NULL;
return true;
}
pre = ptr;
ptr = ptr->next;
}
return false;
}

/** Get a random element from the set. */
int randomizedSetGetRandom(RandomizedSet* obj) {
if (obj->size < 1)
return NULL;
int random = (rand()%obj->size);
return obj->nums[random];
}

void randomizedSetFree(RandomizedSet* obj) {
#if 0
for(int i=0;i<obj->size;i++)
randomizedSetRemove(obj, obj->nums[i]);
free(obj->hashTable);
free(obj);
#endif

}

/**
* Your RandomizedSet struct will be instantiated and called as such:
* struct RandomizedSet* obj = randomizedSetCreate();
* bool param_1 = randomizedSetInsert(obj, val);
* bool param_2 = randomizedSetRemove(obj, val);
* int param_3 = randomizedSetGetRandom(obj);
* randomizedSetFree(obj);
*/

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

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

[20251101更新]

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

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

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

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

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

20240807 又更新好像也沒太多差別(thinking 圖)

bool hasCycle(struct ListNode *head) {
    struct ListNode *pfast , *pslow;
    pfast = head;
    pslow = head;
    while (pfast != NULL)
    {
        pslow = pslow->next;
        pfast = pfast->next;
        if (pfast == NULL)
            return false;
        pfast = pfast->next;
        if (pslow == pfast)
            return true;
    }
    return false;
}

原來可以把pfast->next 的判斷放到while 裡！

bool hasCycle(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)
            return true;
    }
    return false;
}

訂閱：意見 (Atom)

2018年4月16日 星期一

2018年4月14日 星期六

2018年3月9日 星期五

2018年3月7日 星期三

2018年3月6日 星期二

2018年3月5日 星期一

2018年3月4日 星期日

2018年3月3日 星期六

2018年3月1日 星期四

2018年2月26日 星期一

2018年2月25日 星期日

2018年2月24日 星期六

2018年2月23日 星期五