day47(5.24)

1. 圆圈中最后剩下的数字
- 思路:
- 优秀解法:

1. 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
限制：
1 <= n <= 10^5
1 <= m <= 10^6

思路:

关键是找到对应索引位置

将一个组数视作环处理

通过索引取余操作

为了防止数组越界,就需要保持取余的那个数的变化

class Solution {
public int lastRemaining(int n, int m) {
   // 初始化
   List<Integer> list = new ArrayList<>();
   for(int i=0;i<n;i++){
       list.add(i);
   }
   int cur = 0;
   int size = n;
   // 
   while(size!=1){
       int index = (cur+m-1)%size;
       list.remove(index);
       cur = index;
       size--;
   }
   return list.get(0);
}
}

时间过于长, 需要优化
尝试通过数组进行优化,因为list进行remove是一个数组重建的过程,耗时过长

尝试使用了环形链表去解决,也是效率低

class Solution {
  public int lastRemaining(int n, int m) {
      // 初始化
      ListNode head = new ListNode(0);
      ListNode cur = head;
      for(int i=1;i<n;i++){
          ListNode node = new ListNode(i);
          cur.next = node;
          cur = cur.next;
      }
      cur.next = head;
      // 执行n-1次
      // ListNode temp = head;
      for(int j=0;j<n-1;j++){
          for(int k=0;k<m-1;k++){
              cur = cur.next;
          }
          cur.next = cur.next.next;
      }
      return cur.val;
  }
}

1. 圆圈中最后剩下的数字

思路:

优秀解法: