2025A-矩阵最大值
题目描述与示例
题目描述
给定一个仅包含0和1的N*N二维矩阵，请计算二维矩阵的最大值，计算规则如下:
- 每行元素按下标顺序组成一个二进制数(下标越大越排在低位)，二进制数的值就是该行的值，矩阵各行值之和为矩阵的值。
- 允许通过向左或向右整体循环移动每行元素来改变各元素在行中的位置
比如:
[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行为二维矩阵信息，行内元素 边角逗号分隔。
输出描述
矩阵的最大值。
示例一
输入
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.
解题思路
行与行之间的计算是独立的，我们需要找到每一行的最大值，每一行的最大值进行求和即为整个矩阵的最大值。
将特定的一行row考虑为字符串来处理，计算该行的最大值。由于N的范围较小，我们可以考虑字符串row + row来避免考虑循环操作的问题。
遍历row + row中长度为N的子字符串，并计算对应的十进制结果即可。
暂时无法在飞书文档外展示此内容
关于二进制和十进制之间的转换，可详见文档Python常用内置函数、方法、技巧汇总 中的相关内容。
代码
Python
# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频
# 计算每一行最大值的函数
def cal_max_val_per_row(row, N):
# 拼接row+row，处理循环问题
rowrow = row + row
# 初始化当前最大值max_val
max_val = 0
# 找到所有长度为N的连续子串
for i in range(N):
# 计算字符串切片rowrow[i:i+N]
# 对应的十进制数
cur_val = int(rowrow[i:i+N], base = 2)
# 基于cur_val和先前储存的max_val
# 进行答案的更新
max_val = max(max_val, cur_val)
return max_val
# 输入矩阵大小N
N = int(input())
# 初始化答案
ans = 0
for _ in range(N):
# 由于我们想对字符串row进行处理
# 因此可以直接将输入中的逗号","替换为空字符串""
row = input().replace(",", "")
# 计算当前行row的最大值，叠加进ans中
ans += cal_max_val_per_row(row, N)
print(ans)Java
import java.util.Scanner;
public class Main {
// Function to calculate the maximum value in a row
public static int calMaxValPerRow(String row, int N) {
// Concatenate row with itself to handle circularity
String rowRow = row + row;
// Initialize the current maximum value
int maxVal = 0;
// Find all consecutive substrings of length N
for (int i = 0; i < N; i++) {
// Calculate the decimal value of the substring rowRow[i:i+N]
int curVal = Integer.parseInt(rowRow.substring(i, i + N), 2);
// Update the answer based on curVal and the previously stored maxVal
maxVal = Math.max(maxVal, curVal);
}
return maxVal;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int ans = 0;
scanner.nextLine(); // Consume the newline character after reading N
for (int i = 0; i < N; i++) {
String row = scanner.nextLine().replace(",", "");
ans += calMaxValPerRow(row, N);
}
System.out.println(ans);
}
}C++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// Function to calculate the maximum value in each row
int calMaxValPerRow(string row, int N) {
// Concatenate row with itself to handle circularity
string rowrow = row + row;
// Initialize the current maximum value maxVal
int maxVal = 0;
// Find all substrings of length N
for (int i = 0; i < N; i++) {
// Calculate the decimal value of the substring rowrow.substr(i, N)
int curVal = 0;
for (int j = i; j < i + N; j++) {
curVal = curVal * 2 + (rowrow[j] - '0');
}
// Update the answer based on curVal and the previously stored maxVal
maxVal = max(maxVal, curVal);
}
return maxVal;
}
int main() {
int N;
cin >> N;
int ans = 0;
cin.ignore(); // Consume newline character
for (int i = 0; i < N; i++) {
string row;
getline(cin, row);
row.erase(remove(row.begin(), row.end(), ','), row.end()); // Remove commas
ans += calMaxValPerRow(row, N);
}
cout << ans << endl;
return 0;
}时空复杂度
时间复杂度：O(``N^2``)。每一行都需要计算N个二进制数，一共要计算N行。
空间复杂度：O(``1``)。除了矩阵本身，无需额外空间。