Re: [閒聊] 每日leetcode

看板Marginalman作者sustainer123 (caster )時間1年前 (2024/07/05 10:55)推噓2(2推 0噓 2→)

留言4則, 3人參與討論串448/1554 (看更多)

※ 引述《smart0eddie (smart0eddie)》之銘言： : 2024-07-05 : 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points : A critical point in a linked list is defined as either a local maxima or a : local minima. : A node is a local maxima if the current node has a value strictly greater : than the previous node and the next node. : A node is a local minima if the current node has a value strictly smaller : than the previous node and the next node. : Note that a node can only be a local maxima/minima if there exists both a : previous node and a next node. : Given a linked list head, return an array of length 2 containing : [minDistance, maxDistance] where minDistance is the minimum distance between : any two distinct critical points and maxDistance is the maximum distance : between any two distinct critical points. If there are fewer than two : critical points, return [-1, -1]. : 因為是 LL 好像不能幹嘛 : 只能乖乖走 : 程式會分兩階段 : 第一個部分先紀錄符合條件的 node index : 第二個部分算所有 index 之間的 min distance : max dist 直接是 index 最後減最前 : 我應該是少做 early return : 還有多做 function 去判斷 critical point : 時間大概是 100% 的兩倍 : /** : * Definition for singly-linked list. : * struct ListNode { : * int val; : * ListNode *next; : * ListNode() : val(0), next(nullptr) {} : * ListNode(int x) : val(x), next(nullptr) {} : * ListNode(int x, ListNode *next) : val(x), next(next) {} : * }; : */ : class Solution { : public: : vector<int> nodesBetweenCriticalPoints(ListNode* head) { : vector<int> ans(2, -1); : vector<int> idx; : int i = 1; : while (head->next && head->next->next) { : if (isCritical(head)) { : idx.push_back(i); : } : head = head->next; : i++; : } : if (idx.size() >= 2) { : ans[1] = idx.back() - idx.front(); : ans[0] = idx[1] - idx[0]; : for (int i = 2; i < idx.size(); i++) { : if (idx[i] - idx[i-1] < ans[0]) { : ans[0] = idx[i] - idx[i-1]; : } : } : } : return ans; : } : private: : bool isCritical(ListNode* node) { : if (node->val < node->next->val && node->next->val > : node->next->next->val) { : return true; : } : if (node->val > node->next->val && node->next->val < : node->next->next->val) { : return true; : } : return false; : } : }; 思路: 差不多就分成兩步找區域最大值與區域最小值找最短距離不過應該能在找點的同時找最短距離不過我懶得想了姆咪 Python Code: # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]: record = [] pre = head.val head = head.next post = 0 count = 1 while head and head.next: post = head.next.val if head.val > pre and head.val > post: record.append(count) if head.val < pre and head.val < post: record.append(count) pre = head.val count += 1 head = head.next min_distance = float('inf') if len(record) < 2: return [-1,-1] for i in range(1,len(record)): min_distance = min(record[i]-record[i-1],min_distance) return (min_distance,record[-1]-record[0]) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720148118.A.C2A.html

推

JIWP

07/05 10:56, 1年前 , 1^F

07/05 10:56, 1^F

推

smart0eddie

07/05 11:37, 1年前 , 2^F

07/05 11:37, 2^F

→

smart0eddie

07/05 11:37, 1年前 , 3^F

07/05 11:37, 3^F