【2024年华为OD机试】(C卷,100分)- 约瑟夫问题（JavaScriptJava PythonC/C++）

在这里插入图片描述

一、问题描述

题目描述

输入一个由随机数组成的数列（数列中每个数均是大于 0 的整数，长度已知），和初始计数值 m。

从数列首位置开始计数，计数到 m 后，将数列该位置数值替换计数值 m，并将数列该位置数值出列，然后从下一位置重新开始计数，直到数列所有数值出列为止。如果计数到达数列尾段，则返回数列首位置继续计数。

请编程实现上述计数过程，同时输出数值出列的顺序。

示例：

输入的随机数列为：3,1,2,4，初始计数值 m=7，从数列首位置开始计数（数值 3 所在位置）。
- 第一轮计数出列数字为 2，计数值更新 m=2，出列后数列为 3,1,4，从数值 4 所在位置重新开始计数。
- 第二轮计数出列数字为 3，计数值更新 m=3，出列后数列为 1,4，从数值 1 所在位置开始计数。
- 第三轮计数出列数字为 1，计数值更新 m=1，出列后数列为 4，从数值 4 所在位置开始计数。
- 最后一轮计数出列数字为 4，计数过程完成。输出数值出列顺序为：2,3,1,4。

要求实现函数：

void array_iterate(int len, int input_array[], int m, int output_array[]);

输入描述

int len：输入数列的长度。
int input_array[]：输入的初始数列。
int m：初始计数值。

输出描述

int output_array[]：输出的数值出列顺序。

用例

输入：

3,1,2,4
4
7

输出：

2,3,1,4

说明：

第一行是初始数列 input_array。
第二行是初始数列的长度 len。
第三行是初始计数值 m。
输出数值出列顺序。

题目解析

本题是约瑟夫环的变种题。约瑟夫环问题通常描述为：n 个人围成一圈，从某个人开始报数，数到 m 的人出列，接着从下一个人重新开始报数，直到所有人都出列。本题的变种在于每次出列后，计数值 m 会更新为出列的数字。

解题思路

1. 使用双端队列

一种容易理解和实现的方法是使用双端队列（deque）。将 input_array 当作双端队列，从队头取出元素，判断此时计数是否为 m：

如果是，则将取出的元素加入 output_array，并将取出的元素的值赋值给 m，然后 len--，计数重置为 1。
如果不是，则将取出的元素塞回 input_array 的队尾，仅计数 ++。

然而，对于某些编程语言（如 JavaScript），数组实现的双端队列在每次头部元素出队时，都需要进行 O(n) 复杂度的数组元素前移操作，这会影响性能。

2. 使用循环链表

另一种更高效的方法是使用循环链表来模拟约瑟夫环。循环链表本身就实现了环形结构，其 head.prev = tail，tail.next = head。循环链表删除节点的复杂度是 O(1)，因此非常适合解决此类问题。

虽然某些编程语言（如 JavaScript）没有原生的循环链表结构，但我们可以自己实现一个简单的循环链表，只需要实现尾部新增节点操作即可。删除操作可以在实际业务中完成。

3. 实现步骤

初始化循环链表：将 input_array 中的元素依次加入循环链表中。
开始计数：从链表的头部开始，逐个节点计数，直到计数达到 m。
出列操作：当计数达到 m 时，将当前节点的值加入 output_array，并更新 m 为该节点的值。然后删除该节点，继续从下一个节点开始计数。
重复过程：重复上述步骤，直到链表中的所有节点都被删除。

通过这种方法，可以高效地解决约瑟夫环的变种问题，并输出数值出列的顺序。

二、JavaScript算法源码

以下是代码的详细注释和讲解，分为双端队列和循环链表两部分。

双端队列实现

代码结构

输入处理部分：
- 使用 readline 模块读取控制台输入。
- 将输入的三行数据分别解析为：
  - input_arr：初始数列。
  - len：数列的长度。
  - m：初始计数值。
- 当输入完成时，调用 array_iterate 函数处理逻辑，并输出结果。
核心逻辑部分：
- array_iterate 函数实现了双端队列的逻辑。
- 使用 input_arr 作为双端队列，通过 shift 和 push 操作模拟队列的头部出队和尾部入队。
- 通过计数 i 和计数值 m 判断是否需要将当前元素出列。

代码逐行注释

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");// 创建 readline 接口实例
const rl = readline.createInterface({input: process.stdin,  // 输入流output: process.stdout, // 输出流
});const lines = []; // 存储输入的行数据
rl.on("line", (line) => {lines.push(line); // 将每行输入存入 lines 数组// 当输入行数达到 3 行时，开始处理输入if (lines.length === 3) {const input_arr = lines[0].split(","); // 将第一行输入按逗号分隔为数组const len = lines[1]; // 获取第二行输入的数列长度const m = lines[2]; // 获取第三行输入的初始计数值const output_arr = []; // 初始化输出数组array_iterate(len, input_arr, m, output_arr); // 调用核心逻辑函数console.log(output_arr.join(",")); // 输出结果，用逗号分隔lines.length = 0; // 清空 lines 数组，准备下一次输入}
});// 核心逻辑函数
function array_iterate(len, input_arr, m, output_arr) {let i = 1; // 初始化计数器while (len > 0) { // 当数列长度大于 0 时循环const out = input_arr.shift(); // 从队列头部取出一个元素if (i == m) { // 如果计数器等于计数值 moutput_arr.push(out); // 将该元素加入输出数组m = out; // 更新计数值 m 为当前出列的元素值i = 1; // 重置计数器len--; // 数列长度减 1} else { // 如果计数器不等于计数值 minput_arr.push(out); // 将该元素重新加入队列尾部i++; // 计数器加 1}}
}

循环链表实现

代码结构

输入处理部分：
- 与双端队列实现相同，使用 readline 模块读取控制台输入。
- 将输入的三行数据解析为 input_arr、len 和 m。
- 当输入完成时，调用 array_iterate 函数处理逻辑，并输出结果。
核心逻辑部分：
- array_iterate 函数实现了循环链表的逻辑。
- 使用 CircularLinkedList 类初始化循环链表。
- 通过遍历链表，计数并删除节点，直到链表为空。
循环链表实现部分：
- Node 类表示链表的节点，包含 val（值）、next（下一个节点）和 prev（上一个节点）属性。
- CircularLinkedList 类表示循环链表，包含 head（头节点）、tail（尾节点）和 size（链表大小）属性。
- 提供了 append 方法用于向链表尾部添加节点，以及 init 方法用于初始化链表。

