Qmonster吃喝玩樂大事記

2019年6月29日星期六

聽說有去北海道（一）

基於一個住了貴飯店萬萬不能讓它憑空消失在記憶的橫流裡（？）的這個理由

北海道也要來給它寫一寫.

這樣才能拿出來跟老李說「你看你看你看~~~」

繼續閱讀 »

2019年6月22日星期六

一個日月潭

好久沒有寫文章了
難得去了一下日月潭
終於突破礁溪以南我感動 ToT
為表紀念就來寫一下遊記(x)雜記(o)

繼續閱讀 »

2018年4月16日星期一

吸加加的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;
}
};

[20260710] 更新

奇怪別人寫就是比較漂亮～—～

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

void reverse(char *a, char *b){
    char tmp = *a;
    *a=*b;
    *b=tmp;
}

char* addBinary(char* a, char* b) {
    int l1 = strlen(a);
    int l2 = strlen(b);
    int longer= max(l1, l2);
    int carry = 0;
    char *ret = calloc(longer+2, sizeof(char));//for additional carry & ending so it's longer +1 +1
    int idx = 0; 
    while (longer>0){
        int v1=0; 
        int v2=0;
        if (l1-1>=0)
            v1= a[--l1]-'0';
        if (l2-1>=0)
            v2= b[--l2]-'0';
//printf("%d + %d\n", v1, v2);
        int sum = carry+v1+v2;
        carry = (sum>1)? 1: 0;
        ret[idx++]= ((sum& 0x1)==1)? '1' :'0';
        longer--;
    }
    if (carry>0)
        ret[idx++]='1';
//printf("idx %d  carry %d\n", idx,carry);
    for (int i=0; i<idx/2;i++)
        reverse(&ret[i], &ret[idx-1-i]);
    return ret;
}

看來while 可以改成 l1>0 || l2>0 || carry 結果又改出無窮回圈囧

#define max(a,b) (a>b)?(a):(b)
void reverse(char *a, char *b){
    char tmp = *a;
    *a=*b;
    *b=tmp;
}

char* addBinary(char* a, char* b) {
    int l1 = strlen(a);
    int l2 = strlen(b);
    int longer= max(l1, l2);
    int carry = 0;
    char *ret = calloc(longer+2, sizeof(char));//for additional carry & ending so it's longer +1 +1
    int idx = 0; 
    while (l1>0 || l2>0 || carry){
        int v1=0; 
        int v2=0;
        if (l1-1>=0)
            v1= a[--l1]-'0';
        if (l2-1>=0)
            v2= b[--l2]-'0';
        int sum = carry+v1+v2;
        carry = (sum>1)? 1: 0;
        ret[idx++]= ((sum& 0x1)==1)? '1' :'0';
    }
    for (int i=0; i<idx/2;i++)
        reverse(&ret[i], &ret[idx-1-i]);
    return ret;
}

[20260709] 更新

有一點懶得修！這個算是復健題XD 輸入小的時候應該是對的～

但長度一長就一定是錯的要重寫～就先貼下吧. 沒想到當年我竟然是用C++寫的XD

int str2int(char* s1, int len){
    int ret=0;
    for (int i=0; i<len;i++)
    {
        ret = (ret<<1) + (s1[i] & 0x1);
    }
//    printf("ret %d\n",ret);
    return ret;
}
#define STRLEN INT_MAX
void swap(char *a, char *b){
    char tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}

char* int2str(int val){
    char *ret = calloc (STRLEN,sizeof(char));
    int idx = 0;
//printf("int2str val %d\n",val);
    while (val>0)
    {
        if (val&0x1 == 1)
            ret[idx++]='1'; 
        else
            ret[idx++]='0'; 
        val= val>>1;
//printf("int2str idx %d, [%c]\n",idx, ret[idx-1]);
    }
//printf("int2str idx(len) %d\n",idx);
    char *reverse= calloc(idx+1, sizeof(char));
//    char *reverse = (char*) realloc(ret, idx*sizeof(char));
    for (int i=0; i<idx; i++)
        reverse[idx-i-1]= ret[i];
#if 0
printf("int2str idx %d, strlen %d\n",idx, strlen(reverse));
    for (int i=0; i<idx/2; i++)
    {
        swap(&reverse[i], &reverse[idx-i]);
    }    
#endif
    if (idx==0)
        return "0";
    return reverse;
}

char* addBinary(char* a, char* b) {
    int l1 = strlen(a);
    int l2 = strlen(b);
printf("l1 %d l2 %d\n",l1,l2);
    int sum = str2int(a,l1) + str2int(b,l2);
//printf("sum %d\n",sum);

    return int2str(sum);
//    return NULL;
}

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);
*/

訂閱：文章 (Atom)

2019年6月29日 星期六

2019年6月22日 星期六

2018年4月16日 星期一

2018年4月14日 星期六

2018年3月9日 星期五

2018年3月7日 星期三

2018年3月6日 星期二

2018年3月5日 星期一

2018年3月4日 星期日