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

华为OD机试 - 字符串消除 - 栈Stack（Python/JS/C/C++ 2024 C卷 100分）

news 2024/11/1 9:24:12

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

游戏规则：输入一个只包含英文字母的字符串, 字符串中的两个字母如果相邻且相同,就可以消除。在字符串上反复执行消除的动作, 直到无法继续消除为止,此时游戏结束。输出最终得到的字符串长度。

二、输入描述

输入原始字符串str 只能包含大小写英文字母,字母的大小写敏感, str长度不超过100

三、输出描述

输出游戏结束后，最终得到的字符串长度。

四、测试用例

测试用例1

1、输入

2、输出

3、说明

gg可以直接消除得到空串长度为0

测试用例2

1、输入

nezhaahZe

2、输出

五、解题思路

1、list倒序循环中

利用list倒序循环中可以删除元素的特性，删除相邻的相同字符。
如果循环后，有字符抵消，则递归。

2、栈Stack

定义Stack，存储没有抵消的字符
栈顶元素和当前元素一致，则抵消
不一致，则加入栈
输出栈的大小即结果

六、Python算法源码

# 定义函数来处理字符消除
def remove_adjacent_duplicates(s):stack = []for char in s:# 检查栈顶元素是否与当前字符相同if stack and stack[-1] == char:stack.pop()  # 消除else:stack.append(char)  # 添加到栈return len(stack)  # 返回栈的长度# 测试用例
print(remove_adjacent_duplicates("gg"))  # 输出 0
print(remove_adjacent_duplicates("nezhaahZe"))  # 输出 5

七、JavaScript算法源码

// 定义函数来处理字符消除
function removeAdjacentDuplicates(s) {let stack = [];for (let char of s) {// 检查栈顶元素是否与当前字符相同if (stack.length > 0 && stack[stack.length - 1] === char) {stack.pop();  // 消除} else {stack.push(char);  // 添加到栈}}return stack.length;  // 返回栈的长度
}// 测试用例
console.log(removeAdjacentDuplicates("gg"));  // 输出 0
console.log(removeAdjacentDuplicates("nezhaahZe"));  // 输出 5

八、C算法源码

#include <stdio.h>
#include <string.h>int remove_adjacent_duplicates(char *s) {char stack[101];  // 假设最大长度为100，栈多分配1int top = -1;  // 栈顶索引for (int i = 0; s[i]; i++) {// 检查栈顶元素是否与当前字符相同if (top != -1 && stack[top] == s[i]) {top--;  // 消除} else {stack[++top] = s[i];  // 添加到栈}}return top + 1;  // 返回栈的长度
}// 测试用例
int main() {printf("%d\n", remove_adjacent_duplicates("gg"));  // 输出 0printf("%d\n", remove_adjacent_duplicates("nezhaahZe"));  // 输出 5return 0;
}

九、C++算法源码

#include <iostream>
#include <stack>
#include <string>int removeAdjacentDuplicates(const std::string& s) {std::stack<char> stack;  // 创建栈for (char c : s) {// 检查栈顶元素是否与当前字符相同if (!stack.empty() && stack.top() == c) {stack.pop();  // 消除} else {stack.push(c);  // 添加到栈}}return stack.size();  // 返回栈的长度
}// 测试用例
int main() {std::cout << removeAdjacentDuplicates("gg") << std::endl;  // 输出 0std::cout << removeAdjacentDuplicates("nezhaahZe") << std::endl;  // 输出 5return 0;
}