当前位置： 2024华为OD机试题库 (C卷,100分)- 报数游戏（Java & JS & Python）

(C卷,100分)- 报数游戏（Java & JS & Python）

2024-05-07 11

题目描述

100个人围成一圈，每个人有一个编码，编号从1开始到100。

他们从1开始依次报数，报到为M的人自动退出圈圈，然后下一个人接着从1开始报数，直到剩余的人数小于M。

请问最后剩余的人在原先的编号为多少？

输入描述

输入一个整数参数 M

输出描述

如果输入参数M小于等于1或者大于等于100，输出“ERROR!”；

否则按照原先的编号从小到大的顺序，以英文逗号分割输出编号字符串

用例

输入 3
输出 58,91
说明 输入M为3，最后剩下两个人。
输入 4
输出 34,45,97
说明 输入M为4，最后剩下三个人。

题目解析

本题是经典的约瑟夫环问题，可以利用循环链表解决。

解法一：循环链表

定义一个循环链表，头节点val=1，尾节点val=100，头.prev = 尾，尾.next = 头

这样的话，就构造出了一个循环链表。

我们还需要为循环链表设置，尾部追加新节点，删除任意节点的操作。

另外，我们还需要维护一个报数变量idx，从1开始。

这样的话，我们从链表头head开始查询，此时报数idx=1，

  • 如果idx===m，则删除当前节点cur，下一个查询节点变为删除节点的下一个节点，并且重置报数idx=1，
  • 如果idx!==m，则继续查询下一节点，即cur = cur.next，并且报数idx++

按上面逻辑，直到链表的size < m时，结束。

然后，for(i=0; i<size; i++) 遍历出循环链表的每一个节点值，就是题解。

Java算法源码

import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    System.out.println(getResult(m));
  }

  public static String getResult(int m) {
    if (m <= 1 || m >= 100) return "ERROR!";

    CycleLinkedList list = new CycleLinkedList();
    for (int i = 1; i <= 100; i++) list.append(i);

    int idx = 1;
    Node cur = list.head;

    while (list.size >= m) {
      if (idx == m) {
        idx = 1;
        cur = list.remove(cur);
      } else {
        idx++;
        cur = cur.next;
      }
    }

    return list.toString();
  }
}

class Node {
  int val;
  Node prev;
  Node next;

  public Node(int val, Node prev, Node next) {
    this.val = val;
    this.prev = prev;
    this.next = next;
  }
}

class CycleLinkedList {
  Node head;
  Node tail;
  int size = 0;

  public void append(int val) {
    Node node = new Node(val, null, null);

    if (this.size > 0) {
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    } else {
      this.head = node;
      this.tail = node;
    }
    this.head.prev = this.tail;
    this.tail.next = this.head;
    this.size++;
  }

  public Node remove(Node cur) {
    Node pre = cur.prev;
    Node nxt = cur.next;

    pre.next = nxt;
    nxt.prev = pre;

    cur.next = cur.prev = null;

    if (this.head == cur) {
      this.head = nxt;
    }

    if (this.tail == cur) {
      this.tail = pre;
    }
    this.size--;
    return nxt;
  }

  @Override
  public String toString() {
    StringJoiner sj = new StringJoiner(",");

    Node cur = this.head;
    for (int i = 0; i < this.size; i++) {
      sj.add(cur.val + "");
      cur = cur.next;
    }

    return sj.toString();
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const m = line - 0;
  console.log(getResult(m));
});

function getResult(m) {
  if (m <= 1 || m >= 100) {
    return "ERROR!";
  }

  const list = new CycleLinkedList();
  for (let i = 1; i <= 100; i++) list.append(i);

  let idx = 1;
  let cur = list.head;

  while (list.size >= m) {
    if (idx === m) {
      idx = 1;
      cur = list.remove(cur);
    } else {
      idx++;
      cur = cur.next;
    }
  }

  return list.toString();
}

// 节点定义（双向）
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

// 循环链表定义
class CycleLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  append(val) {
    const node = new Node(val);

    if (this.size) {
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    } else {
      this.head = node;
      this.tail = node;
    }
    this.head.prev = this.tail;
    this.tail.next = this.head;
    this.size++;
  }

  remove(cur) {
    const pre = cur.prev;
    const nxt = cur.next;

    pre.next = nxt;
    nxt.prev = pre;

    cur.next = cur.prev = null;

    if (this.head === cur) {
      this.head = nxt;
    }

    if (this.tail === cur) {
      this.tail = pre;
    }

    this.size--;

    return nxt;
  }

  toString() {
    const arr = [];
    let cur = this.head;

    for (let i = 0; i < this.size; i++) {
      arr.push(cur.val);
      cur = cur.next;
    }

    return arr.join();
  }
}

Python算法源码

# 双向节点
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None


# 循环链表
class CycleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def append(self, val):
        node = Node(val)

        if self.size > 0:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
        else:
            self.head = node
            self.tail = node

        self.head.prev = self.tail
        self.tail.next = self.head
        self.size += 1

    def remove(self, cur):
        pre = cur.prev
        nxt = cur.next

        pre.next = nxt
        nxt.prev = pre

        cur.next = cur.prev = None

        if self.head == cur:
            self.head = nxt

        if self.tail == cur:
            self.tail = pre

        self.size -= 1

        return nxt

    def __str__(self):
        arr = []
        cur = self.head

        for i in range(self.size):
            arr.append(str(cur.val))
            cur = cur.next

        return ",".join(arr)


# 输入获取
m = int(input())


