【2024年华为OD机试】(A卷,100分)- 完美走位 (Java JS PythonC/C++)

ops/2025/1/18 12:14:16/

在这里插入图片描述

一、问题描述

题目解析

题目描述

在第一人称射击游戏中,玩家通过键盘的 ASDW 四个按键控制游戏人物分别向左、向后、向右、向前进行移动。假设玩家每按动一次键盘,游戏人物会向某个方向移动一步。如果玩家在操作一定次数的键盘并且各个方向的步数相同时,此时游戏人物必定会回到原点,则称此次走位为完美走位

现给定玩家的走位(例如:ASDA),请通过更换其中一段连续走位的方式,使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。

请返回待更换的连续走位的最小可能长度。如果原走位本身是一个完美走位,则返回 0

输入描述

输入为由键盘字母表示的走位 s,例如:WASDAASD

输出描述

输出为待更换的连续走位的最小可能长度。

用例

输入
WASDAASD
输出
1
说明
将第二个 A 替换为 W,即可得到完美走位。

输入
AAAA
输出
3
说明
将其中三个连续的 A 替换为 WSD,即可得到完美走位。


题目解析

问题分析

  1. 完美走位的定义
    完美走位要求 WASD 四个方向的步数相等。假设走位总长度为 n,则每个方向的步数应为 n/4

  2. 问题转化
    如果原走位中某个方向的步数超过了 n/4,则需要通过替换一段连续走位来减少这些方向的步数,同时增加其他方向的步数,使得最终四个方向的步数相等。

  3. 关键点

    • 统计原走位中 WASD 的个数。
    • 计算每个方向需要减少的步数(即超出 n/4 的部分)。
    • 找到一段连续子串,使得这段子串中包含需要减少的步数,且长度最小。

解题思路

  1. 统计字符个数
    遍历字符串,统计 WASD 的个数,分别记为 count_Wcount_Acount_Scount_D

  2. 计算需要减少的步数
    假设走位总长度为 n,则每个方向的步数应为 n/4。计算每个方向需要减少的步数:

    • extra_W = max(0, count_W - n/4)
    • extra_A = max(0, count_A - n/4)
    • extra_S = max(0, count_S - n/4)
    • extra_D = max(0, count_D - n/4)
  3. 滑动窗口寻找最小子串
    使用滑动窗口的方法,在字符串中寻找一段连续子串,使得这段子串中包含至少 extra_WWextra_AAextra_SSextra_DD。记录满足条件的最短子串长度。

  4. 返回结果
    如果原走位已经是完美走位,则返回 0;否则返回找到的最短子串长度。


示例分析

示例 1
输入:WASDAASD

  • 统计字符个数:W=2, A=3, S=2, D=2
  • 总长度 n=8,每个方向应满足 n/4=2
  • 需要减少的步数:extra_W=0, extra_A=1, extra_S=0, extra_D=0
  • 找到包含 1A 的最短子串,长度为 1(如第二个 A
  • 输出:1

示例 2
输入:AAAA

  • 统计字符个数:W=0, A=4, S=0, D=0
  • 总长度 n=4,每个方向应满足 n/4=1
  • 需要减少的步数:extra_W=0, extra_A=3, extra_S=0, extra_D=0
  • 找到包含 3A 的最短子串,长度为 3
  • 输出:3

复杂度分析

  1. 时间复杂度

    • 统计字符个数:O(n)
    • 滑动窗口寻找最小子串:O(n)
    • 总时间复杂度:O(n)
  2. 空间复杂度

    • 使用常数空间存储字符个数和滑动窗口的指针,空间复杂度为 O(1)

总结

本题的核心是通过滑动窗口的方法,找到一段连续子串,使得替换后能够满足完美走位的条件。关键在于统计字符个数并计算需要减少的步数,然后利用滑动窗口高效地找到最小子串。

二、JavaScript算法源码

这段JavaScript代码用于在Node.js环境下读取控制台输入,并计算字符串中的"W", “A”, “S”, "D"字符的平衡状态。目标是找到一个最短的子串,可以通过替换将整个字符串变得平衡(即每种字符的数量相同)。以下是代码的详细解析和讲解:

输入处理

javascript">const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {console.log(getResult(line));
});
  • 功能:使用Node.js中的readline模块从控制台读取一行输入。
  • 逻辑解释
    • createInterface创建一个读写接口,绑定标准输入输出。
    • on("line", callback)监听每一行输入,每次输入时调用callback

