題目： LeetCode - 497. Random Point in Non-overlapping Rectangles 題目說明給一個陣列代表矩形的左下角座標及右上角座標，所有矩形都不會重疊。要求完成一個函式能隨機取一個在矩形內的點。 解題思路 Solution(vector<vector<int>>& rects)： 先使用一個陣列紀錄到目前的矩形總共有多少的點，方便做隨機取樣。 vector<int> pick()： 隨機取一個小於點的數量的數，接著找出它位於第幾個矩形，接著在該矩形內隨機取一點即可。 參考解法12345678910111213141516171819202122232425// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution &# ...

題目： LeetCode - 905. Sort Array By Parity 題目說明給一個陣列，要求將陣列重新排序，使得偶數的元素都在前面的部份，奇數都在後面的部份。 解題思路遍歷整個陣列，使用雙指針，當碰到偶數就將它跟前面的值交換即可。 參考解法1234567class Solution {public: vector<int> sortArrayByParity(vector<int>& A) { for(int l = 0, r = 0; r < A.size(); ++r) if(!(A[r] % 2)) swap(A[l++], A[r]); return A; }};

題目： LeetCode - 143. Reorder List 題目說明給一個 List，依照題目的要求重新排序。※ 題目規定不能改變 node 的值。 解題思路我們先取得中間的節點 ( 方法可以參考本篇文章：LeetCode - 876 解題紀錄 )，接著將中間到尾端的節點反轉，最後依照要求重新連接即可。 參考解法12345678910111213141516171819202122232425262728293031323334353637class Solution {public: void reorderList(ListNode* head) { if(!head) return; auto mid = findMid(head), l1 = head, l2 = mid->next; mid->next = nullptr; l2 = _reverse(l2); while(l1 && l2) { au ...

題目： LeetCode - 824. Goat Latin 題目說明給一個字串，將字串中的每個單詞拆開並根據題目的規則修改單詞的內容。規則如下： 若是單詞的開頭為母音則在單詞的結尾加上 "ma"。 若是單詞的開頭不為母音則將單詞的開頭移到單詞的結尾並加上 "ma"。 在第一個單詞的結尾加上 'a'，第二的單詞的結尾加上 "aa"…。 解題思路題目的三個規則可以簡化成兩個步驟： 若是單詞的開頭不為母音則將單詞的開頭移到單詞的結尾。 在單詞的結尾加上 "ma" 及對應數量的 'a'。 定義一個 String _append 作為每次都必須加上的結尾，使用 StringStream 將字串的單詞拆開，每次先判斷單詞的開頭是否不為母音，若是的話就將開頭移到結尾，最後加上 _append 及更新 _append 即可。 參考解法123456789101112131415class Solution {public: string toGoatLatin(str ...

題目： LeetCode - 967. Numbers With Same Consecutive Differences 題目說明給兩個整數，N 代表位數，K 代表兩個數字的差，求為 N 位數且鄰近兩個數值的差為 K 的所有數。 解題思路當我們要在一個數後面添加一位數字時，那個數字一定是原本數的最後一位數加 K 或減 K，依照此想法使用遞迴填完數字即可。需要注意的是當 N 為 1 時答案為 {0, 1, 2, ..., 9}，所以需要放入 0。而當 K 為 0 時，l + k 會等於 l - k，所以要排除避免出現兩個相同的數字。 參考解法1234567891011121314151617class Solution {public: vector<int> numsSameConsecDiff(int N, int K) { vector<int> v; if(N == 1) v.emplace_back(0); for(int i = 1; i <= 9; + ...

題目： LeetCode - 1103. Distribute Candies to People 題目說明給兩個整數，candies 表示糖果的數量，num_people 表示糖果要分給的人數。分糖果的規則為 12345678910num_people = 4candies = 40 i: 0 1 2 3people: 1 2 3 4----------------------round 1 1 2 3 4 每個人分到的糖果數： i + 1 + 0 * num_peopleround 2 5 6 7 8 每個人分到的糖果數： i + 1 + 1 * num_peopleround 3 4 每個人分到的糖果數： i + 1 + 2 * num_people 當糖果數量不夠時就全部給當前的那個人即可---------------------- 10 8 10 12 回傳一個代表每個人收到糖果數量的陣列。 解題思路可以直接模擬每次發放糖果的情況，但是效率較低，我們 ...

題目： LeetCode - 123. Best Time to Buy and Sell Stock III 題目說明給一個陣列代表每日的股票價格，求買賣兩次後的最高收益。當手上有一支股票時就無法買第二支股票。 解題思路動態規劃，轉移方程為： 1234cost1 = min(p, cost1);profit1 = max(p - cost1, profit1);cost2 = min(p - profit1, cost2);profit2 = max(p - cost2, profit2); 將 profit1 的收益與 cost2 結合，profit2 即為最後的總收益， 參考解法123456789101112131415class Solution {public: int maxProfit(vector<int>& prices) { int cost1 = INT_MAX, cost2 = INT_MAX; int profit1 = 0, profit2 = 0; for(aut ...

題目： LeetCode - 5. Longest Palindromic Substring 題目說明給一個字串，求此字串最長的回文子字串。 解題思路回文的形式有兩種，一種是奇數個數，一種是偶數個數，所以我們使用一個迴圈遍歷 s，嘗試將字串中的每個端點當作回文的中間並找出回文的長度，找出最長的長度並記錄起始點即可。 參考解法12345678910111213141516171819202122class Solution {public: string longestPalindrome(string s) { _s = s, n = s.size(); int len = INT_MIN, start, curLen; for(int i = 0; i < n; ++i) { curLen = max(getLength(i, i), getLength(i, i + 1)); if(curLen > len) len = curL ...

題目： LeetCode - 435. Non-overlapping Intervals 題目說明給一個二維陣列代表區間，求需要刪除多少個區間使得區間中沒有交集。( 需要刪除最少的區間 ) 解題思路為了方便計算，我們先將區間依照右端點以小到大排序。接著選定一個區間，然後計算右邊的區間和目前區間交集的個數，這些都是需要刪除的區間，接著將目前區間換成目前找到不交集的區間，重複做此步驟即可。 參考解法12345678910111213141516class Solution { static bool cmp(const vector<int>& l, const vector<int>& r) { return l[1] < r[1]; }public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { int count = 0, n = intervals.size() ...

題目： LeetCode - 409. Longest Palindrome 題目說明給一個字串，求字串中的所有字元能組成的最大回文長度。 解題思路回文的形式有兩種，一種是奇數個數，一種是偶數個數，而奇數個數的形式就是偶數個數加上任意一個字元，所以我們先計算每個字元出現的次數，再判斷所有字元裡面是否有出現奇數個數的次數，最後將次數加入長度即可。 參考解法12345678910class Solution {public: int longestPalindrome(string s) { int l = 0, odd = 0; unordered_map<char, int> _m; for(auto c : s) ++_m[c]; for(auto m : _m) { if(m.second % 2) odd = 1; l += m.second / 2 * 2; } return l + odd; }};