斐波那契数列
1.递归
public class Test {
public static int fib(int n){
if(n==1||n==2){
return 1;
}
return fib(n-1)+fib(n-2);
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
System.out.println(fib(n));
}
}
2.迭代
public class Test {
public static int fib(int n){
int f1=1;
int f2=1;
int f3=1;
for (int i = 3; i <=n; i++) {
f3=f1+f2;
f1=f2;
f2=f3;
}
return f3;
}
public static void main11(String[] args) {
System.out.println(fib(1));
System.out.println(fib(2));
System.out.println(fib(3));
System.out.println(fib(4));
System.out.println(fib(5));
}
}
递归法存在很多重复计算，所以用迭代法更好
数组
数组的创建
int[] array1 = new int[10];
如果没有对数组进行初始化，数组中元素有其默认值
char -> /u0000
boolean -> false
数组的初始化
动态初始化
int[] array = new int[10];
int[] array1;
array1 = new int[10];
静态初始化
int[] array1 = new int[]{0,1,2,3,4,5,6,7,8,9};
int[] array1 = {0,1,2,3,4,5,6,7,8,9};//整体初始化，只有一次机会
int[] array2;
array2 = new int[]{10, 20, 30};
//分开写new int[]不能省略
数组长度
数组对象.length
//array.length
遍历数组
可以使用 for-each 遍历数组
int[] array = {1, 2, 3};
for (int x : array) {
System.out.println(x);
}
for-each这种方法拿不到数组下标
Arrays.操作数组相关的工具类
数组转字符串
int[] array=new int[]{1,2,3,4,5};
String ret=Arrays.toString(array);
System.out.println(ret);
【1，2，3，4，5】
模拟
public static String myToString(int[] tmp){
//assert tmp!=null;
if(tmp==null){
return "null";
}
String ret="[";
for (int i = 0; i < tmp.length; i++) {
ret+=tmp[i];
if(i<tmp.length-1){
ret+=",";
}
}
ret+="]";
return ret;
}
public static void main(String[] args) {
int[]array={1,2,3,4};
String s=myToString(array);
System.out.println(s);
}
数组是引用类型
func1修改了形参的指向
这里main方法结束之后引用变量array存的地址值会被销毁，空间被回收，那么{1，2，3，4}不被array引用，如果{1，2，3，4}也没有被其他引用变量引用，那么{1，2，3，4}在堆区上的空间会被JVM回收。
数组拷贝
Arrays.copyOf()
public static void main(String[] args) {
int[] array1={1,3,5,7,91,11,22,44,88,18,29,17,14};
int[] array2=Arrays.copyOf(array1,2*array1.length);
System.out.println(Arrays.toString(array1));
System.out.println(Arrays.toString(array2));
}
[1, 3, 5, 7, 91, 11, 22, 44, 88, 18, 29, 17, 14]
[1, 3, 5, 7, 91, 11, 22, 44, 88, 18, 29, 17, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
将指定源数组中的数组从指定位置复制到目标数组的指定位置,length是拷贝长度。
public static void main(String[] args) {
int[] array1={1,3,5,7,91,11,22,44,88,18,29,17,14};
int[] copy=new int[array1.length];
System.arraycopy(array1,0,copy,3,array1.length-3);
System.out.println(Arrays.toString(copy));
}
[0, 0, 0, 1, 3, 5, 7, 91, 11, 22, 44, 88, 18]
Arrays.copyOfRange(int[] original, int from, int to)
将指定数组的指定范围复制到新数组中。
public static void main(String[] args) {
int[] array1={1,3,5,7,91,11,22,44,88,18,29,17,14};
int[] copy=Arrays.copyOfRange(array1,2,5);//[2,5)
System.out.println(Arrays.toString(array1));
System.out.println(Arrays.toString(copy));
}
[1, 3, 5, 7, 91, 11, 22, 44, 88, 18, 29, 17, 14]
[5, 7, 91]
array.clone();
public static void main(String[] args) {
int[] array={1,3,5,7,91,11,22,44,88,18,29,17,14};
int[] copy=array.clone();//产生一个副本object
System.out.println(Arrays.toString(array));
System.out.println(Arrays.toString(copy));
System.out.println("===============");
copy[0]=99;
System.out.println(Arrays.toString(array));
System.out.println(Arrays.toString(copy));
}
[1, 3, 5, 7, 91, 11, 22, 44, 88, 18, 29, 17, 14]
[1, 3, 5, 7, 91, 11, 22, 44, 88, 18, 29, 17, 14]
===============
[1, 3, 5, 7, 91, 11, 22, 44, 88, 18, 29, 17, 14]
[99, 3, 5, 7, 91, 11, 22, 44, 88, 18, 29, 17, 14]
改变副本不影响原数组
二分查找数组中指定元素
Arrays.sort();
底层快排，结果为升序
public static int binary(int[] array,int k){
int left = 0;
int right = array.length-1;
while (left <= right) {
int mid = (left + right) >>> 1;
if(array[mid] < k) {
left = mid +1;
}else if(array[mid] > k) {
right = mid-1;
}else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] array = {1,3,5,7,91,11,22,44,88,18,29,17,14};
Arrays.sort(array);
System.out.println(Arrays.toString(array));
int index=binary(array,3);
System.out.println(index);
}
[1, 3, 5, 7, 11, 14, 17, 18, 22, 29, 44, 88, 91]
1
二分查找比遍历效率高，查找一次丢掉一半数据
Arrays.fill(int[] a, int fromIndex, int toIndex, int val)
将指定的int值分配给指定的int数组的指定范围的每个元素。
Arrays.equals(int[] a, int[] a2)
如果两个指定的int数组彼此相等 ，则返回 true 。
public static void main(String[] args) {
int[] array=new int[10];
Arrays.fill(array,2,5,-1);//[2,5)
System.out.println(Arrays.toString(array));
int[] array2=array;
boolean flg=Arrays.equals(array,array2);
System.out.println(flg);
}
[0, 0, -1, -1, -1, 0, 0, 0, 0, 0]
true
快捷键：
源码：ctrl+b或ctrl+鼠标左键
方法索引：alt+7
数组冒泡排序
import java.util.Arrays;
public class Test {
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
boolean flag=false;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j]>array[j+1]){
int tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
flag=true;
}
}
if(flag==false){//说明这一趟下来没有发生交换，说明数据已经有序了
return;
}
}
}
public static void main(String[] args) {
int[] array={1,7,3,6,5,9,2,8,0,4};
bubbleSort(array);
System.out.println(Arrays.toString(array));
}
}
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
二维数组
public static void main(String[] args) {
int[][]array1=new int[2][];
array1[0]=new int[3];
array1[1]=new int[4];
System.out.println(Arrays.deepToString(array1));
}
[[0, 0, 0], [0, 0, 0, 0]]
二维数组不能省略行，可以省略列
public static void main(String[] args) {
int[][] array1=new int[2][3];
System.out.println(Arrays.deepToString(array1));
}
[[0, 0, 0], [0, 0, 0]]
打印数组元素
public static void main(String[] args) {
int[][]array1=new int[2][3];
for (int i = 0; i < array1.length; i++) {
for (int j = 0; j < array1[i].length; j++) {
System.out.print(array1[i][j]+" ");
}
System.out.println();
}
System.out.println();
for (int[]arr:
array1) {
for (int x:
arr) {
System.out.print(x+" ");
}
System.out.println();
}
System.out.println();
System.out.println(array1[0]);
System.out.println(Arrays.toString(array1[0]));
}
0 0 0
0 0 0
0 0 0
0 0 0
[I@1b6d3586
//第一行的地址
[0, 0, 0]
//第一行所有元素