工行员工,内网发声
近日,在工商银行内部员工论坛"工软之声"上,有员工发了一篇名为《利润是公司的,身体是自己的》的帖子。
呼吁大家准点下班。
作者在帖子指出「没有什么事是真正紧急的」,客户们根本不关心迭代速度,也不关心手机银行是 8.0 还是 9.0,他们只想在日新月异的 UI 中找到转账汇款的入口。那些所谓加班加点做出来的东西,客户大概率不会领情,满足的只是那个跳脚催进度的人罢了。
从这一段的描述听起来,像是工行内部的软件开发人员。
除了对日常工作的感悟,作者还分享了公司内部的一些"情况"。
包括「年假不能简单由员工本人自行安排」的内部论调,以及「年度内不再下发职工疗休养费用额度」新制度。
这一切都与首页上"关于加强基层员工的休假工作的通知"文章形成鲜明对比。
可以看出,作者是一位老员工,公司的变化让其充满了无奈和失望。
前有 去哪儿吹起号角,现有银行人员内网发声。
最近"反卷"势力很猛呀,建议加大力度。
...
回归主题。
来一道和「银行(校招)」相关的算法原题。
题目描述
平台:LeetCode
题号:331
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。
如果它是一个空节点,我们可以使用一个标记值记录,例如 #
。
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
例如,上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"
,其中 #
代表一个空节点。
给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。
编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null
指针的 '#'
。
你可以认为输入格式总是有效的,例如它永远不会包含两个连续的逗号,比如 "1,,3"
。
示例 1:
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
示例 2:
输入: "1,#"
输出: false
示例 3:
输入: "9,#,#,1"
输出: false
二叉树规律解法
事实上,我们能利用「二叉树」的特性来做。
由于「每一个非空节点都对应了 2 个出度,空节点都对应了 0 个出度;除了根节点,每个节点都有一个入度。」
我们可以使用 in
和 out
来分别记录「入度」和「出度」的数量;m
和 n
分别代表「非空节点数量」和「空节点数量」。
同时,一颗合格的二叉树最终结果必然满足 in == out
。
但我们又不能只利用最终 in == out
来判断是否合法,这很容易可以举出反例:考虑将一个合法序列的空节点全部提前,这样最终结果仍然满足 in == out
,但这样的二叉树是不存在的。
我们还需要一些额外的特性,支持我们在遍历过程中提前知道一颗二叉树不合法。
例如,我们可以从合格二叉树的前提出发,挖掘遍历过程中 in
和 out
与 n
和 m
的关系。
证明 1(利用不等式)
我们令非空节点数量为 m
,空节点数量为 n
,入度和出度仍然使用 in
和 out
代表。
找一下 in
和 out
与 n
和 m
之间的关系。
一颗合格二叉树 m
和 n
的最小的比例关系是 1:2,也就是对应了这么一个形状:
4
/ \
# #
而遍历过程中 m
和 n
的最小的比例关系则是 1:0,「这其实对应了二叉树空节点总是跟在非空节点的后面这一性质。」
换句话说,在没到最后一个节点之前,我们是不会遇到 空节点数量 > 非空节点数量 的情况的。
非空节点数量 >= 空节点数量
在遍历没结束前恒成立:
然后再结合「「每一个非空节点都对应了 2 个出度,空节点都对应了 个出度;除了根节点,每个节点都有一个入度」」特性。
在遍历尚未结束前,我们有以下关系:
简单的变形可得:
-
由 变形可得: -
由 变形可得:
即有:
再将 1 和 2 相加,抵消 n
:
-
=> -
=>
因此,在遍历尚未完成时,in
和 out
始终满足上述关系(与空节点数量 n
无关)。
如果不从合格二叉树的前提( )出发,我们是无法得到上述关系式的。
「因此,我们可以一边遍历一边统计「严格出度」和「严格入度」,然后写一个 check
函数去判定 in
、out
和 m
三者关系是否符合要求,如果不符合则说明二叉树不合法。」
伪代码:
class Solution {
public boolean isValidSerialization(String s) {
String[] ss = s.split(",");
int n = ss.length;
int in = 0, out = 0;
for (int i = 0, m = 0; i < n; i++) {
// 统计「严格出度」和「严格入度」...
if (i != n - 1 && !check(m, in, out)) return false;
}
return in == out;
}
boolean check(int m, int in, int out) {
boolean a = (in <= 2 * m - 1), b = (out <= 2 * m);
return a && b;
}
}
注意:因为我们这里的证明使用到的是不等式。因此统计的必须是「严格出度」&「严格入度」,不能假定一个「非空节点(非根)」必然对应两个「出度」和一个「入度」。
要想统计出「严格出度」&「严格入度」在编码上还是有一定难度的。那么是否可以推导出更加简单性质来使用呢?
请看「证明 2」。
证明 2(利用技巧转换为等式)
我们令非空节点数量为 m
,空节点数量为 n
,入度和出度仍然使用 in
和 out
代表。
找一下 in
和 out
与 n
和 m
之间的关系。
一颗合格二叉树 m
和 n
的最小的比例关系是 1:2,也就是对应了这么一个形状:
4
/ \
# #
而遍历过程中 m
和 n
的最小的比例关系则是 1:0,这「其实对应了二叉树空节点总是跟在非空节点的后面这一性质。」
换句话说,在没到最后一个节点之前,我们是不会遇到 空节点数量 > 非空节点数量
的情况的。
非空节点数量 >= 空节点数量
在遍历没结束前恒成立:
之后我们再采用一个技巧,就是「遍历过程中每遇到一个「非空节点」就增加两个「出度」和一个「入度」,每遇到一个「空节点」只增加一个「入度」。而不管每个「非空节点」是否真实对应两个子节点。」
那么我们的起始条件变成:
从第 个等式出发,结合第 个等式:
即可得 ,也就是 恒成立。
Java 代码:
class Solution {
public boolean isValidSerialization(String s) {
String[] ss = s.split(",");
int n = ss.length;
int in = 0, out = 0;
for (int i = 0; i < n; i++) {
if (!ss[i].equals("#")) out += 2;
if (i != 0) in++;
if (i != n - 1 && out <= in) return false;
}
return in == out;
}
}
C++ 代码:
class Solution {
public:
bool isValidSerialization(string s) {
vector<string> ss;
split(s, ',', ss);
int n = ss.size();
int in = 0, out = 0;
for (int i = 0; i < n; i++) {
if (ss[i] != "#") out += 2;
if (i != 0) in++;
if (i != n - 1 && out <= in) return false;
}
return in == out;
}
void split(const string &s, char delimiter, vector<string> &ss) {
stringstream ss_stream(s);
string item;
while (getline(ss_stream, item, delimiter)) {
ss.push_back(item);
}
}
};
Python 代码:
class Solution:
def isValidSerialization(self, s: str) -> bool:
ss = s.split(',')
n = len(ss)
inval, outval = 0, 0
for i in range(n):
if ss[i] != '#':
outval += 2
if i != 0:
inval += 1
if i != n - 1 and outval <= inval:
return False
return inval == outval
TypeScript 代码:
function isValidSerialization(s: string): boolean {
const ss = s.split(',');
const n = ss.length;
let inval = 0, outval = 0;
for (let i = 0; i < n; i++) {
if (ss[i] !== '#') outval += 2;
if (i !== 0) inval++;
if (i !== n - 1 && outval <= inval) return false;
}
return inval === outval;
};
-
时间复杂度: -
空间复杂度:
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier,年度会员 有效期额外增加两个月,季度会员 有效期额外增加两周,更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。
欢迎关注,明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