【C++ 筆記】資料抽象與 ADT - part 25
【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
【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(迭代器)
【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)
【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)
【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)
【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)
【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)
【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++ 筆記】基礎排序(氣泡、選擇、插入排序法)
【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++ 解題筆記(前兩題)
【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++ 解題筆記(前兩題)
【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?(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++ 解題筆記(第一題)
【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++】競程筆記(對答案二分搜)
【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++ 解題筆記(前兩題)
【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...




