Hi, welcome to my space

Approach BFS，但在做的時候需要去確認下一格是否有與當前的格子連接。 Code class Solution { public: bool hasValidPath(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<pair<int,int>>> dir(7); dir[1] = {{0, -1}, {0, 1}}; // l, r dir[2] = {{-1, 0}, {1, 0}}; // u, d dir[3] = {{0, -1}, {1, 0}}; // l, d dir[4] = {{0, 1}, {1, 0}}; // r, d dir[5] = {{0, -1}, {-1, 0}}; // l, u dir[6] = {{0, 1}, {-1, 0}}; // r, u queue<pair<int,int>> q; vector<vector<bool>> vis(m, vector<bool>(n, 0)); q.push({0, 0}); vis[0][0] = 1; while (!q.empty()) { auto [r, c] = q.front(); q.pop(); if (r == m-1 && c == n-1) return true; for (auto [dr, dc]:dir[grid[r][c]]) { int nr = r+dr; int nc = c+dc; if (nr < 0 || nc < 0 || nr >= m || nc >= n || vis[nr][nc]) { continue; } for (auto [bdr, bdc]:dir[grid[nr][nc]]) { int rr = nr+bdr; // reverse check int rc = nc+bdc; if (rr == r && rc == c) { vis[nr][nc] = 1; q.push({nr, nc}); } } } } return false; } }; murmur 好久沒更新了，我覺得自己情緒控管還是有待加強，太容易被某些事情激怒或弄哭了。或許哭不是件壞事，但生氣絕對是百害而無一利，因為我生氣的對象通常也是我很敬愛的人，而就算自己不傷人，也依然會被人尖銳的言語所刺傷。所以至少不要在別人面前生氣，最好不要展露任何情緒比較好。

Approach 將機器人的 index 依照位置排序，如果一個機器人往右衝就把它丟進 stack，反之，如果一個機器人往左衝，就一直跟 stack 裡面的機器人比較生命值，直到自己的生命值歸零/在較量中輸了或是 stack 已經清空。 AC Code class Solution { public: vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) { int n = positions.size(); vector<int> idx(n), res; stack<int> stack; for (int i = 0; i < n; i++) { idx[i] = i; } sort(idx.begin(), idx.end(), [&](int a, int b) { return positions[a] < positions[b]; }); for (int cur:idx) { if (directions[cur] == 'R') { stack.push(cur); } else { while (!stack.empty() && healths[cur] > 0) { int topIdx = stack.top(); stack.pop(); if (healths[topIdx] > healths[cur]) { healths[topIdx]--; healths[cur]=0; stack.push(topIdx); } else if (healths[topIdx] < healths[cur]) { healths[cur]--; healths[topIdx] = 0; } else { healths[topIdx]=0; healths[cur]=0; } } } } for (int i = 0; i < n; i++) { if (healths[i] > 0) { res.emplace_back(healths[i]); } } return res; } }; Happy April Fool’s Day! 愚人節快樂，還蠻開心的，因為這是一年當中為我量身打造的節日，畢竟我本就是愚人:)

Approach Use hash table to record the frequency of each character of s1 and s2. Note that only the position with same parity can be swapped, if two strings’ sets of odd-position charaters are the same, they must can be permuted using finite number of transpositions. Code class Solution { public: bool checkStrings(string s1, string s2) { int n = s1.length(); vector<int> s1_odd(26, 0), s1_even(26, 0), s2_odd(26, 0), s2_even(26, 0); for (int i = 0 ; i < n; i++) { if (i & 1) { s1_odd[s1[i]-'a']++; s2_odd[s2[i]-'a']++; } else { s1_even[s1[i]-'a']++; s2_even[s2[i]-'a']++; } } for (int i = 0; i < 26; i++) { if (s1_odd[i] != s2_odd[i] || s1_even[i] != s2_even[i]) return false; } return true; } };

