国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Java] 關于一道面試題的思考

rozbo / 569人閱讀

摘要:對于這種會退出的情況,數組顯然不能像鏈表一樣直接斷開,因此采用標記法先生成一個長度為的布爾型數組,用填充。中對整個進行遍歷才能得到此時數組中的數量。

文中的速度測試部分,時間是通過簡單的 System.currentTimeMillis() 計算得到的,
又由于 Java 的特性,每次測試的結果都不一定相同,
對于低數量級的情況有 ± 20 的浮動,對于高數量級的情況有的能有 ± 1000 的浮動。

這道題本質上是個約瑟夫環問題,最佳解法在最下面,本文只是探究一下數組暴力和鏈表的表現差異。
題目

N 個人圍成一圈,順序排號。從第一個人開始報數(從1數到3),凡是到3的人退出圈子,問最后留下的是原來第幾號。

樣例

2 個人時留下的是第二個;

3個人時留下的是第二個;

5個人時留下的是第四個;

12個人時留下的是第十個;

100,000個人時留下的是第92620個人。

機器環境

CPU Intel Xeon E3-1231 v3 @ 3.40GHz

RAM 16 GB

暴力解決

雖然第一反應是用鏈表,但對于人數在1000以下的量級感覺數組也足以勝任,因此先用數組試試。

對于這種會 退出 的情況,數組顯然不能像鏈表一樣直接斷開,因此采用標記法:

先生成一個長度為 N 的布爾型數組,用 true 填充。

報號時,對于報到 3 的位置,用 false 來標記該位置,下次循環如果遇到 false 則可以直接跳過。

那么等到數組內只剩一個 true 的時候,找到其位置,即是最后留下來的人的位置。

既然暴力,那干脆徹底一點:

    public static int findIndex(final int N) {
        boolean[] map = new boolean[N];
        Arrays.fill(map, true);
        int walk = 1;
         // 因為是站成一個圓,所以在遍歷到最后時需要將下標重新指向 0
           // count(map) 就是遍歷整個數組計算還剩余的 true 的數量
        for (int index = 0; count(map) > 1; index = (index == N - 1) ? 0 : (index + 1)) {
            // 對于 false 可以直接跳過,因為它們相當于不存在
               if (! map[index]) continue;
             // 報號時如果不是3 則繼續找下一位;
            if (walk++ != 3) continue;
             // 如果是 3,則重置報號,并將當前位置的值改為 false
            walk = 1;
            map[index] = false;
        }
        return find(map);
    }
    
    // 因為是 count(map) == 1 的情況下才會調用這個方法,所以直接返回第一個 true 所在的位置即可
    public static int find(boolean[] map) {
        for (int i = 0; i < map.length; i++) {
            if (!map[i]) continue;
            return i + 1;
        }
        return -1;
    }

    public static int count(boolean[] map) {
        int count = 0;
        for (boolean bool : map) {
            count += bool ? 1 : 0;
        }
        return count;
    };

對于這個解法,可以跑一下測試看看耗時:

N time / ms
100 1
1,000 13
10,000 686
100,000 80554

很顯然,這種暴力的做法對于大一點的數量級就很吃力了,但是我又不想那么快就用鏈表,有沒有哪里是可以優化的呢。

消除循環

其實在前面的解法中,耗時操作有這么幾個:

findIndex 中不停得對整個 map 進行遍歷,即便對于 false 直接跳過,但杯水車薪。

count 中對整個 map 進行遍歷才能得到此時數組中 true 的數量。

find 中同樣需要對整個 map 進行遍歷才能得到剩下的一個 true 的下標。

其中第一點應該是這種解法的本質,沒什么好辦法,那么看看后兩點。

消除 count

這個方法想做的事就是每次循環時檢查此時數組中 true 的數量是不是只剩一個了,因為這是循環的終結條件。

那么我們可以引入一個計數器:

    private static int findIndex(final int N) {
        boolean[] map = new boolean[N];
        Arrays.fill(map, true);
        int walk = 1;
         int countDown = N;
        for (int index = 0; countDown > 1; index = (index == N - 1) ? 0 : (index + 1)) {
            if (! map[index]) continue;
            if (walk++ != 3) continue;
            walk = 1;
            map[index] = false;
               countDown -= 1;
        }
        return find(map);
    }

改成這種做法后,猜猜對于 100,000 這個數量級,這個暴力算法需要用時多久呢?

答案是 11 ms

對于 100,000,000 這個數量級,這個暴力算法仍只需要 3165 ms。

稍稍透露一下,后邊的鏈表解法在這個數量級的成績是 7738 ms,當然可能是我太垃圾了,發揮不出鏈表的威力 Orz)

消除 find

這個方法要做的是從整個數組中找到唯一的 true 的下標,這同樣可以用一個外部變量來消除循環:

    private static int findIndex(final int N) {
        boolean[] map = new boolean[N];
        Arrays.fill(map, true);
        int walk = 1;
         // 記錄現在訪問到值為 true 的下標
        int current = 0;
        int countDown = N;
        for (int index = 0; countDown > 1; index = (index == N - 1) ? 0 : (index + 1)) {
            if (! map[index]) continue;
            if (walk++ != 3) {
                   // 記錄最后一次遇到 true 的位置
                current = index;
                continue;
            }
            walk = 1;
            map[index] = false;
            countDown -= 1;
        }
         // 人的位置是從 1 開始數的,所以這里要加 1
        return current + 1;
    }

但是這個改動對速度的提升效果很小,對于 100,000,000 這個數量級,速度仍然在 3158 ~ 3191 ms 左右。

不暴力了,用鏈表吧

