从字符串中删除计数大于或等于 burst Length 的相邻重复项

Question

给定一个包含重复字符的字符串和一个突发长度，输出该字符串，使得字符串中相同相邻字符的数量小于突发长度。

输入：abbccccdd，burstLen = 3
正确输出：abbdd
我的输出：abbd

输入：abbcccdeaffff，burstLen = 3
正确输出：abbdea
我的输出：abbea

//Radhe krishna ki jytoi alokik
#include <bits/stdc++.h>
using namespace std;

string solve(string s, int burstLen)
{
    stack<pair<char, int>> ms;
    
    for (int i = 0; i < s.size(); i++)
    {
        if (!ms.empty() && ms.top().first == s[i])
        {
            int count = ms.top().second;
            ms.push({s[i], count + 1});
        }
        
        else
        {
            if(ms.empty() == true  ||  ms.top().first != s[i])
            {
                if(!ms.empty() && ms.top().second >= burstLen)
                {
                    int count = ms.top().second;
                    
                    while(!ms.empty() && count--)
                        ms.pop();
                    //(UPDATE)
                     ms.push({s[i], 1});
                }
                
                else
                    ms.push({s[i], 1});
            }
        }

    }
    
    if(!ms.empty() and ms.top().second >= burstLen)
    {
        int count = ms.top().second;
        while(!ms.empty() && count--)
            ms.pop();
    }

    string ans = "";
    while (!ms.empty())
    {
        ans += ms.top().first;
        ms.pop();
    }
    
    reverse(ans.begin(), ans.end());    
    return ans;
}


int main()
{


    
        string s;
        int burstLen;

        cin >> s;
        cin >> burstLen;

        cout << solve(s, burstLen) << "\n";
}

Answer 1

我的解决方法：

创建一个由字符和字符数组成的对堆栈

如果Stack为空或者栈顶元素不等于字符串中的当前元素

情况一：如果栈顶元素的出现次数大于等于k，则存入一个变量say count，将栈顶元素弹出count次。

情况2：如果堆栈为空，则简单地以频率1压入堆栈中的元素。

遍历整个字符串后，如果堆栈顶部元素的频率大于突发，则开始从堆栈中删除元素（计数）次。

现在，我们在堆栈中有遗漏的元素，开始弹出它们并将它们存储在一个字符串中并反转字符串以保持顺序。

Return 新字符串。

更新：已解决。在这种情况下缺少一行 if(ms.empty() == true || ms.top().first != s[i]) 弹出元素后，我们还必须插入当前元素字符频率 1.

#include<iostream>
#include<stack>
using namespace std;

string solve(string s, int burstLen)
{
    stack<pair<char, int>> ms;
    
    for (int i = 0; i < s.size(); i++)
    {
        if (!ms.empty() && ms.top().first == s[i])
        {
            int count = ms.top().second;
            ms.push({s[i], count + 1});
        }
        
        else
        {
            if(ms.empty() == true  ||  ms.top().first != s[i])
            {
                if(!ms.empty() && ms.top().second >= burstLen)
                {
                    int count = ms.top().second;
                    
                    while(!ms.empty() && count--)
                        ms.pop();
                        
                    ms.push({s[i], 1});
                }
                
                else
                    ms.push({s[i], 1});
            }
        }

    }
    
    if(!ms.empty() and ms.top().second >= burstLen)
    {
        int count = ms.top().second;
        while(!ms.empty() && count--)
            ms.pop();
    }

    string ans = "";
    while (!ms.empty())
    {
        ans += ms.top().first;
        ms.pop();
    }
    
    reverse(ans.begin(), ans.end());    
    return ans;
}


int main()
{


    int t;
    cin >> t;
    
    while(t--)
    {
        string s;
        int burstLen;
        cin >> s >>burstLen;

        cout << solve(s, burstLen) << "\n";
    }

}

Answer 2

我尝试了一下，但它看起来很复杂，所以我建议使用标准库中的一些函数来制作一个更简单的函数。

示例：

#include <algorithm>
#include <iostream>
#include <initializer_list>
#include <iterator>

