[数据结构与算法]算法比赛小结

算法小结

格式

java加快输入和输出

传统的Scanner输入比较慢，用下面的InputReader类加快输入和输出
之前的输入和输出分别用实例化的reader和writer
去替换System.in和System.out
reader.nextInt()
writer.print()

import java.io.*;
import java.util.*;
public class Main {
    
	public static void main(String[] args) {
//		test();
		solution();
	}
	
	public static void solution() {
		InputReader reader = new InputReader(System.in);
	    PrintWriter writer = new PrintWriter(System.out, true);
		int T = reader.nextInt();
		int[] arr = new int[T]; //这里定义的是int类型的数组，实际根据问题改成不同的类型
		for (int i = 0; i < arr.length; i++) {
			String str = reader.next();
			arr[i] = process(str);
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
	public static void test() {
		//写测试的代码
		
	}
	
	//这里定义的是int类型的数组，实际根据问题改成不同的类型
	public static int process(String str) {
		 int res = 0;
		 写解决问题具体的代码
		 
		 return res;
	}
}

class InputReader {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public InputReader(InputStream inputStream) {
		this.reader = new BufferedReader(new InputStreamReader(inputStream));
	}

	public String next() {
		while (tokenizer == null || !tokenizer.hasMoreElements()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {

			}
		}
		return tokenizer.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

}

测试

以排序为例

package 排序;

import java.util.Arrays;

public class Solve {
	public static void swap(int[] arr ,int i,int j){
        if(arr.length == 0 || arr == null){
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void qsort(int[] arr,int left,int right){
    	if (left<right) {
	        int random = left + (int)(Math.random()*(right - left));
	        swap(arr,random,right);
	        int[] p = partition(arr,left,right);
	        partition(arr,left,p[0] - 1);
	        partition(arr,p[1] + 1,right);
    	}
    }
    public static int[] partition(int[] arr,int left,int right){
        int less = left - 1;
        int more = right;
        while(left < more){
            if(arr[left] < arr[right]){
                swap(arr,++less,left++);
            }else if(arr[left] > arr[right]){
                swap(arr,--more,left);
            }else{
                left++;
            }
        }
        swap(arr,more,right);
        return new int[] {less+1,more};
    }
    public static int[] MySort (int[] arr) {
        // write code here
        if(arr == null || arr.length < 2){
            return arr;
        }
        qsort(arr,0,arr.length - 1);
        return arr;
    }

//	以系统自带的排序为例
	public static void comparator(int []arr) {
		Arrays.sort(arr);
	}
//	产生随机数组
	public static int [] generateRandomArray(int maxSize ,int maxValue) {
		int []arr = new int [(int)((maxSize + 1)*Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int)((maxValue + 1)*Math.random()) - (int)(maxValue*Math.random());
		}
		return arr;
	}
//	copy数组
	public static int [] copy(int []arr) {
		if (arr == null) {
			return null;
		}
		int res[] = new int [arr.length];
		for (int i = 0; i < res.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}
//	判断两个数组是否相同
	public static boolean isEqual(int []arr1,int []arr2 ) {
		if (arr1 ==null && arr2 == null) {
			return true;
		}if ((arr1 == null && arr1 != null ) || (arr1 != null && arr1 == null )) {
			return false;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr2.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}
//	打印数组
	public static void printArray(int arr[]) {
		if (arr == null) {
			return ;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
//	用对数器测试
	public static void main(String[] args) {
		int testTime = 5;
		int maxSize = 4;
		int maxValue = 9;
		boolean flag = true;
		for (int i = 0; i < testTime; i++) {
			int []arr1 = generateRandomArray(maxSize,maxValue);
			int []arr2 = copy(arr1);
			MySort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				printArray(arr1);
				printArray(arr2);
				flag = false;
				break;
			}
		}
		System.out.println(flag ? "ok" : "bug");
	}
}

产生随机数

	public static int[] generateRandomArray(int maxSize, int maxValue) {
//		产生长度为[1~maxSize]的数组arr
		int[] arr = new int[(int) ((maxSize) * Math.random()) + 1];
		for (int i = 0; i < arr.length; i++) {
//			arr[i]的范围是	[-maxValue,maxValue]
			arr[i] = (int) ((maxValue + 1) * Math.random())
					- (int) ((maxValue + 1) * Math.random());
		}
		return arr;
	}
	public static int Random_int(int a, int b) {
		// 生成[a-b)的整数
		return (int) (Math.random() * 10 % (a - b) + a);
		// 生成[a-b]的整数
//		return (int)(Math.random() * 10 % (a - b + 1) + a);
	}

	public static double Random_double(double a, double b) {
		// 生成[a-b)的小数
		return Math.random() * (b - a) + a;
	}

数学

最大公约数和最小公倍数

注意：

求两个数的最大公约数和最小公倍数的前提是两个数是正整数，非正整数无意义。

扩展:

利用最大公约数可以化解分数。

公式：分子/分母 = 分子/gcd(分子,分母) / (分母 / gcd())

如: 24 / 18 = 24 / gcd(24,18) / (18/gcd(18,24))

import java.util.Scanner;

public class Gcd_LCM {
//	求a,b 的最大公约数,辗转相除法,
//	非递归法
	public static int gcd(int a,int b) {
		while (a != 0) {
			int temp= b % a;
			b = a;
			a = temp;
		}
		return b;
		//返回值为1，则两个数互为质数。
	}
//	递归法
	public static int gcd2(int a, int b) {
		return b == 0 ? a : gcd2(b, a % b);
	}
//	求a,b 的最小公倍数LCM = a/gcd(a, b)*b;
	public static int LCM(int a,int b) {
		return a/gcd(a,b) * b;
	}
    /**
	 * a除b如果是小数则写成分数的形式 4/24 = 1/6
	 * @param a  分子
	 * @param b  分母
	 */
	public static String huajian(int a, int b) {
		if (a % b == 0 ) {
			return "" + (a / b);
		} else {
			return ""+(a / gcd(a, b)  + "/" + b / gcd(a, b));
		}
	}
	public static void main(String[] args) {
//		System.out.println("请输入两个正整数");
//		Scanner input = new Scanner(System.in);
//		int a = input.nextInt();
//		int b = input.nextInt();
//		System.out.println(240 % 33);
//		System.out.println(33 % 9);
		int a = 16,b = 12;
//		if (gcd(a,b) == 1) { 
//			System.out.println("两个数互为质数");
//		}
//		else System.out.println("最大公约数是："+gcd(a,b));
		System.out.println(a+","+b+"最大公约数是："+gcd(a,b));
		System.out.println(a+","+b+"最小公倍数是："+LCM(a,b));
		System.out.println(huajian(-42, 15));
	}

}

素数

[1] 判断一个数是否是素数

[2] 输出[low,hight]之间的素数

package math;

public class Prime {
	/**
	 * 判断一个数是否为素数，如果是，返回true，否则返回false
	 * @param n 是int类型
	 * @return boolean
	 */
	public static boolean isPrime(int n) {
		int i ;
		boolean flag = false;
		for (i=2;i <= (int)Math.sqrt(n);i++) {
			if(n % i ==0) {
				flag = true;
				break;
			}
		}
		return !flag;
	}
	/**
	 * 输出[low,hight]之间的素数
	 * @param low
	 * @param hight
	 */
	public static void prime_ab(int low,int hight) {
		int index = 0;
		for (int i = low; i <= hight; i++) {
			if(isPrime(i)) {
//				array[index] = i;
				System.out.println(i);
				index++;
			}
		}
		System.out.println("素数的个数："+index+1);
	}
	public static void test() {
//		输出100到10000之间个位数位3的所有素数

		int count = 0;
		int j = 103;
		int k = 1;
		while (j <= 10000) {
			if (isPrime(j) && j % 10 == 3) {
				count++;
				System.out.printf("%5d ",j);
				if(k % 5 == 0) {
					System.out.println();
				}
				k++;
			}
			j++;
			
		}
		System.out.println("\ncount = " + count);
		System.out.println("---------");
//		输出100到10000之间的所有素数
		 count = 0;
		 k = 1;
		for (int i = 100; i <= 10000; i++) {
			if(isPrime(i)) {
				count++;
				System.out.printf("%5d ",i);
				if (k % 5==0) {
					System.out.println();
				}
				k++;
			}
			
		}
		System.out.println("\ncount="+count);
		System.out.println("---------");
	}
	public static void main(String[] args) {
//		输出100到10000之间的所有素数
		prime_ab(100,10000);
		
	}

}

阶乘和组合

package math;

public class 阶乘_组合 {
//	A(n)=n!
//	A的阶乘	非递归
	public static long An(int n) {
		if (n == 0 || n == 1) {
			return 1;
		}
		int An = 1;
		for (int i = 2; i <= n; i++) {
			An *= i;
		}
		return An;
	}
//	C(m,n)=n!/(m!*(n-m)!)
//	c(m,n)组合   C(5,20)  
	public static int C(int m,int n) {
		if (m == 0 || n == 0) {
			return 1;
		}
		if (m > n / 2) {
			m = n - m;
		}
		int fengzi = 1;
		int fengmu = 1;
		while(m != 0) {
			fengzi *= n;
			fengmu *= m;
			n--;
			m--;
		}
		return fengzi/fengmu;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 16;
		System.out.println(An(n));
		System.out.println(C(5,20));
//		C(5,20) = 15504
		System.out.println("9! = "+An(9));
		
	}

}

欧几里得算法

package math;

public class 扩展欧几里得算法 {
	static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	/**
	 *
	 * @param a 第一个参数
	 * @param b 第二个参数
	 * @param x x的值，前两个组成的数组
	 * @param y y的值，前两个组成的数组
	 * @return 返回值为 {最大公约数，x的值，y的值}
	 */
	public static long[] ex_gcd(long a, long b, long[] x, long[] y) {

		long gcd;
		long[] result = new long[3];

		if (b == 0) {
			result[0] = a;
			result[1] = x[0];
			result[2] = y[0];
			return result;
		}
		long q = a / b;
		long tx1 = x[0] - q * x[1];
		long ty1 = y[0] - q * y[1];
		long[] tx = { x[1], tx1 };
		long[] ty = { y[1], ty1 };
		return ex_gcd(b, a % b, tx, ty);
	}

	public static long[] ex_gcd(long a, long b) {
		long[] x = { 1, 0 };
		long[] y = { 0, 1 };
		return ex_gcd(a, b, x, y);
	}

}

矩阵

矩阵的打印

public static void printMatrix(long[][] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.print(a[i][j] + " ");
			}
			System.out.println();
		}
	}

矩阵的乘法

package matrix;

import java.util.Scanner;

public class MatrixMultiply {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		long[][] a = new long[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				a[i][j] = sc.nextLong();
			}
		}
		int p = sc.nextInt();
		long[][] b = new long[n][p];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < p; j++) {
				b[i][j] = sc.nextLong();
			}
		}
		System.out.println();
		printMatrix(matrixMultiply(a, b));
	}
	public static void printMatrix(long[][] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.print(a[i][j] + " ");
			}
			System.out.println();
		}
	}
	public static long[][] matrixMultiply(long[][] a,long[][] b) {
		int n = a.length;
		int m = a[0].length;
		int p = b[0].length;
		if(a[0].length != b.length) throw new IllegalArgumentException();
		long[][] res = new long[m][p];
		for(int i = 0;i < m;i++) {
			for (int j = 0; j < p; j++) {
				for (int k = 0; k < n; k++) {
					res[i][j] += a[i][k] * b[k][j];
				}
			}
		}
		return res;
	}
}

