[数据结构与算法]【面试题】Josepfu 约瑟夫问题

Josepfu 约瑟夫问题实现

什么是约瑟夫问题：

问题分析 ：

1，表示n个人环坐做在一起使用什么样子的数据结构, 数组？链表？ 
2.如何找到第K个结点，如何移动找到每隔m个要操作的结点
3. 最后将结点移动出去

在这次我选择数据结构为环形链表：因为形象直接，增加删除快速

分析图如下:

思路分析

需要一个辅助结点helper指向first结点前一个元素


代码实现

孩子结点

/**
 * @Author: 云萧YYY
 * @DateTime: 2021/08/04
 * @Description: 孩子结点  完成josepfu问题
 */
public class BoyNode {

    private int no;
    private BoyNode next;

    public BoyNode(int no){
        this.no=no;
    }
    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public BoyNode getNext() {
        return next;
    }

    public void setNext(BoyNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "BoyNode{" +
                "no=" + no +
                '}';
    }
}

循环链表

/** @Author: 云萧YYY @DateTime: 2021/08/04 @Description: 模拟解决约瑟夫问题 ，创建环形链表 */
public class CircleSingleLinkedList {

  /** 创建一个初始结点 */
  private BoyNode first = null;
  /** 指向当前结点 */
  private BoyNode cur = null;

  /**
   * * 初始化构建环形链表
   *
   * @param nums 表示添加孩子节点的个数 比如说 创建一个nums个的环形链表，多少个孩子围坐在一起
   */
  public void add(int nums) {
    // 说明创建孩子人数至少有一个
    if (nums < 1) {
      throw new RuntimeException("num值不能小于1");
    }
    // 编号从1开始
    for (int num = 1; num <= nums; num++) {
      //
      BoyNode boy = new BoyNode(num);
      // 如果是开始链表是kong的
      if (first == null) {
        first = boy;
        boy.setNext(boy);
        cur = boy;
      } else {

        // 不为空，链表中至少有一个
        cur.setNext(boy);
        cur = boy;
        cur.setNext(first);
      }
    }
  }

  /**
   * 约瑟夫问题
   *
   * @param k 从k的编号 开始
   * @param m 报m个数
   */
  public void josepfu(int k, int m) {

    if (k < 1 || m < 0 || k > size()) {
      throw new RuntimeException("k,m 不合理");
    }
    // 定义辅助结点 ，将辅助结点移动到最后一个位置
    BoyNode helper = this.getLastNode();
    // 移动helper，first指针，将first指向开始报数的人
    // first 移动到第k个人上
    for (int i = 0; i < k - 1; i++) {
      first = first.getNext();
      helper = helper.getNext();
    }
    // 开始报数，出链表
    while (true) {
      // 只剩下一个结点了
      if (first.getNext() == first) {
        System.out.print("最后一个出列" + first);
        return;
      }
      // 找到第m个人
      for (int j = 0; j < m - 1; j++) {
        first = first.getNext();
        helper = helper.getNext();
      }
      // 移动结点
      System.out.print(first + "出列了"+",\t");
      first = first.getNext();
      helper.setNext(first);
    }
  }

  /**
   * 返回最后一个结点位置
   *
   * @return
   */
  private BoyNode getLastNode() {
    if (first == null) {
      System.out.println("循环链表为空");
    }
    BoyNode end = first;
    do {
      end = end.getNext();
    } while (end.getNext() != first);
    return end;
  }

  public int size() {
    int count = 0;
    if (first == null) {
      return count;
    }
    cur = first;
    do {
      count++;
      cur = cur.getNext();
    } while (cur != first);
    cur = null;
    return count;
  }

  /** 打印一下当前链表 */
  public void printList() {

    if (first == null) {
      return;
    }
    // 辅助指针
    cur = first;
    do {
      System.out.println(cur);
      cur = cur.getNext();
    } while (cur != first);
  }
}

运行代码

/** @Author: 云萧YYY @DateTime: 2021/08/05 @Description: 测试环形链表  解决约瑟夫问题 */
public class CircleLinkedListTest {

  public static void main(String[] args) {
    //
    CircleSingleLinkedList list = new CircleSingleLinkedList();
    list.add(5);
    list.josepfu(3,2);
    //
  //  list.printList();

  }

结果显示