題目： LeetCode - 1041. Robot Bounded In Circle 題目說明給一個字串，代表機器人移動的指令，機器人會不斷重複這段指令，求機器人的移動範圍是否可以用一個圓圈圍住。 解題思路若是要滿足題目的條件，則做完一段指令後機器人需要回到原點，或是機器人面向跟最初不同的方向 ( 向北 )，紀錄機器人的座標及面向，並遍歷字串模擬完成指令後的狀態即可。 參考解法1234567891011121314class Solution {public: bool isRobotBounded(string instructions) { pair<int, int> pos, face{0, 1}; for(auto c : instructions) { if(c == 'G') pos.first += face.first, pos.second += face.second; else ...

題目： LeetCode - 421. Maximum XOR of Two Numbers in an Array 題目說明給一個陣列，找出陣列中最大的任意兩者互斥或的值。 解題思路由於互斥或有 a ^ b = c -> a ^ c = b 的特性，所以可以先找出一個最大值，接著遍歷陣列查看 val ^ 最大值 是否存在，若存在表示這個最大值是可以被陣列中兩數互斥或出來的。由於要找最大值，所以要讓二進制中最高位盡可能為 1，因為只需要判斷最高位，所以我們需要一個 mask，接著將陣列中過遮罩的值存入 unordered_set，最後遍歷 set 查看 val ^ (ret | i) 是否存在即可。 參考解法123456789101112131415class Solution {public: int findMaximumXOR(vector<int>& nums) { int ret{}, mask{}; for(int i = 1 << ...

題目： LeetCode - 58. Length of Last Word 題目說明給一個字串，求字串中最後一個單詞的長度。 解題思路從後面開始遍歷字串，先使用 String 的 find_last_not_of() 從後往前找第一個字母的 index，接著利用 isalpha() 判斷是否為字母，找出長度即可。 參考解法123456789class Solution {public: int lengthOfLastWord(string s) { int idx = s.find_last_not_of(' '), length{}; while(idx >= 0 && isalpha(s[idx--])) ++length; return length; }};

課程名稱：線性代數 CS233 B授課教師：簡廷因發放時間：2020-09-14截止時間：2020-09-28 23:59:59 Get a integer N from parameter, and print the result of 1+2+…+N to STDOUT 0 < N < 65535 Sample input : 10Sample output : 55Sample command : ./tinin.exe 10 題目說明給一個整數 N，求 1 + 2 + … + N 的值並 cout 出來。 解題思路先判斷 argc 是否大於 1，表示至少有一個參數傳入，接著判斷此參數是否 大於 0 且小於 65535。若是的話先使用 atoll() 將字串轉為數字 ( 轉為 long long 避免數值超越 int 的邊界 )，最後使用梯形面積公式算出答案即可。 ※ argc 表示傳入參數的數量，char* argv[] 表示傳入的參數。argv[0] 為程式的名稱。 參考解法1234567891011121314151617#include <iost ...

題目： LeetCode - 198. House Robber 題目說明給一個陣列代表每間房子的搶劫價值，不能搶連續的兩間房子，求能搶劫的最大價值。 解題思路使用動態規劃的思路，dp[i] 代表到第 i - 1 間能搶到的最大價值，遍歷 nums，若是決定第 i - 1 間要搶，則 dp[i] 為 dp[i - 2] + nums[i]，若是不搶則為 dp[i - 1]，兩者取較大者即可。 參考解法12345678910class Solution {public: int rob(vector<int>& nums) { int n = nums.size(); vector<int> dp(n + 1); for(int i = 1; i <= n; ++i) dp[i] = max(dp[max(i - 2, 0)] + nums[i - 1], dp[i - 1]); return dp[n]; }};

題目： LeetCode - 57. Insert Interval 題目說明給一個代表區間的陣列，及一個要插入陣列的區間，插入後需要將重疊的部分合併。 解題思路由於陣列已經依照起始點的位置排序過，所以只需要將區間插入到正確的位置，接著利用 LeetCode - 56 的作法來將重疊的部分合併即可。詳細作法可參考本篇文章：LeetCode - 56 解題紀錄。 參考解法12345678910111213141516class Solution {public: vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { auto iter = intervals.begin(); while(iter != intervals.end() && iter->at(0) < newInterval[0]) ++ ...

題目： LeetCode - 56. Merge Intervals 題目說明給一個代表區間的陣列，要求將有重疊的區間合併。 解題思路先將區間依照起始點排序，接著遍歷區間，若是第一個區間或是區間的起始點大於上個區間的結尾點，表示兩者沒有重疊，直接存入 res，否則更新上個區間的結尾點即可將兩個區間合併。 參考解法1234567891011121314class Solution {public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), [](auto& l, auto& r) { return l[0] < r[0]; }); vector<vector<int>> res; for(auto& interval : in ...

題目： LeetCode - 216. Combination Sum III 題目說明給兩個整數 k 及 n，求在 1 ~ 9 的數字中，找出 k 個相加會等於 n 的數，此為一組，一組內的數字不可重複，每組中的數不可相同。 解題思路使用 dfs 尋找解，為了避免重複，我們由小找到大，每次遞迴中先判斷 k 及 n，若 k 為 0 代表數字已經夠了，此時若是 n 為 0 則代表這是一組解。接著使用迴圈，i 從 bound 開始到 9 繼續做 dfs。 參考解法123456789101112131415161718192021class Solution {public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> res; vector<int> cur; dfs(k, n, 1, cur, res); return res; &# ...

題目： LeetCode - 152. Maximum Product Subarray 題目說明給一個陣列，求陣列中最大的子陣列乘積。 解題思路由於是乘積，極小值乘以負數時會變為極大值，所以需要同時保存目前的子陣列乘積最大值及最小值。使用動態規劃的概念，最大值為 mx * nums[i] 及 nums[i] 兩者取較大者，最小值為 mn * nums[i] 及 nums[i] 兩者取較小者，若是碰到目前元素為負數時，則需要將兩者互換再去判斷。 參考解法123456789101112131415class Solution {public: int maxProduct(vector<int>& nums) { int mx = nums[0], mn = mx, res = mx, n = nums.size(); for(int i = 1; i < n; ++i) { if(nums[i] < 0) swap(mx, mn); ...

題目： LeetCode - 299. Bulls and Cows 題目說明給兩個字串，一個代表猜測的密碼一個代表正確密碼，若是位置及數字都正確則 A 增加，若是數字正確而位置錯誤則 B 增加。 解題思路使用一個陣列紀錄正確密碼的個數，接著遍歷兩個字串，先判斷 guess 當前的字元是否存在陣列中，接著判斷 guess 的當前字元是否等於 secret 的當前字元即可。 參考解法123456789101112131415class Solution {public: string getHint(string secret, string guess) { int A{}, B{}, n = secret.length(); vector<int> v(10); for(auto& c : secret) ++v[c - '0']; for(int i{}; i < n; ++i) ...