当前位置： 首页 > article >正文

【2024年华为OD机试】(C卷,100分)- 字符串筛选排序 （Java JS PythonC/C++）

article 2025/1/16 20:32:02

在这里插入图片描述

一、问题描述

题目描述

输入一个由N个大小写字母组成的字符串

按照ASCII码值从小到大进行排序

查找字符串中第K个最小ASCII码值的字母 (k >= 1)

输出该字母所在字符串中的位置索引 (字符串的第一个位置索引为0)

k如果大于字符串长度则输出最大ASCII码值的字母所在字符串的位置索引

如果有重复字母则输出字母的最小位置索引

输入描述

第一行输入一个由大小写字母组成的字符串

第二行输入k，k必须大于0，k可以大于输入字符串的长度

输出描述

输出字符串中第K个最小ASCII码值的字母所在字符串的位置索引

k如果大于字符串长度则输出最大ASCII码值的字母所在字符串的位置索引

如果第K个最小ASCII码值的字母存在重复，则输出该字母的最小位置索引

用例

用例 1

输入:

AbCdeFG
3

输出:

5

说明:
根据ASCII码值排序，第三个ASCII码值的字母为F

F在字符串中位置索引为5 (0为字符串的第一个字母位置索引)

用例 2

输入:

fAdDAkBbBq
4

输出:

6

说明:
根据ASCII码值排序前4个字母为AABB由于B重复则只取B的第一个最小位置索引6

而不是第二个B的位置索引8

题目解析

本题是简单的字符串操作题。

2023.05.20 补充了第二个用例

根据第二个用例来看，题目要找的第k个，不是去重+升序后的第k个，而只是排序后的第k个。

详细步骤

  1. 读取输入：

    • 读取一个由大小写字母组成的字符串 s。
    • 读取一个整数 k。

  2. 创建字符索引映射：

    • 创建一个字典 char_index，键为字符，值为该字符在字符串中的最小索引。
    • 遍历字符串 s，记录每个字符的最小索引。

  3. 排序字符：

    • 将字符串 s 中的字符按ASCII码值排序，得到排序后的字符列表 sorted_chars。

  4. 查找第K个字符：

    • 如果 k 大于字符串长度，取最大ASCII码值的字符。
    • 否则，取排序后第 k 个字符。

  5. 输出结果：

    • 输出该字符在字符串中的最小位置索引。

用例解释

用例 1
  • 输入：
    • s = "AbCdeFG"
    • k = 3
  • 输出：
    • 5

解释：

  • 按ASCII码值排序后的字符列表：['A', 'C', 'd', 'e', 'F', 'G', 'b']
  • 第3个字符是 F，其在字符串中的位置索引为 5。
用例 2
  • 输入：
    • s = "fAdDAkBbBq"
    • k = 4
  • 输出：
    • 6

解释：

  • 按ASCII码值排序后的字符列表：['A', 'A', 'B', 'B', 'B', 'D', 'D', 'f', 'k', 'q']
  • 第4个字符是 B，其在字符串中的最小位置索引为 6。

通过上述步骤，我们可以高效地求出第K个最小ASCII码值的字母在字符串中的位置索引。这种方法的时间复杂度为 O(n log n)，其中 n 是字符串的长度。

二、JavaScript算法源码

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

JavaScript 代码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline"); // 引入 readline 模块，用于读取控制台输入

// 创建 readline 接口
const rl = readline.createInterface({
  input: process.stdin,  // 输入流为标准输入
  output: process.stdout, // 输出流为标准输出
});

// 存储输入行的数组
const lines = [];

// 监听输入事件
rl.on("line", (line) => {
  lines.push(line); // 将每一行输入存入 lines 数组

  // 当输入行数为 2 时，表示输入完成
  if (lines.length === 2) {
    const [str, k] = lines; // 解构赋值，获取输入的两行数据

    // 调用算法函数并输出结果
    console.log(getKIndex(str, k));

    // 清空 lines 数组，以便处理下一组输入
    lines.length = 0;
  }
});

// 算法函数：获取字符串中第 k 小的字符的索引
function getKIndex(str, k) {
  // 如果 k 大于字符串长度，则将 k 设置为字符串长度
  if (k > str.length) k = str.length;

  // 将字符串转换为数组，排序后获取第 k 小的字符
  const tar = [...str].sort()[k - 1];

  // 返回该字符在原字符串中的索引
  return str.indexOf(tar);
}

代码逻辑讲解

1. 输入处理
  • 使用 readline 模块读取控制台输入。
  • 将每一行输入存入 lines 数组。
  • 当 lines 数组的长度为 2 时，表示输入完成，开始处理数据。
