快手
前几天，我们说了 鹅厂「赠送假期 + 改调休假」，实现连放 10 天 的事儿，当时觉得这安排属实优秀，要比隔壁网易的所谓的"全员 12 天假"，实际是"强制性买二送一"（强制规定使用 2 天年假，换取 1 天赠假）要良心得多。
最近，另外一家大厂「快手」也公布春节放假安排。
虽然也是只有一天赠假，但同样体现出有对"员工放假便利性"充分考虑。
具体的，在法定的 1-28 ~ 2-4（共八天）的基础上增加一天赠假，至于赠送的那一天，员工可以灵活选择是在 1-27 还是在 2-5 使用。
这样的安排，至少可以看得出快手是真心为了员工放假便利性而考虑的。
不像某位读者给我爆料的奇葩公司，是有一天赠假没错，但赠在了 1-26 的调休日里 🤣🤣🤣
法定是从 1-28 开始放假，赠假却赠在了 1-26，这不是引导大家用年假来放 1-27 吗？这种"强引导性的买一送一"比网易的"强制性买二送一"还要心机。
对此，你怎么看？你司的放假安排方案发了吗？是几号到几号呀？欢迎评论区交流。
...
回归主题。
来一道和「快手（校招）」相关的算法题。
题目描述
平台：LeetCode
题号：749
病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。
假设世界由 的二维矩阵 isInfected 组成，isInfected[i][j] == 0 表示该区域未感染病毒，而 isInfected[i][j] == 1 表示该区域已感染病毒。可以在任意 个相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。
每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且 保证唯一 。
你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。
示例 1：
输入: isInfected = [[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]
输出: 10
解释:一共有两块被病毒感染的区域。
在第一天，添加 5 墙隔离病毒区域的左侧。病毒传播后的状态是:
第二天，在右侧添加 5 个墙来隔离病毒区域。此时病毒已经被完全控制住了。
示例 2：
输入: isInfected = [[1,1,1],[1,0,1],[1,1,1]]
输出: 4
解释: 虽然只保存了一个小区域，但却有四面墙。
注意，防火墙只建立在两个不同区域的共享边界上。
示例 3:
输入: isInfected = [[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]
输出: 13
解释: 在隔离右边感染区域后，隔离左边病毒区域只需要 2 个防火墙。
提示:
isInfected[i][j]is either0or1在整个描述的过程中，总有一个相邻的病毒区域，它将在下一轮严格地感染更多未受污染的方块
搜索模拟
根据题意，我们可以按天进行模拟，设计函数 getCnt 用于返回当天会被安装的防火墙数量，在 getCnt 内部我们会进行如下操作：
找出当天「对未感染区域的威胁最大」的区域，并将该区域进行隔离（将 设置为 ）； 对其他区域，进行步长为 的感染操作。
考虑如何实现 getCnt：我们需要以「连通块」为单位进行处理，因此每次的 getCnt 操作，我们先重建一个与矩阵等大的判重数组 vis，对于每个 且未被 标记为 True 的位置进行搜索，搜索过程使用 BFS 实现。
在 BFS 过程中，我们除了统计该连通块所需要的防火墙数量 以外，还需要额外记录当前连通块中 的点集 s1（简称为原集，含义为连通块的格子集合），以及当前连通块相邻的 的点集 s2（简称为扩充集，含义为将要被感染的格子集合）。
根据题意，在单次的 getCnt 中，我们需要在所有连通块中取出其 s2 大小最大（对未感染区域的威胁最大）的连通块进行隔离操作，而其余连通块则进行扩充操作。
因此我们可以使用两个变量 max 和 ans 分别记录所有 s2 中的最大值，以及取得最大 s2 所对应连通块所需要的防火墙数量，同时需要使用两个数组 l1 和 l2 分别记录每个连通块对应的「原集」和「扩充集」，方便我们后续进行「隔离」和「感染」。
Java 代码：
class Solution {
int[][] g;
int n, m, ans;
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
boolean[][] vis;
int search(int _x, int _y, Set<Integer> s1, Set<Integer> s2) {
int ans = 0;
Deque<int[]> d = new ArrayDeque<>();
vis[_x][_y] = true;
d.addLast(new int[]{_x, _y});
s1.add(_x * m + _y);
while (!d.isEmpty()) {
int[] info = d.pollFirst();
int x = info[0], y = info[1];
for (int[] di : dirs) {
int nx = x + di[0], ny = y + di[1], loc = nx * m + ny;
if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) continue;
if (g[nx][ny] == 1) {
s1.add(loc);
vis[nx][ny] = true;
d.addLast(new int[]{nx, ny});
} else if (g[nx][ny] == 0) {
s2.add(loc);
ans++;
}
}
}
return ans;
}
int getCnt() {
vis = new boolean[n][m];
int max = 0, ans = 0;
// l1: 每个连通块的点集 s2: 每个连通块的候选感染点集
List<Set<Integer>> l1 = new ArrayList<>(), l2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 1 && !vis[i][j]) {
// s1: 当前连通块的点集 s2: 当前连通块的候选感染点集
Set<Integer> s1 = new HashSet<>(), s2 = new HashSet<>();
int b = search(i, j, s1, s2), a = s2.size();
if (a > max) {
max = a; ans = b;
}
l1.add(s1); l2.add(s2);
}
}
}
for (int i = 0; i < l2.size(); i++) {
for (int loc : l2.get(i).size() == max ? l1.get(i) : l2.get(i)) {
int x = loc / m, y = loc % m;
g[x][y] = l2.get(i).size() == max ? -1 : 1;
}
}
return ans;
}
public int containVirus(int[][] _g) {
g = _g;
n = g.length; m = g[0].length;
while (true) {
int cnt = getCnt();
if (cnt == 0) break;
ans += cnt;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
vector<vector<int>> g;
int n, m, ans;
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<bool>> vis;
int search(int _x, int _y, unordered_set<int>& s1, unordered_set<int>& s2) {
int ans = 0;
deque<pair<int, int>> d;
vis[_x][_y] = true;
d.push_back({_x, _y});
s1.insert(_x * m + _y);
while (!d.empty()) {
auto [x, y] = d.front(); d.pop_front();
for (auto& di : dirs) {
int nx = x + di[0], ny = y + di[1], loc = nx * m + ny;
if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) continue;
if (g[nx][ny] == 1) {
s1.insert(loc);
vis[nx][ny] = true;
d.push_back({nx, ny});
} else if (g[nx][ny] == 0) {
s2.insert(loc);
ans++;
}
}
}
return ans;
}
int getCnt() {
vis = vector<vector<bool>>(n, vector<bool>(m, false));
int maxv = 0, ans = 0;
vector<unordered_set<int>> l1, l2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 1 && !vis[i][j]) {
unordered_set<int> s1, s2;
int b = search(i, j, s1, s2), a = s2.size();
if (a > maxv) {
maxv = a; ans = b;
}
l1.push_back(s1); l2.push_back(s2);
}
}
}
for (int i = 0; i < l2.size(); i++) {
for (int loc : (l2[i].size() == maxv ? l1[i] : l2[i])) {
int x = loc / m, y = loc % m;
g[x][y] = l2[i].size() == maxv ? -1 : 1;
}
}
return ans;
}
int containVirus(vector<vector<int>>& _g) {
g = _g;
n = g.size(); m = g[0].size();
ans = 0;
while (true) {
int cnt = getCnt();
if (cnt == 0) break;
ans += cnt;
}
return ans;
}
};
Python 代码：
class Solution:
def search(self, x, y, s1, s2):
ans = 0
d = deque()
self.vis[x][y] = True
d.append((x, y))
s1.add(x * self.m + y)
while d:
nx, ny = d.popleft()
for dx, dy in self.dirs:
nx_, ny_ = nx + dx, ny + dy
loc = nx_ * self.m + ny_
if nx_ < 0 or nx_ >= self.n or ny_ < 0 or ny_ >= self.m or self.vis[nx_][ny_]:
continue
if self.g[nx_][ny_] == 1:
s1.add(loc)
self.vis[nx_][ny_] = True
d.append((nx_, ny_))
elif self.g[nx_][ny_] == 0:
s2.add(loc)
ans += 1
return ans
def getCnt(self):
self.vis = [[False] * self.m for _ in range(self.n)]
max_area = 0
ans = 0
l1, l2 = [], []
for i in range(self.n):
for j in range(self.m):
if self.g[i][j] == 1 and not self.vis[i][j]:
s1, s2 = set(), set()
b = self.search(i, j, s1, s2), len(s2)
if b[1] > max_area:
max_area = b[1]
ans = b[0]
l1.append(s1)
l2.append(s2)
for i in range(len(l2)):
for loc in (l1[i] if len(l2[i]) == max_area else l2[i]):
x, y = divmod(loc, self.m)
self.g[x][y] = -1 if len(l2[i]) == max_area else 1
return ans
def containVirus(self, g: List[List[int]]) -> int:
self.g = g
self.n = len(g)
self.m = len(g[0])
self.ans = 0
self.dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
while True:
cnt = self.getCnt()
if cnt == 0: break
self.ans += cnt
return self.ans
TypeScript 代码：
let g: number[][] = null
let n: number = 0, m: number = 0
let vis: boolean[][] = null
const dirs: number[][] = [[1,0],[-1,0],[0,1],[0,-1]]
function search(_x: number, _y: number, s1: Set<number>, s2: Set<number>): number {
let he = 0, ta = 0, ans = 0
let d: Array<number> = new Array<number>()
s1.add(_x * m + _y)
vis[_x][_y] = true
d[ta++] = _x * m + _y
while (he < ta) {
const poll = d[he++]
const x = Math.floor(poll / m), y = poll % m
for (const di of dirs) {
const nx = x + di[0], ny = y + di[1], loc = nx * m + ny
if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) continue
if (g[nx][ny] == 1) {
s1.add(loc)
vis[nx][ny] = true
d[ta++] = loc
} else if (g[nx][ny] == 0) {
s2.add(loc)
ans++
}
}
}
return ans
}
function getCnt(): number {
vis = new Array<Array<boolean>>(n)
for (let i = 0; i < n; i++) vis[i] = new Array<boolean>(m).fill(false)
let max = 0, ans = 0
let l1: Array<Set<number>> = new Array<Set<number>>(), l2: Array<Set<number>> = new Array<Set<number>>()
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (g[i][j] == 1 && !vis[i][j]) {
let s1 = new Set<number>(), s2 = new Set<number>()
const b = search(i, j, s1, s2), a = s2.size
if (a > max) {
max = a; ans = b
}
l1.push(s1); l2.push(s2)
}
}
}
for (let i = 0; i < l2.length; i++) {
for (let loc of l2[i].size == max ? l1[i] : l2[i]) {
const x = Math.floor(loc / m), y = loc % m
g[x][y] = l2[i].size == max ? -1 : 1
}
}
return ans
}
function containVirus(_g: number[][]): number {
g = _g
n = g.length; m = g[0].length
let ans: number = 0
while (true) {
const cnt = getCnt()
if (cnt == 0) break
ans += cnt
}
return ans
};
时间复杂度：最多有 天需要模拟，每天模拟复杂度 ，整体复杂度为 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
