Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者fxfxxxfxx (愛麗絲)時間2年前 (2023/01/07 10:45)推噓3(3推 0噓 2→)

留言5則, 5人參與討論串182/719 (看更多)

134. Gas Station 如果從 i 開始，會是 (gas[i] - cost[i]) + (gas[i+1] - cost[i+1]) + ... - cost[i-1] 所以其實只需要知道兩者的差。定義 A[i] := gas[i] - cost[i], for 0 <= i < n 我們把 A 再複製一遍接在後面，也就是 A[n+i] := A[i], for 0 <= i < n 可以發現，從 i 開始能夠成功的條件是對所有 0 <= j < n，都有 A[i] + A[i+1] + ... + A[i+j] >= 0 (因為我們複製了一份在後面，像是 A[i-1] = A[n-i-1]，所以可以處理繞一圈回來的情況) 定義 prefix sum S 如下 S[0] = 0 S[i+1] = A[0] + ... A[i] 可以發現成功的條件變成對所有 0 <= j < n 都有 S[i+j+1] - S[i] = A[i] + A[i+1] + ... + A[i+j] >= 0 整理一下得到我們要對所有 0 <= j < n，都有 S[i+j+1] >= S[i] 所以我們實際上是要找一個很小的 prefix sum 考慮 S[0], ..., S[n-1] 的最小值的 index 假設是 i 好了，所以我們有 S[i] <= S[j], for 0 <= j < n 所以我們有 S[n+i] = A[0] + ... + A[n-1] + A[n] + ... + A[n+i-1] = A[0] + ... + A[n-1] + A[0] + ... + A[i-1] = S[n] + S[i] <= S[n] + S[j] 所以 S[n+i] 也是 S[n], S[n+1], ..., S[2n-1] 中的最小值接著考慮以下兩種情況若 S[n] >= 0，則 S[i] 就是 S[0], ..., S[2n-1] 中的最小值當然就一定是合法的若 S[n] < 0, 則 S[i+n] < S[i]，所以不管哪個 i 都不合法所以最後就變成 1. 如果 S[n] = A[0] + ... + A[n-1] < 0 則失敗回傳 -1 2. 否則回傳有最小 prefix sum 的 index Racket Code: --------------------------------------------------------- (define/contract (can-complete-circuit gas cost) (-> (listof exact-integer?) (listof exact-integer?) exact-integer?) (let* ([diff (map - gas cost)] [sum (foldl + 0 diff)]) (define (loop lst sm mn idx ans) (if (null? lst) ans (let* ([x (car lst)] [rs (cdr lst)] [nsm (+ sm x)] [nidx (add1 idx)] [nmn (min mn nsm)] [nans (if (<= mn nsm) ans idx)]) (loop rs nsm nmn nidx nans)))) (if (< sum 0) -1 (loop diff 0 0 1 0)))) --------------------------------------------------------- ...開玩笑的，我先寫 C++ 才拿來改的 --------------------------------------------------------- class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int n = gas.size(); int sm = 0, mn = 0, argmin = 0; for (int i = 0; i < n; i++) { sm += gas[i] - cost[i]; if (sm < mn) { mn = sm; argmin = i + 1; } } return sm < 0 ? -1 : argmin; } }; --------------------------------------------------------- -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673059540.A.18C.html

→

Jaka

01/07 10:47, 2年前 , 1^F

01/07 10:47, 1^F

推

SecondRun

01/07 10:51, 2年前 , 2^F

01/07 10:51, 2^F

推

sustainer123

01/07 10:53, 2年前 , 3^F

01/07 10:53, 3^F