2. 算法逻辑
  • 函数 getKIndex：
    • 参数：
      • str：输入的字符串。
      • k：表示需要查找的第 k 小的字符。
    • 逻辑：
      1. 如果 k 大于字符串长度，则将 k 设置为字符串长度（避免越界）。
      2. 将字符串转换为数组，并对数组进行排序。
      3. 获取排序后数组中第 k - 1 个字符（因为数组索引从 0 开始）。
      4. 返回该字符在原字符串中的索引。
3. 示例验证
示例 1：
  • 输入：
    hello
3
  • 处理过程：
    1. 将字符串 "hello" 转换为数组：['h', 'e', 'l', 'l', 'o']。
    2. 对数组排序：['e', 'h', 'l', 'l', 'o']。
    3. 获取第 3 小的字符：'l'。
    4. 返回 'l' 在原字符串中的索引：2。
  • 输出：2。
示例 2：
  • 输入：
    world
5
  • 处理过程：
    1. 将字符串 "world" 转换为数组：['w', 'o', 'r', 'l', 'd']。
    2. 对数组排序：['d', 'l', 'o', 'r', 'w']。
    3. 获取第 5 小的字符：'w'。
    4. 返回 'w' 在原字符串中的索引：0。
  • 输出：0。

总结

  • 功能：在给定字符串 str 和整数 k 的情况下，找到字符串中第 k 小的字符，并返回其索引。
  • 核心逻辑：
    1. 将字符串转换为数组并排序。
    2. 获取排序后数组中第 k - 1 个字符。
    3. 返回该字符在原字符串中的索引。
  • 适用场景：需要查找字符串中第 k 小的字符及其索引的场景。
  • 注意事项：
    • 如果 k 大于字符串长度，则 k 会被设置为字符串长度。
    • 时间复杂度为 O(n log n)，其中 n 是字符串长度（排序操作的时间复杂度）。

如果有其他问题，欢迎随时提问！

三、Java算法源码

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

import java.util.Arrays;  // 导入Arrays类，用于数组操作
import java.util.Scanner; // 导入Scanner类，用于从控制台读取输入

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in); // 创建Scanner对象，用于读取用户输入

    String str = sc.next(); // 读取用户输入的字符串
    int k = sc.nextInt();   // 读取用户输入的整数k

    System.out.println(getResult(str, k)); // 调用getResult方法并输出结果
  }

  public static int getResult(String str, int k) {
    char[] chars = str.toCharArray(); // 将字符串转换为字符数组
    Arrays.sort(chars); // 对字符数组进行排序，按字典序升序排列

    if (k > str.length()) k = str.length(); // 如果k大于字符串长度，则将k设置为字符串长度

    char tar = chars[k - 1]; // 获取排序后字符数组中的第k个字符（索引为k-1）
    return str.indexOf(tar); // 返回该字符在原字符串中的索引位置
  }
}

代码讲解：

  1. 导入类库：

    • import java.util.Arrays;：导入Arrays类，用于对数组进行排序等操作。
    • import java.util.Scanner;：导入Scanner类，用于从控制台读取用户输入。

  2. 主方法 main：

    • Scanner sc = new Scanner(System.in);：创建一个Scanner对象，用于读取用户输入。
    • String str = sc.next();：读取用户输入的字符串。
    • int k = sc.nextInt();：读取用户输入的整数k。
    • System.out.println(getResult(str, k));：调用getResult方法，并将结果输出到控制台。

  3. getResult 方法：

    • char[] chars = str.toCharArray();：将输入的字符串str转换为字符数组chars。
    • Arrays.sort(chars);：对字符数组chars进行排序，排序后字符数组中的字符按字典序升序排列。
    • if (k > str.length()) k = str.length();：如果输入的k大于字符串的长度，则将k设置为字符串的长度，防止数组越界。
    • char tar = chars[k - 1];：获取排序后字符数组中的第k个字符（由于数组索引从0开始，所以是k-1）。
    • return str.indexOf(tar);：返回该字符在原字符串str中的索引位置。

代码功能总结：

  • 该程序的功能是：给定一个字符串和一个整数k，程序会先对字符串中的字符进行排序，然后找到排序后的第k个字符，并返回该字符在原字符串中的索引位置。

示例：

假设输入字符串为"hello"，k为3：

  1. 将字符串转换为字符数组：['h', 'e', 'l', 'l', 'o']。
  2. 对字符数组进行排序：['e', 'h', 'l', 'l', 'o']。
  3. 取第3个字符（索引为2）：'l'。
  4. 返回'l'在原字符串"hello"中的索引位置：2。

因此，程序输出为2。

希望这个解释对您理解代码有所帮助！

四、Python算法源码

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

# 输入获取
s = input()  # 从控制台读取用户输入的字符串
k = int(input())  # 从控制台读取用户输入的整数k

