宇宙厂
过去一年，宇宙厂对于「绩效激励」这一方向的调整，基本上都是按照「加大区分度」来进行。
前几年，即使是表现很差的员工，都能拿到 1~2 个月的年终奖，但从去年年底（或者说今年年初）开始，"躺平大锅饭"几乎没有了。
表现差的会直接没有奖金（甚至连续得到不好的绩效，还会有被开风险），表现好的员工，奖金则会进一步的得到提升。
这听起来十分合理，但会很大程度增加整个公司的"内卷"程度。
以往可能一个按部就班的员工，能顺利拿到及格线的绩效评分，但现在可能按部就班就会落入被淘汰的边缘。
这样的规则，会要求每个人都有额外的贡献价值，不进则退。
而在近期，宇宙厂通过全员邮件宣布：将再进一步提升激励月数的上限，并在两个月后的 2024 年全年绩效评估中启用。
同时，低于 10 股的绩效激励期权（按最新回购价一股 180.7 美元折算，约 1.3W 人民币），会直接以现金形式一次性发放，而超过 10 股的绩效激励期权，则需要按月均速归属（每月 10 股）。
结合从 24 年开始的期权加速归属规则，基本上绝大多数员工，可以在半年内拿完所有的年终奖，最长也不会超过两年。
更加详细的归属规则如下：
如果股数小于等于30股，授予日全部一次性归属; 如果股数大于30股、小于240股，授予日一次性归属30股，随后每月归属10股，直到所有绩效期权归属完（如果剩余可归属总股数不足10股，则在下个归属日一次性进行归属） 如果股数大于等于240股，按月匀速归属，2年完成归属（每月归属股数=总授予期权股数÷24，股数向下取整，余数部分在第24个月合并归属）
这两年，好像不少大厂都玩上了「内卷化」的规则，包括 JD 的，将年终奖提高到动辄 20 个月的水平，看着是给员工提高福利，但实际上是大大增加员工存活的难度。
对此，你怎么看？你见识过什么「加速内卷」的规则？欢迎评论区分享。
...
回归主线。
来一道和「字节跳动」相关的算法题。
题目描述
平台：LeetCode
题号：137
给你一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。
请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99
提示：
nums中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
哈希表
一个朴素的做法是使用「哈希表」进行计数，然后将计数为 的数字进行输出。
哈希表以「数值 : 数值出现次数」形式进行存储。
Java 代码：
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int x : nums) map.put(x, map.getOrDefault(x, 0) + 1);
for (int x : map.keySet()) {
if (map.get(x) == 1) return x;
}
return -1;
}
}
C++ 代码：
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int, int> map;
for (int x : nums) map[x]++;
for (const auto& x : map) {
if (x.second == 1) return x.first;
}
return -1;
}
};
Python 代码：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
num_map = defaultdict(int)
for x in nums:
num_map[x] += 1
for x in num_map:
if num_map[x] == 1:
return x
return -1
TypeScript 代码：
function singleNumber(nums: number[]): number {
const numMap: { [key: number]: number } = {};
for (const x of nums) numMap[x] = (numMap[x] || 0) + 1;
for (const x in numMap) {
if (numMap[parseInt(x)] === 1) return parseInt(x);
}
return -1;
};
时间复杂度： 空间复杂度：
位数统计
哈希表解法的空间复杂度是 的，而题目的【进阶】部分提到应当使用常数空间来做。
其中一个比较容易想到的做法，是利用 int 类型固定为 位。
使用一个长度为 的数组 记录下所有数值的每一位共出现了多少次 ，再对 数组的每一位进行 操作，重新拼凑出只出现一次的数值。
举个 🌰，考虑样例 [1,1,1,3]， 和 对应的二进制表示分别是 00..001 和 00..011，存入 数组后得到 [0,0,...,0,1,4]。进行 操作后得到 [0,0,...,0,1,1]，再转为十进制数字即可得「只出现一次」的答案 。
❝PS. 由于 Python 负数的位表示与正数不同，因此不能直接使用该逻辑来处理。
❞
Java 代码：
class Solution {
public int singleNumber(int[] nums) {
int[] cnt = new int[32];
for (int x : nums) {
for (int i = 0; i < 32; i++) {
if (((x >> i) & 1) == 1) cnt[i]++;
}
}
int ans = 0;
for (int i = 0; i < 32; i++) {
if ((cnt[i] % 3 & 1) == 1) ans += (1 << i);
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> cnt(32, 0);
for (int x : nums) {
for (int i = 0; i < 32; i++) {
if ((x >> i) & 1) cnt[i]++;
}
}
int ans = 0;
for (int i = 0; i < 32; i++) {
if (cnt[i] % 3 & 1) ans |= (1 << i);
}
return ans;
}
};
TypeScript 代码：
function singleNumber(nums: number[]): number {
let cnt = new Array(32).fill(0);
for (const x of nums) {
for (let i = 0; i < 32; i++) {
if ((x >> i) & 1) cnt[i]++;
}
}
let ans = 0;
for (let i = 0; i < 32; i++) {
if ((cnt[i] % 3 & 1) === 1) ans |= (1 << i);
}
return ans;
};
时间复杂度： 空间复杂度：
DFA
如果我们考虑「除了某个元素只出现一次以外，其余每个元素均出现两次」的情况，那么可以使用「异或」运算。
利用相同数异或为 0 的性质，可以帮助我们很好实现状态切换：
本题是考虑「除了某个元素只出现一次以外，其余每个元素均出现三次」的情况，那么对应了「出现 0 次」、「出现 1 次」和「出现 2 次」三种状态，意味着至少需要两位进行记录，且状态转换关系为：
那么如何将上述 DFA 用表达式表示出来呢？有以下几种方法：
用「真值表」写出「逻辑函数表达式」可参考 [wenku.baidu.com/view/e9460ad96729647d27284b73f242336c1eb930f0.html]，化简过程可以参考 [卡诺图化简法：baike.baidu.com/item/%E5%8D%A1%E8%AF%BA%E5%9B%BE%E5%8C%96%E7%AE%80%E6%B3%95] 。
把结论记住（这是一道经典的 DFA 入门题）。
硬做，位运算也就那几种，不会「数字电路」也记不住「结论」，砸时间看着真值表不断调逻辑也是可以写出来的。
Java 代码：
class Solution {
public int singleNumber(int[] nums) {
int one = 0, two = 0;
for(int x : nums){
one = one ^ x & ~two;
two = two ^ x & ~one;
}
return one;
}
}
C++ 代码：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one = 0, two = 0;
for (int x : nums) {
one = one ^ x & ~two;
two = two ^ x & ~one;
}
return one;
}
};
Python 代码：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
one = two = 0
for x in nums:
one = one ^ x & ~two
two = two ^ x & ~one
return one
TypeScript 代码：
function singleNumber(nums: number[]): number {
let one = 0, two = 0;
for (const x of nums) {
one = one ^ x & ~two;
two = two ^ x & ~one;
}
return one;
};
时间复杂度： 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
