45. Jump Game II
題目網址：https://leetcode.cn/problems/jump-game-ii/
題意：給一非負整數 array nums, 你最初位於 nums 的第一個位置。
nums 中的每個元素代表你在該位置可以跳躍的最大長度。
假設你總是可以到達 nums 的最後一個位置。
返回到達 nums 的最後一個位置所需的最少的跳躍次數。
Solution：
想法：利用 Greedy, 用 [start, end] 來記錄每次跳躍的區間, 而 maxPos 則是用來紀錄 [start, end] 中所能跳躍的最遠 index。若 end ≥ nums.size() - 1 代表上一次跳躍已能抵達 nums 的終點, 因此結束循環
class Solution {public: int jump(vector<int>& nums) { int maxPos = 0; // 所能跳躍的最遠 index int start = 0, end = 0, res = 0; // 起始區間 [start, en ...
134. Gas Station
題目網址：https://leetcode.cn/problems/gas-station/
題意：在一條環路上有 n 個加油站, 其中第 i 個加油站有汽油 gas[i] 升。
你有一輛油箱容量無限的的汽車, 從第 i 個加油站開往第 i + 1 個加油站需要消耗 cost[i] 升汽油。你從其中的一個加油站出發, 開始時油箱為空。
給定兩個整數 array gas 和 cost, 如果可以繞環路行駛一圈, 則返回出發時加油站的 index, 否則返回 -1。如果存在解, 則保證它是唯一的。
Solution：
想法：利用 Greedy, 首先判斷總油量是否小於總消耗量。如果是, 那肯定不能走完一圈。否則, 肯定能走完一圈。接下來就是遍歷 nums, 從第一站開始, 計算每一站剩餘的油量, 如果當走到第 i 站時油量為負, 則以第 i + 1 站作為起點重新計算。若抵達某一站時油量為負, 說明從起點到該站中間的所有站都不能到達該點
e.g. gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] (見下圖)
假設從 i = 4 出發, 此時 ...
846. Hand of Straights
題目網址：https://leetcode.cn/problems/hand-of-straights/
題意：Alice 手中有一堆牌, 她想要重新排列這些牌, 將其分成若干組, 使每一組的牌數都是 groupSize, 並且由 groupSize 張連續的牌組成。
給一整數 array hand 和一整數 groupSize, 其中 hand[i] 代表第 i 張牌。如果她可以重新排列這些牌, 返回 true；否則, 返回 false。
Solution：
想法：利用 Greedy, 首先判斷 hand.size() 能否被 groupSize 所整除, 若不行則返回 false。否則, 用 map 統計每張牌出現的次數, 並且根據 card value 由小到大排序。每個 group 每次都先從 map 中取出最小的 card value start, 則該 group 的數字範圍為 [start, start + groupSize - 1], 只要缺少一個便直接返回 false
取出數字後, 要將其出現次數減一, 然後判斷是否為 0。若是的話, 要將其移除, 否則 st ...
1899. Merge Triplets to Form Target Triplet
題目網址：https://leetcode.cn/problems/merge-triplets-to-form-target-triplet/
題意：triplet 是由三個整數所組成的 array。給一 2D 整數 array triplets, 其中 triplets[i] = [ai, bi, ci] 表示第 i 個 triplet。並給一整數 array target = [x, y, z], 表示你想要得到的 triplet。
為了得到 target, 你需要對 triplets 進行下面的操作任意次（也可能是 0 次）：
選出兩個 index（index 從 0 開始）i 和 j（i != j）, 並更新 triplets[j] 為 [max(ai, aj), max(bi, bj), max(ci, cj)]
e.g. triplets[i] = [2, 5, 3] 且 triplets[j] = [1, 7, 5]
➔ 則 triplets[j] 將會更新為 [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5]。
若透過上述 ...
763. Partition Labels
題目網址：https://leetcode.cn/problems/partition-labels/
題意：給一 string s 由小寫字母所組成。我們要把 s 劃分為盡可能多的 partition, 同一字母只能出現在同一個 partition 中。返回一個表示每個 partition 的長度之 array。
Solution：
想法：利用 Greedy, 首先遍歷 s, 並用 lastIdx 紀錄每個字母的最後一個 index, 然後從頭開始遍歷 s, 並不斷更新當前 partition 的結尾。若 i == idx 代表已走到 partition 結尾, 即可確定當前 partition 的 size, 因為該 partition 中的 char 都沒有出現在更後面的位置
class Solution {public: vector<int> partitionLabels(string s) { const int n = s.size(); unordered_map<char, int> ...