題目： LeetCode - 495. Teemo Attacking 題目說明給一個陣列及一個整數，整數代表攻擊後能使敵人中毒的時間，陣列代表攻擊敵人的時間點，若攻擊時敵人處於中毒狀態則中毒狀態更新。 解題思路由於中毒時被攻擊會使中毒狀態更新，所以每次中毒的時間可視為兩次攻擊的間隔及 duration 兩者取較小值，最後判斷攻擊次數是否為 0，若為 0 則回傳 0，否則回傳 ret + duration，因為最後一次攻擊時中毒時間必定為 duration，所以結果需要加上 duration。 參考解法1234567891011121314151617// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int findPoisonedDuration(vector&l ...

題目： LeetCode - 179. Largest Number 題目說明給一個陣列，裡面有包含許多整數，求這些整數能組出的最大數字。 解題思路我們先對陣列進行排序，排序的規則為 to_string(l) + to_string(r) > to_string(r) + to_string(l)，由於答案的組成也是將數字轉換為字串後組起來，所以我們在排序時也是以轉換成字串後組起來較大的數值放在前面，如 9, 30 兩數排序，由於 930 > 309，所以 9 排在前面，最後將陣列組成字串組起來即可。 參考解法123456789101112131415161718// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: string largestNumber( ...

題目： LeetCode - 389. Find the Difference 題目說明給兩個字串 s 及 t，t 為 s 加上一個字元組成，求該字元為何。 解題思路由於字元本身為 ascii code，也是一種數字，所以使用 XOR 找出多出來的字元即可，詳細可參考本篇文章：LeetCode - 136 解題紀錄。 參考解法123456789class Solution {public: char findTheDifference(string s, string t) { char ch{}; for(const auto& c : (s + t)) ch ^= c; return ch; }};

題目： LeetCode - 134. Gas Station 題目說明有一個環形的加油站點，車子的油箱容量無限，給兩個陣列分別代表兩個加油站間需要消耗的油量以及到加油站能補充的油量，求從哪個起點開始可以走完一圈，若無法走完則回傳 -1。 解題思路貪心法，一開始先選 0 作為起點，接著往下走，curr 紀錄目前剩下的油量若是油量不夠到下一個點則選擇下一個點作為起點，同時記錄總獲得的油量及消耗的油量，結束時若是總油量大於等於 0 代表可以從 start 開始走能走完一圈。 參考解法12345678910111213141516171819202122// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int canCompleteCircuit(vector<in ...

題目： LeetCode - 229. Majority Element II 題目說明給一個陣列，求陣列中出現次數大於 陣列大小 / 3 的元素。 解題思路先使用 Unordered_map 紀錄每個元素出現的次數，接著遍歷找出符合條件的元素即可。 參考解法1234567891011121314151617181920// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: vector<int> majorityElement(vector<int>& nums) { int bound = nums.size() / 3; vector<int> ret; unord ...

題目： LeetCode - 1094. Car Pooling 題目說明給一個陣列 trips 及一個整數 capacity，trips 中每個元素包含三個數，依次代表搭車人數、上車站、下車站，capacity 代表公車能同時容納的最大人數，求公車在運送期間人數是否會超過 capacity。 解題思路由於題目有說上車站及下車站的值不會超過 1000，所以定義一個陣列表示站，紀錄每個站會變動的人數，先遍歷 trips，將上車站加上上車的人數，下車站減去下車的人數，接著遍歷 timeStamp，紀錄到目前為止車上的人數，若是人數大於 capacity 回傳 false，否則遍歷結束後回傳 true。 參考解法1234567891011121314class Solution {public: bool carPooling(vector<vector<int>>& trips, int capacity) { int timeStamp[1001] = {}, curCap{& ...

題目： LeetCode - 980. Unique Paths III 題目說明給一個陣列代表二維地圖，1 代表起點，2 代表終點，0 代表可以經過，-1 代表無法經過，求有幾條不同的路徑可以從 1 走到 2 並且所有 0 都經過一次。 解題思路使用 dfs 的概念，先找出 0 的數量及起點的座標，接著使用 dfs，從起點的座標開始，當經過 0 時將 n 加一，並將當前座標先設為 -1，在進入下一層 dfs，結束後將當前座標回復為 0，最後當走到 2 時，若 n 與 target 相等代表有一條達成條件的路徑。 參考解法12345678910111213141516171819202122232425class Solution {public: int uniquePathsIII(vector<vector<int>>& grid) { int x, y, target{}; for(int i{}; i < grid.size(); ++ ...

題目： LeetCode - 1291. Sequential Digits 題目說明給兩個整數 low, high，求大於等於 low 且小於等於 high 的所有整數，整數需要每一位都比前一位的值大 1，如 123、234、3456 …，且返回的陣列須按大小排列。 解題思路題目的要求可以想成從 “123456789” 中找在範圍中的連續子串，先找出 low 及 high 的位數，因為在範圍中的數字位數必定會在 low 及 high 的位數中間，接著使用兩個迴圈，第一層代表位數，第二層為起點 ( 從 0 到 9 - i )，這樣做的同時確保了數字會由小到大，接著判斷，若是數字大於 high 則接下來同位數的數都不會在範圍中，最後判斷若是大於等於 low 則存入結果。 參考解法12345678910111213141516class Solution {public: vector<int> sequentialDigits(int low, int high) { int ldigits = to_string(low). ...

課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-09-16截止時間：2020-09-22 題目說明完成 Unordered_set 的部分函式。 解題思路下面是依照我寫的順序來排序的。 void assignGrow(const size_type cells, const value_type val) 函式功能： 將動態陣列的大小擴張為 cells，並且將值都設為 val。 參考作法： 先判斷原本的動態陣列是否存在，若存在則先刪除，接著重新宣告一個 cells 大小的動態陣列，再將值一一放入，最後將 pointer 的位置更新即可。 參考解法：1234567// set the elements stored here to cells copies of valvoid assignGrow( const size_type cells, const value_type val ){ if (myData.myFirst) delete[] myData.myFirst; myData.myLast = myData.myEnd ...

題目： LeetCode - 121. Best Time to Buy and Sell Stock 題目說明給一個陣列代表每日的股票價格，求買賣一次的最大收益。 解題思路動態規劃，轉移方程為： 12cost = min(p, cost);profit = max(p - cost, profit); 參考解法12345678class Solution {public: int maxProfit(vector<int>& prices) { int cost = INT_MAX, profit = 0; for(auto p : prices) cost = min(p, cost), profit = max(p - cost, profit); return profit; }};