欢迎大家加QQ群:623375442。这周题目有点思维题。以前做过就不难。没碰到过的话,还是很有难度的。

Q1. 优惠券代码验证器

题目描述

给定三个长度为 n 的数组,分别表示 n 张优惠券的属性:codebusinessLineisActive。第 i 张优惠券具有以下属性:

  1. code[i]:一个字符串,表示优惠券的标识符。
  2. businessLine[i]:一个字符串,表示优惠券的业务类别。
  3. isActive[i]:一个布尔值,表示优惠券是否当前有效。

如果满足以下所有条件,则认为该优惠券有效:

  1. code[i] 非空,且仅由字母(a-z,A-Z)、数字(0-9)和下划线(_)组成。
  2. businessLine[i] 属于以下四个类别之一:"electronics""grocery""pharmacy""restaurant"
  3. isActive[i] 为 true

返回一个包含所有有效优惠券代码的数组,按照 businessLine 排序,顺序为:"electronics""grocery""pharmacy""restaurant",然后在每个类别内部按照代码的字典顺序升序排序。

解题思路

  1. 过滤有效优惠券:遍历所有优惠券,只有满足 isActive[i] == truecode[i] 非空且只包含字母、数字或下划线、businessLine[i] 在四个指定类别中时,才将其索引加入候选列表。
  2. 排序:对候选索引列表进行排序,首先按照 businessLine 的固定顺序(electronics < grocery < pharmacy < restaurant),若类别相同则再按照 code 的字典序升序。
  3. 收集结果:遍历排序后的索引列表,按顺序将对应的 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] 查询的结果,按出现顺序返回。

解题思路

  1. 构建并查集:使用 DSU 将所有电力站根据连接 connections 合并成若干电力网,每个网对应一个根节点。
  2. 维护在线集合:为每个并查集根节点维护一个 TreeSet<Integer>,存储当前在线的电力站 id,集合自动保持升序。
  3. 处理查询

    • 类型 2 ([2, x]):将电力站 x 从对应集合中移除,标记离线。
    • 类型 1 ([1, x]):若 x 在线,则返回 x;否则,若集合非空,返回集合中的最小元素;若集合为空,返回 -1。
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 个连通分量。

解题思路

  1. 排序边:将所有边按照 time 降序排序,便于从大时间向小时间依次“恢复”边的存在。
  2. 并查集初始化:初始化并查集,初始时有 n 个连通分量(remain = n)。
  3. 遍历边

    • 对每条边 (u, v, time),若当前连通分量数 remain >= k,则记录 res = time,然后将这条边连接(union),减少连通分量数。
    • remain < k,停止遍历。
  4. 特殊情况:若初始连通分量数就已达到 k,返回 t = 0
  5. 返回结果:最终 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。

解题思路

  1. 逆向思考:从目标点 (tx, ty) 反向到起点 (sx, sy),每步将较大坐标 big 通过逆操作 reduce(big, small) 缩小到上一步状态,直至回到起点。
  2. reduce 方法

    • big 为偶数且 big/2 >= small,说明上一步可能是将 (big/2, small)x 坐标加倍。
    • 否则,若 big - small <= small,说明上一步可能是将 (small, small)y 坐标加上 small 得到 big
    • 否则,无法找到合法逆操作,返回 -1。
  3. 循环终止条件:当 (tx, ty) 走回 (sx, sy) 或者某步无法逆回起点时结束。
  4. 返回步数:记录逆向操作次数即为正向最小步数。
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;
            }
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *