当前位置：首页 > news >正文

每日一道算法题 8（2023-12-16）

news 2025/7/13 18:55:44

题目描述
给定一个仅包含0和1的n*n二维矩阵
请计算二维矩阵的最大值
计算规则如下

每行元素按下标顺序组成一个二进制数(下标越大约排在低位)，
二进制数的值就是该行的值，矩阵各行之和为矩阵的值

允许通过向左或向右整体循环移动每个元素来改变元素在行中的位置
比如
[1,0,1,1,1]向右整体循环移动两位[1,1,1,0,1]
二进制数为11101值为29
[1,0,1,1,1]向左整体循环移动两位[1,1,1,1,0]
二进制数为11110值为30
输入描述
数据的第一行为正整数，记录了N的大小，0 < N <= 20
输入的第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
说明

第一行向右整体循环移动一位（11000），得到最大值 24
第二行向右整体循环移动两位（11000），得到最大值 24
第三行向右整体循环移动一位（10100），得到最大值 20
第四行向右整体循环移动两位（11100），得到最大值 28
第五行向右整体循环移动一位（11010），得到最大值 26

因此最大122

package com.tarena.test.B10;

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

/**
* @author Administrator
*
*/
public class B18 {

   public static void main(String[] args) {
       try(Scanner sc = new Scanner(System.in)){
           int lineNum = Integer.parseInt(sc.nextLine());
           List<String> list = new LinkedList<>();
           for(int i=0;i<lineNum;i++) {
               list.add(sc.nextLine());
           }
           System.out.println(resultInt(lineNum,list));
       }
   }

   public static Integer resultInt(int lineNum,List<String> list) {

       int result = 0;

       for(int i=0,len=list.size();i<len;i++) {
           LinkedList<Integer> intList = Arrays.stream(list.get(i).split(","))
                   .map(Integer::parseInt)
                   .collect(Collectors.toCollection(LinkedList::new));
           int max = getVal(intList);
           for(int j=0,len2=intList.size();j<len2;j++) {
               intList.addFirst(intList.removeLast());
               max = Math.max(max, getVal(intList));
           }
           result +=max;
       }
       return result;
   }

   public static int getVal(List<Integer> intList) {
       StringBuilder str = new StringBuilder();
       for(int i=0,len=intList.size();i<len;i++) {
           str.append(intList.get(i));
       }
       return Integer.parseInt(str.toString(), 2);
   }

}
了解知识点