Yaoの程式小窩

【C++ 筆記】命名空間（Namespace） - part 30 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ 可喜可賀可喜可賀，恭喜本系列終於來到 part 30 啦！ 簡介（Introduction） 我們最熟悉的命名空間不外乎就是： 1using namespace std; 為什麼要用這個？因為我們不想要打那麼多字，每次打一行程式碼都要加上 std:: 不是挺麻煩的嗎？ 123std::coutstd::endlstd::vector <int> a; 但其實除了圖方便以外，命名空間也有其他功能。 假設班上有兩名同學，他們都叫陳柏鈞，為了要區分他們兩個，我們就必定要用到額外的訊息去區分，如一個比較有錢，一個普通，或是一個帥，一個醜等等。 在 C++ 中，假設有個函數叫做 func()，而在另一個 library 也叫做 func()，此時就會有命名衝突（Name conf...

【C++ 筆記】動態記憶體（new / delete） - part 29 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ 動態記憶體（Dynamic Memory） 什麼是動態記憶體？ 當我們宣告一個變數的時候，編譯器會依據這個變數所屬的資料型態，自動配置其記憶體空間。這些資源都是配置於記憶體的堆疊區（stack），生命週期僅止於函數執行期間，當函數執行完成後就會自動清除。 另外，一旦配置後，就不能被刪除或更改他的大小。所以這時候動態記憶體就出現了。 在 C++ 中，記憶體分為兩部分（from 菜鳥教程）： 堆疊區（stack）：在函數內部宣告的所有變數都將佔用堆積記憶體。 堆積區（heap）：程式中未使用的記憶體，在程式執行時可用於動態配置記憶體。 動態記憶體配置是在程式執行時配置記憶體的過程，這可以讓開發者在程式執行期間預留一些記憶體，依據開發者的需求去用它，然後再把記憶體給釋放以用於...

【C++ 筆記】例外處理（Exception Handling） - part 28 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ 例外是什麼？ 例外（exception）又稱為異常，是指程式在執行過程當中發生的例外情況或錯誤事件。如將兩數相除的過程中，有一個數除於 0，這會是一個例外，因為可能會導致未定義的錯誤。 而處理例外的過程就稱為例外處理，對 XD。 基本例外處理 try-catch 語法： 12345678try { // 這可能會拋出一個例外 // Code that might throw an exception} catch (ExceptionType e) { // 例外處理的地方 // exception handling code} 當 try 區塊發生例外的時候，於 try 的區塊會停止，catc...

【C++ 筆記】型態轉換運算子（Casting Operator） 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ 四大運算子 稍後要講的這些運算子都是所謂的顯式轉換，表示有明確的函式去強制轉換資料型態，反之則為隱式轉換，如 10 / 1.0 自動轉成 float。 C-style 的顯式轉換：(int)var。 在 C++ 用 casting operator 取代，也更為安全。 1. static_cast 編譯時才轉換，因此在執行過程中沒有任何的效能開銷。 語法： 1static_cast <new_type> (exp); exp：要轉換的資料。 new_type：所需的運算式型態。 The static_cast can be used to convert between related types, such as numeric types or pointers ...

【C++ 筆記】檔案處理 - part 27 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ 至此之前，我們已經有學過 <iostream> 的標準輸入輸出流 cin, cout。 那本篇要學的就是 <fstream> 裡面的三種流，ofstream, ifstream, fstream。 基本檔案處理（File Handing） <fstream> 定義了三種資料型態： 表格參考：菜鳥教程 資料型態 敘述 ofstream （o：Output）輸出檔案流，用於建立檔案並向檔案寫入訊息。 ifstream （i：Input）輸入檔案流，用於從檔案中讀取訊息。 fstream 上述兩種資料型態的結合體，亦即同時具備兩種資料型態的功能。 要做到檔案處理，需引入 <iostream> 跟 <fstream>。 檔案...

【C++ 筆記】抽象類別（Abstract Class, ABC） - part 26 很感謝你點進來這篇文章。 你好，我並不是什麼 C++、程式語言的專家，所以本文若有些錯誤麻煩請各位鞭大力一點，我極需各位的指正及指導！！本系列文章的性質主要以詼諧的口吻，一派輕鬆的態度自學程式語言，如果你喜歡，麻煩留言說聲文章讚讚吧！ 純虛函數（Pure Virtual Function） 在講抽象類別（簡稱 ABC）之前，先來複習一下這個鬼東西。 :::info 純虛函數（Pure Virtual Functions）： 一個包含純虛函數的類別被稱為抽象類別（Abstract Class），它不能被直接實例化。 純虛函數沒有函數體，宣告時使用 = 0。 它強制衍生類別提供具體的實作。 ::: 來源：菜鳥教程 純虛函數宣告例子： 1234class Shape {public: virtual void draw() = 0; // 純虛擬函式}; 以上這段是來自本篇筆記系列的 part 23 多型。 抽象類別（Abstract Class, ABC） 定義 抽象...

【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 Palindrome difficulty : Easy. tags : hashtable, string, greedy. 題目敘述： 給定一個由大寫或小寫所組成的字串 s，回傳那些可以由字母所組成最長回文的長度。 字母是區分大小寫的，如 Aa 不被視為一種回文。 解題思路： 建立一個 hashtable (unordered_map)，計算每個字母所出現的次數。 如果次數是偶數：表示可以對稱放在回文的左右兩邊，可以全部使用，所以直接將次數加進去 len 裡面。 若次數是奇數：因為回文有對稱性，所以只能用偶數部分（次數 - 1）放在左右兩邊，剩下的字母可置於回文中間。（整個回文只能有一個這樣的字母在中間） solution ( 0 ms )： 12345678910111213141516171819202122232425262728class Solution {public: int longestPalindrom...

【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 i...

【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）又稱雜湊演算法，是一種從任何一種資料中建立小的數字「指紋」的方法。雜湊函式把訊息或資料計算成摘要，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值（又叫雜湊值）（...

【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...

【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 中元素的資料型...

【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://w...

【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 判斷是否有交換，避免多餘比較） 平均情況： $...