华为OD机试 - 对称美学（Python/JS/C/C++ 2024 E卷 100分）

news/2024/9/29 18:21:20 标签: 华为od, python, javascript

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

对称就是最大的美学，现在有一道关于对称字符串的美学。已知：

第1个字符串：R
第2个字符串：BR
第3个字符串：RBBR
第4个字符串：BRRBRBBR
第5个字符串：RBBRBRRBBRBBBRR

相信你已经发现规律了，没错！就是第i个字符串 = 第i-1号字符串取反 + 第i-1号字符串；
取反（R->B，B->R）；

现在告诉你n和k，让你求得第n个字符串的第k个字符是多少。（k的编号从0开始）

二、输入描述

第一行输入一个T，表示有T组用例；

解析来输入T行，每行输入两个数字，表示n，k

1 ≤ T ≤ 100；
1 ≤ n ≤ 64；
0 ≤ k ≤ 2^(n-1) - 1；

三、输出描述

输出T行示例答案；

输出“blue”表示字符等于B；
输出“red”表示字符等于R；

注：输出字符Q区分大小写，请注意输出小写字符串，不带双引号。

四、测试用例

测试用例1：

1、输入

5
1 0
2 1
3 2
4 6
5 8

2、输出

red
red
blue
blue
blue

3、说明

第1个字符串：R -> 第0个字符为R
第2个字符串：BR -> 第1个字符为R
第3个字符串：RBBR -> 第2个字符为B
第4个字符串：BRRBRBBR -> 第6个字符为B
第5个字符串：RBBRBRRBBRBBBRR -> 第8个字符为B

测试用例2：

1、输入

3
1 0
2 0
3 3

2、输出

red
blue
red

3、说明

第1个字符串：R -> 第0个字符为R
第2个字符串：BR -> 第0个字符为B
第3个字符串：RBBR -> 第3个字符为R

五、解题思路

题目要求在生成的对称字符串中，找到第n个字符串的第k个字符。观察字符串的生成规律，我们发现每个字符串都是前一个字符串取反后与前一个字符串拼接而成的。这种递归生成的方式使得我们可以利用递归思想来解决问题，而无需实际生成字符串。

具体步骤如下：

  1. 递归基准：当n=1时，字符串为"R"，所以第0个字符是’R’。
  2. 递归步骤：
    • 计算前一个字符串的长度，即mid = 2^(n-2)。
    • 如果k小于mid，说明第k个字符位于取反后的部分，此时递归查找第n-1个字符串的第k个字符，并取反。
    • 如果k大于等于mid，说明第k个字符位于前一个字符串的部分，此时递归查找第n-1个字符串的第(k - mid)个字符。
  3. 字符取反：‘R’取反为’B’，‘B’取反为’R’。
  4. 输出：根据查找到的字符，输出"red"或"blue"。

这种方法避免了直接生成可能非常大的字符串（n最大为64时字符串长度为2^63），提高了效率。

六、Python算法源码

python"># 导入sys模块用于读取输入
import sys

# 定义递归函数，用于获取第n个字符串的第k个字符
def get_char(n, k):
    # 基准情况：n=1时，字符串只有一个字符'R'
    if n == 1:
        return 'R'
    # 计算前一个字符串的长度，即2^(n-2)
    mid = 1 << (n - 2)
    if k < mid:
        # 如果k在前半部分，取反后递归查找
        c = get_char(n - 1, k)
        return invert(c)  # 取反
    else:
        # 如果k在后半部分，直接递归查找
        return get_char(n - 1, k - mid)

# 定义字符取反函数
def invert(c):
    return 'B' if c == 'R' else 'R'

def main():
    # 读取所有输入
    input = sys.stdin.read().split()
    # 第一个数字是测试用例数量T
    T = int(input[0])
    # 初始化指针
    ptr = 1
    for _ in range(T):
        # 读取n和k
        n = int(input[ptr])
        k = int(input[ptr + 1])
        ptr += 2
        # 获取第n个字符串的第k个字符
        result = get_char(n, k)
        # 根据字符输出对应的颜色
        if result == 'R':
            print("red")
        else:
            print("blue")

