難得寫的還算精準
一回神發現題目還有一行:
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月9日 星期五
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;
}
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';
}
}
}
真是神秘的題目
給一個只有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;
}
只是把三個加起來等於零的部分,
改成給一個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;
}
且不可重覆
非常醜我知道 囧
但總之還是先放個初版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);
*/
竟然又過了!!!
當然效能並不是太好
但似先這樣就好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
竟然沒寫很久就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).
其實我的腦中一片空白 囧
我連暴力法都不會寫了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的面積, 直到做完.
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);
總覺得不知道哪裡怪怪的
真危險吶我吶
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);
*/
雖然還包括了慌張的痛哭跟跑去象山沉澱心靈
但是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);
*/
訂閱：
文章 (Atom)