基础复习

发表于

基础复习咯.

简单算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package com.dottie.interview;

import java.util.Arrays;

public class Algorithm {

    /**
     * 冒泡排序
     */
    public static void bubbleSort() {
        int[] arr = {2, 8, 9, 3, 4, 6, 5, 7, 1};
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                int temp = 0;
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) break;
        }
        System.out.println(Arrays.toString(arr));
        Arrays.stream(arr).forEach(e -> System.out.print(e + "--"));
    }

    /**
     * 插入排序
     */
    public static void directInsertSort() {
        int[] arr = {2, 8, 9, 3, 4, 6, 5, 7, 1};
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                int temp = 0;
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
        Arrays.stream(arr).forEach(e -> System.out.print(e + "**"));
    }

    /**
     * 前提: 要排序的集合已经排好序了.
     * 折半查找, 返回在数组中的下标
     */
    public static int halfSearch(int key) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        bubbleSort();
        System.out.println();

        directInsertSort();
        System.out.println();

        int r = halfSearch(4);
        System.out.println(r);
        int r1 = halfSearch(2);
        System.out.println(r1);
    }
}

集合排序

测试的实体类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package com.dottie.interview;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.experimental.Accessors;

// 这里使用的小工具(lombok) 具体使用自行百度咯.
@Data
@Accessors(chain = true)
@AllArgsConstructor
@NoArgsConstructor
public class Student implements Comparable<Student>{

    private String name;
    private Integer age;

    @Override
    public int compareTo(Student o) {
        return this.getAge() - o.getAge();
    }
}

/**
 * 复习:
 * hashcode: 返回对象的散列码
 * equals: 比较两个对象是否相同; object中默认的比较就是他们的引用是否相同: this == obj
 *         可以自定义该方法: 如: 只要name相同就返回true. this.name == obj.name等等
 *
 *
 * 重写equals方法时, 必须重写hashcode.
 * equals和hashcode的区别:
 * 1. hashcode不同, 对象一定不相同,
 * 2. 但是hashcode相同, 对象可以相同,也可能不同, 这个时候就要比较equals方法.
 * 3. 总之: equals方法相同, 则两个对象(hashcode)一定相同, equals方法不同, hashcode可以相同, 也可以不同.
 */

各种排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
package com.dottie.interview;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class CollectionSort {
    private static Student[] stuArr;

    // 利用静态代码块; 类加载时执行, 只执行一次, 通常用来初始化数据.
    static {
        int stuNum = 10;
        stuArr = new Student[stuNum];
        for (int i = 0; i < stuNum; i++) {
            Student student1 = new Student().setName("dottie" + i).setAge(i + 20);
            stuArr[i] = student1;
        }
        System.out.println("原始数据");
        Arrays.stream(stuArr).forEach(e -> System.out.println(e));
        System.out.println("**********************");
    }


    public static void main(String[] args) {

        /**
         * 数组排序方式一, 自定义比较器Comparator, 灵活
         */
        Arrays.sort(stuArr, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o2.getAge() - o1.getAge();
            }
        });
        Arrays.stream(stuArr).forEach(e -> System.out.println(e));
        System.out.println("**********************");

        /**
         * 方式二, 在实体类中实现Comparable接口
         */
        Arrays.sort(stuArr);
        Arrays.stream(stuArr).forEach(e -> System.out.println(e));
        System.out.println("**********************");

        /**
         * 使用java8中的lambda时. 要先将原来的数组转换成集合Collection类. 或者利用Arrays工具方法,转成stream
         * Arrays.stream(stuArr).sorted((Student s1, Student s2) -> s2.getAge() - s1.getAge());
         * Arrays.asList(stuArr).sort((Student s1, Student s2) -> s2.getAge() - s1.getAge());
         */

        /**
         * 方式三: 利用java8新特性,
         * 单个属性排序.
         */
        Arrays.asList(stuArr).sort((Student s1, Student s2) -> s2.getAge() - s1.getAge());
        Arrays.stream(stuArr).forEach(e -> System.out.println(e));
        System.out.println("**********************");

        /**
         * 方式三: 利用java8新特性,
         * 多个属性排序. 也可以反序Comparator.comparing().reversed()
         * 当然也可以自定义静态方法来比较Stduent::compareByNameThenAge
         * JAVA8还可以提供使用Lambda表达式的静态类型引用，我们在Stduent类增加一个静态比较方法，如下：

             public static int compareByNameThenAge(Stduent h1, Stduent h2) {
             if (h1.getName().equals(h2.getName())) {
             return Integer.compare(h1.getAge(), h2.getAge());
             }
             return h1.getName().compareTo(h2.getName());
             }

         然后就可以在集合students.sort使用这个引用
         students.sort(Stduent::compareByNameThenAge);
         */
        Arrays.asList(stuArr).sort(Comparator.comparing(Student::getAge).thenComparing(Student::getName));
        Arrays.stream(stuArr).forEach(e -> System.out.println(e));
        System.out.println("**********************");


        /**
         * 当然了Collections工具类, 也提供了类似的sort方法
         */
        Collections.sort(Arrays.asList(stuArr), new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getAge() - o2.getAge();
            }
        });
        System.out.println(Arrays.asList(stuArr));
        System.out.println("**********************");

        /**
         * 也可以使用java8新特性
         */
        Collections.sort(Arrays.asList(stuArr), Comparator.comparing(Student::getAge).reversed());
        System.out.println(Arrays.asList(stuArr));
        System.out.println("**********************");
    }

}