# 資訊之芽 Week12 竹區作業題解
[TOC]
## NEOJ 1234
https://neoj.sprout.tw/problem/1234/
### 解題思路 & Code
- $head$ 不指向 $nullptr$
- $head$ 指向 $nullptr$
#### void append(Node *&head, int value)
在 linked list 尾端新增值為 value 的節點。
1. 先判斷 $head$ 是否為 $nullptr$
- 若是，則將新節點直接設為 $head$
- 若否，進 step 2
2. 找到 linked list 的最後一個節點，讓最後一個節點指向新節點
```cpp
void append(Node *&head, int value) {
Node *new_node = new Node;
new_node->value = value;
new_node->next = nullptr;
// TODO: 判斷 head 是否為 nullptr
if (head == nullptr) {
// ....
return;
}
Node *cur = new Node;
cur = head;
while (cur->next != nullptr) {
// 讓 cur 指向下一個節點
// ...
}
// 最後一個節點指向新結點
// ....
}
```
#### void insert(Node *&head, int index, int value)
將值為 value 的節點插入 linked list 索引值為 index 的位置。
1. 判斷 index 是否為 0，index 為 0 代表新結點會變成新的 $head$
- 若是，讓新節點成為 $head$
- 若否，進 step 2
2. 找出 linked list 的第 index-1 個節點 $cur$
1. 新節點指向 $cur$ 的 $next$
2. $cur$ 的 $next$ 指向新節點
- 隨時注意是否指向 $nullptr$ !
```cpp
void insert(Node *&head, int index, int value) {
Node *new_node = new Node;
new_node->value = value;
new_node->next = nullptr;
// TODO: 如果 index 為 0
if (index == 0) {
// ...
return;
}
// TODO: 讓 cur 指向第 index-1 個節點
Node *cur = head;
for (int i = 0; i < index - 1; i++) {
// warning
if (...) {
cur = cur->next;
}
}
// 本題不需要下面這個判斷，但正常來說是必要的 !
if (cur == nullptr) {
delete new_node;
return;
}
// TODO: 接上新的節點
}
```
#### void deleteNode(Node *&head, int value)
在 linked list 刪除值為 value 的節點
1. 判斷 $head$ 是否為 $nullptr$
- 若是，什麼都不做
- 若否，進 step 2
2. 檢查 $head$ 是否為被刪除的節點
- 若是，新增一個指標 $M$ 指向 $head$，讓 $head$ 移到下一個節點，刪掉 $M$ 指向的節點
- 若否，進 step 3
3. 找出 "要被刪除的節點" $del$ 的 "前一個節點" $pre$
- $pre$ 的下一個節點即為 $del$，需要被刪除
- 因此先讓一個指標 $M$ 指向 $del$，讓 $pre$指向下兩個節點，再刪掉 $M$。
```cpp
void deleteNode(Node *&head, int value) {
// 判斷 head 是否為 nullptr
if(head==nullptr){
return;
}
// 檢查 head 是否為被刪除的節點
if(head->value == value){
// ...
return;
}
// 找出 "要被刪除的節點" del 的 "前一個節點" pre
Node *pre = head;
while (pre->next != nullptr && pre->next->value != value) {
pre = pre->next;
}
// 刪除節點
if (pre->next != nullptr) {
// ....
}
}
```
#### void print(Node *head)
印出 linked list 所有值，每印出一個值請換行，包含最後一個值也要換行！
1. 讓指標 $cur$ 指向 $head$
2. 只要 $cur$ 不為 $nullptr$，就印出值並指向下一個節點
```cpp
void print(Node *head) {
Node *current = head;
while (current != nullptr) {
// TODO: 印出值並指向下一個節點
}
}
```
## NEOJ 1111
https://neoj.sprout.tw/problem/1111/
### 解題思路
- 用==C-Style 字串==存取每張牌的資訊，並用 vector 把這些資訊存在一起。
(若會使用 string ， 則不須使用 C-Style 字串)
- 用 ==std::sort()== 對全部的牌==由小到大==排序。
- 在自定義的 compare function 裡，依照題目給的花色大小、數字大小做比較。
比較的優先級如下敘述 $:$
1. $Joker$ 最大，最先判斷是否有 $Joker$，$Joker$ 的資訊是字串長度為 $1$
2. 分別抓出字串的花色 $suit$ 與數字 $number$。==注意 $number$ 的長度==
3. 比較 $number$ 大小。
4. 比較 $suit$ 大小
### Pseudo Code
```cpp
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int get_suit_rank(char c) {
// TODO: 自己定義各個花色的大小，並回傳
}
int get_card_value(string c) {
// TODO: 將卡牌的 number 由 string 回傳成 int
}
bool compare(string a, string b) {
// TODO: 判斷是否為 Joker
// Joker 最大，最先判斷是否有 Joker，若有，則直接回傳。Joker 的資訊是字串長度為 1
// ....
// 抓出字串的花色 suit
char a_suit = a[0];
char b_suit = b[0];
// TODO: 抓出字串的數字 number
string a_number = ...
string b_number = ...
// TODO: 比較數字大小
if (get_card_value(a_number) != get_card_value(b_number)) return ...
// TODO: 比較花色
if (get_suit_rank(a_suit) != get_suit_rank(b_suit)) return ...
return false;
}
int main() {
// 輸入卡牌
int number_of_cards;
cin >> number_of_cards;
vector<string> card(number_of_cards);
for (int i = 0; i < number_of_cards; i++) {
cin >> card[i];
}
// 排序
sort(card.begin(), card.end(), compare);
// TODO : 輸出
// ....
}
```
## NEOJ 20
https://neoj.sprout.tw/problem/20/
### 使用到的變數
- 團體數量
- 假設為 $N$
- 紀錄人與團體之間的關係 `person_to_group`
- 用一個 vector `person_to_group` 來記錄每個人所在的群組
- `person_to_group` 大小設置為 1000000（題目有提到人的編號為 0 ~ 999999）
- 初始值設置為 -1 表示該人不屬於任何群組。
- 輸入每個成員會屬於哪一個群組，這時就更新 `person_to_group`，使其記錄每個人對應的群組編號。
- 主隊列 `main_queue`
- 管理各個團體排隊的順序，存放團體的編號
如下所示:
主隊列中，團體排隊的順序分別為 5, 7, ..., 1, 51, 93。
- 子隊列 `group_queues`
- 大小為 $N$
- 每個團體都有一個隊列來管理其成員的排隊順序。
如下所示:
- 子隊列 5 `group_queues[5]` 裡面有編號 12。
- 代表主隊列之中，所屬團體 5 的人只有編號 12。
- 且在主隊列中的排隊順序為 12。
- 子隊列 7 `group_queues[7]` 裡面有編號8, 10, ..., 4, 13
- 代表主隊列之中，所屬團體 7 的人只有編號 8, 10, ..., 4, 13。
- 且在主隊列中的排隊順序為 8, 10, ..., 4, 13。
- 記錄每個團體是否在主隊列中 `in_main_queue`
- 大小為 $N$
- 初始值為 false。代表一開始所有團體都不在隊列之中
### 解題思路
- `ENQUEUE X`
- 用 `person_to_group` 取得編號為 x 的人所屬的團體
- 檢查是否為單人，不屬於任何群組 (若為 -1 表示該人不屬於任何群組。)
- 若是，幫他創一個單人團體 `new_queue`，把`new_queue`加進 `group_queues`，並更新他的`person_to_group`、`in_main_queue`
- 若否，進入下一步
- 檢查該人所屬團體是否在主隊列之中
- 若否，將該團體加進 `main_queue`，並更新相關變數
- 若是，進入下一步
- 將該人加入其團體的子隊列
- `DEQUEUE X`
- 用`main_queue`取得最前面的團體
- 取出該團體子隊列中的最前面的一個人
- 檢查該團體的`group_queue`是否為空
- 若是，代表沒有人在排隊了，將其從主隊列中移除，並跟新`in_main_queue`
- 若否，進入下一步。
- 輸出取出來的人的編號。
### Pseudo Code
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int t;
cin >> t;
for (int test_case = 1; test_case <= t; test_case++) {
cout << "Line #" << test_case << endl;
int n;
cin >> n;
vector<int> person_to_group(1000000, -1);
for (int i = 0; i < n; i++) {
// TODO: 更新人的所屬團體
// ...
}
queue<int> main_queue;
vector<queue<int>> group_queues(n);
vector<bool> in_main_queue(n, false);
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string command;
cin >> command;
if (command == "ENQUEUE") {
int x;
cin >> x;
int group = person_to_group[x];
// 如果這個人單獨一組，do something......
if (group == -1) {
// ...
}
// 如果不在主隊列之中
if (!in_main_queue[group]) {
// ...
}
group_queues[group].push(x);
}
else if (command == "DEQUEUE") {
// 用`main_queue`取得最前面的團體
// ...
// 取出該團體子隊列中的最前面的一個人
// ...
// TODO: 如果子隊列內已經沒人
if (group_queues[front_group].empty()) {
// ...
}
cout << person << endl;
}
}
}
return 0;
}
```
Sign in with Wallet
Connect another wallet