題目部分

題目	矩陣最大值
難度	難
題目說明	給定一個僅包含 0 和 1 的 N*N 二維矩陣，請計算二維矩陣的最大值，計算規(guī)則如下： 1. 每行元素按下標順序組成一個二進制數(shù)（下標越大越排在低位），二進制數(shù)的值就是該行的值。矩陣各行值之和為矩陣的值。 2. 允許通過向左或向右整體循環(huán)移動每行元素來改變各元素在行中的位置。 比如： [1,0,1,1,1] 向右整體循環(huán)移動 2 位變?yōu)?[1,1,1,0,1]，二進制數(shù)為 11101，值為 29。 [1,0,1,1,1] 向左整體循環(huán)移動 2 位變?yōu)?[1,1,1,1,0]，二進制數(shù)為 11110，值為 30。
輸入描述	1. 輸入的第一行為正整數(shù)，記錄了 N 的大小，0 < N <= 20。 2. 輸入的第 2 到 N+1 行為二維矩陣信息，行內(nèi)元素邊角逗號分隔。
輸出描述	矩陣各行之和的最大值。
補充說明	無
------------------------------------------------------
示例
示例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
說明	第一行向右整體循環(huán)移動 1 位，得到本行的最大值 [1,1,0,0,0]，二進制值為 11000，十進制值為 24。 第二行向右整體循環(huán)移動 2 位，得到本行的最大值 [1,1,0,0,0]，二進制值為 11000，十進制值為 24。 第三行向左整體循環(huán)移動 1 位，得到本行的最大值 [1,0,1,0,0]，二進制值為 10100，十進制值為 20。 第四行向右整體循環(huán)移動 2 位，得到本行的最大值 [1,1,1,0,0]，二進制值為 11100，十進制值為 28。 第五行向右整體循環(huán)移動 1 位，得到本行的最大值 [1,1,0,1,0]，二進制值為 11010，十進制值為 26。 因此，矩陣的最大值為 122。

---

解讀與分析

題目解讀：

矩陣的每一行為一個二進制數(shù)字，通過左右移動，得到最大的二進制數(shù)。輸出所有最大二進制數(shù)之和。

分析與思路：

1. 解析輸入矩陣的每一行，并轉換成對應的 10 進制數(shù)字；
2. 每一行的二進制數(shù)字每向右移動一位，相當于把這個數(shù)字（第一步中解析的數(shù)字，設為 value） 除以 2（取整），設為 valuePart1；然后再把?value % 2 的值（設為 modValue），乘以?，設為 valuePart2，計算 valuePart1 與 valuePart2 之和即為向右移動一位之后的結果。
3. 在第 2 步獲取的數(shù)字的基礎上，繼續(xù)右移。對于一個 N 位的二進制，向右移動 N 位之后就會回到初始值。因而，移動 (N -1) 次求出這 N 個數(shù)中的最大值即可。
4. 然后對每一行的最大值求和，并輸出。

時間復雜度為 O()，空間復雜度為 O(n)。

---

代碼實現(xiàn)

Java代碼

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;/*** 支持優(yōu)先級的隊列* * @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() 函數(shù)返回的是浮點數(shù)，為了避免浮點數(shù)計算時出現(xiàn)誤差（大概率應該不會出現(xiàn)誤差），為了保證程序的正確性，最后使用了?Math.round() 函數(shù)。
Math.round() 返回 long 型數(shù)字，為了避免數(shù)據(jù)類型不匹配，使用強制數(shù)據(jù)類型轉換。因為 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;
}

(完)