Posts

Binary Search 中的 lower bound & upper bound

前言 c++ 的 STL 有提供兩個跟 binary seach 有關的 function: lower_bound 和 upper_bound, 每次在寫 leetcode 相關的題目時都會一直忘記這兩個 function 的定義，故決定紀錄一下兩者的定義及用法 Include STL lower_bound 和 upper_bound 被定義在 <algorithm> 裡面 #include <algorithm> Lower Bound 找出數列中第一個大於或等於 target 的位置, 換句話說就是找到 >= target 的最小值的位置 // vector<int> v; // assume v is a sorted array auto it = lower_bound(v.begin(), v.end(), target); int idx = it - v.begin(); Upper Bound 找出數列中第一個大於 target 的位置, 換句話說就是找到 > target 的最小值的位置 // vector<int> v; // assume v is a sorted array auto it = upper_bound(v.

Monday, July 24, 2023 | 1 閱讀

如何在 Local 端測試/執行 Github Actions

前言最近在寫 side project 時想要設定 Github Actions 來自動化編譯跟測試流程，但是按照我之前的經驗是第一次設定 github action 的 workflow 時都會需要不斷修改來達到自己想要的結果，但是如果想要測試的話就會需要一直 commit & push 到 github 上面才有辦法測試，因此這次在設定 workflow 前，我想要找到一個可以不用 push 到 github 就可以在 local 端測試我的 workflow 的工具，這樣我就可以先測試完我的 workflow 後再一次 push 上去 github, 減少設定錯誤的機會，也不用一直繁瑣的 commit & push. 而我找到的工具就是 nektos/act 這個專案，目前在 github 上約有 40k 個 stars，可見這個需求有多大，本篇文就是紀錄如何使用這個工具的筆記。 Install nektos/act 這個專案有提供多種平台以及安裝方式，因為基本上我只會用這個工具來測試我的 workflow 有沒有寫錯，因此我選擇的是安裝官方提供的 GitHub CLI 擴充套件 Install Github CLI Offical installation guide 首先按照官方教學安裝 Github CLI type -p curl >/dev/null || (sudo apt update && sudo apt install curl -y) curl -fsSL https://cli.

Saturday, July 15, 2023 | 1 閱讀

如何在 Synology NAS 使用 non-root user 執行 Docker command

最近因為需要在 Synology NAS 上部署 Coder，container 需要 docker 的運行權限，因為 DSM 的 docker 比較特別，故這裡紀錄一下要如何讓非 root user 也能使用 docker 步驟首先 ssh 進 NAS 後，使用以下指令來新增 “docker” 這個 group, 並把需要 docker 權限的 user 加入 docker group sudo synogroup --add docker sudo synogroup --member docker $USER # 將自己加入 docker group 成功新增後，登入 DSM，可以看到在使用者群組的地方多了一個 docker, 可以加上補充說明這個 group 的作用 (所以理論上應該直接在 DSM 新增 group 就好了，但是我沒試過) 接著將 docker.sock 的 group ownership 從 root 改成 docker sudo chown root:docker /var/run/docker.sock 改完後重新登入，應該就可以不用加 sudo 就可以執行 docker command 了！

Wednesday, June 21, 2023 | 1 閱讀

[OpenWrt] 如何擴充 squashfs 的可用空間

問題我的 OpenWrt 是安裝在樹梅派上面，採用 squashfs, 安裝完後可以正常使用，但是可用空間只有 100 MB 左右，這是正常現象，如果沒有要安裝很多套件的話其實 100 MB 很夠用了，但是就無法完整利用到整個 SD 卡的空間 (我是裝 32G)；如果要裝 docker 等較大型的套件很快就空間不足了，故本篇文章即是要解決此問題。其實官方有 Wiki 教學是利用到 losetup 來完成，但是我自己嘗試是沒有成功的，我也懶得研究為甚麼，僅留下連結給有興趣的讀者自行嘗試看看。解決方式首先安裝套件，我們需要 cfdisk 和 resize2fs opkg update opkg install cfdisk resize2fs 安裝好後，可以先用 ls /dev 確認你的 SD 卡的 device 名稱，通常應該會是 /dev/mmcblk0 在 terminal 輸入以下指令 cfdisk /dev/mmcblk0 接著你應該會進入 cfdisk 的互動式介面可以看到在 /dev/mmcblk0p2 後面有很大的 free space. 接下來，用鍵盤移到 /dev/mmcblk0p2，會出現 Resize 的選項，選擇 Resize 這時系統會要你輸入要劃多大的空間，這裡不用輸入，保留預設值就好，這樣系統就會把所有的 free space 都劃進 /dev/mmcblk0p2，結果如下完成後輸入 yes 確認變更，這時候從畫面上可以看到 /dev/mmcblk0p2 已經變成 29.

Monday, November 28, 2022 | 1 閱讀

Leetcode 隨筆 - 62. Unique Paths

