gpt4 book ai didi

string - 使由 '{' 、 '}' 、 '[' 、 ']' 、 '(' 、 ')' 组成的括号字符串的最小加法有效

转载 作者:行者123 更新时间:2023-12-04 11:33:44 25 4
gpt4 key购买 nike

这个问题是对熟悉的堆栈问题( https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/ )的补充,我们必须返回最小加法次数以使括号字符串有效。但是这个问题只包含'('和')'。如果我们将该问题扩展到其他类型的括号,如“[”、“]”、“{”、“}”,会发生什么。我刚刚在与 friend 的讨论中遇到了这个问题,需要关于如何处理的帮助。
例如:[[[{{}]]){)}) -> [[[{{ } }]] ] ( ){ ( )} ( )
在这种情况下,答案是添加 5 个以使其有效。
我想不出合适的方法。我考虑的两种方法是:

  • 与普通问题类似,我们在浏览字符串时将开始类型 '(', '{', '[' 推送到堆栈,如果我们找到结束类型 ')', '}', ']' 我们检查在栈顶,如果它们相互补充,我们弹出并继续,否则我们增加计数器并继续而不弹出。遍历字符串后,我们将答案输出为计数器和堆栈大小的总和。在这种方法中,上面的示例将不起作用,因为额外的 '{' 会破坏该方法。
  • 另一种方法类似于上面的即。我们压入括号的开始类型,如果我们找到一个结束类型并且堆栈的顶部与它互补,我们弹出并继续字符串,否则我们将弹出直到我们得到匹配的字符串,并且每次弹出我们增加计数器。遍历字符串后,总值是计数器和堆栈大小的总和。但这不适用于 {{{{]}}}} 这样的情况,其中字符 ']' 会弹出所有内容并增加答案。

  • 我也在考虑将这些结合起来,更像是一个动态规划,我们将最大程度地看到最高值,或者看到堆栈中的匹配项或堆栈是否为空。但我不确定这两种情况是否是唯一需要考虑的情况。

    最佳答案

    解释
    我们将逐个字符地处理我们的输入字符串,并更新目前遇到的有关括号的某些信息。对于每个括号类型,创建一个堆栈以保留 职位未补偿的左括号。基本上,它表示在检查时需要多少当前类型的右括号才能使字符串有效。
    对于输入的每个括号,执行以下操作之一:

  • 如果括号是开放的(任何类型),只需将其位置添加到相应的堆栈中。
  • 否则,它是一个右括号。如果堆栈中没有左括号,只需增加结果总和 - 可以立即补偿不平衡的右括号。
  • 最后,它是一个右括号,当前类型的堆栈中有左括号。所以,把位于同类型的最后一个左括号和当前括号之间的其他类型的所有不平衡括号的数量相加!不要忘记从堆栈中删除匹配的元素。

  • 最后,将每个堆栈的剩余大小添加到结果总和中,因为每种类型可能仍然存在不平衡的左括号。
    代码
    我在 中创建了一个简单的解决方案C++ ,但如果需要,它可以轻松转换为任何其他语言:
    #include <iostream>
    #include <stack>
    #include <unordered_map>

    bool isOpeningBracket(char bracket) {
    return bracket == '(' || bracket == '[' || bracket == '{';
    }

    int main() {
    std::string line;
    std::cin >> line;
    std::unordered_map<char, char> closingToOpeningBracket = {
    {')', '('},
    {']', '['},
    {'}', '{'}
    };

    std::unordered_map<char, std::unique_ptr<std::stack<uint64_t>>> bracketsMap;
    bracketsMap['{'] = std::make_unique<std::stack<uint64_t>>();
    bracketsMap['['] = std::make_unique<std::stack<uint64_t>>();
    bracketsMap['('] = std::make_unique<std::stack<uint64_t>>();
    uint64_t addOperations = 0;

    for(auto i = 0; i < line.size(); i++) {
    auto bracket = line[i];
    bool isOpening = isOpeningBracket(bracket);

    auto key = bracket;
    if (!isOpening) {
    key = closingToOpeningBracket[bracket];
    }
    auto &bracketStack = bracketsMap[key];
    if (isOpening) {
    bracketStack->push(i);
    } else if (!bracketStack->empty()) {
    auto openingBracketPosition = bracketStack->top();
    bracketStack->pop();

    for (auto & [key, value] : bracketsMap) {
    while (!value->empty() && value->top() > openingBracketPosition) {
    addOperations++;
    value->pop();
    }
    }
    } else {
    addOperations++;
    }
    }

    for (auto & [key, value] : bracketsMap) {
    addOperations += value->size();
    }

    std::cout << addOperations << "\n";

    return 0;
    }
    时空复杂度
    该解决方案的时间和空间复杂度为 O(n)。

    关于string - 使由 '{' 、 '}' 、 '[' 、 ']' 、 '(' 、 ')' 组成的括号字符串的最小加法有效,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64218609/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com