You are given a 2D vector bookshelf, where each element represents a book type numbered from 1 to k. The task is to empty the bookshelf by selecting a book and removing all books of the same type that lie in the same row or column as the selected book. The goal is to determine the minimum number of turns needed to completely clear the bookshelf.
For instance, if you select a book of type 2 located at row 0 and column 3, you would remove all books of type 2 present in row 0 and column 3, including the selected book.
Constraints
1 ≤ bookshelf.size() ≤ 1001 ≤ bookshelf[0].size() ≤ 1001 ≤ k ≤ 100
Example 1
Input:
bookshelf = [[1, 1, 1], [1, 2, 2], [1, 2, 1]]
k = 2Output:
3Explanation:
Example 2
Input:
bookshelf = [[1, 2, 2], [1, 2, 2], [2, 1, 2]]
k = 2Output:
4Explanation: For each turn, you select a book and remove all books of the same type either in the same row or column. The objective is to minimize the number of turns it takes to completely empty the bookshelf.
解法
这是一个二分图最小顶点覆盖(König)的变形。对每个 type t：行集 R_t × 列集 C_t 构成一组要清除的"格子"。每次操作选 (r, c, t) 删除该行该列上所有 t — 等价于选行/列覆盖该 type 的全部出现位置。对每个 type 单独跑 König：建二分图 (rows, cols)，每个 (r, c, t) 出现位置连边，最小顶点覆盖 = 最大匹配(匈牙利算法)。各 type 答案之和即总操作数。时间 O(K·R·C·sqrt(V)) 量级，小规模 OA 朴素增广即可。
from collections import defaultdict
from typing import List
def empty_shelf(bookshelf: List[List[int]], k: int) -> int:
by_type = defaultdict(list)
for i, row in enumerate(bookshelf):
for j, t in enumerate(row):
if t != 0:
by_type[t].append((i, j))
total = 0
for t, cells in by_type.items():
rows = sorted({r for r, _ in cells})
cols = sorted({c for _, c in cells})
ri = {r: i for i, r in enumerate(rows)}
ci = {c: i for i, c in enumerate(cols)}
adj = [[] for _ in rows]
for r, c in cells:
adj[ri[r]].append(ci[c])
match_col = [-1] * len(cols)
def try_kuhn(u, visited):
for v in adj[u]:
if visited[v]:
continue
visited[v] = True
if match_col[v] == -1 or try_kuhn(match_col[v], visited):
match_col[v] = u
return True
return False
m = 0
for u in range(len(rows)):
visited = [False] * len(cols)
if try_kuhn(u, visited):
m += 1
total += m
return totalimport java.util.*;
class Solution {
int[] matchCol; List<List<Integer>> adj;
boolean tryKuhn(int u, boolean[] vis) {
for (int v : adj.get(u)) {
if (vis[v]) continue;
vis[v] = true;
if (matchCol[v] == -1 || tryKuhn(matchCol[v], vis)) { matchCol[v] = u; return true; }
}
return false;
}
public int emptyShelf(int[][] bookshelf, int k) {
Map<Integer, List<int[]>> byType = new HashMap<>();
for (int i = 0; i < bookshelf.length; i++)
for (int j = 0; j < bookshelf[i].length; j++)
if (bookshelf[i][j] != 0) byType.computeIfAbsent(bookshelf[i][j], x -> new ArrayList<>()).add(new int[]{i, j});
int total = 0;
for (var entry : byType.entrySet()) {
var cells = entry.getValue();
TreeSet<Integer> rs = new TreeSet<>(), cs = new TreeSet<>();
for (var p : cells) { rs.add(p[0]); cs.add(p[1]); }
Map<Integer, Integer> ri = new HashMap<>(), ci = new HashMap<>();
int idx = 0; for (int r : rs) ri.put(r, idx++);
idx = 0; for (int c : cs) ci.put(c, idx++);
adj = new ArrayList<>();
for (int i = 0; i < rs.size(); i++) adj.add(new ArrayList<>());
for (var p : cells) adj.get(ri.get(p[0])).add(ci.get(p[1]));
matchCol = new int[cs.size()]; Arrays.fill(matchCol, -1);
int m = 0;
for (int u = 0; u < rs.size(); u++) {
boolean[] vis = new boolean[cs.size()];
if (tryKuhn(u, vis)) m++;
}
total += m;
}
return total;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<vector<int>> adj;
vector<int> matchCol;
bool tryKuhn(int u, vector<bool>& vis) {
for (int v : adj[u]) {
if (vis[v]) continue;
vis[v] = true;
if (matchCol[v] == -1 || tryKuhn(matchCol[v], vis)) { matchCol[v] = u; return true; }
}
return false;
}
public:
int emptyShelf(vector<vector<int>>& bookshelf, int k) {
map<int, vector<pair<int,int>>> byType;
for (int i = 0; i < (int)bookshelf.size(); i++)
for (int j = 0; j < (int)bookshelf[i].size(); j++)
if (bookshelf[i][j] != 0) byType[bookshelf[i][j]].push_back({i, j});
int total = 0;
for (auto& [t, cells] : byType) {
set<int> rs, cs;
for (auto& p : cells) { rs.insert(p.first); cs.insert(p.second); }
unordered_map<int,int> ri, ci;
int idx = 0; for (int r : rs) ri[r] = idx++;
idx = 0; for (int c : cs) ci[c] = idx++;
adj.assign(rs.size(), {});
for (auto& p : cells) adj[ri[p.first]].push_back(ci[p.second]);
matchCol.assign(cs.size(), -1);
int m = 0;
for (int u = 0; u < (int)rs.size(); u++) {
vector<bool> vis(cs.size(), false);
if (tryKuhn(u, vis)) m++;
}
total += m;
}
return total;
}
};There is a arr of string products given to you, and a string search.
On inserting each character of search in the search bar, the program shows all the
product in the products vector of which the prefix is matching. Of the products
matching we need to show at most top 3 lexicographically smallest strings. All the products are
unique.
Example 1
Input:
products = ["abcd", "abba", "adbc", "abcc"]
search = "abcd"Output:
[["abba", "abcc", "abcd"], ["abba", "abcc", "abcd"], ["abcc", "abcd"], ["abcd"]]Explanation:
The function should return a list of lists of strings, where each list corresponds to the top 3
lexicographically smallest strings in products that match the prefix formed by the
search word up to that point.
Step 1: Word = "a", Matching Prefix Products = ["abba", "abcc", "abcd"]
Step 2: Word = "ab", Matching Prefix Products = ["abba", "abcc", "abcd"]
Step 3: Word = "abc", Matching Prefix Products = ["abcc", "abcd"]
Step 4: Word = "abcd", Matching Prefix Products = ["abcd"]
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理