getResult 函数

javascript">function getResult(str) {// 初始化计数器用于统计每个字符的出现次数const count = {W: 0,A: 0,S: 0,D: 0,};// 统计输入字符串中每个字符的数量for (let c of str) count[c]++;// 计算平衡状态下每个字符应有的平均数量const avg = str.length / 4;let total = 0; // 用于记录不平衡状态下多余的字符个数let flag = true; // 用于标记字符串是否已经平衡for (let c in count) {if (count[c] > avg) {flag = false; // 如果某个字符数量超过平均值,标记为不平衡count[c] -= avg; // 更新多余字符的数量total += count[c];} else {delete count[c]; // 删除不需要调整的字符}}if (flag) return 0; // 如果字符串已经平衡,返回0let i = 0;let j = 0;let minLen = str.length + 1; // 初始化最小子串长度为字符串长度+1// 使用滑动窗口技术寻找最短子串while (j < str.length) {const jc = str[j];if (count[jc]-- > 0) {total--;}while (total === 0) {minLen = Math.min(minLen, j - i + 1);const ic = str[i];if (count[ic]++ >= 0) {total++;}i++;}j++;}return minLen;
}

代码讲解

  1. 统计字符数量

    • 使用计数器count记录"W", “A”, “S”, "D"在输入字符串中的数量。
  2. 计算平衡状态

    • 平衡状态下,每个字符应有的数量是总长度除以4。
    • 检查是否有字符的数量超过平均值,如果超过,计算多余数量并更新计数器。
  3. 滑动窗口寻找最短子串

    • 滑动窗口:通过两个指针ij,在字符串上移动,寻找满足条件的最短子串。
    • 调整窗口:如果窗口内的子串使得所有字符达到平衡状态(total为0),记录子串长度,并尝试缩小窗口。
  4. 返回结果

    • 如果字符串本身已经平衡,返回0。
    • 否则,返回找到的最短子串长度。

通过这种方法,可以有效找出需要替换的最短子串,使字符串中的"W", “A”, “S”, "D"字符数量达到平衡。该算法利用了滑动窗口的技巧,使得时间复杂度相对较低,适合处理较长的字符串。

三、Java算法源码

这段Java代码用于解决一个字符串平衡问题,其中需要找到一个最短的子串,通过替换该子串,可以使整个字符串中的"W", “A”, “S”, "D"字符数量相等。下面是对代码的详细解释:

代码解析

main 方法
java">public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println(getResult(sc.next()));
}
  • 功能:从标准输入获取一个字符串,并输出计算结果。
  • 逻辑解释
    • 使用Scanner类获取用户输入。
    • 调用getResult方法计算结果并打印。
getResult 方法
java">public static int getResult(String str) {// count用于记录W,A,S,D字母的数量HashMap<Character, Integer> count = new HashMap<>();for (int i = 0; i < str.length(); i++) {Character c = str.charAt(i);count.put(c, count.getOrDefault(c, 0) + 1);}
  • 功能:统计字符串中每个字符的数量。
  • 逻辑解释
    • 使用HashMap记录"W", “A”, “S”, "D"字符的出现次数。
    • 遍历字符串,将每个字符的计数存入HashMap

java">    int avg = str.length() / 4;int total = 0;boolean flag = true;for (Character c : count.keySet()) {if (count.get(c) > avg) {flag = false;count.put(c, count.get(c) - avg);total += count.get(c);} else {count.put(c, 0);}}
  • 功能:计算并验证字符的平衡状态。
  • 逻辑解释
    • 计算平衡状态下每个字符应有的数量avg
    • 如果字符数量超过avg,标记为不平衡,并计算多余数量。
    • 如果所有字符都未超过avg,则字符串已经平衡。

