1、题目一

? ? 有 n个人围成一圈，顺序排号。从第一个人开始报数（从 1 到 3 报数），凡报到 3 的人退出圈子，问最后留下的是原来第几号的那位。

? ? 其实这是一个约瑟夫环问题，这个问题最本质其实就是循环链表的问题，围成一个圈之后，报数即是循环链表的删除操作。

? ? 通常在没有想到很好的方法的时候，我们即会以最常用的思维去解决问题，所以最普通的方法如下：

1.1、解法一

import java.util.Calendar;
import java.util.Scanner;
?
public class YsfTest {
?
    public static void main(String[] args) {
        
        while(true){
            Scanner sc = new Scanner(System.in);
     ? ? ? ?System.out.println("请输入游戏进行的人数:");
     ? ? ? ?int n = sc.nextInt();
     ? ? ? ?long start = Calendar.getInstance().getTimeInMillis();
     ? ? ? ?System.out.println(way1(n,3));
     ? ? ? ?long end = Calendar.getInstance().getTimeInMillis();
     ? ? ? ?System.out.println(end-start);
        }
    }
    
    public static String way1(int n,int m){
        boolean[] arr = new boolean[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i]= true;
        }
        int leftCount = n; //从左到右剩下的人数
        int countNum = 0; //计数器
        int index = 0; //报数人数
        int ret = 0; //最后剩下的人的位置
        if(leftCount==1){//如果一开始就只有一个人
            ret = 1;
        }else{
            while(leftCount>1){//如果左到右一直都大于1个人就需要报数
                if(arr[index]){
                    countNum++;
                    if(countNum==m){
                        countNum = 0;//计数器归0
                        arr[index] = false;
                        leftCount--;
                    }
                }
                index++; //结算循环次数
                if(index==n){ //数组长度不会变，到了最后一个人要重置重写开始报
                    index = 0;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==true){
                ret = i+1;
            }
        }
        return Integer.toString(ret);
    }
    
}

? ? 这个思路就是创建一个数组，数组中报到对应数的设置为false,即被淘汰的，当只剩下最后一个人，也就是只有一个true了。这种解法的效率如何呢？

1.2、解法二

前面说到，这本质就是一个链表，所以呢，我们用链表的方式去实现。

import java.util.Calendar;
import java.util.Scanner;
?
public class YsfTest2 {
 ? ?public static void main(String[] args) {
 ?      while(true){
            Scanner sc = new Scanner(System.in);
     ? ? ? ?System.out.println("请输入游戏进行的人数:");
     ? ? ? ?int n = sc.nextInt();
     ? ? ? ?long start = Calendar.getInstance().getTimeInMillis();
     ? ? ? ?CreatLink link =new CreatLink();
     ? ? ? ?link.creatLink(n);
     ? ? ? ?System.out.println(link.playGame(3));
     ? ? ? ?link = null;
     ? ? ? ?long end = Calendar.getInstance().getTimeInMillis();
     ? ? ? ?System.out.println("耗时："+(end-start));
        }
    }
}
?
?
class CreatLink{
 ? ?Node head;
 ? ?class Node{
 ? ? ? ?int data;
 ? ? ? ?Node next;
 ? ? ? ?public Node(int data){
 ? ? ? ? ? ?this.data=data;
 ? ? ?  }
 ?  }
 ? ?//创建循环链表
 ? ?public void creatLink(int sum){
 ? ? ? ?Node temp=new Node(1);
 ? ? ? ?head=temp;
 ? ? ? ?for (int i = 2; i <=sum; i++) {
 ? ? ? ? ? ? ? ?temp.next=new Node(i);
 ? ? ? ? ? ? ? ?temp=temp.next;
 ? ? ?  }
 ? ? ? ?temp.next=head;
 ?  }
 ? ?
 ? ?//开始游戏
 ? ?public String playGame(int num){
 ? ? ? ?Node temp=head; //从第一个人开始
 ? ? ? ?//出列的节点
 ? ? ? ?Node removeNode;
 ? ? ? ?//循环链表中当只剩一个节点时,该节点的引用指向自己
 ? ? ? ?while(temp.next!=temp){
 ? ? ? ? ? ?for (int i = 2; i <num; i++) {
 ? ? ? ? ? ? ? ?temp=temp.next;
 ? ? ? ? ?  }
 ? ? ? ? ? ?removeNode=temp.next;
 ? ? ? ? ? ?temp.next=temp.next.next;
 ? ? ? ? ? ?temp=removeNode.next;
 ? ? ?  }
 ? ? ? ?return Integer.toString(temp.data);
 ?  }
}

