[閒聊] Leetcode 2130已回收
Leetcode 75 裡面其中一題
https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/
剛開始我猜大概很簡單的把東西全塞進vector大概也能過
但是八成是要你用fast / slow pointer去找中間
最好是能one pass解
-----
# 解1:
用fast/slow pointer找到中間，同時把前半的list內容塞進vector裡面
再從中間開始一路找到最後面，跟vector裡的內容加起來找max。
class Solution {
public:
int pairSum(ListNode* head) {
vector<int> sum;
ListNode *fast = head, *slow = head;
int output = 0;
while (fast) {
sum.push_back(slow->val);
fast = fast->next->next;
slow = slow->next;
}
size_t n = sum.size() * 2;
size_t i = sum.size();
while (slow) {
output = max(output, sum[n-1-i] + slow->val);
i++;
slow = slow->next;
}
return output;
}
};
但是我想不太到怎摸做才能空間複雜度O(1)
直到我偷看其他人做法
-----
# 解2:
一樣用fast/slow pointer找到中間
然後直接把linked list破壞，把list後半直接倒過來
再重新跑一遍linked list的一半找max
確實input不管怎摸搞，最後都不會是我管記憶體leak
所以我指標愛怎摸插就怎摸插
但是 姆咪
int pairSum(ListNode* head) {
ListNode *fast = head->next, *slow = head;
int output = 0;
while (fast->next) {
fast = fast->next->next;
slow = slow->next;
}
ListNode *next = nullptr, *prev = nullptr;
slow = slow->next;
while (slow) {
next = slow->next;
slow->next = prev;
prev = slow;
slow = next;
}
while (prev) {
output = max(output, head->val + prev->val);
head = head->next;
prev = prev->next;
}
return output;
}
-----
# 解3:
我又去試了最簡單的搞法
還真的過了 = =
速度跟解2搞不好有得比，因為vector可以先cache起來之類我猜
--
neuenmuller@atelier:home$ touch plachta
touch: cannot touch 'plachta': Permission denied
neuenmuller@atelier:home$ sudo touch plachta
[sudo] password for neuenmuller:
neuenmuller is not in the sudoers file. This incident will be reported.
neuenmuller@atelier:home$
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 97.99.29.95 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698889632.A.60B.html
推
11/02 09:53,
2年前
, 1F
11/02 09:53, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：