输入

2 2
1 2
1 -1
3
1 2 -3
-1 1 2

输出

-1 4 1
2 1 -5

矩阵的转置

package matrix;

import java.util.Scanner;

public class MatrixTranspose {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		int[][] a = new int[m][n];
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[0].length; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		printMatrix(matrixTranspose(a));
	}
//	打印矩阵
	public static void printMatrix(int[][] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.print(a[i][j] + " ");
			}
			System.out.println();
		}
	}
//	矩阵的转置
	public static int[][] matrixTranspose(int[][] a) {
		int[][] res = new int[a[0].length][a.length];
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				res[j][i] = a[i][j];
			}
		}
		return res;
	}
}

字符串

字符串常见的操作

package string;

public class _01StringBasicOpeMethod {
/*
https://blog.csdn.net/sjq__python_web/article/details/80099454
*/
	 public static void main(String args[]){
	        String str = "如何才能变得像棋哥一样优秀？算了吧，憋吹牛逼！"; //定义一个字符串
	        System.out.println(str);  //输出字符串
	        /***1、length()方法***/
	        int length = str.length();//得到字符串长度
	        System.out.println("字符串的长度为："+length);
	        /***2、charAt()方法***/
	        String str1 = "0123456789";
	        char ch = str.charAt(7);  //得到索引为7的字符(索引从0开始)
	        System.out.println("字符串中的第8个字符为："+ch);
	        char ch2 = str1.charAt(9);
	        System.out.println("字符串中的第9个字符为："+ch2);
	        /***3、getChars()方法***/
	        char chardst[] = new char[20]; //定义容量为80的字符数组，用于存储从字符串中提取出的一串字符
	        System.out.print("chardst:");
	        System.out.println(chardst);
	        for (int i = 0; i < chardst.length; i++) {
				chardst[i] = 'i';
			}
	        System.out.println(chardst);
	        str.getChars(0,14,chardst,5);
//		   		  1、indexBegin：需要复制的字符串的开始索引
//	            2、 indexEnd:需要复制的字符串的结束索引，indexEnd-1
//	            3、array: 前面定义的 char 型数组的数组名
//	            4、arrayBegin: 数组 array 开始存储的位置索引号
	        System.out.println("字符数组中存放的内容为："+chardst);//错误，输出的是编码
	        System.out.println(chardst); //**括号中不可带其他字符串
	 }
	
}

