<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by FlyotLin on Medium]]></title>
        <description><![CDATA[Stories by FlyotLin on Medium]]></description>
        <link>https://medium.com/@flyotlin?source=rss-4bf41e1533e1------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*tg6a-IjhjEMgUZNes71INQ.png</url>
            <title>Stories by FlyotLin on Medium</title>
            <link>https://medium.com/@flyotlin?source=rss-4bf41e1533e1------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 02:58:26 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@flyotlin/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Leetcode 8 & 9]]></title>
            <link>https://medium.com/@flyotlin/leetcode-8-9-c1482dc62676?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/c1482dc62676</guid>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Thu, 21 Nov 2024 02:46:32 GMT</pubDate>
            <atom:updated>2024-11-21T02:46:32.313Z</atom:updated>
            <content:encoded><![CDATA[<p>這兩題都算滿簡單的，所以放在一起講。</p><p><a href="https://leetcode.com/problems/string-to-integer-atoi">https://leetcode.com/problems/string-to-integer-atoi</a></p><p><a href="https://leetcode.com/problems/palindrome-number/">https://leetcode.com/problems/palindrome-number/</a></p><h3>Solution</h3><h4>Leetcode 8 — string to integer atoi</h4><p>這題只有一些邊界問題要討論，其實挺簡單的。</p><p>邊界問題是 integer (int) 是否會 overflow，跟昨天的 <a href="https://medium.com/@flyotlin/leetcode-7-reverse-integer-f6e4bf243475">Leetcode 7</a> 有點像。</p><p>把數字字元加到 int 變數 n 時，正負數會分開處理。也就是正數用 + 的，負數用 - 的。</p><p>判斷 overflow 則會分別判 INT_MAX 和 INT_MIN，但因為 res 已經是正負數，所以如果 overflow 發生，就直接把最大最小的邊界值給 res 就好。</p><p>如果最後才考慮正負，res 恆為正，會發生 INT_MIN 沒辦法被表示在 res 裡面。</p><h4>Leetcode 9 — Palindrome number</h4><p>naive solution 是把數字轉字串，再檢查該字串是否為回文字串。</p><p>follow up 則是不轉成字串，嘗試直接檢查該數字是否為回文。</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c1482dc62676" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 7 — Reverse integer]]></title>
            <link>https://medium.com/@flyotlin/leetcode-7-reverse-integer-f6e4bf243475?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/f6e4bf243475</guid>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Wed, 20 Nov 2024 02:27:54 GMT</pubDate>
            <atom:updated>2024-11-20T02:27:54.000Z</atom:updated>
            <content:encoded><![CDATA[<h3>Leetcode 7 — Reverse integer</h3><p>很簡單的一個題目，唯一要注意的點是怎麼判斷 int overflow。</p><p><a href="https://leetcode.com/problems/reverse-integer">https://leetcode.com/problems/reverse-integer</a></p><h3>Solution</h3><p>定義 n 為原本的數字。做法是用 % 取餘數，取得 n 的最小位數。接著再 n/10，持續這件事直到 n 為 0。</p><pre>n := original number<br>rev := reverse of n<br><br>while n != 0<br>  remainder = n % 10<br>  rev = 10 * rev + remainder</pre><p>但要判斷反轉後的 n 是不是會 overflow。</p><p>int 的範圍是 2³¹ -1 ~ -2³¹，也就是 2147483647 ~ -2147483648。</p><p>根據上面的 pseudocode，可以知道 10*rev+remainder 可能造成 overflow，因此要特別檢查。</p><pre>10 * rev + remainder &gt;= INT_MAX<br>rev &gt;= (INT_MAX - remainder) / 10</pre><p>如果 rev &gt; INT_MAX，肯定會造成 overflow。</p><p>如果 rev = INT_MAX，就要看 remainder。INT_MAX / 10 會把個位數的 7 去掉，所以當 remainder 大於 7，就會造成 overflow。</p><p>INT_MIN 也是同理，當 remainder 小於 -8，就會 overflow。</p><h3>Note</h3><h4>C/C++ 負數除法與取餘</h4><pre>    cout &lt;&lt; 12 % 10 &lt;&lt; endl;    // 2<br>    cout &lt;&lt; 12 / 10 &lt;&lt; endl;    // 1<br><br>    cout &lt;&lt; -12 % 10 &lt;&lt; endl;   // -2<br>    cout &lt;&lt; -12 / 10 &lt;&lt; endl;   // -1<br><br>    cout &lt;&lt; -23 % 10 &lt;&lt; endl;   // -3<br>    cout &lt;&lt; -23 / 10 &lt;&lt; endl;   // -2</pre><p>跟正整數的除法、取餘一樣，只不過加上負號。</p><p>跟 Python 負數取餘 (<strong>餘數不會是負的</strong>) 的行為不同，但跟 Javascript 的行為相同。</p><h4>C++ template 模板</h4><p>template 其實就是泛型，可以將具體的資料型別抽離程式碼，在 compile time 透過 compiler 自動帶入型別 + 檢查。</p><p>template 分為兩種，function template 與 class template。</p><p>example:</p><pre>// funciton template<br>template &lt;class T&gt;<br>T add(T a, T b) {<br>    return a + b;<br>}<br><br>// class template<br>template &lt;class T&gt;<br>class MyClass<br>{<br>    T&amp; add(const T&amp; a) {<br>        return *this;<br>    }<br>};<br><br>MyClass&lt;int&gt; c1;</pre><p>通常動態型別的語言不需要 template/generic，因為本身就支援動態型別了，如 Python、Javascript。</p><p>但像是 Typescript 因為引入型別，因此又支援 generics。</p><h3>Refs</h3><ul><li><a href="https://www.rocksaying.tw/archives/3641717.html">https://www.rocksaying.tw/archives/3641717.html</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f6e4bf243475" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 6 — Zigzag Conversion]]></title>
            <link>https://medium.com/@flyotlin/leetcode-6-zigzag-conversion-70a90b71fb05?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/70a90b71fb05</guid>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Wed, 20 Nov 2024 01:50:08 GMT</pubDate>
            <atom:updated>2024-11-20T01:50:08.242Z</atom:updated>
            <content:encoded><![CDATA[<h3>Leetcode 6 — Zigzag Conversion</h3><p>想維持解題的規律跟手感，但最近實驗室還是會有些雜事 block 住，只能寫多少算多少了。</p><p>目前還沒很進入找工作的狀態，可能是還有碩論跟雜事要忙，沒辦法全神貫注地投入。</p><p><a href="https://leetcode.com/problems/zigzag-conversion/">https://leetcode.com/problems/zigzag-conversion/</a></p><h3>Solution</h3><p>這題其實沒什麼演算法，解法有以下兩種：</p><h4>1. 找出數學的規律</h4><p>依序 concat 每個 zigzag row 的字元，要找出每個 row 的每個字元之間 index 的間隔。<br>以 PAYPALISHIRING，3 列為例，zigzag 字串會長成：</p><pre>P.  A.  H.  N<br>A P L S I I G<br>Y.  I   R</pre><p>第一列的 index 是 0, 4, 8, …，與最後一列的規律一樣，都是 stride = 4，其中stride=2*row-2 。</p><p>中間的列還要考慮會有其他的字元，所以 stride 不是單純的 2*row-2。規律會變成 (stride-2*i, 2 )，i 是當前的 row number。</p><p>時間複雜度: O(n)</p><p>空間複雜度: O(1)</p><h4>2. 用 2D array 儲存 zigzag 字串</h4><p>先建立一個 2D 的 array，接著把 string 依照 zigzag 順序放到 2D array 中。最後再 row-by-row 地把字串印出來。</p><p>時間複雜度: O(n)</p><p>空間複雜度: O(n²)</p><p>第二個解法的好處是想法單純，但當初第一次看到這題目並沒想到這想法，而是想用第一種解法，找出數學規律。</p><h3>Note</h3><h4>std::unordered_set</h4><p>底層是用 hash table 實作的，跟 std::set 的實作不同，std::set 底層是紅黑樹 （self balance binary tree）。</p><p>set 是個 associative container (關聯式容器)，裡面只能儲存<strong>不重複</strong>的元素。</p><p>如名字所述，一個有排序，一個沒有排序。排序指的是用 iterator 遍歷該容器時，是否會有序的遍歷容器內的元素。</p><ul><li>unordered_set<br>插入、查詢、刪除：O(1)<br>空間：O(n)<br>碰撞發生時，插入的 worst case time complexity 為 O(n)</li><li>set<br>插入、刪除：avg O(1), worst O(logn)<br>查詢：O(logn)<br>空間：O(n)</li></ul><pre>#include &lt;iostream&gt;<br>// 需要引入標頭檔 (header file)<br>#include &lt;unordered_set&gt;<br>#include &lt;set&gt;<br><br>using namespace std;<br><br>int main() {<br>    set&lt;int&gt; s;<br>    // unordered_set&lt;int&gt; s;<br>    s.insert(1);<br>    s.insert(5);<br>    s.insert(2);<br><br>    for (auto it = s.begin(); it != s.end(); it++) {<br>        cout &lt;&lt; *it &lt;&lt; &quot; &quot;;<br>    }<br>    cout &lt;&lt; endl;<br>}</pre><h4>hash table</h4><p>能快速地將 key 對應到 value，屬於一種關聯式陣列 associative array。</p><p>內部透過 hash function，將 key 轉換成 hash table 的 index，再從 table 的 index 把 value 取出。</p><p>給定不同的 value，hash function 有可能計算出相同的 index，這種情況被稱作是 hash collision (碰撞)。</p><p>關聯式陣列指的是有鍵值對應 (key-value) 的資料結構，又被稱為 map (對映) 或 dictionary (字典)。</p><h3>Ref</h3><ul><li><a href="https://shengyu7697.github.io/std-unordered_set/">https://shengyu7697.github.io/std-unordered_set/</a></li><li><a href="https://github.com/bradtraversy/traversy-js-challenges/blob/main/06-hash-tables-maps-sets/02-hash-table-intro/readme.md">https://github.com/bradtraversy/traversy-js-challenges/blob/main/06-hash-tables-maps-sets/02-hash-table-intro/readme.md</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=70a90b71fb05" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 3 — Longest substring without repeating characters]]></title>
            <link>https://medium.com/@flyotlin/leetcode-3-longest-substring-without-repeating-characters-14ac3154b289?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/14ac3154b289</guid>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Sun, 17 Nov 2024 07:27:09 GMT</pubDate>
            <atom:updated>2024-11-17T07:27:09.429Z</atom:updated>
            <content:encoded><![CDATA[<h3>Leetcode 3 — Longest substring without repeating characters</h3><p><a href="https://leetcode.com/problems/longest-substring-without-repeating-characters">https://leetcode.com/problems/longest-substring-without-repeating-characters</a></p><h3>Solution</h3><p>使用 sliding window + set 就能解決這個問題，只是一開始被前幾天解的 dp 題 (找「最長回文子字串 longest palandromic substring」) 擾亂思緒，往列舉出所有長度的子字串，再一個個的檢查是否 valid 的方向思考。</p><p>不過，這題 input string 長度是 10⁴，用列舉法的 TC 就至少是 O(n³)，肯定會 TLE。</p><p>其實這題並沒有那麼複雜，可以用 sliding window 維護兩個 pointer (left &amp; right)，由左往右慢慢更新。並且把當前的 window 範圍內出現過的 character 紀錄在 set 裡面。</p><p>遇到沒看過的字元，就 right += 1。</p><p>遇到看過的字元，就持續 left +=1，直到當前的 s(left, right) 不包含重複的字元。</p><p><a href="https://github.com/flyotlin/leetcode/blob/main/3-longest-substring-without-repeating-characters/1.cpp">leetcode/3-longest-substring-without-repeating-characters/1.cpp at main · flyotlin/leetcode</a></p><h3>Note</h3><h4>std::set</h4><pre>// 初始化<br>std::set&lt;int&gt; s{1, 3, 4};<br><br>int arr[] = [1, 3, 5, 5];<br>std::set&lt;int&gt; s(arr, arr+4);  // 從 c-style 的 array 初始化<br><br>// 插入<br>s.insert(1);<br><br>// 查找<br>s.count(1);  // 回傳純量，0 or 1<br>s.find(1);  // 回傳 iterator，沒找到會回傳 s.end()<br><br>// 刪除<br>s.erase(1);<br><br>// 清空<br>s.clear();</pre><h4>std::unordered_set</h4><h3>Refs</h3><ul><li><a href="https://shengyu7697.github.io/std-set/">https://shengyu7697.github.io/std-set/</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=14ac3154b289" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 4 — Median of Two Sorted Arrays]]></title>
            <link>https://medium.com/@flyotlin/leetcode-4-median-of-two-sorted-arrays-3a4e30ffea52?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/3a4e30ffea52</guid>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Fri, 15 Nov 2024 09:28:04 GMT</pubDate>
            <atom:updated>2024-11-15T09:49:26.759Z</atom:updated>
            <content:encoded><![CDATA[<h3>Leetcode 4 — Median of Two Sorted Arrays</h3><p><a href="https://leetcode.com/problems/median-of-two-sorted-arrays">https://leetcode.com/problems/median-of-two-sorted-arrays</a></p><h3>Solution</h3><p>這題給你兩個 sorted array，請你找出這兩個 array 合併後的中位數。</p><h4>Brute force</h4><p>測資的限制其實挺寬鬆的，雖然要求 O(log(m+n)) 的時間複雜度，但就算用 O(m+n) 的解法也是能 AC。</p><p>brute force 就單純的直接 merge 兩個 array，再直接計算 median 回傳。</p><h4>Two pointers</h4><p>在兩個 vector 上分別維護 pointer i, j，初始值為 0。迭代更新 i, j，如果 v1[i] ≤ v2[j]，就把 i 加一。</p><p>更新過程中，也把最新的兩個 value 存到 m1, m2 中。</p><p>持續以上的過程，直到累積 size/2 個 value，最後就能把 m1, m2 的 value 當作 median 回傳。</p><p><a href="https://github.com/flyotlin/leetcode/blob/main/4-median-of-two-sorted-array/2.cpp">https://github.com/flyotlin/leetcode/blob/main/4-median-of-two-sorted-array/2.cpp</a></p><h3>Note</h3><h4>Vector initialization</h4><ul><li>vector&lt;int&gt; vec = {1, 2, 3}; : Using initializer list</li><li>vector&lt;int&gt; vec;</li><li>vector&lt;int&gt; vec(num, value); : Initialize vector with num values</li><li>vector&lt;int&gt; vec = {arr, arr+size};</li><li>vector&lt;type&gt; vec(v.begin(), v.end());</li></ul><h4>const for variables in C++</h4><ol><li>一般的 scalar<br>在 stack 上的 scalar value 不能被修改</li><li>指標<br>依照 const 的位置，會導致 stack 上的 pointer 或 heap 上的實際內容不能被修改</li></ol><pre>// scalar<br>const int num = 5;<br>num = 6;  // error<br><br>// pointer (指標指向的 heap 內容不可修改)<br>const char* name = &quot;abc&quot;;<br><br>// pointer (在 stack 上的指標本身不可修改)<br>char* const name = &quot;abc&quot;;<br></pre><h4>const for function in C++</h4><ol><li>const 加在 member function 前<br>不能修改 member function 的回傳值，通常用在 reference 上。</li><li>const 加在 member function 後<br>該 member function 不能修改 data member。</li></ol><pre>class Person {<br>public:<br>  void toggle() const {<br>    int n = 2;<br>    n = 3;  // ok<br><br>    name = &quot;abc&quot;;  // compile-error<br>  }<br><br>  const string&amp; getName() {<br>    return this-&gt;name;<br>  }<br>private:<br>  string name;<br>}<br><br>int main() {<br>  Person p;<br>  const string&amp; name = p.getName();<br>  <br>  name = &quot;abc&quot;;  // compile-error<br>}</pre><h3>Refs</h3><ul><li><a href="https://www.geeksforgeeks.org/initialize-a-vector-in-cpp-different-ways/">https://www.geeksforgeeks.org/initialize-a-vector-in-cpp-different-ways/</a></li><li><a href="https://shengyu7697.github.io/cpp-const/">https://shengyu7697.github.io/cpp-const/</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3a4e30ffea52" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 5 — Longest Palindromic Substring]]></title>
            <link>https://medium.com/@flyotlin/leetcode-5-longest-palindromic-substring-63aa3b4943e3?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/63aa3b4943e3</guid>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Thu, 14 Nov 2024 02:59:42 GMT</pubDate>
            <atom:updated>2024-11-15T03:43:04.115Z</atom:updated>
            <content:encoded><![CDATA[<h3>Leetcode 5 — Longest Palindromic Substring</h3><p>前陣子在忙些雜事，刷題就荒廢了一陣子。途中還跑去學 Rust，之後可能會把 Rust book 重要的內容也整理一下，打成一篇筆記。</p><p><a href="https://leetcode.com/problems/longest-palindromic-substring/">https://leetcode.com/problems/longest-palindromic-substring/</a></p><p>這題算標準的 Longest Palindromic Substring (最長回文子字串)，但很久沒寫這類題目，因此花了滿久卡在思考流程與邊界條件。</p><h3>Solution</h3><h4>Brute Force</h4><p>暴力 brute force 的想法是：</p><p>從長度為 1 的子字串枚舉到長度為 n 的子字串，遇到<strong>是回文且較長</strong>，就更新 global 最大值。</p><p>時間複雜度是 O(n³)，outer loop 是長度 1-n，inner loop 是枚舉該長度的所有字串 (n)，再加上檢查字串是否為回文。</p><p><a href="https://github.com/flyotlin/leetcode/blob/main/5-longest-palindromic-substring/3.cpp">leetcode/5-longest-palindromic-substring/3.cpp at main · flyotlin/leetcode</a></p><p>brute force 雖然是 n³，但因為 input 限制字串長度為 1000，10⁹ 勉強能通過，不會 TLE。</p><p>但要注意 memory 使用，字串直接放在 stack 上傳，可能會造成 memory limit exceed。</p><p>把字串直接存在 heap 上就行了。</p><h4>DP</h4><p>但仔細想想，這題目有點 dp (dynamic programming) 的味道。枚舉的過程中，短的字串會被包含在長的字串中。其實沒必要在看長的字串時，從頭開始檢查是否為回文。</p><p>可以用一個 array dp(i, j)紀錄 s(i, j) 是否為回文。根據題目要求，也可以變化為紀錄 s(i, j) 的最長子回文長度。</p><pre>// 初始條件<br>dp(i, j) = false<br><br>// 更新<br>dp(i, j) = true, if dp(i+1, j-1) = true<br>         = false, else</pre><p>但更新時要注意邊界，例如：</p><ul><li>i == j, =&gt; 0</li><li>i &gt; j, 這邊不會出現</li><li>j-1 &lt; 0, 特判</li></ul><p>dp(i,j) 更新後，就可以更新 global 最大值。</p><h4>Manacher’s Algorithm</h4><p>TBD</p><h3>Note</h3><h4>如何判斷回文？</h4><p>solve 1:</p><p>利用兩個變數作為頭尾往中間靠攏，自己覺得比較直覺，不用思考字串奇偶長度的邊界問題。</p><pre>bool isPalindrome(string s) {<br> int l = 0;<br> int r = s.size() - 1;<br><br> while (l &lt;= r) {<br>  if (s[l] != s[r]) {<br>   return false;<br>  }<br>  l++, r--;<br> }<br> return true;<br>}</pre><p>solve 2:</p><p>出發點是「比較 <strong>size/2</strong> 次」，頭尾要自己計算，我覺得比較不直覺。</p><p>奇數的部分，for 的 end condition 有等於，會比較中間的 char，沒有等於就不會比較到。可以直接省略等於。</p><pre>bool isPalindrome(string s) {<br> for (int i = 0; i &lt; s.size() / 2; i++) {<br>  if (s[i] != s[s.size() - i - 1]) {<br>   return false;<br>  }<br> }<br> return true;<br>}</pre><h4>memset()</h4><ul><li>declaration:</li></ul><pre>void *memset(void *ptr, int value, size_t n);<br><br>bool dp[100][100];<br>memset(dp, 5, sizeof(dp));</pre><p>使用 memset() 需要 include string.h (C) 或 cstring (C++)，可以將 ptr 指向的記憶體區塊 (n 個 byte) 設為 value 。</p><p>memset() 的單位是 byte，因此只適用於 bool、char 之類大小為 1 byte 的型別。</p><p>像是 int 之類的型別 (4 bytes)，就不能用 memset() 來初始化。</p><h3>Refs</h3><ul><li><a href="https://web.ntnu.edu.tw/~algo/Palindrome.html">https://web.ntnu.edu.tw/~algo/Palindrome.html</a></li><li><a href="https://leetcode.com/problems/longest-palindromic-substring/solutions/3202985/best-c-3-solution-dp-string-brute-force-optimize-one-stop-solution">https://leetcode.com/problems/longest-palindromic-substring/solutions/3202985/best-c-3-solution-dp-string-brute-force-optimize-one-stop-solution</a></li><li><a href="https://shengyu7697.github.io/cpp-memset/">https://shengyu7697.github.io/cpp-memset/</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=63aa3b4943e3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 225 — Implement Stack using Queues]]></title>
            <link>https://medium.com/@flyotlin/leetcode-225-implement-stack-using-queues-624a2b39a6e3?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/624a2b39a6e3</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[cpp]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Fri, 01 Nov 2024 15:58:45 GMT</pubDate>
            <atom:updated>2024-11-01T15:58:45.367Z</atom:updated>
            <content:encoded><![CDATA[<h3>Leetcode 225 — Implement Stack using Queues</h3><p>接續昨天的選題，今天挑了一個 queue 相關的題目。</p><p><a href="https://leetcode.com/problems/implement-stack-using-queues">https://leetcode.com/problems/implement-stack-using-queues</a></p><h3>Solution</h3><p>題目的要求是使用兩個 queue (q1、q2) 來模擬 stack FILO 的行為。用紙筆簡單畫了一下，有了一點想法。</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QHatu58CYzzpLAiP_tIjtQ.jpeg" /></figure><p>主要的想法是，在 stack pop 前，push() 就只塞到其中一個 queue 裡面。</p><p>在過程中，如果遇到：</p><ul><li>empty()：檢查兩個 queue 的 size</li><li>top()：回傳當前 queue 的 back()</li></ul><p>最後，當 stack pop() 的時候，持續 pop q1，並且將數值塞到 q2，直到 q1 為空。pop 的過程中，最後一個元素是 stack 的 top，要特別保留下來，並且不塞到 q2。</p><h3>Note</h3><h4>STL Queue</h4><p>member functions:</p><ul><li>push()</li><li>pop()</li><li>front(): queue head, popped first</li><li>back(): queue tail, popped last</li><li>size()</li><li>empty()</li></ul><h4>C++ Class</h4><p>Class 是 OOP 為了達成資料抽象 (abstraction) 與資料封裝 (encapsulation) 的手段，用來區分介面 (interface) 與實作 (implementation)。</p><p>在 C 的世界中，其實老早就有抽象的概念，將 declaration (.h) 與 definition (.c) 拆分開來。</p><p>在 class 的實作中，可以不用加上 this，直接訪問被定義的 member data 或 function。</p><p>C++ 的 class constructor 可以利用 <strong>initialization list</strong> 快速初始化 member data。</p><p><strong>C++ class 中的 this 是一個指向 object 本身的 <em>pointer</em>。</strong></p><p>C++ 的 class 還有 copy constructor、move constructor，還可以做 operator overloading，詳細的介紹之後有讀到再補充。（Rules of three/five）</p><pre>class T {<br>public:<br>  T() {}  // constructor<br>  ~T() {}  // destructor<br>  // member data<br>  // member function<br>private:<br>  // members<br>protected:<br>  // members<br>};</pre><h3>Reference</h3><ul><li><a href="https://cplusplus.com/reference/queue/queue/">https://cplusplus.com/reference/queue/queue/</a></li><li><a href="https://hackmd.io/@Mes/MinerT_Class">https://hackmd.io/@Mes/MinerT_Class</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=624a2b39a6e3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 20 — Valid Parentheses]]></title>
            <link>https://medium.com/@flyotlin/leetcode-20-valid-parentheses-38febbf1651d?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/38febbf1651d</guid>
            <category><![CDATA[stack]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[cpp]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Thu, 31 Oct 2024 14:02:19 GMT</pubDate>
            <atom:updated>2024-10-31T14:02:19.818Z</atom:updated>
            <content:encoded><![CDATA[<h3>Leetcode 20 — Valid Parentheses</h3><p>這幾天會找一些 stack、queue 的題目練習，主要圍繞在 C++ 的語法複習，以及基礎資料結構的熟悉。</p><p><a href="https://leetcode.com/problems/valid-parentheses">https://leetcode.com/problems/valid-parentheses</a></p><h3>Solution</h3><p>標準的可以利用 stack FILO 特性的題目。</p><p>解法就是單純的依序讀取字串，遇到的左括號放進 stack 中，遇到右括號就開始比對 stack top。</p><p>如果跟 stack top 成對，就 pop stack；反之，則代表這是個不合法的 parentheses string。</p><h3>Note</h3><h4>Stack</h4><ul><li>特性：FILO</li><li>可以用 array 或 linked list 實作</li><li>時間複雜度<br>插入：O(1)、搜尋：O(n)</li><li>C++ STL container 以 sequence adapter 的方式實作</li><li>對 stack 操作前，要檢查 stack 是否是 empty。<br>否則會因為 stack 預設的 container 是以 linked list 實作的 deque，而踩到 SEGV (segmentation violation)</li></ul><h4>Iterator</h4><p>“Iterate” is a technical term for looping.</p><p>An iterator is a pointer to the element inside a data structure.</p><p>Though underlying data access mechanism is different, iterator provides <strong>a uniform interface</strong> to access data from either <strong>sequential</strong> or <strong>associative</strong> container.</p><h4>How to use Iterator?</h4><p>Take vector for example:</p><pre>vector&lt;int&gt; vec = {1, 2, 3};<br>vector&lt;int&gt;::iterator it;<br><br>// forward<br>for (it = vec.begin(); it != vec.end(); it++) {<br>  cout &lt;&lt; *it &lt;&lt; endl;<br>}<br><br>// backward (reverse)<br>for (it = vec.rbegin(); it != vec.rend(); it++) {<br>  cout &lt;&lt; *it &lt;&lt; endl;<br>}</pre><p>Note that vec.end() points to one position after the last element.</p><h3>Conclusion</h3><p>有空可以再手刻以 array 和 linked list 實作的 stack，而非直接使用 STL library 的 stack。</p><h3>Reference</h3><ul><li><a href="https://web.ntnu.edu.tw/~algo/Data.html">https://web.ntnu.edu.tw/~algo/Data.html</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=38febbf1651d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 23 — Merge k Sorted Lists]]></title>
            <link>https://medium.com/@flyotlin/leetcode-23-merge-k-sorted-lists-e45c6b306e39?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/e45c6b306e39</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Wed, 30 Oct 2024 15:26:50 GMT</pubDate>
            <atom:updated>2024-10-30T15:26:50.261Z</atom:updated>
            <content:encoded><![CDATA[<h3>Leetcode 23 — Merge k Sorted Lists</h3><p>接續前一天的策略，隨手從 Leetcode Linked List 題組中挑了一個 Hard 的題目。</p><p>之前做過 Merge two Sorted Lists，這題算是那一題的變形、Follow-up。</p><p><a href="https://leetcode.com/problems/merge-k-sorted-lists">https://leetcode.com/problems/merge-k-sorted-lists</a></p><h3>Solution</h3><p>看完題目後，偷瞄了一下 Topics 發現跟 heap、priority queue 有關。當下還沒仔細思考複雜度，但腦中瞬間有了一個解法。</p><p>建立一個 priority_queue，遍歷所有 Linked Lists 中的 elements，並且加到 priority queue 裡面。</p><p>接著再依序取 priority queue 的 top（最小值）並且 pop，直到 queue 變成空的。</p><p>題目的限制是：</p><ul><li>Linked List 的數量: k (0 ≤ k ≤ 10⁴)</li><li>Linked List 中元素個數: n (0 ≤ n ≤ 500)</li></ul><p>最多有 10⁶ 個元素，時間複雜度會是 O(nk*ln(nk))，大約需要 10⁶ * ln10⁶ 次計算。</p><p>空間複雜度是 O(nk)，因為需要一個儲存所有元素的 priority queue。</p><p>不過，使用 priority queue 就沒辦法用到題目給的 sorted 的好處。AC 後看其他人的 solution 是 divide and conquer，就能利用到這個好處了。</p><h3>Note</h3><h4>Priority Queue</h4><p>是一個 heap 的結構，C++ STL (standard template library) 也有這個資料結構。</p><p>在 C++ STL 實作中，<a href="https://en.cppreference.com/w/cpp/container/priority_queue">priority queue</a> 的 declaration 是：</p><pre>template&lt;<br>    class T,<br>    class Container = std::vector&lt;T&gt;,<br>    class Compare = std::less&lt;typename Container::value_type&gt;<br>&gt; class priority_queue;</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8LDxtoEvjI1Q4uOcg_jlPQ.png" /></figure><p>預設會由大排到小，如果要由小到大，需要指定 Compare 為 std::greater&lt;int&gt;。<br><strong>Compare return true，會越晚從 priority queue 被 pop 出來。</strong></p><p>值得注意的是，<a href="https://en.cppreference.com/w/cpp/container">STL container</a> 有幾種類別：</p><ul><li>sequence containers<br>如 array、vector、list、deque</li><li>associative containers<br>如 set、map</li><li>unordered associative containers<br>如 unordered_set、unordered_map</li></ul><p>但，priority queue 其實並不屬於以上的任何一個類別。priority queue 是一個 container adaptor，用來<strong>提供不同的 interface 給 sequence container</strong>。</p><p>這也是為什麼在 template 的 declaration 中，第二個 template parameter 會是 container。</p><h4>Leetcode address sanitizer</h4><p>第一次寫完 submit 的時候發現會一直出現以下的錯誤：</p><pre>AddressSanitizer: attempting free on address which was not malloc()-ed</pre><p>後來檢查了一下，在程式碼中有一個 ListNode *head;，沒有被初始化為一個 ListNode 的 object 或者是 nullptr。</p><h3>Conclusion</h3><p>submit 出現的各種 error（如 AddressSanitizer）有空可以再更仔細的追究發生的原因。</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e45c6b306e39" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Leetcode 11 — Container with most water]]></title>
            <link>https://medium.com/@flyotlin/leetcode-11-container-with-most-water-7ac4d9203d44?source=rss-4bf41e1533e1------2</link>
            <guid isPermaLink="false">https://medium.com/p/7ac4d9203d44</guid>
            <category><![CDATA[c-programming]]></category>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[FlyotLin]]></dc:creator>
            <pubDate>Tue, 29 Oct 2024 04:05:35 GMT</pubDate>
            <atom:updated>2024-10-29T04:05:35.800Z</atom:updated>
            <content:encoded><![CDATA[<h3>Leetcode 11 — Container with most water</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bCm-PlDfdhykn18rBJevvQ.png" /></figure><p>最近開始刷題，先從基本的 data structure 開始複習。策略是主題式的複習，這幾天的目標是 array、linked list 之類的資料結構，因此從 leetcode array 類別中選到了這一題。</p><p><a href="https://leetcode.com/problems/container-with-most-water">https://leetcode.com/problems/container-with-most-water</a></p><h3>Naive Solution</h3><p>這題乍看之下的 naive solution 是 O(n²)，把所有可能的長寬組合都暴力嘗試過一遍，Pseudocode 如下：</p><pre>max_area = 0<br>for i = 1 ... n<br>  for j = i+1 ... n<br>    max_area = max(max_area, (j-i) * min(height[i], height[j]))</pre><p>不過仔細觀察題目的限制 (constraints)，2 ≤ n ≤ 10⁵，以這種 O(n²) 的解法，複雜度會變成 10¹⁰，超過一般 CPU 可以在時間範圍內處理完的指令數。</p><p>印象中一般在解這種題目的最大可接受複雜度是 10⁸ ~ 10⁹，超過的話通常會 TLE。（有錯請糾正我，知道 10⁸ 怎麼導出來的也可以告訴我，太久沒寫這類題目）</p><h3>Real Solution</h3><p>這題其實可以利用 <strong>two pointer</strong> 的方法解決。</p><p>two pointer 通常會用在 sorted array 或 sorted linked list 上，將 left、right pointer 分別設在左右兩個端點，利用 sorted 的特性，逐漸往中心收攏，<strong>探索最大的可能性</strong>，個人覺得<strong>有種 greedy 的味道</strong>。</p><p>這題雖然沒有 sorted array，但有個特性是最大的底 * 最大的高，會得到最大的面積。</p><p>一開始我們無法得知最大的高，因此可以先從最大的底探索，也就是把 two pointer 設在左右端點。</p><p>接著，逐漸往中心靠攏，在過程中把較短的邊捨棄掉，探索最大的高。</p><p>如此一來，就能將所有可能的最大面積都探索過一次。</p><h3>Bonus</h3><h4>Min &amp; Max</h4><p>在過程中用到 C++ 的 max 跟 min，就順手看了一下 <a href="https://cplusplus.com/reference/algorithm/max/">cppreference</a> 的介紹。</p><p>如果 a, b 是一樣的 (equivalent)，會直接回傳 a。</p><p>除了最基本的 max(a, b) 這樣的用法， max() 還有多個 overloaded 的實作。</p><p>其中一種實作可以傳入 comp，改掉預設的 compare 行為。max 預設是 &lt;，min 預設是 &gt;，也可以自己傳入一個 binary <strong>function</strong>。<br>我想這個設計，是為了支援 object 之間的比較。因為預設的 &gt;、&lt; 只能比較 scalar，除非 object 的 class 有做 operator overloading。</p><p>另一種實作可以傳入 il (initializer list)，讓 max、min 可以從一個 list 中找出最大、最小值。</p><p>另外，max 跟 min 為了支援多種 data type，將資料型態從實作中抽離，背後是透過 C++ 的 template 實作的。</p><h4>Initializer List</h4><p>根據 cppreference，initializer list 的 declaration 是 <strong>a list of elements of type </strong><strong>const T</strong> 。</p><p>可以透過 std::initializer_list 來定義</p><p><a href="https://cplusplus.com/reference/initializer_list/initializer_list/">std::initializer_list</a></p><h3>Conclusion</h3><p>寫題目前要把題目的 constraints 看好，把時間、空間複雜度估好，不然很容易一 submit 就 TLE。</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7ac4d9203d44" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>