入门训练
1.斐波那契数列
题目：输出一行，包含一个整数，表示Fn除以10007的余数。
关键：mod运算运用
(a×b) mod c=(a mod c * b mod c) mod c
(a+b) mod c=(a mod c+ b mod c) mod c
(a-b) mod c=(a mod c- b mod c) mod c
2.算圆的面积
java.math中有PI的定义
图片.png
图片.png
图片.png
3.序列求和
使用大整数类进行累加
import java.util.*;
import java.math.*;
public class Main {
static public void main(String args[]) {
double a;
Scanner in = new Scanner(System.in);
a=in.nextDouble();
BigDecimal e = new BigDecimal(2);
BigDecimal c = new BigDecimal(a+1);
BigDecimal d = new BigDecimal(a);
e=c.multiply(d).divide(e);
System.out.println(e);
}
}
4.A+B问题
让double输出没有小数点 System.out.printf("%.0f",a);
import java.util.*;
public class Main {
static public void main(String args[]) {
double a,b ;
Scanner in = new Scanner(System.in);
a=in.nextDouble();
b=in.nextDouble();
a=a+b;
System.out.printf("%.0f",a);
}
}
基础练习
1.数组排序
使用自动排序 Arrays.sort()
import java.util.*;
public class Main {
static public void main(String args[])
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++)
{
a[i]= in.nextInt();
}
Arrays.sort(a);
for(int i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
}
}
2.十六进制转八进制
①十六进制转二进制再转八进制
StringBuffer又称为可变字符序列，它是一个类似于 String 的字符串缓冲区，通过某些方法调用可以改变该序列的长度和内容。原来StringBuffer是个字符串的缓冲区，即就是它是一个容器，容器中可以装很多字符串。并且能够对其中的字符串进行各种操作。
图片.png
import java.io.*;
public class Main{
public static void main(String args[]) throws NumberFormatException,IOException{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(buf.readLine());
String str[] = new String[n];
for(int i=0;i<n;i++) {
str[i]=buf.readLine();
}
for(int j=0;j<n;j++) {
transform(str[j]);
}
}
public static void transform(String s) {
StringBuffer st= new StringBuffer();
char c[] = s.toCharArray();
for(int i=0;i<c.length;i++) {
switch(c[i]) {
case '0':{
st.append("0000");
break;
}
case '1':{
st.append("0001");
break;
}
case '2':{
st.append("0010");
break;
}
case '3':{
st.append("0011");
break;
}
case '4':{
st.append("0100");
break;
}
case '5':{
st.append("0101");
break;
}
case '6':{
st.append("0110");
break;
}
case '7':{
st.append("0111");
break;
}
case '8':{
st.append("1000");
break;
}
case '9':{
st.append("1001");
break;
}
case 'A':{
st.append("1010");
break;
}
case 'B':{
st.append("1011");
break;
}
case 'C':{
st.append("1100");
break;
}
case 'D':{
st.append("1101");
break;
}
case 'E':{
st.append("1110");
break;
}
case 'F':{
st.append("1111");
break;
}
}
}
transform_02(st);
}
public static void transform_02(StringBuffer s) {
int i=s.length();
if(i%3==0) {
if(s.substring(0, 3).equals("000"))
s.delete(0, 3);
}
if(i%3==1) {
if(s.substring(0, 1).equals("0"))
s.delete(0, 1);
else
s.insert(0,"00");
}
if(i%3==2) {
if(s.substring(0, 2).equals("00"))
s.delete(0, 2);
else
s.insert(0,"0");
}
int n =s.length()/3;
String s1[] = new String[n];
StringBuffer sbf=new StringBuffer();
for(int j=0;j<n;j++) {
s1[j]=s.substring(j*3,j*3+3);
if(s1[j].equals("000"))
sbf.append("0");
if(s1[j].equals("001"))
sbf.append("1");
if(s1[j].equals("010"))
sbf.append("2");
if(s1[j].equals("011"))
sbf.append("3");
if(s1[j].equals("100"))
sbf.append("4");
if(s1[j].equals("101"))
sbf.append("5");
if(s1[j].equals("110"))
sbf.append("6");
if(s1[j].equals("111"))
sbf.append("7");
}
String s2=sbf.toString();
System.out.println(s2);
}
}
②调用函数
String bs1 = Integer.toBinaryString(Integer.valueOf("A1", 16)); // 十六进制转2进制
String bs1 = Integer.toOctalString(Integer.valueOf("A1", 16)); // 十六进制转8进制
String bs1 = Integer.toString(Integer.valueOf("A1", 16)); // 十六进制转8进制
但该方法只能处理很小的数字
③使用大整数类 不能用于大题 会运行超时
BigInteger a= new BigInteger(string , radix);
String s3 = a.toString(radix);
import java.math.BigInteger;
import java.util.*;
public class Main{
static public void main(String arg[]) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String str[] = new String[n];
for(int i=0;i<n;i++) {
str[i] =in.next();
}
for(int i=0;i<n;i++) {
String s2=str[i].toString();
BigInteger a= new BigInteger(s2,16);
String s3 = a.toString(8);
System.out.println(s3);
}
}
}
3.十进制转十六进制
import java.util.*;
public class Main {
public static void main (String args[]){
int n=new Scanner(System.in).nextInt();
System.out.println(Integer.toHexString(n).toUpperCase());
}
}
4.特殊的回文数
坑：StringBuffer st2 = new StringBuffer();
若让 st1 = st2.reverse(); 则st1和st2都会变成st2的逆序
st1.equals()比较的是两个对象，对于任何非空引用值str1 和 str2，当且仅当str1 和 str2 引用同一个对象时，此方法才返回 true 可以用toString String.equals()进行比较
java进行代码调试 下断点后，右键单击代码区域，选择Debug as ->java application
① 该方法会运行超时
package 特殊的回文数;
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) {
int n = new Scanner(System.in).nextInt();
StringBuffer st = new StringBuffer();
StringBuffer st1 = new StringBuffer();
for(int num=10000;num<999999;num++) {
int sum=0; int r; int t=num;
while(t!=0)
{
r = t%10;
sum+=r;
t = t/10;
}
if(sum!=n) continue;
st.append(num);
st1.append(num).reverse();
String St = st.toString();
String St1 = st1.toString();
if(!St.equals(St1))
continue;
else System.out.println(num);
}
}
}
②用ArrayList和Collections实现
分类为5位数和6位数
用i、j、k表示
5位数为ijkji
6位数为ijkkji
Collections 为 ArrayList的父类 可以用Collections.sort(List) 对List进行排序
import java.util.*;
public class Main{
public static void main(String args[]) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
ArrayList<Integer> rs = new ArrayList<Integer>();
for(int i=1;i<10;i++)
for(int j=0;j<10;j++)
for(int k=0;k<10;k++) {
if(2*i+2*j+k==n)
rs.add(i*10000+j*1000+k*100+j*10+i);
if(2*i+2*j+2*k==n) {
rs.add(i*100000+j*10000+k*1000+k*100+j*10+i);
}
Collections.sort(rs);
for(int i=0;i<rs.size();i++)
System.out.println(rs.get(i));
}
}
}
5.回文数
①StringBuffer
import java.util.*;
public class Main {
public static void main(String args[]) {
for (int i = 1000; i < 10000; i++) {
StringBuffer s1 = new StringBuffer();
StringBuffer s2 = new StringBuffer();
s1.append(i);
s2.append(i);
s2=s2.reverse();
String s3 = s1.toString();
String s4 = s2.toString();
if (s3.equals(s4)) System.out.println(i);
}
}
}
②取余再求积
15.public class Main {
16.
17. /**
18. * @param args
19. */
20.
21. public static void main(String args[]) {
22. // TODO Auto-generated method stub
23. Scanner cin = new Scanner(System.in);
24. for(int i=1001;i<10000;i++)
25. {
26. int j=0;
27. for(int x=i;x!=0;x/=10)
28. {
29. j=j*10+x%10;
30. }
31. if(j==i)System.out.println(i);
32. }
33. }
34.}
6.特殊的数
import java.util.*;
public class Main {
public static void main(String args[]) {
for(int i=1;i<9;i++)
for(int j=0;j<9;j++)
for(int k=0;k<9;k++) {
int n=i*100+j*10+k;
if(n==Math.pow(i, 3)+Math.pow(j,3)+Math.pow(k, 3))
System.out.println(n);
}
}
}
7.01字串
①
public class Main {
public static void main(String args[]) {
for(int i=0;i<32;i++)
{
Integer a = new Integer(i);
String c =a.toBinaryString(i);
Integer d = new Integer(c);
System.out.printf("%05d\n", d);
}
}
}
②
1.
2.public class Main{
3.public static void main (String args[]){
4.
5.for(int a1=0;a1<2;a1++){
6. for(int a2=0;a2<2;a2++){
7. for(int a3=0;a3<2;a3++){
8. for(int a4=0;a4<2;a4++){
9. for(int a5=0;a5<2;a5++){
10. StringBuffer s=new StringBuffer();
11. System.out.println(s.append(a1).append(a2).append(a3).append(a4).append(a5));
12. }
13. }
14. }
15. }
16.}
17.
18.}
19.}
8.字母图形
JAVA基本类型及其封装类
图片.png
1.基本类型和封装类的相互转换（以int类型为例）
基本数据类型转封装类：
int num = 3;
Integer integer = new Integer(num);
JDK在添加了自动装装箱的功能之后，我们甚至可以Integer integer = 3;
封装类转基本数据类型：
Integer integer = new Integer(3);
int num = integer.intValue();
当然，也可以直接 int num = integer，这里的自动拆箱，其实也是调用了封装类的intValue()方法来实现的。
注意：简单来说，装箱就是 自动将基本数据类型转换为包装器类型；拆箱就是 自动将包装器类型转换为基本数据类型。
进行 = 赋值操作（装箱或拆箱）
进行+，-，*，/混合运算 （拆箱）
进行>,<,==比较运算（拆箱）
调用equals进行比较（装箱）
ArrayList,HashMap等集合类 添加基础类型数据时（装箱）
2、将String类型字符串与基本数据类型进行转换。
字符串转基本数据类型：
String ageString = "23";
int age = Integer.parseInt(ageString);
基本数据类型转字符串：
String age = 23 + "";
或者 String age = String.valueOf(23);
封闭类转字符串：
直接调用封装类对象的toString()方法即可。
Integer age = 23;
String ageString = age.toString();
字母的序号与两个坐标的差的绝对值有关。
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException,NumberFormatException{
BufferedReader strin = new BufferedReader(new InputStreamReader(System.in));
String s = strin.readLine();
String st[] = s.split(" ");
char c[] = new char[Integer.parseInt(st[1])];
int time =0;
int timemax = Integer.parseInt(st[0]);
for(int i =0;i<c.length;i++) {
c[i]=(char)('B'+i);
}
for(int k=0;k<timemax;k++) {
for(int j=0;j<c.length;j++) {
if(j<time) {
c[j]=(char)(c[j]+1);
}
if(j>=time) {
c[j]=(char)(c[j]-1);
}}time++;
System.out.println(c);
}
}
}
9.数列特征
将String转为int的方法：int a = Integer.parseInt(String);
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException,NumberFormatException{
ArrayList<Integer> a = new ArrayList<Integer>();
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String n1 = in.readLine();
int a1= Integer.parseInt(n1);
int sum=0;
String n2 = in.readLine();
String c[] = n2.split(" ");
for(int i=0;i<a1;i++) {
int t = Integer.parseInt(c[i]);
a.add(t);
sum+=t;
}
int max,min;
max = Collections.max(a);
min = Collections.min(a);
System.out.println(max);
System.out.println(min);
System.out.println(sum);
}
}
10.查找整数
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException,NumberFormatException{
ArrayList<Integer> a = new ArrayList<Integer>();
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String n1 = in.readLine();
int a1= Integer.parseInt(n1);
String n2 = in.readLine();
String n3 = in.readLine();
String a2[] = n2.split(" ");
int a3= Integer.parseInt(n3);
for(int i=0;i<a1;i++) {
int t = Integer.parseInt(a2[i]);
a.add(t);
}
int index;
index = a.indexOf(a3);
System.out.println(index+1);
}
}
11.闰年判断
什么是闰年：
当以下情况之一满足时，这一年是闰年：
年份是4的倍数而不是100的倍数；
年份是400的倍数。
其他的年份都不是闰年。
12.杨辉三角形
使用二维数组int[][] a = new int[n][n]
import java.util.*;
public class Main {
public static void main(String args[]) {
int n = new Scanner(System.in).nextInt();
int[][] d= new int[n][n];
for(int i=0;i<n;i++) {
for(int j=0;j<=i;j++) {
if(j==0||j==i)
d[i][j]=1;
else
d[i][j]=d[i-1][j-1]+d[i-1][j];
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<=i;j++) {
System.out.print(d[i][j]+" ");
}
System.out.println();
}
}
}
算法训练
1.区间k大数查询
List排序用 Collections.sort( )
数组排序用 Array.sort( )
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException,NumberFormatException{
BufferedReader s1 = new BufferedReader(new InputStreamReader(System.in));
String a1 = s1.readLine();
int n = Integer.parseInt(a1);
String a2 =s1.readLine();
String c[]= a2.split(" ");
String a3 =s1.readLine();
int m = Integer.parseInt(a3);
for(int i=0;i<m;i++) {
String a4 = s1.readLine();
String c2[] = a4.split(" ");
int start = Integer.parseInt(c2[0]);
int r = Integer.parseInt(c2[1]);
int k = Integer.parseInt(c2[2]);
findk(n,c,start,r,k);
}
}
static void findk(int n,String c[],int start,int r,int k) {
ArrayList<Integer> list1 = new ArrayList<Integer>();
for(int j=0;j<r-start+1;j++) {
list1.add(Integer.parseInt(c[start+j-1]));
}
Collections.sort(list1);
Collections.reverse(list1);
System.out.println(list1.get(k-1));
}
}
2.最大最小公倍数
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long N = sc.nextInt();
long max;//定义最小公倍数
if (N<=2) {
max = N;//N为1 ， 2 的情况
}else if (N%2 == 1) {//判断N是否为奇数，如为基数，则N N-1 N-2 互质
max = N*(N-1)*(N-2);
}else if (N%3 != 0) {//此处表明N为偶数，N与N-2有最大公倍数2，但与N-3互质，固所选第三位整数往后推一位，即N-3
max = N*(N-1)*(N-3);
}else {//此处表明，此时的N与另两位整数总有最大公约数，固选择的三个整数整体往后推一位，即N-1 N-2 N-3
max = (N-1)*(N-2)*(N-3);
}
System.out.print(max);
}
}
3.k好数
java中数组的初始值为0
动态规划：列表一步一步地解决问题---二维数组
参考 https://blog.csdn.net/yztfst/article/details/86599291
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int jz = in.nextInt();
int w = in.nextInt();
long[][] dp = new long[1000][1000];
for(int i=1;i<jz;i++) {
dp[0][i]=1;
}
for(int i=1;i<w;i++) {
for(int j=0;j<jz;j++) {
for(int j2=0;j2<jz;j2++) {
if((j!=j2+1)&&(j!=j2-1))
dp[i][j]=(dp[i][j]+dp[i-1][j2])%1000000007;
}
}
}
long sum = 0;
for(int i=0;i<jz;i++) {
sum= (sum%1000000007+dp[w-1][i]%1000000007)%1000000007;
}
System.out.println(sum);
}}
4.结点选择
参考 https://blog.csdn.net/qq_40693171/article/details/83590048
StreamTokenizer效率更高
- 类java.io.StreamTokenizer可以获取输入流并将其分析为Token(标记)。StreamTokenizer的nextToken方法将读取下一个标记
- 默认情况下，StreamTokenizer认为下列内容是Token：字母、数字、除C和C++注释符号以外的其他符号。如符号“/”不是Token，注释后的内容也不是，而“\”是Token。单引号和双引号以及其中的内容，只能算是一个Token。
- 要统计文件的字符数，不能简单地统计Token数，因为字符数不等于Token，按照Token的规定，引号中的内容就算是10页也算是一个Token。如果希望引号和引号中的内容都算作Token，应该通过StreamTokenizer的ordinaryCha()方法将单引号和双引号当做普通字符处理。
import java.util.*;
import java.io.*;
import java.io.*;
public class Main {
static int leng[];
public static void main(String[] args) throws IOException {
// TODO 自动生成的方法存根
StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int n=(int)in.nval;in.nextToken();int m=(int)in.nval;
List<node>list[]=new ArrayList[n];//存储路径
for(int i=0;i<n;i++)//声明
{
list[i]=new ArrayList<>();
}
leng=new int[n];
boolean jud[]=new boolean[n];//判断是否在队列内
for(int i=1;i<n;i++) {leng[i]=Integer.MAX_VALUE;}//初始最长均为max
for(int i=0;i<m;i++)
{
in.nextToken();int u=(int)in.nval;
in.nextToken();int v=(int)in.nval;
in.nextToken();int l=(int)in.nval;
list[u-1].add(new node(v-1, l));
}
Queue<Integer>q1=new ArrayDeque<Integer>();
q1.add(0);//第一个
while(!q1.isEmpty())
{
int x=q1.poll();
jud[x]=false;
for(int i=0;i<list[x].size();i++)//遍历
{
int index=list[x].get(i).x;//x邻居该节点的编号
int length=list[x].get(i).leng;//x到这个邻居的距离
if(leng[index]>leng[x]+length)
{
leng[index]=leng[x]+length;
if(!jud[index])//队列中没有该点
{q1.add(index);jud[index]=true;}
}
}
}
for(int i=1;i<n;i++)
{
out.println(leng[i]);
}
out.flush();
}
static class node
{
int x;
int leng;
public node(int x,int leng)
{
this.x=x;
this.leng=leng;
}
}
}
