Re: [閒聊] Leetcode 2130
※ 引述《Neuenmuller (蘇菲・諾伊恩謬拉)》之銘言：
: Leetcode 75 裡面其中一題
: https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/
: 剛開始我猜大概很簡單的把東西全塞進vector大概也能過
: 但是八成是要你用fast / slow pointer去找中間
: 最好是能one pass解
我的思路是先跑一次迴圈找數量
然後用遞迴往裡面跑
跑到中間的時候折返回來
然後就把節點跟折返節點的值加起來
例如
0-> 1-> 2-> 3-> 4-> 5↓
11<-10<- 9<- 8<- 7<- 6
雖然這樣空間複雜度是一
但是實際上堆疊用了不少的記憶體
最後時間打敗54% 空間打敗47%
完全沒有比較好
TS code:
function pairSum (head: ListNode | null): number {
let maxSum = 0
let n = 0
let node = head
while (node != null) {
n++;
node = node.next
}
const findSum = (node: ListNode, index: number): ListNode => {
if (index === n / 2 - 1) {
const returnNode = node.next
maxSum = Math.max(maxSum, node.val + returnNode.val)
return returnNode.next
}
if (index < n / 2) {
const returnNode = findSum(node.next, index + 1)
maxSum = Math.max(maxSum, node.val + returnNode.val)
return returnNode.next
}
return node.next
}
findSum(head, 0)
return maxSum
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698896158.A.785.html
→
11/02 11:56,
7月前
, 1F
11/02 11:56, 1F
→
11/02 12:29,
7月前
, 2F
11/02 12:29, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：