746. Min Cost Climbing Stairs
題目網址：https://leetcode.cn/problems/min-cost-climbing-stairs/
題意：給一整數 array cost, 其中 cost[i] 代表從第 i 皆樓梯往上爬所需支付的費用。一旦支付該費用, 可以選擇往上爬一個 or 二個台階。
可以選擇從 index 為 0 or 1 的位置開始往上爬。
請計算到達樓梯頂部 index = cost.size() 所需的最小費用。
Solution 1：
想法：利用 DP, 定義 dp[i] 為抵達 index = i 所需的最小費用, 因此 dp[i] 為 抵達前一階的最小費用 + 該階的費用、抵達前兩階的最小費用 + 該階的費用 中取較小者
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
class Solution {public: int minCostClimbingStairs(vector<int>& cost) { const int n ...
111. Minimum Depth of Binary Tree
題目網址：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
題意：給一 BT, 求 root-to-leaf 的 path 之最小長度(tree 的最小深度)。
最小長度: path 上的 node 數
注意：若今給一 skew tree, 則 min_depth = n
Solution 1：
想法：利用 BFS
class Solution {public: int minDepth(TreeNode* root) { if (!root) { return 0; } int depth = 1; queue<TreeNode*> q; q.push(root); while (!q.empty()) { const int size = q.size(); for (int i = 0; ...
191. Number of 1 Bits
題目網址：https://leetcode.cn/problems/number-of-1-bits/
題意：給一無號整數 n, 返回其二進制表示中 1 的個數。
進階：如果多次呼叫此 function, 要如何優化？
Solution 1：
想法：每次判斷 n 的最右 bit 是否為 1, 若是的話, 則 cnt++, 判斷完最右 bit 後將 n 右移一位, 重複以上步驟直到 n == 0 （沒有 1-bit）為止
class Solution {public: int hammingWeight(uint32_t n) { int cnt = 0; while (n > 0) { const int rightmost = n & 1; if (rightmost == 1) { cnt++; } n >>= 1; } ...
268. Missing Number
題目網址：https://leetcode.cn/problems/missing-number/
題意：原本有一包含 [0, n] 總共 n + 1 個數的 array, 今給一只有 n 個數的 array nums, 找出缺失的數。
Solution 1：
想法：先將 nums 排序, 然後用 loop 檢查第 i 個數是否在 nums 中
class Solution {public: int missingNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { if (nums[i] != i) { return i; } } return nums.size(); // Example 2 } ...
234. Palindrome Linked List
題目網址：https://leetcode.cn/problems/palindrome-linked-list/
題意：判斷 linked list 是否迴文。
Solution：
想法：利用 876. Middle of the Linked List 的方法取得 linked list 的中點然後 reverse 以 slow 為 head 的 linked list, 最後比較兩個 linked list 是否相等(reverse linked list 可參考 206. Reverse Linked List)
class Solution {public: bool isPalindrome(ListNode* head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->nex ...