网站建设管理员,阿里云新增网站,网站建设找 三尾狐,网页制作论文3000字题目部分
题目矩阵最大值难度难题目说明给定一个仅包含 0 和 1 的 N*N 二维矩阵#xff0c;请计算二维矩阵的最大值#xff0c;计算规则如下#xff1a; 1. 每行元素按下标顺序组成一个二进制数#xff08;下标越大越排在低位#xff09;#xff0c;二进制数的值就是该行…题目部分
题目矩阵最大值难度难题目说明给定一个仅包含 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 到 N1 行为二维矩阵信息行内元素边角逗号分隔。输出描述矩阵各行之和的最大值。补充说明无------------------------------------------------------示例示例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乘以 设为 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.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最大值 比 稍大此时不会越界。
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;
} (完)
