【2024年华为OD机试】 (C卷,100分)- 停车场车辆统计（Java JS PythonC/C++）

ops/2025/1/16 22:53:05/

在这里插入图片描述

一、问题描述

题目描述

特定大小的停车场，数组 cars[] 表示，其中 1 表示有车，0 表示没车。

车辆大小不一，小车占一个车位（长度1），货车占两个车位（长度2），卡车占三个车位（长度3）。

统计停车场最少可以停多少辆车，返回具体的数目。

输入描述

整型字符串数组 cars[]，其中 1 表示有车，0 表示没车，数组长度小于 1000。

输出描述

整型数字字符串，表示最少停车数目。

用例

输入

1,0,1

输出

2

说明
1 个小车占第 1 个车位

第二个车位空

1 个小车占第 3 个车位

最少有两辆车

输入

1,1,0,0,1,1,1,0,1

输出

3

说明
1 个货车占第 1、2 个车位

第 3、4 个车位空

1 个卡车占第 5、6、7 个车位

第 8 个车位空

1 个小车占第 9 个车位

最少 3 辆车

题目解析

这道题的意思应该是：给定了车位占用情况，如 1,1,0,0,1,1,1,0,1，这种车位占用情况，可能停了 6 辆车，即每个 1 都停了一个小车，这是最多的情况，但是现在要求最少可能停几辆车。

解题思路
  1. 优先处理大车：为了使停车数量最少，应优先考虑停放占用车位多的车辆，即先处理卡车（占3个车位），再处理货车（占2个车位），最后处理小车（占1个车位）。
  2. 遍历数组：
    • 处理卡车：遍历数组，查找连续的三个 1（111），每找到一个，计数加 1，并将这三个位置标记为已处理（例如，可以将其置为 0 或其他标记）。
    • 处理货车：继续遍历数组，查找连续的两个 1（11），每找到一个，计数加 1，并将这两个位置标记为已处理。
    • 处理小车：最后遍历数组，查找单个的 1，每找到一个，计数加 1，并将该位置标记为已处理。
  3. 统计结果：遍历完成后，计数器中的值即为最少停车数目。

通过这种方法，我们可以确保在给定的车位占用情况下，停放的车辆数量最少。时间复杂度为 O(n)，其中 n 是数组的长度，因为我们只需要遍历数组几次。

二、JavaScript算法源码

以下是 JavaScript 代码的详细中文注释和讲解：

JavaScript 代码实现

javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline"); // 导入 readline 模块，用于读取控制台输入// 创建 readline.Interface 实例，用于处理输入和输出
const rl = readline.createInterface({input: process.stdin,  // 设置输入流为标准输入output: process.stdout, // 设置输出流为标准输出
});// 监听 'line' 事件，当用户输入一行内容并按下回车时触发
rl.on("line", (line) => {// 对输入的行内容进行处理let str = line.replaceAll(",", "") // 去掉字符串中的所有逗号.replaceAll("111", "x") // 将连续的三个 "1" 替换为 "x".replaceAll("11", "x")  // 将连续的两个 "1" 替换为 "x".replaceAll("1", "x");  // 将单个的 "1" 替换为 "x"let count = 0; // 定义变量 count，用于统计 "x" 的数量// 使用 while 循环统计 "x" 的数量while (true) {let index = str.indexOf("x"); // 查找字符串中第一个 "x" 的位置if (index !== -1) { // 如果找到 "x"count++; // 将 count 的值加 1str = str.slice(index + 1); // 截取字符串，从当前 "x" 的下一个字符开始} else { // 如果没有找到 "x"break; // 退出循环}}console.log(count); // 输出统计结果
});

代码讲解

1. 导入 readline 模块

  • const readline = require("readline");：导入 readline 模块，用于读取控制台输入。

2. 创建 readline.Interface 实例

  • rl = readline.createInterface({ input: process.stdin, output: process.stdout });：
    • 创建一个 readline.Interface 实例，用于处理控制台的输入和输出。
    • input: process.stdin：设置输入流为标准输入。
    • output: process.stdout：设置输出流为标准输出。