代码逐行注释

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");// 创建 readline 接口实例
const rl = readline.createInterface({input: process.stdin,  // 输入流output: process.stdout, // 输出流
});const lines = []; // 存储输入的行数据
rl.on("line", (line) => {lines.push(line); // 将每行输入存入 lines 数组// 当输入行数达到 3 行时，开始处理输入if (lines.length === 3) {const input_arr = lines[0].split(","); // 将第一行输入按逗号分隔为数组const len = lines[1]; // 获取第二行输入的数列长度const m = lines[2]; // 获取第三行输入的初始计数值const output_arr = []; // 初始化输出数组array_iterate(len, input_arr, m, output_arr); // 调用核心逻辑函数console.log(output_arr.join(",")); // 输出结果，用逗号分隔lines.length = 0; // 清空 lines 数组，准备下一次输入}
});// 核心逻辑函数
function array_iterate(len, input_arr, m, output_arr) {const cll = new CircularLinkedList(); // 创建循环链表实例cll.init(input_arr); // 使用输入数组初始化链表let cur = cll.head; // 初始化当前节点为链表头节点let i = 1; // 初始化计数器while (cll.size) { // 当链表大小大于 0 时循环if (i == m) { // 如果计数器等于计数值 mconst pre = cur.prev; // 获取当前节点的前一个节点const nxt = cur.next; // 获取当前节点的下一个节点pre.next = nxt; // 将前一个节点的 next 指向下一个节点nxt.prev = pre; // 将下一个节点的 prev 指向前一个节点m = cur.val; // 更新计数值 m 为当前节点的值output_arr.push(m); // 将当前节点的值加入输出数组cur.next = cur.prev = null; // 断开当前节点的连接cur = nxt; // 将当前节点移动到下一个节点i = 1; // 重置计数器cll.size--; // 链表大小减 1} else { // 如果计数器不等于计数值 mi++; // 计数器加 1cur = cur.next; // 将当前节点移动到下一个节点}}
}// 链表节点类
class Node {constructor(val) {this.val = val; // 节点值this.next = null; // 下一个节点this.prev = null; // 上一个节点}
}// 循环链表类
class CircularLinkedList {constructor() {this.head = null; // 链表头节点this.tail = null; // 链表尾节点this.size = 0; // 链表大小}// 向链表尾部添加节点append(val) {const node = new Node(val); // 创建新节点if (this.size) { // 如果链表不为空this.tail.next = node; // 将尾节点的 next 指向新节点node.prev = this.tail; // 将新节点的 prev 指向尾节点this.tail = node; // 更新尾节点为新节点} else { // 如果链表为空this.head = node; // 头节点为新节点this.tail = node; // 尾节点为新节点}this.head.prev = this.tail; // 头节点的 prev 指向尾节点this.tail.next = this.head; // 尾节点的 next 指向头节点this.size++; // 链表大小加 1}// 使用数组初始化链表init(arr) {arr.forEach((val) => {this.append(val); // 将数组中的每个值添加到链表中});}
}

总结

双端队列实现：
- 使用数组的 shift 和 push 方法模拟双端队列。
- 逻辑简单直观，但每次 shift 操作的时间复杂度为 O(n)，性能较低。
循环链表实现：
- 使用自定义的循环链表结构，删除节点的时间复杂度为 O(1)。
- 逻辑稍复杂，但性能更高，适合处理大规模数据。

两种实现方式均能正确解决问题，选择哪种方式取决于具体场景和性能需求。

三、Java算法源码

以下是 Java 使用 LinkedList 模拟双端队列 的代码详细注释和讲解：

代码结构

输入处理部分：
- 使用 Scanner 读取控制台输入。
- 将输入的三行数据分别解析为：
  - input_arr：初始数列。
  - len：数列的长度。
  - m：初始计数值。
- 调用 getResult 函数处理逻辑，并输出结果。
核心逻辑部分：
- 使用 LinkedList 模拟双端队列。
- 通过 removeFirst 和 add 方法实现队列的头部出队和尾部入队。
- 通过计数 i 和计数值 m 判断是否需要将当前元素出列。
输出处理部分：
- 使用 StringJoiner 将结果数组拼接为字符串，以逗号分隔。

代码逐行注释

import java.util.*;public class Main {public static void main(String[] args) {// 创建 Scanner 对象，用于读取控制台输入Scanner sc = new Scanner(System.in);// 读取第一行输入，按逗号分隔并转换为 Integer 数组Integer[] input_arr =Arrays.stream(sc.nextLine().split(",")) // 按逗号分隔字符串.map(Integer::parseInt)          // 将每个字符串转换为 Integer.toArray(Integer[]::new);        // 转换为 Integer 数组// 读取第二行输入，转换为整数 len（数列长度）int len = Integer.parseInt(sc.nextLine());// 读取第三行输入，转换为整数 m（初始计数值）int m = Integer.parseInt(sc.nextLine());// 调用核心逻辑函数，并输出结果System.out.println(getResult(input_arr, len, m));}// 核心逻辑函数public static String getResult(Integer[] input_arr, int len, int m) {// 使用 LinkedList 模拟双端队列，并初始化为输入数组LinkedList<Integer> dq = new LinkedList<>(Arrays.asList(input_arr));// 初始化输出数组ArrayList<Integer> output_arr = new ArrayList<>();int i = 1; // 初始化计数器while (len > 0) { // 当数列长度大于 0 时循环Integer out = dq.removeFirst(); // 从队列头部取出一个元素if (i == m) { // 如果计数器等于计数值 moutput_arr.add(out); // 将该元素加入输出数组m = out; // 更新计数值 m 为当前出列的元素值i = 1; // 重置计数器len--; // 数列长度减 1} else { // 如果计数器不等于计数值 mdq.add(out); // 将该元素重新加入队列尾部i++; // 计数器加 1}}// 使用 StringJoiner 将输出数组拼接为字符串，以逗号分隔StringJoiner sj = new StringJoiner(",");for (Integer ele : output_arr) {sj.add(ele + ""); // 将每个元素添加到 StringJoiner}return sj.toString(); // 返回拼接后的字符串}
}

代码逻辑详解

1. 输入处理

第一行输入：
- 使用 sc.nextLine() 读取一行输入。
- 使用 split(",") 按逗号分隔字符串，得到字符串数组。
- 使用 Arrays.stream 将字符串数组转换为 Integer 数组。
第二行输入：
- 使用 sc.nextLine() 读取一行输入，并转换为整数 len。
第三行输入：
- 使用 sc.nextLine() 读取一行输入，并转换为整数 m。

2. 核心逻辑

初始化双端队列：
- 使用 LinkedList 初始化双端队列 dq，并将输入数组 input_arr 转换为列表传入。
计数与出列：
- 初始化计数器 i 为 1。
- 使用 while 循环，当数列长度 len 大于 0 时继续循环。
- 每次从队列头部取出一个元素 out。
- 如果计数器 i 等于计数值 m：
  - 将 out 加入输出数组 output_arr。
  - 更新计数值 m 为 out。
  - 重置计数器 i 为 1。
  - 数列长度 len 减 1。
- 如果计数器 i 不等于计数值 m：
  - 将 out 重新加入队列尾部。
  - 计数器 i 加 1。

3. 输出处理

使用 StringJoiner 将输出数组 output_arr 拼接为字符串，以逗号分隔。
返回拼接后的字符串。

示例运行

输入

3,1,2,4
4
7

运行过程

初始化双端队列 dq 为 [3, 1, 2, 4]。
开始计数：
- 第一轮：i=1, m=7，取出 3，i 不等于 m，将 3 加入队列尾部，队列变为 [1, 2, 4, 3]。
- 第二轮：i=2, m=7，取出 1，i 不等于 m，将 1 加入队列尾部，队列变为 [2, 4, 3, 1]。
- 第三轮：i=3, m=7，取出 2，i 不等于 m，将 2 加入队列尾部，队列变为 [4, 3, 1, 2]。
- 第四轮：i=4, m=7，取出 4，i 不等于 m，将 4 加入队列尾部，队列变为 [3, 1, 2, 4]。
- 第五轮：i=5, m=7，取出 3，i 不等于 m，将 3 加入队列尾部，队列变为 [1, 2, 4, 3]。
- 第六轮：i=6, m=7，取出 1，i 不等于 m，将 1 加入队列尾部，队列变为 [2, 4, 3, 1]。
- 第七轮：i=7, m=7，取出 2，i 等于 m，将 2 加入输出数组，更新 m=2，队列变为 [4, 3, 1]。
- 继续循环，直到队列为空。

输出

2,3,1,4

总结

使用 LinkedList 模拟双端队列，逻辑清晰，代码简洁。
通过 removeFirst 和 add 方法实现队列的头部出队和尾部入队。
使用 StringJoiner 方便地拼接输出结果。

四、Python算法源码

以下是 Python 使用 deque 模拟双端队列 的代码详细注释和讲解：

代码结构

输入处理部分：
- 使用 input() 读取控制台输入。
- 将输入的三行数据分别解析为：
  - input_arr：初始数列，使用 deque 存储。
  - length：数列的长度。
  - m：初始计数值。
核心逻辑部分：
- 使用 deque 模拟双端队列。
- 通过 popleft 和 append 方法实现队列的头部出队和尾部入队。
- 通过计数 i 和计数值 m 判断是否需要将当前元素出列。
输出处理部分：
- 使用 map 和 join 将结果数组拼接为字符串，以逗号分隔。

代码逐行注释

from collections import deque  # 导入 deque 模块# 输入获取
input_arr = deque(list(map(int, input().split(","))))  # 读取第一行输入，按逗号分隔并转换为整数列表，存储到 deque 中
length = int(input())  # 读取第二行输入，转换为整数 length（数列长度）
m = int(input())  # 读取第三行输入，转换为整数 m（初始计数值）# 算法入口
def getResult():global input_arr  # 声明使用全局变量 input_arrglobal length  # 声明使用全局变量 lengthglobal m  # 声明使用全局变量 moutput_arr = []  # 初始化输出数组i = 1  # 初始化计数器while length > 0:  # 当数列长度大于 0 时循环out = input_arr.popleft()  # 从队列头部取出一个元素if i == m:  # 如果计数器等于计数值 moutput_arr.append(out)  # 将该元素加入输出数组m = out  # 更新计数值 m 为当前出列的元素值i = 1  # 重置计数器length -= 1  # 数列长度减 1else:  # 如果计数器不等于计数值 minput_arr.append(out)  # 将该元素重新加入队列尾部i += 1  # 计数器加 1return ",".join(map(str, output_arr))  # 将输出数组拼接为字符串，以逗号分隔# 算法调用
print(getResult())  # 调用核心逻辑函数，并输出结果

代码逻辑详解

1. 输入处理

第一行输入：
- 使用 input() 读取一行输入。
- 使用 split(",") 按逗号分隔字符串，得到字符串列表。
- 使用 map(int, ...) 将字符串列表转换为整数列表。
- 使用 deque 将整数列表转换为双端队列 input_arr。
第二行输入：
- 使用 input() 读取一行输入，并转换为整数 length。
第三行输入：
- 使用 input() 读取一行输入，并转换为整数 m。

2. 核心逻辑

初始化输出数组：
- 创建一个空列表 output_arr，用于存储出列的元素。
计数与出列：
- 初始化计数器 i 为 1。
- 使用 while 循环，当数列长度 length 大于 0 时继续循环。
- 每次从队列头部取出一个元素 out。
- 如果计数器 i 等于计数值 m：
  - 将 out 加入输出数组 output_arr。
  - 更新计数值 m 为 out。
  - 重置计数器 i 为 1。
  - 数列长度 length 减 1。
- 如果计数器 i 不等于计数值 m：
  - 将 out 重新加入队列尾部。
  - 计数器 i 加 1。

3. 输出处理

使用 map(str, output_arr) 将输出数组 output_arr 中的元素转换为字符串。
使用 ",".join(...) 将字符串列表拼接为以逗号分隔的字符串。
返回拼接后的字符串。

示例运行

输入

3,1,2,4
4
7

运行过程

初始化双端队列 input_arr 为 deque([3, 1, 2, 4])。
开始计数：
- 第一轮：i=1, m=7，取出 3，i 不等于 m，将 3 加入队列尾部，队列变为 deque([1, 2, 4, 3])。
- 第二轮：i=2, m=7，取出 1，i 不等于 m，将 1 加入队列尾部，队列变为 deque([2, 4, 3, 1])。
- 第三轮：i=3, m=7，取出 2，i 不等于 m，将 2 加入队列尾部，队列变为 deque([4, 3, 1, 2])。
- 第四轮：i=4, m=7，取出 4，i 不等于 m，将 4 加入队列尾部，队列变为 deque([3, 1, 2, 4])。
- 第五轮：i=5, m=7，取出 3，i 不等于 m，将 3 加入队列尾部，队列变为 deque([1, 2, 4, 3])。
- 第六轮：i=6, m=7，取出 1，i 不等于 m，将 1 加入队列尾部，队列变为 deque([2, 4, 3, 1])。
- 第七轮：i=7, m=7，取出 2，i 等于 m，将 2 加入输出数组，更新 m=2，队列变为 deque([4, 3, 1])。
- 继续循环，直到队列为空。

输出

2,3,1,4

总结

使用 deque 模拟双端队列，逻辑清晰，代码简洁。
通过 popleft 和 append 方法实现队列的头部出队和尾部入队。
使用 map 和 join 方便地拼接输出结果。

五、C/C++算法源码：

以下是 C语言 和 C++ 实现的代码，包含详细的中文注释和讲解。

C语言实现

代码结构

链表节点定义：
- ListNode 结构体表示链表节点，包含 ele（节点值）和 next（指向下一个节点的指针）。
链表定义：
- LinkedList 结构体表示链表，包含 size（链表大小）、head（头节点指针）和 tail（尾节点指针）。
链表操作函数：
- new_LinkedList：初始化链表。
- addLast_LinkedList：向链表尾部添加节点。
- removeFirst：移除链表头部节点并返回其值。
主函数逻辑：
- 读取输入数据并初始化链表。
- 使用链表模拟双端队列，实现计数和出列逻辑。
- 输出结果。

代码逐行注释

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义链表节点结构体
typedef struct ListNode {int ele; // 节点值struct ListNode* next; // 指向下一个节点的指针
} ListNode;// 定义链表结构体
typedef struct {int size; // 链表大小ListNode* head; // 头节点指针ListNode* tail; // 尾节点指针
} LinkedList;// 初始化链表
LinkedList* new_LinkedList() {LinkedList* link = (LinkedList*)malloc(sizeof(LinkedList)); // 分配内存link->size = 0; // 初始化大小为 0link->head = NULL; // 头节点指针为空link->tail = NULL; // 尾节点指针为空return link;
}// 向链表尾部添加节点
void addLast_LinkedList(LinkedList* link, int ele) {ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 创建新节点node->ele = ele; // 设置节点值node->next = NULL; // 新节点的 next 指针为空if (link->size == 0) { // 如果链表为空link->head = node; // 头节点指向新节点link->tail = node; // 尾节点指向新节点} else { // 如果链表不为空link->tail->next = node; // 尾节点的 next 指向新节点link->tail = node; // 更新尾节点为新节点}link->size++; // 链表大小加 1
}// 移除链表头部节点并返回其值
int removeFirst(LinkedList* link) {if (link->size == 0) exit(-1); // 如果链表为空，退出程序ListNode* removed = link->head; // 获取头节点if (link->size == 1) { // 如果链表只有一个节点link->head = NULL; // 头节点指针为空link->tail = NULL; // 尾节点指针为空} else { // 如果链表有多个节点link->head = link->head->next; // 头节点指向下一个节点}link->size--; // 链表大小减 1int res = removed->ele; // 获取移除节点的值free(removed); // 释放移除节点的内存return res; // 返回移除节点的值
}int main() {LinkedList* dq = new_LinkedList(); // 初始化链表// 读取输入数列int num;while (scanf("%d", &num)) { // 读取整数addLast_LinkedList(dq, num); // 将整数添加到链表尾部if (getchar() != ',') break; // 如果下一个字符不是逗号，结束输入}int len;scanf("%d", &len); // 读取数列长度int m;scanf("%d", &m); // 读取初始计数值LinkedList* output_arr = new_LinkedList(); // 初始化输出链表int i = 1; // 初始化计数器while (len > 0) { // 当数列长度大于 0 时循环int out = removeFirst(dq); // 移除链表头部节点并获取其值if (i == m) { // 如果计数器等于计数值 maddLast_LinkedList(output_arr, out); // 将值添加到输出链表m = out; // 更新计数值 mi = 1; // 重置计数器len--; // 数列长度减 1} else { // 如果计数器不等于计数值 maddLast_LinkedList(dq, out); // 将值重新添加到链表尾部i++; // 计数器加 1}}// 输出结果char res[100000] = ""; // 初始化结果字符串ListNode* cur = output_arr->head; // 获取输出链表的头节点while (cur != NULL) { // 遍历输出链表char tmp[10];sprintf(tmp, "%d", cur->ele); // 将节点值转换为字符串strcat(res, tmp); // 将字符串拼接到结果中cur = cur->next; // 移动到下一个节点if (cur != NULL) { // 如果下一个节点不为空strcat(res, ","); // 添加逗号分隔符}}puts(res); // 输出结果字符串return 0;
}

C++实现

代码结构

链表节点定义：
- ListNode 类表示链表节点，包含 ele（节点值）和 next（指向下一个节点的指针）。
链表定义：
- LinkedList 类表示链表，包含 size（链表大小）、head（头节点指针）和 tail（尾节点指针）。
链表操作函数：
- LinkedList 构造函数：初始化链表。
- addLast：向链表尾部添加节点。
- removeFirst：移除链表头部节点并返回其值。
主函数逻辑：
- 读取输入数据并初始化链表。
- 使用链表模拟双端队列，实现计数和出列逻辑。
- 输出结果。

代码逐行注释

#include <iostream>
#include <sstream>
#include <string>
using namespace std;// 定义链表节点类
class ListNode {
public:int ele; // 节点值ListNode* next; // 指向下一个节点的指针ListNode(int val) : ele(val), next(nullptr) {} // 构造函数
};// 定义链表类
class LinkedList {
public:int size; // 链表大小ListNode* head; // 头节点指针ListNode* tail; // 尾节点指针LinkedList() : size(0), head(nullptr), tail(nullptr) {} // 构造函数// 向链表尾部添加节点void addLast(int ele) {ListNode* node = new ListNode(ele); // 创建新节点if (size == 0) { // 如果链表为空head = node; // 头节点指向新节点tail = node; // 尾节点指向新节点} else { // 如果链表不为空tail->next = node; // 尾节点的 next 指向新节点tail = node; // 更新尾节点为新节点}size++; // 链表大小加 1}// 移除链表头部节点并返回其值int removeFirst() {if (size == 0) exit(-1); // 如果链表为空，退出程序ListNode* removed = head; // 获取头节点if (size == 1) { // 如果链表只有一个节点head = nullptr; // 头节点指针为空tail = nullptr; // 尾节点指针为空} else { // 如果链表有多个节点head = head->next; // 头节点指向下一个节点}size--; // 链表大小减 1int res = removed->ele; // 获取移除节点的值delete removed; // 释放移除节点的内存return res; // 返回移除节点的值}
};int main() {LinkedList dq; // 初始化链表// 读取输入数列string input;getline(cin, input); // 读取一行输入stringstream ss(input); // 使用字符串流处理输入string token;while (getline(ss, token, ',')) { // 按逗号分隔输入dq.addLast(stoi(token)); // 将字符串转换为整数并添加到链表尾部}int len;cin >> len; // 读取数列长度int m;cin >> m; // 读取初始计数值LinkedList output_arr; // 初始化输出链表int i = 1; // 初始化计数器while (len > 0) { // 当数列长度大于 0 时循环int out = dq.removeFirst(); // 移除链表头部节点并获取其值if (i == m) { // 如果计数器等于计数值 moutput_arr.addLast(out); // 将值添加到输出链表m = out; // 更新计数值 mi = 1; // 重置计数器len--; // 数列长度减 1} else { // 如果计数器不等于计数值 mdq.addLast(out); // 将值重新添加到链表尾部i++; // 计数器加 1}}// 输出结果string res;ListNode* cur = output_arr.head; // 获取输出链表的头节点while (cur != nullptr) { // 遍历输出链表res += to_string(cur->ele); // 将节点值转换为字符串并拼接到结果中cur = cur->next; // 移动到下一个节点if (cur != nullptr) { // 如果下一个节点不为空res += ","; // 添加逗号分隔符}}cout << res << endl; // 输出结果字符串return 0;
}

总结

C语言实现：
- 使用结构体和指针实现链表。
- 通过手动管理内存（malloc 和 free）实现链表操作。
- 代码稍显冗长，但逻辑清晰。
C++实现：
- 使用类和面向对象特性实现链表。
- 通过 new 和 delete 管理内存。
- 代码更简洁，可读性更高。

两种实现方式均能正确解决问题，选择哪种方式取决于具体场景和编程语言偏好。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

机试是进入技术面的第一关：
华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。
技术面试需要手撕代码：
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。
入职后的可信考试：
入职华为后，还需要通过“可信考试”。可信考试分为三个等级：
- 入门级：主要考察基础算法与编程能力。
- 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
- 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

关注历年真题：
- 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
- 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。
适应新题目：
- E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
- 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。
掌握常见算法：
华为OD考试通常涉及以下算法和数据结构：
- 排序算法（快速排序、归并排序等）
- 动态规划（背包问题、最长公共子序列等）
- 贪心算法
- 栈、队列、链表的操作
- 图论（最短路径、最小生成树等）
- 滑动窗口、双指针算法
保持编程规范：
- 注重代码的可读性和注释的清晰度。
- 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

官方参考：
- 华为招聘官网或相关的招聘平台会有一些参考信息。
- 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
加入刷题社区：
- 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
- 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。
寻找系统性的教程：
- 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
- 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

本地编写代码
- 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。
调整心态，保持冷静
- 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。
输入输出完整性
- 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。
快捷键使用
- 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
- 避免使用 Ctrl+S，以免触发浏览器的保存功能。
浏览器要求
- 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。
交卷相关
- 答题前，务必仔细查看题目示例，避免遗漏要求。
- 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
- 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。
时间和分数安排
- 总时间：150 分钟；总分：400 分。
- 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。
考试环境准备
- 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
- 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。
技术问题处理
- 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
- 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。