總結：與往屆題目相比，，暴力題型少了許多，增加了dp和圖論的考察，不過在不會的情況下，暴力還是能騙不少分的
目錄
試題A：門牌制作
試題B：尋找2020
試題C：蛇形填數
試題D：七段碼
試題E：排序
試題F：成績分析
試題G：單詞分析
試題H：數字三角形
試題I：子串分值和
試題J：裝飾珠
試題A：門牌制作
思路：列舉就行，水題一道，沒啥說的，上代碼
public class 門牌制作 {
public static void main(String[] args) {
int cnt=0;
for (int i = 1; i <= 2020; i++) {
String s=i+"";
for (int j = 0; j < s.length(); j++) {
if(s.charAt(j)=='2') cnt++;
}
}
System.out.println(cnt);
}
}
答案：624
試題B：尋找2020
思路：這道題比較重要的一個地方就是檔案的讀取了，畢竟有幾百行，我這里使用的是BufferedReander來讀取，需要注意的是，該類在使用readline方法時，若沒有檔案內容了，將回傳null，因此我們可以
利用這一點來通過while(read.readline()!=null)來對檔案進行讀取，讀取的字串再轉換為char陣列，這一步完成后，就沒啥難度了，暴力就是
import java.io.*;
public class 尋找2020 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(new FileInputStream("D:\\QQ檔案\\2020.txt")));
String s="";
char [][]arr=new char[300][];
int cur=0;
int ans=0;
while((s=bf.readLine())!=null)
{
arr[cur++]=s.toCharArray();
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if(arr[i][j]=='2')
{
if(i<arr.length-3&&arr[i+1][j]=='0'&&arr[i+2][j]=='2'&&arr[i+3][j]=='0') ans++;//從上往下看
if(j<arr[i].length-3&&arr[i][j+1]=='0'&&arr[i][j+2]=='2'&&arr[i][j+3]=='0') ans++;//從左往右看
if(i<arr.length-3&&j<arr[i].length-3&&arr[i+1][j+1]=='0'&&arr[i+2][j+2]=='2'&&arr[i+3][j+3]=='0') ans++;//斜著看
}
}
}
System.out.println(ans);
}
}
答案：16520
試題C：蛇形填數
思路：這里我們仔細觀察他填數的規律，先是第一行第一列，然后右填一個，進而往左下角填，左下角填的規律是x增加，y減少，終止條件是y減少到1列，終止后往下填一位，進而右上填，右上填的規律是x--
，y++，終止條件是x減少到1，因此我們可以模擬這個程序，用while(arr[20][20]!0)來進行模擬，上代碼
public class 蛇形填數 {
static int [][]arr=new int[100][100];
public static void main(String[] args) {
int curx=1;//定義橫坐標x的位置
int cury=1;//縱坐標y的位置
int ans=0;//目前排到哪個數了
arr[curx][cury]=++ans;//初始化第一個值
while(arr[20][20]==0)//當我們的目標值已經被填充時退出回圈
{
arr[curx][++cury]=++ans;//右填一位，然后開始左下遞推
while(cury>1)//左下遞推的規律是x增加，y減少，終止標志是y減少到1,等于1時就該退出回圈了
{
arr[++curx][--cury]=++ans;
}
arr[++curx][cury]=++ans;//下移一位，然后開始右上遞推
while(curx>1)//右上遞推的規律是x減少，y增加，終止標志是x減少到1，等于1時就該退出回圈了
{
arr[--curx][++cury]=++ans;
}
}
System.out.println(arr[20][20]);
}
}
答案：761
試題D：七段碼
思路：我們將這七個燈泡用1~7來表示，然后用集合列舉的方式，列舉出他們的所有組合，然后判斷每個組合是否連通，前者使用dfs列舉即可，而后者使用并查集來判斷(ps：并查集是用來判斷不同的成員是否
可以相互連通的一種工具，例如：a認識b，b認識c，c認識d，那么如何判斷a是否認識d呢？這不是本篇討論的重點，詳情請移至該大佬的博客：https://blog.csdn.net/chen134225/article/details/82052537)，上代碼
public class 七段碼 {
static int [] bin;//并查集陣列
static int [][]arr;//記錄相鄰關系
static boolean [] key;//記錄該編號的燈泡是否已經被選
static int ans;
public static void main(String[] args) {
arr=new int[8][8];//賦值為1表示兩個編號的燈泡是相鄰的，具有連通的條件
arr[1][2]=1;
arr[1][6]=1;
arr[2][1]=1;
arr[2][3]=1;
arr[2][7]=1;
arr[3][4]=1;
arr[3][7]=1;
arr[3][2]=1;
arr[4][3]=1;
arr[4][5]=1;
arr[5][4]=1;
arr[5][6]=1;
arr[5][7]=1;
arr[6][1]=1;
arr[6][7]=1;
arr[6][5]=1;
arr[7][2]=1;
arr[7][6]=1;
arr[7][5]=1;
arr[7][3]=1;
int [] record=new int[8];
key=new boolean[8];
dfs(0,0,record);
System.out.println(ans);
}
/**
* 該方法為并查集的尋找根節點的方法
* @param x 回傳該編號結點的祖宗結點
* @return
*/
private static int find(int x)
{
if(x==bin[x]) return x;
return bin[x]=find(bin[x]);
}
/**
*
* @param cur 記錄當前被挑中的燈管的編號
* @param max 當前被挑選的燈泡的最大編號
* @param record 目前已經被選中的燈泡編號的集合
*/
private static void dfs(int cur,int max,int [] record)
{
if(judge(record,cur)) ans++;
for (int i = max+1; i <= 7; i++) {
if(!key[i])
{
key[i]=true;
record[cur]=i;
dfs(cur+1,i,record);
key[i]=false;
}
}
}
/**
* 該方法的作用是判斷當前集合是否滿足相鄰
* @param now 當前被挑選的燈泡的集合
* @param cur 當前集合中燈泡的數目
* @return
*/
public static boolean judge(int [] now,int cur)
{
int cnt=cur-1;//使得所有的點剛好連通的最少邊的數目等于點的數目減一，因此我們需要判斷能否構建這么多的邊
bin=new int[8];
//初始化并查集陣列
for (int i = 0; i < 8; i++) {
bin[i]=i;
}
for (int i = 0; i < cur; i++) {
for (int j = i+1; j < cur; j++) {
if(find(now[i])!=find(now[j])&&arr[now[i]][now[j]]==1)//若兩個點互不聯通
{
cnt--;//構建一條邊，還需要構建的邊數減一
bin[find(now[i])]=bin[find(now[j])];//構建邊
}
}
}
if(cnt==0) return true;//剛好構建完成則回傳true
return false;
}
}
答案：80
試題E：排序
思路：不會，，，，
試題F：成績分析
思路：過于簡單，直接上代碼：
import java.util.Scanner;
public class 成績分析 {
public static void main(String[] args) {
int max=0;
int min=1000;
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
double mid=0;
for (int i = 0; i < n; i++) {
int x=scanner.nextInt();
max=Math.max(x,max);
min=Math.min(x,min);
mid+=x;
}
System.out.println(max);
System.out.println(min);
System.out.printf("%.2f",(mid/n));
}
}
試題G：單詞分析
思路：開個26長度的數字來計數即可，寫入的時候用i-'a'來寫入即可，沒啥說的，上代碼：
import java.util.Scanner;
public class 單詞分析 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s=scanner.nextLine();
char arr[]=new char[26];
for (int i = 0; i < s.length(); i++) {
arr[s.charAt(i)-'a']++;
}
int max=0;
char ans=' ';
for (int i = 0; i < arr.length; i++) {
if(arr[i]>max)
{
max=arr[i];
ans=(char) (i+'a');
}
}
System.out.println(ans);
System.out.println(max);
}
}
試題H：數字三角形
思路：吐血分享，，，，這個題條件里面的：向左下走的次數和向右下走的次數不能超過1，我一直一直一直以為是實時的要求，例如我第一步向左下角走了，那么我下一步就只能右下角走，如果我第一步向右下角走了，下一步只能向左下角走，但是！但是！但是！，這是錯誤的理解，正解是：你可以隨便怎么走，只需要保證到達底部的時候左下角的總次數不能和右下角的次數超過1，例如總共需要走5步時，我可先連續走兩步左下角，也可以連續走三步右下角，，也可以交叉著來，，，，，好了，理解了這一點之后這題就沒有難度了，就是一道普通的dp數字三角形，每一步都來源于左上角或者右上角，所以我們可以遞推出結果，輸出的時候需要注意當n為奇數和偶數的區別，代碼
import java.util.Scanner;
public class 數字三角形 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int [][]arr=new int[n+1][n+1];
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= i; j++) {
int s=scanner.nextInt();
arr[i][j]=s+Math.max(arr[i-1][j-1],arr[i-1][j]);
}
}
System.out.println(n%2==1?arr[n][n/2+1]:Math.max(arr[n][n/2],arr[n][n/2+1]));
}
}
試題I：子串分值和
思路：n太大了，，，目前只摸索出60分的代碼，當n超過兩萬時就會超時，，，
import java.util.Scanner;
public class 子串分值和 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s=scanner.nextLine();
char []arr=s.toCharArray();
int ans=0;
long time1=System.currentTimeMillis();
for (int i = 0; i < arr.length; i++) {
int cnt=0;
boolean [] key=new boolean[26];
for (int j = i; j < arr.length; j++) {
if(!key[arr[j]-'a'])
{
key[arr[j]-'a']=true;
cnt++;
}
//System.out.println(cnt);
ans+=cnt;
}
}
long time2=System.currentTimeMillis();
System.out.println(ans);
System.out.println(time2-time1);
}
}
試題J：裝飾珠
思路：完全不會，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/264477.html
標籤：java
下一篇：JAVA技術入門