寻找2020 (蓝桥杯) JAVA

题目描述

小蓝有一个数字矩阵,里面只包含数字0 和2。小蓝很喜欢2020,他想找到这个数字矩阵中有多少个2020 。 小蓝只关注三种构成2020
的方式: 同一行里面连续四个字符从左到右构成2020。 同一列里面连续四个字符从上到下构成2020。
在一条从左上到右下的斜线上连续四个字符,从左上到右下构成2020。 例如,对于下面的矩阵:

220000
000000
002202
000000
000022
002020

一共有5 个2020。其中1 个是在同一行里的,1 个是在同一列里的,3 个是斜线上的。
小蓝的矩阵比上面的矩阵要大,由于太大了,他只好将这个矩阵放在了一个文件里面。 在本试题中有一个文件 2020.txt,里面给出了小蓝的矩阵。
请帮助小蓝确定在他的矩阵中有多少个2020。

这是一道结果填空的题,你只需要算出结果后提交即可。
本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

答案:16520

解题思路:

1.首先我们应该明白,这道题采用暴力破解法比较好,不必害怕数据量的庞大,正真执行完连一秒都不需要,等下会在代码下方详细写出计算机执行整个代码所需时间的计算过程。


2.既然要用暴搜,那么就得面临一个问题,如何将文件内容传入数组内,即定义一个多少尺寸的数组才能让数据被装入

方法其实很简单,我们只需要计算出,文件的长和宽就可以了。
以下是计算文件数据宽度的代码:

import java.util.*;

public class Main{
	 public static void main(String[] args){ 
         Scanner sc = new Scanner(System.in);
         String s = sc.nextLine();
         System.out.print(s.length());
	 }
}

只要输入文件矩阵的第一行即可。
输出:
在这里插入图片描述
这样矩阵的宽度,我们就知道了。

接下来只要求出矩阵的面积我们就知道到矩阵的长了代码如下:

import java.util.*;

public class Main{
	 public static void main(String[] args){ 
         Scanner sc = new Scanner(System.in);
         String s = "";
         while(true) {
        	 String s1 = sc.nextLine();
        	 if(s1.equals(null)) break;
        	 s = s + s1;
         }
         System.out.print(s.length());
	 }
}

输出:
在这里插入图片描述
那就很容易得出这个矩阵是一个 300 * 300 的。


3.那么接下来的思路就清晰了,由于题目的规则很明确了,1.从左到右,2.从上到下,3.从左上到右下。分别遍历一下有几个2020即可。为了不漏任何一个点我们每个点都要作为起点。且连续遍历的四个点按顺序依次符合2, 0, 2, 0我们才会记数,否者无效。

本题完整代码如下:

import java.util.*;

public class Main{
	 public static char a[][] = new char[300][300];//存矩阵
	 public static int b[] = new int [4];
	 public static void main(String[] args){ 
		b[0] = 2;b[1] = 0;b[2] = 2;b[3] = 0;//存2020四个值
        Scanner sc = new Scanner(System.in);
        for(int i = 0; i < 300; i ++) {
        	String s = sc.nextLine();
        	a[i] = s.toCharArray();//直接转成数组
        }
        for(int i = 0; i < 300; i ++) {
        	for(int j = 0; j < 300; j ++) {//每个点都要当起点
        		dfsLR(i, j, 0);
        		dfsUD(i, j, 0);
        		dfsSW(i, j, 0);
        	}
        }
        System.out.print(sumlr + sumud + sumsw);
     }
	 public static int sumlr = 0;//左到右
	 public static int sumud = 0;//上到下
	 public static int sumsw = 0;//左上到右下
	 public static void dfsLR(int i, int j, int k) {
		 if(b[k] != a[i][j] - '0') return;//有一个不符合直接退出
		 if(k == 3) {
			 sumlr ++;//符合记数
			 return;
		 }
		 int fxx = i;
		 int fyy = j + 1;//新点
		 if(fxx >= 0 && fxx < 300 && fyy >= 0 && fyy < 300) dfsLR(fxx, fyy, k + 1);//往右遍历
	 }
	 public static void dfsUD(int i, int j, int k) {
		 if(b[k] != a[i][j] - '0') return;
		 if(k == 3) {
			 sumud ++;
			 return;
		 }
		 int fxx = i + 1;
		 int fyy = j;
		 if(fxx >= 0 && fxx < 300 && fyy >= 0 && fyy < 300) dfsUD(fxx, fyy, k + 1);
	 }
	 public static void dfsSW(int i, int j, int k) {
		 if(b[k] != a[i][j] - '0') return;
		 if(k == 3) {
			 sumsw ++;
			 return;
		 }
		 int fxx = i + 1;
		 int fyy = j + 1;
		 if(fxx >= 0 && fxx < 300 && fyy >= 0 && fyy < 300) dfsSW(fxx, fyy, k + 1);
	 }
}

