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"]
解法
先把 products 字典序排序。对 search 的每个前缀 P，用二分找到 sorted 中以 P 起头的第一个位置，从那里向后取最多 3 个仍以 P 起头的产品。时间 O(N log N + L·log N)，L 为 search 长。
from bisect import bisect_left
from typing import List
def suggested_products(products: List[str], search: str) -> List[List[str]]:
s = sorted(products)
out: List[List[str]] = []
for i in range(1, len(search) + 1):
prefix = search[:i]
lo = bisect_left(s, prefix)
cur = []
for j in range(lo, min(lo + 3, len(s))):
if s[j].startswith(prefix):
cur.append(s[j])
else:
break
out.append(cur)
return outimport java.util.*;
class Solution {
public List<List<String>> suggestedProducts(String[] products, String search) {
String[] s = products.clone();
Arrays.sort(s);
List<List<String>> out = new ArrayList<>();
for (int i = 1; i <= search.length(); i++) {
String pre = search.substring(0, i);
int lo = Arrays.binarySearch(s, pre);
if (lo < 0) lo = -lo - 1;
List<String> cur = new ArrayList<>();
for (int j = lo; j < Math.min(lo + 3, s.length); j++) {
if (s[j].startsWith(pre)) cur.add(s[j]); else break;
}
out.add(cur);
}
return out;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string search) {
vector<string> s = products;
sort(s.begin(), s.end());
vector<vector<string>> out;
for (int i = 1; i <= (int)search.size(); i++) {
string pre = search.substr(0, i);
int lo = lower_bound(s.begin(), s.end(), pre) - s.begin();
vector<string> cur;
for (int j = lo; j < min(lo + 3, (int)s.size()); j++) {
if (s[j].compare(0, pre.size(), pre) == 0) cur.push_back(s[j]); else break;
}
out.push_back(cur);
}
return out;
}
};