解法 基本上就是對於 row 跟 column 存 prefix sum，然後看當前累積的和有沒有機會等於全部元素的和除以 2。這是一題應該被放在簡單類別的中等題。 class Solution { public: bool canPartitionGrid(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); long long sum = 0; for (auto i:grid) { for (auto j:i) sum += j; } if (sum & 1) return false; sum >>= 1; long long cur_hor = 0; for (int i = 0; i < m-1; i++) { for (int j = 0; j < n; j++) cur_hor += grid[i][j]; if (cur_hor == sum) return true; } long long cur_ver = 0; for (int j = 0; j < n-1; j++) { for (int i = 0; i < m; i++) cur_ver += grid[i][j]; if (cur_ver == sum) return true; } return false; } }; 不知道標題要取什麼 之後想養成跑步的習慣，天氣跟時間允許的話就跑，code跟我至少要有一個是跑得動的～XD 感覺自己還在因為某些事造成的創傷所苦，希望趕快好起來！不然有的時候我真的好怕自己失去面對一切的動力，或許有時候我還是該跟人類說話，我不知道(?)

Solution 對每個位置存 prefix product 跟 suffix product (這個位置以前所有元素的乘積，和這個位置以後所有元素的 product)，最後把這兩個數字乘起來(記得模12345)就好了:))) class Solution { public: vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) { const int mod = 12345; int n = grid.size(), m = grid[0].size(); vector<vector<int>> prefixP(n, vector<int>(m, 1)); vector<vector<int>> suffixP(n, vector<int>(m, 1)); long long cur = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i == j && i == 0) { cur = (cur * grid[i][j]) % mod; continue; } prefixP[i][j] = cur % mod; cur = (cur * grid[i][j]) % mod; } } cur = 1; for (int i = n-1; i >= 0; i--) { for (int j = m-1; j >= 0; j--) { if (i == n-1 && j == m-1) { cur = (cur * grid[i][j]) % mod; continue; } suffixP[i][j] = cur % mod; cur = (cur * grid[i][j]) % mod; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { grid[i][j] = (prefixP[i][j] * suffixP[i][j]) % mod; } } return grid; } };

Problem Link https://leetcode.com/problems/determine-whether-matrix-can-be-obtained-by-rotation/ Solution class Solution { public: bool equal(vector<vector<int>>& a, vector<vector<int>>& b) { int n = a.size(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] != b[i][j]) return false; } } return true; } void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); reverse(matrix.begin(), matrix.end()); for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { swap(matrix[i][j], matrix[j][i]); } } } bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) { for (int i = 0; i < 4; i++) { if (equal(mat, target)) return true; rotate(mat); } return false; } }; untitled 很久沒有更新了，主要原因還是因為自己的惰性。這次的旋轉可以透過多開一個陣列存的方式實現。但如果要省空間，也可以 in-place 地做，一種方式是透過對稱性，先把整個矩陣上下翻轉，再沿著主對角線翻轉 (這是順時針，如果要逆時針就是先左右翻轉，再延主對角線翻轉) ...

