华为OD机考算法题：矩阵最大值

题目部分


题目	矩阵最大值
难度	难
题目说明	给定一个仅包含 0 和 1 的 N*N 二维矩阵，请计算二维矩阵的最大值，计算规则如下： 1. 每行元素按下标顺序组成一个二进制数（下标越大越排在低位），二进制数的值就是该行的值。矩阵各行值之和为矩阵的值。 2. 允许通过向左或向右整体循环移动每行元素来改变各元素在行中的位置。比如： [1,0,1,1,1] 向右整体循环移动 2 位变为 [1,1,1,0,1]，二进制数为 11101，值为 29。 [1,0,1,1,1] 向左整体循环移动 2 位变为 [1,1,1,1,0]，二进制数为 11110，值为 30。
输入描述	1. 输入的第一行为正整数，记录了 N 的大小，0 < N <= 20。 2. 输入的第 2 到 N+1 行为二维矩阵信息，行内元素边角逗号分隔。
输出描述	矩阵各行之和的最大值。
补充说明	无
------------------------------------------------------
示例
示例1
输入	5 1,0,0,0,1 0,0,0,1,1 0,1,0,1,0 1,0,0,1,1 1,0,1,0,1
输出	122
说明	第一行向右整体循环移动 1 位，得到本行的最大值 [1,1,0,0,0]，二进制值为 11000，十进制值为 24。第二行向右整体循环移动 2 位，得到本行的最大值 [1,1,0,0,0]，二进制值为 11000，十进制值为 24。第三行向左整体循环移动 1 位，得到本行的最大值 [1,0,1,0,0]，二进制值为 10100，十进制值为 20。第四行向右整体循环移动 2 位，得到本行的最大值 [1,1,1,0,0]，二进制值为 11100，十进制值为 28。第五行向右整体循环移动 1 位，得到本行的最大值 [1,1,0,1,0]，二进制值为 11010，十进制值为 26。因此，矩阵的最大值为 122。

解读与分析

题目解读：

矩阵的每一行为一个二进制数字，通过左右移动，得到最大的二进制数。输出所有最大二进制数之和。

分析与思路：

1. 解析输入矩阵的每一行，并转换成对应的 10 进制数字；
2. 每一行的二进制数字每向右移动一位，相当于把这个数字（第一步中解析的数字，设为 value）除以 2（取整），设为 valuePart1；然后再把 value % 2 的值（设为 modValue），乘以 $2^{N-1}$ ，设为 valuePart2，计算 valuePart1 与 valuePart2 之和即为向右移动一位之后的结果。
3. 在第 2 步获取的数字的基础上，继续右移。对于一个 N 位的二进制，向右移动 N 位之后就会回到初始值。因而，移动 (N -1) 次求出这 N 个数中的最大值即可。
4. 然后对每一行的最大值求和，并输出。

时间复杂度为 O( $n^{2}$ )，空间复杂度为 O(n)。

代码实现

Java代码

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 支持优先级的队列
 * 
 * @since 2023.10.26
 * @version 0.1
 * @author Frank
 *
 */
public class MatrixMaxValue {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNext()) {
	    String input = sc.nextLine();
	    int count = Integer.parseInt( input );
	    int maxValue = 0;
	    for( int i = 0; i < count; i ++ )
	    {
		input = sc.nextLine();
		maxValue += getMaxValueEachLine( count, input );
	    }
	    System.out.println( maxValue );
	}
    }
    
    private static int getMaxValueEachLine( int count, String input )
    {
	int sourceValue = parseStringValue( input );
	int maxValue = sourceValue;
	 int curValue = sourceValue;
	// 右移 n - 1 次，求最大值
	for( int i = 0; i < count - 1; i ++ )
	{	   
	    int partValue1 = curValue / 2;
	    int partValue2 = (int) Math.round ( ( curValue % 2 ) * Math.pow( 2 , count - 1) );  // 使用round避免误差，不会越界
	    curValue = partValue1 + partValue2;
	    if( curValue > maxValue )
	    {
		maxValue = curValue;
	    }
	}
	return maxValue;
    }

    private static int parseStringValue( String input )
    {
	int ret = 0;
	String[] binaryArr = input.split( "," );
	for( int i = 0; i < binaryArr.length; i ++ )
	{
	    ret *= 2;
	    ret += Integer.parseInt( binaryArr[i] );
	}
	
	return ret;
    }
}

在以上 Java 代码中，Math.pow() 函数返回的是浮点数，为了避免浮点数计算时出现误差（大概率应该不会出现误差），为了保证程序的正确性，最后使用了 Math.round() 函数。
Math.round() 返回 long 型数字，为了避免数据类型不匹配，使用强制数据类型转换。因为 N 的最大值是 20，最大值 $2^{20} - 1$ ，比 $10^{6}$ 稍大，此时不会越界。

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
    while (line = await readline()) {
        var count = parseInt( line );
        var maxValue = 0;
        for (var i = 0; i < count; i++) {
            line = await readline()
            maxValue += getMaxValueEachLine(count, line );
        }
        console.log(maxValue);
    }
}();

function getMaxValueEachLine(count, input) {
    var sourceValue = parseStringValue(input);
    var maxValue = sourceValue;
    var curValue = sourceValue;
    // 右移 n - 1 次，求最大值
    for (var i = 0; i < count - 1; i++) {
        var partValue1 = parseInt( curValue / 2 );
        var partValue2 = Math.round((curValue % 2) * Math.pow(2, count - 1)); // 使用round，避免误差，不会越界
        curValue = partValue1 + partValue2;
        if (curValue > maxValue) {
            maxValue = curValue;
        }
    }
    return maxValue;
}

function parseStringValue(input) {
    var ret = 0;
    var binaryArr = input.split(",");
    for (var i = 0; i < binaryArr.length; i++) {
        ret *= 2;
        ret += parseInt(binaryArr[i]);
    }

    return ret;
}

(完)