华为社招笔试题

约瑟夫环问题

已知 100 围坐在一张圆桌周围。从编号为 1 的人开始报数，数到 m 的那个人出列；他的下一个人又从 1 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人少于 m 个数，输出圆桌上人的原始编号。

写了个很挫的递归算法(也可以改成循环，懒得改),然后 case 是全部跑通过了。

编程答案

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int m = in.nextInt();
            if (m <=1 || m>=100){
                System.out.println("ERROR!");
                continue;
            }
            Map<Integer, Integer> numList = new HashMap<>();
            for (int i=1;i<=100;i++){
                numList.put(i, i);
            }
            count(numList, m, 1, numList.size());
        }
    }

    private static void count(Map<Integer, Integer> numList, int m, int step, int maxSize){
        if (maxSize < m){
            // 打印结果
            StringBuilder sb = new StringBuilder();
            for (Integer i =1;i<= maxSize;i++){
                sb.append(numList.get(i)).append(",");
            }
            System.out.println(sb.toString().substring(0,sb.lastIndexOf(",")));
            return;
        }
        int s = 1;
        for (int i=1;i<= maxSize;i++){
            if (step == m){
                step = 1;
                continue;
            }
            numList.put(s, numList.get(i));
            step ++;
            s ++;
        }
        count(numList, m, step, s-1);
    }
}

最后祝我等到华为面试，并且面试顺利。