斐波那契数列

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));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

递归法存在很多重复计算，所以用迭代法更好

数组

数组的创建

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);
}
1
2
3
4

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

【1，2，3，4，5】
1

模拟
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);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

数组是引用类型

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
2
3
4
5
6

[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]
1
2

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));
    }
1
2
3
4
5
6

[0, 0, 0, 1, 3, 5, 7, 91, 11, 22, 44, 88, 18]
1

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
2
3
4
5
6

[1, 3, 5, 7, 91, 11, 22, 44, 88, 18, 29, 17, 14]
[5, 7, 91]
1
2

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
2
3
4
5
6
7
8
9
10

[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]
1
2
3
4
5

改变副本不影响原数组

二分查找数组中指定元素

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

[1, 3, 5, 7, 11, 14, 17, 18, 22, 29, 44, 88, 91]
1
1
2

二分查找比遍历效率高，查找一次丢掉一半数据

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);
    }
1
2
3
4
5
6
7
8

[0, 0, -1, -1, -1, 0, 0, 0, 0, 0]
true
1
2

快捷键：
源码：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));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1

二维数组

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));
    }
1
2
3
4
5
6

[[0, 0, 0], [0, 0, 0, 0]]
1

二维数组不能省略行，可以省略列

public static void main(String[] args) {
        int[][] array1=new int[2][3];
        System.out.println(Arrays.deepToString(array1));
    }
1
2
3
4

[[0, 0, 0], [0, 0, 0]]
1

打印数组元素
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]));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

0 0 0 
0 0 0 

0 0 0 
0 0 0 

[I@1b6d3586
//第一行的地址
[0, 0, 0]
//第一行所有元素
1
2
3
4
5
6
7
8
9
10