面试题62. 圆圈中最后剩下的数字

川长思鸟来 2023-02-11 03:09 55阅读 0赞

# 题目来源 #

[leetcode][]

# 题目描述 #

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

# 题目解析 #

## 模拟 ##

注意不能用LinkedList，要用ArrayedList。ArrayedList删除时是连续空间访问，而LinkedList是非连续空间访问，ArrayedList性能更好

class Solution {
        
        public int lastRemaining(int n, int m) {
        
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++){
        
                list.add(i);
            }
    
            int start = 0;
            while (n != 1){
        
                start =   (start + m - 1) % n;
                list.remove(start);
                n--;
            }
    
            return list.get(0);
        }
    }

![在这里插入图片描述][20200521114337967.png]

## 公式法 ##

[具体解析][Link 1]

如果只有1个人，返回0  
如果2个人： 返回 （0+m）%2  
3个人： 返回(（0+m）%2 + m) %2

一直到n个人为止

class Solution {
        
        public int lastRemaining(int n, int m) {
        
            int ans = 0; // 只有一个人
            
            // 从第二个人开始推
            for (int i = 2; i <= n; i++){
        
                ans = (ans + m) % i;
            }
    
            return ans;
        }
    }

![在这里插入图片描述][20200521112451972.png]

## 递归 ##

class Solution {
        
        public int lastRemaining(int n, int m) {
        
            if (n == 1){
        
                return 0;
            }
    
            int x = lastRemaining(n - 1, m);
            return (x + m) % (n);
        }
    }

![在这里插入图片描述][20200521114406688.png]

[leetcode]: https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521114433693.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200521114337967.png]: https://img-blog.csdnimg.cn/20200521114337967.png
[Link 1]: https://blog.csdn.net/zhizhengguan/article/details/106250796
[20200521112451972.png]: https://img-blog.csdnimg.cn/20200521112451972.png
[20200521114406688.png]: https://img-blog.csdnimg.cn/20200521114406688.png