leetcode
leetcode 1901 ~ 1950
数组的最大与和

数组的最大与和

难度:

标签:

题目描述

代码结果

运行时间: 35 ms, 内存: 16.3 MB


// Java Stream Solution
// 思路:
// 1. 使用回溯法和流式API来枚举所有可能的分配方案。
// 2. 对于每一个方案,计算每个数字与其所在篮子编号的按位与结果之和。
// 3. 通过维护最大值来得到最大与和。
// 
// 代码实现:
import java.util.stream.IntStream;

public class SolutionStream {
    private int maxAndSum;

    public int maxAndSum(int[] nums, int numSlots) {
        maxAndSum = 0;
        int[] slots = new int[numSlots + 1];
        backtrack(nums, 0, slots);
        return maxAndSum;
    }

    private void backtrack(int[] nums, int index, int[] slots) {
        if (index == nums.length) {
            int sum = IntStream.range(1, slots.length)
                                .filter(i -> slots[i] > 0)
                                .map(i -> IntStream.range(0, nums.length)
                                                   .filter(j -> nums[j] == slots[i])
                                                   .map(j -> nums[j] & i)
                                                   .sum())
                                .sum();
            maxAndSum = Math.max(maxAndSum, sum);
            return;
        }

        IntStream.range(1, slots.length).forEach(i -> {
            if (slots[i] < 2) {
                slots[i]++;
                backtrack(nums, index + 1, slots);
                slots[i]--;
            }
        });
    }
}

解释

方法:

该题解使用了网络流的最小费用最大流算法来解决问题。首先,构建一个图,其中包含一个源点和一个汇点,以及代表数字和篮子的节点。为每个数字到每个篮子的边设置一个容量为无穷大,费用为该数字与篮子编号的按位与的负值。这样设置费用是为了最小费用流算法能求得最大与和。同时,将所有数字连接到源点的边的容量设为1,费用设为0,意味着每个数字只能选择一个篮子。每个篮子到汇点的边的容量设置为2,费用为0,表示每个篮子最多只能放两个数字。通过不断找到一条从源点到汇点的最小费用的路径并增加流量,直到没有增广路径存在,计算总的最小费用,并将其转化为最大与和。

时间复杂度:

O(V^2*E)

空间复杂度:

O(V + E)

代码细节讲解

🦆
为什么在构建网络流模型时,将每个数字到篮子的边的费用设置为该数字与篮子编号按位与的负值?
在该问题中,目标是最大化所有数字与其对应篮子编号的按位与的和。为了使用最小费用最大流算法解决这一最大化问题,我们将每个按位与的结果转化为负值作为费用。这样,原本求最小费用的算法就可以通过寻找总费用最小的方式来实际上找到按位与和的最大值。因此,通过设置费用为按位与结果的负值,我们将问题转化为标准的最小费用流问题,使得算法可以应用于此场景。
🦆
在题解中使用SPFA算法寻找最小费用路径,这种方法相比其他如Dijkstra算法有什么优势或特别之处?
SPFA(Shortest Path Faster Algorithm)算法是Bellman-Ford算法的一种改进,它在实际应用中通常比Bellman-Ford更高效。与Dijkstra算法相比,SPFA算法的主要优势在于它可以正确处理图中存在负权边的情况。在最小费用流问题中,由于按位与操作结果转化为负值费用,负权边是常见的。因此,SPFA算法更适合本题解中的场景,能够有效地寻找最小费用路径,即使路径中包含负权边。
🦆
题解中提到,每个篮子到汇点的边的容量设为2,这是如何保证每个篮子至多只能放两个数字的?
在构建网络流模型时,每个篮子到汇点的边的容量设置为2意味着通过这条边的流量不能超过2。这直接限制了每个篮子节点可以接受的总流量,即最多只能有两个数字的流量(每个数字对应单位流量)流入汇点。因此,这种容量设置确保了每个篮子在解决方案中最多只能包含两个数字。
🦆
在题解的算法实现中,如何确保最终的输出是最大与和而非最小与和?
在算法实现中,虽然使用的是最小费用流算法,但是每个数字到篮子的边的费用被设置为了该数字与篮子编号按位与结果的负值。因此,最小化这些负值费用的和实际上等同于最大化原始的按位与结果的和。在算法的最后,通过计算所有路径的负费用乘以流量的总和,并取其负值(即`-dist[end] * min_flow`),从而得到最大的与和。这样确保了最终输出是最大与和而非最小值。

相关问题