模式匹配

题十：解码字符串

腾讯2019校招

小Q想要给他的朋友发送一个神秘的字符串，但是他发现字符串过长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同的字符串S将会压缩为[m|S]（m为一个整数且1⇐m⇐100），例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入描述：

输入第一行包含一个字符串S，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压缩后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出描述：

输出一个字符串，代表解压后的字符串。

输入示例：

HG[3|B[2|CA]]F

输出示例：

HGBCACABCACABCACAF

说明：

HG[3|B[2|CA]]F ->
HG[3|BCACA]F ->
HGBCACABCACABCACAF

个人觉得我的解法很烂，而且太繁琐，但是目前还想不出更好的。代码也写的比较乱orz. 主要想法是遍历一遍字符串，如果不是特定的压缩模式，直接添加到结果中就好，如果遇到了特殊模式（[3|AB]），将该模式提取出来交给另一个函数解码，模式可能递归存在，所以使用一个栈确保提取出正确的模式。

#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
 
// decode pattern like "[3|abc]"
// note: end is included
string PatternDecode(const string& s, size_t beg, size_t end)
{
  // the minmal len: [3|a]
  // beg=0, end=4
  if (end - beg >= 4)
  {
    string ret;
    auto pos_delimiter = s.find('|', beg);
    int num_repeats = std::stoi(s.substr(beg+1, pos_delimiter-beg-1));
    {
      auto pos_left = s.find('[', pos_delimiter);
      if (pos_left < end) // has sub-pattern
      {
        ret += s.substr(pos_delimiter+1, pos_left-pos_delimiter-1);
        auto pos_right = s.rfind(']', end-1);
        ret += PatternDecode(s, pos_left, pos_right);
        ret += s.substr(pos_right+1, end-pos_right-1);
      }
      else  // has not sub-pattern
      {
        ret += s.substr(pos_delimiter+1, end-pos_delimiter-1);
      }
    }
    string res;
    while (num_repeats--)
      res += ret;
 
    return res;
  }
  else
  {
    throw std::invalid_argument("range too small");
  }
}
 
void Decode(const string& s, string* o)
{
  if (s.empty())
    throw std::invalid_argument("empty coded string");
 
  stack<size_t> stk;
  for (size_t i = 0; i != s.size(); ++i)
  {
    if (stk.empty() && std::isalpha(s[i]))
    {
      o->push_back(s[i]);
    }
    else if (s[i] == '[')
    {
      stk.push(i);
    }
    else if (s[i] == ']')
    {
      // if the stk has only one elem, then the last ']' of
      // a pattern is determined, we shall first decode this
      // pattern before going on.
      if (stk.size() == 1)
      {
        size_t pattern_beg = stk.top();
        o->append(PatternDecode(s, pattern_beg, i));
      }
      stk.pop();
    }
  }
}
 
int main()
{
  // io
  string input;
  cin >> input;
  string output;
  Decode(input, &output);
  cout << output;
  return 0;
}

排序

场景题

括号匹配

原题：https://leetcode.com/problems/valid-parentheses/

class Solution {
public:  
  bool isValid(string s) {    // 此解法还是比较elegant的
    stack<char> stk;
        
    for (auto &c : s)
    {
      switch (c)
      {
        case '{': stk.push('}'); break;
        case '(': stk.push(')'); break;
        case '[': stk.push(']'); break;
        default:
        {
          if (stk.empty() || c != stk.top()) // 巧妙地判断了stk非空
              return false;
          else
              stk.pop();
        }
      }
    }
    return stk.empty();
  }
};

树相关