华为社招笔试题

约瑟夫环问题

已知 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);
    }
}

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

# 算法题 

标 题:《华为社招笔试题》
作 者:zeekling
描 述:梅干菜你个小酥饼哦。
地 址:https://www.zeekling.cn/articles/2020/02/23/1582452011400.html
本站加了原创标签的文章都是本站原创作品, 转载请注明:转载自ZEEKLING博客

评论

取消