leetcode 390. Elimination Game | 390. 消除游戏（Java）

旧城等待， 2022-08-31 15:16 130阅读 0赞

## 题目 ##

[https://leetcode.com/problems/elimination-game/][https_leetcode.com_problems_elimination-game]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 方法1：模拟（内存超出限制） ####

最朴素的思路，模拟每一轮的消除，直到剩余大小为 1 为止。

此方法内存超限。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public int lastRemaining(int n) { 
            int[] a = new int[n];
            for (int i = 0; i < n; i++) { 
                a[i] = i + 1;
            }
    
            int size = n;
            int[] b = null;
            boolean L = true; // start from left
            while (size >= 1) { 
                size /= 2;
                b = new int[size]; // 每轮缩容一半
                int p = 0;
                if (L) { 
                    while (p < size) { 
                        b[p] = a[p * 2 + 1];
                        p++;
                    }
                    L = false;
                } else { 
                    while (p < size) { 
                        b[size - p - 1] = a[a.length - (p * 2 + 1) - 1];
                        p++;
                    }
                    L = true;
                }
                int[] t = a;
                a = b;
                b = t;
            }
            return b[0];
        }
    }

#### 方法2：只记录起始位置以及步长（通过） ####

参考：[JAVA: Easiest solution O(logN) with explanation][JAVA_ Easiest solution O_logN_ with explanation]

My idea is to update and record **head** in each turn. when the total number becomes 1, head is the only number left.

When will head be updated?

*  if we move from left
 *  if we move from right and the total remaining number % 2 == 1  
    like 2 4 6 8 10, we move from 10, we will take out 10, 6 and 2, head is deleted and move to 4  
    like 2 4 6 8 10 12, we move from 12, we will take out 12, 8, 4, head is still remaining 2

then we find a rule to update our head.

example:  
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1.  Let us start with **head = 1, left = true, step = 1 (times 2 each turn), remaining = n(24)**
2.  we first move from left, we definitely need to move head to next position. **(head = head + step)**  
    So after first loop we will have:  
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 - > 2 4 6 8 10 12 14 16 18 20 22 24  
    **head = 2, left = false, step = 1 \* 2 = 2, remaining = remaining / 2 = 12**
3.  second loop, we move from right, in what situation we need to move head?  
    only if the remaining % 2 == 1, in this case we have 12 % 2 == 0, we don’t touch head.  
    so after this second loop we will have:  
    2 4 6 8 10 12 14 16 18 20 22 24 - > 2 6 10 14 18 22  
    **head = 2, left = true, step = 2 \* 2 = 4, remaining = remaining / 2 = 6**
4.  third loop, we move from left, move head to next position  
    after third loop we will have:  
    2 6 10 14 18 22 - > 6 14 22  
    **head = 6, left = false, step = 4 \* 2 = 8, remaining = remaining / 2 = 3**
5.  fourth loop, we move from right, NOTICE HERE:  
    we have remaining(3) % 2 == 1, so we know we need to move head to next position  
    after this loop, we will have  
    6 14 22 - > 14  
    **head = 14, left = true, step = 8 \* 2 = 16, remaining = remaining / 2 = 1**
6.  while loop end, return head

class Solution { 
        public int lastRemaining(int n) { 
            boolean L = true; // 是否从左向右
            int size = n;
            int step = 1;
            int begin = 1; // 开始的数字（而非位置）
            while (size > 1) { 
                if (L || size % 2 == 1) { 
                    begin += step;
                }
                size /= 2;
                step *= 2;
                L = !L;
            }
            return begin;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_elimination-game]: https://leetcode.com/problems/elimination-game/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/bf04d36c89234f8ab26571d333fa5b92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/ad6db7a1009e4b6b9da40b90b16c020d.png
[JAVA_ Easiest solution O_logN_ with explanation]: https://leetcode.com/problems/elimination-game/discuss/87119/JAVA:-Easiest-solution-O%28logN%29-with-explanation
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/7a2db34839de4fb5988cd6b0fc987d75.png