查看完整版本 : 火雞

tom.care 2018-11-29 01:03 PM

火雞

*** 作者被禁止或刪除 內容自動屏蔽 ***

tom.care 2018-12-17 05:48 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

煙民母親生賤種 2018-12-18 12:29 AM

Erect the Fence  :fst_010:

我朝朝都 erect 架喎。tom care 你呢?:fst_008:

darigold 2018-12-18 11:36 AM

[code]    class Solution
    {
    public:
        vector<Point> outerTrees(vector<Point>& points)
        {
            if (points.size() < 4)
            {
                return points;
            }            
            for (int i = 1; i < points.size(); i++)
            {
                if (points[i].x < points[0].x || (points[i].x == points[0].x) && (points[i].y < points[0].y)) {
                    swap(points[i], points[0]);
                }
            }

            vector<Point> answer;
            answer.push_back(points[0]);
            while (true)
            {
                Point& basePoint = answer[answer.size() - 1];
                // In the first iteration, we know that it is impossible for the hull to end, so we pick index 1 as the candidate and start the loop from 2
                // In any other iterations, it is possible that the convex hull ends, so we use 0 as the nextIndex and loop through all the points that are not on the hull
                int nextIndex = (answer.size() == 1) ? 1 : 0;
                int start = answer.size() + nextIndex;

                for (int testIndex = start; testIndex < points.size(); testIndex++)
                {
                    Point& nextPoint = points[nextIndex];
                    Point& testPoint = points[testIndex];
                    bool take = false;
                    int cross = (nextPoint.x - basePoint.x) * (testPoint.y - basePoint.y) - (nextPoint.y - basePoint.y) * (testPoint.x - basePoint.x);
                    if (cross > 0)
                    {
                        take = true;
                    }
                    else if (cross == 0)
                    {
                        // If we found co-linear points in the set of points that are not added to the hull, they are either all added to the hull or not at all.
                        // so we picked the one with least distance to keep it in the hull order.
                        //
                        // The statement above is always true, but the co-linear points we just found might not all come from the points not added to the hull.
                        // The only special case when nextIndex = 0. In that case, we should always set take = true to ensure this point (and any other points
                        // also co-linear with points[0]) to be chosen in the hull.
                        int next_base_squared_dist = (nextPoint.x - basePoint.x) * (nextPoint.x - basePoint.x) + (nextPoint.y - basePoint.y) * (nextPoint.y - basePoint.y);
                        int test_base_squared_dist = (testPoint.x - basePoint.x) * (testPoint.x - basePoint.x) + (testPoint.y - basePoint.y) * (testPoint.y - basePoint.y);
                        if (nextIndex == 0 || next_base_squared_dist > test_base_squared_dist)
                        {
                            take = true;
                        }
                    }
                    if (take)
                    {
                        nextIndex = testIndex;
                    }
                }
                if (nextIndex == 0)
                {
                    break;
                }
                answer.push_back(points[nextIndex]);
                swap(points[answer.size() - 1], points[nextIndex]);
            }

            return answer;
        }
    };
};[/code]

tom.care 2018-12-18 03:55 PM

*** 作者被禁止或刪除 內容自動屏蔽 ***

獵頭先生 2018-12-18 04:00 PM