java">    if (flag) return 0;int i = 0;int j = 0;int minLen = str.length() + 1;while (j < str.length()) {Character jc = str.charAt(j);if (count.get(jc) > 0) {total--;}count.put(jc, count.get(jc) - 1);while (total == 0) {minLen = Math.min(minLen, j - i + 1);Character ic = str.charAt(i);if (count.get(ic) >= 0) {total++;}count.put(ic, count.get(ic) + 1);i++;}j++;}return minLen;
}
  • 功能:使用滑动窗口技术寻找最短子串。
  • 逻辑解释
    • 使用两个指针ij定义一个窗口,在字符串上滑动。
    • 当窗口内的子串满足所有字符达到平衡状态(total为0),记录当前子串长度。
    • 调整窗口大小,继续寻找更短的子串。

总结

  • 输入输出:该程序从标准输入读取字符串,并输出一个整数,表示能够使字符串平衡的最短子串的长度。
  • 时间复杂度:通过使用滑动窗口技术,该算法在大多数情况下运行时间为O(n),适合处理较大的字符串。
  • 使用场景:这段代码适用于需要在字符串中平衡特定字符数量的场景,例如在游戏开发中平衡移动指令等。

希望这些解析对你理解这段代码有所帮助!如果有其他问题或需要进一步解释,请随时提出。

四、Python算法源码

这段Python代码的目标是从输入的字符串中找到一个最短的子串,通过替换该子串,可以使整个字符串中"W", “A”, “S”, "D"字符的数量达到平衡。以下是对代码的详细解析和讲解:

代码解析

输入获取
python">s = input()
  • 功能:从标准输入读取一个字符串,并将其存储在变量s中。
getResult 函数
python">def getResult(s):# 初始化一个字典用于统计W, A, S, D的数量count = {"W": 0,"A": 0,"S": 0,"D": 0}# 统计每个字符的数量for c in s:count[c] += 1
  • 功能:统计字符串中每个字符的数量。
  • 逻辑解释
    • 使用字典count记录"W", “A”, “S”, "D"字符的出现次数。

python">    avg = len(s) / 4  # 平衡状态时每个字符应有的数量total = 0  # 记录多余字符的总数flag = True  # 标记是否已经平衡for c in count.keys():if count[c] > avg:flag = False  # 标记为不平衡count[c] -= avg  # 计算多余部分total += count[c]  # 更新多余字符总数else:count[c] = 0  # 设置为0,表示不需要调整
  • 功能:计算当前字符的平衡状态。
  • 逻辑解释
    • 计算平衡状态下每个字符应有的平均数量avg
    • 检查每种字符是否超过平均值,并更新多余数量。
    • 如果字符数量不超过平均值,设为0,表明不需要调整。

python">    if flag:return 0  # 如果已经平衡,返回0i = 0j = 0minLen = len(s) - 1  # 初始化最短子串长度while j < len(s):jc = s[j]if count[jc] > 0:total -= 1count[jc] -= 1while total == 0:minLen = min(minLen, j - i + 1)ic = s[i]if count[ic] >= 0:total += 1count[ic] += 1i += 1j += 1return minLen
  • 功能:使用滑动窗口技术寻找最短的子串。
  • 逻辑解释
    • 使用两个指针ij定义一个窗口,在字符串上滑动。
    • 当窗口内的子串使得所有字符达到平衡状态(total为0),记录当前子串长度。
    • 调整窗口大小,尝试找到更短的子串。

总结

  • 输入输出:程序从标准输入读取字符串,并输出能够使其达到平衡状态的最短子串的长度。
  • 时间复杂度:通过使用滑动窗口技术,该算法在大多数情况下运行时间为O(n),适用于处理较长的字符串。
  • 使用场景:适合需要在字符串中平衡特定字符数量的应用场景,例如在游戏开发中控制移动指令的平衡等。

