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

题目部分

解读与分析

题目解读：

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

分析与思路：

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

时间复杂度为 O()，空间复杂度为 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.27
 * @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，最大值 ，比  稍大，此时不会越界。

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;
}

(完)