hiho一下第75周《Colorful Lecture Note》题目分析

2
1

题目描述

给定一个字符串，其中某些字符被一对颜色标签 包裹住。标签可能互相嵌套，每个字符的颜色由包裹住其最内层的标签确定，问红黄蓝颜色的字母各有多少个。

本题需要注意两点：一是字符串可能包含空格，二是可能存在字符没有被任何标签包裹住。

解题思路

由于需要字符串进行分析，首先我们要考虑如何将字符串分割。这里有两个条件：

  • <和>之间为一个标签，比如<yellow>,</yellow>
  • >和<之间为一段字符串，比如<red>aaaa</red>中的aaaa

根据这两个条件，我们可以将整个字符串分解成一个一个部分，比如：

<yellow>aaa<blue>bbb</blue>ccc</yellow>dddd<red>abc</red>

分解为：

<yellow>,aaa,<blue>,bbb,</blue>,ccc,</yellow>,dddd,<red>,abc,</red>

对于分割的过程，可以参考下面的代码，其中word[]是分割后的数组，n是长度：

prev = 0
n = 0
word = []
For i = 1 .. the length of string
    If string[i] == '<' Then
        // string[prev .. i - 1]的部分为一个字符串
        // 此处有可能出现 prev > i - 1 的情况，则表示出现了连续标签，如"<red><blue>"
        // 若出现这种情况，则不加入word中。
        If prev <= i - 1 Then word[++n] = string[prev .. i - 1]
        prev = i
    Else 
        If string[i] == '>' Then
            //string[prev .. i]的部分为一个标签
            word[++n] = string[prev .. i]
            prev = i + 1
        End If
    End If
End For

由于中标签是可以嵌套定义的，而一段字符串的颜色是跟直接包含它的标签相关。因此对于：

<yellow><blue>word</blue></yellow>

其中word最终显示为蓝色。

对于这种嵌套的处理，这里所采用的做法是将子标签进行递归，并且子标签内所有内容不计入父标签。

举个例子：

<yellow>,aaa,<blue>,word,</blue>,bbb,</yellow>

首先我们读取到<yellow>，我们知道有一个新的标签，新建计数器cnt = 0。

接下来处理了aaa，这是一个字符串，所以直接统计字母个数，cnt = 3。

紧接着我们读取到了<blue>，我们发现这是一个新的标签，因此我们进入递归的过程。直到遇到</blue>，再跳出回到当前。

之后我们读取到了bbb，仍然加入当前<yellow>的计数器，cnt = 3+3 = 6。

最后读取到</yellow>，结束这个<yellow>标签。

将以上的过程写成伪代码为：

// 假设将字符串分割之后得到word[]数组,长度为n
// word[i]表示第i个部分
// color是当前颜色
dfs(i, color)
    cnt = 0
    While (i <= n)
        If (word[i]不是标签)
            cnt = cnt + word[i].length
        Else    // word[i]是标签
            If (word[i]是起始标签)
                i = dfs(i+1, getColor(word[i]))    // 一个子标签，迭代处理，并返回子标签结尾
            Else
                Break         // 结束标签，因此跳出循环
            End If
        End If
        i = i + 1
    End While
    color对应的颜色统计增加cnt
    Return i    // 当前结束标签的位置

由于每个word只会处理一次，因此整个程序时间复杂度为 O(n)。


对于上面的dfs算法，如果仔细观察，可以发现其本质就是一个颜色入栈出栈的过程。

当发现开始标签时，进行入栈；当发现结束标签时进行出栈。

因此伪代码可以写作：

top = 0
For i = 1 .. n
    If (word[i]不是标签)
        If (top != 0) // 考虑可能出现不在标签内的字符串
            stack[top].cnt = stack[top].cnt + word[i].length
        End If
    Else
        If (word[i]是起始标签)
            top = top + 1
            stack[top].color = getColor( word[i] ); // 获取标签的颜色
            stack[top].cnt = 0
        Else
            stack[top].color对应的颜色统计增加stack[top].cnt
            top = top - 1
        End If
    End If
End For

并且可以将整个预处理的过程也放在手工栈中：

prev = 0
For i = 1 .. the length of string
    If string[i] == '<' Then
        //string[prev .. i - 1]的部分为一个字符串

        If (top != 0) // 考虑可能出现不在标签内的字符串
            stack[top].cnt = stack[top].cnt + i - prev
        End If

        prev = i
    Else 
        If string[i] == '>' Then
            // string[prev .. i]的部分为一个标签

            If (string[prev .. i]是起始标签)
                top = top + 1
                stack[top].color = getColor( string[prev .. i]] );  // 获取标签的颜色
                stack[top].cnt = 0
            Else
                stack[top].color对应的颜色统计增加stack[top].cnt
                top = top - 1
            End If

            prev = i + 1
        End If
    End If