題目難度：Medium 題目連結: Unique Paths 題目大綱給你一個 m x n 的矩陣地圖, 請你找出從座標 (0, 0) 走到 (m-1, n-1) 一共有多少種走法。題目有限制每一次只能往下或往右走一步。解題思路解法一 - DP 設計一個 2 維陣列 dp[m][n], 其中 dp[i][j] 對應到座標 (i, j)，代表了從 (0, 0) 走到 (i, j) 一共有多少種走法。接著從題目的限制我們可以知道，要走到 (i, j) 的話一定要先走到 (i-1, j) 或是 (i, j-1)，然後再往下或往右走一步來到達 (i, j)。也就是說，走到 (i, j) 的走法數，會等於走到 (i-1, j) 的走法數加上走到 (i, j-1) 的走法數有了這層關係，我們就可以得出 dp 的公式如下： dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 而一開始要初始化 dp[i][0] = 1 (0 <= i <= m) 以及 dp[0][j] = 1 (0 <= j <= n)，代表從起點開始，一路往右或往下都只有一種走法

Tuesday, November 1, 2022 | 2 閱讀

Leetcode 隨筆 - 139. Word Break

題目難度：Medium 題目連結: Word Break 題目大綱給定一個字串 s 和一個字串陣列 wordDict, 請你判斷是否有辦法程式碼解法一這是我看完 NeetCode 影片的前半段的解題思路後想出來的解法 class Solution { private: vector<int> word_len; int s_len; vector<int> dp; public: void solve(string& s, int idx, vector<string>& wordDict) { if (idx >= s_len) { dp[s_len] = 1; return; } if (dp[idx] != -1) return; for (int i = 0; i < wordDict.size(); i++) { if (s.compare(idx, word_len[i], wordDict[i]) == 0) { solve(s, idx + word_len[i], wordDict); if (dp[s_len] == 1) return; } } dp[idx] = 0; } bool wordBreak(string s, vector<string>& wordDict) { word_len.

Sunday, October 30, 2022 | 1 閱讀

Leetcode 隨筆 - 152. Maximum Product Subarray

題目難度：Medium 題目連結: Maximum Product Subarray 題目大綱給你一個整數陣列, 找出擁有最大乘積的子陣列 (contiguous non-empty subarray) 程式碼 class Solution { public: int maxProduct(vector<int>& nums) { int ans = nums[0]; int max_product = 1; int min_product = 1; int t1, t2; for (int i = 0; i < nums.size(); i++) { t1 = max_product * nums[i]; t2 = min_product * nums[i]; max_product = max(t1, max(t2, nums[i])); min_product = min(t1, min(t2, nums[i])); ans = max(max_product, ans); } return ans; } };

Saturday, October 29, 2022 | 1 閱讀

Leetcode 隨筆 - 199. Binary Tree Right Side View

題目難度：Medium 題目連結: Binary Tree Right Side View 題目大綱給你一個 binary tree, 請你找出：從右邊看這棵樹，能看到的 node 有哪些。解題思路這題翻譯過後就是，請你找出此 binary tree 的每一層的最右邊的 node，所以我們只需要使用 level order traverse 的方式把 tree 掃過一遍抓出每層最右邊的 node 就行了！程式碼實作採用 C++ STL 的 queue, 遍歷時加上每個 node 的 level 資訊，當每掃到新的 level 時就會把該 node 加進 ans 裡面並更新 level 資訊；再來因為我們需要最右邊的 node, 所以 traverse 順序改成先掃右邊的 subtree 再掃左邊 subtree 的方式比較方便實作。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> rightSideView(TreeNode* root) { queue<pair<TreeNode*, int>> q; pair<TreeNode*, int> node; vector<int> ans; int cur_level = -1; if (root == NULL) return vector<int>(); q.

Monday, July 11, 2022 | 1 閱讀

Leetcode 隨筆 - 665. Non-decreasing Array

題目難度：Medium 題目連結: Non-decreasing Array 題目大綱給你一個陣列 nums，請你檢查是否可以在 “最多修改一個元素的值” 的限制下，把這個陣列變成一個非遞減陣列 (原來就已經是非遞減陣列也可以算通過檢查) 非遞減定義： nums[i] <= nums[i+1], where 0 <= i <= nums.size()-2 解題思路首先需要把陣列從頭開始掃描一遍，遇到 nums[i+1] < nums[i] 時停下來檢查是否可以修改元素值來完成題目要求，如果可以改，那就紀錄本次修改。所以我們可以用一個 counter 來記錄修改次數，而若修改次數大於 1 次就可以提前結束不用再往後檢查了。接下來重點就是：要怎麼確認可以修改(改成非遞減)？這裡可以分成幾個 case 來討論： Case 1. 陣列的開頭 or 結尾發生遞減情況也就是 nums[0] > nums[1] or nums[nums.size()-1] > nums[nums.size()-2]，這時候一定可以修改，因為只要把陣列頭的值往下修或把陣列尾的值往上調就可以了，所以直接更新 counter (counter++) 即可。 Case 2. 陣列中間發生遞減情況這時候發生了 nums[i+1] < nums[i]，為了判斷是否能夠只改一個值就能改成非遞減陣列，我們必須額外再抓出 nums[i-1] & nums[i+2] 這兩個元素來幫助我們判斷。首先第一項檢查 nums[i+2] 是否大於等於 nums[i-1] ? 因為若這個條件不符合，代表除了 nums[i] 跟 nums[i+1] 之外，在 nums[i+2] 這個位置又讓陣列發生了遞減情況，所以至少要改兩個地方，這樣絕對達不到題目要求，因此我們可以提早結束判斷、回傳失敗結果。

Saturday, June 25, 2022 | 2 閱讀

LeetCode 隨筆 - 74. Search a 2D Matrix

題目難度：Medium 題目連結: Search a 2D Matrix 題目大綱給你一個 m x n 的整數二維陣列和一個 value target，要你判斷 target 是否在這個陣列中。題目保證這個二維陣列：每個 row 的數字的順序已經由小到大排序過了每個 row 的第一個數字一定比上一個 row 的最後一個數字還要大解題思路由題目可知，將這個二維陣列按照 row 展開成一維陣列後就是一個排序過的 array，所以我們就可以直接用二分搜 (Binary Search) 來找 target。需要注意的是傳入的是二維陣列，所以在寫 binary search 的時候需要轉換一維 & 二維之間的坐標系一維 & 二維坐標系轉換範例：假設我們要轉換一維陣列的 index i 到一個 m x n (m rows * n columns) 的二維陣列的 index (row, col) row = i / n; col = i % n; 程式碼 binary search 可以使用迴圈或遞迴的方式來實作，以下提供兩種版本供讀者參考

Saturday, June 18, 2022 | 2 閱讀

LeetCode 隨筆 - 203. Remove Linked List Elements

題目難度：Easy 題目大綱給你一個單向的 linked list, 再給你一個數字 val, 移除該 linked list 中所有 Node.val == val 的 node 並回傳處理完後的 linked list. 解題思路分兩步驟來解：首先檢查 head node 是否符合條件，若 head 符合條件則一直執行 head = head->next ，不斷地把 head 截掉直到 head 是有效的 (Node.val != val) 接著一個 node 一個 node 去歷遍整個 list, 每個 node 的操作為：看下一個 node (後續以 next node 代稱) 是否符合條件，若符合的話就把自己的 next 指標接到 next node 的 next 指標 (也就是移除該 next node)，並繼續比較新的 next node (也就是回到第 2 步剛開始的操作)，否則繼續往下 loop 剩餘的 node 理論上移除掉的 node 要記得 free 掉不然會 memory leak, 不過這只是練習而已 LeetCode 好像也沒檢查這個，有沒有 free 掉都可以 AC

leetcode

Sunday, September 19, 2021 | 1 閱讀

Raspberry Pi 透過 Serial Port 連線 - 踩雷筆記

最近因為想要從 serial port 登入樹梅派而入手了一個 USB 轉 TTL 傳輸線，沒想到設定過程踩了不少雷，故寫了這篇作為提醒用。我是從電子材料行買的，型號為CONCBLUSBTTL，使用 PL2303TA 晶片理論上 win10 可以自動抓可以用的驅動，不需要特別下載。但如果有問題的話還是可以從晶片製造商的驅動程式下載頁面下載最新的驅動。解壓縮後除了驅動程式外還有一個小程式可以用來檢查晶片型號。這裡遇到我採的第一個雷 (自己雷)：在我一開始無法順利設定時，經爬文得知，由於舊款晶片 (PL2303HX 系列) 有偽造情形，故 win10 自動抓的驅動並不支援該款晶片的產品，需要下載舊版驅動才行，我還以為自己真幸運在 2021 還買得到舊款晶片，大費周章跑去前人的 blog 載舊版驅動，結果還是不行；又因為在舊版驅動下跑上面原廠提供的晶片型號檢查程式會將我的傳輸線誤判為 PL2303XA/PL2303HXA 害我誤以為自己真的買到 PL2303HX 晶片，一直往錯誤的方向 google。後來完全解決不了，改用新版驅動再測最後一次，想說不行就要放棄這條線了，才發現原來都是驅動搞的鬼。這裡提醒一下接線的注意事項，傳輸線和樹梅派的 TX/RX 要反著接，也就是線的 TX 要接到 Pi 的 RX，線的 RX 要接到 Pi 的 TX。GND 當然也要記得接。我這條線還有一個 5V 線，接上去後可以為 Pi 供電並開機，不過看其他人文章表示不一定要接這條線，而且我怕 GPIO 的供電不穩 (我用的是 pi 4, pi 4 在供電不足的情況下 wifi 會無法連線，就算能順利連上品質也不好，所以供電一定要足) 所以就沒接了。解決完驅動問題接下來就剩連線設定了，這裡是第二個要注意的地方，所有參數都要設定正確不然就會連不上！像是 speed，網路上的教學大都多是教人設定為 115200，但我的這條線，在裝置管理員的預設值為 9600，所以連線時要設 9600；還有 flow control 不論是 putty 或是 MobaXterm 預設都會是 Xon/Xoff，同樣與這條線的預設值不符，要記得關掉。

Wednesday, February 10, 2021 | 1 閱讀