最大方阵和
难度:
标签:
题目描述
给你一个 n x n 的整数方阵 matrix 。你可以执行以下操作 任意次 ：
- 选择
matrix中 相邻 两个元素，并将它们都 乘以-1。
如果两个元素有 公共边 ，那么它们就是 相邻 的。
你的目的是 最大化 方阵元素的和。请你在执行以上操作之后，返回方阵的 最大 和。
示例 1：
输入：matrix = [[1,-1],[-1,1]] 输出：4 解释：我们可以执行以下操作使和等于 4 ： - 将第一行的 2 个元素乘以 -1 。 - 将第一列的 2 个元素乘以 -1 。
示例 2：
输入：matrix = [[1,2,3],[-1,-2,-3],[1,2,3]] 输出：16 解释：我们可以执行以下操作使和等于 16 ： - 将第二行的最后 2 个元素乘以 -1 。
提示：
n == matrix.length == matrix[i].length2 <= n <= 250-105 <= matrix[i][j] <= 105
代码结果
运行时间: 83 ms, 内存: 23.8 MB
/*
题目思路：
与之前的解法相同，但这里使用Java Stream API来处理数组的遍历和求和。
算法步骤：
1. 使用Stream遍历矩阵，将负数转换为正数并统计总和。
2. 使用Stream查找最小的绝对值元素。
3. 根据负数的个数是否为奇数，调整最终的和。
*/
import java.util.Arrays;
public class MaxMatrixSumStream {
public static int maxMatrixSum(int[][] matrix) {
int n = matrix.length;
// 计算总和和找到最小的绝对值
int totalSum = Arrays.stream(matrix)
.flatMapToInt(Arrays::stream)
.map(Math::abs)
.sum();
int minAbsValue = Arrays.stream(matrix)
.flatMapToInt(Arrays::stream)
.map(Math::abs)
.min()
.getAsInt();
// 统计负数的个数
long negativeCount = Arrays.stream(matrix)
.flatMapToInt(Arrays::stream)
.filter(x -> x < 0)
.count();
// 如果负数的个数是奇数，则减去最小的绝对值两次
if (negativeCount % 2 != 0) {
totalSum -= 2 * minAbsValue;
}
return totalSum;
}
public static void main(String[] args) {
int[][] matrix1 = {{1, -1}, {-1, 1}};
int[][] matrix2 = {{1, 2, 3}, {-1, -2, -3}, {1, 2, 3}};
System.out.println(maxMatrixSum(matrix1)); // 输出：4
System.out.println(maxMatrixSum(matrix2)); // 输出：16
}
}解释
方法:
这道题目的思路是通过矩阵的行和列的操作，使得矩阵中尽可能多的元素变为正数，从而最大化矩阵元素的和。首先遍历矩阵的每一行，统计每行中负数的个数。如果负数的个数为偶数，那么可以通过翻转操作使得该行所有元素都变为正数。如果负数的个数为奇数，那么可以翻转除了一个绝对值最小的负数以外的所有负数，使得该行只剩下一个负数。接着，统计转换后留有一个负数的行数，如果这个数为偶数，那么可以通过列的翻转操作，使得所有行都变为正数。如果这个数为奇数，那么最终会剩下一个负数，我们选择矩阵中绝对值最小的那个数成为负数。最后，返回矩阵所有元素的绝对值之和，如果有剩余的负数，则减去该负数的两倍。
时间复杂度:
O(n^2)
空间复杂度:
O(1)
代码细节讲解
🦆
在解决方案中，你是如何确定将哪一行或哪一列的元素进行翻转？
▷🦆
为什么在负数个数为奇数的行中，选择保留绝对值最小的负数而不是其他负数？
▷🦆
如何处理矩阵中所有元素均为负数的情况？是否存在特殊的翻转策略？
▷🦆
在进行行和列的翻转操作时，是否考虑了翻转顺序可能对最终结果的影响？
▷