Zako's Blog

題目網址：https://leetcode.cn/problems/sqrtx/ 題意：給一非負整數 x, 計算並返回 x 的平方根 。 由於返回類型是整數, 因此答案只保留整數部分, 小數部分將被捨棄。 注意：禁止使用 pow(x, 0.5) or x ** 0.5 運算。 Solution： 想法：利用 Binary Search, 左閉右開容易導致 overflow。當 x = INT_MAX 時, x + 1 會 overflow, 故要先將 x 轉成 long class Solution {public: int mySqrt(int x) { int left = 0, right = x; while (left <= right) { // mid 轉成 long, 避免 mid * mid 出現 overflow const long mid = left + (right - left) / 2; if (mid * mi ...

題目網址：https://leetcode.cn/problems/intersection-of-two-linked-lists/ 題意：給兩個 linked list 的 head headA 和 headB, 返回兩個 linked list 相交的起始點。若不存在相交, 則返回 null。 題目保證 linked list 中不存在 cycle。 注意：函數返回後, linked list 必須保持原先的結構。 進階：設計 $O(m + n)$ time 且 $O(1)$ space 的演算法。 Solution 1： 想法：利用 hash set, 先將 headA 中的每個點 insert 到 visited 中, 然後再遍歷 headB 中的每個點, 一旦發現 visited 已存在, 則返回該點。 class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<List ...

題目網址：https://leetcode.cn/problems/remove-element/ 題意：給一整數 array nums 和一整數 val，請 in-place 移除所有數值等於 val 的元素, 並返回移除後 nums 的新長度。 不要使用額外的空間, 設計 $O(1)$ space 的演算法, 並原地修改 nums。 元素的順序可以改變, 不需要考慮 nums 中超出新長度後面的元素。 Solution： 想法：利用 Two Pointers, 先初始化 slow = fast = 0, 用 fast 來遍歷 nums, 而 slow 用來指向新 array 下一個要填入的元素的 index。一旦 nums[fast] != val, 則 nums[slow] = nums[fast], 然後 slow += 1 e.g. nums = [3, 2, 2, 3], val = 3 slow = 0, fast = 0, 此時 nums[fast] = 3 = val 跳過 slow = 0, fast = 1, 此時 nums[fast] = 2, nums ...

題目網址：https://leetcode.cn/problems/last-stone-weight-ii/ 題意：有一堆石頭, 用整數 array stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。 每一回合, 從中選出任意兩塊石頭, 然後將它們一起粉碎。假設石頭的重量分別為 x 和 y, 且 x ≤ y。粉碎的可能結果如下： 若 x == y, 則兩塊石頭都會被完全粉碎 若 x != y, 則重量為 x 的石頭將會完全粉碎, 而重量為 y 的石頭新重量為 y - x 最後, 最多只會剩下一塊石頭。返回此石頭最小的可能重量, 如果沒有石頭剩下, 則返回 0。 Solution 1： 想法：假設 stones = [a, b, c, d], 每次取出兩顆來粉碎, 可以想成每次取出兩數, 然後在這兩數前面分別加上 +/- 號, e.g. 其中一種可能的解為 a - b + c - d（類似 494. Target Sum）。因此, 利用 hash set s 保存前 i - 1 個石頭所產生的和, 然後一一取出這些和, 並加上第 i 個數分別取 +/- ...

題目網址：https://leetcode.cn/problems/longest-palindrome/ 題意：給一只由大、小寫字母所組成的 string s, 返回這些字母所能組成的最長迴文 string 之長度。 須區分大、小寫, 比如 "Aa" 不能當作一個迴文 string。 Solution： 想法：利用 Greedy。在一個迴文 string 中, 最多只有一個 char 能出現奇數次, 其餘的 char 皆須出現偶數次。我們可以將每個 char 使用偶數次, 使得它們根據迴文中心對稱。在這之後, 如果有剩餘的 char，我們可以再從中取出一個, 作為迴文中心。 class Solution {public: int longestPalindrome(string s) { unordered_map<char, int> freqs; for (const auto& ch : s) { ++freqs[ch];
...