? ? 这种解法，注意可能创建对象过多，会出现：Exception in thread "main" java.lang.OutOfMemoryError: Java heap space。我们可以设置一下Default VM参数。最终看到的运行效率如下：

1.3、解法三

? ? 对于上面两种解法，无论是数组、还是链表，都要频繁的去查询、删除，这样效率其实是很低的。所以，聪明的人就会找规律。

? ? 假设：我们有10个人，[0,1,2,3,4,5,6,7,8,9]，数到3的人被踢出去

? ? 第一次：踢掉了2，我们记作f(10,3)，那么后面继续的话从3开始，还有[3,4,5,6,7,8,9,10%10,11%10]

? ? 第二次：踢掉了5，此时还有9个数我们记作f(9,3),同理还有[6,7,8,9,0,1,3,4]

? ? 第三次：踢掉了8，此时还有8个数我们记作f(8,3),同理还有[9,0,1,3,4,6,7]

? ? 如果在踢第二次的时候，我们将其重新编号：

? ? [3,4,5,6,7,8,9,10%10,11%10]

? ? [0,1,2,3,4,5,6,7,8]，我们发现，其实差值就是等于我们数的数字。

? ? [0+3,1+3,2+3,3+3,4+3,5+3,6+3,(7+3)%10,(8+3)%]

? ? 因此，继续推理可以得出：

? ? f(10,3) = (f(9,3)+3)%10

? ? f(9,3)=(f(8,3)+3)%9

? ? f(8,3)=(f(7,3)+3)%8

? ? ...

? ? f(2,3) = (f(1,3)+3)%2

? ? 当执行到倒数第二次的时候，就只剩下一个人了。

public class YsfTest3 {
 ? ?public static void main(String[] args) {
 ?      while(true){
            Scanner sc = new Scanner(System.in);
     ? ? ? ?System.out.println("请输入游戏进行的人数:");
     ? ? ? ?int n = sc.nextInt();
     ? ? ? ?long start = Calendar.getInstance().getTimeInMillis();
     ? ? ? ?System.out.println(way3(n,3));
     ? ? ? ?long end = Calendar.getInstance().getTimeInMillis();
     ? ? ? ?System.out.println("耗时："+(end-start));
        }
    }
 ? ?
 ? ?public static String way3(int n,int m){
 ?      int ret = 0;
 ? ? ? ?for (int i = 2; i < n; i++) {
            ret = (ret+m)%i;
        }
 ? ? ? ?return Integer.toString(ret+1);
 ?  }
}

? ? 我们再来看下这种解法的效率，数量越大和前面的两种方式差距也越大，效率设置达到之前的10倍。

2、题目二

? ? 我们经常会碰到计算一个某个字符串在原字符串中出现的次数问题。这种问题提供以下几个思路参考。

public class StringCountNum {
    
 ? ?public static void main(String[] args){
 ?      String s = "acbaaabadadasjajcaaaakkkadakadajaka";
 ? ? ? ?String test_s = "aa";
 ? ? ? ?System.out.println(way1(s,test_s));
 ? ? ? ?System.out.println(way2(s,test_s));
 ? ? ? ?System.out.println(way3(s,test_s));
 ?  }
 ? ?
 ? ?public static String way1(String s1,String s2){
 ?      int count = 0; 
     ? ?Pattern p = Pattern.compile(s2); 
     ? ?Matcher m = p.matcher(s1); 
     ? ?while (m.find()) { 
     ? ? ? count++; 
     ?  } 
     ? ?return count+"";
 ?  }
 ? ?
 ? ?public static String way2(String s1,String s2){
 ?      int count = 0;
 ? ? ? ?while(s1.indexOf(s2)>=0) {
 ? ? ? ? ? ?s1 = s1.substring(s1.indexOf(s2)+s2.length());
 ? ? ? ? ? ?count++;
 ? ? ?  }
 ? ? ? ?return count+"";
 ?  }
 ? ?
 ? ?public static String way3(String s1,String s2){
 ?      int count2 = 0;
 ?      count2 = (s1.length()-s1.replace(s2, "").length())/s2.length();
 ?      return count2+"";
 ?  }
 ? ?
}