20260223 數值方法看起來學的東西挺硬，不過學點理論的東西也不錯，第一堂課在教 Floating point system 以及一些定理的證明，上課形式是純粹播放幾年前的影片@@。然後教授英文很破 QQ 智慧型汽車導論跟 DSDL 跟我預期的差不多，不過我喜歡林忠緯的上課步調 (雖然是也看影片，不過影片錄的比林智仁好多ㄌ，講解條理分明) 20260224 作業系統還沒真正上課，暫時不評論。想到今年導生宴巫教授又會覺得我很眼熟，但我卻沒什麼理她就覺得挺尷尬的 QQ 我會努力在 OS 拿到 A+ 的，一定會。 高等電腦視覺我退掉了，我不能接受由學生上課，而且教授第一堂課就播了非常多搞笑影片，或許是為了讓上課變有趣，不過影片裡面甚至包括女性露點的畫面 = =。整個印象降到谷底。 20260225 去試著簽簽看 Web 程式設計，張傑帆的課整體很令人放鬆，儘管團隊合作依然令人不悅，我主要希望自己能累積一些實作經驗，而且自己以前蠻喜歡前端的，但學習之路皆半途而廢。 這禮拜沒有 Sato 的代數導論II 太難過了 20260226 重量訓練老師是梁澤敬，前田徑國手，感覺是個很有料的老師。 洪一平機率還沒開始上課，希望以他的步調能把 syllabus 的內容都講完。然後他又提到 Gaussian splatting 跟 inverse filtering ，影像處理的 PTSD 直接竄上來 @@ 別搞事了一平。 llm 不知道是不是這類文章真的變多了，還是我有意去滑，感覺有明顯 AI 生成痕跡的文章隨處可見，有夠噁心，說真的看到就想吐，難道大部分的受眾都不會感到反感嗎？ 然後我也很常看到軟體工程師是黃昏職業，什麼世界上90%的工作都會消失blablabla。說實話，我並不是不相信這些說詞，只是我並不喜歡人們做的那些事 (包括寫作、開發)，被貶低成一文不值、沒有任何意義。如果今天每個知識形成的過程都被忽略，學習舊知識、舊技能也被視為是迂腐不堪，或是應當被社會淘汰掉的事，這社會將會是災難性地枯燥乏味，時至今日我們依舊沒有看清 LLM 是一個極度擅長文字接龍的工具，忽略幻覺等缺陷，它並不需要為自己的錯誤負責，因此完全信任真的是件很可怕的事。 alone 反正因為某些因素，我有點不想再跟任何認識的人說話。我不喜歡自己的行為舉止、聲音，一切都是。這週我在學校基本上是沉默的，感覺其他人的聲音在自己的耳中都變得刺耳無比。我這學期無論如何都想拿到書卷獎，為此我一定要比系上所有人都還要努力，再也沒有什麼事情比前途、課業、工作、家人與金錢重要了，包括自己的健康、快樂、生活品質，人與人不過是互相利用罷了，為此我只要去建立利益為基礎的關係就好了。 荒謬、瘋狂、自大，我也懷疑自己是否真的這麼想，我知道我說出來的可能是錯的，但我卻沒辦法說服自己那是錯的，因為或許這樣做自己才能真正擁有成果? 真正成功？ 成功是什麼？我是誰？ 一切疑問都如同許久之前的夢一樣，在熟悉的環境中漾入模糊當中，與焦慮一同折磨著我的每條神經。為了不再悲傷、生氣，我或許該繼續麻痺自己的感受嗎？我不知道，我真的會有好過來的一天嗎？我越來越不期待那一天的到來了，因為自己從未改變，一樣是那個醜惡、懶惰而自我中心的小丑。 nothing changes 不會再有人過來幫我了，儘管我希望有。

Approach 1 搭車時用手機打的w class Solution { public: vector<int> sortByBits(vector<int>& arr) { int n = arr.size(); vector<pair<int,int>> v(n); for (int i = 0; i < n; i++) { v[i] = std::make_pair(__builtin_popcount(arr[i]), arr[i]); } sort(v.begin(), v.end()); for (int i = 0; i < n; i++) { arr[i] = v[i].second; } return arr; } }; Approach 2 使用 Brian Kernighan’s algorithm 來更有效率的找出一個數的 set bit 有幾個 (即 hamming weight)。 class Solution { public: static int findWeight(int x) { int res = 0; while (x) { res++; x &= (x-1); } return res; } static bool cmp(int a, int b) { if (findWeight(a) == findWeight(b)) { return a < b; } return findWeight(a) < findWeight(b); } vector<int> sortByBits(vector<int>& arr) { sort(arr.begin(), arr.end(), cmp); return arr; } };

今天用Python寫 :p Code # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: ans = 0 def traverse(self, root, cur): if not root: return if not root.left and not root.right: cur = cur<<1 | root.val self.ans += cur return self.traverse(root.left, cur<<1 | root.val) self.traverse(root.right, cur<<1 | root.val) def sumRootToLeaf(self, root: Optional[TreeNode]) -> int: self.traverse(root, 0) return self.ans

Approach 1 (brute force) class Solution { public: bool hasAlternatingBits(int n) { int cur = n & 1; for (int i = 1; i < 31; i++) { if ( (n >> i) == 0 ) break; int nxt = (n >> i) & 1; if (nxt == cur) return false; else cur = nxt; } return true; } }; Approach 2 (XOR trick) class Solution { public: bool hasAlternatingBits(int n) { long long x = n ^ (n>>1); return ((x & (x+1)) == 0); } }; Approach 3 (XOR trick too:)) class Solution { public: bool hasAlternatingBits(int n) { unsigned int x = n ^ (n >> 2); return ((x & (x-1)) == 0); } };