市長的隨筆

我也好想成為電神喔～

發布於 更新於 分類於 文章字數： 304 所需閱讀時間 ≈ 1 分鐘

HackMD 課堂連結

容器

Zerojudge 題目

  1. c123: 00514 - Rails

這是之前寫的，我知道用 goto 很醜，但…好爽:)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <stack>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    ouo:
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        while (true) {
            stack<int> st;
            int train;
            int point = 1;
            int high = 0;

            for (int i = 0; i < n; i++) {
                cin >> train;
                if (train == 0) {
                    goto ouo;
                }
                for (int i = point; i <= train; i++) {
                    st.push(i);
                    point++;
                    high++;
                }
                if (st.top() == train) {
                    st.pop();
                    high--;
                }
            }
            if (st.empty()) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
}
  1. e447: queue 練習
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <queue>
using namespace std;

queue<int> a;

int main() {
    int times;
    cin >> times;
    for (int i = 0; i < times; i++) {
        int word;
        cin >> word;
        switch (word) {
            case 1:
                int num;
                cin >> num;
                a.push(num);
                break;
            case 2:
                if (a.empty()) {
                    cout << "-1\n";
                    break;
                }
                cout << a.front() << "\n";
                break;
            case 3:
                if (a.empty()) {
                    break;
                }
                a.pop();
                break;
        };
    }
}

Leetcode 題目

  1. 20. Valid Parentheses

好。。。我直接暴力解。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isValid(string s) {
        stack<char> check;
        for (auto i : s) {
            if (check.empty() && (i == ')' || i == ']' || i == '}')) return false;
            if (i == ')' && check.top() != '(') {
                return false;
            } else if (i == ']' && check.top() != '[') {
                return false;
            } else if (i == '}' && check.top() != '{') {
                return false;
            } else if (i == '(' || i == '[' || i == '{') {
                check.push(i);
            } else {
                check.pop();
            }
        }
        if (check.empty()) {
            return true;
        }
        return false;
    }
};
  1. 1700. Number of Students Unable to Eat Lunch

比較沒有那麼暴力的暴力解 XD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int j;
        for (int i = 0; i < sandwiches.size(); i++) {
            for (j = 0; j < students.size(); j++) {
                if (sandwiches[i] == students[j]) {
                    students[j] = 9;
                    break;
                }
            }
            if (j == students.size()) {
                return students.size() - i;
            }
        }
        return 0;
    }
};

發布於 更新於 文章字數： 384 所需閱讀時間 ≈ 1 分鐘

這是我第一次去考 APCS（誰叫你之前都忘記報），當天考觀念時肚子真的痛得要命，直到中午才去宣洩…我的考場在台北大學三峽校區，令我意外的是男女比沒有到很重，但是大佬倒是挺多的。考實作題時，不知道是不是緊張，就是一直在 debug…最後是寫到第三題寫了一點就結束了。我那天超孤單😢，我朋友給我請假…說他抽考沒讀，我也沒讀啊🤬。反正最後考了 4 / 3 還蠻理想的。

數字遊戲（易）

ZJ 連結：https://zerojudge.tw/ShowProblem?problemid=i399

輸入：3 個 1 ~ 9 的數字

輸出：先輸出數值出現最多的次數，再輸出三個數，且去除重複，由大到小。

想法：既要去掉重複又要排序，我的第一想法就是使用 set。set 是一個容器，它具有資料的唯一性，也就是不可重複，且容器內也會排序，跟 map 一樣。第一筆輸出我會用 4 - set 長度，這樣恰好是重複的個數，再用反向迭代器輸出 set 容器即可。

實作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <set>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int data[3];
    cin >> data[0] >> data[1] >> data[2];
    set<int> myset(data, data + 3);

    cout << 4 - myset.size();
    for (auto it = myset.rbegin(); it != myset.rend(); ++it) {
        cout << " " << *it;
    }
    return 0;
}

字串解碼（中）

想法：就…純粹的暴力解吧…，還有注意題目需求，這題要你解密，不是加密（我朋友不小心…）

實作：未更新（懶）

發布於 更新於 分類於 文章字數： 572 所需閱讀時間 ≈ 2 分鐘

電腦怎麼進行四則運算？

電腦其實很笨，所以計算機在做運算時，只會依你的命令順序做運算。

比如題目為 3 + 2 * 4

若照著順序按，得到的答案是 20。但以四則運算來說這很明顯已經錯了，答案應該為 11。

那前中後序的差別就是運算子的先後順序，可電腦有更好的方法進行四則運算，那就是後（前）序式。

後序式如：3 2 4 * +

數字在前，而運算子在後。在中序轉後序時，運算子會在過程中有比對先後順序，而非直接把運算式按順序放置後方。

1
2
3
運算子 數字 數字  // 前序
數字 運算子 數字  // 中序
數字 數字 運算子  // 後序

所以如果要讓電腦看得懂四則運算的規則必須要讓電腦知道每個符號的有先順序
如：
* / 大於 + -
( ) 大於 * /

中序式轉後序式

若遇到數字則直接輸出或放入字串，遇到運算子就判斷後放進 stack 裡。
若 stack.top() 的運算子權重小於讀取的運算子，如：+ - 小於 * / 直接 stack.push(運算子)，
若 stack.top() 的運算子權重大於讀取的運算子，如：* / 大於 + - 則先輸出或放入字串 stack.top()，再 stack.pop()，最後才 stack.push(運算子)。
若符號是 ( 則直接放入，繼續進行程式直到遇到 )，才把 stack 到 ( 裡的符號輸出或放入字串，記得最後也要把 ( pop 掉。

中序式元素 stack 後序式
( ( 無
3 ( 3
+ (+ 3
2 (+ 32
) 32+
* * 32+
( *( 32+
4 *( 32+4
- *(- 32+4
1 *(- 32+41
) * 32+41-
32+41-* 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int order(char sy) {
    if (sy == '+' || sy == '-') {
        return 1;
    } else if (sy == '*' || sy == '/') {
        return 2;
    } else {
        return 0;
    }
}

int main() {
    string str;

    while (cin >> str) {
        stack<char> symbol;   // stack 放運算子
        string postfix = "";  // 後序式

        for (int i = 0; str[i] != '\0'; i++) {
            if (str[i] == '(') {  // 符號處理
                symbol.push('(');
            } else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') {
                if (symbol.empty()) {
                    symbol.push(str[i]);
                } else {
                    int a = order(symbol.top()), b = order(str[i]);
                    // 若 a 是 *, b 是 -, 則權重大的先放進後序式
                    while (a >= b) {
                        postfix.push_back(symbol.top());
                        symbol.pop();
                        if (symbol.empty()) break;
                    }
                    symbol.push(str[i]);
                }
            } else if (str[i] == ')') {
                while (symbol.top() != '(') {
                    postfix.push_back(symbol.top());
                    symbol.pop();
                }
                symbol.pop();
            } else {  // 數字處裡
                postfix.push_back(str[i]);
            }
        }
        // 將未拿出的符號提出
        while (!symbol.empty()) {
            postfix.push_back(symbol.top());
            symbol.pop();
        }
        // 後序式輸出
        cout << postfix << "\n";
    }
    return 0;
}