# 查看完整版本 : LeetCode

fx360bx 2016-1-27 12:35 AM

[quote]原帖由 [i]darigold[/i] 於 2015-10-22 10:16 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=428390073&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
LeetCode OJ - Gas Station [/quote]

[url=https://leetcode.com/discuss/81890/8ms-simple-o-n-c-solution]https://leetcode.com/discuss/81890/8ms-simple-o-n-c-solution[/url]

darigold 2016-1-27 03:08 AM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-27 12:35 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434778285&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
[url=https://leetcode.com/discuss/81890/8ms-simple-o-n-c-solution]https://leetcode.com/discuss/81890/8ms-simple-o-n-c-solution[/url]

[/quote]

public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
1:     int idx = -1, total = 0, maxn = -1;
2:     for(int i = cost.size()-1; i >= 0; --i)
3:     {
4:         total += gas[i] - cost[i];
5:         if(total > maxn)
6:         {
7:             idx = i;
8:             maxn = total;
9:         }
10:    }
}
};[/code]Line 1 會execute幾次？
Line 2 會execute幾次？
...

fx360bx 2016-1-27 02:44 PM

[quote]原帖由 [i]darigold[/i] 於 2016-1-27 03:08 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434782494&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

public:
int canCompleteCircuit(vector& gas, vector& cost) {
1:     int idx = -1, total = 0, maxn = -1;
2:     f ... [/quote]

Circular route + unknown station start 唔係應該需要多啲 loops 去計多個 totals 嗎？

darigold 2016-1-27 03:15 PM

reverse engineering比engineering 難，這點和其它工程很不一樣，起樓難，但係拆樓容易。compile code容易，但係反compile很難。

BTW，你quote既呢個答案做得比我好，想法很巧妙，被個贊佢。

fx360bx 2016-1-27 05:20 PM

[quote]原帖由 [i]darigold[/i] 於 2016-1-27 03:15 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434811129&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

reverse engineering比engineering 難，這點和其它工程很不一樣，起樓難，但係拆樓容易。compile code ... [/quote]

[url=https://leetcode.com/discuss/69335/my-one-pass-solution]https://leetcode.com/discuss/69335/my-one-pass-solution[/url]

0 1 2 3 4

fx360bx 2016-1-27 08:21 PM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-27 05:20 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434818443&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[url=https://leetcode.com/discuss/69335/my-one-pass-solution]https://leetcode.com/discuss/69335/my-one-pass-solution[/url]

0 1 2 3 4

darigold 2016-1-28 02:12 AM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-27 08:21 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434828235&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[/quote]

public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
1:     int idx = -1, total = 0, maxn = -1;
2:     for(int i = cost.size()-1; i >= 0; --i)
3:     {
4:         total += gas - cost;
5:         if(total > maxn)
6:         {
7:             idx = i;
8:             maxn = total;
9:         }
10:    }
}
};[/code]上個post已經提到關鍵問題係total和maxn到底代表乜？既然你諗唔到(well，希望你係有去諗但係諗唔到)，咁我就解釋一下吧。

gas[4]的定義係第五號站有幾多gas攞，cost[4]係由第五號站去第一號站要用幾多油，所以

[b]total = gas[4] - cost[4] 就係由第五號站開始出發，到第一號站剩低既油，當然，有可能係負數。[/b]

[b]total = gas[3] - cost[3] + gas[4] - cost[4] 就係由第四號站開始出發，到第一號站剩低既油，當然，有可能係負數。[/b]

start from 最大既話，成功機會最大。

[b]關鍵就係唔駛loop! 同prefix sum既idea一樣，可以用減法。[/b]

= total_max + sum(i = 0 to k-2) [gas[i] - cost[i]]
= total_max + sum(i = 0 to 4) [gas[i] - cost[i]] - sum(i = k - 1 to 5) [gas[i] - cost[i]]
= total_max + full_total - total[k - 1][/code]呢個最終expression一定>= 0，我們知道full_total >= 0，total_max - total at anywhere 都 >= 0，所以整體係>= 0

To be fair，你搵到既呢個solution係人地引以為豪，最快既solution，又冇寫諗法出黎，reverse engineer番佢既諗法係好困難既。

[[i] 本帖最後由 darigold 於 2016-1-28 02:40 AM 編輯 [/i]]

fx360bx 2016-1-28 02:29 PM

[quote]原帖由 darigold 於 2016-1-28 02:12 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434845240&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

Thank you 師兄用左咁長時間打解釋~ :handshake:smile_o12::smile_o09:

[[i] 本帖最後由 fx360bx 於 2016-1-28 02:35 PM 編輯 [/i]]

darigold 2016-1-28 03:19 PM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-28 02:29 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434871755&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
Thank you 師兄用左咁長時間打解釋~ :handshake:smile_o12::smile_o09:
[/quote]

[quote]

[/quote]

[quote]

[/quote]

[quote]

[/quote]

[url=http://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/]http://www.geeksforgeeks.org/dynamic-programming-set-11-egg-dropping-puzzle/[/url]

[quote]
The solution is guaranteed to be unique
[/quote]

[[i] 本帖最後由 darigold 於 2016-1-28 03:20 PM 編輯 [/i]]

fx360bx 2016-1-28 03:26 PM

[quote]原帖由 [i]darigold[/i] 於 2016-1-28 03:19 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434874805&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[quote]Given a singly linked list, determine if it is a palindrome.[/quote]

[[i] 本帖最後由 fx360bx 於 2016-1-28 03:30 PM 編輯 [/i]]

darigold 2016-1-28 03:33 PM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-28 03:26 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434875229&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

fx360bx 2016-1-28 03:38 PM

[quote]原帖由 [i]darigold[/i] 於 2016-1-28 03:33 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434875647&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

I see~

O(1) space 仲要同 list 既長度冇關係，真心難做到…:smile_27:

[[i] 本帖最後由 fx360bx 於 2016-1-28 03:41 PM 編輯 [/i]]

darigold 2016-1-28 10:51 PM

O(n) time O(n) space 做到未？

O(1) space 俾個提示你。

fx360bx 2016-1-28 10:56 PM

[quote]原帖由 [i]darigold[/i] 於 2016-1-28 10:51 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434901011&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
O(n) time O(n) space 做到未？

O(1) space 俾個提示你。

darigold 2016-1-28 11:38 PM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-28 10:56 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434901289&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[/quote]

fx360bx 2016-1-28 11:41 PM

fx360bx 2016-1-29 12:00 AM

darigold 2016-1-29 12:02 AM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-28 11:41 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434904271&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

post code 啦

fx360bx 2016-1-29 12:07 AM

[quote]原帖由 [i]darigold[/i] 於 2016-1-29 12:02 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434905560&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

post code 啦

[url=http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-palindr]http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-palindr[/url] ... [/quote]

import java.util.List;

public class Solution {

while (node!=null) {
node = node.next;
}

for (int i=0; i<list.size()/2; i++) {
if (!list.get(i).equals(list.get(list.size()-i-1))) {
return false;
}
}

return true;
}
}[/code]Btw，呢個 LeetCode 網都幾 discouraging，下下都話 Time Limit Exceeded，根本就唔知岩定錯，只係知過左時。唔接受 naïve code 就咪標籤 Easy 啦嘛~ :L:smile_42::@

[[i] 本帖最後由 fx360bx 於 2016-1-29 01:21 AM 編輯 [/i]]

darigold 2016-1-29 01:33 AM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-29 12:07 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434905882&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[/quote]

[url=https://github.com/Microsoft/ChakraCore/blob/master/lib/Runtime/ByteCode/ByteCodeGenerator.cpp]https://github.com/Microsoft/ChakraCore/blob/master/lib/Runtime/ByteCode/ByteCodeGenerator.cpp[/url]

[url=https://github.com/cshung/coreclr/blob/master/src/gc/gc.cpp]https://github.com/cshung/coreclr/blob/master/src/gc/gc.cpp[/url]

[quote] [i]fx360bx[/i]  2016-1-29 12:07 AM o [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434905882&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
Btw，呢個 LeetCode 網都幾 discouraging，下下都話 Time Limit Exceeded，根本就唔知岩定錯，只係知過左時。唔接受 naïve code 就咪標籤 Easy 啦嘛~
[/quote]

[url=https://www.codewars.com/]https://www.codewars.com/[/url]

[url=http://www.spoj.com/problems/PRIME1/]http://www.spoj.com/problems/PRIME1/[/url]

[[i] 本帖最後由 darigold 於 2016-1-29 01:45 AM 編輯 [/i]]

fx360bx 2016-1-29 01:53 AM

[quote]原帖由 [i]darigold[/i] 於 2016-1-29 01:33 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434909398&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[url=https://github.com/Microsoft/ChakraCore/blob/master/lib/Runtime/ByteCode/ByteCodeGenerator.cpp]https://github.com/Microsoft/ChakraCore/blob/master/lib/Runtime/ByteCode/ByteCodeGenerator.cpp[/url]

fx360bx 2016-1-29 02:07 AM

darigold 2016-1-29 05:04 AM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-29 01:53 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434909858&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[/quote]

[url=https://careers.microsoft.com/jobdetails.aspx?ss&pg=0&so&rw=1&jid=195917&jlang=EN&pp=SS]https://careers.microsoft.com/jobdetails.aspx?ss&pg=0&so&rw=1&jid=195917&jlang=EN&pp=SS[/url]

[quote]

[/quote]

Nike廣告也說，impossible is nothing。

[[i] 本帖最後由 darigold 於 2016-1-29 02:45 PM 編輯 [/i]]

stupidsing 2016-1-29 07:19 AM

clr 個 garbage collector!?

Susan﹏汪汪 2016-1-29 10:09 AM

[quote]原帖由 [i]stupidsing[/i] 於 2016-1-29 07:19 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434914022&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
clr 個 garbage collector!?

darigold 2016-1-29 01:37 PM

[quote]原帖由 [i]stupidsing[/i] 於 2016-1-29 07:19 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434914022&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
clr 個 garbage collector!?

[/quote]

fx360bx 2016-1-29 01:41 PM

[quote]原帖由 [i]darigold[/i] 於 2016-1-29 05:04 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434912585&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[url=https://careers.microsoft.com/jobdetails.aspx?ss&pg=0&so&rw=1&jid=195917&jlang=EN&pp=SS]https://careers.microsoft.com/jobdetails.aspx?ss&pg=0&so&rw=1&jid=195917&jlang=EN&pp=SS[/url]

fx360bx 2016-1-29 01:44 PM

[quote]原帖由 [i]darigold[/i] 於 2016-1-29 01:37 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434932266&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

[[i] 本帖最後由 fx360bx 於 2016-1-29 01:49 PM 編輯 [/i]]

Susan﹏汪汪 2016-1-29 02:03 PM

[quote]原帖由 [i]fx360bx[/i] 於 2016-1-29 01:41 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434932502&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

arithmetic: [url=https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/Arithmetic.swift]https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/Arithmetic.swift[/url]
FFT: [url=https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/CooleyTukey.swift]https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/CooleyTukey.swift[/url]
convolution:
1. [url=https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/CircularConvolve.swift]https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/CircularConvolve.swift[/url]
2. [url=https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/DiscreteConvolve.swift]https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/DiscreteConvolve.swift[/url]

Fourier: [url=https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Fourier.swift]https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Fourier.swift[/url]
Polynomial: [url=https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Maths/Polynomial.swift]https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Maths/Polynomial.swift[/url]
Geometry: [url=https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Maths/Geometry.swift]https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Maths/Geometry.swift[/url]

fx360bx 2016-1-29 02:07 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2016-1-29 02:03 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=434933542&ptid=24497948][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

arithmetic: [url=https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/Arithmetic.swift]https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/Arithmetic.swift[/url]
FFT: [url=https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/CooleyTukey.swift]https://github.com/SusanDoggie/Doggie/blob/master/Doggie/Accelerate/CooleyTukey.swift[/url]
co ... [/quote]