欢迎大家加QQ群:623375442。这周题目有点思维题。以前做过就不难。没碰到过的话,还是很有难度的。
Q1. 优惠券代码验证器
题目描述
给定三个长度为 n
的数组,分别表示 n
张优惠券的属性:code
、businessLine
和 isActive
。第 i
张优惠券具有以下属性:
code[i]
:一个字符串,表示优惠券的标识符。businessLine[i]
:一个字符串,表示优惠券的业务类别。isActive[i]
:一个布尔值,表示优惠券是否当前有效。
如果满足以下所有条件,则认为该优惠券有效:
- code[i] 非空,且仅由字母(a-z,A-Z)、数字(0-9)和下划线(_)组成。
- businessLine[i] 属于以下四个类别之一:
"electronics"
、"grocery"
、"pharmacy"
、"restaurant"
。 - isActive[i] 为
true
。
返回一个包含所有有效优惠券代码的数组,按照 businessLine
排序,顺序为:"electronics"
、"grocery"
、"pharmacy"
、"restaurant"
,然后在每个类别内部按照代码的字典顺序升序排序。
解题思路
- 过滤有效优惠券:遍历所有优惠券,只有满足
isActive[i] == true
、code[i]
非空且只包含字母、数字或下划线、businessLine[i]
在四个指定类别中时,才将其索引加入候选列表。 - 排序:对候选索引列表进行排序,首先按照
businessLine
的固定顺序(electronics < grocery < pharmacy < restaurant),若类别相同则再按照code
的字典序升序。 - 收集结果:遍历排序后的索引列表,按顺序将对应的
code
添加到结果列表并返回。
class Solution {
// 定义合法业务线的顺序数组,用于后续排序时比较顺序
private static final String[] validBusiness = {"electronics", "grocery", "pharmacy", "restaurant"};
public List<String> validateCoupons(String[] code, String[] businessLine, boolean[] isActive) {
// 存放符合条件的优惠券索引
List<Integer> buffer = new ArrayList<>();
int len = code.length;
// 遍历每张优惠券
for (int i = 0; i < len; ++i) {
// 如果优惠券有效且代码和业务线合法,则加入候选列表
if (isActive[i] && isValidCode(code[i]) && isValidBusiness(businessLine[i])) {
buffer.add(i);
}
}
// 对索引列表进行排序:先按业务线顺序,再按代码字典序
Collections.sort(buffer, (a, b) -> {
// 如果业务线相同,则按 code 的字典序比较
if (businessLine[a].equals(businessLine[b])) {
return code[a].compareTo(code[b]);
}
// 不同业务线时,按 validBusiness 数组中的顺序比较
return getBusinessOrder(businessLine[a]) - getBusinessOrder(businessLine[b]);
});
// 构造结果列表
List<String> res = new ArrayList<>();
for (int idx : buffer) {
res.add(code[idx]);
}
return res;
}
// 检查 code 是否只包含字母、数字或下划线,且非空
private boolean isValidCode(String code) {
if (code == null || code.length() == 0) {
return false; // 为空则不合法
}
for (int i = 0; i < code.length(); ++i) {
char c = code.charAt(i);
// 判断字符是否是数字、字母或下划线
if ((c >= '0' && c <= '9') ||
(c >= 'a' && c <= 'z') ||
(c >= 'A' && c <= 'Z') ||
c == '_') {
// 合法字符,继续检查
} else {
return false; // 出现其他字符则不合法
}
}
return true;
}
// 判断业务线是否合法
private boolean isValidBusiness(String business) {
for (String b : validBusiness) {
if (b.equals(business)) {
return true;
}
}
return false;
}
// 获取业务线在 validBusiness 数组中的顺序,用于自定义排序
private int getBusinessOrder(String business) {
for (int i = 0; i < validBusiness.length; i++) {
if (validBusiness[i].equals(business)) {
return i;
}
}
return Integer.MAX_VALUE; // 如果未找到,置为最大值,排在最后
}
}
Q2. 电力网维护
题目描述
给定一个整数 c
,表示 c
个电力站,每个电力站都有一个唯一的标识符 id
,范围为 1 到 c
(1-based 索引)。
这些电力站通过 n
条双向电缆相互连接,表示为一个 2D 数组 connections
,其中每个元素 connections[i] = [ui, vi]
表示电力站 ui
和电力站 vi
之间的连接。直接或间接连接的电力站形成一个电力网。
初始时,所有电力站都处于在线(正常运行)状态。
你还将给定一个 2D 数组 queries
,其中每个查询可以是以下两种类型之一:
[1, x]
:请求对电力站x
进行维护检查。如果电力站x
在线,则由它自己解决检查。如果电力站x
离线,则由同一电力网中最小id
的正常电力站解决检查。如果该电力网中没有在线电力站,则返回 -1。[2, x]
:电力站x
离线(即变为非操作状态)。
返回一个整数数组,表示每个类型为 [1, x]
查询的结果,按出现顺序返回。
解题思路
- 构建并查集:使用 DSU 将所有电力站根据连接
connections
合并成若干电力网,每个网对应一个根节点。 - 维护在线集合:为每个并查集根节点维护一个
TreeSet<Integer>
,存储当前在线的电力站 id,集合自动保持升序。 -
处理查询:
- 类型 2 (
[2, x]
):将电力站x
从对应集合中移除,标记离线。 - 类型 1 (
[1, x]
):若x
在线,则返回x
;否则,若集合非空,返回集合中的最小元素;若集合为空,返回 -1。
- 类型 2 (
class Solution {
public int[] processQueries(int c, int[][] connections, int[][] queries) {
// 初始化并查集,节点编号从 1 到 c,故数组大小为 c+1
DSU uf = new DSU(c + 1);
// 将所有连接对在并查集中合并
for (int[] con : connections) {
uf.union(con[0], con[1]);
}
// 为每个连通分量根节点维护一个 TreeSet,存储在线节点 ID
@SuppressWarnings("unchecked")
TreeSet<Integer>[] sets = new TreeSet[c + 1];
for (int i = 1; i <= c; ++i) {
int root = uf.find(i);
if (sets[root] == null) {
sets[root] = new TreeSet<>();
}
sets[root].add(i); // 初始时所有节点都在线
}
List<Integer> resList = new ArrayList<>();
// 处理每条查询
for (int[] q : queries) {
int type = q[0], id = q[1];
int root = uf.find(id);
if (type == 2) {
// 类型 2:节点下线,从集合中移除
sets[root].remove(id);
} else {
// 类型 1:维护检查
if (sets[root].contains(id)) {
// 自己在线,返回自身
resList.add(id);
} else if (sets[root].isEmpty()) {
// 本网格无在线节点,返回 -1
resList.add(-1);
} else {
// 返回当前网格中最小的在线节点 ID
resList.add(sets[root].first());
}
}
}
// 转换结果为数组
int[] res = new int[resList.size()];
for (int i = 0; i < resList.size(); i++) {
res[i] = resList.get(i);
}
return res;
}
}
class DSU {
private int[] parent;
// 构造函数,初始化 parent[i] = i
public DSU(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找操作,带路径压缩
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并操作,将 x 的根连接到 y 的根
public void union(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
parent[fx] = fy;
}
}
}
Q3. 最小时间达到 k
个连通分量
题目描述
给定整数 n
和一个无向图,图中有 n
个节点,标号从 0 到 n - 1
。通过一个 2D 数组 edges
表示边集,其中 edges[i] = [ui, vi, timei]
表示边 (ui, vi)
会在时间 timei
被删除。
你需要找到最小时间 t
,使得在删除所有 time <= t
的边后,图中至少包含 k
个连通分量。
解题思路
- 排序边:将所有边按照
time
降序排序,便于从大时间向小时间依次“恢复”边的存在。 - 并查集初始化:初始化并查集,初始时有
n
个连通分量(remain = n
)。 -
遍历边:
- 对每条边
(u, v, time)
,若当前连通分量数remain >= k
,则记录res = time
,然后将这条边连接(union),减少连通分量数。 - 若
remain < k
,停止遍历。
- 对每条边
- 特殊情况:若初始连通分量数就已达到
k
,返回t = 0
。 - 返回结果:最终
res
即为删除到该时间后,连通分量数首次达到(或超过)k
时所对应的最小时间。
class Solution {
public int minTime(int n, int[][] edges, int k) {
// 按删除时间降序排序边
Arrays.sort(edges, (a, b) -> Integer.compare(b[2], a[2]));
DSU uf = new DSU(n);
int res = Integer.MAX_VALUE;
// 遍历每条边
for (int[] e : edges) {
// 如果当前连通分量数量已达到 k,则记录此时删除的边对应的时间
if (uf.getRemain() >= k) {
res = e[2];
} else {
// 否则合并这条边对应的两个节点
uf.union(e[0], e[1]);
}
}
// 如果初始时就满足条件,返回 0
if (uf.getRemain() >= k) {
return 0;
}
return res;
}
}
class DSU {
private int[] parent;
private int remain; // 当前连通分量数量
public DSU(int n) {
parent = new int[n];
// 初始时每个节点都是独立的连通分量
for (int i = 0; i < n; i++) {
parent[i] = i;
}
remain = n;
}
// 查找根节点,路径压缩
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并操作,如果两个节点不在同一分量则合并并更新 remain
public void union(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
parent[fx] = fy;
remain--; // 合并后分量数减少
}
}
// 获取当前连通分量数量
public int getRemain() {
return remain;
}
}
Q4. 最小步数到达目标点
题目描述
给定四个整数 sx
, sy
, tx
, ty
,表示二维网格中的两个点 (sx, sy)
和 (tx, ty)
。
在任何点 (x, y)
,定义 m = max(x, y)
。可执行以下两种操作之一:
- 移动到
(x + m, y)
。 - 移动到
(x, y + m)
。
返回到达 (tx, ty)
的最小步数,如果无法到达则返回 -1。
解题思路
- 逆向思考:从目标点
(tx, ty)
反向到起点(sx, sy)
,每步将较大坐标big
通过逆操作reduce(big, small)
缩小到上一步状态,直至回到起点。 -
reduce 方法:
- 若
big
为偶数且big/2 >= small
,说明上一步可能是将(big/2, small)
的x
坐标加倍。 - 否则,若
big - small <= small
,说明上一步可能是将(small, small)
的y
坐标加上small
得到big
。 - 否则,无法找到合法逆操作,返回 -1。
- 若
- 循环终止条件:当
(tx, ty)
走回(sx, sy)
或者某步无法逆回起点时结束。 - 返回步数:记录逆向操作次数即为正向最小步数。
class Solution {
public int minMoves(int sx, int sy, int tx, int ty) {
int count = 0; // 步数计数
// 只要目标坐标在起始坐标的右上方,就继续尝试回退
while (tx >= sx && ty >= sy) {
// 若已回退到起点,则结束
if (tx == sx && ty == sy) {
break;
}
count++; // 每次回退算一步
if (tx > ty) {
// 若 x 较大,则减少 x
tx = findLastNumber(tx, ty);
if (tx == -1) {
return -1; // 无法合法回退
}
} else if (tx < ty) {
// 若 y 较大,则减少 y
ty = findLastNumber(ty, tx);
if (ty == -1) {
return -1; // 无法合法回退
}
} else {
// tx == ty 时,根据起点情况特殊处理
if (sx == 0) {
tx = 0;
} else {
ty = 0;
}
}
}
// 检查是否成功回退到起点
return (tx == sx && ty == sy) ? count : -1;
}
/**
* 计算上一步的大坐标值
* @param big 当前较大坐标
* @param small 当前较小坐标
* @return 上一步的大坐标,或 -1 表示不可达
*/
private int findLastNumber(int big, int small) {
// 情况 1:big 可由自身的一半回退
if (big % 2 == 0 && big / 2 >= small) {
return big / 2;
} else {
// 情况 2:big 可由 big - small 回退
int remain = big - small;
if (remain > small) {
return -1; // 回退后仍大于另一坐标,不合法
} else {
return remain;
}
}
}
}