3. 监听 line 事件

  • rl.on("line", (line) => { ... });：
    • 监听 line 事件，当用户输入一行内容并按下回车时触发。
    • 回调函数中的 line 参数是用户输入的内容。

4. 处理输入字符串

  • 对输入的行内容进行处理：
    • replaceAll(",", "")：去掉字符串中的所有逗号。
    • replaceAll("111", "x")：将连续的三个 "1" 替换为 "x"。
    • replaceAll("11", "x")：将连续的两个 "1" 替换为 "x"。
    • replaceAll("1", "x")：将单个的 "1" 替换为 "x"。

5. 统计 "x" 的数量

  • 使用 while 循环统计 "x" 的数量：
    • let index = str.indexOf("x");：查找字符串中第一个 "x" 的位置。
    • 如果找到 "x"（index !== -1）：
      • 将 count 的值加 1。
      • 使用 str.slice(index + 1) 截取字符串，从当前 "x" 的下一个字符开始。
    • 如果没有找到 "x"，退出循环。

6. 输出统计结果

  • console.log(count);：输出统计结果 count。

示例分析

示例 1

输入：

1,1,1,1,1

输出：

2

解释：

  • 输入字符串为 "1,1,1,1,1"。
  • 去掉逗号后，字符串变为 "11111"。
  • 将连续的三个 "1" 替换为 "x"，字符串变为 "x11"。
  • 将连续的两个 "1" 替换为 "x"，字符串变为 "xx"。
  • 统计 "x" 的数量为 2。

示例 2

输入：

1,1,1,1

输出：

2

解释：

  • 输入字符串为 "1,1,1,1"。
  • 去掉逗号后，字符串变为 "1111"。
  • 将连续的三个 "1" 替换为 "x"，字符串变为 "x1"。
  • 将单个的 "1" 替换为 "x"，字符串变为 "xx"。
  • 统计 "x" 的数量为 2。

注意事项

  1. 替换顺序：

    • 代码中替换的顺序非常重要：
      • 先替换连续的三个 "1"，再替换连续的两个 "1"，最后替换单个的 "1"。
      • 如果顺序颠倒，可能会导致统计结果不准确。

  2. 统计逻辑：

    • 使用 while 循环和 indexOf 方法统计 "x" 的数量。
    • 每次找到 "x" 后，截取字符串从当前 "x" 的下一个字符开始，避免重复统计。

  3. 输入格式：

    • 输入字符串中可能包含逗号，需要先去掉逗号再进行替换。

总结

  • 该代码通过字符串替换和循环统计，实现了对特定字符 "x" 的计数。
  • 代码逻辑清晰，但需要注意替换顺序和统计逻辑。
  • 如果有其他问题，欢迎继续提问！

三、Java算法源码

以下是 Java 代码的详细中文注释和讲解：

Java 代码实现

java">import java.util.Scanner; // 导入 Scanner 类，用于读取用户输入public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in); // 创建 Scanner 对象，用于读取输入// 读取用户输入的一行字符串，并对其进行处理String str =sc.nextLine() // 读取用户输入的一行字符串.replaceAll(",", "") // 去掉字符串中的所有逗号.replaceAll("111", "x") // 将连续的三个 "1" 替换为 "x".replaceAll("11", "x")  // 将连续的两个 "1" 替换为 "x".replaceAll("1", "x");  // 将单个的 "1" 替换为 "x"int ans = 0; // 定义变量 ans，用于统计 "x" 的数量// 遍历处理后的字符串，统计 "x" 的数量for (int i = 0; i < str.length(); i++) {if (str.charAt(i) == 'x') { // 如果当前字符是 'x'ans++; // 将 ans 的值加 1}}System.out.println(ans); // 输出统计结果}
}

代码讲解

1. 导入 Scanner 类

  • import java.util.Scanner;：导入 Scanner 类，用于读取用户输入。

