神仙公司（上海）
神仙公司，终归是绕不过上海这座城市。
之所以身处上海，但迟迟不愿意写，主要原因有两个：
我所了解到的上海神仙公司，绝大多数都是外企。但如果在一篇推文中只推荐外企，往往会有"诚意不足"的嫌疑，或许是因为外企除了「学历+年限」要求以外，还会有对「外语」有所要求，面试的形式和内容，和国内互联网也有很大不同，众多因素使得外企看上去似乎离人很远。更重要的是，相比于那些常年招聘几千号人（社招）的国内互联网公司，外企 HC 相对有限。 这几年外企的"风评"不太好。大家听到的都是什么「取消居家办公，福利收紧、多轮大裁员、整个中国区的关停撤出、股价不行，高管被要求退还薪资 ...」这样的消息。嗯...消息大多都属实，但我所知道的，在这些公司的朋友，少数真的上了裁员名单，但也获得了不错的赔偿；大多数还在其职，仍然过得舒坦。
综上，对于外企部分，我们简单带过一下，它们都有「超长假期+灵活工作模式+补充商业保险+各项补贴/礼金+持股计划+松弛办公氛围+完善娱乐配套」等各项特点。
推荐：Google、Microsoft、Apple、SAP、Intel、PayPal、eBay、Airwallex、Booking、Dell ...
然后是大家更加关心的，非外企的神仙公司。
拳头游戏（有外企基因，但现在是由腾讯 100% 控股的子公司，运营管理仍由原团队全权负责）：1075，六险一金，超长假期，入职可自由选购各种外设，每年还有海外出差现场感受电竞赛事的机会，定期体检，生日福利，通讯补贴，住房补贴，员工旅游，每周团建，在招岗位 15k~45k； 唯品会：965，足额五险一金，补充医疗保险，免费班车，住房补贴，三餐免费，零食下午茶，节日福利，配套各类健身房，定期体检，员工旅游，在招岗位 25k~50k，14 薪； MOODY：1075，六险一金，季度奖金，每日零食下午茶，节日福利，生日礼金，定期体检，季度团建旅游，在招岗位 10k~25k； 鹰角网络：955，五险一金，额外补充公积金，全员覆盖商业保险，免费工作餐，零食下午茶，年度体检，父母体检报销，租房补贴，交通补贴，在招岗位 25k~50k，15 薪； 东方财富：965，足额五险一金，每日零食下午茶，节日福利，定期体检，员工旅游，在招岗位 20k~55k，13~16 薪； 叠纸游戏：早10:30晚7:30，双休，可弹性工作，五险一金，额外补充医疗保险，有餐补，每日零食下午茶，定期体检，员工旅游，节日福利，生日礼金，在招岗位 20k~40k，16 薪； 谷川联行：早8:30晚5:30，双休，五险一金，交通补贴，午餐补贴，租房补贴，通讯补贴，节日福利，定期旅游，全员每年体检，每日零食下午茶，在招岗位 10k~30k，13 薪； 网龙网络：早9:00晚6:30，双休，可弹性工作，六险一金，免费班车，工作餐补，零食下午茶，年度体检，在招岗位 30k~65k，14~16 薪；
尽力了，非外企的实在不好找呀 🤣🤣🤣
以上就是关于「上海神仙公司」，你有什么想分享的呢，欢迎评论区留言。
...
回归主题。
周末，来一道还算简单算法题。
题目描述
平台：LeetCode
题号：1252
给你一个 的矩阵，最开始的时候，每个单元格中的值都是 。
另有一个二维索引数组 indices， 指向矩阵中的某个位置，其中 和 分别表示指定的行和列（从 开始编号）。
对 所指向的每个位置，应同时执行下述增量操作：
行上的所有单元格，加 。 列上的所有单元格，加 。
给你 、 和 。请你在执行完所有 指定的增量操作后，返回矩阵中 奇数值单元格 的数目。
示例 1：
输入：m = 2, n = 3, indices = [[0,1],[1,1]]
输出：6
解释：最开始的矩阵是 [[0,0,0],[0,0,0]]。
第一次增量操作后得到 [[1,2,1],[0,1,0]]。
最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。
示例 2：
输入：m = 2, n = 2, indices = [[1,1],[0,0]]
输出：0
解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。
提示：
进阶：你可以设计一个时间复杂度为 且仅用 额外空间的算法来解决此问题吗？
基本分析
容易想到时间复杂度为 ，空间复杂度为 的做法，在此不再赘述。
对于某个位置最终累加值为奇数的充要条件为「所在行被累加次数的奇偶性」与「所在列被累加次数的奇偶性」不同。
因此我们可以统计累加次数为奇数的行数 （累加次数为偶数的行数为 ），累加次数为奇数的列数 （累加次数为偶数的列数为 ），根据乘法原理，最终答案为 。
计数模拟
由于我们只需关系某个位置的奇偶性，而不关心具体的累加值，我们可以创建两个数组 r 和 c，统计每行和每列的累加值的奇偶性。
当 为 True 含义为第 行的累加值为奇数，否则为偶数。列数组 c 的统计规则同理。
Java 代码：
class Solution {
public int oddCells(int m, int n, int[][] ins) {
boolean[] r = new boolean[m], c = new boolean[n];
int a = 0, b = 0;
for (int[] info : ins) {
a += (r[info[0]] = !r[info[0]]) ? 1 : -1;
b += (c[info[1]] = !c[info[1]]) ? 1 : -1;
}
return a * (n - b) + (m - a) * b;
}
}
C++ 代码：
class Solution {
public:
int oddCells(int m, int n, vector<vector<int>>& ins) {
vector<bool> r(m, false), c(n, false);
int a = 0, b = 0;
for (const auto& info : ins) {
a += (r[info[0]] = !r[info[0]]) ? 1 : -1;
b += (c[info[1]] = !c[info[1]]) ? 1 : -1;
}
return a * (n - b) + (m - a) * b;
}
};
Python 代码：
class Solution:
def oddCells(self, m: int, n: int, ins: List[List[int]]) -> int:
r, c = [False] * m, [False] * n
for i, j in ins:
r[i] ^= 1
c[j] ^= 1
a, b = sum(r), sum(c)
return a * (n - b) + (m - a) * b
TypeScript 代码：
function oddCells(m: number, n: number, ins: number[][]): number {
const r = new Array<boolean>(m).fill(false), c = new Array<boolean>(n).fill(false)
let a = 0, b = 0
for (const [i, j] of ins) {
a += (r[i] = !r[i]) ? 1 : -1
b += (c[j] = !c[j]) ? 1 : -1
}
return a * (n - b) + (m - a) * b
};
时间复杂度：构建计数数组的复杂度为 ，统计奇数行和奇数列复杂度为 ，其中 为数组 ins的长度，复杂度为空间复杂度：
位运算
更进一步，我们可以使用两个 long 变量 和 来分别充当行和列的计数数组，当 的第 位为 ，代表第 行累加值为奇数，当 的第 位为 ，代表第 行累加值为偶数； 的计数规则同理。而翻转二进制中的某一位可使用「异或」操作。
当处理完所有的 ins 之后，可通过「遍历 的低 位 + 遍历 的低 位」来得到行数中奇数个数 ，列数中奇数个数 ，复杂度为 ；也可以使用 bitCount 统计 long 二进制数中 的个数（本质是分治操作），复杂度为 。
Java 代码：
class Solution {
public int oddCells(int m, int n, int[][] ins) {
long c1 = 0, c2 = 0;
for (int[] info : ins) {
c1 ^= 1L << info[0];
c2 ^= 1L << info[1];
}
int a = 0, b = 0;
for (int i = 0; i < m; i++) a += ((c1 >> i) & 1);
for (int i = 0; i < n; i++) b += ((c2 >> i) & 1);
return a * (n - b) + (m - a) * b;
}
}
Java 代码：
class Solution {
public int oddCells(int m, int n, int[][] ins) {
long c1 = 0, c2 = 0;
for (int[] info : ins) {
c1 ^= 1L << info[0];
c2 ^= 1L << info[1];
}
int a = Long.bitCount(c1), b = Long.bitCount(c2);
return a * (n - b) + (m - a) * b;
}
}
C++ 代码：
class Solution {
public:
int oddCells(int m, int n, vector<vector<int>>& ins) {
long long c1 = 0, c2 = 0;
for (const auto& info : ins) {
c1 ^= 1LL << info[0];
c2 ^= 1LL << info[1];
}
int a = 0, b = 0;
for (int i = 0; i < m; i++) a += ((c1 >> i) & 1);
for (int i = 0; i < n; i++) b += ((c2 >> i) & 1);
return a * (n - b) + (m - a) * b;
}
};
Python 代码：
class Solution:
def oddCells(self, m: int, n: int, ins: List[List[int]]) -> int:
c1, c2 = 0, 0
for i, j in ins:
c1 ^= (1 << i)
c2 ^= (1 << j)
a, b = 0, 0
for i in range(m):
a += (c1 >> i) & 1
for i in range(n):
b += (c2 >> i) & 1
return a * (n - b) + (m - a) * b
TypeScript 代码：
function oddCells(m: number, n: number, ins: number[][]): number {
const c1 = [0, 0], c2 = [0, 0]
for (const [i, j] of ins) {
c1[Math.ceil(i / 32)] ^= (1 << (i % 32))
c2[Math.ceil(j / 32)] ^= (1 << (j % 32))
}
let a = 0, b = 0
for (let i = 0; i < m; i++) a += (c1[Math.ceil(i / 32)] >> (i % 32) & 1)
for (let i = 0; i < n; i++) b += (c2[Math.ceil(i / 32)] >> (i % 32) & 1)
return a * (n - b) + (m - a) * b
};
时间复杂度：处理所有的 ins复杂度为 ，其中 为数组ins的长度；使用遍历方式统计奇数行和奇数列个数复杂度为 ；使用bitCount操作统计二进制中 个数，复杂度为 ，其中 为long二进制数长度，整体复杂度为 或空间复杂度：
答疑
评论区有同学提到 bitCount 的复杂度问题，如下是 Long.bitCount 操作的源码：
public static int bitCount(long i) {
// HD, Figure 5-14
i = i - ((i >>> 1) & 0x5555555555555555L);
i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
i = i + (i >>> 8);
i = i + (i >>> 16);
i = i + (i >>> 32);
return (int)i & 0x7f;
}
这自然不是通过遍历统计位数的 做法，普遍会认为是 。
但上述操作目的是进行成组统计（分治），而能够这样写是因为默认了 long 是 长度，因此严格意义来说这段代码复杂度是 的。
作为对比，可以把 Integer.bitCount 的源码看一下：
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
统计原理如出一辙，而能够这样统计，是因为默认了 int 长度为 ，其分组统计所需要的操作次数也与二进制数的长度相关，因此复杂度为 。
将上述两个 bitCount 视为 都是不对的。
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
