390. 消除游戏

这一题是约瑟夫环的入门级问题
image.png
image.png
看到实例之后和下面一题一样，拉成一个圆就知道为什么是类似的题了，约瑟夫环针对的问题就是一个循环的环上面，间隔n个数字进行删除的问题。
这个题的难点在于如何去分析这个循环潜藏的对称性：
image.png
以上公式有点歧义，实际上是指一个过程，f(i)是指从左往右，再从右往左这个过程，而不是进行一次“从左往右从右往左”结束之后的结果。因此成立的条件是两个例子：

  1. vec![1, 2, 3, 4, 5, 6, 7, 8, 9]
  2. f[i] => vec![2, 4, 6, 8] => vec![2, 6] => vec![6]
  3. f'[i]=> vec![8, 6, 4, 2] => vec![8, 4] => vec![4]

本质上源于这个:
image.png
因为是对应位置的，因此无论如何都是对位相加。
下一个问题是，约瑟夫环在消除之后都会导致重新编号：
image.png
根据上面的发现，现在的问题来到了我们进行一次消除之后的数组变化：
image.png
根据递推条件，直接写代码即可：

  1. class Solution {
  2.     public int lastRemaining(int n) {
  3.         return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
  4.     }
  5. }
  7. pub fn last_remaining(n: i32) -> i32 {
  8.     match n {
  9.         1 => 1,
  10.         _ => (n/2 + 1 - Solution::last_remaining(n/2)) * 2
  11.     }
  12. }

1823. 找出游戏的获胜者

这一题是典型的约瑟夫环问题，这里先看一下模拟的办法，比较锻炼过程思维：
核心是，我们由于每次绕回来之后会遇见已经遍历过的：

  1. 需要进行标记
  2. 需要取模实现循环
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
 // 加10因为出现了溢出
 let mut checked = vec![false; n as usize + 10];
 // cnt记录选取到了几个人，cur记录当前是第几个人
 // 为了方便取模，我们调整点编号从 00 开始，在返回答案时再重新调整为从 11 开始。
 let (mut cur, mut cnt) = (0, 0);
 while cnt != n-1 {
     // 走k个，注意，因为走过的没有被去除，因此还是在里面走，需要多走
     for i in 0..k-1 {
         cur += 1;
         while checked[cur % n as usize] { cur += 1; }
     }
     // 去一个
     checked[cur % n as usize] = true;
     cnt += 1;
     cur += 1;
     // 注意更新这个,for里确保了cur一定不是走过的，这里需要确保下一个
     // 开始的位置不能是找过的
     while checked[cur % (n as usize)] { cur += 1; }
 }
 (cur as i32) % n + 1
}
    image.png
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
if n <= 1 { return n }
let ans = (Solution::find_the_winner(n-1, k) + k) % n;
match ans {
   0 => n,
   _ => ans
}
}