可怜百度人
可怜的百度股民
注意，这里说的是持有百度股票的股民，不是百度，百度没啥好可怜的。
前天（3月25日）中午，财联社爆料百度和 Apple 达成合作，百度将为苹果今年发布的 iPhone16、Mac 系统和 iOS18 提供 AI 功能。
这对百度来说属于利好，于是盘中一度高涨 6.5% 个点。
但可惜，虽然百度在 H 股上市，但本质还是中国公司，只要是中国公司，就逃脱不了「出利好 = 高开低走」的宿命。
于是当天百度的股价走势是这样的：
前一天收盘价 98.2，开盘 99.2，消息出来后，最高 104.9（涨幅约 6.5%），然后开始冲高回落，最终收盘 100.7（涨幅 2.55%）。
收盘价低于当日成交均价 101.1，这意味着那些因为利好消息冲进去的股民，当日收盘大概率是浮亏的。
PS. 记住这个当日成交均价，待会要考。
后续结果你猜怎么着？
昨天一位接近苹果的知情人士跳出来，否认了苹果已和百度达成 AI 合作的消息。
前面说的「出利好 = 高开低走」只是中国公司的传统艺能之一，另外一个传统艺能是「出利空 = 集体抢跑 = 低开低走」，于是今天的百度走势是：
午盘价为 99.3，盘中最低去到了 98.3，比消息出来前的午盘价还要低。
你可能会说，现在的 99.3 和消息当天开盘价的 99.2 看起来差的不多嘛，没消息股价也会波动的呀。
是的，但是股民的成本价可不是 99.2，大概率是要比前面说的日成交均价 101.1 要高，因为拉升是发生在午盘，消息当天交易量异动那段时间，均价其实接近 102。
即使我们用 101.1 去算，那么这批股民也 3 天亏了 2 个点。
我本身没有过任何交易百度股票以及相关衍生物的经历，我也几乎不抓这种热点投机。
但平心而论，你能说这批股民错信小作文吃亏，是单纯活该吗？
不太能，小道消息的投机是有反水风险，但每次都明牌的高开低走，简直就离谱。
尤其是百度在出利好小作文的前段时间，已经跌了一段时间了：
因此不存在内幕消息抢跑，爆料小作文后趁机出货的情况，所以当天的高开低走完全就是市场惯性。
这是市场投资者普遍没有耐心，只想镰刀相见，把投资玩成零和游戏的表现。
不难评，但不适合评。
如果这次你在百度小作文这里交了学费，以后不要交；如果这次没有交学费，看着这推文，以后要学会忍手。
...
回归主线。
继续来一道和「百度」社招相关算法原题。
题目描述
平台：LeetCode
题号：934
给你一个大小为 n x n 的二元矩阵 g，其中 1 表示陆地，0 表示水域。
岛是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连，g 中恰好存在两座岛。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成一座岛。
返回必须翻转的 0 的最小数目。
示例 1：
输入：g = [[0,1],[1,0]]
输出：1
示例 2：
输入：g = [[0,1,0],[0,0,0],[0,0,1]]
输出：2
示例 3：
输入：g = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1
提示：
- n=g.length=g[i].lengthn = g.length = g[i].lengthn=g.length=g[i].length
- 2<=n<=1002 <= n <= 1002<=n<=100
g[i][j]为0或1g中恰有两个岛
并查集 + 双向 BFS
使用「并查集」将两个岛标记出来，然后将两个岛的点分别入队，再运用「双向 BFS」来找最短通路。
对于所有满足 g[i][j]=1g[i][j] = 1g[i][j]=1 的节点与其四联通的方向，值同为 111 的节点进行并查集连通性维护。
随后建立两个队列 d1 和 d2 分别存储两个岛的节点（以二元组 (x,y)(x, y)(x,y) 的方式出入队），并使用两个哈希表 m1 和 m2 来记录从两岛屿出发到达该节点所消耗的步数（以节点的一维编号为 key，以消耗步数为 value）。
最后是使用「双向 BFS」来求解使两岛屿联通的最小通路：每次从队列中较少的进行拓展，只有尚未被处理过的节点（没有被当前哈希表所记录）才进行入队并更新消耗步数，当拓展节点在另外一个队列对应的哈希表表中出现过，说明找到了最短通路。
Java 代码：
class Solution {
static int N = 10010;
static int[] p = new int[N];
static int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int n;
int getIdx(int x, int y) {
return x * n + y;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void union(int x, int y) {
p[find(x)] = p[find(y)];
}
public int shortestBridge(int[][] g) {
n = g.length;
for (int i = 0; i <= n * n; i++) p[i] = i;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 0) continue;
for (int[] di : dirs) {
int x = i + di[0], y = j + di[1];
if (x < 0 || x >= n || y < 0 || y >= n) continue;
if (g[x][y] == 0) continue;
union(getIdx(i, j), getIdx(x, y));
}
}
}
int a = -1, b = -1;
Deque<int[]> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
Map<Integer, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == 0) continue;
int idx = getIdx(i, j), root = find(idx);
if (a == -1) a = root;
else if (a != root && b == -1) b = root;
if (root == a) {
d1.addLast(new int[]{i, j});
m1.put(idx, 0);
} else if (root == b) {
d2.addLast(new int[]{i, j});
m2.put(idx, 0);
}
}
}
while (!d1.isEmpty() && !d2.isEmpty()) {
int t = -1;
if (d1.size() < d2.size()) t = update(d1, m1, m2);
else t = update(d2, m2, m1);
if (t != -1) return t - 1;
}
return -1; // never
}
int update(Deque<int[]> d, Map<Integer, Integer> m1, Map<Integer, Integer> m2) {
int sz = d.size();
while (sz-- > 0) {
int[] info = d.pollFirst();
int x = info[0], y = info[1], idx = getIdx(x, y), step = m1.get(idx);
for (int[] di : dirs) {
int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny);
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (m1.containsKey(nidx)) continue;
if (m2.containsKey(nidx)) return step + 1 + m2.get(nidx);
d.addLast(new int[]{nx, ny});
m1.put(nidx, step + 1);
}
}
return -1;
}
}
Python 代码：
import queue
class Solution:
def shortestBridge(self, g: List[List[int]]) -> int:
def getIdx(x, y):
return x * n + y
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(x, y):
p[find(x)] = p[find(y)]
def update(d, cur, other):
sz = d.qsize()
while sz != 0:
x, y = d.get()
idx, step = getIdx(x, y), cur.get(getIdx(x, y))
for di in dirs:
nx, ny = x + di[0], y + di[1]
nidx = getIdx(nx, ny)
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if nidx in cur:
continue
if nidx in other:
return step + 1 + other.get(nidx)
d.put([nx, ny])
cur[nidx] = step + 1
sz -= 1
return -1
n = len(g)
p = [i for i in range(n * n + 10)]
dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for i in range(n):
for j in range(n):
if g[i][j] == 0:
continue
for di in dirs:
x, y = i + di[0], j + di[1]
if x < 0 or x >= n or y < 0 or y >= n:
continue
if g[x][y] == 0:
continue
union(getIdx(i, j), getIdx(x, y))
a, b = -1, -1
d1, d2 = queue.Queue(), queue.Queue()
m1, m2 = {}, {}
for i in range(n):
for j in range(n):
if g[i][j] == 0:
continue
idx, root = getIdx(i, j), find(getIdx(i, j))
if a == -1:
a = root
elif a != root and b == -1:
b = root
if a == root:
d1.put([i, j])
m1[idx] = 0
elif b == root:
d2.put([i, j])
m2[idx] = 0
while not d1.empty() and not d2.empty():
t = -1
if d1.qsize() < d2.qsize():
t = update(d1, m1, m2)
else:
t = update(d2, m2, m1)
if t != -1:
return t - 1
return -1
TypeScript 代码：
let n: number
const p = new Array<number>(10010).fill(0)
const dirs = [[0,1],[0,-1],[1,0],[-1,0]]
function shortestBridge(g: number[][]): number {
function getIdx(x: number, y: number): number {
return x * n + y
}
function find(x: number): number {
if (p[x] != x) p[x] = find(p[x])
return p[x]
}
function union(x: number, y: number): void {
p[find(x)] = p[find(y)]
}
function update(d: Array<Array<number>>, m1: Map<number, number>, m2: Map<number, number>): number {
let sz = d.length
while (sz-- > 0) {
const info = d.shift()
const x = info[0], y = info[1], idx = getIdx(x, y), step = m1.get(idx)
for (const di of dirs) {
const nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny)
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
if (m1.has(nidx)) continue
if (m2.has(nidx)) return step + 1 + m2.get(nidx)
d.push([nx, ny])
m1.set(nidx, step + 1)
}
}
return -1
}
n = g.length
for (let i = 0; i < n * n; i++) p[i] = i
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (g[i][j] == 0) continue
for (const di of dirs) {
const x = i + di[0], y = j + di[1]
if (x < 0 || x >= n || y < 0 || y >= n) continue
if (g[x][y] == 0) continue
union(getIdx(i, j), getIdx(x, y))
}
}
}
let a = -1, b = -1
const d1 = new Array<number[]>(), d2 = new Array<number[]>()
const m1 = new Map<number, number>(), m2 = new Map<number, number>()
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (g[i][j] == 0) continue
const idx = getIdx(i, j), root = find(idx)
if (a == -1) a = root
else if (a != root && b == -1) b = root
if (a == root) {
d1.push([i, j])
m1.set(idx, 0)
} else if (b == root) {
d2.push([i, j])
m2.set(idx, 0)
}
}
}
while (d1.length != 0 && d2.length != 0) {
let t = -1
if (d1.length < d2.length) t = update(d1, m1, m2)
else t = update(d2, m2, m1)
if (t != -1) return t - 1
}
return -1
}
- 时间复杂度：O(n2)O(n^2)O(n2)
- 空间复杂度：O(n2)O(n^2)O(n2)
最后
给大伙通知一下 📢 ：
全网最低价 LeetCode 会员目前仍可用，快来薅羊毛！！！
📅 年度会员：有效期加赠两个月！！; 季度会员：有效期加赠两周！！
🧧 年度会员：获 66.66 现金红包！！; 季度会员：获 22.22 现金红包！！
🎁 年度会员：参与当月丰厚专属实物抽奖（中奖率 > 30%)！！
更多详情请戳 这里 。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