首页 > 编程语言 >【Py/Java/C++三种语言OD独家2024E卷真题】20天拿下华为OD笔试之【回溯】2024E-字符串拼接【欧弟算法】全网注释最详细分类最全的华为OD真题题解

【Py/Java/C++三种语言OD独家2024E卷真题】20天拿下华为OD笔试之【回溯】2024E-字符串拼接【欧弟算法】全网注释最详细分类最全的华为OD真题题解

时间:2024-09-10 14:54:58浏览次数:9  
标签:字符 cnt 真题 OD ans 回溯 path 2024E

可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练(备注【CSDN】否则不通过)

文章目录

相关推荐阅读

从2024年8月14号开始,OD机考全部配置为2024E卷
注意几个关键点:

  1. 大部分的题目仍为往期2023A+B+C以及2024D的旧题。注意万变不离其宗,把方法掌握,无论遇到什么题目都可以轻松应对。
  2. 支持多次提交题目,以最后一次提交为准。可以先做200的再做100的,然后可以反复提交。
  3. E卷仍然为单机位+屏幕监控的形式进行监考。
  4. 进入考试界面新加入了这样一段话并且用红字标出,可以看出华子对作弊代考等行为是0容忍的,请各位同学认真学习,不要妄图通过其他违规途径通过考试。
    在这里插入图片描述

题目描述与示例

题目描述

给定M (0<M<=30)个字符(a-z),从中取出任意字符(每个字符只能用一次)拼接成长度为N (0<N<=5)的字符串,要求相同的字符不能相邻,计算出给定的字符列表能拼接出多少种满足条件的字符串,输入非法或者无法拼接出满足条件的字符串则返回0

输入描述

给定的字符列表和结果字符串长度,中间使用空格(" ")拼接

输出描述

满足条件的字符串个数

示例一

输入

abc 1

输出

3

说明

给定的字符为abc,结果字符串长度为1,可以拼接成a,b,c,共3

示例二

输入

aabc 3

输出

8

说明

给定的字符为aabc,结果字符串长度为3,可以拼接成abc,acb,bac,bca,cba,cab,aba,aca,共8

解题思路

本题数据量不大,虽然只是要求枚举数量而不是枚举具体的字符串,但仍然可以通过回溯来解决。

注意到在本题中,原输入字符串s中的字符顺序并不重要,只有出现次数是关键信息。

所以很容易考虑应该使用哈希表计数器来统计s中各个字符出现的次数。即

cnt = Counter(s)

回溯的重点在于回溯函数的编写。函数传参需要包含三个参数:

  • n:目标字符串的长度
  • path:当前所选择的路径字符串的情况
  • cnt:原字符串s中的字符剩余情况

考虑递归终止条件,显然当len(path) == n时,我们找到了一个长度为n的拼接字符串,更新ans并退出递归,即

global ans
if len(path) == n:
    ans += 1
    return

考虑横向遍历过程,我们需要考虑cnt中的所有key以及这些keyvalue。当

  • value == 0时,说明key这个字符已经在之前被选择过了,无法再选
  • (path and key == path[-1])时,说明此时key和当前path的最后一个字符一致,此时是不能够选择key延长在path的后面的。

对于上述两种情况,都可以直接跳过该(key, value)对。

当不满足上述情况时,则可以进行状态更新和回溯,以及回溯结束后的回滚操作。即

for k, v in cnt.items():
    if v == 0 or (path and k == path[-1]):
        continue
    cnt[k] -= 1
    dfs(cnt, path + k, n)
    cnt[k] += 1

综上整体的回溯函数为

def dfs(cnt, path, n):
    global ans
    if len(path) == n:
        ans += 1
        return
    for k, v in cnt.items():
        if v == 0 or (path and k == path[-1]):
            continue
        cnt[k] -= 1
        dfs(cnt, path + k, n)
        cnt[k] += 1

这就完成了本题的核心递归函数。

至于递归入口,则传入path = ""即可。

另外题目说明当出现非法输入时需要返回0,因此还需要判断s中的每一个字符是否均为小写字符。

PS:感兴趣的同学可以思考一下如何使用dp完成这个问题

代码

python

# 题目:【回溯】2024E-字符串拼接
# 分值:200
# 作者:许老师-闭着眼睛学数理化
# 算法:回溯
# 代码看不懂的地方,请直接在群上提问


from collections import Counter


