华为笔试 - 占位符替换

2020春招华为出了3道算法题。两道搜索一道没看。其中第一道是Linux Shell占位符替换。用了深搜解决。

题目大意

在Linux Shell中，常用${xx}的形式做命令的占位替换。当shell的字符串中局部需要其他变量替换的时候，就用此占位符来代表变量的代入。例如：

a=1234
b=/abc/${a}/

则b变量最终数据为：

/abc/1234/

现在有一组（可能）包含占位符的变量，他们的占位符替换不循环引用。问这组变量最后的变量应该被替换为怎么样的字符串？
如：

a=abc
b=de/${a}/fg
c=/hj/${b}/${a}

a替换如b变量中的占位符，得：/de/abc/fg
b替换c变量中的占位符，得：/hj/de/abc/fg/abc
如此，最后一行得输出为：/hj/de/abc/fg/abc

输入

一共$N$行。
第1行为一个整数$n$，即后继拥有得变量数。
第2到第$N-1$一共$n$行，为每个变量式的表达；

3
a=ab
b=cd/${a}
c=/def/${b}/${a}

输出

一行，为第n行的替换后的结果。上述输入结果：

/def/cd/ab/ab

Write Up

此题解法多，深搜最好理解：用一个串来记录结果。假设为字符串$S$。从头到尾搜索最后一个变量的串。遇到占位符，立即搜索该占位符，然后加上去。三种形式：

• 如果没有${xxx}这种形式，则后续字符串没有变量，附加上去就好；如：a=ab，没有任何东西。S += "ab" => "ab"；这是递归结束情况。因为原题描述，该图为DAG。
• 如果第1个字符为$，则说明开头即变量，搜索。如：a=ab, b=${a}，需要搜索变量a附加上去；
• 其余情况：先附加一部分，截取子串；如：current -> /ab/${a}，则先S += "/ab/"，再搜索${a}

完整代码如下：

#include <cmath>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct thePair {
  string first;
  string second;
  thePair(string a, string b) : first(a), second(b) {}
};

vector<thePair> p;
string finalRes = "";

void dfs(string cur) {
  while (cur.size() > 0) {
    int pos = cur.find_first_of("$");
    if (pos == string::npos) {
      finalRes += cur;
      return;
    }

    if (pos != 0) finalRes += cur.substr(0, pos);

    pos = cur.find_first_of("{");
    int left = cur.find_first_of("}");
    string next = cur.substr(pos + 1, left - pos - 1);
    for (thePair& j : p) {
      if (j.first == next) {
        dfs(j.second);
        break;
      }
    }
    cur = cur.substr(left + 1);
  }
}

thePair split(string n) {
  int i = 0;
  for (; i < n.size(); i++) {
    if (n[i] == '=') {
      break;
    }
  }
  return thePair(n.substr(0, i), n.substr(i + 1));
}

int main(int argc, char const* argv[]) {
  int n;
  cin >> n;
  vector<string> vec;
  for (int i = 0; i < n; i++) {
    string m;
    cin >> m;
    p.push_back(split(m));
  }

  string target = p[p.size() - 1].second;
  dfs(target);
  cout << finalRes << endl;
  return 0;
}

finalRes为最终需要的结果。thePair为分割变量与字符串所用。不断缩短cur，即目前状态，最后清零。finalRes为全局变量，在oi中很习惯使用。