# leetcode_OJ WC94 解題心得 + おまけ

• Contest time: Jul 22, 2018

## PA. Leaf-similar Trees 樹水題

• 題意：從左到右葉子順序一樣的樹
• 思路：DFS一遍，放入葉子即可
• 分析：Time complexity O(N), Space complexity O(N), (auxiliary vector to store the leaf data)
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
#define pb push_back
class Solution
{
public:
vector<int> l1;
vector<int> l2;

bool leafSimilar(TreeNode* root1, TreeNode* root2)
{
get_leaf(root1, l1);
get_leaf(root2, l2);
return l1 == l2;
}
void get_leaf(TreeNode* root, vector<int>& lv)
{
if(root == NULL)
{
return;
}
else if(root->left == NULL && root->right == NULL)
{
lv.pb(root->val);
}

if(root->left)
{
get_leaf(root->left, lv);
}
if(root->right)
{
get_leaf(root->right, lv);
}
}

};


## PB. 874. Walking Robot Simulation 自己比較弱的模擬題

• 題意：模擬機器人走路，遇到障礙物座標則會停在他 前一個位置（例如障礙物的X=6，則遇到障礙物至多行走到X=5)

### 解法一

• 思路：用數學硬幹，確認四個方向看往哪走，例如朝向+y的方向(向北)，則以下條件成立代表撞上障礙物 posx == obstacles[j][0] && posy < obstacles[j][1] && posy + commands[i] >= obstacles[j][1] 表示X軸一致，往北走剛好撞上，再把Y軸設為障礙物前一個即可。
• 分析：Time complexity O(N + K)where N, K = # of commands and obstacles respectively. Space complexity O(1)
class Solution {
public:
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles)
{
int posx = 0, posy = 0, dir = 0, ans = 0; //0 north 1 east 2 south 3 west
int cango = 1;
for(int i = 0; i < commands.size(); i++)
{

if(commands[i] == -1)
{
dir = (dir + 1) % 4;
}
else if(commands[i] == -2)
{
if(dir == 0)
{
dir = 3;
}
else
{
dir--;
dir %= 4;
}
}
else
{
cango = 1;
for(int j = 0; j < obstacles.size(); j++)
{
switch (dir)
{
case 0:
{
if(posx == obstacles[j][0])
{
if(posy < obstacles[j][1] && posy + commands[i] >= obstacles[j][1])
{

posy = obstacles[j][1] - 1;
cango = 0;
}
}
break;
}
case 1:
{
if(posy == obstacles[j][1])
{
if(posx < obstacles[j][0] && posx + commands[i] >= obstacles[j][0])
{
posx = obstacles[j][0] - 1;

cango = 0;
}
}
break;
}
case 2:
{
if(posx == obstacles[j][0])
{
if(posy > obstacles[j][1] && posy - commands[i] <= obstacles[j][1])
{
posy = obstacles[j][1] + 1;

cango = 0;
}
}
break;
}
case 3:
{
if(posy == obstacles[j][1])
{
if(posx > obstacles[j][0] && posx - commands[i] <= obstacles[j][0])
{
posx = obstacles[j][0] + 1;

cango = 0;
}
}
break;
}
cout << endl;
default: break;
}
if(cango == 0)
{
break;
}
}
if(cango)
{
switch (dir)
{
case 0:
{

posy += commands[i];
break;
}
case 1:
{

posx += commands[i];
break;
}
case 2:
{

posy -= commands[i];
break;
}
case 3:
{

posx -= commands[i];
break;
}
default: break;
}
}
}
ans = max(ans, posx * posx + posy * posy);
}
return ans;
}
};


### 解法二

• 思路：用set存障礙物，模擬四方位，dx dy，北東南西，用dir變數搭配mod4來做轉向的動作，每次向指定的移動方向走一單位，並且檢查當前位置是否存在於障礙物的set中，便會自然而然走到障礙物前停下。
• 分析：Time complexity O(N + K)where N, K = # of commands and obstacles respectively. Space complexity O(K), use a set to store the positions of obstacles.
class Solution {
public:
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int robotSim(vector<int>& commands, vector<vector<int>>& obstacles)
{
int posx = 0, posy = 0, dir = 0, ans = 0, tmpx = 0, tmpy = 0; //0 north 1 east 2 south 3 west
int cango = 1;
set<pair<int, int>> obst_set;
for(auto &it : obstacles)
{
obst_set.insert(make_pair(it[0], it[1]));
}
for(int i = 0; i < commands.size(); i++)
{
if(commands[i] == -1)
{
dir = (dir + 1) % 4;
}
else if(commands[i] == -2)
{
if(dir == 0)
{
dir = 3;
}
else
{
dir--;
dir %= 4;
}
}
else
{
for(int j = 0; j < commands[i] ;j++) //move grid one by one
{
tmpx = posx + dx[dir];
tmpy = posy + dy[dir];
if(obst_set.find(make_pair(tmpx, tmpy)) != obst_set.end())
{
break;
}
else
{
posx = tmpx;
posy = tmpy;
}
}
}
ans = max(ans, posx * posx + posy * posy);
}
return ans;
}
};


