11.1秋招进展-周末摆烂

# P1229 遍历问题## 题目描述我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。## 输入格式共两行，第一行表示该二叉树的前序遍历结果 s_1，第二行表示该二叉树的后序遍历结果 s_2。保证至少存在一棵二叉树满足给出的信息，s _ 1, s _ 2 中只含小写字母，且在某个字符串中不存在相同的字母。## 输出格式输出可能的中序遍历序列的总数，结果不超过 2^{63}-1。#1##1```abccba```##1```4```定义 dfs(preL, preR, postL, postR)返回该区间对应的中序序列数。根 = pre[preL]，在后序中找到根的位置 postRootIdx。左子树长度 = postRootIdx - postL。如果左子树长度 == 0（即 pre[preL+1] 不存在或 pre[preL+1] == post[postR-1] 吗？要仔细判断）—— 实际上判断条件：前序第二个字符 pre[preL+1] 在后序中的位置如果是 postR-1（即后序的倒数第二个），则说明左子树为空或右子树为空？其实应该是：前序第二个字符在后序中的位置如果是 postR-1，说明该节点只有一个孩子，且这个孩子是左孩子还是右孩子不确定。此时，总方案数 = dfs(左子树) * dfs(右子树) * 2？但注意，这里左子树长度是 1（那个孩子），右子树长度 0，所以 dfs(左子树) 是那个孩子的子树的中序方案数，dfs(右子树)=1，所以这一层方案数 = dfs(child) * 2。如果左子树长度 > 0 且 pre[preL+1] != post[postR-1]，则正常划分左右，方案数 = dfs(left) * dfs(right)。代码如下：#include <iostream>#include <string>#include <vector>using namespace std;typedef long long ll;string pre, post;vector<int> post_pos(26, -1);ll solve(int preL, int preR, int postL, int postR) {if (preL > preR) return 1;if (preL == preR) return 1;int root = pre[preL];int leftRoot = pre[preL + 1];int idx = post_pos[leftRoot - 'a'];int leftLen = idx - postL + 1;if (leftLen == 0 || pre[preL + 1] == post[postR - 1]) {// 此时 preL+1..preR 是唯一的孩子子树return solve(preL + 1, preR, postL, postR - 1) * 2;} else {ll leftCount = solve(preL + 1, preL + leftLen, postL, idx);ll rightCount = solve(preL + leftLen + 1, preR, idx + 1, postR - 1);return leftCount * rightCount;}}int main() {cin >> pre >> post;int n = pre.size();for (int i = 0; i < n; i++) {post_pos[post[i] - 'a'] = i;}ll ans = solve(0, n - 1, 0, n - 1);cout << ans << endl;return 0;}

之前本科以及研一研二就听说着毕业季，就业难，压力大，看着学长学姐师兄师姐找工作也是挺难的，我听着感觉确实得早点准备，早早的开始准备项目，找找实习，充实充实的阅历，提高自己的竞争力，不知不觉就到了我找工作的时候刚开始打算8月底写好简历以及面试准备再投递的，结果到了七月底就发现很多公司已经开了，赶紧准备简历，还有项目什么的，匆匆忙忙，终于在8.10号搞定了的这时候开始投递，当时还感觉自己应该做好了准备，而且实习经历啥的咱都有，学历也还不错，拿个sp应该没问题吧（有点小飘）而且投递的时候我也只投递我感觉不错的几个公司，如图一所示，但是投递之后，虾皮高德直接简历挂，飞腾投递完以后就了无音信，美团一面回...

我的物欲不是很高，工资大致够用就行。比起这个，我更喜欢有时间去做自己喜欢的事：爬山，旅游，跟朋友见面，摄影，健身。薪资再高，每天晚上下班回到家就是睡，周末一天休息也是睡，会让我觉得失去了自我，没有任何意义。

目前这个就业环境，很多朋友说自己几乎是毕业即失业，对于我们理工科的同学，也要提前做好准备了。 我关注昇维旭其实有一段时间了，对比往年，今年新开了AI算法的岗位，相比互联网公司的卷，半导体是一种新的发展方向，AI在芯片制造的其实有很大的应用空间。深圳国资背景、做存储芯片研发的企业，前景有、技术竞争力有，我几乎没怎么犹豫，就是奔着国企去的，了解的信息在脑子里过了一遍，确认岗位要求和我的专业背景匹配，就投了。 秋招第十投了，又完成了一个小目标，很期待了，期待能进入下一轮，如果在昇维旭做AI算法，还是很稳健的，压力会相对小一些。现在已经一面了， 跟初试面试官聊下来，AI这个团队在做的事情还是非常有意思...