787. Cheapest Flights Within K Stops
題目網址：https://leetcode.cn/problems/cheapest-flights-within-k-stops/
題意：有 n 個城市通過一些航班連接。給一整數 array flights, 其中 flights[i] = [from_i, to_i, price_i] , 表示該航班都從城市 from_i 開始, 以價格 price_i 抵達 to_i。
給定所有的城市和航班, 以及起點 src 和終點 dst, 找出一條最多經過 k 站中轉的 path, 使得從 src 到 dst 的價格最便宜, 並返回該價格。 如果不存在這樣的 path, 則返回 -1。
Solution 1：
想法：利用 Dijkstra 演算法
建立 adjacent lit
建立 min heap
執行 BFS
typedef pair<int, int> pii; // {weight, next}typedef tuple<int, int, int> t3i; // {cost, cur, times} ...
198. House Robber
題目網址：https://leetcode.cn/problems/house-robber/
題意：你是一名專業的強盜, 計劃搶劫沿路的房子。每棟房子都藏有一定數量的金錢, 唯一阻止你搶劫的限制是相鄰的房子都連接了安全系統, 如果闖入兩棟相鄰的房子，它會自動報警。
給一整數 array nums, 表示每棟房子所藏有的金額, 返回在不報警的情況下能搶劫的最大金額。
Solution 1：
想法：利用 DP, 其中 dp[i] 代表 index 位於區間 [0, i] 這 i + 1 間房子中可搶劫的最大金額。接著，我們考慮單一一間房子的情況，對於 index = i 的房子我們有兩種選擇，要搶 or 不搶
若 index = i 的房子不搶, 此時的最大金額 = 區間 [0, i - 1] 的最大金額 = dp[i - 1]
若 index = i 的房子要搶, 此時的最大金額 = 區間 [0, i - 2] 的最大金額 + index = i 的金額 = dp[i - 2] + nums[i]
➔ 因此 dp[i] 就為這兩種可能中 ...
213. House Robber II
題目網址：https://leetcode.cn/problems/house-robber-ii/
題意：你是一名專業的強盜, 計劃搶劫沿街的房屋。每棟房子都藏有一定數量的錢。所有的房子都排成一圈。這意味著第一棟房子是最後一棟的鄰居。同時, 相鄰的房屋都連接了安全系統, 如果同一晚上有兩間相鄰的房屋被闖入，它會自動報警。
給定一個整數 array nums, 表示每棟房子的金額, 返回在不報警的情況下搶劫的最大金額。
Solution：
想法：跟 198. House Robber 類似, 只是首尾相連, 如果搶了第一家，就不能搶最後一家, 所以第一家和最後一家只能搶其中的一家, 或者都不搶。 所以把第一家和最後一家分別去掉, 各算一遍能搶的最大值, 然後比較兩個值取其中較大的一個即為所求
class Solution {public: int rob(vector<int>& nums) { const int n = nums.size(); if (n <= 1) { ...
5. Longest Palindromic Substring
題目網址：https://leetcode.cn/problems/longest-palindromic-substring/
題意：給一 string s, 找出 s 中最長的迴文 substring。
注意：
substring 指的是 string 中 連續的 subset
subsequence 則是 string 的 subset
Solution 1：
想法：利用 DP, 因為我們發現「一個迴文去掉兩頭後, 剩下的部分仍為迴文」, 我們用 dp[i][j] 代表 substring s[i~j] 是否迴文, 則可得到下列公式：
dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]
dp[i + 1][j - 1] 在 dp[i][j] 的左下方, 故順序為由左至右, 一行一行的填, 其中對角線為 true
e.g. "abba" 中已知 "bb" 為迴文, 所以 dp[1][2] = true
➔ 則 dp[0][3] 則因為 "a" == & ...
102. Binary Tree Level Order Traversal
題目網址：https://leetcode.cn/problems/binary-tree-level-order-traversal/
題意：給一 BT root, 返回 node.val 之 level-order（由上層往下層, 每層由左至右）。
Solution 1：
想法：利用 BFS
class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { if (!root) { return {}; } vector<vector<int>> res; queue<TreeNode*> q; q.emplace(root); while (!q.empty()) { vector<int> level; ...