## PC. 875. Koko Eating Bananas 二分搜

• 題意：猴子吃香蕉，一小時吃K個，除不盡也算一小時，有數堆香蕉，從第一堆開始食用，警衛會在H時間後回來，否則猴子會被抓包，問最小的K為何。
• TLE思路：

• 警衛可能很久才回來(H大，K勢必就可以很小)或相反，因此 決定從最大的時間（1e9）降下，以及從0上升，同時看這兩種食用速度是否逾時
• mxm從1e9降下(一定吃得完，時間逾時將flg設1代表找到能食用速度K的上界)/zr從零開始算，當不會逾時(因為從零開始算，不會逾時代表找到最少)，代表找到K的下界。
• 缺失分析：若食用速度趨於1e9的中間，則從頭尾走要相當久，即便一次走雙向，是故應該用二分搜尋，每次切半看時間上下界線中位數是否趕得及食用完畢。

• 分析：Time complexity O(N^2), Space complexity O(1)
• 以下為TLE的程式碼

class Solution
{
public:
int minEatingSpeed(vector<int>& pls, int hr)
{
int mxm = 1e9, minn = 0;
int zr = 1;
int tmp_time = 0;
int flg = 0, flg2 = 0;
while(1)
{
//cnt down from max
tmp_time = 0;
if(!flg)
{
for(auto &j : pls)
{
tmp_time += ceil((float) ((float)j / (float)mxm));
}
mxm--;
}
if(tmp_time > hr)
{
flg = 1;
}
//cnt up from min
tmp_time = 0;
if(!flg2)
{
for(auto &j : pls)
{
tmp_time += ceil((float) ((float)j / (float)zr));
}
zr++;
}
if(tmp_time < hr)
{
flg2 = 1;
}
if(flg && flg2)
{
break;
}
if(zr >= mxm)
{
break;
}
}
return zr > mxm ? mxm + 2 : zr + 2;
}
};


• 改進思路：二分搜尋

• 分析：Time complexity O(N log K) where N is the number of piles and K is the maximum size of a pile(binary search according to pile size to determine the eating speed and each round in testing we have to run through the whole pile to sum up the time = sum(pile[i] / current eating speed)) Space complexity O(1)
//binary search
class Solution
{
public:
int minEatingSpeed(vector<int>& pls, int hr)
{
int mxm = 1e9, minn = 1, mid = 0, ans = 1e9;
while(minn < mxm)
{
int tmp_time = 0; //count the time for current eating speed K
mid = (mxm + minn) / 2;
for(auto &j : pls)
{
tmp_time += ceil(((float)j / (float)mid));
}
if(tmp_time > hr) //cannot finish before guard back, should eat faster
{
minn = mid + 1;
}
else //can finish before guard back, may eat slower
{
mxm = mid;
ans = min(ans, mid);
}
}
return ans;
}
};


## PD.873. Length of Longest Fibonacci Subsequence LIS 的費波那契版本

• 題意：一樣給一個嚴格增的序列，問最長嚴格增的費波那契子序列
• TLE思路：

• 稍微優化的暴力解，首先將費氏數列三項定好。
• 接著看現在一(i) 二(j) 項目加總是否能大於等於j + 1(因為嚴格增，小於就沒機會從此點出發形成費氏數列，例如1 2 5 9 14 .... 便不可能從1為起點，因為1 + 2 < 5)
• 若大於 j + 1，則持續搜索j + 1之後的序列，並且 三個數字一組移動，列出第三項預期數值 thr_expected，符合arr[k]就持續往後走並且遞增(三項並不一定要毗鄰，因此thr_expected符合的時候，只要向後移動即可) 例如 1 2 3 4 5 6 8 10 14 從 1(fir) 2(sec) 3(thr_expected) ->(4被跳掉，因為 arr[3] != thr_expected) 2(fir) 3(sec) 5(thr_expected) -> 3(fir) 5(sec) 8(thr_expected)...
• 最後看長度是否大於二確認有費氏子序列，無則回傳0
• 缺失分析：O(N^3)太暴力，在查找 thr_expected 實際上可以用unordered_set加速(儲存整份array)，將平均線性的時間優化為常數(unordered_set worst = linear, average = constant)