# 回溯的函数
# path是列表或者字符串均可,这里path选择字符串
def dfs(cnt, path, n):
    global ans
    # path长度已经为n,找到了一个答案
    if len(path) == n:
        ans += 1
        return
    # 横向遍历,考虑字符k以及其剩余个数v
    for k, v in cnt.items():
        # 如果剩余个数为0,或者k和path前一个字符一样,则直接跳过k
        if v == 0 or (path and k == path[-1]):
            continue
        # 状态更新:选择k,所以k的的剩余个数-1
        cnt[k] -= 1
        # 回溯:path的末尾要加上k这个字符来作为新的path
        dfs(cnt, path + k, n)
        # 回滚:把选择的这个k还回去,所以k的剩余个数+1
        cnt[k] += 1

# 有可能存在输入非法的情况,所以使用try-except语句
try:
    # 输入字符串s,答案字符的长度n
    s, n = input().split()
    n = int(n)
    # 使用哈希表统计s种每一个字符出现的次数
    # 显然,s中字符的出现顺序不重要
    cnt = Counter(s)
    # 如果s中的字符出现非小写字母的情况(非法输入),输出0
    # 只有全为小写字母,才可以进行回溯过程
    if all("a" <= k <= "z" for k in cnt):
        ans = 0
        dfs(cnt, "", n)
        print(ans)
    else:
        print(0)
except:
    print(0)

java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int ans = 0;

    // 回溯的函数
    static void dfs(Map<Character, Integer> cnt, StringBuilder path, int n) {
        // path长度已经为n,找到了一个答案
        if (path.length() == n) {
            ans++;
            return;
        }
        // 横向遍历,考虑字符k以及其剩余个数v
        for (char k : cnt.keySet()) {
            int v = cnt.get(k);
            // 如果剩余个数为0,或者k和path前一个字符一样,则直接跳过k
            if (v == 0 || (path.length() > 0 && k == path.charAt(path.length() - 1))) {
                continue;
            }
            // 状态更新:选择k,所以k的的剩余个数-1
            cnt.put(k, v - 1);
            // 回溯:path的末尾要加上k这个字符来作为新的path
            dfs(cnt, new StringBuilder(path).append(k), n);
            // 回滚:把选择的这个k还回去,所以k的剩余个数+1
            cnt.put(k, v);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] parts = input.split(" ");
        String s = parts[0];
        int n = Integer.parseInt(parts[1]);
        Map<Character, Integer> cnt = new HashMap<>();
        for (char ch : s.toCharArray()) {
            cnt.put(ch, cnt.getOrDefault(ch, 0) + 1);
        }
        // 如果s中的字符出现非小写字母的情况(非法输入),输出0
        // 只有全为小写字母,才可以进行回溯过程
        boolean valid = true;
        for (char ch : cnt.keySet()) {
            if (ch < 'a' || ch > 'z') {
                valid = false;
                break;
            }
        }
        if (valid) {
            ans = 0;
            dfs(cnt, new StringBuilder(), n);
            System.out.println(ans);
        } else {
            System.out.println(0);
        }
    }
}

cpp

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int ans = 0;

// 回溯的函数
void dfs(unordered_map<char, int>& cnt, string path, int n) {
    // path长度已经为n,找到了一个答案
    if (path.length() == n) {
        ans++;
        return;
    }
    // 横向遍历,考虑字符k以及其剩余个数v
    for (auto& kv : cnt) {
        char k = kv.first;
        int v = kv.second;
        // 如果剩余个数为0,或者k和path前一个字符一样,则直接跳过k
        if (v == 0 || (!path.empty() && k == path.back())) {
            continue;
        }
        // 状态更新:选择k,所以k的的剩余个数-1
        cnt[k]--;
        // 回溯:path的末尾要加上k这个字符来作为新的path
        dfs(cnt, path + k, n);
        // 回滚:把选择的这个k还回去,所以k的剩余个数+1
        cnt[k]++;
    }
}

