西山居3.20笔试代码(未AK 2.6/3.0)

第一题

题意: 给定一个后序遍历数组, 求这个后序遍历是否是一个对应二叉搜索树的后序遍历 思路: 我们先假定它可以构成BST 拿到数组先排个序, 得到中序遍历结果 我们用后序遍历结果和中序遍历结果去构造二叉树 看能否正常构造 不能返回false 能则返回true 以下代码beat 80%, 可能有corner case没考虑到

vector<int> inOrder;
vector<int> lastOrder;

bool build(int inL, int inR, int laL, int laR) {
  if (inL == inR && laL == laR && inOrder[inL] == lastOrder[laL]) return true;
  // 定根节点
  int roVal = lastOrder[laR];
  int idx;
  int cnt = 0;
  set<int> s1;
  set<int> s2;
  bool find = false;
  // 在中序中找到根节点 区分左右
  for (int i = inL; i <= inR; i++) {
    if (inOrder[i] == roVal) {
      idx = i;
      find = true;
      break;
    }
  }
  if (!find) return false;
  // 两边的元素
  for (int i = inL; i <= inR; i++) {
    if (i < idx) {
      s1.insert(inOrder[i]);
    }
    if (i > idx) {
      s2.insert(inOrder[i]);
    }
  }
  // 查看元素是否相同
  for (int i = laL; i < laL + s1.size(); i++) {
    if (s1.find(lastOrder[i]) == s1.end()) return false;
  }

  for (int i = laR - 1; i >= laR - s2.size(); i--) {
    if (s2.find(lastOrder[i]) == s2.end()) return false;
  }
  // 递归
  bool L = build(inL, idx - 1, laL, laL + s1.size() - 1);
  bool R = build(idx + 1, inR, laL + s1.size(), laR - 1);
  return L && R;
}

bool IsPostOrderTraversal(vector<int>& pnArr) {
  // write code here
  lastOrder = pnArr;
  inOrder = pnArr;
  sort(inOrder.begin(), inOrder.end());
  return build(0, pnArr.size() - 1, 0, pnArr.size() - 1);
}

第二题

给定一个字符串数组 返回TOP K频率的字符串, 若相同按字典序排序 思路: 统计排序即可 最简单的一题 AC

vector<string> topKFrequent(vector<string>& words, int k) {
  map<string, int> table;
  for (int i = 0; i < words.size(); i++) {
    if (table.find(words[i]) == table.end()) {
      table[words[i]] = 1;
    } else {
      table[words[i]] = table[words[i]] + 1;
    }
  }
  vector<pair<int, string>> info;
  for (auto it = table.begin(); it != table.end(); it++) {
    string s = it->first;
    // 这里是前K个 需要逆序排 所以直接塞个负值
    int w = -it->second;
    info.push_back(make_pair(w, s));
  }
  vector<string> ans;
  for (int i = 0; i < k; i++) {
    ans.push_back(info[i].second);
  }
  return ans;
}

第三题

香槟杯倒香槟, 上层的杯子溢出来的香槟会等量地分配在下一层的左右两边, 问倒了K杯香槟, 第I层第J列的香槟杯有多少香槟(占比)

思路: 首先确定前多少层是满的,哪一层半满 半满的这一层是按什么方式来分配的 可以计算每一层分配的权值, 因为样例的精度不高(%.5f), 直接用double算都可以骗过80%的点

第一层 1 第二层 1/2 1/2 第三层 1/4 1/2 1/4 第四层 ...

我们将权重定为w 则 w[i][j] = w[i-1][j] * 0.5 + w[i-1][j-1] * 0.5 半满的层算出多出来的香槟 再按这个权重去分配即可

int least(int n) {
  int level;
  for (level = 1; level <= 100; level++) {
    n -= level;
    if (n <= 0) break;
  }
  if (n == 0) return level;
  return level - 1;
}

double w[200][200] = {0};

void cal() {
  for (int i = 0; i <= 100; i++) {
    memset(w[i], 0, sizeof w[i]);
  }
  w[1][1] = 1.0;
  for (int i = 2; i <= 100; i++) {
    for (int j = 1; j <= i; j++) {
      w[i][j] = w[i - 1][j] * 0.5 + w[i - 1][j - 1] * 0.5;
    }
  }
}

double champagneTower(int poured, int query_row, int query_glass) {
  int level = least(poured);
  int use = 0;
  for (int i = 1; i <= level; i++) use += i;
  int last = poured - use;
  debug(w[query_row + 1][query_glass + 1]);
  if (query_row + 1 <= level) return 1.0;
  if (query_row + 1 > level + 1) return 0.0;
  return w[query_row + 1][query_glass + 1] * last;
}