# 算法入口
def getResult(s, k):
    chars = list(s)  # 将字符串s转换为字符列表
    chars.sort()  # 对字符列表进行排序，按字典序升序排列

    if k > len(s):  # 如果k大于字符串的长度
        k = len(s)  # 将k设置为字符串的长度，防止越界

    tar = chars[k - 1]  # 获取排序后字符列表中的第k个字符（索引为k-1）
    return s.index(tar)  # 返回该字符在原字符串s中的索引位置

# 调用算法
print(getResult(s, k))  # 调用getResult函数并输出结果

代码讲解：

  1. 输入获取：

    • s = input()：从控制台读取用户输入的字符串，并赋值给变量s。
    • k = int(input())：从控制台读取用户输入的整数，并赋值给变量k。

  2. getResult 函数：

    • chars = list(s)：将字符串s转换为字符列表chars。
    • chars.sort()：对字符列表chars进行排序，排序后字符列表中的字符按字典序升序排列。
    • if k > len(s): k = len(s)：如果输入的k大于字符串的长度，则将k设置为字符串的长度，防止索引越界。
    • tar = chars[k - 1]：获取排序后字符列表中的第k个字符（由于列表索引从0开始，所以是k-1）。
    • return s.index(tar)：返回该字符在原字符串s中的索引位置。

  3. 调用算法：

    • print(getResult(s, k))：调用getResult函数，并将结果输出到控制台。

代码功能总结：

  • 该程序的功能是：给定一个字符串和一个整数k，程序会先对字符串中的字符进行排序，然后找到排序后的第k个字符，并返回该字符在原字符串中的索引位置。

示例：

假设输入字符串为"hello"，k为3：

  1. 将字符串转换为字符列表：['h', 'e', 'l', 'l', 'o']。
  2. 对字符列表进行排序：['e', 'h', 'l', 'l', 'o']。
  3. 取第3个字符（索引为2）：'l'。
  4. 返回'l'在原字符串"hello"中的索引位置：2。

因此，程序输出为2。

注意事项：

  1. 索引从0开始：
    • Python中的列表索引从0开始，因此第k个字符的索引是k-1。
  2. 越界处理：
    • 如果k大于字符串的长度，程序会将k设置为字符串的长度，避免索引越界。
  3. 字符重复：
    • 如果字符串中有重复字符，s.index(tar)会返回第一个匹配字符的索引。

希望这个解释对您理解代码有所帮助！

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

以下是 C语言代码 和 C++代码 的详细中文注释和讲解，并附上代码转换。

C语言代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 10000  // 定义最大字符串长度

// 比较函数，用于qsort排序
int cmp(const void* a, const void* b) {
    return (*(char*) a) - (*(char*) b);  // 按字符的ASCII值升序排序
}

int main() {
    char s[MAX_SIZE];  // 定义字符数组，用于存储输入的字符串
    gets(s);  // 从控制台读取字符串（注意：gets不安全，建议使用fgets）

    int k;
    scanf("%d", &k);  // 从控制台读取整数k

    int n = strlen(s);  // 获取字符串的长度

    char s_cp[n + 1];  // 定义字符数组，用于存储字符串的副本
    strcpy(s_cp, s);  // 将原字符串复制到副本中

    qsort(s_cp, n, sizeof(char), cmp);  // 对副本字符串进行排序

    if (k > n) {  // 如果k大于字符串长度
        k = n;  // 将k设置为字符串长度，防止越界
    }

    char target = s_cp[k - 1];  // 获取排序后字符串的第k个字符（索引为k-1）

    printf("%lld\n", strchr(s, target) - s);  // 输出目标字符在原字符串中的索引

    return 0;
}

C语言代码讲解：

  1. 头文件：

    • #include <stdio.h>：标准输入输出库，用于printf和scanf。
    • #include <stdlib.h>：标准库，用于qsort。
    • #include <string.h>：字符串处理库，用于strlen和strcpy。

  2. 宏定义：

    • #define MAX_SIZE 10000：定义最大字符串长度为10000。

  3. 比较函数 cmp：

    • 用于qsort排序，按字符的ASCII值升序排列。

  4. 主函数 main：

    • char s[MAX_SIZE];：定义字符数组，用于存储输入的字符串。
    • gets(s);：从控制台读取字符串（注意：gets不安全，建议使用fgets）。
    • scanf("%d", &k);：从控制台读取整数k。
    • int n = strlen(s);：获取字符串的长度。
    • char s_cp[n + 1];：定义字符数组，用于存储字符串的副本。
    • strcpy(s_cp, s);：将原字符串复制到副本中。
    • qsort(s_cp, n, sizeof(char), cmp);：对副本字符串进行排序。
    • if (k > n) { k = n; }：如果k大于字符串长度，将k设置为字符串长度。
    • char target = s_cp[k - 1];：获取排序后字符串的第k个字符。
    • printf("%lld\n", strchr(s, target) - s);：输出目标字符在原字符串中的索引。