字符串的比较方法

package string;

public class _02StringCompareMethod {

//	String 比较方法
	public static void main(String[] args) {
		String str1 = "abcd";
		String str2 = "Abcd";
		String str3 = "abdc";
		String str4 = "abcdef";
//		比较的是字符串的 Unicode 值
//		不忽略大小写比较,从左往右比较,小写字母比大写字母大
		if (str1.compareTo(str2) > 0) {
			System.out.println(str1 + " > " + str2);
		}
		if (str1.compareTo(str3) < 0) {
			System.out.println(str1 + " < " + str3);
		}
		String str5 = "ab cd";
		String str6 = "abcd";
//		长度不同的，遇到空格，空格比其他的小
		if (str5.compareTo(str6) < 0) {
			System.out.println(str5 + " < " + str6);
		}
//(1) 不忽略字符串大小写情况下判别字符串相等的方法 eaquals(another str)
//格式：boolean result = str1.equals(str2);
//当且仅当 str1 和 str2 的长度相等，且对应位置字符的 Unicode 编码完全相等，返回 true, 否则返回 false

		String str7 = "1234";
		String str8 = "1234";
		String str9 = "1234 ";
		if (str7.equals(str8)) {
			System.out.println(str7+"="+str8);
		}
		if (!str7.equals(str9)) {
			System.out.println(str7+"!="+str9+", ");
		}
//(2) 忽略字符串大小写情况下判别字符串相等的方法 equalsIgnoreCase(another str)
//格式：boolean result = str1.equals(str2);
		String str10 = "abcd";
		String str11 = "Abcd";
		if (str10.equalsIgnoreCase(str11)) {
			System.out.println(str10+"="+str11);
		}
	}
	     
}

字符串与其他数据类型的转换

package string;

public class _03字符串与其他数据类型的转换 {
/*
https://blog.csdn.net/sjq__python_web/article/details/80099454
*/
	public static void main(String args[]){
        /***将字符串类型转换为其他数据类型***/
        boolean bool = Boolean.getBoolean("false"); //字符串类型转换为布尔类型
        int integer = Integer.parseInt("20");    //字符串类型转换为整形
        long LongInt = Long.parseLong("1024");   //字符串类型转换为长整形
        float f = Float.parseFloat("1.521");     //字符串类型转换为单精度浮点型
        double d = Double.parseDouble("1.52123");//字符串类型转换为双精度浮点型
//        byte bt = Byte.parseByte("ab");         //字符串类型转换为byte型
        char ch = "棋哥".charAt(0);
        System.out.println(ch);
        /***将其他数据类型转换为字符串类型方法1***/
        String strb1 = String.valueOf(bool);    //将布尔类型转换为字符串类型
        String stri1 = String.valueOf(integer); //将整形转换为字符串类型
        String strl1 = String.valueOf(LongInt); //将长整型转换为字符串类型
        String strf1 = String.valueOf(f);       //将单精度浮点型转换为字符串类型
        String strd1 = String.valueOf(d);       //将double类型转换为字符串类型
//        String strbt1 = String.valueOf(bt);     //将byte转换为字符串类型
        String strch1 = String.valueOf(ch);     //将字符型转换为字符串类型
    }
}

_04字符串查找

package string;

public class _04字符串查找 {
	public static void main(String args[]){
        String str = "How qi bocome handsome like qi ge"; //定义一个长字符串
        System.out.println("该字符串为："+str);
        /***1、indexOf()方法查找字符首个出现位置格式1,2***/
        int index1 = str.indexOf(" ");  //找到第一个空格所在的索引
        int index2 = str.indexOf(" ",4); //找到索引4以后的第一个空格所在索引
        System.out.println("第一个空格所在索引为："+index1);
        System.out.println("索引4以后的第一个空格所在索引为："+index2);
        System.out.println("*****************");
        /***2、lastIndexOf()方法查找字符最后出现位置格式1,2***/
        int index3 = str.lastIndexOf(" ");  //找到最后一个空格所在的索引
        int index4 = str.lastIndexOf(" ",10);//找到索引10以后的第一个空格所在索引
        System.out.println("最后一个空格所在索引为："+index3);
        System.out.println("索引10以前最后一个空格所在索引为："+index4);
        System.out.println("*****************");
        /***3、indexOf()方法查找子字符串第一次出现位置格式1,2***/
        int index5 = str.indexOf("qi"); //找到"qi"子字符串第一次出现位置的索引
        int index6 = str.indexOf("qi",5);//找到索引5以后子字符串"qi"第一个出现位置所在索引
        System.out.println("子字符串qi第一次出现位置的索引号为："+index5);
        System.out.println("索引5以后子字符串qi第一次出现位置的索引号为："+index6);
        System.out.println("*****************");
        /***4、lastIndexOf()方法查找子字符串最后一次出现位置格式1,2***/
        int index7 = str.lastIndexOf("qi");
        int index8 = str.lastIndexOf("qi",5);
        System.out.println("子字符串qi最后一次出现位置的索引号为："+index7);
        System.out.println("索引号5以后子字符串qi最后一次出现位置的索引号为："+index8);
    }
}

