先浅学一遍数据结构，不会拉倒，找点简单题练练语法基础
然后边学边刷二分查找和双指针
递归和暴力，边学边刷
学习贪心，练个几十道
再去过下数据结构
开始算法:搜索，动态规划，
搜索很重要，深度优先可骗分
然后动态规划，挺难，多学多练看造化
一共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>() {
@Override
public 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>() {
@Override
public 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-n
int 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]的索引left
if(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;//最小为1
dp[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中，然后递归调用dfs
for(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-6
static 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作为block
if (!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();//数N
k=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份 每份至少大于i
for(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和y1
int 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;//起点步数为0
int[][] 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++;
}
//循环可以走的所有点 切判断点是否合法 且不能等于x
for(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}};
//bfs
while(!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)****
模拟 构造 回文
防超时
优化点说明：
- 分离循环： 为两种日期类型分别设置循环，找到结果后立即终止。
- 减少字符串转换： 在生成日期时直接操作字符串，避免重复转换。
- 提前终止： 找到符合条件的日期后立即返回，减少不必要的循环。
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});
//bfs
while(!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个数123456
c=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){//12
int t = n%10;//2
if((t>temp&&temp!=0)||t==0){//到个位不比较
return false;
}
temp = t;//temp=2
n/=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是预留jk
for(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);
//在此输入您的代码...直接暴力试一试 虽然多 但行列应该不超过500
char[][] 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食堂
贪心
贪心的核心优先级：
- 满桌优先 首先一定是让桌子都塞满人，这样利用率才能最大化。
- 小桌优先 先把人放到小桌中，因为小桌（4人桌）的人数组合搭配不够灵活，大桌（6人桌）可以有更多中组合搭配。
- 人多优先 寝室人多的先安置，因为人多不灵活，如果后面不能安置了，那么会损失很多人，利用率就下降了。
- 空少优先 当一个桌子不得不空出位置时，尽量少空出位置。(空出位置数相同时,优先排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();
}