End For

这两种方法都可以顺利解决该题目，你可以选择擅长的方法来解决。

6 answer(s)

0 
int main() {
    string s; 
    int c[3] = {0, 0, 0}; // red, yellow, blue
    getline(cin, s);
    int n = s.size();
    int i = 0;
    stack<int> st;
    int counter = 0;
    while (i < n) {
        if (s[i] == '<') {
            ++i;
            if (s[i] == '/') {
                ++i;
                if (s[i] == 'r') c[0] += counter; 
                else if (s[i] == 'y') c[1] += counter; 
                else if (s[i] == 'b') c[2] += counter;
                counter = st.top();
                st.pop();
            } else {
                st.push(counter);
                counter = 0;
            }
            while (i < n && s[i] != '>') ++i;
        } 
        else if (s[i] >= 'a' && s[i] <= 'z') ++counter;
        ++i;
    }

    cout << c[0] << " " << c[1] << " " << c[2] << endl;
    return 0;
}
0

std::string input_str; std::cin>>input_str; len = input_str.length();

Label nocolor; nocolor.color = "nocolor"; nocolor.cnt = 0; while(icnt += i-prev; } else { result_vec.push_back(nocolor); } } else { result_vec_iter = std::find_if(result_vec.begin(), result_vec.end(), label_stack.top()); if(result_vec_iter != result_vec.end()) { result_vec_iter->cnt += i-prev; } else { Label newcolor; newcolor.color = label_stack.top().color; newcolor.cnt = i-prev; result_vec.push_back(newcolor); } } prev = i+1; } else { if(input_str[i]=='>') { if(input_str[prev]!='/') { Label nextcolor; nextcolor.color = input_str.substr(prev, i-prev); nextcolor.cnt = 0; label_stack.push(nextcolor); } else { label_stack.pop(); }

        prev = i+1;
    }
}

i++;

}

for(result_vec_iter = result_vec.begin(); result_vec_iter != result_vec.end(); result_vec_iter++) { std::cout<<"color: "<color<<"\t"; std::cout<<"count: "<cnt<

return 0;

0

空格没有影响吗

0 
sada
0

include

include

include

include

include

typedef struct Label { std::string color; int cnt; /* bool operator == (const Label &rht) { return (color.compare(rht.color)==0); } */ bool operator () (const Label &rht) { return (color.compare(rht.color)==0); } //bool operator < (const Label lht, const Label rht) bool operator < (const Label &rht)const { //return (lht.color.compare(rht.color)<0); return (color.compare(rht.color)<0); } }Label;

int main(int argc, char * argv[]) { int prev = 0; int i = 0; int len = 0; std::stack label_stack; //std::stack label_stack; std::vector result_vec; std::vector::iterator result_vec_iter;

std::string input_str;
std::cin>>input_str;
len = input_str.length();

Label nocolor;
nocolor.color = "nocolor";
nocolor.cnt = 0;
while(i<len)
{
    if(input_str[i]=='<')
    {
        if(label_stack.empty())
        {
            result_vec_iter = std::find_if(result_vec.begin(), result_vec.end(), nocolor);
            if(result_vec_iter != result_vec.end())
            {
                result_vec_iter->cnt += i-prev;
            }
            else
            {
                result_vec.push_back(nocolor);
            }
        }
        else
        {
            result_vec_iter = std::find_if(result_vec.begin(), result_vec.end(), label_stack.top());
            if(result_vec_iter != result_vec.end())
            {
                result_vec_iter->cnt += i-prev;
            }
            else
            {
                Label newcolor;
                newcolor.color = label_stack.top().color;
                newcolor.cnt = i-prev;
                result_vec.push_back(newcolor);
            }
        }
        prev = i+1;
    }
    else
    {
        if(input_str[i]=='>')
        {
            if(input_str[prev]!='/')
            {
                Label nextcolor;
                nextcolor.color = input_str.substr(prev, i-prev);
                nextcolor.cnt = 0;
                label_stack.push(nextcolor);
            }
            else
            {
                label_stack.pop();
            }

            prev = i+1;
        }
    }

    i++;
}

for(result_vec_iter = result_vec.begin(); result_vec_iter != result_vec.end(); result_vec_iter++)
{
    std::cout<<"color: "<<result_vec_iter->color<<"\t";
    std::cout<<"count: "<<result_vec_iter->cnt<<std::endl;
}


return 0;

}

0

自己调的没问题。提交就是错误。难道没有测试数据……

  • 自己多测试一些数据 注意输入可能有空格

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