(B卷,100分)- 矩阵最大值（Java & JS & Python & C）

题目描述

给定一个仅包含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行为二维矩阵信息，行内元素边角逗号分隔。

输出描述

矩阵的最大值。

用例

题目解析

本题数量级不大，可以考虑暴力解法，即双重for。

外层for，遍历每一行。

内层for，将每一行当成双端队列结构，每次尾部出队元素再头部入队，得到一个新状态的二进制字符串，进行N次，即可得到该行所有二进制字符串，我们只需要计算出每个二进制字符串的十进制数，保留最大值，作为该行结果。

最后对每一行的最大十进制数求和即为题解。

Java算法源码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = Integer.parseInt(sc.nextLine());

    int ans = 0;

    for (int i = 0; i < n; i++) {
      LinkedList<Integer> dq =
          Arrays.stream(sc.nextLine().split(","))
              .map(Integer::parseInt)
              .collect(Collectors.toCollection(LinkedList::new));

      int max = getVal(dq);

      for (int j = 1; j < n; j++) {
        dq.addFirst(dq.removeLast());
        max = Math.max(max, getVal(dq));
      }

      ans += max;
    }

    System.out.println(ans);
  }

  public static int getVal(LinkedList<Integer> dq) {
    StringBuilder sb = new StringBuilder();
    for (Integer v : dq) sb.append(v);
    return Integer.parseInt(sb.toString(), 2);
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    n = lines[0] - 0;
  }

  if (n && lines.length === n + 1) {
    lines.shift();
    const matrix = lines.map((line) => line.split(",").map(Number));
    console.log(getResult(n, matrix));
    lines.length = 0;
  }
});

function getResult(n, matrix) {
  let ans = 0;

  for (let i = 0; i < n; i++) {
    let max = parseInt(matrix[i].join(""), 2);
    for (let j = 1; j < n; j++) {
      matrix[i].unshift(matrix[i].pop());
      max = Math.max(max, parseInt(matrix[i].join(""), 2));
    }
    ans += max;
  }

  return ans;
}

Python算法源码

# 输入获取
n = int(input())
matrix = [input().split(",") for _ in range(n)]


# 算法入口
def getResult():
    ans = 0

    for i in range(n):
        maxV = int("".join(matrix[i]), 2)
        for j in range(1, n):
            matrix[i].insert(0, matrix[i].pop())
            maxV = max(maxV, int("".join(matrix[i]), 2))
        ans += maxV

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>

#define MAX_SIZE 20
#define MAX(a,b) a > b ? a : b

int getVal(int dq[], int dq_size);
void move(int dq[], int dq_size);

int main() {
    int n;
    scanf("%d", &n);

    int ans = 0;

    for(int i=0; i<n; i++) {
        int dq[MAX_SIZE];

        for(int j = 0; j < n; j++) {
            scanf("%d", &dq[j]);
            getchar();
        }

        int max = getVal(dq, n);
        for(int j=1; j<n; j++) {
            move(dq, n);
            max = MAX(max, getVal(dq, n));
        }

        ans += max;
    }

    printf("%dn", ans);

    return 0;
}

void move(int dq[], int dq_size) {
    int tmp = dq[0];

    for(int i=1; i<dq_size; i++) {
        dq[i-1] = dq[i];
    }

    dq[dq_size-1] = tmp;
}

int getVal(int dq[], int dq_size) {
    int ans = 0;

    for(int i=0; i<dq_size; i++) {
        ans += dq[i] * (1 << (dq_size - i - 1));
    }

    return ans;
}