2. 主函数 main

  • 功能：读取用户输入的一行字符串，对其进行处理，并统计特定字符的数量。
  • 逻辑：
    1. 创建 Scanner 对象 sc，用于读取用户输入。
    2. 读取用户输入的一行字符串，并对其进行处理：
      • 使用 replaceAll(",", "") 去掉字符串中的所有逗号。
      • 使用 replaceAll("111", "x") 将连续的三个 "1" 替换为 "x"。
      • 使用 replaceAll("11", "x") 将连续的两个 "1" 替换为 "x"。
      • 使用 replaceAll("1", "x") 将单个的 "1" 替换为 "x"。
    3. 定义变量 ans，用于统计 "x" 的数量。
    4. 遍历处理后的字符串，统计 "x" 的数量：
      • 使用 str.charAt(i) 获取字符串中第 i 个字符。
      • 如果当前字符是 'x'，则将 ans 的值加 1。
    5. 输出统计结果 ans。

示例分析

示例 1

输入：

1,1,1,1,1

输出：

2

解释：

  • 输入字符串为 "1,1,1,1,1"。
  • 去掉逗号后，字符串变为 "11111"。
  • 将连续的三个 "1" 替换为 "x"，字符串变为 "x11"。
  • 将连续的两个 "1" 替换为 "x"，字符串变为 "xx"。
  • 统计 "x" 的数量为 2。

示例 2

输入：

1,1,1,1

输出：

1

解释：

  • 输入字符串为 "1,1,1,1"。
  • 去掉逗号后，字符串变为 "1111"。
  • 将连续的三个 "1" 替换为 "x"，字符串变为 "x1"。
  • 将单个的 "1" 替换为 "x"，字符串变为 "xx"。
  • 统计 "x" 的数量为 2。

注意事项

  1. 替换顺序：

    • 代码中替换的顺序非常重要：
      • 先替换连续的三个 "1"，再替换连续的两个 "1"，最后替换单个的 "1"。
      • 如果顺序颠倒，可能会导致统计结果不准确。

  2. 输入格式：

    • 输入字符串中可能包含逗号，需要先去掉逗号再进行替换。

  3. 统计逻辑：

    • 统计的是替换后的 "x" 的数量，而不是原始的 "1" 的数量。

总结

  • 该代码通过字符串替换和遍历统计，实现了对特定字符 "x" 的计数。
  • 代码逻辑清晰，但需要注意替换顺序和输入格式。
  • 如果有其他问题，欢迎继续提问！

四、Python算法源码

以下是 Python 代码的详细中文注释和讲解：

Python 代码实现

python"># 读取用户输入的一行字符串，并对其进行处理
s = input()  # 读取用户输入的一行字符串
s = s.replace(",", "")  # 去掉字符串中的所有逗号
s = s.replace("111", "x")  # 将连续的三个 "1" 替换为 "x"
s = s.replace("11", "x")   # 将连续的两个 "1" 替换为 "x"
s = s.replace("1", "x")    # 将单个的 "1" 替换为 "x"ans = 0  # 定义变量 ans，用于统计 "x" 的数量# 遍历处理后的字符串，统计 "x" 的数量
for c in s:  # 遍历字符串中的每一个字符if c == 'x':  # 如果当前字符是 'x'ans += 1  # 将 ans 的值加 1print(ans)  # 输出统计结果

代码讲解

1. 读取用户输入

  • s = input()：读取用户输入的一行字符串，并将其赋值给变量 s。

2. 字符串替换

  • s = s.replace(",", "")：去掉字符串中的所有逗号。
  • s = s.replace("111", "x")：将连续的三个 "1" 替换为 "x"。
  • s = s.replace("11", "x")：将连续的两个 "1" 替换为 "x"。
  • s = s.replace("1", "x")：将单个的 "1" 替换为 "x"。