C++代码

#include <iostream>
#include <algorithm>  // 包含sort函数
#include <cstring>    // 包含strlen和strchr函数

using namespace std;

int main() {
    char s[10000];  // 定义字符数组，用于存储输入的字符串
    cin.getline(s, 10000);  // 从控制台读取字符串（安全的方式）

    int k;
    cin >> k;  // 从控制台读取整数k

    int n = strlen(s);  // 获取字符串的长度

    char s_cp[n + 1];  // 定义字符数组，用于存储字符串的副本
    strcpy(s_cp, s);  // 将原字符串复制到副本中

    sort(s_cp, s_cp + n);  // 对副本字符串进行排序

    if (k > n) {  // 如果k大于字符串长度
        k = n;  // 将k设置为字符串长度，防止越界
    }

    char target = s_cp[k - 1];  // 获取排序后字符串的第k个字符（索引为k-1）

    cout << (strchr(s, target) - s) << endl;  // 输出目标字符在原字符串中的索引

    return 0;
}

C++代码讲解：

  1. 头文件：

    • #include <iostream>：输入输出流库，用于cin和cout。
    • #include <algorithm>：算法库，用于sort函数。
    • #include <cstring>：C风格字符串处理库，用于strlen和strchr。

  2. 主函数 main：

    • char s[10000];：定义字符数组，用于存储输入的字符串。
    • cin.getline(s, 10000);：从控制台读取字符串（安全的方式）。
    • cin >> k;：从控制台读取整数k。
    • int n = strlen(s);：获取字符串的长度。
    • char s_cp[n + 1];：定义字符数组，用于存储字符串的副本。
    • strcpy(s_cp, s);：将原字符串复制到副本中。
    • sort(s_cp, s_cp + n);：对副本字符串进行排序。
    • if (k > n) { k = n; }：如果k大于字符串长度，将k设置为字符串长度。
    • char target = s_cp[k - 1];：获取排序后字符串的第k个字符。
    • cout << (strchr(s, target) - s) << endl;：输出目标字符在原字符串中的索引。

代码功能总结：

  • 该程序的功能是：给定一个字符串和一个整数k，程序会先对字符串中的字符进行排序，然后找到排序后的第k个字符，并返回该字符在原字符串中的索引位置。

示例：

假设输入字符串为"hello"，k为3：

  1. 将字符串转换为字符数组：['h', 'e', 'l', 'l', 'o']。
  2. 对字符数组进行排序：['e', 'h', 'l', 'l', 'o']。
  3. 取第3个字符（索引为2）：'l'。
  4. 返回'l'在原字符串"hello"中的索引位置：2。

因此，程序输出为2。

注意事项：

  1. C语言中的gets不安全：
    • 建议使用fgets替代gets，例如：fgets(s, MAX_SIZE, stdin);。
  2. C++中的cin.getline：
    • 是安全的输入方式，可以避免缓冲区溢出。
  3. 字符重复：
    • 如果字符串中有重复字符，strchr会返回第一个匹配字符的索引。

希望这个解释对您理解代码有所帮助！


http://www.kler.cn/a/505472.html

相关文章：

  • （一）QSQLite3库简介
  • Three.js 性能优化：打造流畅高效的3D应用
  • 7.STM32F407ZGT6-RTC
  • 【C++】PP5015 [NOIP2018 普及组] 标题统计
  • thinkphp 5.0 结合redis 做延迟队列，队列无法被消费
  • 详解 Docker 启动 Windows 容器第二篇：技术原理与未来发展方向
  • 网络分析仪测试S参数
  • 网络协议基础--协议分层
  • Java学习教程，从入门到精通，JDBC驱动程序类型及语法知识点（91）
  • 可以用于分割字符串的方法（python）
  • Mock 单元测试详细
  • 11-天猫订单数据分析
  • 深度剖析底层原理：CPU缓存一致性的奥秘
  • 机器学习-归一化
  • 低代码独特架构带来的编译难点及多线程解决方案
  • 【2025 Rust学习 --- 16 集合：Rust的STL】
  • go-echo学习笔记
  • 【Qt】01－了解QT
  • T-SQL编程
  • Python3 函数
  • 网安-HTML
  • 移动端H5缓存问题
  • 太速科技-402-基于TMS320C6678+XC7K325T的高性能计算核心板
  • 青少年编程与数学 02-006 前端开发框架VUE 27课题、TypeScript
  • 数字可调控开关电源设计（论文+源码）
  • C# 运算符和类型强制转换(对象的相等比较)