_05字符串截取与拆分

package string;

public class _05字符串截取与拆分 {
	public static void main(String args[]){
        String str = "How to cut and split strings"; //定义字符串
        System.out.println("字符串为："+str);
        int length = str.length(); //获取字符串长度，保存到变量中
        System.out.println("字符串长度为："+length);
        /***1、substring()方法截取出第一个单词和最后一个单词***/
        //首先配合indexOf()和lastIndexOf()方法找到第一个单词和最后一个单词前后空格的索引号
        //第一个单词的左范围索引为0，最后一个单词的右范围索引为length-1
        int firstIndex = str.indexOf(' '); //找到第一个空格所在位置
        int lastIndex = str.lastIndexOf(' '); //找到最后一个空格所在位置
        System.out.println("第一个空格的索引号为："+firstIndex);
        System.out.println("最后一个空格的索引号为："+lastIndex);
        //利用substring()方法根据第一个和最后一个单词的索引范围截取出第一个和最后一个单词
        String firstWord = str.substring(0,firstIndex); //截取出第一个单词
        String lastWord = str.substring(lastIndex+1,length);//截取出最后一个单词
        System.out.println("第一个单词为："+firstWord);
        System.out.println("最后一个单词为："+lastWord);
        /***1、split()方法拆分出所有单词***/
        String stringArray[] = str.split(" ");  //根据空格要求拆分出所有单词保存到字符串数组中
        System.out.println("拆分之后的各个词汇为："); //输出提示信息
        for(int i = 0;i<stringArray.length;i++){
            System.out.print(stringArray[i]+"\t");
        }
    }
}

_06字符串的替换或修改

package string;

public class _06替换或修改 {
	public static void main(String args[]){
        String str1 = "vbasic";
        String str2 = "Vbasic";
        System.out.println("str1 = "+str1);
        System.out.println("str2 = "+str2);
        /***1、concat()方法将两字符串合并***/
        String str3 = str1.concat(str2);
        System.out.println("str1和str2合并后的字符串为："+str3);
        /***2、toLowerCase()方法将str1字符全部转换为小写***/
        String str4 = str1.toLowerCase();
        System.out.println("str1的字符全部转换为小写："+str4);
        /***3、toUpperCase()方法将str2字符全部转换为大写***/
        String str5 = str2.toUpperCase();
        System.out.println("str2的字符全部转换为大写："+str5);
        /***4、实现字符串的替换，原字符串内容不变***/
        String str6 = str1.replaceFirst("(?i)VBASIC","C++");
        String str7 = str2.replaceFirst("(?-i)VBASIC","C++");
        System.out.println("替换后的str1："+str6);
        System.out.println("替换后的str2:"+str7);
    }
}

字符串的加密和解密

package string;

public class 加密解密 {
/*
给一段原字符和加密字符的关系：str1 ,str2
求字符串 string加密后的字符串ans;

*/
	public static String jiaMi(String str1,String str2,String string) {
//		将要加密的字符转换成char数组
		char[] c = string.toCharArray();
		String ans = "";
//		遍历char数组
		for (int i = 0; i < c.length; i++) {
//			在原码中找到相应字符的下标
			int j = str1.indexOf(c[i]);
//			通过下标在密码中找到加密后的字符
			ans += str2.substring(j, j + 1);
		}
		return ans;
	}
	public static String jieMi(String str1,String str2 ,String string) {
//		将要解密的字符串转换成char数组
		char[] ch = string.toCharArray();
		String ans = "";
//		遍历char数组
		for (int i = 0; i < ch.length; i++) {
//			找到char数组相应字符对应在密码的下标
			int j = str2.indexOf(ch[i]);
//			通过下标找到原码，然后拼接一下
			ans += str1.substring(j, j + 1);
		}
		return ans;
	}
	public static void main(String[] args) {
//		原字符
		String str1 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
//		加密后的字符
		String str2 = "yxmdacikntjhqlgoufszpwbrevYXMDACIKNTJHQLGOUFSZPWBREV";
		
//		需要加密的字符串
		String str = "YeRikGSunlRzgDlvRwYkXkrGWWhXaA";
		System.out.println(jiaMi(str1, str2, str));
//		EaFnjISplhFviDhwFbEjRjfIBBkRyY
		String string = "EaFnjISplhFviDhwFbEjRjfIBBkRyY";
		System.out.println(jieMi(str1, str2, string));
//		YeRikGSunlRzgDlvRwYkXkrGWWhXaA
	}
}

字符串大小写的转换

package string;

public class 字符串大小写转换 {
	public class ToLowerUpperCase {
		private String str;
		public String toLowerCase(String str,int i) {
			return str.toLowerCase();
		}
	}
	public static void main(String[] args) {
//		大写转小写
		String str = "Test 例子 Demo 哈哈 ";
		System.out.println("[" + str + "] 转小写 [" + str.toLowerCase() + "]");
//		小写转大写
		String str2 = "Test 例子 Demo 哈哈 ";
		System.out.println("[" + str2 + "] 转大写 [" + str2.toUpperCase() + "]");
		
//		这两个例子的 中文都保留了原来的样子
		
//		大写转小写
		String str3 = "DEPTNO";
		System.out.println("[" + str + "] 转小写 [" + str3.toLowerCase() + "]");
//		小写转大写
		String str4 = "Test 例子 Demo 哈哈 ";
		System.out.println("[" + str2 + "] 转大写 [" + str4.toUpperCase() + "]");
 	}
}

