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

資訊專欄INFORMATION COLUMN

leetcode390.Elimination Game

Godtoy / 951人閱讀

摘要：題目要求假設(shè)有一共個(gè)數(shù)字，從左往右開(kāi)始每隔一位刪除一個(gè)數(shù)字，到達(dá)最右側(cè)后，再?gòu)挠彝竺扛粢晃粍h除一個(gè)數(shù)字，如此反復(fù)，直到剩下最后一個(gè)數(shù)字。由此可見(jiàn)，假如我們定義一個(gè)遞歸函數(shù)我們可以有來(lái)獲取結(jié)果。

題目要求 
There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

假設(shè)有1-n一共n個(gè)數(shù)字，從左往右開(kāi)始每隔一位刪除一個(gè)數(shù)字，到達(dá)最右側(cè)后，再?gòu)挠彝竺扛粢晃粍h除一個(gè)數(shù)字，如此反復(fù)，直到剩下最后一個(gè)數(shù)字。問(wèn)最后剩下的數(shù)字是多少。

思路一：遞歸

先從一個(gè)例子入手，當(dāng)n等于7時(shí)，數(shù)字序列為1,2,3,4,5,6,7, 刪除序列如下：

1 2 3 4 5 6 7
  2   4   6
      4

可以看到，第一輪刪除后剩下的2，4，6就相當(dāng)于是1，2，3的兩倍，我們可以等價(jià)于從右往左刪除1，2，3后剩余的結(jié)果乘2。由此可見(jiàn)，假如我們定義一個(gè)遞歸函數(shù)f(n, left),我們可以有f(n/2, right)來(lái)獲取結(jié)果。

    public int lastRemaining(int n) {
        return lastRemaining(n, true);
    }
    
    public int lastRemaining(int n, boolean left) {
        if(n == 1) {
            return 1;
        }
        if(n % 2 == 1) {
            return lastRemaining(n / 2, !left) * 2;
        }else{
            if( left ) {
                return lastRemaining(n/2, !left) * 2;
            }else {
                return lastRemaining(n/2, !left) * 2 -1;
            }
        }
    }
思路二

這里其實(shí)存在一個(gè)鏡像刪除的問(wèn)題，也就是說(shuō)，對(duì)于任何一個(gè)1~n的序列來(lái)說(shuō)，從左往右開(kāi)始刪除和從右往左開(kāi)始刪除剩余的結(jié)果的和一定為(n+1)，也就是所謂的鏡像刪除問(wèn)題。
舉個(gè)例子：

從左往右開(kāi)始刪除
1 2 3 4 5 6
  2   4   6
      4
      
從右往左開(kāi)始刪除
1 2 3 4 5 6
1   3   5
    3

可以看到二者剩余的值加起來(lái)一定為n+1即7。
根據(jù)這個(gè)原理，我們可以優(yōu)化上面的遞歸，無(wú)需再利用left值來(lái)標(biāo)記是從左往右刪除還是從右往左刪除，直接執(zhí)行鏡像刪除即可。

    public int lastRemaining2(int n) {
        return n == 1 ? 1 : (1 + n / 2 - lastRemaining2(n/2)) * 2;
    }

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/77452.html

相關(guān)文章

  • [Leetcode] Nim Game 尼姆游戲

    摘要：腦筋急轉(zhuǎn)彎復(fù)雜度時(shí)間空間思路這題往小說(shuō)可以追溯到小學(xué)奧數(shù)或者腦筋急轉(zhuǎn)彎的書中，往大說(shuō)可以深究到博弈論。代碼如果一開(kāi)始就是的倍數(shù)，你就輸了，因?yàn)閷?duì)方可以用同樣的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...

    cartoon 評(píng)論0 收藏0

  • LeetCode[45] Jump Game II

    摘要：復(fù)雜度思路每次設(shè)置一個(gè)窗口，觀察在這一步下能到達(dá)的最遠(yuǎn)距離，不斷的移動(dòng)這個(gè)窗口。計(jì)數(shù)，需要移動(dòng)幾次，才能覆蓋到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...

    keelii 評(píng)論0 收藏0

  • Leetcode PHP題解--D37 682. Baseball Game

    摘要：題目鏈接題目分析給定一個(gè)字符串?dāng)?shù)組，每一個(gè)字符串有以下形式數(shù)字。直接計(jì)算得分。。代表上一輪分?jǐn)?shù)無(wú)效。思路這題沒(méi)什么好說(shuō)的了。用區(qū)分各種情況，進(jìn)行相應(yīng)處理即可。最終代碼若覺(jué)得本文章對(duì)你有用，歡迎用愛(ài)發(fā)電資助。 682. Baseball Game 題目鏈接 682. Baseball Game 題目分析 給定一個(gè)字符串?dāng)?shù)組，每一個(gè)字符串有以下形式： 數(shù)字。直接計(jì)算得分。 +。代表本輪...

    wzyplus 評(píng)論0 收藏0

  • Leetcode PHP題解--D64 292. Nim Game

    摘要：拿到最后一顆石頭的一方為剩方。現(xiàn)給定一個(gè)石頭數(shù)量，判斷你最終是否能取得勝利。對(duì)方全拿，對(duì)方贏。因此，必輸無(wú)疑。當(dāng)剩下的石頭為的整數(shù)倍雙方都采取最優(yōu)策略時(shí)，先下手的一方為輸家。因此這個(gè)題目就很簡(jiǎn)單了，只要判斷給定的數(shù)字是否是的整數(shù)倍即可。 D64 292. Nim Game 題目鏈接 292. Nim Game 題目分析 假設(shè)你和朋友玩一個(gè)撿石頭的游戲，你和朋友輪流拿1~3顆石頭。拿到最...

    XGBCCC 評(píng)論0 收藏0

  • [Leetcode] Jump Game 跳躍游戲

    摘要：代碼記錄下當(dāng)前區(qū)域的上界，以便待會(huì)更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的下界后續(xù)如果要求返回最短跳躍路徑，如何實(shí)現(xiàn)可以使用，并根據(jù)一個(gè)全局最短步數(shù)維護(hù)一個(gè)全局最短路徑，當(dāng)搜索完所有可能后返回這個(gè)全局最短路徑。 Jump Game I 最新解法請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/01/... Given an array of non-negat...

    venmos 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<