希望这些解析对你理解这段代码有所帮助!如果有其他问题或需要进一步解释,请随时提出。

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

好的,我将根据这段Python代码转换为C++和C语言版本,并提供详细的中文注释和讲解。

C++ 版本

#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;int getResult(const string& s) {// 使用unordered_map记录W, A, S, D的数量unordered_map<char, int> count = {{'W', 0},{'A', 0},{'S', 0},{'D', 0}};// 统计每个字符的数量for (char c : s) {count[c]++;}int avg = s.length() / 4; // 计算每个字符在平衡状态下应有的平均数量int total = 0; // 记录多余字符的总数bool flag = true; // 标记是否已经平衡for (auto& kv : count) {if (kv.second > avg) {flag = false; // 标记为不平衡kv.second -= avg; // 计算多余部分total += kv.second; // 更新多余字符总数} else {kv.second = 0; // 设置为0,表示不需要调整}}if (flag) return 0; // 如果已经平衡,返回0int i = 0;int j = 0;int minLen = s.length(); // 初始化最短子串长度while (j < s.length()) {char jc = s[j];if (count[jc] > 0) {total--;}count[jc]--;while (total == 0) {minLen = min(minLen, j - i + 1);char ic = s[i];if (count[ic] >= 0) {total++;}count[ic]++;i++;}j++;}return minLen;
}int main() {string s;cin >> s;cout << getResult(s) << endl;return 0;
}

C 版本

#include <stdio.h>
#include <string.h>// 定义一个结构体来模拟哈希映射
typedef struct {char key;int value;
} Entry;int getResult(const char* s) {// 使用数组模拟哈希映射,记录W, A, S, D的数量Entry count[4] = {{'W', 0},{'A', 0},{'S', 0},{'D', 0}};int n = strlen(s);// 统计每个字符的数量for (int i = 0; i < n; i++) {for (int j = 0; j < 4; j++) {if (s[i] == count[j].key) {count[j].value++;break;}}}int avg = n / 4; // 计算每个字符在平衡状态下应有的平均数量int total = 0; // 记录多余字符的总数int flag = 1; // 标记是否已经平衡for (int j = 0; j < 4; j++) {if (count[j].value > avg) {flag = 0; // 标记为不平衡count[j].value -= avg; // 计算多余部分total += count[j].value; // 更新多余字符总数} else {count[j].value = 0; // 设置为0,表示不需要调整}}if (flag) return 0; // 如果已经平衡,返回0int i = 0;int j = 0;int minLen = n; // 初始化最短子串长度while (j < n) {char jc = s[j];for (int k = 0; k < 4; k++) {if (jc == count[k].key) {if (count[k].value > 0) {total--;}count[k].value--;break;}}while (total == 0) {minLen = (j - i + 1 < minLen) ? j - i + 1 : minLen;char ic = s[i];for (int k = 0; k < 4; k++) {if (ic == count[k].key) {if (count[k].value >= 0) {total++;}count[k].value++;break;}}i++;}j++;}return minLen;
}int main() {char s[1001];scanf("%s", s);printf("%d\n", getResult(s));return 0;
}

代码讲解

  1. 输入输出

    • C++: 使用cincout从标准输入输出读取和打印。
    • C: 使用scanfprintf进行输入输出操作。
  2. 数据结构

    • C++: 使用unordered_map来记录每个字符的计数。
    • C: 使用结构体数组模拟哈希映射,进行字符计数。
  3. 逻辑流程

    • 统计输入字符串中"W", “A”, “S”, "D"的数量。
    • 计算每种字符在平衡状态下应有的数量。
    • 使用滑动窗口技术寻找满足条件的最短子串:
      • 当窗口内的子串使得所有字符达到平衡状态时,记录当前子串长度。
      • 尝试缩小窗口以寻找更短的子串。