回文串

package string;

import java.util.ArrayList;
import java.util.Scanner;

public class 回文串 {
    //判断一个字符串是否为回文串
//	区分大小写
	public static boolean isPalindromeString(String string) {
		char[] ch = string.toCharArray();
		for (int i = 0; i < ch.length / 2; i++) {
			if (ch[i] != ch[ch.length - 1 - i]) {
				return false;
			}
		}
		return true;
	}
//	不区分大小写
	public static boolean isPalindromeString2(String string) {
		 String string2 = string.toLowerCase();//全部变成小写
		char[] ch = string2.toCharArray();
		for (int i = 0; i < ch.length / 2; i++) {
			if (ch[i] != ch[ch.length - 1 - i]) {
				return false;
			}
		}
		return true;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<String> string = new ArrayList<String>();
//		string.add("12345");
//		string.add("12321");
//		string.add("abcba");
		string.add("Abcba");
		for (int i = 0; i < string.size(); i++) {
			System.out.println(string.get(i));
			System.out.println("区分大小写：");
			if (isPalindromeString(string.get(i))) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
			System.out.println("不区分大小写：");
			if (isPalindromeString2(string.get(i))) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}

	}
}

大数运算

大整数BigInteger

package 大数运算;

import java.math.BigInteger;

public class BigIntegerTest {
/*
java中用于操作大数的类主要有两个，一个是BigInteger，代表大整数类用于对大整数进行操作，
另一个是BigDecimal，代表大浮点型。
因为这两种类的使用方法是一样的且通常情况下我们处理的数据是整数，
所以下面我们以BigInteger为例进行讲解

https://blog.csdn.net/dongchengrong/article/details/78848399
*/
	
	public static void main(String[] args) {
//		1、新建一个值为123的大整数对象
//		System.out.println("===新建对象===");
		BigInteger b = new BigInteger("123");//第一种，参数是字符串
		int a1 = 456;
		BigInteger a = BigInteger.valueOf(a1);    //第二种，参数可以是int、long
		long c1 = 123;
		BigInteger c = BigInteger.valueOf(c1);
		
//		2、大整数的四则运算
		System.out.println("==大整数的四则运算==");
		a. add(b);    //a,b均为BigInteger类型，加法
		System.out.printf(a +"+"+ b +" = "+a.add(b)+"\n");
		a.subtract(b);   //减 法
		System.out.printf(a +"-"+ b +" = "+a.subtract(b)+"\n");
		a.multiply(b);    //乘法
		System.out.printf(a +"*"+ b +" = "+a.multiply(b)+"\n");
		a.divide(b);  //除法
		System.out.printf(a +"/"+ b +" = "+a.divide(b)+"\n");
		
//		3,常用方法
		System.out.println("===常用方法===");
		a.mod(b);  //求余
		System.out.printf(a +".mod("+ b +") = "+a.mod(b)+"\n");
		a.gcd(b);  //求最大公约数
		System.out.printf(a +".gcd("+ b +") = "+a.gcd(b)+"\n");
		a.max(b);  //求最大值
		System.out.printf(a +".max("+ b +") = "+a.max(b)+"\n");
		a.min(b);  //求最小值
		System.out.printf(a +".min("+ b +") = "+a.min(b)+"\n");
		 
//		4、大整数比较大小
		System.out.println("===大整数比较大小===");
		a.equals(b);  //如果a、b相等返回true否则返回false
		System.out.println(a.equals(b));
		a.compareTo(b);  //a小于b返回-1，等于返回0，大于返回1
		BigInteger compareTo1 = new BigInteger("-123");
		BigInteger compareTo2 = new BigInteger("123");
		BigInteger compareTo3 = new BigInteger("123");
		BigInteger compareTo4 = new BigInteger("200");
		System.out.println(compareTo1.compareTo(compareTo2));
		System.out.println(compareTo2.compareTo(compareTo3));
		System.out.println(compareTo4.compareTo(compareTo3));
		
//		5、BigInteger中的常数
		System.out.println("===BigInteger中的常数====");
		 BigInteger big0 = BigInteger.ZERO;   //大整数0
		 System.out.println(big0);
		 BigInteger big1 = BigInteger.ONE;   //大整数1
		 System.out.println(big1);
		 BigInteger big10 = BigInteger.TEN; //大整数10
		 System.out.println(big10);
		 
//		 6、求大整数的位数
		 System.out.println("===求大整数的位数====");
		//先转换成字符串再求字符串的长度
		 BigInteger biglength = new BigInteger("123456789");
		a.toString().length();   //a的类型为BigInteger
		System.out.println(biglength.toString().length());
		
	}
}

大浮点数

package 大数运算;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;

public class BigDecimalTest {
/*
float和double类型的主要设计目标是为了科学计算和工程计算。
他们执行二进制浮点运算，
这是为了在广域数值范围上提供较为精确的快速近似计算而精心设计的。
然而，它们没有提供完全精确的结果，所以不应该被用于要求精确结果的场合。
但是，商业计算往往要求结果精确，这时候BigDecimal就派上大用场啦。

https://blog.csdn.net/qq_35868412/article/details/89029288
*/
	
