→ SecondRun: 大師 01/23 22:44
推 JerryChungYC: 你的每日怎麼跟我的不一樣 01/24 07:04
https://leetcode.com/problems/maximum-length-of-pair-chain
646. Maximum Length of Pair Chain
你被給予一個包含n對配對的數組，其中每一對配對pairs[i]由兩個元素lefti和righti組
成，並且lefti小於righti。
一對配對p2 = [c, d]可以跟在一對配對p1 = [a, b]之後，如果b小於c。這樣就可以形成
一個配對的鏈。
你需要返回可以形成的最長鏈的長度
思路:
先將pairs進行排列，之後從最小的pair為起點，逐個比較。
假如最小pair[1] < 當前pair[0]
則鏈長度+1 當前pair變成新的最小pair 繼續進行比較
Python code:
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort(key=lambda x: x[1])
n = 1
prev = pairs[0]
for cur in pairs[1:]:
if prev[1] < cur[0]:
n += 1
prev = cur
return n
看解答才想出來 姆咪
其實思路差不多
我是用prev[1] >= cur[0]當條件
但怎麼改都有問題
後來改成這樣就過了
不過prev[1] >= cur[0]跟prev[1] < cur[0]等價才對
應該有解法吧 再想想
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.137.25 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706020323.A.5B8.html