希望这些代码和讲解能够帮助你理解这段算法!如果有进一步的疑问或需要更多的解释,请随时告诉我。

六、尾言

什么是华为OD?

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

为什么刷题很重要?

  1. 机试是进入技术面的第一关:
    华为OD机试(常被称为机考)主要考察算法和编程能力。只有通过机试,才能进入后续的技术面试环节。

  2. 技术面试需要手撕代码:
    技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

  3. 入职后的可信考试:
    入职华为后,还需要通过“可信考试”。可信考试分为三个等级:

    • 入门级:主要考察基础算法与编程能力。
    • 工作级:更贴近实际业务需求,可能涉及复杂的算法或与工作内容相关的场景题目。
    • 专业级:最高等级,考察深层次的算法以及优化能力,与薪资直接挂钩。

刷题策略与说明:

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

  1. 关注历年真题:

    • 题库中的旧题占比较大,建议优先刷历年的A卷、B卷、C卷、D卷题目。
    • 对于每道题目,建议深度理解其解题思路、代码实现,以及相关算法的适用场景。
  2. 适应新题目:

    • E卷中包含全新题目,需要掌握全面的算法知识和一定的灵活应对能力。
    • 建议关注新的刷题平台或交流群,获取最新题目的解析和动态。
  3. 掌握常见算法:
    华为OD考试通常涉及以下算法和数据结构:

    • 排序算法(快速排序、归并排序等)
    • 动态规划(背包问题、最长公共子序列等)
    • 贪心算法
    • 栈、队列、链表的操作
    • 图论(最短路径、最小生成树等)
    • 滑动窗口、双指针算法
  4. 保持编程规范:

    • 注重代码的可读性和注释的清晰度。
    • 熟练使用常见编程语言,如C++、Java、Python等。

如何获取资源?

  1. 官方参考:

    • 华为招聘官网或相关的招聘平台会有一些参考信息。
    • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
  2. 加入刷题社区:

    • 找到可信的刷题交流群,与其他备考的小伙伴交流经验。
    • 关注知名的刷题网站,如LeetCode、牛客网等,这些平台上有许多华为OD的历年真题和解析。
  3. 寻找系统性的教程:

    • 学习一本经典的算法书籍,例如《算法导论》《剑指Offer》《编程之美》等。
    • 完成系统的学习课程,例如数据结构与算法的在线课程。

积极心态与持续努力:

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

考试注意细节

  1. 本地编写代码

    • 在本地 IDE(如 VS Code、PyCharm 等)上编写、保存和调试代码,确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误,提高代码准确性。
  2. 调整心态,保持冷静

    • 遇到提示不足或实现不确定的问题时,不必慌张,可以采用更简单或更有把握的方法替代,确保思路清晰。
  3. 输入输出完整性

    • 注意训练和考试时都需要编写完整的输入输出代码,尤其是和题目示例保持一致。完成代码后务必及时调试,确保功能符合要求。
  4. 快捷键使用

    • 删除行可用 Ctrl+D,复制、粘贴和撤销分别为 Ctrl+CCtrl+VCtrl+Z,这些可以正常使用。
    • 避免使用 Ctrl+S,以免触发浏览器的保存功能。
  5. 浏览器要求

    • 使用最新版的 Google Chrome 浏览器完成考试,确保摄像头开启并正常工作。考试期间不要切换到其他网站,以免影响考试成绩。
  6. 交卷相关

    • 答题前,务必仔细查看题目示例,避免遗漏要求。
    • 每完成一道题后,点击【保存并调试】按钮,多次保存和调试是允许的,系统会记录得分最高的一次结果。完成所有题目后,点击【提交本题型】按钮。
    • 确保在考试结束前提交试卷,避免因未保存或调试失误而丢分。
  7. 时间和分数安排

    • 总时间:150 分钟;总分:400 分。
    • 试卷结构:2 道一星难度题(每题 100 分),1 道二星难度题(200 分)。及格分为 150 分。合理分配时间,优先完成自己擅长的题目。
  8. 考试环境准备

    • 考试前请备好草稿纸和笔。考试中尽量避免离开座位,确保监控画面正常。
    • 如需上厕所,请提前规划好时间以减少中途离开监控的可能性。
  9. 技术问题处理

    • 如果考试中遇到断电、断网、死机等技术问题,可以关闭浏览器并重新打开试卷链接继续作答。
    • 出现其他问题,请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利,取得理想成绩!


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