	public static void main(String[] args) {
		System.out.println(0.2 + 0.1);
        System.out.println(0.3 - 0.1);
        System.out.println(0.2 * 0.1);
        System.out.println(0.3 / 0.1);
        
//    你认为你看错了，但结果却是是这样的。问题在哪里呢？
//    原因在于我们的计算机是二进制的。浮点数没有办法是用二进制进行精确表示。
//    我们的CPU表示浮点数由两个部分组成：指数和尾数，这样的表示方法一般都会失去一定的精确度，
//    有些浮点数运算也会产生一定的误差。如：2.4的二进制表示并非就是精确的2.4。
//    反而最为接近的二进制表示是 2.3999999999999999。
//    浮点数的值实际上是由一个特定的数学公式计算得到的。
        
//        创建BigDecimal
        System.out.println("创建BigDecimal");
        BigDecimal bigBigDecimal = new BigDecimal("12.3456");
        System.out.println(bigBigDecimal);
        
//        double double1 = 0.123;
//        BigDecimal doubleBigDecimal = BigDecimal.valueOf(double1);
//        System.out.println(doubleBigDecimal);
        
//        BigDecimal bigDecimal = new BigDecimal(2);
//        System.out.println("bigDecimal=" + bigDecimal);
        BigDecimal bDouble = new BigDecimal(2.3);	//不推荐使用
        System.out.println("bDouble=" + bDouble);	
        
//        JDK的描述：1、参数类型为double的构造方法的结果有一定的不可预知性。
//        有人可能认为在Java中写入newBigDecimal(0.1)所创建的BigDecimal正好等于 0.1（
//        非标度值 1，其标度为 1），但是它实际上等于0.1000000000000000055511151231257827021181583404541015625。
//        这是因为0.1无法准确地表示为 double（或者说对于该情况，不能表示为任何有限长度的二进制小数）。
//        这样，传入到构造方法的值不会正好等于 0.1（虽然表面上等于该值）。 
        
        double d = 0.123;
//        double 类型的一定要转的话，先把double转换成String类型，float同理
        BigDecimal bigdouble = new BigDecimal(Double.toString(d));
        float f = 0.12f;
        BigDecimal bigfloat = new BigDecimal(Float.toString(f));
        
//        其他类型的创建方式
        BigDecimal bString = new BigDecimal("2.3");//推荐使用
        System.out.println("bString=" + bString);
//        BigDecimal(int)       创建一个具有参数所指定整数值的对象。 
//        BigDecimal(long)    创建一个具有参数所指定长整数值的对象。 
        int int1 = 34;
        BigDecimal bigint = new BigDecimal(int1);
        System.out.println(int1);
        long long1 = 123456789;
        BigDecimal biglong = new BigDecimal(long1);
        System.out.println(long1);
        
//        四则运算
        BigDecimal first = new BigDecimal("369");
        BigDecimal second = new BigDecimal("123");
        
//        加法
        System.out.println("a + b = " + first.add(second));
//        减法
        System.out.println("a - b = " + first.subtract(second));
//        乘法
        System.out.println("a * b = " + first.multiply(second));
//        除法
        System.out.println("a / b = " + first.divide(second));
        
//        舍入模式
//        ROUND_CEILING    //向正无穷方向舍入
//        ROUND_DOWN    //向零方向舍入
//        ROUND_FLOOR    //向负无穷方向舍入
//        ROUND_HALF_DOWN    //向（距离）最近的一边舍入，除非两边（的距离）是相等,如果是这样，向下舍入, 例如1.55 保留一位小数结果为1.5
//        ROUND_HALF_EVEN    //向（距离）最近的一边舍入，除非两边（的距离）是相等,如果是这样，如果保留位数是奇数，使用ROUND_HALF_UP，如果是偶数，使用ROUND_HALF_DOWN
//        ROUND_HALF_UP    //向（距离）最近的一边舍入，除非两边（的距离）是相等,如果是这样，向上舍入, 1.55保留一位小数结果为1.6,也就是我们常说的“四舍五入”
//        ROUND_UNNECESSARY    //计算结果是精确的，不需要舍入模式
//        ROUND_UP    //向远离0的方向舍入
        
//        如果进行除法运算的时候，结果不能整除，有余数，这个时候会报java.lang.ArithmeticException: 
//        这边我们要避免这个错误产生，在进行除法运算的时候，针对可能出现的小数产生的计算，必须要多传两个参数
//        divide(BigDecimal，保留小数点后几位小数，舍入模式)
        
        BigDecimal biga = new BigDecimal("456");
        BigDecimal bigb = new BigDecimal("123");
//        System.out.println(biga.divide(bigb));	报错
//      需要对BigDecimal进行截断和四舍五入可用setScale方法，例：
        BigDecimal c = new BigDecimal("2.135");
        c = c.setScale(2, RoundingMode.HALF_UP);
        System.out.println(c);
        c = c.setScale(0, RoundingMode.HALF_UP);
        System.out.println(c);
//        直接进行截断和四舍五入
        System.out.println(biga.divide(bigb,1,BigDecimal.ROUND_HALF_UP));
//      max 和 min
      System.out.printf(first +".max("+ second +") = "+first.max(second)+"\n");
      System.out.printf(first +".min("+ second +") = "+first.min(second)+"\n");
      
      BigInteger a = BigInteger.ONE;//1
      BigInteger b = BigInteger.ONE;//1
		//斐波那契数列的迭代形式
		for (int i = 3; i < 300; i++) {
			BigInteger tmp = b;
			b = a.add(b);
			a = tmp;
		//大浮点数的除法
		}
		BigDecimal res = new BigDecimal(a,110).divide(new BigDecimal(b,110), BigDecimal.ROUND_HALF_DOWN);
	    //截取字符串,包括0和小数点共103位，即小数点后有101位
//		substring(0,103) 下标从0到103的字符串
		System.out.println(res.toPlainString().substring(0,103));
		
		
    
	}
}

快速幂运算

package 快速幂;

import java.math.BigInteger;
import java.time.Duration;
import java.time.Instant;

public class 快速幂 {

//	递归计算a^n 
//	5 ^ 1000 = ( 5^2 ) ^ 500 = ( 5^4 ) ^ 250...
//	参考：https://blog.csdn.net/qq_19782019/article/details/85621386
	public static long fastpower(long base,long power) {
		long result = 1L;
		while (power > 0) {
//			如果是奇数
			if ((power & 1) == 1) {
				result *= base;
			}
			power = power >> 1;
			base *= base;
		}
		return result;
	}
	public static long fastpower2(long base,long power) {
		long result = 1;
		while (power > 0) {
			if (power % 2 == 1) {
				result *= base;
			}
			power = power / 2;
			base *= base;
		}
		return result;
	}
	public static long fastpower1(long base,long power) {
		long result = 1;
		while (power > 0) {
			if (power % 2 == 1) {
				result *= base;
				power--;
			}else {
				base = base*base;
				power = power / 2;
			}
		}
		return result;
	}
	public static void main(String[] args) {
		System.out.println(fastpower1(2, 10));
		System.out.println(fastpower2(2, 10));
		System.out.println(fastpower(2, 10));
		System.out.println((long)Math.pow(2, 10));
		int testTime = 1000;
		boolean flag = true;
		for (int i = 2; i < testTime; i++) {
			for (int j = 2; j < testTime; j++) {
//				System.out.println("i:"+i+",j:"+j);
				if (fastpower(i, j) != fastpower1(i, j)
				 || fastpower(i, j) != fastpower2(i, j)) {
					System.out.println(fastpower(2, 10));
					System.out.println(fastpower1(2, 10));
					System.out.println(fastpower2(2, 10));
					flag = false;
				}
			}
		}
		System.out.println(flag ? "ok" : "bug");
//		ok
		System.out.println(fastpower2(2, 62));
	}
}