if __name__ == "__main__":
    main()

七、JavaScript算法源码

javascript">// 使用标准输入输出模块
const readline = require('readline');

// 创建接口用于读取输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

// 定义递归函数，用于获取第n个字符串的第k个字符
function getChar(n, k) {
    // 基准情况：n=1时，返回'R'
    if (n === 1) {
        return 'R';
    }
    // 计算前一个字符串的长度，即2^(n-2)
    const mid = 1 << (n - 2);
    if (k < mid) {
        // 如果k在前半部分，取反后递归查找
        const c = getChar(n - 1, k);
        return invert(c); // 取反
    } else {
        // 如果k在后半部分，直接递归查找
        return getChar(n - 1, k - mid);
    }
}

// 定义字符取反函数
function invert(c) {
    return (c === 'R') ? 'B' : 'R';
}

// 读取所有输入数据
let input = [];
rl.on('line', function(line){
    input = input.concat(line.trim().split(' '));
});

rl.on('close', function(){
    // 第一个数字是测试用例数量T
    let T = parseInt(input[0]);
    let ptr = 1;
    for(let i = 0; i < T; i++){
        // 读取n和k
        let n = parseInt(input[ptr]);
        let k = BigInt(input[ptr + 1]); // 使用BigInt处理大数
        ptr += 2;
        // 获取第n个字符串的第k个字符
        let result = getChar(n, Number(k));
        // 根据字符输出对应的颜色
        if(result === 'R'){
            console.log("red");
        }
        else{
            console.log("blue");
        }
    }
});

八、C算法源码

#include <stdio.h>

// 定义字符取反函数
char invert_char(char c) {
    return (c == 'R') ? 'B' : 'R';
}

// 定义递归函数，用于获取第n个字符串的第k个字符
char get_char(int n, unsigned long long k) {
    // 基准情况：n=1时，返回'R'
    if (n == 1) {
        return 'R';
    }
    // 计算前一个字符串的长度，即2^(n-2)
    unsigned long long mid = 1ULL << (n - 2);
    if (k < mid) {
        // 如果k在前半部分，取反后递归查找
        char c = get_char(n - 1, k);
        return invert_char(c); // 取反
    }
    else {
        // 如果k在后半部分，直接递归查找
        return get_char(n - 1, k - mid);
    }
}