相关文章

币安面经(2)

自我介绍 项目介绍 qps 数据量 缓存一致性&#xff1f; qps 使用缓存&#xff1a; 将热点数据缓存在内存中&#xff0c;提高读取效率。 负载均衡&#xff1a; 使用负载均衡器&#xff08;如 Nginx&#xff09;分配请求&#xff0c;避免某一节点过载。 异步处理&#xff1a; 对…

SQLite 3.48.0 发布,有哪些更新?

SQLite 开发团队于 2025 年 1 月 14 日发布了 SQLite 3.48.0 版本&#xff0c;我们来解读一下新版本的改进功能。 EXPLAIN QUERY PLAN SQLite 使用 EXPLAIN QUERY PLAN 命令获取查询语句的执行计划&#xff0c;新版本改进了执行计划输出结果中的覆盖索引优化信息&#xff1a;…

Spring项目 spring-boot-actuators配置(健康检查)

文章目录 **结果展示**actuators &#xff08;健康监查&#xff09;1、添加配置2、配置管理 本文介绍了如何安装健康检查&#xff0c;和配置启用健康检查的info和health端点 有问题请私信问题或者评论区&#xff0c; 结果展示 http://127.0.0.1:8080/actuator {"_links…

b站视频(网页加客户端)+本地视频 生成回链

b站视频(网页加客户端)本地视频 生成回链 引言 基于上一篇博客方案 本地视频进度加入笔记根据进度快速锁定视频位置 我想着只有本地的话, 那b站上的视频, 不是每次都得下载下来吗? 如果是一套课程, 直接下载, 然后视频处理成mp3,还好, 如果只是一个视频, 每次这样处理就有点…

网络安全 | 什么是威胁情报?

威胁情报 威胁情报-介绍 威胁情报也称为“网络威胁情报”(CTI)&#xff0c;是详细描述针对组织的网络安全威胁的数据。威胁情报可帮助安全团队更加积极主动地采取由数据驱动的有效措施&#xff0c;在网络攻击发生之前就将其消弭于无形。威胁情报可帮助组织更有效地检测和应对…

HttpClient和HttpGet实现音频数据的高效爬取与分析

一、案例背景 假设我们要爬取一个名为“MusicHub”的音乐网站上的热门歌曲音频数据。MusicHub是一个广受欢迎的音乐平台&#xff0c;提供了丰富的歌曲播放和下载服务。我们的目标是获取该网站上热门歌曲的音频文件&#xff0c;并分析其音频特征&#xff0c;以了解当前的音乐流…

二百八十四、Flink——Flink提交任务两种方式(亲测、附截图)

一、目的 在IDEA中开发好项目后&#xff0c;如何在Flink上提交打包的jar包&#xff0c;有两种方式&#xff0c;分别是WEB UI 界面提交和通过命令行来提交 二、WEB UI 界面提交方式 1 在Submit New Job&#xff0c;点击右侧的Add New&#xff0c;上传打包好的jar包 2 点击刚才…

NumPy;NumPy在数据分析中的应用;NumPy与其他库的搭配使用

NumPy&#xff1b;NumPy在数据分析中的应用&#xff1b;NumPy与其他库的搭配使用 NumPy&#xff1a;Python 数据分析的核心工具什么是 NumPy&#xff1f;NumPy 的主要优势 NumPy 在数据分析中的应用1. 数据处理与清洗2. 数学和统计分析3. 数组变换与矩阵运算 NumPy 与其他库的搭…