Yaoの程式小窩

【C++ 筆記】資料抽象與 ADT - part 25很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ 簡介 Data abstraction refers to providing only essential information about the data to the outside world, ignoring unnecessary details or implementation.From GeeksForGeeks 資料抽象指的是只提供外界所必要的資訊，忽略不必要的細節或實作面。 什麼意思呢？就像你在玩遊戲時，可以看到角色的 HP、MP 等資訊，但你不需要知道這些數值是怎麼計算的、存在哪個記憶體位址、或者用什麼資料結構去記錄這些資訊。 遊戲開發者只會讓你看到角色的重要狀態資訊，而把它的具體表示方法（如 class 的欄位、加密編碼或計算過程）藏起來，這就是資料抽象。 資料...

【Leetcode C++ 解題筆記】Greedy - part 1本筆記僅供個人學習用途，內容斟酌參考。 409. Longest Palindromedifficulty : Easy. tags : hashtable, string, greedy. 題目敘述： 給定一個由大寫或小寫所組成的字串 s，回傳那些可以由字母所組成最長回文的長度。 字母是區分大小寫的，如 Aa 不被視為一種回文。 解題思路： 建立一個 hashtable (unordered_map)，計算每個字母所出現的次數。 如果次數是偶數：表示可以對稱放在回文的左右兩邊，可以全部使用，所以直接將次數加進去 len 裡面。 若次數是奇數：因為回文有對稱性，所以只能用偶數部分（次數 - 1）放在左右兩邊，剩下的字母可置於回文中間。（整個回文只能有一個這樣的字母在中間） solution ( 0 ms )： 12345678910111213141516171819202122232425262728class Solution {public: int longestPalindrome(...

【C++筆記】Iterator（迭代器）該筆記僅供個人學習用途，部分用詞、解釋等若有誤方可指正，感謝您的觀看。 簡介Iterator，名為迭代器，光看名字就是一個非常抽象的東西XD。 Iterator 是一種類指針（pointer-like）的物件，指向 STL container 的元素。像是 vec.begin() 跟 vec.end() 分別指向 vec 容器的第一個元素跟末尾元素的記憶體位址，使用 * 做 Dereference 的動作即可取值。 整理一下：Iterator 的意義是記憶體位址，使用 * Dereference operator 可用來取得目前 iterator 所指向的元素的值。 Why is Iterator?而迭代器之所以被稱為迭代器，是因為它的設計目的是為了支援容器中元素的「逐一存取」（iteration），類似於指標。 首先要說什麼是迭代 iteration？ 「迭代」的核心概念是：重複逐個存取資料結構中的每個元素，直到全部處理完畢。其實就是跑迴圈的意思，如下是一個最基本的迭代行為： 12345// use for loop to do iter...

【C++】競程筆記（資料結構：Unordered set / map）程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 簡介Unordered set / map 皆為無序的（unordered）關聯式容器，內部實作原理皆是 Hash（雜湊），對於每次操作的時間複雜度都是 $O(1)$ 。如果此資料結構發生碰撞的話，最壞的時間複雜度會到 $O(n)$ 。 那既然都無序了，所以就字面上意思，輸出的元素不一定會照著順序排。 Unordered set / map 提供了較快的操作速度，在操作上面也與原本的 set / map 無異，基本上都相通。 另外兩者的標頭檔都有稍微更改： 12#include <unordered_set>#include <unordered_map> 雜湊（Hash）介紹 雜湊函式（英語：Hash function）又稱雜湊演算法，是一種從任何一種資料中建立小的數字「指紋」的方法。雜湊函式把訊息或資料計算成摘要，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值（又叫雜湊值）（has...

【C++】競程筆記（資料結構：map）程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 簡介map 是 C++ STL 裡面的一個容器，跟 set 一樣都是關聯式容器（Associative Container），他用鍵值對（Key & Value）的方式來存資料，並自動依 key 的順序進行排序（預設為升序）。 可以想成 Python 的 dictionary，但有點不一樣。 鍵值對就是 key 對應一個 value，如：{1, "apple"}，1 這個 key 會對應到 apple，輸入 1 時就會輸出 apple。 map 的底層結構也是基於紅黑樹的自平衡二元搜尋樹。 特性 唯一性： key 不能重複。 元素型態： pair<const Key, T>，key 為常數。 不支援隨機存取： 只能透過 iterator 遍歷容器。 雙向迭代器： 可向前向後遍歷元素，表示可用 rbegin() 跟 rend() 反向迭代器。 語法（Syntax）1map<key_type, v...

【C++】競程筆記（資料結構：set）程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 簡介set 是基於紅黑樹（Red-black tree）所實現的，紅黑樹是一種自平衡避免退化的二元搜尋樹，而因為 STL 幫我們實作出來了，所以不用再重造輪子。 所以 set 在查詢、插入、刪除這方面都是對數時間 $O(logn)$ 。 另外 set 也是一種關聯式容器（Associative Container），就是使用 key 來做資料存取（set 以輸入的 value 作為 key，可查找 value 是否存在 set 中）。 關聯式容器也可再細分為有序（ordered）與無序（unordered）。 set 特性 唯一性： set 中的元素不能重複出現，若 insert 重複值，會自動被忽略。 有序性： set 中的元素會依照升序（預設）自動排序，可改成降序。 無法直接修改： 因為直接修改會破壞 set 的有序性，所以要改的話要先刪除再插入。 語法（Syntax）1set<T, comp> s; T：在 set 中元素的資料型態。 comp...

【C++】競程筆記（資料結構：Heap）程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 簡介Heap（堆積），是一個完全二元樹的資料結構，主要應用於優先佇列（priority queue）中。 由於他是完全二元樹結構，所以： 除了最底層外，其他每一層都是滿的。 最底層節點從左到右依序填滿。 樹上的每一個節點儲存一個可以比較大小的鍵值（key），並支援以下操作： 插入一個鍵值 詢問目前最大的鍵值 刪除最大的鍵值From NTUCPC Guide Heap 通常遵守下列其中一種堆積性質： 最小堆（Min-Heap）：每個節點的值都 $\leq$ 其子節點的值。（根節點是整棵樹中最小的元素） 最大堆（Max-Heap）：每個節點的值都 $\ge$ 其子節點的值。（根節點是整棵樹中最大的元素） Image Source：https://www.geeksforgeeks.org/dsa/heap-data-structure/ 以下網站有可以滑動的視窗，展示哪一種是 invalid heap，哪一種是 valid heap。 https://www....

【C++】競程筆記（資料結構：Binary Tree）程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 簡介樹（Tree）在電腦科學領域是一個由「節點」（Node）和「邊」所組成的圖形，如圖： Image Source：https://www.geeksforgeeks.org/dsa/binary-tree-data-structure/ 基本術語 節點（Node）： 如 1、2、3、4 等這些數字被圓圈包起來的就是一個節點。 根節點（Root）： 指的是最上層的節點，沒有父節點，如 1 就是根節點 Root。 子節點（Child）： 位於某節點之下的直接後繼節點，如 1 底下的 2 跟 3 都是 1 的子節點；2 底下的 4 跟 5 都是 2 的子節點。 父節點（Parent）： 反之，父節點為子節點的上層節點。1 是 2 跟 3 的父節點，2 是 4 跟 5 的父節點。 葉節點（Leaf）： 沒有任何子節點的節點。如 8, 5, 9, 10 都沒有子節點，所以稱為葉節點。 深度（Depth）： 根節點的深度定義為 0，子節點的深度等於...

【C++ 筆記】基礎排序（氣泡、選擇、插入排序法）本筆記僅供個人學習用途，內容斟酌參考。 1.Bubble Sort原理：兩兩相鄰比較，大的往後推，重複進行多輪直到完成排序。 1234567891011void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { // 內層進行兩兩相鄰元素比較與交換 for (int j = 0; j < n - 1 - i; ++j) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } }} 時間複雜度： 最佳情況： $O(n)$ （若資料已排序，可加入 flag 判斷是否有交換，避免多餘比較） 平均情況： $O(...

【APCS】2023年1月實作題 C++ 解題筆記（前兩題）此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=j605 題目說明： 有 $K$ 個提交紀錄，第 $i$ 個提交紀錄有兩整數 $t_i, s_i$ ，分別為上傳時間跟提交分數，若第 $i$ 次的提交結果為嚴重錯誤，則 $s_i = -1$ 。 計算總分公式：提交紀錄最高分 $-$ 總提交次數 $-$ 總嚴重次數 $\times 2$。 若總分算出來 $< 0$ ，則計為 $0$ 。 輸出一行，總分和第一次最高分的時間點。 解題思路： 宣告兩變數 ans, sum_s，分別用來計算總分跟總嚴重錯誤次數 輸入的時候就可以先判斷是否有 s[i] == -1 的情形。 max_element(s.begin(), s.end()); 計算值最大的元素，但記得這回傳結果會是迭代器，要加上 * 解參考運算子（Dereference）。 用 find(s.begin(), s.end(), max_score); 跟 distance 去算第一...

【APCS】2023年6月實作題 C++ 解題筆記（前兩題）此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=k731 題目說明： 給定一個如數學座標一樣的二維平面（y 正為北, x 正為東），起始位置於 $(0, 0)$ 。輸入給 $n$ 個座標，必須按照這些點的順序移動，題目保證只會垂直或水平方向移動，不會斜向移動。且第一個點保證一定是 x 軸正的位置(初始方向向右)。 請輸出這條路徑中，左轉、右轉、迴轉的個數分別為多少。 解題思路： 定義方向： 0：東。 1：北。 2：西。 3：南。 計算方向： 根據相鄰兩點的座標變化，去判斷移動方向。如：若 x 不變，y 增加，則方向為北（1）；若 x 增加，y 不變，則方向為東（0）。 判斷轉向： 每點 $p_i$ （ $i$ 從 $1$ 到 $n-1$ ），分別計算兩個方向： 進入方向 d1：從 $P_{i-1}$ 到 $P_i$ 。 離開方向 d2：從 $Pi$ 到 $P_{i+1}$ 。 判斷 d1, d2 變化量 dir： dir =...

怎麼背 ASCII Code？（APCS 觀念題）以下是一個 ASCII Code 表。 圖片來源：https://shihyu.github.io/books/apas01.html ASCII 碼的取值範圍為 0 ~ 127，可用 7 個 bit 來表示一個字元。 那這東西怎麼背呢？其實只要找「開頭」就好，因為你也知道後面都是連續的，稍微數一下就可以推算出來。 比如十進位數字，只要找 0 的 ASCII Code = 48 即可，要找 7 的 ASCII code 的話就是 48 + 7 = 55。 接下來是英文字母，要記得他還分大小寫，同樣的，只要找開頭 A 跟 a 的 ASCII code 即可，如： A 的 ASCII code = 65。 a 的 ASCII code = 97。 那之後的英文字母，我相信大部分人應該都有背過 a-z 吧，之後數看在開頭的第幾位就可以了。 另外可以發現大小寫之間的 ascii code 的差值是 32，所以你只要記住大寫或小寫全部的 ascii code，即可用 32 去推算大小寫。 如：我知道 C 的 ASCII code 是 ...

【APCS】2023年10月實作題 C++ 解題筆記（第一題）此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=m370 題目說明： n 個位置上有食物，有一隻老鼠剛開始位於位置 x，覓食時只能往左或往右一個方向，試問找出最大能吃多少食物，並且最後一次吃食物停下的位置。 解題思路： 建立 vector <int> f(n + 1)，並把 x 丟進去 f 裡面，順序不重要，丟進去就好。 輸入完所有的 f 後，再進行排序。 使用 auto it = find(f.begin(), f.end(), x); 找出 x 的索引值。 計算從 x 到最小索引值跟最大索引值的距離，取 max() 得出最多能吃多少食物。 最後透過 f[0] 跟 f.back() 分別取得最後的位置。 範例程式碼： 1234567891011121314151617181920212223242526#include <bits/stdc++.h>using namespace std;int main()...

【C++】競程筆記（對答案二分搜）程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。 例題：https://zerojudge.tw/ShowProblem?problemid=h084 暴力解：直接窮舉所有可能高度的 x，並且看海報寬度，遍歷木板高度選可以貼的地方，但是這樣時間複雜度會是 $O(n^2)$ ，木板高度可能高達 $10^9$ 。 具體程式碼寫法： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657// 暴力破解法.cpp#include <bits/stdc++.h>using namespace std;bool canPlacePosters(const vector<int>& h, const vector<int>& w, int x) { int n = h.size(); int k = w.size(...

【APCS】2024年1月實作題 C++ 解題筆記（前兩題）此筆記僅供個人學習用途，內容僅供參考。 https://zerojudge.tw/ShowProblem?problemid=m931 題目說明： 有 $n$ 個角色，分別都有攻擊力（ $a_i$ ）跟防禦力（ $d_i$ ）。 能力值 = $a{i}^{2} + d{i}^{2}$ 。 輸出第二大的能力值的角色的攻擊力跟防禦力。 解題思路： 建立三個 vector：a, d, state，分別存每個角色的攻擊力、防禦力、能力值。 由於要求第二大，再加上預設排序函式都是升序，要降序就用反向迭代器 rbegin() 跟 rend()。 因為測資沒很大，直接遍歷找 (a[i]*a[i] + d[i]*d[i]) == state[1]。 cout 並 break，後面再找就沒意思。 1234567891011121314151617181920212223242526272829303132#include <iostream>#include <vector>#include <alg...