Re: [閒聊] 每日leetcode
3025. Find the Number of Ways to Place People I
思路:
按照x由小到大排序points
如果x一樣大就將y較大的排在前面
接著開始檢查所有pair
預設points[i]是左上點, 從j=i+1開始檢查右下點
因為排序過的關係, 所以points[j]一定比points[i]還要右邊
那就只要檢查y, 令top = points[i][1]
令bottom為前一個能構成pair的points[j][1]
points[j][1]不能超過top, 也不能小於bottom
這樣就能得到答案了
golang :
func numberOfPairs(points [][]int) int {
slices.SortFunc(points, func(i, j []int) int {
if i[0] == j[0] {
return j[1] - i[1]
}
return i[0] - j[0]
})
n, ans := len(points), 0
for i := 0; i < n; i++ {
top := points[i][1]
bottom := math.MinInt64
for j := i + 1; j < n; j++ {
if points[j][1] <= top && points[j][1] > bottom {
ans++
bottom =points[j][1]
if points[j][1] == top{
break
}
}
}
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1756831559.A.EDC.html
推
09/03 00:52,
3月前
, 1F
09/03 00:52, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1512 之 1548 篇)：