leetcode390.Elimination Game

Godtoy 發布于2019-08-19 11:33 / 959人閱讀

摘要：題目要求假設有一共個數字，從左往右開始每隔一位刪除一個數字，到達最右側后，再從右往左每隔一位刪除一個數字，如此反復，直到剩下最后一個數字。由此可見，假如我們定義一個遞歸函數我們可以有來獲取結果。

題目要求

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

假設有1-n一共n個數字，從左往右開始每隔一位刪除一個數字，到達最右側后，再從右往左每隔一位刪除一個數字，如此反復，直到剩下最后一個數字。問最后剩下的數字是多少。

思路一：遞歸

先從一個例子入手，當n等于7時，數字序列為1,2,3,4,5,6,7, 刪除序列如下：

1 2 3 4 5 6 7
  2   4   6
      4

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

    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;
            }
        }
    }

思路二

這里其實存在一個鏡像刪除的問題，也就是說，對于任何一個1~n的序列來說，從左往右開始刪除和從右往左開始刪除剩余的結果的和一定為(n+1)，也就是所謂的鏡像刪除問題。
舉個例子：

從左往右開始刪除
1 2 3 4 5 6
  2   4   6
      4
      
從右往左開始刪除
1 2 3 4 5 6
1   3   5
    3

可以看到二者剩余的值加起來一定為n+1即7。
根據這個原理，我們可以優化上面的遞歸，無需再利用left值來標記是從左往右刪除還是從右往左刪除，直接執行鏡像刪除即可。

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

GPU云服務器云服務器 Leetcod LeetCode LeetCode_String leetcode_35_SearchIn

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

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

[Leetcode] Nim Game 尼姆游戲

摘要：腦筋急轉彎復雜度時間空間思路這題往小說可以追溯到小學奧數或者腦筋急轉彎的書中，往大說可以深究到博弈論。代碼如果一開始就是的倍數，你就輸了，因為對方可以用同樣的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...

cartoon 2019-08-14 12:45 評論0 收藏0
LeetCode[45] Jump Game II

摘要：復雜度思路每次設置一個窗口，觀察在這一步下能到達的最遠距離，不斷的移動這個窗口。計數，需要移動幾次，才能覆蓋到末尾的值。 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 2019-08-14 15:02 評論0 收藏0
Leetcode PHP題解--D37 682. Baseball Game

摘要：題目鏈接題目分析給定一個字符串數組，每一個字符串有以下形式數字。直接計算得分。。代表上一輪分數無效。思路這題沒什么好說的了。用區分各種情況，進行相應處理即可。最終代碼若覺得本文章對你有用，歡迎用愛發電資助。 682. Baseball Game 題目鏈接 682. Baseball Game 題目分析給定一個字符串數組，每一個字符串有以下形式：數字。直接計算得分。 +。代表本輪...

wzyplus 2019-07-01 12:42 評論0 收藏0
Leetcode PHP題解--D64 292. Nim Game

摘要：拿到最后一顆石頭的一方為剩方?，F給定一個石頭數量，判斷你最終是否能取得勝利。對方全拿，對方贏。因此，必輸無疑。當剩下的石頭為的整數倍雙方都采取最優策略時，先下手的一方為輸家。因此這個題目就很簡單了，只要判斷給定的數字是否是的整數倍即可。 D64 292. Nim Game 題目鏈接 292. Nim Game 題目分析假設你和朋友玩一個撿石頭的游戲，你和朋友輪流拿1~3顆石頭。拿到最...

XGBCCC 2019-07-01 12:48 評論0 收藏0
[Leetcode] Jump Game 跳躍游戲

摘要：代碼記錄下當前區域的上界，以便待會更新下一個區域的上界更新下一個區域的上界更新下一個區域的下界后續如果要求返回最短跳躍路徑，如何實現可以使用，并根據一個全局最短步數維護一個全局最短路徑，當搜索完所有可能后返回這個全局最短路徑。 Jump Game I 最新解法請見：https://yanjia.me/zh/2019/01/... Given an array of non-negat...

venmos 2019-08-14 12:24 評論0 收藏0