[quote]原帖由 [i]tom.care[/i] 於 2018-11-29 01:03 PM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=491249914&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
[url=https://leetcode.com/problems/erect-the-fence/]https://leetcode.com/problems/erect-the-fence/[/url] [/quote]
Tom.care
你好,一直留意你好耐。見你Coding 能力十分高超,我有一D Job Opportunity,你有冇興趣想知?
Please PM if you are interested.

煙民母親生賤種 2018-12-19 11:23 PM

[quote]原帖由 [i]tom.care[/i] 於 2018-12-18 03:55 PM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492155900&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

9120744 [/quote]食雞係好殘忍架!:fst_004:你無睇 Peta 既咩?:fst_016:

assembly.jc 2018-12-20 03:10 AM

用 Haskell Implements [url=https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/]"Graham Scan Algorithm"[/url],速度係 O (n log n),唔同嘅係 link 入面嘅算法會刪除同一條上面的樹,但題目要求保留,所以慳返幾行 code:

可以試下 run: [url=https://repl.it/repls/DelightfulLightheartedTriggers]https://repl.it/repls/DelightfulLightheartedTriggers[/url]

import Data.List (sortBy)

data Orientation = Coliner | Clockwise | CounterClock deriving (Show, Eq)

distance (x1, y1) (x2, y2) = (x1 - x2) ^ 2 + (y1 - y2) ^ 2

orientation (px, py) (qx, qy) (rx, ry) =
    case (qy - py) * (rx - qx) - (qx - px) * (ry - qy)
        of x | x == 0    -> Coliner
              | x >  0    -> Clockwise
              | otherwise -> CounterClock

orientOrder p0 p1 p2 =
    case orientation p0 p1 p2 of
        Clockwise    -> GT
        CounterClock -> LT
        Coliner      -> if distance p0 p1 >= distance p0 p2 then GT else LT

findLowestPoint points =
    head $ filterPoint leftmost $ filterPoint lowest points
    where lowest   ps p    = minimum (map snd ps) == snd p
          leftmost ps p    = minimum (map fst ps) == fst p
          filterPoint f ps = filter (f ps) ps

findConves stack [] = stack
findConves stack@(c:p:_) points@(n:ps)
    | orientation p c n == Clockwise = findConves (tail stack) points
    | otherwise                      = findConves (n:stack) ps

convexHull points =
    let orderedPoints = p0 : sortBy (orientOrder p0) (filter (/=p0) points)
    in  findConves (reverse $ take 3 orderedPoints) (drop 3 orderedPoints)
    where p0 = findLowestPoint points

main = mapM_ print $ convexHull [(1,1), (2,2), (2,0), (2,4), (3,3), (4,2)]

[[i] 本帖最後由 assembly.jc 於 2018-12-20 03:22 AM 編輯 [/i]]

雨中勇敢的白襪 2018-12-20 09:44 AM

大家樂外賣,...

獵頭先生 2018-12-20 11:18 AM

[quote]原帖由 [i]獵頭先生[/i] 於 2018-12-18 04:00 PM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492156138&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

Tom.care
你好,一直留意你好耐。見你Coding 能力十分高超,我有一D Job Opportunity,你有冇興趣想知?
Please PM if you are interested. [/quote]

原來我未夠50分用唔到PM功能,儲夠50分再pm.

tom.care 2018-12-21 08:14 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

assembly.jc 2018-12-22 01:34 PM

[quote]原帖由 [i]tom.care[/i] 於 2018-12-21 08:14 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492273719&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
[url=https://leetcode.com/problems/numbers-at-most-n-given-digit-set/]https://leetcode.com/problems/numbers-at-most-n-given-digit-set/[/url] [/quote]

啱啱睇緊 Haskell Memoization,以為這條題目可以應用到,原來唔需要。試 run: [url=https://repl.it/repls/ForcefulDisloyalZip]https://repl.it/repls/ForcefulDisloyalZip[/url]


countLessThan num digits =
    let nums = map (read . pure) (show num)::[Int]
        ds   = map (read . pure) digits::[Int]
    in  count nums ds + sum [length ds ^ k | k <- [1..length nums-1]]
    where count [] _      = 1
          count (n:ns) ds = length (filter (<n) ds)  * length ds ^ length ns +
                            length (filter (==n) ds) * count ns ds

main = do print $ countLessThan 100 "1357"
         print $ countLessThan 1000000000 "149"

tom.care 2018-12-25 11:32 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

darigold 2018-12-27 04:55 AM

[quote]原帖由 [i]assembly.jc[/i] 於 2018-12-20 03:10 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492224903&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
用 Haskell Implements "Graham Scan Algorithm",速度係 O (n log n),唔同嘅係 link 入面嘅算法會刪除同一條上面的樹,但題目要求保留,所以慳返幾行 code:
可以試下 run: [url=https://repl.it/repls/DelightfulLightheartedTriggers]https://repl.it/repls/DelightfulLightheartedTriggers[/url]
[/quote]
你的 implementation 有一個 bug,這個 test case 應該 output 所有點,但是你的實現只 output 了 (0,4)(4,4)(3,3)(2,2)(1,1)
(0,0)。[code]main = mapM_ print $ convexHull [(0,0), (1,1), (2,2), (3,3), (4,4), (0, 1), (0, 2), (0, 3), (0, 4)][/code][attach]9151106[/attach]

關鍵在於 sorting ,在 co-linear 的情況下你的 sorting 是選擇把更接近底點的先放在前面。在這個 test case 裏,在右面,這是正確的選擇,在上面,卻是相反的。我不知道如何去 fix ,所以我改寫了 Jarvis march。

這是通過 leetcode 給的一個 test case 發現的,leetcode 上有人嘗試了 fix 這個問題。
[url]https://leetcode.com/problems/erect-the-fence/discuss/103307/c-graham-scanmonotone-chain-dealing-with-collinear-cases[/url]

assembly.jc 2018-12-27 05:27 PM

[quote]原帖由 [i]darigold[/i] 於 2018-12-27 04:55 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492523506&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

你的 implementation 有一個 bug,這個 test case 應該 output 所有點,但是你的實現只 output 了 (0,4)(4,4)(3,3)(2,2)(1,1)
(0,0)。main = mapM_ print $ convexHull [(0,0), (1,1), (2,2), (3,3), (4,4), (0, 1), (0, 2), (0, 3), (0 ... [/quote]

Graham Scan 已經搵晒 d vertices 出來,只要將這些 vertices 連線就係多邊形嘅邊界,再將係邊界上的 points 加入答案就可以了。
問題係,邊個 vertice 同邊個 vertice 連埋一起。因 vertices 由 「右,上,左,下」的次序排列,所以將相鄰的 vertices 相連即可。最後的 point 與 p0 (即 lowest leftmost point) 相連。
再檢查原本的 points 是否在邊界的直線上,如果是 point 是 vertice 就不用查了。這是小弟初步諗法。

[[i] 本帖最後由 assembly.jc 於 2018-12-27 05:37 PM 編輯 [/i]]

tom.care 2018-12-29 01:21 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

assembly.jc 2018-12-29 03:27 AM

[quote]原帖由 [i]darigold[/i] 於 2018-12-27 04:55 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492523506&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]

你的 implementation 有一個 bug,這個 test case 應該 output 所有點,但是你的實現只 output 了 (0,4)(4,4)(3,3)(2,2)(1,1)
(0,0)。main = mapM_ print $ convexHull [(0,0), (1,1), (2,2), (3,3), (4,4), (0, 1), (0, 2), (0, 3), (0 ... [/quote]

按 #15 提到的方法做左個簡單的 implementation: 試 run:[url=https://repl.it/repls/PeacefulMutedMarkuplanguage]https://repl.it/repls/PeacefulMutedMarkuplanguage[/url]

修改不太複雜,只加多個 findBoundary function 如下:


findBoundary _ [] _ = []
findBoundary _ _ [] = []
findBoundary p0 points vs = filter onBoundary points
    where onBoundary p= any (isInterior p) (zip vs (tail vs) ++ [(last vs, p0)])
          isInterior p (sp, ep) = (p /= sp && p /= ep) &&
                                  (orientation sp p ep == Coliner) &&
                                  (orientOrder sp p ep == LT)

convexHull points =
    let orderedPoints = p0 : sortBy (orientOrder p0) (filter (/=p0) points)
        conves        = reverse $ findConves (reverse $ take 3 orderedPoints)
                                             (drop 3 orderedPoints)
        boundPoints   = findBoundary p0 points conves
    in  nub (conves ++ boundPoints)
    where p0 = findLowestPoint points

問題係速度變成 O(n^2),排序個度諗諗可能會快一些。

東邊日出西邊雨 2019-1-4 02:31 PM

[quote]原帖由 [i]獵頭先生[/i] 於 2018-12-20 11:18 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492235884&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]


原來我未夠50分用唔到PM功能,儲夠50分再pm. [/quote]
邊度睇到個分數? 點樣可以加分?

tom.care 2019-2-9 08:49 AM

*** 作者被禁止或刪除 內容自動屏蔽 ***

darigold 2019-2-14 10:13 AM

[quote]原帖由 [i]tom.care[/i] 於 2018-12-29 01:21 AM 發表 [url=https://computer.discuss.com.hk/redirect.php?goto=findpost&pid=492607614&ptid=27880325][img]https://computer.discuss.com.hk/images/common/back.gif[/img][/url]
[url=https://leetcode.com/problems/delete-columns-to-make-sorted/]https://leetcode.com/problems/delete-columns-to-make-sorted/[/url] [/quote][quote]class Solution
{
public:
    int minDeletionSize(vector& A)
    {
        if (A.size() == 0)
        {
            return 0;
        }
        int l = A[0].length();
        int ans = 0;
        for (int c = 0; c < l; c++)
        {
            for (int r = 1; r < A.size(); r++)
            {
                if (A[r][c] < A[r - 1][c])
                {
                    ans++;
                    break;
                }
            }
        }
        return ans;
    }
};[/quote]

[[i] 本帖最後由 darigold 於 2019-7-30 09:38 PM 編輯 [/i]]

alvin__luk 2019-2-14 12:37 PM

Interesting...




I actually implemented this function in one of my computer vision libraries many years ago.

tom.care 2019-2-14 11:43 PM

*** 作者被禁止或刪除 內容自動屏蔽 ***
頁: [1]
查看完整版本: 火雞