• 分析：Time complexity O(N^3), Space complexity O(1)

class Solution
{
public:
int lenLongestFibSubseq(vector<int>& arr)
{
int fir = arr[0], sec = arr[1], thr_expected = 0, res = 0, cur_len;
for(int i = 0; i < arr.size() - 2; i++)
{

for(int j = i + 1; j < arr.size() - 1; j++)
{
if(arr[i] + arr[j] >= arr[j + 1])
{
fir = arr[i];
sec = arr[j];
thr_expected = arr[i] + arr[j];
cur_len = 2;
for(int k = j + 1; k < arr.size(); k++)
{
if(thr_expected == arr[k])
{
fir = sec;
sec = thr_expected;
thr_expected = fir + sec;
cur_len++;
res = max(cur_len, res);
}
}
}
}
}
return res == 2 ? 0 : res;
}
};


• 改進思路：將查詢的結構優化為unordered_map(實際上map也行，但我們不在意順序，沒差)

• 分析：Time complexity O(N^2), Space complexity O(N)
class Solution
{
public:
int lenLongestFibSubseq(vector<int>& arr)
{
int fir = arr[0], sec = arr[1], thr_expected = 0, res = 0, cur_len;
unordered_set<int> myset(arr.begin(), arr.end());
for(int i = 0; i < arr.size() - 2; i++)
{

for(int j = i + 1; j < arr.size() - 1; j++)
{
if(arr[i] + arr[j] >= arr[j + 1])
{
fir = arr[i];
sec = arr[j];
thr_expected = arr[i] + arr[j];
cur_len = 2;
while(myset.find(thr_expected) != myset.end()) //keep going the rest in the array
{
fir = sec;
sec = thr_expected;
thr_expected = fir + sec;
cur_len++;
res = max(cur_len, res);
}
}
}
}
return res == 2 ? 0 : res;
}
};


---

## おまけ 856. Score of Parentheses stack應用

• 題意：給一堆平衡好的括號， () = 1, (()) = 2, ()() = 2, (()(()) = 2 * ( 1 + 2 ) = 6
• 思路：用stack記錄左括號位置以及當前分數，遇到右括號，棧頂端是-1則代表，對稱形式的括號已經配對，將分數一分推入棧；反之若不是代表還沒有-1就一路pop裡面的元素直到-1又出現(代表此又刮好已經一路將內部的分數加總，回溯到他自己對應對稱的左括號)， 例如 (()(())) (可以將程式碼自己stdout棧的內容會比較好懂唷 :D)

• ( stack top [-1] back
• (( stack top [-1,-1] back
• (() stack top is -1, pop -1 out, push -1 in (source code line 17), now stack top [1,-1] back
• (()( stack top [-1,1,-1] back
• (()(( stack top [-1,-1,1,-1] back
• (()(() pop -1 out, push -1 in stack top [1,-1,1,-1] back
• (()(()) stack top is not -1, keep popping until -1 and x2 the pushed score in, pop -1 out, now stack top [2,1,-1] back
• (()(())) stack top is not -1, keep popping until -1 and x2 the pushed score in, pop -1 out now stack top [6] back
• 最後的while loop 將沒有加總完成的分數全數加總
• 分析：Space complexity O(N), Time complexity O(N)

class Solution
{
public:
int scoreOfParentheses(string str)
{
stack<int> stk;
unsigned int total_score = 0;
for(int i = 0; i < str.size(); i++)
{
int acculmulate_score = 0;
if(str[i] == '(')
{
stk.push(-1);
}
else
{
if(stk.top() == -1)
{
stk.pop();
stk.push(1);
}
else //keep adding until maching the symmetric part
{
while(stk.top() != -1)
{
acculmulate_score += stk.top();
stk.pop();
}
stk.pop(); //pop the symmetrically matched left parenthesis
acculmulate_score *= 2;
stk.push(acculmulate_score);
}
}
}
//accumulate the rest if not finished
while(stk.size())
{
total_score += stk.top();
stk.pop();
}