比亚迪
今天,一篇名为《比亚迪真的越来越让人失望了》的帖子出现在了学生根据地。
![alt](https://img-blog.csdnimg.cn/img_convert/2662cd39c2b7b2ac8d6d286b084fe7cb.png)
帖子中写道:比亚迪正在搞竞争文化,末位淘汰,领导们还一副"不缺人"的口吻,应届生刚进去可能觉得还行,但长期来说,离职率很高,搞活动发的也都是钥匙扣等小礼品,直言其没有大公司的文化和底蕴。
比亚迪这种高压竞争文化,其实就像互联网行业的"狼性精神",但少了点"肉"。
待遇不提升,福利不跟上,这种模式短期内或许能激发潜能,但长期看,基本留不住人。
这几年很多快速发展的公司,都有类似的问题。
业务起飞了,一下子来钱快了,但企业文化、利益分配和管理底蕴,根本跟不上。
问这些创始人的发展路线和管理方式,答案都是清一色的"学华为"。
其中时间线最近,业务又和比亚迪相仿的,是同为造车新势力的理想汽车。
今年年初,考验各个大厂的年终奖实力的时候,理想汽车以「普遍 5 个月,不少人甚至拿到 8 个月」的年终奖方案,冲上热搜。
理想汽车的 CEO 甚至在微博回应此事:
![alt](https://img-blog.csdnimg.cn/img_convert/b457a844a4bb87b2fcf366caf5cc5b14.png)
当时看「不能只学华为的流程,而不学华为的利益分配」这一句话,还真是有模有样。
但谁又能逃过"回旋镖",尤其是身在白热化淘汰赛中的新能源车企。
于是,这家高调宣布学华为利益分配的公司,在三个月后迎来了大面积裁员,整体裁员比例达到 18%。
不过理想汽车这种做法总归是比「只跟和华为学狼性,钱却不多掏一分」的公司,是要更高一个层次。
但作为打工人,梦中情司只有「敢于将利润往下分配」的能力是不够的,更重要的还看中「核心业务的盈利能力」,否则就是跟了个"二愣子"企业家,上半年领奖,下半年失业。
...
回归主题。
简简单单算法题。
题目描述
平台:LeetCode
题号:1178
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏,请你来猜猜看吧。
字谜的迷面 puzzle
按字符串形式给出,如果一个单词 word
符合下面两个条件,那么它就可以算作谜底:
-
单词 word
中包含谜面puzzle
的第一个字母。 -
单词 word
中的每一个字母都可以在谜面puzzle
中找到。
例如,如果字谜的谜面是 "abcdefg"
,那么可以作为谜底的单词有 "faced"
, "cabbage"
, 和 "baggage"
;而 "beefed"
(不含字母 "a"
)以及 "based"
(其中的 "s"
没有出现在谜面中)都不能作为谜底。
返回一个答案数组 answer
,数组中的每个元素 answer[i]
是在给出的单词列表 words
中可以作为字谜迷面 puzzles[i]
所对应的谜底的单词数目。
示例:
输入:
words = ["aaaa","asas","able","ability","actt","actor","access"],
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
输出:[1,1,3,2,4,0]
解释:
1 个单词可以作为 "aboveyz" 的谜底 : "aaaa"
1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"
没有单词可以作为 "gaswxyz" 的谜底,因为列表中的单词都不含字母 'g'。
提示:
-
words[i][j]
,puzzles[i][j]
都是小写英文字母 -
每个 puzzles[i]
所包含的字符都不重复
朴素位运算 (TLE)
根据「谜底」和「谜面」的对应条件:
-
单词 word
中包含谜面puzzle
的第一个字母。 -
单词 word
中的每一个字母都可以在谜面puzzle
中找到
puzzle
本身长度只有 7 位,而且不重复;我们可以发现对应条件与 word
的重复字母无关。
因此我们可以使用「二进制」数来表示每一个 word
和 puzzle
:
一个长度为 26 的二进制数来表示(直接使用长度为 32 的 int 即可,使用低 26 位),假如有 str = "abz"
则对应了 100...011
(共 26 位,从右往左是 a - z)。
至此我们可以已经可以得出一个朴素解法的思路了:
-
预处理除所有的 word
对应的二进制数字。计算量为 ,数量级为1e6
-
对每个 puzzle
进行条件判定(每一个puzzle
都需要遍历所有的word
进行检查)。计算量为 ,数量级为1e9
计算机单秒的计算量为 1e7
左右(OJ 测评器通常在 1e6
~1e7
之间),哪怕忽略常数后,我们的总运算也超过了上限,铁定超时。
代码:
class Solution {
public List<Integer> findNumOfValidWords(String[] ws, String[] ps) {
// 预处理出所有的 word 所对应的二进制数值
List<Integer> list = new ArrayList<>();
for (String w : ws) list.add(getBin(w));
// 判定每个 puzzles 有多少个谜底
List<Integer> ans = new ArrayList<>();
for (String p : ps) ans.add(getCnt(list, p));
return ans;
}
// 判定某个 puzzles 有多少个谜底
int getCnt(List<Integer> ws, String str) {
int ans = 0;
// 获取当前 puzzles 对应的二进制数字
int t = getBin(str);
// 当前 puzzles 的首个字符在二进制数值中的位置
int first = str.charAt(0) - 'a';
for (int w : ws) {
// check 条件一:单词 word 中包含谜面 puzzle 的第一个字母
if ((w >> first & 1) == 0) continue;
// check 条件二:单词 word 中的每一个字母都可以在谜面 puzzle 中找到
if ((w & t) == w) ans++;
}
return ans;
}
// 将 str 所包含的字母用二进制标识
// 如果 str = abz 则对应的二进制为 100...011 (共 26 位,从右往左是 a - z)
int getBin(String str) {
int t = 0;
char[] cs = str.toCharArray();
for (char c : cs) {
// 每一位字符所对应二进制数字中哪一位
int u = c - 'a';
// 如果当前位置为 0,代表还没记录过,则进行记录 (不重复记录)
if ((t >> u & 1) == 0) t += 1 << u;
}
return t;
}
}
-
时间复杂度: -
空间复杂度:每个 word
对应了一个 int,每个puzzle
对应了一个答案。复杂度为
哈希表 & 位运算
因此我们需要优化上述步骤 1 或者步骤 2 。显然超时的主要原因是步骤 2 计算量太多了。
一个很显眼的突破口是利用 puzzles[i].length == 7
,同时判定条件 1 对 puzzle
的首字母进行了限定。
「对于一个确定的 puzzle
而言,我们要找它有多少个「谜底」。可以通过枚举它所有可能的「谜底」,再去 words
里面找每一个「谜底」出现了多少次。」
「结合题意的话,就是固定住 puzzle
的首位,去枚举其余后面的 6 位的所有的可能性(每一位都有保留和不保留两种选择),即枚举子集的过程。」
你可能还是无法理解,其实就是一个通过 puzzle
反推 word
的过程:
举个🌰吧,假如我们有 puzzle
是 gabc
(假定现在的 puzzle
长度只有 4) ,那么可能的 word
有哪些?
-
首先要满足条件一,也就是 word
必然包含首字母g
; -
然后是条件二, word
中的每一位都在puzzle
出现过,因此可能的word
包括g
、ga
、gb
、gc
、gab
、gac
、gbc
、gabc
。
使用 1 和 0 代表 puzzle
每一位选择与否的话,其实就是对应了 1000、1100、1010、1001、1110、1101、1011、1111。
搞明白了这个过程之后,我们需要对 words
进行词频统计,我们可以使用「哈希表」记录相同含义的 word
出现了多少次(相同含义的意思是包含字母类型一样的 word
,因为答案和 word
的重复字符无关)
这样做的复杂度/计算量是多少呢?
-
统计所有 word
的词频。计算量为 ,数量级为1e6
-
对应每个 puzzle
而言,由于其长度确定为 7,因此所有枚举所有可能「谜底」的数量不为 个,可以看做是 的,检查每个可能的「谜底」在words
出现次数是通过哈希表,也是近似 的。因此在确定一个puzzle
的答案时,与words
的长度无关。计算量为 ,数量级为1e4
计算机单秒的计算量为 1e7
左右(OJ 测评器通常在 1e6
~1e7
之间),因此可以过。
代码:
class Solution {
public List<Integer> findNumOfValidWords(String[] ws, String[] ps) {
// 转用 「哈希表」来统计出所有的 word 所对应的二进制数值
Map<Integer, Integer> map = new HashMap<>();
for (String w : ws) {
int t = getBin(w);
map.put(t, map.getOrDefault(t, 0) + 1);
}
// 判定每个 puzzle 有多少个谜底
List<Integer> ans = new ArrayList<>();
for (String p : ps) ans.add(getCnt(map, p));
return ans;
}
int getCnt(Map<Integer, Integer> map, String str) {
int ans = 0;
int m = str.length();
char[] cs = str.toCharArray();
// 当前 puzzle 的首个字符在二进制数值中的位置
int first = cs[0] - 'a';
// 枚举「保留首个字母」的所有子集
// 即我们需要先固定 puzzle 的首位字母,然后枚举剩余的 6 位是否保留
// 由于是二进制,每一位共有 0 和 1 两种选择,因此共有 2^6 种可能性,也就是 2^6 = 1 << (7 - 1) = 64 种
// i 代表了所有「保留首个字母」的子集的「后六位」的二进制表示
for (int i = 0; i < (1 << (m - 1)); i++) {
// u 代表了当前可能的谜底。先将首字母提取出来
int u = 1 << first;
// 枚举「首个字母」之后的每一位
for (int j = 1; j < m; j++) {
// 如果当前位为 1,代表该位置要保留,将该位置的字母追加到谜底 u 中
if (((i >> (j - 1)) & 1) != 0) u += 1 << (cs[j] - 'a');
}
// 查询这样的字符是否出现在 `words` 中,出现了多少次
if (map.containsKey(u)) ans += map.get(u);
}
return ans;
}
// 将 str 所包含的字母用二进制标识
// 如果 str = abz 则对应的二进制为 100...011 (共 26 位,从右往左是 a - z)
int getBin(String str) {
int t = 0;
char[] cs = str.toCharArray();
for (char c : cs) {
// 每一位字符所对应二进制数字中哪一位
int u = c - 'a';
// 如果当前位置为 0,代表还没记录过,则进行记录 (不重复记录)
if ((t >> u & 1) == 0) t += 1 << u;
}
return t;
}
}
-
时间复杂度: -
空间复杂度: word
和puzzle
分别具有最大长度和固定长度,使用空间主要取决于量数组的长度。复杂度为
位运算说明
a >> b & 1
代表检查 a
的第 b
位是否为 1,有两种可能性 0 或者 1
a += 1 << b
代表将 a
的第 b
位设置为 1 (当第 b
位为 0 的时候适用)
如不想写对第 b
位为 0
的前置判断,a += 1 << b
也可以改成 a |= 1 << b
点评
这道题解发到 LeetCode 之后,很多同学反映还是看不懂,还是不理解。
于是我重新的思考了这道题的每一个环节。
这道题之所是 Hard,是因为考察的都是违反人性"直觉"的东西:
-
状态压缩:对一个单词出现过哪些字母,不能采用我们直观中的 map/set 进行记录,而要利用一个长度为 26 的二进制数来记录,对于某个字母需要计算在二进制数中的哪一位,如果出现过用 1 表示,没出现过用 0 表示 -
正难则反:不能从 words
数组出发,去检查有哪些word
符合要求;而要反过来从puzzle
出发,去枚举当前puzzle
所有合法的word
,再去确定这些合法的word
在真实的words
数组中出现了多少次
大家要尽量去理解这种思路的合理性,当这种思路也形成意识的时候,这种题也就不难了。
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier,年度会员 有效期额外增加两个月,季度会员 有效期额外增加两周,更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。
欢迎关注,明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