3. 统计 "x" 的数量

  • ans = 0：定义变量 ans，用于统计 "x" 的数量，初始值为 0。
  • for c in s:：遍历处理后的字符串 s 中的每一个字符。
    • if c == 'x':：如果当前字符是 'x'。
      • ans += 1：将 ans 的值加 1。

4. 输出结果

  • print(ans)：输出统计结果 ans。

示例分析

示例 1

输入：

1,1,1,1,1

输出：

2

解释：

  • 输入字符串为 "1,1,1,1,1"。
  • 去掉逗号后，字符串变为 "11111"。
  • 将连续的三个 "1" 替换为 "x"，字符串变为 "x11"。
  • 将连续的两个 "1" 替换为 "x"，字符串变为 "xx"。
  • 统计 "x" 的数量为 2。

示例 2

输入：

1,1,1,1

输出：

2

解释：

  • 输入字符串为 "1,1,1,1"。
  • 去掉逗号后，字符串变为 "1111"。
  • 将连续的三个 "1" 替换为 "x"，字符串变为 "x1"。
  • 将单个的 "1" 替换为 "x"，字符串变为 "xx"。
  • 统计 "x" 的数量为 2。

注意事项

  1. 替换顺序：

    • 代码中替换的顺序非常重要：
      • 先替换连续的三个 "1"，再替换连续的两个 "1"，最后替换单个的 "1"。
      • 如果顺序颠倒，可能会导致统计结果不准确。

  2. 输入格式：

    • 输入字符串中可能包含逗号，需要先去掉逗号再进行替换。

  3. 统计逻辑：

    • 统计的是替换后的 "x" 的数量，而不是原始的 "1" 的数量。

总结

  • 该代码通过字符串替换和遍历统计，实现了对特定字符 "x" 的计数。
  • 代码逻辑清晰，但需要注意替换顺序和输入格式。
  • 如果有其他问题，欢迎继续提问！

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

以下是 C 语言 和 C++ 版本的代码实现，并附上详细的中文注释和讲解：

C 语言代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>/*!* 字符串替换函数* @param s 主串* @param sub 目标子串* @param rep 替换子串* @return 一个新串，新串等价于主串将自身目标子串部分替换为rep串的结果*/
char *replaceAll(char *s, char *sub, char *rep) {// 新串char *res = (char *) calloc(strlen(s), sizeof(char)); // 分配内存，用于存储替换后的字符串// 目标子串长度int len = (int) strlen(sub);// 在主串中找到目标子串第一次出现的位置char *t = strstr(s, sub); // 查找子串 sub 在主串 s 中的位置while (t != NULL) { // 如果找到子串t[0] = '\0'; // 将子串起始位置置为字符串结束符strcat(res, s); // 将主串中目标子串之前的部分拼接到 res 中strcat(res, rep); // 将替换子串拼接到 res 中s = t + len; // 更新主串起始位置，跳过已处理的部分t = strstr(s, sub); // 继续查找下一个目标子串}strcat(res, s); // 将主串剩余部分拼接到 res 中return res; // 返回替换后的字符串
}int main() {char s[1000] = {'\0'}; // 定义字符数组 s，用于存储用户输入int s_len = 0; // 记录输入字符串的长度char c;while (scanf("%c", &c)) { // 逐个读取字符s[s_len++] = c; // 将字符存入数组 s 中if (getchar() != ',') break; // 如果下一个字符不是逗号，结束输入}// 先把卡车，即111的停车情况先弄出来(替换为x)，再将火车，即11的停车情况弄出来(替换为x)，最后再弄小车1的情况(替换为x)。char *res = replaceAll(replaceAll(replaceAll(s, "111", "x"), "11", "x"), "1", "x");int count = 0; // 定义变量 count，用于统计 "x" 的数量// 统计x字符的数量，即为最少停车数量int i = 0;while (res[i] != '\0') { // 遍历替换后的字符串if (res[i] == 'x') { // 如果当前字符是 'x'count++; // 将 count 的值加 1}i++;}printf("%d\n", count); // 输出统计结果return 0; // 程序正常结束
}