模运算

package 模运算;

public class 模运算的性质 {
//模运算性质一：(a + b) % p = (a % p + b % p) % p
//模运算性质二：(a - b) % p = (a % p - b % p + p) % p
//模运算性质三：(a * b) % p = (a % p * b % p) % p
//模运算性质四：a ^ b % p = ((a % p)^b) % p
//模运算性质五：ab % p = ((a % p) * ( b % p)) % p, 其中 ab 是?个数字，如:2874，98374
//
	//模运算性质一：(a + b) % p = (a % p + b % p) % p
	public static int method1(long a,long b,int p) {
		return (int)((a % p + b % p) % p);
	}
	
	//模运算性质二：(a - b) % p = (a % p - b % p + p) % p
	public static int method2(long a,long b,int p) {
		return (int)((a % p - b % p) % p);
	}

	//模运算性质三：(a * b) % p = (a % p * b % p) % p
	public static int method3(long a,long b,int p) {
		return (int)((a % p * b % p) % p);
	}

	//模运算性质四：a ^ b % p = ((a % p)^b) % p
	public static int method4(long a,long b,int p) {
		return (int)(((a % p)^b) % p);
	}

	//模运算性质五：ab % p = ((a % p) * (b % p)) % p, 
//	其中 ab 是?个数字，如:2874，98374
	public static int method5(long a,long b,int p) {
		return (int)(((a % p) * ( b % p)) % p);
	}
	public static void main(String[] args) {
		System.out.println(method1(23, 45, 19));
		System.out.println(method2(23, 45, 19));
		System.out.println(method3(23, 45, 19));
		System.out.println(method4(23, 45, 19));
		System.out.println(method5(3, 4, 5));
		System.out.println(34 % 5);
	}
}

几何

三角形

package 几何;

public class 三角形 {

/*	海伦公式： 
	S=（△）=√[p(p-a)(p-b)(p-c)] 
	其中p是三角形的周长的一半p=(a+b+c)/2.
	输出三角形的3边，求三角形面积
*/	public static double S(double a,double b,double c) {
		double s;
		double p = (a + b + c) / 2;
		return Math.sqrt(p * (p - a) * (p - b) * (p - c));
	}
//  已知：A,B,C的顶点坐标为：(a,b),(c,d),(e,f)
//	(ad+ be+cf- af- bc-de)/2
	public static double S3(double a,double b,double c,double d,double e,double f) {
		return Math.abs((a*d+ b*e+c*f- a*f- b*c-d*e)/2);
	}
	
	public static void main(String[] args) {
//		输出三角形的3边，求三角形面积
		double a = 5;
		double b = 7;
		double c = Math.sqrt(a*a + b*b);
		System.out.println(S(a,b,c));
//		(0,0),(0,3),(0,4)
		System.out.println(S3(0,0,0,a,b,0));
	}
}

圆

package 几何;

public class 圆 {

//	圆的周长 2*pi*r
	public static double circumference(double r) {
		return 2*Math.PI*r;
	}
	
//	圆的面积 area (r)= pi*r*r
	public static double area(double r) {
		return Math.PI*r*r;
	}
//	圆柱体的表面积 ：2*pi*r*r + 2*pi*r*h = 2*pi*r*(r + h)
	public static double surface_area(double r,double h) {
		return 2*Math.PI*r*(r + h);
	}
//	球的表面积 ：4*Math.PI*r*r
//	球的体积:4*r*r*r/3

}

日历

闰年

package 日历;

public class IsLeap {
/**
 * 闰年是公历中的名词，闰年分为普通闰年和世纪闰年。1、 普通闰年:公历年份是4的倍数的，且
不是100的倍数，为普通闰年。(如2004、 2020年就是闰年) ; 2、世纪闰年:公历年份是整百
数的，必须是400的倍数才是世纪闰年(如1 900年不是世纪闰年，2000年是世纪闰年)。

 * @param year
 * @return
 */
	public static boolean isLeap(int year) {
		return year % 4== 0 && year % 100 != 0 || year % 400 == 0;
	}
	public static void main(String[] args) {
		//输出 2000-2050年之间的闰年：
		for (int i = 2000; i <= 2050; i++) {
			if (isLeap(i)) {
				System.out.printf("%d\n",i);
			}
		}
	}

}

递归和动态规划

换钱的方法数

package 递归_动态规划;

public class 换钱的方法数 {

	public static void main(String[] args) {
		int[] arr = { 10, 5, 1, 25 };
		int aim = 2200;
		long start = 0;
		long end = 0;
		start = System.currentTimeMillis();
		System.out.println(coins1(arr, aim));
		end = System.currentTimeMillis();
		System.out.print("coins1:");
		System.out.println((end - start) + "ms");
		
		start = System.currentTimeMillis();
		System.out.println(coins2(arr, aim));
		end = System.currentTimeMillis();
		System.out.print("coins2:");
		System.out.println((end - start) + "ms");
		
		start = System.currentTimeMillis();
		System.out.println(coins3(arr, aim));
		end = System.currentTimeMillis();
		System.out.print("coins3:");
		System.out.println((end - start) + "ms");
		
		start = System.currentTimeMillis();
		System.out.println(coins4(arr, aim));
		end = System.currentTimeMillis();
		System.out.print("coins4:");
		System.out.println((end - start) + "ms");
		
		start = System.currentTimeMillis();
		System.out.println(coins5(arr, aim));
		end = System.currentTimeMillis();
		System.out.print("coins5:");
		System.out.println((end - start) + "ms");
	}
	public static int coins1(int[] arr,int aim) {
		if (arr == null || aim < 0 || arr.length == 0) {
			return 0;
		}
		return process1(arr, 0, aim);
	}