int main() {
    int T;
    // 读取测试用例数量
    scanf("%d", &T);
    while(T--){
        int n;
        unsigned long long k;
        // 读取n和k
        scanf("%d %llu", &n, &k);
        // 获取第n个字符串的第k个字符
        char result = get_char(n, k);
        // 根据字符输出对应的颜色
        if(result == 'R') {
            printf("red\n");
        }
        else {
            printf("blue\n");
        }
    }
    return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;

// 定义字符取反函数
char invert_char(char c) {
    return (c == 'R') ? 'B' : 'R';
}

// 定义递归函数，用于获取第n个字符串的第k个字符
char get_char(int n, unsigned long long k) {
    // 基准情况：n=1时，返回'R'
    if (n == 1) {
        return 'R';
    }
    // 计算前一个字符串的长度，即2^(n-2)
    unsigned long long mid = 1ULL << (n - 2);
    if (k < mid) {
        // 如果k在前半部分，取反后递归查找
        char c = get_char(n - 1, k);
        return invert_char(c); // 取反
    }
    else {
        // 如果k在后半部分，直接递归查找
        return get_char(n - 1, k - mid);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    // 读取测试用例数量
    cin >> T;
    while(T--){
        int n;
        unsigned long long k;
        // 读取n和k
        cin >> n >> k;
        // 获取第n个字符串的第k个字符
        char result = get_char(n, k);
        // 根据字符输出对应的颜色
        if(result == 'R') {
            cout << "red\n";
        }
        else {
            cout << "blue\n";
        }
    }
    return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

在这里插入图片描述


http://www.niftyadmin.cn/n/5683515.html

相关文章

js中防抖 debounce 节流 throttle 原理 从0手动实现

js中防抖 debounce 节流 throttle 原理 从0手动实现

1 防抖 高频触发事件时&#xff0c;执行损耗高的操作&#xff0c;连续触发过程中&#xff0c;只执行最后一次。 高频事件&#xff1a;input scroll resize等。损耗高&#xff1a;网络请求、dom操作。 实现防抖步骤&#xff1a;1.在回调函数中判断timer是否存在&#xff0c;存在…
阅读更多...
docker kibana 连接es

docker kibana 连接es

server.name: kibana server.host: “0” #容器中配置&#xff0c;去掉http://127.0.0.1:9200 elasticsearch.hosts: [“http://host.docker.internal:9200”] #设置访问用户 elasticsearch.username: “elastic” #设置访问密码 elasticsearch.password: “elastic” #设置中文…
阅读更多...
TCP编程:从入门到实践

TCP编程:从入门到实践

目录 一、引言 二、TCP协议原理 1.面向连接 2.可靠传输 三、TCP编程实践 1.TCP服务器 2.TCP客户端 四、总结 本文将带你了解TCP编程的基本原理&#xff0c;并通过实战案例&#xff0c;教你如何在网络编程中运用TCP协议。掌握TCP编程&#xff0c;为构建稳定、高效的网络通信…
阅读更多...
服务器使用frp做内网穿透详细教程，请码住

服务器使用frp做内网穿透详细教程，请码住

目录 1.内网穿透的定义 2.前提条件 3.frp下载地址 4.配置服务器端的frps.toml文件 5. 配置客户端&#xff0c;即物理服务器或者是电脑本机地址 6.添加服务端启动命令startServerFrp.sh 7.添加客户端启动命令startClientFrp.sh 8. 查看服务端启动日志 9.查看客户端启…
阅读更多...
【算法】反向传播算法

【算法】反向传播算法

David Rumelhart 是人工智能领域的先驱之一&#xff0c;他与 James McClelland 等人在1986年通过其著作《Parallel Distributed Processing: Explorations in the Microstructure of Cognition》详细介绍了反向传播算法&#xff08;Backpropagation&#xff09;&#xff0c;这一…
阅读更多...
哈希表(HashMap、HashSet)

哈希表(HashMap、HashSet)

文章目录 一、 什么是哈希表二、 哈希冲突2.1 为什么会出现冲突2.2 如何避免出现冲突2.3 出现冲突如何解决 三、模拟实现哈希桶/开散列&#xff08;整型数据&#xff09;3.1 结构3.2 插入元素3.3 获取元素 四、模拟实现哈希桶/开散列&#xff08;泛型&#xff09;4.1 结构4.2 插…
阅读更多...
python绘制动态残差图，plot交互模式

python绘制动态残差图，plot交互模式

python绘制动态残差图 动态刷新数据&#xff0c;交互模式 # 开启交互模式plt.ion()# 创建初始数据x_line [0, 1]err_wage [0, 10]# 创建图形和轴fig, ax plt.subplots()line, ax.plot(x_line, err_wage, b-) # b-表示蓝色实线# ax.set_xlim(0, 20) # 设置x轴的范围# ax.…
阅读更多...
甘肃非遗文化网站：Spring Boot开发实战

甘肃非遗文化网站：Spring Boot开发实战

3 系统分析 当用户确定开发一款程序时&#xff0c;是需要遵循下面的顺序进行工作&#xff0c;概括为&#xff1a;系统分析–>系统设计–>系统开发–>系统测试&#xff0c;无论这个过程是否有变更或者迭代&#xff0c;都是按照这样的顺序开展工作的。系统分析就是分析系…
阅读更多...
最新文章

Copyright @ 2022~2023