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

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

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

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

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年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日 星期五

2018年2月22日 星期四

2018年2月21日 星期三