C++ 代码

#include <iostream>
#include <string>
using namespace std;/*!* 字符串替换函数* @param s 主串* @param sub 目标子串* @param rep 替换子串* @return 一个新串，新串等价于主串将自身目标子串部分替换为rep串的结果*/
string replaceAll(string s, string sub, string rep) {size_t pos = 0; // 用于记录子串的位置while ((pos = s.find(sub, pos)) != string::npos) { // 查找子串 sub 在主串 s 中的位置s.replace(pos, sub.length(), rep); // 将子串替换为 reppos += rep.length(); // 更新查找起始位置，跳过已替换的部分}return s; // 返回替换后的字符串
}int main() {string s; // 定义字符串 s，用于存储用户输入char c;while (cin >> c) { // 逐个读取字符s += c; // 将字符拼接到字符串 s 中if (cin.get() != ',') break; // 如果下一个字符不是逗号，结束输入}// 先把卡车，即111的停车情况先弄出来(替换为x)，再将火车，即11的停车情况弄出来(替换为x)，最后再弄小车1的情况(替换为x)。string res = replaceAll(replaceAll(replaceAll(s, "111", "x"), "11", "x"), "1", "x");int count = 0; // 定义变量 count，用于统计 "x" 的数量// 统计x字符的数量，即为最少停车数量for (char ch : res) { // 遍历替换后的字符串if (ch == 'x') { // 如果当前字符是 'x'count++; // 将 count 的值加 1}}cout << count << endl; // 输出统计结果return 0; // 程序正常结束
}

代码讲解

1. 字符串替换函数 replaceAll

  • C 语言：
    • 使用 strstr 查找子串位置，并通过 strcat 拼接字符串。
    • 需要手动管理内存（分配和释放）。
  • C++：
    • 使用 string::find 查找子串位置，并通过 string::replace 替换子串。
    • 无需手动管理内存，string 类会自动处理。

2. 主函数 main

  • C 语言：
    • 使用字符数组 char s[1000] 存储输入。
    • 使用 scanf 和 getchar 逐个读取字符。
  • C++：
    • 使用 string 类存储输入。
    • 使用 cin 和 cin.get() 逐个读取字符。

3. 替换逻辑

  • 先替换连续的三个 "1" 为 "x"，再替换连续的两个 "1" 为 "x"，最后替换单个的 "1" 为 "x"。
  • 替换顺序非常重要，确保优先匹配更长的子串。

4. 统计逻辑

  • 遍历替换后的字符串，统计 "x" 的数量。

示例分析

示例 1

输入：

1,1,1,1,1

输出：

2

解释：

  • 输入字符串为 "1,1,1,1,1"。
  • 去掉逗号后，字符串变为 "11111"。
  • 将连续的三个 "1" 替换为 "x"，字符串变为 "x11"。
  • 将连续的两个 "1" 替换为 "x"，字符串变为 "xx"。
  • 统计 "x" 的数量为 2。

示例 2

输入：

1,1,1,1

输出：

2

解释：

  • 输入字符串为 "1,1,1,1"。
  • 去掉逗号后，字符串变为 "1111"。
  • 将连续的三个 "1" 替换为 "x"，字符串变为 "x1"。
  • 将单个的 "1" 替换为 "x"，字符串变为 "xx"。
  • 统计 "x" 的数量为 2。

注意事项

  1. 内存管理：

    • C 语言：需要手动释放 replaceAll 函数中分配的内存。
    • C++：无需手动管理内存，string 类会自动处理。

  2. 替换顺序：

    • 先替换更长的子串（如 "111"），再替换较短的子串（如 "11" 和 "1"）。

  3. 输入格式：

    • 输入字符串中可能包含逗号，需要先去掉逗号再进行替换。

总结

  • C 语言 和 C++ 版本的代码逻辑一致，但实现方式有所不同。
  • C++ 版本利用了 string 类的特性，代码更简洁且易于维护。
  • 如果有其他问题，欢迎继续提问！