使用鏈表可以很方便得體現 退出 這個概念,鏈表的長度會隨著算法的進行而越來越短直至剩下最后一個元素。因為沒有 跳過標記為 false 的步驟,理論上會比暴力數組解法要快。

    static class Node {
           // 當前節點的下標,即人的位置
        int index;
           // 上一個節點
        Node prev;
         // 下一個節點
        Node next;

        public Node (int index) {
            this.index = index;
        }

        public Node append(Node next) {
            this.next = next;
            next.prev = this;
            return next;
        }

         // 需要報號為3的人(當前元素)退出時,從鏈表中斷開并將兩邊拼接起來
        public Node jump() {
            Node newNode = this.next;
            newNode.prev = this.prev;
            newNode.prev.next = newNode;
            this.prev = null;
            this.next = null;
            return newNode;
        }

        public static int findIndex(final int N) {
            Node root = new Node(1);
               // 初始化鏈表并賦值,這個過程對于很大的數量級而言速度肯定是慢過對數組的賦值的,
             // 畢竟類的實例化需要開銷。因此這段初始化不計入時間
            Node current = root;
            for (int i = 2; i <= N; i++) {
                current = current.append(new Node(i));
            }
            // 將首尾相連構成循環列表
            current = current.append(root);
          
            long mills = System.currentTimeMillis();
          
            int COUNTER = N;
            int walk = 1;
            while (COUNTER > 1) {
                if (walk++ != 3) {
                    current = current.next;
                } else {
                    current = current.jump();
                    walk = 1;
                    COUNTER -= 1;
                }
            }

            System.out.println(System.currentTimeMillis() - mills);
            return current.index;

        }
    }
看看兩種解法的速度對比
N 數組暴力法 / ms 數組暴力法(改進) / ms 鏈表法 / ms
100 2 0 0
1,000 15 1 0
10,000 673 5 1
100,000 79998 10 3
1,000,000 N/A 38 64
10,000,000 N/A 309 718
100,000,000 N/A 3151 7738

? 對于 1,000,000 及以上的數量級就沒測原數組暴力法了,太慢了...

總結

可以看到,在百萬級別,改進的數組暴力法已經要比鏈表法快一半了,在億級要快的更多。

當然這個速度差異很大程度上是因為隨著數量級的加大,鏈表法所需要的內存開銷已經超出一個合理的范圍了,隨之而來的就是鏈表的斷開重組操作要比 標記 重太多了。

但是這只是 想知道最后一個人的位置 的情況,數組的下標可以做到一定程度的契合,如果情況更復雜了,顯然數組就不夠用了。

對于鏈表法在超大數量級的解法,感覺可以用多線程來做一次整體循環內的截斷,只是這樣復雜度就上去了,暫時不做了,有興趣的讀者可以自行嘗試一下。

算法的力量
    public static int josephus(int n) {
        int res = 0;
        if (n == 0) return 0;
        if (n < 3) {
            for (int i = 2; i <= n; i++) {
                res = (res + 3) % i;
            }
        } else {
            res = josephus(n - n / 3);
            if (res < (n % 3)) {
                res = res - (n % 3) + n;
            } else {
                res = res - (n % 3) + (res - (n % 3)) / 2;
            }
        }
        return res;
    }

    public static void main(String ...args) {
        System.out.println(hosephus(1000000000));
    }

這個解法對于一億這個數量級的運算時間是不到 0 ms,來自我的 ACMer 同學 ( 打不過正規軍啊,跪了

據我同學所說:

遞歸層數 log 級別,n 可以達到 1e18 級別,15 ms 內給出答案。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/68851.html

相關文章

  • 一道【脈脈】上 頭條 算法面試題的思考

    摘要:偶然間在脈脈上看到了一道頭條的算法面試題按照題目的理解,簡單的寫了一個網頁開始學的不僅是技術,更是夢想得到了如下效果圖得到如題可以進行開關的示例在最后一個燈特殊處理,鏈接第一個燈,形成環經過測試發現只要從序號開始,如 偶然間在脈脈上看到了一道頭條的算法面試題 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照題...

    tyheist 評論0 收藏0
  • 一道【脈脈】上 頭條 算法面試題的思考

    摘要:偶然間在脈脈上看到了一道頭條的算法面試題按照題目的理解,簡單的寫了一個網頁開始學的不僅是技術,更是夢想得到了如下效果圖得到如題可以進行開關的示例在最后一個燈特殊處理,鏈接第一個燈,形成環經過測試發現只要從序號開始,如 偶然間在脈脈上看到了一道頭條的算法面試題 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照題...

    xuxueli 評論0 收藏0
  • 尾調用優化——記一道面試題的思考

    摘要:如果函數內部還調用函數,那就還有一個的調用幀,依次類推。等同于等同于如果所有函數都是尾調用,那么完全可以做到每次執行時,調用幀只有一項,這將大大節省內存。這就是尾調用優化。尾遞歸函數調用自身,稱為遞歸。 前言 面某東,有一道題目是 實現一個斐波拉契數列, 已知第一項為0,第二項為1,第三項為1,后一項是前兩項之和,即f(n) = f(n - 1) + f(n -2)。 拿到這個題目,二...

    awkj 評論0 收藏0
  • 鏈式調用與事件循環--一道JavaScript面試題的思考

    摘要:最后畫幾張粗糙的圖,簡單描述一下這個執行的過程因為是鏈式調用,所以在鏈上的都會入棧然后執行,額,執行棧少畫了和。。。 前言:昨天在群里討(jin)論(chui)技(niu)術(pi),有位老鐵發了一道他面的某公司面試題,順手保存了。今早花了一點時間把這題做了出來,發現挺有意思的,決定在今天認真工(hua)作(shui)前,與大家分享我的解題方案和思考過程。 題目如下(可以自己先思考一會...

    wow_worktile 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<