代码运行时间的计算:

计算机每秒可以运行10^9

本代码每个构成的每个点都要遍历,且最坏情况下,每个起点开始都要判断四次 2 0 2 0
那么总遍历次数就是 90000 * 4 * 3 大概就是10^6
那么所需最大时间T = 10^6 / 10^9 大概就是 1ms

是不是比想象得快很多,所以有时候我们不能被其“虚假”的数据量所吓到。😄


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/3938.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

南京邮电大学通达学院《数学实验》MATLAB实验答案

南京邮电大学通达学院《数学实验》MATLAB实验答案一 声明二 MATLAB下载三 南京邮电大学通达学院《数学实验》练习一1.11.21.31.41.51.61.71.81.91.101.11![请添加图片描述](https://img-blog.csdnimg.cn/a3d3a094f6ea4dff85c0fd0bf40bbb44.jpeg)四月维夏&#xff0c;六月徂暑。…

百度文心一言可以完胜ChatGPT的4点可能性

文心一言&#xff0c;百度全新一代知识增强大语言模型&#xff0c;文心大模型家族的新成员&#xff0c;能够与人对话互动&#xff0c;回答问题&#xff0c;协助创作&#xff0c;高效便捷地帮助人们获取信息、知识和灵感。但说实话&#xff0c;很多人拿他与ChatGPT相对比&#x…

项目经理注意!掌握这5个关键点,提升效率80%!

很多项目在刚接手时&#xff0c;遇到的问题种类多并且复杂&#xff0c;乍一看很令人头疼&#xff0c;但仔细梳理下来好像也没有那么难&#xff0c;只需要厘清以下5个关键点&#xff1a; 一、做好项目的五个关键 具体的思路就是: 明确事->找对人->排计划->定机制->…

Bulk vector export as SLD and GeoJson

QGIS插件&#xff0c;可以导出所有图层的GeoJson数据格式和SLD图层样式文件。 缺点&#xff1a;导出的文件名和图层名称不对应。

数据结构与算法:滑动窗口类题目总结

滑动窗口类型题目解题框架总结&#xff1a; class Solution:def problemName(self, s: str) -> int:# Step 1: 定义需要维护的变量们 (对于滑动窗口类题目&#xff0c;这些变量通常是最小长度&#xff0c;最大长度&#xff0c;或者哈希表)x, y ..., ...# Step 2: 定义窗口…

Node.js学习笔记——Node.js模块化

一、介绍 1.1.什么是模块化与模板&#xff1f; 将一个复杂的程序文件依据一定规则&#xff08;规范&#xff09;拆分成多个文件的过程称之为模块化。 其中拆分出的每个文件就是一个模块&#xff0c;模块的内部数据是私有的&#xff0c;不过模块可以暴露内部数据以便其他模块…

【树与二叉树】二叉树顺序结构实现以及堆的概念及结构--详解介绍

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录1. 二叉树顺序结构2.…

Elasticsearch:Elasticsearch 容量规划

Elasticsearch 是一个可扩展的分布式系统&#xff0c;可为企业搜索、日志聚合、可观察性和安全性提供解决方案。 Elastic 解决方案建立在一个单一、灵活的技术堆栈之上&#xff0c;可以部署在任何地方。 要在自托管或云端运行生产环境 Elasticsearch&#xff0c;需要规划基础架…

Linux硬链接与软链接

图示区别 硬链接 具有相同inode节点号的多个文件互为硬链接文件&#xff1b;删除硬链接文件或者删除源文件任意之一&#xff0c;文件实体并未被删除&#xff1b;只有删除了源文件和所有对应的硬链接文件&#xff0c;文件实体才会被删除&#xff1b;硬链接文件是文件的另一个入…

贯穿设计模式第四话--里氏替换原则

&#x1f973;&#x1f973;&#x1f973; 茫茫人海千千万万&#xff0c;感谢这一刻你看到了我的文章&#xff0c;感谢观赏&#xff0c;大家好呀&#xff0c;我是最爱吃鱼罐头&#xff0c;大家可以叫鱼罐头呦~&#x1f973;&#x1f973;&#x1f973; 从今天开始&#xff0c;将…

关于位运算的巧妙性:小乖,你真的明白吗?

一.位运算的概念什么是位运算&#xff1f;程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。位运算就是直接操作二进制数&#xff0c;那么有哪些种类的位运算呢&#xff1f;常见的运算符有与(&)、或(|)、异或(^)、…

软硬结合板设计,过孔到软板区域的间距设计多少合适

一博高速先生成员&#xff1a;王辉东 十里樱花香无边&#xff0c; 满枝芳华尽娇艳。 春风不知少年心&#xff0c; 红粉树下看如烟。 周六的下午&#xff0c;赵理工推开窗&#xff0c;一阵香风袭来&#xff0c;空气中氤氲着樱花的气息。樱花开得浪漫&#xff0c;恰似少年的…

[致敬未来的攻城狮计划 1] 使用 “FSP Configuration”(FSP 配置)透视配置器设置运行环境

开启攻城狮的成长之旅&#xff01;这是我参与的由 CSDN博客专家 架构师李肯&#xff08;http://yyds.recan-li.cn&#xff09;和 瑞萨MCU &#xff08;瑞萨电子 (Renesas Electronics Corporation) &#xff09; 联合发起的「 致敬未来的攻城狮计划 」的第 4 天&#xff0c;点击…

动态规划-不相交的线

动态规划-不相交的线 前言 动态规划中存在一类问题&#xff0c;它涉及到两个数组或链表&#xff0c;需要求解出两个数组中的最长公共子序列&#xff0c;如果要求解两个数组的最长公共子序列。如果采取最原始的方式&#xff0c;选择对第一个数组中的元素的不同排列进行有序组合…

Excel:vlookup函数

Excel:VlookUp函数VlookUp函数VlookUp函数 首先还是先放官方文档的参考&#xff1a;VLOOKUP 函数 Vlookup函数参数&#xff1a; VLOOKUP(lookup_ value, table_ array, col index_ num, [range_ lookup]) lookup_ value&#xff1a;要查找的内容&#xff1b; table_ array&a…

CloudCompare 二次开发(6)——插件中拖拽添加Qt窗口(区域生长算法为例)

目录 一、概述二、插件制作三、Cmake编译四、插件代码五、结果展示一、概述 手动拖拽的方式搭建Qt对话框界面的制作流程,以PCL中的点云区域生长算法为例进行制作。 二、插件制作 1、将....\plugins\example路径下的ExamplePlugin复制一份并修改名字为CCPointCloudProcess。 …

大数据之Spark基础环境

文章目录前言一、Spark概述&#xff08;一&#xff09;Spark是什么&#xff08;二&#xff09;Spark的四大特点&#xff08;三&#xff09;Spark的风雨十年&#xff08;四&#xff09;Spark框架模块&#xff08;五&#xff09;Spark通信框架总结前言 #博学谷IT学习技术支持# 本…

【lwIP(第四章)】网络接口

目录一、lwIP网络接口简介二、lwIP的netif结构三、lwIP的netif相关函数1. lwIP网络接口的全局变量2. netif_add()函数3. netif_remove()函数4. netif_set_default()函数一、lwIP网络接口简介 lwIP协议栈支持多种不同的网络接口&#xff08;网卡&#xff09;&#xff0c;由于网卡…

OSPF----优化

优化主要目的---减少LSA的更新量以及数量 路由汇总&#xff08;减少骨干区域的LSA更新量&#xff09;OSPF特殊秋雨&#xff08;减少非骨干区域的LSA更新量&#xff09;OSPF路由汇总&#xff08;路由聚合&#xff09; OSPF路由汇总是由手工部署的OSPF的汇总称为---区域汇总&…

Swagger快速入门【基础总结】

Swagger 背景信息 什么是前后端分离&#xff1a; 即: Vue Springboot 开发模式 以前是后端时代(后端是主力)&#xff1a;前端只用管理静态页面&#xff1b;html—>后端。 前后端分离时代&#xff1a; 前端 &#xff1a;前端控制层、视图层【前端团队】后端&#xff1a;后…