# 學習程式設計演算法與資料結構並於leetcode實作練習
# 目錄：
1. 摘要
2. 研究目標和規劃
3. 研究成果和能力成長
4. 執行過程中的困難及反思
5. 心得
# 摘要：
於leetcode（解題網站）上實作：排序與二分搜、堆疊、佇列、串列鏈結、貪婪等演算法和資料結構，共解出20題（3題hard，9題medium，8題easy），並於計畫之外延伸學習樹演算法（線段樹及最小生成樹、廣度優先搜尋(BFS)、廣度優先搜尋(DFS))，亦於計畫學習之演算法加深學習（如於學習串列鏈結時查找延伸學習資料資料，習得Two Pointer、Floyd’s Algorithm、Sliding Window等延伸演算法並實作），過程中加深資料檢索及自學能力，而程式設計能力和系統思考與解決問題能力及規劃執行、創新應變能力皆有顯著提升，也在透過網路自學的過程中更進一步增益科技資訊及媒體素養，更是確立自己對於程式設計領域的好奇心及熱情。過程中也習得檢閱報錯的能力（如map越界存取、存取到空指標），也發現自己解題時花費大量時間在除錯原因在於解題規劃的不足，在程式撰寫細節上也更加提升，如：下有意義的變數名、程式是否足夠精簡、有無不必要的程式碼。
leetcode介紹：
leetcode是一間2015年成立於美國舊金山，為軟體工程師求職者提供面試題庫的公司，於leetcode網站中的所有題目皆來自業界公司的面試考古題，包括Google、Apple、Microsoft、 facebook等公司。調查顯示不論職位，面試時出現的題目至少三分之一是位於leetcode上的考古題。而在網站上可以看到自己撰寫的程式的執行效率、記憶體用量排名，使使用者在有限的條件下寫出程式碼。
# 研究目標和規劃：
第一週：排序與二分搜及其實作
第二周：堆疊（stack）與佇列（queue）及其延伸演算法(前、中、後序表示式)、樹(tree)演算法。
第三週：實作練習上周習得（queue、stack、前、中、後序表達式之轉換）內容。
第四週：串列鏈結（Linked list)
第五週：貪婪（greedy）
# 研究成果和能力成長：
#### 成果總覽（leetcode題數）
#### 排序與二分搜及其實作
* 題號：374. Guess Number Higher or Lower(EASY)
```cpp=
class Solution {
public:
int guessNumber(int n)
{
long long int left=1;
long long int right=n;
long long int helf=(left+right)/2;
long long int result;
while(right>=left)
{
result=guess(helf);
if(result==0) break;
else if(result==-1) right=(helf-1);
else left=helf+1;
helf=(left+right)/2;
}
return int(helf);
}
};
```
* 題號：367. Valid Perfect Square(EASY)
```cpp=
class Solution
{
public:
bool isPerfectSquare(int num)
{
bool result =false;
//helf*helf compair with num
long long int left=1;
long long int right =num;
long long int helf=(right+left)/2;
while(right>=left)
{
if(helf*helf==num)
{
result=true;
break;
}
else if(helf*helf>num)right=helf-1;
else left=helf+1;
helf=(left+right)/2;
}
return result;
}
};
```
* 題號：852. Peak Index in a Mountain Array(MEDIUM)
```cpp=
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr)
{
int left=0;
int right=arr.size();
long long int helf=(long long int)((left+right)/2);
int index=-1;
while(right>=left)
{
if(arr[helf+1]<arr[helf]&&arr[helf]>arr[helf-1])
{
index=helf;
break;
}
else if(arr[helf+1]>arr[helf]) left=helf+1;
else if(arr[helf+1]<arr[helf]) right=helf-1;
helf=(long long int)((left+right)/2);
}
return index;
}
};
```
* 題號：540. Single Element in a Sorted Array(MEDIUM)
```cpp=
class Solution {
public:
int singleNonDuplicate(vector<int>& nums)
{
int left =0;
int right =nums.size()-1;
long long int helf=(long long int)((left+right)/2);
bool even=false;
while(left<right)
{
if(helf%2==0) even=true;
else even=false;
if(helf==nums.size()-1) return nums[helf];
if(helf==0)return nums[helf];
if(nums[helf]!=nums[helf+1]&&nums[helf-1]!=nums[helf]) break;
if(even)
{
if(helf<nums.size()-1&&nums[helf+1]==nums[helf]) left=helf+1;
else
{
if(helf>0)right=helf-1;
else return nums[helf];
}
}
else
{
if(helf>0&&nums[helf-1]==nums[helf]) left=helf+1;
else
{
if(helf>0)right=helf-1;
else return nums[helf];
}
}
helf=(long long int)((left+right)/2);
}
if(right==left) return nums[right];
return nums[helf];
}
};
```
* 題號：1095. Find in Mountain Array(HARD)
```cpp=
class Solution
{
public:
int findInMountainArray(int target, MountainArray &mountainArr)
{
int left=0;
int right=mountainArr.length()-1;
long long int helf=(long long int)((left+right)/2);
int top=0;
int toplocation=0;
while(right>left)
{
int a,c;
int b=mountainArr.get(helf);
if(helf<mountainArr.length()-1)a=mountainArr.get(helf+1);
else a=b;
if(helf>1)c=mountainArr.get(helf-1);
else c=b;
if(a<b&&c<b)
{
top=b;
toplocation=helf;
break;
}
else if(a<b) right=helf-1;
else if(a>b) left=helf+1;
helf=(long long int)((left+right)/2);
}
if(right==left)
{
top=mountainArr.get(helf);
toplocation=helf;
}
int left1=0;
int right1=toplocation;
int helf1=(long long int)((left1+right1)/2);
bool find1 =false;
int index=-1;
while(right1>left1)
{
int d=mountainArr.get(helf1);
if(d==target)
{
find1=true;
index=helf1;
break;
}
if(d>target&&helf1>0) right1=helf1-1;
else if(d<target&&helf1<mountainArr.length()-1) left1=helf1+1;
else if(helf1==0||helf1==mountainArr.length()-1)
{
break;
}
helf1=(long long int)((left1+right1)/2);
}
if(left1==right1)
{
if(mountainArr.get(helf1)==target)
{
helf1=(long long int)((left1+right1)/2);
find1=true;
index=helf1;
}
}
cout << find1<< " "<< index << "\n";
if(!find1)
{
int left2=toplocation;
int right2=mountainArr.length()-1;
int helf2=(long long int)((left2+right2)/2);
while(right2>left2)
{
int e=mountainArr.get(helf2);
if(e==target)
{
index=helf2;
break;
}
if(e<target&&helf2>0) right2=helf2-1;
else if(e>target&&helf2<mountainArr.length()-1) left2=helf2+1;
else if(helf2==0||helf2==mountainArr.length()-1)
{
break;
}
helf2=(long long int)((left2+right2)/2);
}
if(right2==left2)
{
helf2=(long long int)((left2+right2)/2);
if(mountainArr.get(helf2)==target)index=helf2;
}
}
cout << index;
return index;
}
};
```
#### 堆疊（stack）及其延伸演算法(前、中、後序表示式)、佇列（queue）和樹(tree)演算法
* 題號：682. Baseball Game(EASY)
```cpp=
class Solution
{
public:
int calPoints(vector<string>& operations)
{
vector<int> data;
for(int i=0;i<operations.size();i++)
{
int size=data.size()-1;
if(operations[i]=="+")data.push_back(data[size]+data[size-1]);
else if(operations[i]=="*")data.push_back(data[size]*data[size-1]);
else if(operations[i]=="C")data.pop_back();
else if(operations[i]=="D")data.push_back(data[size]*2);
else
{
data.push_back(stoi(operations[i]));
}
}
int result=0;
for(int i=0;i<data.size();i++) result+=data[i];
return result;
}
};
```
* 題號：234. Palindrome Linked List(EASY)
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head)
{
if(head->next==nullptr) return true;
vector<int> data;
while(head!=nullptr)
{
data.push_back(head->val);
head=head->next;
}
bool result=false;
int j=data.size()-1;
int i=0;
for(;i<data.size()/2&&j>data.size()/2;i++,j--)
{
if(data[i]==data[j])
{
cout << "kkk\n";
result=true;
continue;
}
else
{
cout << "iii\n";
result=false;
break;
}
}
if(data.size()%2==0)
{
if(data[i]==data[j])
{
cout << "ppp\n";
result=true;
}
else result=false;
}
return result;
}
};
```
* 題號：155. Min Stack(MEDIUM)
```cpp=
class MinStack
{
private:
int length=0;
Linklist *linklist=nullptr;
public:
MinStack()
{
}
void push(int val)
{
if(this->linklist==nullptr)
{
this->length+=1;
this->linklist=new Linklist(val);
this->linklist->minn=val;
}
else
{
this->length+=1;
Linklist *now= this->linklist;
this->linklist=nullptr;
this->linklist=new Linklist(val,now);
if(this->linklist->val<this->linklist->next->minn)
{
this->linklist->minn=this->linklist->val;
}
else
{
this->linklist->minn=this->linklist->next->minn;
}
}
}
void pop()
{
if(this->linklist==nullptr)
{
}
else
{
this->length-=1;
Linklist *now=this->linklist->next;
this->linklist->next=nullptr;
delete this->linklist;
this->linklist=now;
}
}
int top()
{
return this->linklist->val;
}
int getMin()
{
return this->linklist->minn;
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
```
* 題號：150. Evaluate Reverse Polish Notation(MEDIUM)
```cpp=
class Solution
{
public:
int evalRPN(vector<string>& tokens)
{
vector<int> data;
for(int i=0;i<tokens.size();i++)
{
int len=data.size()-1;
if(tokens[i]=="+")
{
int end=data[len];
data.pop_back();
int end_1=data[len-1];
data.pop_back();
data.push_back(end+end_1);
}
else if(tokens[i]=="-")
{
int end=data[len];
data.pop_back();
int end_1=data[len-1];
data.pop_back();
data.push_back(end_1-end);
}
else if(tokens[i]=="*")
{
int end=data[len];
data.pop_back();
int end_1=data[len-1];
data.pop_back();
data.push_back(end*end_1);
}
else if(tokens[i]=="/")
{
int end=data[len];
data.pop_back();
int end_1=data[len-1];
data.pop_back();
data.push_back(end_1/end);
}
else data.push_back(stoi(tokens[i]));
}
return data[0];
}
};
```
* 題號：227. Basic Calculator II(MEDIUM)
```cpp=
class Solution
{
public:
int calculate(string s)
{
cout << s << "\n";
map<char,int> bouns=
{
{'+',1},{'-',1},{'*',2},{'/',2},{'(',0}
};
stack<int> num;
stack<char> chara;
for(int i=0;i<s.size();i++)
{
if(s[i]==' ')
{
continue;
}
if(s[i]>=48&&s[i]<=58)
{
int k=i;
int total=0;
while(true)
{
total+=(static_cast<int>(s[k])-48);
if(s[k+1]>=48&&s[k+1]<=58)
{
total*=10;
k++;
i++;
}
else
{
num.push(total);
break;
}
}
}
else
{
if(chara.size()==0||s[i]=='(') chara.push(s[i]);
else if(s[i]==')')
{
while(true)
{
if(chara.top()=='(')
{
chara.pop();
break;
}
else
{
char operation=chara.top();
chara.pop();
int a=num.top();
num.pop();
int b=num.top();
num.pop();
int result=0;
if(operation=='+')result=b+a;
else if(operation=='-')result=b-a;
else if(operation=='*')result=b*a;
else if(operation=='/')result=b/a;
num.push(result);
}
}
}
else
{
while(true)
{
if(chara.size()==0||bouns[s[i]]>bouns[chara.top()])
{
chara.push(s[i]);
break;
}
else
{
char operation=chara.top();
chara.pop();
int a=num.top();
num.pop();
int b=num.top();
num.pop();
int result=0;
if(operation=='+')result=b+a;
else if(operation=='-')result=b-a;
else if(operation=='*')result=b*a;
else if(operation=='/')result=b/a;
num.push(result);
}
}
}
}
}
while(chara.size()>0)
{
char operation=chara.top();
chara.pop();
int a=num.top();
num.pop();
int b=num.top();
num.pop();
int result=0;
if(operation=='+')result=b+a;
else if(operation=='-')result=b-a;
else if(operation=='*')result=b*a;
else if(operation=='/')result=b/a;
num.push(result);
}
return num.top();
}
};
```
* 題號：101. Symmetric Tree(EASY)
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
/*void search(vector<int> &result,TreeNode *root)
{
TreeNode *pole=root;
while(pole->left==nullptr&&pole->right==nullptr)
{
if(pole==nullptr)
{
result.pb(-99999);
return;
}
else
{
result.pb(pole->val);
}
}
}*/
class Solution
{
public:
bool isSymmetric(TreeNode* root)
{
if(root->left==nullptr)
{
if(root->right==nullptr) return true;
else return false;
}
else if(root->right==nullptr) return false;
queue<TreeNode*> left1,right1;
left1.push(root->left);
right1.push(root->right);
TreeNode *temp=nullptr;
TreeNode *temp2=nullptr;
while(!left1.empty())
{
if(right1.empty()) return false;
temp=left1.front();
temp2=right1.front();
//cout << temp->val << "\n";
//cout << temp2->val << "\n";
if(temp==nullptr)
{
if(temp2==nullptr)
{
left1.pop();
right1.pop();
continue;
}
else return false;
}
else if(temp2==nullptr)return false;
if(temp->val!=temp2->val) return false;
left1.pop();
right1.pop();
left1.push(temp->left);
left1.push(temp->right);
right1.push(temp2->right);
right1.push(temp2->left);
}
if(!right1.empty()) return false;
else return true;
}
};
```
* 題號：100. Same Tree(EASY)
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr)
{
if(q!=nullptr) return false;
else if(q==nullptr) return true;
}
if(p==nullptr)
{
if(q!=nullptr) return false;
else if(q==nullptr) return true;
}
queue<TreeNode*> p1,q1;
p1.push(p);
q1.push(q);
TreeNode* temp=nullptr;
TreeNode* temp2=nullptr;
while(!p1.empty())
{
if(q1.empty()) return false;
temp=p1.front();
temp2=q1.front();
if(temp==nullptr)
{
if(temp2!=nullptr) return false;
}
if(temp2==nullptr)
{
if(temp!=nullptr) return false;
}
else if(temp->val!=temp2->val) return false;
p1.pop();
q1.pop();
if(temp->left!=nullptr) p1.push(temp->left);
else if(temp2->left!=nullptr) return false;
if(temp->right!=nullptr) p1.push(temp->right);
else if(temp2->right!=nullptr) return false;
if(temp2->left!=nullptr) q1.push(temp2->left);
if(temp2->right!=nullptr) q1.push(temp2->right);
}
if(!q1.empty()) return false;
return true;
}
};
```
* 題號：404. Sum of Left Leaves(EASY)
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
int sum=0;
void find(TreeNode* &parent,TreeNode* &child,int &a)
{
child=parent->left;
if(child==nullptr)
{
if(a>0||parent->right!=nullptr)
{
child=parent->right;
if(child==nullptr)return ;
else if(child->left==nullptr&&child->right==nullptr) return;
a=0;
}
if(child==nullptr)
{
a=0;
return;
}
}
if(child->left==nullptr&&child->right==nullptr)
{
sum+=child->val;
a=0;
}
if(parent->left!=nullptr)
{
a++;
find(parent->left,child,a);
}
if(parent->right!=nullptr)
{
a=0;
find(parent->right,child,a);
}
}
class Solution
{
public:
int sumOfLeftLeaves(TreeNode* root)
{
sum=0;
int a=0;
if(root==nullptr) return 0;
if(root->right==nullptr&&root->left==nullptr) return 0;
TreeNode* parent=root;
TreeNode* child=parent;
find(parent,child,a);
return sum;
}
};
```
* 題號：102. Binary Tree Level Order Traversal(MEDIUM)
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#define pb push_back
#define pp pop_back
class Solution
{
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
vector<vector<int>> result;
vector<int> level;
if(root==nullptr) return result;
level.pb(root->val);
result.pb(level);
level.clear();
if(root->left==nullptr&&root->right==nullptr)return result;
TreeNode* temp=root->left;
vector<TreeNode*> tree;
tree.pb(root);
while(!tree.empty())
{
temp=tree.front();
if(temp!=root&&temp->val==level[0])
{
if(tree.size()<2||tree[1]==nullptr||tree[1]->val==level[1])
{
if(!level.empty())result.pb(level);
level.clear();
}
}
tree.erase(tree.begin());
if(temp->left!=nullptr)
{
tree.pb(temp->left);
level.pb(temp->left->val);
}
if(temp->right!=nullptr)
{
tree.pb(temp->right);
level.pb(temp->right->val);
}
}
return result;
}
};
```
#### 串列鏈結（Linked list)
* 題號：234. Palindrome Linked List(EASY)
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head)
{
if(head->next==nullptr) return true;
vector<int> data;
while(head!=nullptr)
{
data.push_back(head->val);
head=head->next;
}
bool result=false;
int j=data.size()-1;
int i=0;
for(;i<data.size()/2&&j>data.size()/2;i++,j--)
{
if(data[i]==data[j])
{
cout << "kkk\n";
result=true;
continue;
}
else
{
cout << "iii\n";
result=false;
break;
}
}
if(data.size()%2==0)
{
if(data[i]==data[j])
{
cout << "ppp\n";
result=true;
}
else result=false;
}
return result;
}
};
```
* 題號：21. Merge Two Sorted Lists(EASY)
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
void put1(ListNode* &list1,vector<int> &data)
{
data.push_back(list1->val);
if(list1->next==nullptr) return;
put1(list1->next,data);
}
void put2(ListNode* &list2,vector<int> &data)
{
data.push_back(list2->val);
if(list2->next==nullptr) return;
put2(list2->next,data);
}
void push(ListNode* &list3,vector<int> &data,int i)
{
if(data.size()==0) return;
if(data.size()==i) return;
list3->next=new ListNode(data[i]);
push(list3->next,data,i+1);
}
class Solution
{
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
if(list1==nullptr)
{
if(list2==nullptr) return list1;
else return list2;
}
else if(list2==nullptr)
{
return list1;
}
vector<int> data;
put1(list1,data);
put2(list2,data);
sort(data.begin(),data.end());
for(int x : data) cout << x << ' ';
ListNode* list3=new ListNode(data[0]);
push(list3,data,1);
return list3; }
};
```
* 題號：19. Remove Nth Node From End of List(MEDIUM)
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
void length(ListNode* head, int &L)
{
L++;
if(head->next==nullptr) return;
length(head->next,L);
}
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
if(head->next==nullptr)
{
head=nullptr;
return head;
}
else if(head->next->next==nullptr)
{
if(n==1)
{
ListNode *first1=head;
first1->next=nullptr;
return head;
}
}
int L=0;
length(head,L);
if(n==L)
{
ListNode *first2=head;
ListNode *back2=head->next;
first2=nullptr;
head=back2;
return head;
}
ListNode *front=nullptr;
ListNode *back=nullptr;
ListNode *now=head;
L-=n;
L-=1;
while(L>0)
{
now=now->next;
L--;
}
front=now;
back=now->next->next;
front->next->next=nullptr;
delete front->next;
front->next=back;
return head;
}
};
```
* 題號：142. Linked List Cycle II(MEDIUM)
* Floyd's Algorithm
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head)
{
int pos=-1;
if(head==nullptr||head->next==nullptr) return nullptr;
ListNode* fast=head;
ListNode* slow=head;
while(fast!=nullptr&&fast->next!=nullptr)
{
fast=fast->next;
if(fast->next!=nullptr) fast=fast->next;
else return nullptr;
slow=slow->next;
if(fast==slow)
{
fast=head;
pos++;
while(fast!=slow)
{
pos++;
fast=fast->next;
slow=slow->next;
cout << pos;
}
return fast;
break;
}
}
return nullptr;
cout << fast->val << "\n";
cout << slow->val<< "\n";
}
};
```
* 題號：23. Merge k Sorted Lists(HARD)
```cpp=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<int> data;
int L=lists.size();
if(L==0) return nullptr;
else if(L==1) return lists[0];
//cout << L << ' ';
ListNode *now=lists[0];
int i=0;
while(L--)
{
while(now!=nullptr)
{
data.push_back(now->val);
if(now->next!=nullptr)now=now->next;
else break;
}
i++;
now=lists[i];
}
for(int x : data) cout << x << ' ';
if(data.size()==0) return lists[0];
sort(data.begin(),data.end());
reverse(data.begin(),data.end());
ListNode *result=new ListNode(data.back());
ListNode *lo=result;
data.pop_back();
while(data.size()>0)
{
int k=data.back();
data.pop_back();
lo->next=new ListNode(k);
lo=lo->next;
}
return result ;
}
};
```
#### 貪婪（greedy）
* 題號：1606. Find Servers That Handled Most Number of Requests(HARD)
```cpp=
class CPU
{
public:
int id = -1;
int completeTimes = 0;
CPU(int id) {this->id = id;}
void reset() {this->completeTimes += 1;}
};
class Solution
{
private:
int maxTimes = 0;
vector<CPU> CPUs;
set<int> executeDoneTime;
set<int> idle;
unordered_map<int, queue<int>> busy; // executeDoneTime : cpu id
int MAX_EXECUTE_ROUND = 2100000000;
public:
vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load)
{
int nowRound = arrival.at(0);
for(int x=0; k>x; x++)
{
CPU temp(x);
this->idle.insert(x);
this->CPUs.push_back(temp);
}
for(int process=0, length=load.size(); length > process; process++)
{
if(nowRound != arrival.at(process))
{
nowRound = arrival.at(process);
this->checkoutCPU(nowRound);
}
if(this->idle.empty()) continue;
set<int>::iterator idleCPU = this->idle.lower_bound(process % k);
if(idleCPU == this->idle.end()) idleCPU = this->idle.begin();
int executedTime = arrival.at(process) + load.at(process);
this->executeDoneTime.insert(executedTime);
this->busy[executedTime].push(*idleCPU);
this->idle.erase(*idleCPU);
}
nowRound = this->MAX_EXECUTE_ROUND;
this->checkoutCPU(nowRound);
vector<int> result;
for (vector<CPU>::iterator cpu = this->CPUs.begin(); cpu != this->CPUs.end(); ++cpu)
if((*cpu).completeTimes == this->maxTimes)
result.push_back((*cpu).id);
return result;
}
void checkoutCPU(int round)
{
if(this->busy.empty()) return;
int executeTime = -1;
while(!this->executeDoneTime.empty() && round >= (executeTime = *this->executeDoneTime.begin()))
{
queue<int> *CPUrange = &this->busy[executeTime];
while(!CPUrange->empty())
{
int now = CPUrange->front();
CPUrange->pop();
this->idle.insert(now);
this->CPUs.at(now).reset();
if(this->CPUs.at(now).completeTimes > this->maxTimes) this->maxTimes = this->CPUs.at(now).completeTimes;
}
this->busy.erase(executeTime);
this->executeDoneTime.erase(executeTime);
}
}
};
```
# 執行過程中的困難及反思：
* 實作除錯花大量時間
* 科技資訊與程式設計能力
* 系統思考與解決問題
從理解基本概念到靈活運用，再去進行延伸學習，過程中的每一件事並不畫上等號，實作練習耗費的時間遠超過概念的理解和學習，如何除錯(debug)也是在實作中屢次遇到的難題，例如在寫指標相關的題目，有時出現存取錯誤或定位不正確的問題，解題過程中也經常遭遇只有部分測資通過、越界存取或遞迴卡死等等情形，有時打好程式碼只需30分鐘，可除錯卻生生花了我一個小時甚至更多，面對這些問題，在五週的題目練習、進階演算法的學習後，再度解題時發現這些原先令我十分困擾、無從下手的錯誤也因為經驗增加逐漸有跡可循，得以在報錯的第一時間就逐步縮小範圍、排除錯誤，且在開始打程式碼前針對題目的規劃能力更強，過去打到哪裏想到哪裏的解題壞習慣（發現正因此壞習慣導致自己經常在除錯花大量時間），在全面規劃完題目後再開始打程式碼，改正習慣後花在除錯的時間便大幅減少。在解題細節上也更加注意、提升，如：下有意義的變數名、程式是否足夠精簡、有無不必要得程式碼，甚至更加有餘裕在解開題目之餘得以思考是否存在更優解，於此感受到自己程式設計能力的提升。
* 延伸學習
* 身心素質與自我精進
在學習過程中發現許多演算法皆是環環相扣，如佇列與樹演算法，因為演算法的好奇及熱情，所以在自主學習的時間甚至額外花費時間，盡最大的努力學習進階知識並實作。延伸學習後意外的收穫到許多不在原先計劃之中的演算法，例如樹及其相關演算法。
* 報告呈現方式與價值
* 規劃執行與創新應變能力
* 目的探究與價值思考
原先對於此份報告的價值及呈現方式有許多迷茫的部分，製作此份報告我的目的為何？是打算將目的放在觀念上的整理還是實際應用呢？在過程中不斷探索：如何使時間發揮最大效益，使此份報告發揮「自主學習」價值最大化？藉由和師長討論、查找相關網路資料、和同儕討論，參考並思考、執行製作報告方式，具體實例如在實作過程中發現流程圖對邏輯梳理輯呈現成果的方式不如想像中的大又耗時，因而即時應變，更改原先策略轉而尋找其餘資料呈現方式，最終決定以創造最大學習價值為優先，取代原先製作流程圖計畫轉而研究自身解法的優缺點及如何優化。最終決定以HackMD主題式依照演算法種類彙整題目成果及解法之效率、記憶體消耗的百分比，同時整理自己各難度題目之通過率一併呈現。
# 心得：自我精進與價值思考
* 程式設計能力
* 系統思考與解決問題能力
* 規劃執行、創新應變能力
* 科技資訊及媒體素養
藉由實作練習，加深對複合概念題目的辨析和拆解能力，並研究及分析自身解法和leetcode上熱門解法之優缺點、差異。此自主學習計畫除加深對既有技能（遞迴、函式、物件及區塊、指標、迭代器等）的理解和活用，更是初次踏入演算法世界的里程碑，除了概念的理解，對許多程式設計手法、演算法的本質也有深一步認知，而計畫實行過程中也不斷思考、探索報告呈現方式及其價值，最終以實作成果、學習效益最大化的方式調整學習計畫和報告呈現方式。
透過五週時間，藉由自主查找演算法之相關延伸概念及尋找leetcode題目練習，將許多演算法（上述提及）從理解再到實作，也對競程的世界有初步的理解，過程中與師長、同儕交流意見、查找線上資源自學，發現自己的程式設計能力和系統思考與解決問題能力及規劃執行、創新應變能力皆有顯著提升，也在透過網路自學的過程中更進一步增益科技資訊及媒體素養，更是確立自己對於程式設計領域的好奇心及熱情。
Sign in with Wallet
Connect another wallet