http://www.ppmy.cn/ops/150657.html

相关文章

微信小程序集成Vant Weapp移动端开发的框架

微信小程序集成Vant Weapp移动端开发的框架

什么是Vant Weapp Vant 是一个轻量、可靠的移动端组件库&#xff0c;于 2017 年开源。 目前 Vant 官方提供了 Vue 2 版本、Vue 3 版本和微信小程序版本&#xff0c;并由社区团队维护 React 版本和支付宝小程序版本。 官网地睛&#xff1a;介绍 - Vant Weapp (vant-ui.gith…
阅读更多...
JSON.stringify（res，null，2）的含义

JSON.stringify（res，null，2）的含义

JSON.stringify(res, null, 2) 是 JavaScript 中将对象转换为 JSON 字符串的方法&#xff0c;具体说明如下&#xff1a; 参数解释 res&#xff1a;要转换的对象。它可以是 JavaScript 中的任意类型&#xff0c;如对象、数组、字符串、数字等。例如&#xff0c;{name: "K…
阅读更多...
使用vue3实现语音交互的前端页面

使用vue3实现语音交互的前端页面

代码地址&#xff1a;https://github.com/ZZD3627/my-third-vue.git 需求 1.前端实现录音并将音频传到通过http请求将音频传递到后端 2.基于后端识别的语音及后端返回的内容进行语音沟通实现 1.使用MediaRecorder在前端使用录音功能 2.使用SpeechSynthesis实现将后端传来的文…
阅读更多...
深度解析 React 中 setState 的原理：同步与异步的交织

深度解析 React 中 setState 的原理：同步与异步的交织

在 React 框架的核心机制里&#xff0c;setState是实现动态交互与数据驱动视图更新的关键枢纽。深入理解setState的工作原理&#xff0c;尤其是其同步与异步的特性&#xff0c;对于编写高效、稳定且可预测的 React 应用至关重要。 一、setState 的基础认知 在 React 组件中&a…
阅读更多...
Vue.js devtools插件点击Root失效或不显示数据甚至没有Root的解决方法

Vue.js devtools插件点击Root失效或不显示数据甚至没有Root的解决方法

文章目录 一、问题描述二、原因分析三、解决方法 一、问题描述 在vue开发者工具devTools插件中&#xff0c;有时候会遇到没有Root或点击Root失效等问题。 正常情况如下图&#xff1a; Vue工具devtools没有root 二、原因分析 源码如下&#xff1a; 上图中的示例是name字…
阅读更多...
C51交通控制系统的设计与实现

C51交通控制系统的设计与实现

实验要求&#xff1a; 本题目拟设计一个工作在十字路口的交通信号灯控制系统&#xff0c;设东西方向为主干道A&#xff0c;南北方向为辅助干道B。要求&#xff1a;&#xff08;1&#xff09;用发光二极管模拟交通灯信号&#xff1b;&#xff08;2&#xff09;灵活控制主、辅干…
阅读更多...
插入排序与霍纳规则

插入排序与霍纳规则

参考书&#xff1a;机械工业出版社《算法导论》第二版 插入排序 插入排序来自扑克牌的灵感&#xff0c;每次抽牌都要从洗好的牌堆里抽一张&#xff0c;然后与自己现有的牌比较&#xff0c;插入到合适的位置 算法步骤 由此可以看到&#xff0c;插入排序时对元素进行这样一种操…
阅读更多...
【蓝桥杯】Python算法——快速幂

【蓝桥杯】Python算法——快速幂

零、前言 距离25年蓝桥杯还有大概三个月时间&#xff0c;接下来重点应该会放在蓝桥杯备考方向&#xff0c;一起努力&#xff0c;一起加油 一、快速幂 如何快速求 a b p a^bp abp&#xff1f;如果直接循环aaa…毫无疑问时间复杂度是很大的&#xff0c;那么怎么降低计算量呢&…
阅读更多...
最新文章

Copyright @ 2022~2023