蓝桥杯备考

先浅学一遍数据结构，不会拉倒，找点简单题练练语法基础

然后边学边刷二分查找和双指针

递归和暴力，边学边刷

学习贪心，练个几十道

再去过下数据结构

开始算法:搜索，动态规划，

搜索很重要，深度优先可骗分

然后动态规划，挺难，多学多练看造化

一共10道题,填空题,只需要答案 代码题:提交代码 从易到难

一等奖:10% 二等奖20% 三等奖30%

刷题:洛谷 力扣(偏面试) 真题

暴力搜索

深度优先搜索重要

动态规划

前三道题中通常涉及到循环.

• for循环:可以在题目中找到循环次数
• while:只知道循环条件

考察循环时,还会涉及到集合,字符串等知识点的应用.例如

• 对字符串一般考察常用函数.字符串转字符数组,判断结尾等
• 集合一般考察集合特性: list:有序可重复 set:无序不可重复 map:键值对key-value.

一.必备知识复习

1.集合

2.栈

Stack<> stack = new Stack<>();

先进后出

3.队列

Queue<引用数据类型>queue = new LinkedList<>();

先进先出

4.排序库的使用

5.字符串

//1.将数字转成字符串
String j = i+"";//2.将字符串转成字符串数组
char[] chars = j.toCharArray();//3.对数组进行排序
Arrays.sort(数组);//4.逆序打印
for (int i = chars.length-1; i >=0; i--) {System.out.print(chars[i]);;
}//5.全部转大小写
toLowerCase()/toUpperCase()//6.equals方法
//即使两个字符串对象位于不同的内存位置，只要它们包含相同的字符序列，equals方法也会返回true。//7.使用StringBuffer和StringBuilder的append方法可以轻松的拼接字符串如果字符串存在
大量修改操作,并且单线程,使用StringBuilder 多线程,使用StringBuffer,
可以用到其中的reverse()函数对字符串进行翻转//8. 1byte=8bit   1KB=1024byte   1MB=1024KB  1GB=1024MB//9.通过实现Comparator接口进行自定义排序
Arrays.sort(arr,new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return (o2+o1).compareTo(o1+o2);}
});//10.charAt(i)返回索引为i的字符//11.String类的contains方法它用于检测一个字符串内是否包含
//另一个特定的字符序列（或称为子字符串）//12.常用函数 绝对值函数Math.abs();    整型转字符串 Integer.toString();字符串转整型 Integer.parseInt();//StringBuilder的delete方法 
//作用：删除字符串下标为0的元素（注意此时的0下标的元素改了为下标为1的字符）//主要用到的方法 StringBuilder的append用来拼接到字符串末尾  
//String.charAt(i)取走第i个元素
//sb.indexOf:返回指定字符串第一次出现在字符串中的索引 若没有则返回-1或自己设置的默认值
//sb.subString(index)截取该下标后的字符串
//String.vauleOf()将()转为字符串System.out.printf("%.2f",a);//输出两位小数

1.确定字符串是否是另一个的排列

package com.study.Str;import java.util.Arrays;
import java.util.Scanner;/*
实现一个算法来识别一个字符串 str2str2 是否是另一个字符串 str1str1 的排列。
排列的解释如下：如果将 str1str1 的字符拆分开，重新排列后再拼接起来，
能够得到 str2str2 ，那么就说字符串 str2str2 是字符串 str1str1 的排列。
（不忽略大小写）
如果 str2str2 字符串是 str1str1 字符串的排列，则输出 YES；
如果 str2str2 字符串不是 str1str1 字符串的排列，则输出 NO；*/
public class str2 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//思路 将str1和str2字符串转换为字符数组 然后进行排序 排序后重新赋值给字符串 然后调用equals方法进行比较char[] s1 = scan.next().toCharArray();char[] s2 = scan.next().toCharArray();Arrays.sort(s1);Arrays.sort(s2);String str1 = new String(s1);//传入字符数组也可以创建字符串String str2 = new String(s2);//使用equals方法//即使两个字符串对象位于不同的内存位置，只要它们包含相同的字符序列，equals方法也会返回true。System.out.println(str1.equals(str2)==true?"YES":"NO");scan.close();}
}

2.压缩字符串*

package com.study.Str;import java.util.Arrays;
import java.util.Scanner;//实现一个算法来压缩一个字符串。压缩的要求如下：//需要判断压缩能不能节省空间，仅在压缩后字符串比原字符串长度更短时进行压缩。//压缩的格式是将连续相同字符替换为字符 + 数字形式，例如 "AAABCCDDDD" 变为 "A3BC2D4"。
public class str3 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//思路:先将字符串转换成字符数组进行排序 利用计数器进行计数 利用StringBuilder来记录返回的数组String str = scan.next();char[] s = str.toCharArray();Arrays.sort(s);StringBuilder sb =  new StringBuilder();int i=0;int count=1;for(i=0;i<s.length-1;i++) {//length-1防止越界if(s[i]==s[i+1]) {count++;continue;//继续循环 不执行下面的语句}if(count==1) {sb.append(s[i]);}else {sb.append(s[i]).append(count);}//重置计数器count=1;}//添加最后一个元素 出循环时i=length-1即最后一个元素if(count==1) {sb.append(s[i]);}else {sb.append(s[i]).append(count);}if(sb.length()<s.length) {System.out.println(sb);}else {System.out.println("NO");}scan.close();}
}

3.拼数-自定义排序

package com.study.Str;import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;public class str4 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//给定  n 个正整数 a1,a2,…,ana1,a2,…,an，你可以将它们任意排序。//现要将这 n个数字连接成一排，即令相邻数字收尾相接，组成一个数。//问，这个数最大可以是多少。//思路:将数组最左边的一位进行排序 需要用到内部类自定义排序规则//将两个字符串拼接比较排序int n = scan.nextInt();String[] arr = new String[n];for(int i=0;i<n;i++) {arr[i]=scan.next();}Arrays.sort(arr,new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return (o2+o1).compareTo(o1+o2);}});//连接所有字符串StringBuilder sb = new StringBuilder();for(int i=0;i<n;i++) {sb.append(arr[i]);}System.out.println(sb);scan.close();}
}

4.最长回文子串-中心扩展法