	public static int process1(int[] arr,int index, int aim) {
		int res = 0;
		if (index == arr.length) {
			return res = aim == 0 ? 1 : 0;
		}else {
			for (int i = 0; arr[index] * i <= aim; i++) {
				res += process1(arr, index + 1, aim - arr[index] * i);
			}
		}
		return res;
	}
//	index [0,arr.length] aim[0,aim]
	public static int coins2(int[] arr,int aim) {
		if (arr == null || aim < 0 || arr.length == 0) {
			return 0;
		}
		int[][] map = new int[arr.length + 1][aim + 1];
		return process2(arr, 0, aim,map);
	}
	public static int process2(int[] arr,int index, int aim, int[][] map) {
		int res = 0;
		if (index == arr.length) {
			return res = aim == 0 ? 1 : 0;
		}else {
//			mapValue == 0 没有计算，mapValue == -1计算了,
			int mapValue = 0;
			for (int i = 0; arr[index] * i <= aim; i++) {
				mapValue = map[index + 1][aim - arr[index] * i];
//				如果计算了
				if (mapValue != 0) {
					res += mapValue == -1 ? 0 : mapValue;
				}else {
					res += process2(arr, index + 1, aim - arr[index] * i, map);
				}
			}
		}
		map[index][aim] = res == 0 ? -1 : res;
		return res;
	}
	public static int coins3(int[] arr,int aim) {
		if (arr == null || aim < 0 || arr.length == 0) {
			return 0;
		}
		int[][] dp = new int[arr.length][aim + 1];
		for (int i = 0; i < arr.length; i++) {
			dp[i][0] = 1;
		}
		for (int j = 1; j * arr[0] <= aim; j++) {
			dp[0][arr[0] * j] = 1;
		}
		int sum = 0;
		for (int i = 1; i < dp.length; i++) {
			for (int j = 1; j <= aim; j++) {
				sum = 0;
				for (int k = 0; j - k * arr[i] >= 0; k++) {
					sum += dp[i - 1][j - k * arr[i]];
				}
				dp[i][j] = sum;
			}
		}
		return dp[arr.length - 1][aim];
	}
//	时间复杂度O(N * aim)
	public static int coins4(int[] arr,int aim) {
		if (arr == null || aim < 0 || arr.length == 0) {
			return 0;
		}
		int[][] dp = new int[arr.length][aim + 1];
		for (int i = 0; i < arr.length; i++) {
			dp[i][0] = 1;
		}
		for (int j = 1; j * arr[0] <= aim; j++) {
			dp[0][arr[0] * j] = 1;
		}
		for (int i = 1; i < dp.length; i++) {
			for (int j = 1; j <= aim; j++) {
				dp[i][j] = dp[i - 1][j];
				dp[i][j] +=  j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
			}
		}
		return dp[arr.length - 1][aim];
	}
//	空间压缩
	public static int coins5(int[] arr,int aim) {
		if (arr == null || aim < 0 || arr.length == 0) {
			return 0;
		}
		int[] dp = new int[aim + 1];
		for (int i = 0; i < arr.length; i++) {
			dp[0] = 1;
		}
		for (int j = 1; j * arr[0] <= aim; j++) {
			dp[arr[0] * j] = 1;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = 1; j <= aim; j++) {
				dp[j] +=  j - arr[i] >= 0 ? dp[j - arr[i]] : 0;
			}
		}
		return dp[aim];
	}
}

一维动态规划

package 递归_动态规划;

public class 机器人到达指定位置方法数 {

	public static void main(String[] args) {
		int N = 7;
		int M = 4;
		int K = 9;
		int P = 5;
		System.out.println(way1(N, M, K, P));
		System.out.println(way2(N, M, K, P));
		System.out.println(way3(N, M, K, P));
	} 
//	N个格子，还可以走rest步，当前在cur位置
	public static int walk(int N ,int cur, int rest, int P){
//		没有步数了，如在P位置，则是一种方法，否则为0
		if (rest == 0) {
			return cur == P ? 1 : 0;
		}
//		如果还有步数
//		如果在1位置，只能右移，
		if (cur == 1) {
			return walk(N, 2, rest - 1, P);
		}
//		如果在N位置，只能左移
		if (cur == N) {
			return walk(N, N - 1, rest - 1, P);
		}
//		在中间位置,左移或者右移
		return walk(N, cur - 1, rest - 1, P) + walk(N, cur + 1, rest - 1, P);
	}
	public static int way1(int N ,int M, int K, int P) {
		if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
			return 0;
		}
		return walk(N, M, K, P);
	}
	public static int way2(int N ,int M, int K, int P) {
		if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
			return 0;
		}
		int[][] dp = new int[K + 1][N + 1];
		dp[0][P] = 1;
		for (int i = 1; i < dp.length; i++) {
			for (int j = 1; j < dp[0].length; j++) {
				if (j == 1) {
					dp[i][j] = dp[i - 1][2];
				}else if (j == N ) {
					dp[i][j] = dp[i - 1][N - 1];
				}else {
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
				}
			}
		}
		printArray(dp);
		return dp[K][M];
	}
	public static int way3(int N ,int M, int K, int P) {
		if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
			return 0;
		}
		int[] arr = new int[N + 1];
		arr[P] = 1;
		for (int i = 1; i <= K; i++) {
			int LeftUp = arr[1];
			for (int j = 1; j < arr.length; j++) {
				int temp = arr[j];
				if (j == 1) {
					arr[j] = arr[2];
				}else if (j == arr.length - 1) {
					arr[j] = LeftUp;
				}else {
					arr[j] = LeftUp + arr[j + 1];
				}
				LeftUp = temp;
			}
			for (int j = 0; j < arr.length; j++) {
				System.out.print(arr[j] + " ");
			}
			System.out.println();
		}
		return arr[M];
	}
	static void printArray(int[][] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}
	}
}