作者： admin

目标

在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。

还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。

返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。

示例 1：

输入：price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
输出：14
解释：有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5 。 
大礼包 1 ，你可以以 ¥5 的价格购买 3A 和 0B 。 
大礼包 2 ，你可以以 ¥10 的价格购买 1A 和 2B 。 
需要购买 3 个 A 和 2 个 B ， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。

示例 2：

输入：price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
输出：11
解释：A ，B ，C 的价格分别为 ¥2 ，¥3 ，¥4 。
可以用 ¥4 购买 1A 和 1B ，也可以用 ¥9 购买 2A ，2B 和 1C 。 
需要买 1A ，2B 和 1C ，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B ， ¥4 购买 1C 。 
不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。

说明：

• n == price.length == needs.length
• 1 <= n <= 6
• 0 <= price[i], needs[i] <= 10
• 1 <= special.length <= 100
• special[i].length == n + 1
• 0 <= special[i][j] <= 50
• 生成的输入对于 0 <= j <= n - 1 至少有一个 special[i][j] 非零。

思路

有一个购物清单 need，need[i] 表示需要购买商品 i 的数量，price[i] 表示商品 i 的单价，此外还有一组大礼包 special，special[j][i] 表示大礼包 j 中包含的第 i 件商品的数量，并且 specal[j][n] 表示该大礼包的价格。求购买 need 清单中的商品最少花费多少钱，我们可以购买大礼包任意次，但是购买的总数量不能超过需求的数量，尽管可能价格更低。

完全背包问题是物品有无限个，背包容量有限，求能装下的最大价值/最小价值。如果将题目中的清单视为多个背包容量，单买物品 i，以及购买大礼包 j 中的商品 i 视为不同的商品，那么我们求的是装满所有背包的最小价值。问题在于，大礼包不光有商品 i，还有其它商品，如何处理？

网友题解将单买也看成大礼包，只不过其它商品数量为 0，这样可以统一处理大礼包。

// todo

代码

性能

目标

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

示例 1：

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2：

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

说明:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• edges 中无重复元素
• 给定的图是连通的

思路

有一颗 n 个节点的树，节点编号 1 ~ n。使用 edges 表示向树中两个没有直接连接的节点之间加一条边之后的边的集合，找出一条可以删除的边使得 edges 变为一颗有 n 个节点的树。如果有多种选择，返回 edges 中最后出现的那个，即下标最大的边。

我们可以选择一个根节点，比如从节点 1 出发，使用回溯记录已经访问过的节点，如果发现回到已访问过的非父节点说明出现了环。如果只是寻找环的上的任一条边的话，直接返回即可。

麻烦点在于题目要求返回 edges 中最后出现的边，因此我们需要记录访问的路径，从环开始的节点往后的节点都是在环上的。最后从后向前遍历 edges 找到第一个两端点都在环上的边。

官网题解使用的是并查集。// todo

代码

/**
 * @date 2024-10-27 16:34
 */
public class FindRedundantConnection684 {
    List<Integer>[] g;
    Set<Integer> loop;
    List<Integer> path;
    int start;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        g = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            g[edge[0]].add(edge[1]);
            g[edge[1]].add(edge[0]);
        }
        loop = new HashSet<>(n);
        path = new ArrayList<>();
        dfs(0, 1);
        loop = new HashSet<>();
        for (int i = path.size() - 1; i >= 0; i--) {
            loop.add(path.get(i));
            if (start == path.get(i)) {
                break;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (loop.contains(edges[i][0]) && loop.contains(edges[i][1])) {
                return edges[i];
            }
        }
        return null;
    }

    private boolean dfs(int parent, int current) {
        for (Integer next : g[current]) {
            if (next == parent) {
                continue;
            }
            if (loop.contains(next)) {
                start = next;
                return true;
            } else {
                loop.add(next);
                path.add(next);
                if (dfs(current, next)) {
                    return true;
                }
                path.remove(path.size() - 1);
                loop.remove(next);
            }
        }
        return false;
    }

}

性能

目标

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

• 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
• 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。

以整数形式返回执行最优操作能够获得的 最大 总奖励。

示例 1：

输入：rewardValues = [1,1,3,3]
输出：4
解释：
依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]
输出：11
解释：
依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

说明：

• 1 <= rewardValues.length <= 2000
• 1 <= rewardValues[i] <= 2000

思路

有一个长度为 n 的整数数组 rewardValues 和一个变量 x 初始为 0，可以执行任意次操作，每次操作可以从 [0, n - 1] 中选一个未标记的下标 i，如果 rewardValues[i] > x，x += rewardValues[i]，并标记 i。求 x 的最大值。

// todo

代码

性能