public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//思路 通过遍历字符 中心扩散法  String s = scan.next();s=longestPalindrome(s);System.out.println(s.length());scan.close();}public static String longestPalindrome(String s) {//回文长度int maxLen=0;//回文起始位置索引int maxLenS=0;//遍历字符串for(int i=0;i<s.length();i++) {//定义左右指针和该位置的回文长度int left=i-1;int right=i+1;int len=1;//最短回文长度为1//防止越界 以字符数组中心点情况为例 abccbybccaa//开始 i指向y 当i-1等于i时 len++ 指针左移再进行比较(循环+条件) 向右同理while(left>=0&& s.charAt(left)==s.charAt(i)) {left--;len++;}while(right<s.length()&& s.charAt(right)==s.charAt(i)) {right++;len++;}while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)) {left--;right++;len+=2;}//记录最大回文长度 和回文起始位置if(len>maxLen) {maxLen=len;maxLenS=left;}}return s.substring(maxLenS+1, maxLenS+1+maxLen);}

5.反转字符串中的字符-倒序遍历

package com.study.Str;import java.util.Arrays;
import java.util.Scanner;//实现一个算法来实现反转字符数组的功能。反转的要求如下：
//1. 将字符数组的字符进行反转，例如 ['b', ' ', 'a', 'r'] 变成 ['r', 'a', ' ', 'b']。
//2. 将字符数组替换为反转后的数组。
public class str6 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//思路 倒序遍历即可//nextLine()可以读取一整行的内容包括空格char[] arr1 = scan.nextLine().toCharArray();char[] arr2 = new char[arr1.length];for(int i=0;i<arr1.length;i++) {arr2[arr2.length-i-1]=arr1[i];}for(int i=0;i<arr2.length;i++) {System.out.print(arr2[i]);}scan.close();}
}

6.数字反转

package com.study.Str;import java.util.Arrays;
import java.util.Scanner;public class str8 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//转成字符串 然后利用字符串翻转来处理//注意正负数分别处理 利用Math.abs()绝对值函数来处理 int num = scan.nextInt();int num1 = Math.abs(num);String s = Integer.toString(num1);StringBuilder sb = new StringBuilder(s).reverse();int a = Integer.parseInt(sb.toString());if(num<0) {System.out.println(-a);}else {System.out.println(a);}scan.close();}
}

6.时空复杂度分析

计算机1s可以计算10的8次方,要控制代码的时间复杂度在10^8以内

二.算法

1.模拟

用代码模拟题意

package com.study.moni;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();long ans = 0;for(int i=1;i<=n;i++) {String s = i+"";if(s.contains("2")||s.contains("0")||s.contains("1")||s.contains("9")) {ans+=i;}}System.out.println(ans);}
}

2.前缀和

前缀和就是数组中从第一个元素到当前元素之间所有元素的累加和。

即

前缀和的运用

推导公式: sum[i]=sum[i-1]+a[i-1]

sum[L,R] = sum[R]-sum[L-1]

例题1

package com.study.moni;import java.util.Scanner;public class Main1 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//思路 分析出整个式子的规律 sum为a1+...+an//提公因式可以得:S=a1(sum-a1)+a2(sum-a1-a2)+...int n = scan.nextInt();int[] a = new int[n];long sum=0,res=0;for(int i=0;i<n;i++) {a[i]=scan.nextInt();sum+=a[i];}for(int i=0;i<n;i++) {sum-=a[i];res+=sum*a[i];}System.out.println(res );}
}

例题2**97 k倍区间

package com.study.moni;import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class Main1 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//思路 这是一个前缀和问题 两边区间的和为k的倍数即符合题意//前缀和计算公式:sum[i]=sum[i-1]+arr[i]//前缀和中有一个推导公式适用于本题:  sum[L,R] = sum[R]-sum[L-1]     //即需要找出区间有多少个(sum[R]-sum[L-1])%k==0即是符合条件的//通过双重for循环可以简单找出来/** for(int i=1;i<=n;i++){* 		for(int j=1;j<=i;j++){* 			if((s[i]-s[j-1])%k==0&&(s[i]-s[j-1])>0){*				count++;*			}*		}*}*但双重循环会超时 需要优化掉一个循环 将判断公式变形->s[R]%k==s[L-1]%k*即对前缀和取模后 结果相等的两个前缀和可以构成一个k倍区间*意思就是说对于给定K,如果有任意两个前缀和%K,的结果相等，这时的L和R就能构成一个k倍区间*我们1.使用一个哈希表来存储每个前缀和对 k 取模后的结果及其出现的次数。*2.在遍历数组计算前缀和时，检查当前前缀和对 k 取模后的结果是否在哈希表中已经存在。*3.更新哈希表中前缀和对 k 取模后的结果出现的次数。*/int n=scan.nextInt();int k=scan.nextInt();long count=0;int[] arr = new int[n];long sum=0;Map<Integer,Integer> map = new HashMap<>();map.put(0,1);//初始化 表名前缀和为0的情况有一次for(int i=0;i<n;i++) {arr[i]=scan.nextInt();sum+=arr[i];//计算当前sum%k的结果//还得处理负数情况 int mod = (int)((sum%k+k)%k);//检查之前是否存在 存在就将之前值加上去if(map.containsKey(mod)) {count+=map.get(mod);}//更新哈希表中当前前缀和对k取模后出现的次数	//getOrDefault方法是返回mod这个key对应的值,不存在这个key则返回第二个参数作为默认值map.put(mod,map.getOrDefault(mod, 0)+1);}System.out.println(count);scan.close();//1 1 2 3 4 5//1 2 4 7 11 16}
}

例题3

package com.study.moni;import java.util.Scanner;public class Main2 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] arr = new int[n];for(int i=0;i<n;i++) {arr[i]=scan.nextInt();}int[] sum = new int[n];for(int i=0;i<n;i++)sum[i+1]=sum[i]+arr[i];int  m = scan.nextInt();for(int i=0;i<m;i++) {int l = scan.nextInt()-1;//题目是1-n 减一变为0-nint r = scan.nextInt()-1;System.out.println(sum[r+1]-sum[l]);}}
}

3.二分查找

版本1

将区间[l,r]划分成[l,mid]和[mid+1,r] 其更新操作是r=mid,l=mid+1 计算mid时不需要+1

模板1
int[] arr = {1,2,3,4,5,6};
int left=0,right=arr.length-1;
int k=3;
while(left<right){//left==right退出循环int mid = (left+right)/2;if(arr[mid]>=k)right=mid;else left=mid+1;
}
//数组的区间[0,left-1]满足arr[i]<k
[left,n-1]满足arr[i]>=k

版本2

将区间[l,r]划分成[l,mid-1]和[mid,r]时 更新操作是

模板2
int[] arr = {1,2,3,4,5,6};
int left=0,right=arr.length-1;
int k=3;
while(left<right){//left==right退出循环int mid = (left+right+1)/2;if(arr[mid]>k)right=mid-1;else left=mid;
}
//数组的区间[0,left]满足arr[i]<k
[left+1,n-1]满足arr[i]>11111k

例题1-172递增三元组

import java.util.Scanner;
import java.util.Arrays;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//思路 通过二分查找法 找出循环中满足Ai<Bj<Ck的int n =scan.nextInt();int[] a = new int[n];int[] b = new int[n];int[] c = new int[n];for(int i=0;i<n;i++)a[i]=scan.nextInt();for(int i=0;i<n;i++)b[i]=scan.nextInt();for(int i=0;i<n;i++)c[i]=scan.nextInt();Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);int[] B =new int[n];for(int i=0;i<n;i++) {int left=0,right=n-1;while(left<right) {//left==right退出循环int mid = (left+right)/2;if(c[mid]>b[i]) {right=mid;}else {left = mid+1;}}//通过二分查找找出第一个大于b[i]的索引leftif(c[left]>b[i]) {B[i]=n-left;//记录此次循环中满足Ci>Bi的个数=left+n-1+1}}//计算B数组的前缀和long[] sum = new long[n+1];for(int i=1;i<=n;i++) {sum[i]=sum[i-1]+B[i-1];}long ans = 0;//同理找满足Bj>Ai的for(int i=0;i<n;i++) {int left=0,right=n-1;while(left<right) {int mid = (left+right)/2;if(b[mid]>a[i]) {right=mid;}else {left = mid+1;}}if(b[left]>a[i]) {//进来的都是满足条件的ans+=sum[n]-sum[left];//>left索引的都符合即可得到符合条件的个数}}System.out.println(ans);scan.close();}
}

例题2- 99分巧克力

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//思路分析: 通过二分查找找出满足题意的最大边长(类似这种最大问题一般涉及到二分)//问题的解具有单调性 找出这个边长的临界值//输入int n=scan.nextInt();int k=scan.nextInt();int[] h=new int[n];	int[] w=new int[n];	for(int i=0;i<n;i++) {h[i]=scan.nextInt();w[i]=scan.nextInt();}//确定二分查找的上下界int left=1,right=100000;while(left<right) {int mid=(left+right+1)/2;if(check(mid,h,w,k))//如果能切出k块正方形则尝试更大的边长left=mid;else //不能则尝试更小的边长right=mid-1;}System.out.println(left);scan.close();}//判断当前mid是否满足条件 能否切割出k个正方形public static boolean check(int mid,int[]h,int[]w,int k) {int ans=0;for(int i=0;i<h.length;i++) {//属于整除法,分别计算矩形的高度和宽度能够容纳多少个边长为 mid 的正方形的“行”和“列”，//然后将这两个数量相乘得到总的正方形数量,（只考虑完整的正方形）int res=(h[i]/mid)*(w[i]/mid);ans+=res;}return ans>=k;}
}

浮点二分

二分的二段性,集合中的元素有存在分界线,给定条件可以将集合中的元素分成两部分,一部分满足条件,一部分不满足

例题3 -浮点二分模板题

package com.study.erFen;import java.util.Scanner;//浮点二分
public class erFen1 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int k = scan.nextInt();double[] a = new double[n];for(int i=0;i<n;i++)a[i]=scan.nextDouble();double left=0,right=1e9;while(right-left>1e-2) {double mid = (left+right)/2;if(check(a,mid,k))right=mid;else left=mid;}System.out.println(left);}public static boolean check(double[]a,double mid,double k) {int res=0;for(double x:a) {res+=(int)(x/mid);}return res<k;}
}

4.动态规划

例题1-程序员爬楼梯

package com.study.dp;import java.util.Scanner;public class dp1 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//1.考虑最后一步由前面哪些状态转移来,推出转移方程//N可以由n-1 和n-3得来dp[i]=dp[i-1]+dp[i-3];//2.考虑当前状态与哪些状态有关 定义几维数组来表示当前状态//只和n有关 一维数组即可//3.计算时间复杂度 判断是否需要优化int n=scan.nextInt();if(n<3) {System.out.println(1);}else {int[] dp = new int[n+1];dp[1]=1;dp[2]=1;dp[3]=2;for(int i=4;i<=n;i++) dp[i]=dp[i-1]+dp[i-3];System.out.println(dp[n]);}}
}

例题2-最长上升子序列

package com.study.dp;import java.util.Scanner;public class dp2 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//以每个元素为结尾的最长上升子序列的长度作为状态//[1, 7, 3, 5, 9, 4, 8]//dp[0]=1 dp[1]=2(1-7) dp[2]=2(1-3) dp[3]=3(1-3-5) dp[4]=4(1-3-5-9)//对于每个i都需要查找前面比他小的元素j 然后找到最大的dp[j]+1作为dp[i]的值//为什么是dp[j]+1:找出的子序列还需要加上arr[i] (因为是严格满足arr[j]<arr[i]的)//由此可以得出 dp[i]=max(dp[j]+1)]int n = scan.nextInt();int[] arr = new int[n];for(int i=0;i<n;i++)arr[i]=scan.nextInt();int[] dp = new int[n];int maxLen=1;//最小为1dp[0]=1;for(int i=0;i<n;i++) {for(int j=0;j<i;j++) {if(arr[j]<arr[i]) {dp[i]=Math.max(dp[i], dp[j]+1);}}//每次循环结束更新一下maxLen的值maxLen=Math.max(maxLen, dp[i]);}System.out.println(maxLen);}
}

例题3-3512接龙数列*****

package com.study.dp;import java.util.Scanner;public class dp3 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//思路:找出最少删除多少个数使得剩下的数为接龙数列//找到状态的定义和转移  //dp数组记录以每个数字结尾的最长子序列长度 遍历每个数 计算其首尾数字更新对应的dp值//总长度-最长子序列长度即最少次数int n = scan.nextInt();int[] nums=new int[n];for(int i=0;i<n;i++)nums[i]=scan.nextInt();int[] dp = new int[10]; // dp[d] 表示以数字d结尾的最长接龙子序列的长度int maxLength = 0;for (int num : nums) {int h = getFirstDigit(num); // 当前元素的首位数字int t = Math.abs(num % 10);  // 当前元素的末位数字（处理负数情况）int maxPrev = 0;// 找出所有以h结尾的子序列中的最长长度for (int d = 0; d < 10; d++) {if (d == h) {maxPrev = Math.max(maxPrev, dp[d]);}}// 更新以t结尾的最长子序列长度dp[t] = Math.max(dp[t], maxPrev + 1);// 更新全局最长长度maxLength = Math.max(maxLength, dp[t]);}System.out.println(nums.length - maxLength);//在此输入您的代码...scan.close();}// 获取数字的首位数字（处理负数情况）private static int getFirstDigit(int num) {num = Math.abs(num);while (num >= 10) {num /= 10;}return num;}
}

例题4-4985蜗牛

5.最大公约数和最小公倍数(gcd,lcm)

例题1-信息与未来

package com.study.Math;import java.util.Scanner;public class math2 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int x = scan.nextInt();int y = scan.nextInt();int z = scan.nextInt();int d=gcd(x,y);d=gcd(d,z);System.out.println(d);}public static int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
}

例题2

package com.study.Math;import java.util.Arrays;
import java.util.Scanner;public class math1 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] a=new int[n];for(int i=0;i<n;i++)a[i]=scan.nextInt();Arrays.sort(a);int d=a[1]-a[0];for(int i=2;i<n;i++)d=gcd(d,a[i]-a[i-1]);if(d==0){System.out.println(n);}else{long res=1;for(int i=1;i<n;i++){res+=(a[i]-a[i-1])/d;}System.out.println(res);}}public static int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
}

6.暴力搜索

package com.study.moni;import java.util.Scanner;
//n层就n层for循环 即暴力
public class Main5 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();for(int i=1;i<=3;i++) {for(int j=1;j<=3;j++) {if(j==i) continue;for(int k=1;k<=3;k++) {if(k==i||k==j) continue;System.out.println(i+" "+j+" "+k);}}}}
}

7.进制转换

1.调用Integer.toString(x,y)方法,将x(十进制数)转换成y进制(字符串)

2.自己写

例题1

package com.study.Math;import java.util.Scanner;public class Math3 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int x = scan.nextInt();char[] c = scan.next().toCharArray();int sum=0,k=1;for(int i=c.length-1;i>=0;i--) {//逆序遍历 从最后一位开始处理int res=0;if(c[i]>='A'&&c[i]<='Z')//超过十进制res=c[i]-'A'+10;//表示是十几进制else res=c[i]-'0';//转换成对应的数字sum+=res*k;//当前位的数值*x^n次方 k*=x;//二进制转十进制如101=1*2^2+0*2^1+1*2^0//此处同理 }System.out.println(sum);}
}

例题2

package com.study.Math;import java.util.Scanner;public class math4 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int x = scan.nextInt();String str = Integer.toString(n,x).toUpperCase();System.out.println(str);}
}

8.常用api

 

9.DFS(深度优先搜索)

深度优先遍历（DFS）
核心思想：尽可能深地探索图的分支，直到没有未访问的相邻节点，再回溯继续探索其他分支。

• 实现方式：用栈（或递归）保存待访问节点。
• 特点：适合路径查找（如迷宫）、回溯问题，空间复杂度较低（仅需存储当前路径）。
• 比喻：像“一条路走到黑”，深入到底再折返。

例题1-全排列

1<=n<=9

package com.study.DFS;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class dfs1 {static List<List<Integer>> list = new ArrayList<>();public static void main(String[] args) {Scanner scan = new Scanner(System.in);//为什么要用dfs:全排列需生成所有可能的元素排列组合，//DFS通过回溯法系统地探索所有决策路径，确保每个分支都被完整遍历。int n = scan.nextInt();//全排列的元素个数int[] v = new int[n+1];//标记是节点是否访问过List<Integer> t= new ArrayList<>();//集合dfs(n,v,t);//调用深度优先遍历算法for(int i=0;i<list.size();i++) {for(int j=0;j<list.get(i).size();j++) {System.out.print("     "+list.get(i).get(j));}System.out.println();}}public static void dfs(int n,int[]v,List<Integer>t) {//如果集合t的长度==排列数n 说明已经形成了完整的排列 将其添加到大集合中if(t.size()==n) {list.add(new ArrayList<>(t));return ;//递归出口}//否则遍历所有可能的数字(1-n)//如果i没有被标记为已使用（v[i]==0），//就标记它为已使用，添加到当前排列t中，然后递归调用dfsfor(int i=1;i<=n;i++) {if(v[i]==1)continue;v[i]=1;t.add(i);//标记该路径已尝试dfs(n,v,t);v[i]=0;//将当前选择的数字标记为"未使用"，允许上层递归重新选择该数字t.remove(t.size()-1);//从当前路径中移除最后添加的数字，使路径回退到上一层状态/** 想象你在迷宫中探索：v[i]=1 + t.add(i)：你走进一条死胡同，标记该路径为已尝试。v[i]=0 + t.remove()：发现死胡同后原路返回，清除标记，尝试其他岔路。*/}}
}

图的搜索

例题1-264危险系数

package com.study.DFS;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class dfs2 {//站点即节点数量 通道数即边数量//m行是初始化边 如 1-3 2-3 3-4 3-5 4-5 5-6static List<Integer>[] list;//list是一个数组的列表，用于存储每个节点的邻接节点。static boolean[] visited; // 数组标记访问状态static boolean flag = false;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();list = new List[n + 1];// 为每个节点初始化一个空的邻接列表//每个节点的邻接列表是邻接表的一部分，而不是独立的邻接表。for (int i = 1; i <= n; i++) {list[i] = new ArrayList<>();}//无向图 初始化邻接表//遍历所有的边，将邻接节点添加到相应的列表中for (int i = 0; i < m; i++) {int x = scan.nextInt();int y = scan.nextInt();list[x].add(y);// 将 y 添加到 x 的邻接列表中list[y].add(x);// 将 x 添加到 y 的邻接列表中}int x = scan.nextInt();int y = scan.nextInt();visited = new boolean[n + 1]; // 初始化访问数组// 初始连通性检查flag = false;dfs(x, y, x, 0);//x y是否连通if (!flag) {System.out.println(-1);} else {int ans = 0;for (int i = 1; i <= n; i++) {//遍历所有节点 跳过x y 孤立点if (i == x || i == y || list[i].isEmpty()) continue;// 每次测试前重置访问标记 for (int j = 1; j <= n; j++) visited[j] = false;flag = false;dfs(x, y, x, i);//传入i作为blockif (!flag) ans++;//若移除 i 后 x 和 y 不连通，危险系数ans 加一}System.out.println(ans);}}/*** 递归的搜索是否存在从起点到终点的路径 同时排除被屏蔽的节点* @param s 起点* @param t 终点* @param u 当前节点* @param block 需要屏蔽的节点*/public static void dfs(int s, int t, int u, int block) {if (u == t) {flag = true;return;//递归出口 已经找到终点}visited[u] = true; // 标记当前节点已访问for (int v : list[u]) {//遍历当前节点的邻接节点if (!visited[v] && v != block) { // 未被访问过且遍历的邻接节点不是阻塞的节点dfs(s, t, v, block);//递归调用dfs以v为当前节点 继续搜索路径if (flag) return; // 找到后立即终止递归}}}
}

剪枝

例题

package com.study.dp;import java.util.Scanner;public class dp4 {static int n,k,ans=0;public static void main(String[] args) {Scanner scan = new Scanner(System.in);n=scan.nextInt();//数Nk=scan.nextInt();//要分K份dfs(1,0,0);System.out.println(ans);}/*** * @param last 上一份的值* @param sum 当前已分出的总和* @param cnt 已分的份数*/public static void dfs(int last,int sum,int cnt) {if(cnt==k) {if(sum==n) {//已分份数和已分总和等于k,n 计数器++ans++;}return;//递归终止条件}//未剪枝写法
//		for(int i=last;i<=n;i++) {
//			dfs(i,sum+i,cnt+1);
//		}//从last开始递增 确保大于上一份的值//剪枝条件 未分配的数 (sum-n)至少能分成k-cnt份 每份至少大于ifor(int i=last;sum+i*(k-cnt)<=n;i++) {//剪枝循环dfs(i,sum+i,cnt+1);}}
}

10.BFS(广度优先搜索)

广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。它的核心思想是从根节点开始，逐层访问邻近的节点，直到找到目标节点或遍历完所有节点。

通过队列实现,队列(先进先出)

例题

package com.study.BFS;import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class bfs1 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();char[][]c=new char[n][m];for(int i=0;i<n;i++)c[i]=scan.next().toCharArray();//一列一列的读int ans=0;for(int i=0;i<n;i++) {//遍历每个网格for(int j=0;j<m;j++) {if(c[i][j]!='0') {//是细胞就BFS一下bfs(i,j,c);ans++;}}}System.out.println(ans);}public static void bfs(int i,int j,char[][]c) {int n=c.length;//行数int m=c[0].length;//列数Queue<int[]>q=new LinkedList<>();//创建队列q.add(new int[] {i,j});//将初始坐标加入队列中int[][]dx= {{1,0},{-1,0},{0,1},{0,-1}};//定义方向数组while(!q.isEmpty()) {//终止条件:队列不为空int[]a=q.poll();//获取队列中第一个元素int x=a[0];//获得x坐标int y=a[1];//获得y坐标c[x][y]='0';//将当前节点设为已访问for(int k=0;k<4;k++) {//遍历四个方向，计算相邻节点的坐标x1和y1int x1=x+dx[k][0];int y1=y+dx[k][1];if(x1<0||x1>=n||y1<0||y1>=m||c[x1][y1]=='0')//未越界且未被访问continue;q.add(new int[] {x1,y1});//将合法未访问节点加入队列}}}
}

刷题记录

1.504-单词分析***

模拟/枚举

package com.study.BL;import java.util.Scanner;//暴力
public class bl1 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//思路1:双重for暴力求解 只能通过70%的测试点/**char[] c = scan.next().toCharArray();char result=' ';int maxLen=0;for(int i=0;i<c.length;i++) {int max=0;char currentChar=c[i];for(int j=0;j<c.length;j++) {if(currentChar==c[j]) {max++;}}if(maxLen<max) {maxLen=max;result=currentChar;}}System.out.println(result);System.out.println(maxLen);*///思路2 利用数组来记录长度char[] c = scan.next().toCharArray();int[] counts = new int[26];for(char a:c) {counts[a-'a']++;}//一层循环找出数组中最大的值int max=0;char result=' ';for(int i=0;i<26;i++) {if(counts[i]>max) {max=counts[i];result = (char) ('a' + i);}}System.out.println(result);System.out.println(max);scan.close();}
}

2.19709-好数**

暴力/枚举/位处理

public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int num = scan.nextInt();int ans=0;for(int i=1;i<=num;i++) {ans+=method(i);}System.out.println(ans);scan.close();}public static int method(int n) {int count=0;int a=1;//记录当前是那位 首先是个位boolean flag=true;while(n!=0) {//对于个位数只用判断奇数位 但多位数需要每个位数都满足//正难则反去不满足的int t = n%10;//取出当前n的个位if(a%2==1){//奇数位if(t%2==0)flag=false;}else{//偶数位if(t%2==1)flag=false;}a++;n/=10;}if(flag) {return 1;}else {return 0;}}

3.1216-走迷宫***

bfs

package com.study.BFS;import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class bfs2 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//思路:采用二维数组来记录步数 和迷宫同样大小 但含义是到达该格子的步数int n = scan.nextInt();int m = scan.nextInt();int[][] grid = new int[n][m];for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {grid[i][j]=scan.nextInt();}}//读取出入口坐标 并转成0索引开头int x1 = scan.nextInt()-1;int y1 = scan.nextInt()-1;int x2 = scan.nextInt()-1;int y2 = scan.nextInt()-1;int[][]steps = new int[n][m];for(int[] a:steps) {Arrays.fill(a, -1);//初始化位-1 表示未访问}//创建队列Queue<int[]> q = new LinkedList<>();q.add(new int[]{x1,y1});//起点入队steps[x1][y1]=0;//起点步数为0int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};while(!q.isEmpty()) {int[] current = q.poll();int x = current[0];int y = current[1];//循环终止条件:找到出口后返回步数if(x==x2&&y==y2) {System.out.println(steps[x][y]);return;}//探索四个方向for(int[]dir:dirs) {int nx = x+dir[0];int ny = y+dir[1];//检查新坐标是否合法且未被访问if(nx>=0&&ny>=0&&nx<n&&ny<m&&grid[nx][ny]==1&&steps[nx][ny]==-1) {steps[nx][ny]=steps[x][y]+1;//更新步数q.add(new int[] {nx,ny}	);}}}System.out.println(-1);}
}

4.3447-七步诗***

dfs/bfs

package com.study.BFS;import java.util.Arrays;
import java.util.Scanner;public class bfs3 {static boolean visited[][];static int sum;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();char[][] c = new char[n][m];for(int i=0;i<n;i++) {c[i]=scan.next().toCharArray();}visited=new boolean[n][m];for(int i=0;i<n;i++) {Arrays.fill(visited[i], false);}sum=0;//遍历二维字符数组for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {if(c[i][j]=='S'&&!visited[i][j]) {dfs(i,j,c);}}}System.out.println(sum);}public static void dfs(int x,int y,char[][] c) {//定义二维数组 记录马儿飞的八个方向int[][] jump = {{2,-1},{2,1},{1,-2},{1,2},{-1,2},{-1,-2},{-2,-1},{-2,1}};//数据不能越界int n = visited.length;int m = visited[0].length;if(x<0||y<0||x>=n||y>=m)return;visited[x][y]=true;//标记为已访问if(c[x][y]=='b') {sum++;}//循环可以走的所有点 切判断点是否合法 且不能等于xfor(int i=0;i<8;i++) {int nx = x+jump[i][0];int ny = y+jump[i][1];if(nx>=0&&ny>=0&&nx<n&&ny<m&&c[nx][ny]!='x'&&!visited[nx][ny]) {//未越界 未被访问 不是湿地//判断下一个点是否满足dfs(nx,ny,c);}}}
}

package com.study.BFS;import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class bfs3 {static boolean visited[][];static int sum;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();char[][] c = new char[n][m];for(int i=0;i<n;i++) {c[i]=scan.next().toCharArray();}visited=new boolean[n][m];for(int i=0;i<n;i++) {Arrays.fill(visited[i], false);}sum=0;//使用队列进行bfs遍历Queue<int[]> q = new LinkedList<>();//找到起点并加入队列for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {if(c[i][j]=='S') {q.add(new int[] {i,j});visited[i][j]=true;//找到起点后立刻退出循环break;}}}//移动的8个方向int[][] jump = {{2,-1},{2,1},{1,-2},{1,2},{-1,2},{-1,-2},{-2,-1},{-2,1}};//bfswhile(!q.isEmpty()) {int[] current = q.poll();//取出来int x = current[0];int y = current[1];if(c[x][y]=='b') {sum++;}for(int[] dir:jump) {int nx = x+dir[0];int ny = y+dir[1];//检查新位置是否合法等if(nx>=0&&nx<n&&ny>=0&&ny<m&&c[nx][ny]!='x'&&!visited[nx][ny]) {visited[nx][ny]=true;q.add(new int[] {nx,ny});//放入}}}System.out.println(sum);}
}

5.502-成绩统计*

数学

package com.study.Math;import java.util.Scanner;public class math5 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//调用Math.round方法进行四舍五入int n = scan.nextInt();int a=0,b=0;//优秀 及格int c;for(int i=1;i<=n;i++) {c=scan.nextInt();if(c>=60)a++;if(c>=85)b++;}double passRate = (double)a/n*100;double excellentRate = (double)b/n*100;int pr = (int)Math.round(passRate);int er = (int)Math.round(excellentRate);System.out.println(pr+"%");System.out.println(er+"%");scan.close();}
}

6.498-回文日期(90)****

模拟 构造 回文

防超时

优化点说明：

1. 分离循环： 为两种日期类型分别设置循环，找到结果后立即终止。
2. 减少字符串转换： 在生成日期时直接操作字符串，避免重复转换。
3. 提前终止： 找到符合条件的日期后立即返回，减少不必要的循环。

package com.study.moni;import java.util.Scanner;public class Main6 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();// 寻找下一个回文日期for (int i = n + 1; i < 89991231; i++) {if (isLegalDate(i) && isHW(i)) {System.out.println(i);break;}}// 寻找下一个ABABBABA日期for (int i = n + 1; i < 89991231; i++) {if (isLegalDate(i) && isAB(i)) {System.out.println(i);break;}}scan.close();}public static boolean isHW(int n) {char[] c = Integer.toString(n).toCharArray();int left = 0, right = 7;while (left < 4) {if (c[left] != c[right]) return false;left++;right--;}return true;}public static boolean isAB(int n) {char[] c = Integer.toString(n).toCharArray();return c[0] == c[2] && c[0] == c[5] && c[0] == c[7] &&c[1] == c[3] && c[1] == c[4] && c[1] == c[6];}public static boolean isLegalDate(int n) {if(n<10000101||n>89991231)return false;String s = Integer.toString(n);int year = Integer.parseInt(s.substring(0, 4));int month = Integer.parseInt(s.substring(4, 6));int day = Integer.parseInt(s.substring(6, 8));if (month < 1 || month > 12) return false;int[] maxDays = {31,28,31,30,31,30,31,31,30,31,30,31};if (day < 1 || day > maxDays[month-1]) return false;return true;}
}

7.101拉马车***

模拟 字符串操作

package com.study.moni;import java.util.Scanner;public class Main7 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//题意:输入两副牌 直到有一方没牌可出游戏结束//出牌规则:从自己的纸牌队列的头部拿走一张，放到桌上，并且压在最上面一张纸牌上（如果有的话）//赢牌条件:所出牌k和牌桌上有K ,赢牌的一方继续出牌,可赢走包括包括//K在内的以及两k之间的纸牌都赢回来，放入自己牌的队尾(注意是翻转后拼接 需要用到reverse()方法)//注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。也就是说放入桌上的牌是可以直接通过append方法拼接的//思路:通过StringBuilder对字符串进行一系列操作//主要用到的方法 StringBuilder的append用来拼接到字符串末尾  //String.charAt(i)取走第i个元素//sb.indexOf:返回指定字符串第一次出现在字符串中的索引 若没有则返回-1或自己设置的默认值//sb.subString(index)截取该下标后的字符串//String.vauleOf()将()转为字符串StringBuilder a = new StringBuilder(scan.next());StringBuilder b = new StringBuilder(scan.next());//牌桌StringBuilder desk = new StringBuilder();boolean flag = true;//控制AB出牌 trueA出牌 falseb出牌while(a.length()>0&&b.length()>0) {char currentCard;//出的牌StringBuilder currentHand;//当前是谁的手牌if (flag) {if (a.length() == 0) break;currentCard = a.charAt(0);currentHand = a;} else {if (b.length() == 0) break;currentCard = b.charAt(0);currentHand = b;}// 先出牌到桌面desk.append(currentCard);currentHand.delete(0, 1);//检查赢牌条件//indexOf从位置0开始查找当前牌在桌面字符串中的位置int index = desk.indexOf(String.valueOf(currentCard));//判断的是当前牌是否是桌面上的唯一存在 desk.length() - 1是刚刚放入的if (index!= desk.length() - 1) {//索引位置不等于刚刚放入牌的索引位置 则说明有这个牌了已经//计算赢牌范围StringBuilder won = new StringBuilder(desk.substring(index));won.reverse();currentHand.append(won);desk.delete(index , desk.length());continue; // 继续由当前玩家出牌}// 切换玩家flag = !flag;}System.out.println(a.length()==0?b:a);scan.close();}
}

8.126交换瓶子*

模拟

public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n = scan.nextInt();int[] arr = new int[n+1];for(int i=1;i<=n;i++) {arr[i]=scan.nextInt();}int count=0;//编号不为i的就进行交换for(int i=1;i<=n;i++) {if(arr[i]!=i) {int j=1;for(j=i;j<=n;j++) {if(arr[j]==i) {//找到了编号i对应的数 把这个数和i交换break;}}int temp = arr[i];arr[i]=i;arr[j]=temp;count++;}}System.out.println(count);scan.close();}

9.130-移动距离***

bfs寻找最短路径

package com.study.moni;import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main9 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);// 读取输入int w = scan.nextInt();int m = scan.nextInt();int n = scan.nextInt();//思路:通过bfs来寻找最短路径 先要获取起点和终点坐标int[] start = getZuoBiao(m,w);int[] end = getZuoBiao(n,w);//bfs初始化int[][]dirs = {{1,0},{-1,0},{0,1},{0,-1}};boolean[][] visited = new boolean[10000][w];Queue<int[]> q = new LinkedList<>();//传入三个参数 坐标和移动距离//传入起点visited[start[0]][start[1]]=true;q.add(new int[] {start[0],start[1],0});//bfswhile(!q.isEmpty()) {int[] current = q.poll();int x = current[0];int y = current[1];int dis = current[2];//四个方向进行遍历for(int[]dir:dirs) {int nx = x+dir[0];int ny = y+dir[1];//检查新坐标是否合法if (nx >= 0 && ny >= 0 && nx < 10000 && ny < w && !visited[nx][ny]) {//找到终点结束循环if(nx==end[0]&&ny==end[1]) {System.out.println(dis+1);scan.close();return;}//未到终点更新状态继续找q.add(new int[] {nx,ny,dis+1});visited[nx][ny]=true;}}}}public static int[] getZuoBiao(int n,int width) {//计算在第几行 索引从0开始int row = (n-1)/width;//计算行内位置 余数即从左或从右的第几个数012...int r = (n-1)%width;int c;if(row%2==0) {//奇数行 正序c=r;}else {//偶数行 逆序 如左边第2个数 实际上是右边第width-r-1个数123456c=width-r-1;}return new int[] {row,c};}
}

10.145数位递增的数*

模拟 位分离

package com.study.moni;import java.util.Scanner;public class Main10 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n =scan.nextInt();int count=0;for(int i=1;i<=n;i++){if(isDZ(i)){count++;
//	                System.out.println(i);}}System.out.println(count);scan.close();}public static boolean isDZ(int n){if(n<10) {return true;}int temp=0;//记录上一次的位数字while(n!=0){//12int t = n%10;//2if((t>temp&&temp!=0)||t==0){//到个位不比较return false;}temp = t;//temp=2n/=10;//1}return true;}
}

11.146三元数组中心问题**

暴力

package com.study.BL;import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;public class bl3 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//直接暴力 无需多言int n = scan.nextInt();int[] arr = new int[n];for(int i=0;i<n;i++){arr[i]=scan.nextInt();}//利用set集合来存储符合条件的j(中心)防止重复Set<Integer> s = new HashSet<>();for(int i=0;i<n-2;i++){//-2是预留jkfor(int j=i+1;j<n-1;j++){if(arr[j]>arr[i]){//满足左边才继续循环for(int k=j+1;k<n;k++){if(arr[k]>arr[j]){s.add(j);break;//找到了立即结束循环 优化性能}}}}}System.out.println(s.size());scan.close();}
}

12.148音节判断

模拟

public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//顺序:辅元辅元 //满足上述条件 从1(索引)开始判断 辅音跳过 char[] a = scan.next().toCharArray();//利用两个Boolean类型的值来控制判断是元音还是辅音boolean f1 = true,f2 = true;int m=0;//记录符合条件的次数for(int i=0;i<a.length;i++) {if((a[i]!='a' && a[i]!='e' && a[i]!='i' && a[i]!='o' && a[i]!='u')&&f1) {m++;f1=false;f2=true;}if((a[i] == 'a' || a[i] == 'e' || a[i] == 'i' || a[i] == 'o' || a[i] == 'u') && f2) {m++;f2 = false;f1=true;}}System.out.println(m==4?"yes":"no");scan.close();}

13.149-长草***

bfs

package com.study.BFS;import java.util.*;public class bfs4 {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();char[][] grid = new char[n][m];for(int i=0; i<n; i++) {grid[i] = scan.next().toCharArray();}int k = scan.nextInt();int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};for(int steps = 0; steps < k; steps++) {boolean[][] visited = new boolean[n][m];Queue<int[]> queue = new LinkedList<>();// 每月先收集当前所有草地位置for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {if(grid[i][j] == 'g' && !visited[i][j]) {queue.add(new int[]{i, j});visited[i][j] = true;}}}// 执行BFS扩散while(!queue.isEmpty()) {int[] current = queue.poll();for(int[] dir : dirs) {int nx = current[0] + dir[0];int ny = current[1] + dir[1];if(nx >=0 && ny >=0 && nx < n && ny < m && !visited[nx][ny] && grid[nx][ny] != 'g') {grid[nx][ny] = 'g';visited[nx][ny] = true;//关键点就是每月只对g点进行一轮扩散 所以此处不需要再从新添加队列了
//                        queue.add(new int[]{nx, ny});}}}}// 输出结果for(int i=0; i<n; i++) {System.out.println(new String(grid[i]));}scan.close();}
}

14.1065寻找2020**

模拟

package com.study.BL;import java.util.Scanner;public class bl4 {static int count=0;public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...直接暴力试一试 虽然多 但行列应该不超过500char[][] c = new char[300][300];for(int i=0;i<c.length;i++) {c[i]=scan.next().toCharArray();}for(int i=0;i<c.length;i++) {for(int j=0;j<c.length;j++) {is2020(i,j,c);}}System.out.println(count);}//进行判断public static void is2020(int i,int j,char[][]c) {if(i+3<c.length) {StringBuilder sb = new StringBuilder();sb.append(c[i][j]);sb.append(c[i+1][j]);sb.append(c[i+2][j]);sb.append(c[i+3][j]);if(sb.toString().equals("2020")) {count++;}}if(j+3<c.length) {StringBuilder sb = new StringBuilder();sb.append(c[i][j]);sb.append(c[i][j+1]);sb.append(c[i][j+2]);sb.append(c[i][j+3]);if(sb.toString().equals("2020")) {count++;}}if(j+3<c.length&&i+3<c.length) {StringBuilder sb = new StringBuilder();sb.append(c[i][j]);sb.append(c[i+1][j+1]);sb.append(c[i+2][j+2]);sb.append(c[i+3][j+3]);if(sb.toString().equals("2020")) {count++;}}}
}

15.19699类斐波那契循环数

暴力 构造 枚举

package com.study.BFS;public class bfs5 {public static void main(String[] args) {//在此输入您的代码...//猜测最大的类斐波那契数在1000000-9999999之间for(int i=9999999;i>=5000000;i--){if(isFeiBo(i)){System.out.println(i);break;}}}public static boolean isFeiBo(int n){//利用数组来存储数列 前七位是该数的每一位//后面要对n进行处理 先记录n的值int m =n;int[] a = new int[50];for(int i=6;i>=0;i--){a[i]=n%10;n/=10;}int k=0;int sum=0;//超过n后还没有值等于n说明不是类斐波那契数//a8=a1+...+a7 防止数组越界while(sum<m&&k+7<50){a[k+7]=a[k]+a[k+1]+a[k+2]+a[k+3]+a[k+4]+a[k+5]+a[k+6];sum=a[k+7];k++;if(sum==m){return true;}} return false;}
}

16.19732分布式队列

模拟

public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//本题并没有涉及到打印队列中的元素 只涉及到个数可用一个n大小的数组来记录个数int n = scan.nextInt();int[] count = new int[n];while(scan.hasNext()) {String s = scan.next();if(s.equals("add")) {//添加操作int x = scan.nextInt();count[0]++;//主节点}else if(s.equals("sync")) {//同步操作 元素添加到主节点后，需要同步到所有的副节点后int x = scan.nextInt();//副节点会从主节点中同步下一个自己缺失的元素
//        		count[x]++;同步一次 该队列的元素个数+1,但不可能超过主节点的元素数count[x]=Math.min(count[x]+1,count[0]);}else {//查询操作//查看分布式队列中有多少个元素可见 //所有节点都有这个元素这个元素才算可见 故即找出队列数组中的最小值int min = count[0];for(int i=1;i<n;i++) {if(count[i]<min) {min=count[i];}}System.out.println(min);}}scan.close();}

17.19724食堂

贪心

贪心的核心优先级：

1. 满桌优先 首先一定是让桌子都塞满人，这样利用率才能最大化。
2. 小桌优先 先把人放到小桌中，因为小桌（4人桌）的人数组合搭配不够灵活，大桌（6人桌）可以有更多中组合搭配。
3. 人多优先 寝室人多的先安置，因为人多不灵活，如果后面不能安置了，那么会损失很多人，利用率就下降了。
4. 空少优先 当一个桌子不得不空出位置时，尽量少空出位置。(空出位置数相同时,优先排6人桌的，因为人相对于排4人桌更多)

public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...//要尽可能空桌少int q = scan.nextInt();while(q!=0){q--;int a2 = scan.nextInt();int a3 = scan.nextInt();int a4 = scan.nextInt();int b4 = scan.nextInt();int b6 = scan.nextInt();//四人寝四人坐int sum=0;//满座匹配4人寝坐4人桌while(b4>0&&a4>=1) {b4--;a4--;sum+=4;}//满座匹配2x2人寝坐4人桌while(b4>0&&a2>=2) {b4--;a2-=2;sum+=4;}//满座匹配2+4人寝坐6人桌while(b6>0&&a4>=1&&a2>=1) {b6--;a4--;a2--;sum+=6;}//满座匹配2x3人寝坐6人桌while(b6>0&&a3>=2) {b6--;a3-=2;sum+=6;}//满座匹配3x2人寝坐6人桌while(b6>0&&a2>=3) {b6--;a2-=3;sum+=6;}//空1座匹配2+3人寝坐6人桌while(b6>0&&a2>=1&&a3>=1) {b6--;a2--;a3--;sum+=5;}//空1座匹配3人寝坐4人桌while(b4>0&&a3>0) {b4--;a3--;sum+=3;}//空2座匹配2x2人寝坐6人桌while(b6>0&&a2>=2) {b6--;a2-=2;sum+=4;}//空2座匹配4人寝坐6人桌while(b6>0&&a4>0) {b6--;a4--;sum+=4;}//空2座匹配2人寝坐4人桌while(b4>0&&a2>0) {b4--;a2--;sum+=2;}//空3座匹配3人寝坐6人桌while(b6>0&&a3>0) {b6--;a3--;sum+=3;}//空4座匹配2人寝坐6人桌while(b6>0&&a2>0) {b6--;a2--;sum+=2;}System.out.println(sum);}scan.close();}