std::string solve(const std::string& in, size_t burstlen) {
    std::string retval;

    for(std::string::const_iterator begin = in.cbegin(), bend;
        begin != in.end();
        begin = bend) 
    {

        // find the first char not equal to the current char
        bend = std::find_if_not(std::next(begin), in.end(), 
                                [curr=*begin](char ch){ return ch==curr; });

        if(std::distance(begin, bend) < burstlen) {
            // length ok, append it
            retval.append(begin, bend);
        }
    }

    return retval;
}

int main() {
    std::initializer_list<std::string> tests{
        "abbccccdd", "abbcccdeaffff"};
    for(auto test : tests) std::cout << solve(test, 3) << '\n';
}

输出：

abbdd
abbdea

Answer 3

至少使用容器适配器 std::queue 而不是 std::stack 会更好，因为不需要调用算法 std::reverse.

此外，如果堆栈的项目包含存储频率的第二个数据成员，那么您可以只为重复字符增加此数据成员，而不是将每个重复字符都放入堆栈中。

例如您程序中的这段代码

    if (!ms.empty() && ms.top().first == s[i])
    {
        int count = ms.top().second;
        ms.push({s[i], count + 1});
    }

使函数定义过于复杂和不清楚，因为相同的字符以不同的频率压入堆栈。

不过，如果您想使用容器适配器 std::stack，函数定义可能看起来更简单。您没有使用 class std::string.

的功能

这是一个演示程序，展示了如何使用您的 std::stack 方法编写函数。

#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <iterator>
#include <algorithm>

std::string solve( const std::string &s, size_t burstLen )
{
    std::stack<std::pair<char, size_t>> stack;
    
    for ( const auto &c : s )
    {
        if ( stack.empty() || stack.top().first != c )
        {
            stack.push( { c, 1 } );
        }
        else
        {
            ++stack.top().second;
        }
    }

    std::string ans;
    
    while ( !stack.empty() )
    {
        if ( stack.top().second < burstLen )
        {
            ans.append( stack.top().second, stack.top().first );
        }
        stack.pop();
    }
    
    std::reverse( std::begin( ans ), std::end( ans ) );
    
    return ans;
}

int main()
{
    std::cout << solve( "abbccccdd", 3 ) << '\n';
    std::cout << solve( "abbcccdeaffff", 3 ) << '\n';
}

程序输出为

abbdd
abbdea

在从左侧和右侧移除一个不小于突发长度的字符序列后，使用堆栈很有趣sub-sequences一个再次不小于突发长度的新序列你还需要将其删除。

在这种情况下，您可以使用两个堆栈。

这是一个演示程序。

#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <iterator>
#include <algorithm>

std::string solve( const std::string &s, size_t burstLen )
{
    std::stack<std::pair<char, size_t>> stack_in;
    
    for ( const auto &c : s )
    {
        if ( stack_in.empty() || stack_in.top().first != c )
        {
            stack_in.push( { c, 1 } );
        }
        else
        {
            ++stack_in.top().second;
        }
    }

    std::stack<std::pair<char, size_t>> stack_out;

    while ( !stack_in.empty() )
    {
        if ( !stack_out.empty() && stack_out.top().first == stack_in.top().first )
        {
            if ( stack_out.top().second + stack_in.top().second < burstLen )
            {
                stack_out.top().second += stack_in.top().second;
            }
            else
            {
                stack_out.pop();
            }
        }
        else if ( stack_in.top().second < burstLen )
        {
            stack_out.push( stack_in.top() );
        }
        
        stack_in.pop();
    }
    
    std::string ans;
    
    while ( !stack_out.empty() )
    {
        ans.append( stack_out.top().second, stack_out.top().first );
        stack_out.pop();
    }
    
    return ans;
}


int main()
{
    std::cout << solve( "abbccccdd", 3 ) << '\n';
    std::cout << solve( "abbcccdeaffff", 3 ) << '\n';
    std::cout << solve( "aabcddeeedccbaa", 3 );
}

程序输出为

abbdd
abbdea
aabbaa

从字符串中删除计数大于或等于 burst Length 的相邻重复项

Remove adjacent Duplicates from a String which have count greater than or equal to burst Length

c++

string

algorithm

stack

data-structures