[Leetcode解題] 391. Perfect Rectangle
題目
391. Perfect Rectangle
給定一組 axis-aligned（軸對齊）矩形，每個矩形由 [x1, y1, x2, y2] 定義其左下角和右上角座標。請判斷這些矩形是否能完美拼成一個沒有重疊、沒有缺口的矩形區域。
每個矩形都用 rectangles[i] = [xi, yi, ai, bi] 表示，底部左側是 (xi, yi)，右上角是 (ai, bi)。
[Leetcode解題] 2818. Apply Operations to Maximize Score
題目
2818. Apply Operations to Maximize Score
你有一個長度為 n 的正整數陣列 nums，以及一個整數 k。
你初始分數為 1，可以最多進行 k 次以下操作來最大化你的分數：
- 選擇一段未被選過的子陣列
nums[l, ..., r]。 - 在這段子陣列中，選擇一個具有「最高質因數個數 (prime score)」的元素
x：- 若有多個數有同樣的質因數個數，選擇最左邊的那一個。
- 將當前分數乘上
x。
質因數個數的定義：一個整數有多少不同的質因數。 例如：300 = 2² × 3 × 5²，因此它的質因數個數是 3（分別為 2, 3, 5）。
請回傳最大可能的分數，結果請對 10^9 + 7 取模。
[Leetcode解題] 1028. Recover a Tree From Preorder Traversal
題目
1028. Recover a Tree From Preorder Traversal
這題給定一個preorder DFS的樹，以字串表達，並且以dash('-') 表達深度，求我們還原成用資料結構表示的樹
[Leetcode解題] 2872. Maximum Number of K-Divisible Components
題目
2872. Maximum Number of K-Divisible Components
這題給定一棵樹，包含從0到n-1的點，另外給定一個矩陣edges表示相連的點，以及一個values表示各點上的值。
題目另外給定一個數k，求我們最多可以把這棵樹切成幾個connected graph，並且每個graph上點的值(values)和可以被k整除。
這題題目較難理解，可以搭配題目網址的圖看。
[Leetcode解題] 2458. Height of Binary Tree After Subtree Removal Queries
題目
2458. Height of Binary Tree After Subtree Removal Queries
給一個Binary Tree，以及一串Queries，Queries表示要移除的點，此題要回傳移除該點後該樹的高度(heights)為多少，並且每個Query之間是獨立的。
[Leetcode解題] 1106. Parsing A Boolean Expression
1106. Parsing A Boolean Expression
題目
1106. Parsing A Boolean Expression
這題我們給一個boolean expression，然後要判斷最後的結果，有可能的operation有!, &, |，這邊題目給的字串一定符合規則。
[Leetcode解題] 10. Regular Expression Matching - DP解
題目說明
10. Regular Expression Matching
給定一個輸入字串 s 和一個模式 p，實作正則表達式匹配，支援以下兩種特殊符號：
.可以匹配任意單一字元。*可以匹配零個或多個它前一個字元。
匹配必須覆蓋整個輸入字串，不能只匹配部分字串。
[Leetcode解題] 2751. Robot Collisions - 使用stack解
題目
有n個機器人，每個機器人都有其位置、健康值和移動方向。
給定三個0索引的整數數組：positions（位置）、healths（健康值），以及一個字符串directions（directions[i] 可能是 ‘L’ 表示向左，或是 ‘R’ 表示向右）。所有positions中的整數是唯一的。
所有機器人會同時開始以相同的速度沿著他們給定的方向移動。如果兩個機器人在移動過程中碰撞到同一個位置，他們就會發生碰撞。
如果兩個機器人發生碰撞，健康值較低的機器人會被移除，而另一個機器人的健康值會減少1。存活的機器人繼續沿著它原本的方向移動。如果兩個機器人的健康值相同，那麼它們都會被移除。
求存活下來的機器人的健康值（按照原本給定的順序）
解題思路
- 初始化與排序：
我們需要對機器人的位置做排序以便移動機器人，並且需要存下索引來拿到健康值跟移動方向。
首先，將每個機器人的索引和位置結合成元組，並將這些元組放入一個列表 pos_w_idx中。
根據機器人的位置對pos_w_idx進行排序，以便按位置模擬機器人的移動。
- 模擬移動與碰撞：
使用一個stack來處理碰撞情況，棧中存放的是向右移動（’R’）的機器人索引。
遍歷排序後的機器人列表 pos_w_idx，根據機器人的方向進行處理：
如果機器人向右移動（’R’），將其索引推入stack中。
如果機器人向左移動（’L’），需要檢查棧頂stack.top()的機器人是否會發生碰撞。
- 處理碰撞邏輯：
我們發現，只有當一個左邊的機器人向右，另一個右邊的機器人向左的時候才會發生碰撞。
如果棧頂機器人的健康值大於當前機器人的健康值，則當前機器人被移除，棧頂機器人的健康值減少1。
如果棧頂機器人的健康值小於當前機器人的健康值，則棧頂機器人被移除，當前機器人的健康值減少1並繼續進行碰撞檢查。
如果棧頂機器人的健康值等於當前機器人的健康值，則兩者都被移除。
- 收集結果：
在處理完所有機器人後，檢查健康值數組 healths，將健康值不為零的機器人健康值加入結果列表ans中。
返回結果列表ans，即最終存活的機器人的健康值。
程式碼
class Solution(object):
def survivedRobotsHealths(self, positions, healths, directions):
"""
:type positions: List[int]
:type healths: List[int]
:type directions: str
:rtype: List[int]
"""
pos_w_idx = []
for idx, position in enumerate(positions):
pos_w_idx.append((idx, position))
pos_w_idx = sorted(pos_w_idx, key=lambda x: x[1])
stack = []
for idx, pos in pos_w_idx:
if directions[idx] == 'R':
stack.append(idx)
continue
if directions[idx] == 'L':
while stack:
if healths[stack[-1]] > healths[idx]:
# Collision, R wins
healths[idx] = 0
healths[stack[-1]] -= 1
break
elif healths[stack[-1]] < healths[idx]:
# Collision, L wins
healths[idx] -= 1
healths[stack[-1]] = 0
stack.pop()
else:
# Collision, tie
healths[idx] = 0
healths[stack[-1]] = 0
stack.pop()
break
ans = []
for health in healths:
if health:
ans.append(health)
return ans
時間複雜度
Bottleneck在於做排序的部分，所以時間複雜度為$O(nlogn)$
[Leetcode解題] 84. Largest Rectangle in Histogram - monotonic-stack解
84. Largest Rectangle in Histogram
題目
84. Largest Rectangle in Histogram
給定一個由整數組成的數組 heights，這個數組代表直方圖的柱子高度，其中每個柱子的寬度為 1。請返回直方圖中最大矩形的面積。
[Leetcode解題] 514. Freedom Trail - 用DP結合BFS解
514. Freedom Trail
題目
給定一個圓形的轉盤，上面有N個英文字母，中間有一個按鈕可以輸入該字母，每往右或往左轉動一個字母，計算為一步，按下按鈕也計算為一步。
當給定一個字串key，題目問要經過多少步才能輸入完整個字串。
[Leetcode解題] 992. Subarrays with K Different Integers
題目
992. Subarrays with K Different Integers 給定一個整數陣列nums和一個整數k，返回nums中好的子陣列的數量。
好的陣列是一個陣列，其中不同整數的數量正好是k。
例如，[1,2,3,1,2]有3個不同的整數：1、2和3。 子陣列是陣列的連續部分。
[Leetcode解題] 41. First Missing Positive
題目：
41. First Missing Positive 給定一個未排序的整數陣列 nums。返回未出現在 nums 中的最小正整數。
你必須實現一個時間複雜度為 $O(n)$，額外空間複雜度為 $O(1)$ 的算法。
[Leetcode解題] 295. Find Median from Data Stream - 使用heap解
題目
295. Find Median from Data Stream 中位數是排序整數列表中的中間值。如果列表的大小是偶數，則沒有中間值，中位數是兩個中間值的平均值。
例如，對於 arr = [2,3,4]，中位數為 3。 例如，對於 arr = [2,3]，中位數為 (2 + 3) / 2 = 2.5。
實現 class MedianFinder：
MedianFinder(): 初始化 MedianFinder。
void addNum(int num): 將整數 num 從資料流添加到資料結構中。
double findMedian(): 返回到目前為止所有元素的中位數。
[Leetcode解題] 140. Word Break II
140. Word Break II
題目
給一個字串以及一個詞表（一個包含單詞的矩陣），求該字串是否能被以詞表內的單字切分，並返回所有的可能，單字可以被重複利用。
[Leetcode解題] 2009. Minimum Number of Operations to Make Array Continuous - 使用 Binary Search 算法
題目
2009. Minimum Number of Operations to Make Array Continuous 給定一個整數陣列 nums。在一次操作中，你可以將 nums 中的任何元素替換為任何整數。 如果滿足以下兩個條件，則 nums 被認為是連續的：
nums 中的所有元素都是唯一的。 nums 中的最大元素與最小元素之間的差等於 nums.length - 1。 例如，nums = [4, 2, 5, 3] 是連續的，但 nums = [1, 22, 22, 24, 24] 不是連續的。
返回使 nums 變得連續所需的最小操作次數。
[Leetcode解題] 127. Word Ladder - BFS解
題目
127. Word Ladder 給定兩個單字 beginWord 和 endWord，以及一個字典 wordList，其中包含了許多單字。請找出從 beginWord 到 endWord 的最短轉換序列的長度，轉換規則如下：
- 每個相鄰的單字之間只能相差一個字母。
- 轉換序列中的每個單字都必須在 wordList 中，但 beginWord 不一定需要在 wordList 中。
- 最後一個單字必須是 endWord。 如果無法找到這樣的轉換序列，則返回 0。
[Leetcode解題] Median of Two Sorted Arrays - 使用分治法(Divide-and-conquer)算法
題目
4. Median of Two Sorted Arrays 兩個已排序陣列的中位數
給定兩個大小分別為 $m$ 和 $n$ 的已排序陣列 $nums1$ 和 $nums2$，找出這兩個陣列的中位數。
整體運行時間複雜度應為 $O(log(m+n))$。
[Leetcode解題] Text Justification - greedy解
題目
68. Text Justification 這是一道文本格式化的題目。給定一個字符串數組 words 和一個寬度 maxWidth，要求將文本格式化為每一行的寬度正好為 maxWidth 且完全（左右）對齊。
題目要求應該採用貪婪策略將您的文字打包，即在每一行中打包盡可能多的文字。必要時填充額外的空格’‘，使每一行的寬度正好為 maxWidth。
文字之間的額外空格應盡可能均勻分配。如果一行上的空格數不均勻分配在文字之間，左邊的空槽將分配更多的空格，而右邊的空槽分配的空格較少。
最後一行的文本應左對齊，並且在文字之間不插入額外空格。