# 算法入口
def getResult():
    if m <= 1 or m >= 100:
        return "ERROR!"

    cycList = CycleLinkedList()
    for i in range(1, 101):
        cycList.append(i)

    idx = 1
    cur = cycList.head

    while cycList.size >= m:
        if idx == m:
            idx = 1
            cur = cycList.remove(cur)
        else:
            idx += 1
            cur = cur.next

    return str(cycList)


# 算法调用
print(getResult())

解法二：递归

逻辑分析，需要先考虑两点

  • 找到报数M的人
  • 维持连续报数

我这边维护了一个外部变量count，让他初始值为1，因为报数从1开始。

遍历数组，每遍历完一次，则count++，下次遍历时判断count是不是已经超过M了，若超过则count重置为1，以此模拟报数。

当count%M===0时，表示当前遍历的数组元素就是报数M的人，我们将他filter踢出去了。

维持连续报数，指的是，当我遍历完数组后，如果数组元素个数不少于M个，则需要新的报数轮次，此时新一轮的遍历时，第一个元素的报数需要接着上一轮结束时的报数，这个也可以通过外部变量count来维护。

Java算法源码

import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    System.out.println(getResult(m));
  }

  public static String getResult(int m) {
    if (m <= 1 || m >= 100) return "ERROR!";

    ArrayList<Integer> arr = new ArrayList<>();
    for (int i = 1; i <= 100; i++) arr.add(i);

    return recursive(arr, m, 1);
  }

  public static String recursive(ArrayList<Integer> arr, int m, int count) {
    ArrayList<Integer> nxt = new ArrayList<>();

    for (Integer v : arr) {
      if (count == m + 1) {
        count = 1;
      }

      if (count++ % m != 0) {
        nxt.add(v);
      }
    }

    if (nxt.size() >= m) {
      return recursive(nxt, m, count);
    } else {
      StringJoiner sj = new StringJoiner(",");
      for (Integer v : nxt) sj.add(v + "");
      return sj.toString();
    }
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const m = parseInt(line);

  if (m <= 1 || m >= 100) {
    return console.log("ERROR!");
  }

  const arr = new Array(100).fill().map((_, index) => index + 1);

  console.log(recursive(arr, m, 1));
});

// 1 2 3 4 5 6 7 8 9 10
// 1 2 _ 4 5 _ 7 8 _ 10
// 1 _ _ 4 5 _ _ 8 _ 10
// _ _ _ 4 5 _ _ _ _ 10
// _ _ _ 4 _ _ _ _ _ 10

/* 算法逻辑 */
function recursive(arr, m, count) {
  arr = arr.filter(() => {
    if (count == m + 1) count = 1;
    return count++ % m;
  });

  if (arr.length >= m) {
    return recursive(arr, m, count);
  } else {
    return arr.join(",");
  }
}

Python算法源码

# 输入获取
m = int(input())


def recursive(arr, m, count):
    nxt = []

    for v in arr:
        if count == m + 1:
            count = 1

        if count % m != 0:
            nxt.append(v)

        count += 1

    if len(nxt) >= m:
        return recursive(nxt, m, count)
    else:
        return ",".join(map(str, nxt))


# 算法入口
def getResult():
    if m <= 1 or m >= 100:
        return "ERROR!"

    arr = [i for i in range(1, 101)]

    return recursive(arr, m, 1)


# 算法调用
print(getResult())

解法三：双端队列

还有一种非常简单，非常好理解的做法就是双端队列。

双端队列本质也是维护一个循环结构。

即，

当报数===m时，则队头出队，报数重置为1，对应此时新对头。

当报数 !== m时，则队头加入队尾，报数++，对应此时新队头。

Java算法源码

import java.util.ArrayDeque;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    System.out.println(getResult(m));
  }

  public static String getResult(int m) {
    if (m <= 1 || m >= 100) return "ERROR!";

    ArrayDeque<Integer> dq = new ArrayDeque<>();
    for (int i = 1; i <= 100; i++) dq.add(i);

    int idx = 1;
    while (dq.size() >= m) {
      if (idx == m) {
        dq.removeFirst();
        idx = 1;
      } else {
        dq.addLast(dq.removeFirst());
        idx++;
      }
    }

    StringJoiner sj = new StringJoiner(",");

    dq.stream().sorted((a, b) -> a - b).forEach(v -> sj.add(v + ""));

    return sj.toString();
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const m = parseInt(line);

  if (m <= 1 || m >= 100) {
    return console.log("ERROR!");
  }

  const dq = new Array(100).fill(0).map((_, idx) => idx + 1);

  let idx = 1;

  while (dq.length >= m) {
    if (idx === m) {
      dq.shift();
      idx = 1;
    } else {
      dq.push(dq.shift());
      idx++;
    }
  }

  console.log(dq.sort((a, b) => a - b).join());
});

Python算法源码

# 输入获取
m = int(input())


# 算法入口
def getResult():
    if m <= 1 or m >= 100:
        return "ERROR!"

    dq = [i for i in range(1, 101)]

    idx = 1

    while len(dq) >= m:
        if idx == m:
            dq.pop(0)
            idx = 1
        else:
            dq.append(dq.pop(0))
            idx += 1

    dq.sort()
    return ",".join(map(str, dq))


# 算法调用
print(getResult())

总结

上面三种解题思路，循环链表的性能是最优的，而基于数组filter的解法，会创建大量零时数组，造成内存浪费，基于双端队列的解法，本质也是基于数组，队头出队，对于数组来说，会导致整体数组元素前移一位，即每次队头出队，都有一次O(n)时间复杂度的元素位置调整，而同样的操作，对应于循环链表删除节点的操作， 只需要O(1)时间复杂度。

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

0

评论0

取消

首页 发现 VIP 我的

站点公告

没有账号？注册  忘记密码？