資訊之芽 Week12 竹區作業題解

• 資訊之芽 Week12 竹區作業題解
  • NEOJ 1234
    • 解題思路 & Code
  • NEOJ 1111
    • 解題思路
    • Pseudo Code
  • NEOJ 20
    • 使用到的變數
    • 解題思路
    • Pseudo Code

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 的最後一個節點，讓最後一個節點指向新節點

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$ !

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$。

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$，就印出值並指向下一個節點

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

#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

#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;
}