圆圈中最后剩下数字

题目描述：

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

样例：

输入：n=5 , m=3 输出：3

分析：

将这n个数字存入列表中，通过举例可以得出第一次删除的数字下标为(m-1)%n记为c， 之后每一次删除的数字下标均为（c+m-1）%list.size()

public int LastRemaining_Solution(int n, int m) { if(n==0||m==0) return -1; List<Integer> list=new ArrayList<>(); for(int i=0;i<n;i++) list.add(i); int c=(m-1)%n; while(list.size()!=1) { list.remove(c); c=(c+m-1)%list.size(); } return list.get(0); }

环形单链表的约瑟夫问题

题目描述

一个环形单向链表的头结点head和报数的值m。 返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删掉。

题解

普通解法：

1、如果链表为空或者链表节点数为1，或者m的值小于1，则不用调整就直接返回2、在环形链表中遍历每个节点，不断转圈，不断让每个节点报数。3、当报数达到m时，就删除当前报数的节点4、删除节点后，别忘了还要把剩下的节点继续连成环状，继续转圈报数，继续删除5、不停地删除，直到环形链表中只剩一个节点，过程结束。6、每删除一个节点，都需要遍历m次，一共需要删除的节点数为n-1，所以这种方法的时间复杂度为O(nm) public static Node killNode(Node head,int m) { if(head==null||head.next==head||m<1) { return head; } Node last=head; //找到next节点指向头结点的节点 while(last.next!=head) { last=last.next; } int count=0; //当next节点指向自己时结束 while(head!=last) { if(++count==m) { last.next=head.next; count=0; }else { last=last.next; } head=last.next; } return head; }

O（N）的解法

1、统计链表中节点的个数，将每个节点添加到列表中保存2、第一次删除的节点下标为(m-1)%节点个数3、下一次删除的节点下标为(上一次删除的节点的下标+m-1)%当前节点个数4、直到列表长度为1时停止 public static Node killNode1(Node head,int m) { if(head==null||head.next==head||m<1) { return head; } List<Node> list=new ArrayList(); Node last=head; list.add(head); //找到next节点指向头结点的节点 while(last.next!=head) { last=last.next; list.add(last); } int index=(m-1)%list.size(); while(list.size()!=1) { list.remove(index); index=(index+m-1)%list.size(); } Node n=list.get(0); n.next=n; return n; }