int main() {
    string input;
    getline(cin, input);
    string s;
    int n;
    size_t pos = input.find(' ');
    s = input.substr(0, pos);
    n = stoi(input.substr(pos + 1));
    unordered_map<char, int> cnt;
    for (char ch : s) {
        cnt[ch]++;
    }
    // 如果s中的字符出现非小写字母的情况(非法输入),输出0
    // 只有全为小写字母,才可以进行回溯过程
    bool valid = true;
    for (auto& kv : cnt) {
        char ch = kv.first;
        if (ch < 'a' || ch > 'z') {
            valid = false;
            break;
        }
    }
    if (valid) {
        ans = 0;
        dfs(cnt, "", n);
        cout << ans << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}

时空复杂度

时间复杂度:O(NT^N)T为字符集的大小,最多为26N为目标字符串的长度。状态树的高度为N,叶子节点的数量最多为T^N

空间复杂度:O(N)。为状态树的高度。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务300+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

标签:字符,cnt,真题,OD,ans,回溯,path,2024E
From: https://blog.csdn.net/weixin_48157259/article/details/142073369

相关文章

  • vscode 不能进行调试
    首先终端会显示正在启动生成...cmd/cchcp65001>nul&&D:\Magic_Tools\MinGw64\bin\gcc.exe-fdiagnostics-color=always-gD:\Magic_Tools\VSCode-win32-x64-1.85.1\mycode\new\test.c-oD:\Magic_Tools\VSCode-win32-x64-1.85.1\mycode\new/test'......
  • 【漏洞复现】华三 H3C IMC 智能管理中心 /byod/index.xhtml RCE
    免责声明:        本文内容旨在提供有关特定漏洞或安全漏洞的信息,以帮助用户更好地了解可能存在的风险。公布此类信息的目的在于促进网络安全意识和技术进步,并非出于任何恶意目的。阅读者应该明白,在利用本文提到的漏洞信息或进行相关测试时,可能会违反某些法律法规......
  • 【Vue】npm ERR! code ERESOLVE
    npmERR!codeERESOLVE是npm在处理依赖关系时遇到版本冲突或无法解析依赖树时抛出的错误代码。这通常意味着项目中的某些包依赖于其他包的特定版本,而这些版本之间存在冲突,或者这些包的最新版本不兼容。解决方法:运行npminstall或npmupdate时添加--force参数来忽略......
  • Leetcode3264. K 次乘运算后的最终数组 I
    EverydayaLeetcode题目来源:3264.K次乘运算后的最终数组I解法1:模拟操作:遍历数组nums,找到其中的最小值x,如果存在多个最小值,选择最前面的一个。将它乘以multiplier。共执行k次操作。代码:/**@lcapp=leetcode.cnid=3264lang=cpp**[3264]K次乘运算......
  • Leetcode3265. 统计近似相等数对 I
    EverydayaLeetcode题目来源:3265.统计近似相等数对I解法1:枚举暴力枚举数组nums中下标i和j满足i<j的nums[i]和nums[j],判断它们是否近似相等。细节:先对数组nums升序排序,在判断它们是否近似相等,转成字符串进行比较,且只交换较大数的数位。代码:/**@l......
  • 一周的豆包MarsCode 编程助手全面测评
    豆包MarsCode编程助手安装步骤进入豆包MarsCode官方网站,sourl.cn/yWAtYr点击登陆/注册账号点击【立即获取编程助手】下载对应插件,我这里是用vscode安装豆包MarsCode编程助手豆包MarsCode,基于豆包大模型的智能开发工具,提供CloudIDE及AI编程助手两种使用形态,具备代码补全......
  • 华为OD机试真题-工号不够用了怎么办-2024年OD统一考试(E卷)
    题目描述3020年,空间通信集团的员工人数突破20亿人,即将遇到现有工号不够用的窘境,现在,请你负责调研新工号系统。继承历史传统,新的工号系统由小写英文字母Q(a-z)和数字(0-9)两部分构成。新工号由一段英文字母开头,之后跟随一段数字,比如"aaahw0001"“a12345","abcd1"”a00"。注意......
  • 【算法题】13.罗马数字转整-力扣(LeetCode)
    【算法题】13.罗马数字转整-力扣(LeetCode)1.题目下方是力扣官方题目的地址13.罗马数字转整数罗马数字包含以下七种字符:I,V,X,L,C,D和M。字符数值I1V5X10L50C100D5......
  • 一文学会开源图书库Koodo+Reader本地Windows电脑安装与远程访问
    文章目录前言1.KoodoReader功能特点1.1开源免费1.2支持众多格式1.3多平台兼容1.4多端数据备份同步1.5多功能阅读体验1.6界面简洁直观2.KoodoReader安装流程2.1安装Git2.2安装Node.js2.3下载koodoreader3.安装Cpolar内网穿透3.1配置公网地址3.2配置固......
  • 基于nodejs+vue非结构化数据[程序+论文+开题] 计算机毕业设计
    本系统(程序+源码+数据库+调试部署+开发环境)带文档lw万字以上,文末可获取源码系统程序文件列表开题报告内容研究背景随着信息技术的飞速发展,数据量呈爆炸性增长,其中非结构化数据占据了绝大部分比例。非结构化数据,如文本、图像、音频、视频等,因其形式多样、内容丰富,在企业决......