• JAVA算法和数据结构

    一、Arrays类

    1.1 Arrays基本使用

    我们先认识一下Arrays是干什么用的，Arrays是操作数组的工具类，它可以很方便的对数组中的元素进行遍历、拷贝、排序等操作。

    下面我们用代码来演示一下：遍历、拷贝、排序等操作。需要用到的方法如下

    1. public class ArraysTest1 {
    2.     public static void main(String[] args) {
    3.         // 1、public static String toString(类型[] arr): 返回数组的内容
    4.         int[] arr = {10, 20, 30, 40, 50, 60};
    5.         System.out.println(Arrays.toString(arr));
    6. ​
    7.         // 2、public static 类型[] copyOfRange(类型[] arr, 起始索引, 结束索引) ：拷贝数组（指定范围，包前不包后）
    8.         int[] arr2 = Arrays.copyOfRange(arr, 1, 4);
    9.         System.out.println(Arrays.toString(arr2));
    10. ​
    11.         // 3、public static copyOf(类型[] arr, int newLength)：拷贝数组，可以指定新数组的长度。
    12.         int[] arr3 = Arrays.copyOf(arr, 10);
    13.         System.out.println(Arrays.toString(arr3));
    14. ​
    15.         // 4、public static setAll(double[] array, IntToDoubleFunction generator)：把数组中的原数据改为新数据又存进去。
    16.         double[] prices = {99.8, 128, 100};
    17.         //                  0     1    2
    18.         // 把所有的价格都打八折，然后又存进去。
    19.         Arrays.setAll(prices, new IntToDoubleFunction() {
    20.             @Override
    21.             public double applyAsDouble(int value) {
    22.                 // value = 0  1  2
    23.                 return prices[value] * 0.8;
    24.             }
    25.         });
    26.         System.out.println(Arrays.toString(prices));
    27. ​
    28.         // 5、public static void sort(类型[] arr)：对数组进行排序(默认是升序排序)
    29.         Arrays.sort(prices);
    30.         System.out.println(Arrays.toString(prices));
    31.     }
    32. }

    1.2 Arrays操作对象数组

    刚才我们使用Arrays操作数组时，数组中存储存储的元素是int类型、double类型，是可以直接排序的，而且默认是升序排列。

    如果数组中存储的元素类型是自定义的对象，如何排序呢？接下来，我们就学习一下Arrays如何对对象数组进行排序。

    首先我们要准备一个Student类，代码如下：

    1. public class Student implements Comparable{
    2.     private String name;
    3.     private double height;
    4.     private int age;
    5.     
    6.     public Student(String name, double height, int age) {
    7.         this.name = name;
    8.         this.height = height;
    9.         this.age = age;
    10.     }
    11. ​
    12.     @Override
    13.     public String toString() {
    14.         return "Student{" +
    15.                 "name='" + name + '\'' +
    16.                 ", height=" + height +
    17.                 ", age=" + age +
    18.                 '}';
    19.     }
    20. }
    21. ​

    然后再写一个测试类，往数组中存储4个学生对象，代码如下。此时，运行代码你会发现是会报错的。

    1. public class ArraysTest2 {
    2.     public static void main(String[] args) {
    3.         // 目标：掌握如何对数组中的对象进行排序。
    4.         Student[] students = new Student[4];
    5.         students[0] = new Student("蜘蛛精", 169.5, 23);
    6.         students[1] = new Student("紫霞", 163.8, 26);
    7.         students[2] = new Student("紫霞", 163.8, 26);
    8.         students[3] = new Student("至尊宝", 167.5, 24);
    9. ​
    10.         // 1、public static void sort(类型[] arr)：对数组进行排序。
    11.         Arrays.sort(students);
    12.         System.out.println(Arrays.toString(students));
    13.     }
    14. }

    上面的代码为什么会报错呢？因为Arrays根本就不知道按照什么规则进行排序。为了让Arrays知道按照什么规则排序，我们有如下的两种办法。

    • 排序方式1：让Student类实现Comparable接口，同时重写compareTo方法。Arrays的sort方法底层会根据compareTo方法的返回值是正数、负数、还是0来确定谁大、谁小、谁相等。代码如下：

    1. public class Student implements Comparable{
    2.     private String name;
    3.     private double height;
    4.     private int age;
    5.     
    6.     //...get、set、空参数构造方法、有参数构造方法...自己补全
    7. ​
    8.     // 指定比较规则
    9.     // this  o
    10.     @Override
    11.     public int compareTo(Student o) {
    12.         // 约定1：认为左边对象 大于 右边对象 请您返回正整数
    13.         // 约定2：认为左边对象 小于 右边对象 请您返回负整数
    14.         // 约定3：认为左边对象 等于 右边对象 请您一定返回0
    15.         /* if(this.age > o.age){
    16.             return 1;
    17.         }else if(this.age < o.age){
    18.             return -1;
    19.         }
    20.         return 0;*/
    21. ​
    22.         //上面的if语句，也可以简化为下面的一行代码
    23.         return this.age - o.age; // 按照年龄升序排列
    24.         // return o.age - this.age; // 按照年龄降序排列
    25.     }
    26.     
    27.     @Override
    28.     public String toString() {
    29.         return "Student{" +
    30.                 "name='" + name + '\'' +
    31.                 ", height=" + height +
    32.                 ", age=" + age +
    33.                 '}';
    34.     }
    35. }

    • 排序方式2：在调用Arrays.sort(数组,Comparator比较器);时，除了传递数组之外，传递一个Comparator比较器对象。Arrays的sort方法底层会根据Comparator比较器对象的compare方法方法的返回值是正数、负数、还是0来确定谁大、谁小、谁相等。代码如下

    1. public class ArraysTest2 {
    2.     public static void main(String[] args) {
    3.         // 目标：掌握如何对数组中的对象进行排序。
    4.         Student[] students = new Student[4];
    5.         students[0] = new Student("蜘蛛精", 169.5, 23);
    6.         students[1] = new Student("紫霞", 163.8, 26);
    7.         students[2] = new Student("紫霞", 163.8, 26);
    8.         students[3] = new Student("至尊宝", 167.5, 24);
    9. ​
    10.         // 2、public static  void sort(T[] arr, Comparator c)
    11.         // 参数一：需要排序的数组
    12.         // 参数二：Comparator比较器对象（用来制定对象的比较规则）
    13.         Arrays.sort(students, new Comparator() {
    14.             @Override
    15.             public int compare(Student o1, Student o2) {
    16.                 // 制定比较规则了：左边对象 o1   右边对象 o2
    17.                 // 约定1：认为左边对象 大于 右边对象 请您返回正整数
    18.                 // 约定2：认为左边对象 小于 右边对象 请您返回负整数
    19.                 // 约定3：认为左边对象 等于 右边对象 请您一定返回0
    20. //                if(o1.getHeight() > o2.getHeight()){
    21. //                    return 1;
    22. //                }else if(o1.getHeight() < o2.getHeight()){
    23. //                    return -1;
    24. //                }
    25. //                return 0; // 升序
    26.                  return Double.compare(o1.getHeight(), o2.getHeight()); // 升序
    27.                 // return Double.compare(o2.getHeight(), o1.getHeight()); // 降序
    28.             }
    29.         });
    30.         System.out.println(Arrays.toString(students));
    31.     }
    32. }

    二、Lambda表达式

    JDK8新增的一种语法形式，叫做Lambda表达式。作用：用于简化匿名内部类代码的书写。

    2.1 Lambda表达式基本使用

    怎么去简化呢？Lamdba是有特有的格式的，按照下面的格式来编写Lamdba。

    (被重写方法的形参列表) -> {
    被重写方法的方法体代码;
}

    需要给说明一下的是，在使用Lambda表达式之前，必须先有一个接口，而且接口中只能有一个抽象方法。（注意：不能是抽象类，只能是接口）

    像这样的接口，我们称之为函数式接口，只有基于函数式接口的匿名内部类才能被Lambda表达式简化。

    public interface Swimming{
    void swim();
}

    有了以上的Swimming接口之后，接下来才能再演示，使用Lambda表达式，简化匿名内部类书写。

    1. public class LambdaTest1 {
    2.     public static void main(String[] args) {
    3.         // 目标：认识Lambda表达式.
    4.         //1.创建一个Swimming接口的匿名内部类对象
    5. 		Swimming s = new Swimming(){
    6.              @Override
    7.              public void swim() {
    8.                  System.out.println("学生快乐的游泳~~~~");
    9.              }
    10.          };
    11.          s.swim();
    12. 		
    13.         //2.使用Lambda表达式对Swimming接口的匿名内部类进行简化
    14.         Swimming s1 = () -> {
    15.               System.out.println("学生快乐的游泳~~~~");
    16.         };
    17.         s1.swim();
    18.     }
    19. }

    好的，我们现在已经知道Lamdba表达式可以简化基于函数式接口的匿名内部类的书写。接下来，我们可以把刚才使用Arrays方法时的代码，使用Lambda表达式简化一下了。

    1. public class LambdaTest2 {
    2.     public static void main(String[] args) {
    3.         // 目标：使用Lambda简化函数式接口。
    4.         double[] prices = {99.8, 128, 100};
    5.         //1.把所有元素*0.8: 先用匿名内部类写法
    6.         Arrays.setAll(prices, new IntToDoubleFunction() {
    7.             @Override
    8.             public double applyAsDouble(int value) {
    9.                 // value = 0  1  2
    10.                 return prices[value] * 0.8;
    11.             }
    12.         });
    13.         //2.把所有元素*0.8: 改用Lamdba表达式写法
    14.         Arrays.setAll(prices, (int value) -> {
    15.                 return prices[value] * 0.8;
    16.         });
    17. ​
    18.         System.out.println(Arrays.toString(prices));
    19.         System.out.println("-----------------------------------------------");
    20.         
    21.         Student[] students = new Student[4];
    22.         students[0] = new Student("蜘蛛精", 169.5, 23);
    23.         students[1] = new Student("紫霞", 163.8, 26);
    24.         students[2] = new Student("紫霞", 163.8, 26);
    25.         students[3] = new Student("至尊宝", 167.5, 24);
    26.         //3.对数组中的元素按照年龄升序排列: 先用匿名内部类写法
    27.         Arrays.sort(students, new Comparator() {
    28.             @Override
    29.             public int compare(Student o1, Student o2) {
    30.                 return Double.compare(o1.getHeight(), o2.getHeight()); // 升序
    31.             }
    32.         });
    33.         //4.对数组中的元素按照年龄升序排列: 改用Lambda写法
    34.         Arrays.sort(students, (Student o1, Student o2) -> {
    35.                 return Double.compare(o1.getHeight(), o2.getHeight()); // 升序
    36.         });
    37.         System.out.println(Arrays.toString(students));
    38.     }
    39. }

    2.2 Lambda表达式省略规则

    Java觉得代码还不够简单，于是还提供了Lamdba表达式的几种简化写法。具体的简化规则如下

    1.Lambda的标准格式
    (参数类型1 参数名1, 参数类型2 参数名2)->{
        ...方法体的代码...
        return 返回值;
    }
​
2.在标准格式的基础上()中的参数类型可以直接省略
    (参数名1, 参数名2)->{
        ...方法体的代码...
        return 返回值;
    }
    
3.如果{}总的语句只有一条语句，则{}可以省略、return关键字、以及最后的“;”都可以省略
    (参数名1, 参数名2)-> 结果
    
4.如果()里面只有一个参数，则()可以省略
    (参数名)->结果

    接下来从匿名内部类开始、到Lambda标准格式、再到Lambda简化格式，一步一步来简化一下。

    1. public class LambdaTest2 {
    2.     public static void main(String[] args) {
    3.         // 目标：使用Lambda简化函数式接口。
    4.         double[] prices = {99.8, 128, 100};
    5.         //1.对数组中的每一个元素*0.8: 匿名内部类写法
    6.         Arrays.setAll(prices, new IntToDoubleFunction() {
    7.             @Override
    8.             public double applyAsDouble(int value) {
    9.                 // value = 0  1  2
    10.                 return prices[value] * 0.8;
    11.             }
    12.         });
    13.         //2.需求：对数组中的每一个元素*0.8,使用Lambda表达式标准写法
    14.         Arrays.setAll(prices, (int value) -> {
    15.                 return prices[value] * 0.8;
    16.         });
    17.         //3.使用Lambda表达式简化格式1——省略参数类型
    18.         Arrays.setAll(prices, (value) -> {
    19.             return prices[value] * 0.8;
    20.         });
    21.         //4.使用Lambda表达式简化格式2——省略()
    22.         Arrays.setAll(prices, value -> {
    23.             return prices[value] * 0.8;
    24.         });
    25.         //5.使用Lambda表达式简化格式3——省略{}
    26.         Arrays.setAll(prices, value -> prices[value] * 0.8 );
    27. ​
    28.         System.out.println(Arrays.toString(prices));
    29.         
    30.         System.out.println("------------------------------------
    31. ​
    32.         Student[] students = new Student[4];
    33.         students[0] = new Student("蜘蛛精", 169.5, 23);
    34.         students[1] = new Student("紫霞", 163.8, 26);
    35.         students[2] = new Student("紫霞", 163.8, 26);
    36.         students[3] = new Student("至尊宝", 167.5, 24);
    37.         
    38.         //1.使用匿名内部类
    39.         Arrays.sort(students, new Comparator() {
    40.             @Override
    41.             public int compare(Student o1, Student o2) {
    42.                 return Double.compare(o1.getHeight(), o2.getHeight()); // 升序
    43.             }
    44.         });
    45.         //2.使用Lambda表达式表达式——标准格式
    46.         Arrays.sort(students, (Student o1, Student o2) -> {
    47.                 return Double.compare(o1.getHeight(), o2.getHeight()); // 升序
    48.         });
    49.         //3.使用Lambda表达式表达式——省略参数类型
    50.         Arrays.sort(students, ( o1,  o2) -> {
    51.             return Double.compare(o1.getHeight(), o2.getHeight()); // 升序
    52.         });
    53.         //4.使用Lambda表达式表达式——省略{}
    54.         Arrays.sort(students, ( o1,  o2) -> Double.compare(o1.getHeight(), o2.getHeight()));
    55. ​
    56. ​
    57.         System.out.println(Arrays.toString(students));
    58.     }
    59. }

    三、JDK8新特性（方法引用）

    我们知道Lambda是用来简化匿名代码的书写格式的，而方法引用是用来进一步简化Lambda表达式的，它简化的更加过分。

    到这里有小伙伴可能就想慰问Java爸爸了：“之前的代码挺好的呀！好不容易学会，你又来搞这些，把我都搞晕了。“ 说句大实话，确实有这样的问题，学习新的东西肯定会增加我们的学习成本，从心理上来说多少是有写抗拒的。但是从另一个角度想，一旦我们学会了，会大大简化我们的代码书写，提高我们编写代码的效率，而且这些新的语法都是有前提条件的，遇到的时候就简化得了。再退一步想，就算你没有学会，还是用以前的办法一点问题也没有。

    3.1 静态方法引用

    我们先学习静态方法的引用，还是用之前Arrays代码来做演示。现在准备好下面的代码

    1. public class Test1 {
    2.     public static void main(String[] args) {
    3.         Student[] students = new Student[4];
    4.         students[0] = new Student("蜘蛛精", 169.5, 23);
    5.         students[1] = new Student("紫霞", 163.8, 26);
    6.         students[2] = new Student("紫霞", 163.8, 26);
    7.         students[3] = new Student("至尊宝", 167.5, 24);
    8. ​
    9.         // 原始写法：对数组中的学生对象，按照年龄升序排序
    10.         Arrays.sort(students, new Comparator() {
    11.             @Override
    12.             public int compare(Student o1, Student o2) {
    13.                 return o1.getAge() - o2.getAge(); // 按照年龄升序排序
    14.             }
    15.         });
    16. ​
    17.         // 使用Lambda简化后的形式
    18.         Arrays.sort(students, (o1, o2) -> o1.getAge() - o2.getAge());
    19.     }
    20. }

    现在，我想要把下图中Lambda表达式的方法体，用一个静态方法代替

    准备另外一个类CompareByData类，用于封装Lambda表达式的方法体代码；

    1. public class CompareByData {
    2.     public static int compareByAge(Student o1, Student o2){
    3.         return o1.getAge() - o2.getAge(); // 升序排序的规则
    4.     }
    5. }

    现在我们就可以把Lambda表达式的方

    1. //静态方法引用：类名::方法名
    2. Arrays.sort(students, CompareByData::compareByAge);

    法体代码，改为下面的样子

    Arrays.sort(students, (o1, o2) -> CompareByData.compareByAge(o1, o2));

    Java为了简化上面Lambda表达式的写法，利用方法引用可以改进为下面的样子。实际上就是用类名调用方法，但是把参数给省略了。这就是静态方法引用

     

    3.2 实例方法引用
     

    现在，我想要把下图中Lambda表达式的方法体，用一个实例方法代替。
     

     

    在CompareByData类中，再添加一个实例方法，用于封装Lambda表达式的方法体
     

     

    接下来，我们把Lambda表达式的方法体，改用对象调用方法
     

     
 
    CompareByData compare = new CompareByData();
Arrays.sort(students, (o1, o2) -> compare.compareByAgeDesc(o1, o2)); // 降序
     

     

    最后，再将Lambda表达式的方法体，直接改成方法引用写法。实际上就是用类名调用方法，但是省略的参数。这就是实例方法引用
     

     
 
    CompareByData compare = new CompareByData();
Arrays.sort(students, compare::compareByAgeDesc); // 降序

     

     

     

    3.2 特定类型的方法引用
     

     

     
 
    Java约定：
    如果某个Lambda表达式里只是调用一个实例方法，并且前面参数列表中的第一个参数作为方法的主调，    后面的所有参数都是作为该实例方法的入参时，则就可以使用特定类型的方法引用。
格式：
    类型::方法名
     

     

    1. public class Test2 {
    2.     public static void main(String[] args) {
    3.         String[] names = {"boby", "angela", "Andy" ,"dlei", "caocao", "Babo", "jack", "Cici"};
    4.         
    5.         // 要求忽略首字符大小写进行排序。
    6.         Arrays.sort(names, new Comparator() {
    7.             @Override
    8.             public int compare(String o1, String o2) {
    9.                 // 制定比较规则。o1 = "Andy"  o2 = "angela"
    10.                 return o1.compareToIgnoreCase(o2);
    11.             }
    12.         });
    13.         
    14.         //lambda表达式写法
    15.         Arrays.sort(names, ( o1,  o2) -> o1.compareToIgnoreCase(o2) );
    16.         //特定类型的方法引用！
    17.         Arrays.sort(names, String::compareToIgnoreCase);
    18. ​
    19.         System.out.println(Arrays.toString(names));
    20.     }
    21. }
     

     

    3.3 构造器引用
     

    现在，我们准备一个JavaBean类，Car类
     

    1. public class Car {
    2.     private String name;
    3.     private double price;
    4. ​
    5.     public Car() {
    6. ​
    7.     }
    8. ​
    9.     public Car(String name, double price) {
    10.         this.name = name;
    11.         this.price = price;
    12.     }
    13. ​
    14.     public String getName() {
    15.         return name;
    16.     }
    17. ​
    18.     public void setName(String name) {
    19.         this.name = name;
    20.     }
    21. ​
    22.     public double getPrice() {
    23.         return price;
    24.     }
    25. ​
    26.     public void setPrice(double price) {
    27.         this.price = price;
    28.     }
    29. ​
    30.     @Override
    31.     public String toString() {
    32.         return "Car{" +
    33.                 "name='" + name + '\'' +
    34.                 ", price=" + price +
    35.                 '}';
    36.     }
    37. }
     

    因为方法引用是基于Lamdba表达式简化的，所以也要按照Lamdba表达式的使用前提来用，需要一个函数式接口，接口中代码的返回值类型是Car类型
     

     
 
    interface CreateCar{
    Car create(String name, double price);
}
     

     

    最后，再准备一个测试类，在测试类中创建CreateCar接口的实现类对象，先用匿名内部类创建、再用Lambda表达式创建，最后改用方法引用创建。同学们只关注格式就可以，不要去想为什么（语法就是这么设计的）。
     

    1. public class Test3 {
    2.     public static void main(String[] args) {
    3.         // 1、创建这个接口的匿名内部类对象。
    4.         CreateCar cc1 = new CreateCar(){
    5.             @Override
    6.             public Car create(String name, double price) {
    7.                 return new Car(name, price);
    8.             }
    9.         };
    10.         //2、使用匿名内部类改进
    11.         CreateCar cc2 = (name,  price) -> new Car(name, price);
    12. ​
    13.         //3、使用方法引用改进：构造器引用
    14.         CreateCar cc3 = Car::new;
    15.         
    16.         //注意：以上是创建CreateCar接口实现类对象的几种形式而已，语法一步一步简化。
    17.         
    18.         //4、对象调用方法
    19.         Car car = cc3.create("奔驰", 49.9);
    20.         System.out.println(car);
    21.     }
    22. }
     

     

    四、常见算法
     

    1.1 认识算法
     

    接下来，我们认识一下什么是算法。算法其实是解决某个实际问题的过程和方法。比如百度地图给你规划路径，计算最优路径的过程就需要用到算法。再比如你在抖音上刷视频时，它会根据你的喜好给你推荐你喜欢看的视频，这里也需要用到算法。
     

    我们为什么要学习算法呢？主要目的是训练我们的编程思维，还有就是面试的时候，面试官也喜欢问一下算法的问题来考察你的技术水平。最后一点，学习算法是成为一个高级程序员的必经之路。
     

    当然我们现在并不会学习非常复杂的算法，万丈高楼平地起，我们现在只需要学习几种常见的基础算法就可以了。而且Java语言本身就内置了一些基础算法给我们使用，实际上自己也不会去写这些算法。
     

     

     

    1.2 冒泡排序
     

    接下来，我们学习一种算法叫排序算法，它可以价格无序的整数，排列成从小到大的形式（升序），或者从大到小的形式（降序）
     

    排序算法有很多种，我们这里只学习比较简单的两种，一种是冒泡排序，一种是选择排序。学习算法我们先要搞清楚算法的流程，然后再去“推敲“如何写代码。（注意，我这里用的次是推敲，也就是说算法这样的代码并不是一次成型的，是需要反复修改才能写好的）。
     

     

     

    先来学习冒泡排序，先来介绍一下，冒泡排序的流程
     

     
 
    冒泡排序核心思路：每次将相邻的两个元素继续比较
如下图所示：
   第一轮比较 3次
   第二轮比较 2次
   第三轮比较 1次
     

     

     

    1. public class Test1 {
    2.     public static void main(String[] args) {
    3.         // 1、准备一个数组
    4.         int[] arr = {5, 2, 3, 1};
    5. ​
    6.         // 2、定义一个循环控制排几轮
    7.         for (int i = 0; i < arr.length - 1; i++) {
    8.             // i = 0  1  2           【5， 2， 3， 1】    次数
    9.             // i = 0 第一轮            0   1   2         3
    10.             // i = 1 第二轮            0   1             2
    11.             // i = 2 第三轮            0                 1
    12. ​
    13.             // 3、定义一个循环控制每轮比较几次。
    14.             for (int j = 0; j < arr.length - i - 1; j++) {
    15.                 // 判断当前位置的元素值，是否大于后一个位置处的元素值，如果大则交换。
    16.                 if(arr[j] > arr[j+1]){
    17.                     int temp = arr[j + 1];
    18.                     arr[j + 1] = arr[j];
    19.                     arr[j] = temp;
    20.                 }
    21.             }
    22.         }
    23.         System.out.println(Arrays.toString(arr));
    24.     }
    25. }
     

     

    1.2 选择排序
     

    刚才我们学习了冒泡排序，接下来我们学习了另一种排序方法，叫做选择排序。按照我们刚才给大家介绍的算法的学习方式。先要搞清楚算法的流程，再去推敲代码怎么写。
     

    所以我们先分析选择排序算法的流程：选择排序的核心思路是，每一轮选定一个固定的元素，和其他的每一个元素进行比较；经过几轮比较之后，每一个元素都能比较到了。
     

     

    接下来，按照选择排序的流程编写代码
     

    1. ublic class Test2 {
    2.     public static void main(String[] args) {
    3.         // 1、准备好一个数组
    4.         int[] arr = {5, 1, 3, 2};
    5.         //           0  1  2  3
    6. ​
    7.         // 2、控制选择几轮
    8.         for (int i = 0; i < arr.length - 1; i++) {
    9.             // i = 0 第一轮    j = 1 2 3
    10.             // i = 1 第二轮    j = 2 3
    11.             // i = 2 第三轮    j = 3
    12.             // 3、控制每轮选择几次。
    13.             for (int j = i + 1; j < arr.length; j++) {
    14.                 // 判断当前位置是否大于后面位置处的元素值，若大于则交换。
    15.                 if(arr[i] > arr[j]){
    16.                     int temp = arr[i];
    17.                     arr[i] = arr[j];
    18.                     arr[j] = temp;
    19.                 }
    20.             }
    21.         }
    22.         System.out.println(Arrays.toString(arr));
    23.     }
    24. }
     

     

     

    1.3 查找算法
     

    接下来，我们学习一个查找算法叫做二分查找。在学习二分查找之前，我们先来说一下基本查找，从基本查找的弊端，我们再引入二分查找，这样我们的学习也会更加丝滑一下。
     

    先聊一聊基本查找：假设我们要查找的元素是81，如果是基本查找的话，只能从0索引开始一个一个往后找，但是如果元素比较多，你要查找的元素比较靠后的话，这样查找的此处就比较多。性能比较差。
     

     

    再讲二分查找：二分查找的主要特点是，每次查找能排除一般元素，这样效率明显提高。但是二分查找要求比较苛刻，它要求元素必须是有序的，否则不能进行二分查找。
     

    •  
      二分查找的核心思路
       
     

     
 
    第1步：先定义两个变量，分别记录开始索引(left)和结束索引(right)
第2步：计算中间位置的索引，mid = (left+right)/2;
第3步：每次查找中间mid位置的元素，和目标元素key进行比较
        如果中间位置元素比目标元素小，那就说明mid前面的元素都比目标元素小
            此时：left = mid+1
        如果中间位置元素比目标元素大，那说明mid后面的元素都比目标元素大
            此时：right = mid-1
        如果中间位置元素和目标元素相等，那说明mid就是我们要找的位置
            此时：把mid返回       
注意：一搬查找一次肯定是不够的，所以需要把第1步和第2步循环来做，只到left>end就结束，如果最后还没有找到目标元素，就返回-1.
     

     

     

    1. /**
    2.  * 目标：掌握二分查找算法。
    3.  */
    4. public class Test3 {
    5.     public static void main(String[] args) {
    6.         // 1、准备好一个数组。
    7.         int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
    8. ​
    9.         System.out.println(binarySearch(arr, 150));
    10. ​
    11.         System.out.println(Arrays.binarySearch(arr, 81));
    12.     }
    13. ​
    14.     public static int binarySearch(int[] arr, int data){
    15.         // 1、定义两个变量，一个站在左边位置，一个站在右边位置
    16.         int left = 0;
    17.         int right = arr.length - 1;
    18. ​
    19.         // 2、定义一个循环控制折半。
    20.         while (left <= right){
    21.             // 3、每次折半，都算出中间位置处的索引
    22.             int middle = (left + right) / 2;
    23.             // 4、判断当前要找的元素值，与中间位置处的元素值的大小情况。
    24.             if(data < arr[middle]){
    25.                 // 往左边找，截止位置（右边位置） = 中间位置 - 1
    26.                 right = middle - 1;
    27.             }else if(data > arr[middle]){
    28.                 // 往右边找，起始位置（左边位置） = 中间位置 + 1
    29.                 left = middle + 1;
    30.             }else {
    31.                 // 中间位置处的元素值，正好等于我们要找的元素值
    32.                 return middle;
    33.             }
    34.         }
    35.         return -1; // -1特殊结果，就代表没有找到数据！数组中不存在该数据！
    36.     }
    37. }
     

     

    五、正则表达式
     

    正则表达式其实是由一些特殊的符号组成的，它代表的是某种规则。
     

     
 
    正则表达式的作用1：用来校验字符串数据是否合法
     
 
    正则表达式的作用2：可以从一段文本中查找满足要求的内容
     

     

     

    5.1 正则表达式初体验
     

    现在，我们就以QQ号码为例，来体验一下正则表达式的用法。注意：现在仅仅只是体验而已，我们还没有讲正则表达式的具体写法。
     

    •  
      不使用正则表达式，校验QQ号码代码是这样的
       
     

    1. public static boolean checkQQ(String qq){
    2.         // 1、判断qq号码是否为null
    3.         if(qq == null || qq.startsWith("0") || qq.length() < 6 || qq.length() > 20){
    4.             return false;
    5.         }
    6. ​
    7.         // 2、qq至少是不是null,不是以0开头的，满足6-20之间的长度。
    8.         // 判断qq号码中是否都是数字。
    9.         // qq = 2514ghd234
    10.         for (int i = 0; i < qq.length(); i++) {
    11.             // 根据索引提取当前位置处的字符。
    12.             char ch = qq.charAt(i);
    13.             // 判断ch记住的字符，如果不是数字，qq号码不合法。
    14.             if(ch < '0' || ch > '9'){
    15.                 return false;
    16.             }
    17.         }
    18.         // 3、说明qq号码肯定是合法
    19.         return true;
    20.     }
     

    •  
      用正则表达式代码是这样的
       
     

    1. public static boolean checkQQ1(String qq){
    2.     return qq != null && qq.matches("[1-9]\\d{5,19}");
    3. }
     

     

    5.2 正则表达式书写规则
     

    这里需要用到一个方法叫matches(String regex)。这个方法时属于String类的方法。
     

     

    这个方法是用来匹配一个字符串是否匹配正则表达式的规则，参数需要调用者传递一个正则表达式。但是正则表达式不能乱写，是有特定的规则的。
     

    下面我们就学习一下，正则表达式的规则。从哪里学呢？在API中有一个类叫做Pattern，我们可以到API文档中搜索，关于正则表达式的规则，这个类都告诉我们了。
     

     

     

    我们将这些规则，在代码中演示一下
     

    1. /**
    2.  * 目标：掌握正则表达式的书写规则
    3.  */
    4. public class RegexTest2 {
    5.     public static void main(String[] args) {
    6.         // 1、字符类(只能匹配单个字符)
    7.         System.out.println("a".matches("[abc]"));    // [abc]只能匹配a、b、c
    8.         System.out.println("e".matches("[abcd]")); // false
    9. ​
    10.         System.out.println("d".matches("[^abc]"));   // [^abc] 不能是abc
    11.         System.out.println("a".matches("[^abc]"));  // false
    12. ​
    13.         System.out.println("b".matches("[a-zA-Z]")); // [a-zA-Z] 只能是a-z A-Z的字符
    14.         System.out.println("2".matches("[a-zA-Z]")); // false
    15. ​
    16.         System.out.println("k".matches("[a-z&&[^bc]]")); // ： a到z，除了b和c
    17.         System.out.println("b".matches("[a-z&&[^bc]]")); // false
    18. ​
    19.         System.out.println("ab".matches("[a-zA-Z0-9]")); // false 注意：以上带 [内容] 的规则都只能用于匹配单个字符
    20. ​
    21.         // 2、预定义字符(只能匹配单个字符)  .  \d  \D   \s  \S  \w  \W
    22.         System.out.println("徐".matches(".")); // .可以匹配任意字符
    23.         System.out.println("徐徐".matches(".")); // false
    24. ​
    25.         // \转义
    26.         System.out.println("\"");
    27.         // \n \t
    28.         System.out.println("3".matches("\\d"));  // \d: 0-9
    29.         System.out.println("a".matches("\\d"));  //false
    30. ​
    31.         System.out.println(" ".matches("\\s"));   // \s: 代表一个空白字符
    32.         System.out.println("a".matches("\s")); // false
    33. ​
    34.         System.out.println("a".matches("\\S"));  // \S: 代表一个非空白字符
    35.         System.out.println(" ".matches("\\S")); // false
    36. ​
    37.         System.out.println("a".matches("\\w"));  // \w: [a-zA-Z_0-9]
    38.         System.out.println("_".matches("\\w")); // true
    39.         System.out.println("徐".matches("\\w")); // false
    40. ​
    41.         System.out.println("徐".matches("\\W"));  // [^\w]不能是a-zA-Z_0-9
    42.         System.out.println("a".matches("\\W"));  // false
    43. ​
    44.         System.out.println("23232".matches("\\d")); // false 注意：以上预定义字符都只能匹配单个字符。
    45. ​
    46.         // 3、数量词： ?   *   +   {n}   {n, }  {n, m}
    47.         System.out.println("a".matches("\\w?"));   // ? 代表0次或1次
    48.         System.out.println("".matches("\\w?"));    // true
    49.         System.out.println("abc".matches("\\w?")); // false
    50. ​
    51.         System.out.println("abc12".matches("\\w*"));   // * 代表0次或多次
    52.         System.out.println("".matches("\\w*"));        // true
    53.         System.out.println("abc12张".matches("\\w*")); // false
    54. ​
    55.         System.out.println("abc12".matches("\\w+"));   // + 代表1次或多次
    56.         System.out.println("".matches("\\w+"));       // false
    57.         System.out.println("abc12张".matches("\\w+")); // false
    58. ​
    59.         System.out.println("a3c".matches("\\w{3}"));   // {3} 代表要正好是n次
    60.         System.out.println("abcd".matches("\\w{3}"));  // false
    61.         System.out.println("abcd".matches("\\w{3,}"));     // {3,} 代表是>=3次
    62.         System.out.println("ab".matches("\\w{3,}"));     // false
    63.         System.out.println("abcde徐".matches("\\w{3,}"));     // false
    64.         System.out.println("abc232d".matches("\\w{3,9}"));     // {3, 9} 代表是  大于等于3次，小于等于9次
    65. ​
    66.         // 4、其他几个常用的符号：(?i)忽略大小写 、 或：| 、  分组：()
    67.         System.out.println("abc".matches("(?i)abc")); // true
    68.         System.out.println("ABC".matches("(?i)abc")); // true
    69.         System.out.println("aBc".matches("a((?i)b)c")); // true
    70.         System.out.println("ABc".matches("a((?i)b)c")); // false
    71. ​
    72.         // 需求1：要求要么是3个小写字母，要么是3个数字。
    73.         System.out.println("abc".matches("[a-z]{3}|\\d{3}")); // true
    74.         System.out.println("ABC".matches("[a-z]{3}|\\d{3}")); // false
    75.         System.out.println("123".matches("[a-z]{3}|\\d{3}")); // true
    76.         System.out.println("A12".matches("[a-z]{3}|\\d{3}")); // false
    77. ​
    78.         // 需求2：必须是”我爱“开头，中间可以是至少一个”编程“，最后至少是1个”666“
    79.         System.out.println("我爱编程编程666666".matches("我爱(编程)+(666)+"));
    80.         System.out.println("我爱编程编程66666".matches("我爱(编程)+(666)+"));
    81.     }
    82. }
     

     

    5.3 正则表达式应用案例
     

    学习完正则表达式的规则之后，接下来我们再利用正则表达式，去校验几个实际案例。
     

    •  
      正则表达式校验手机号码
       
     

    1. /**
    2.  * 目标：校验用户输入的电话、邮箱、时间是否合法。
    3.  */
    4. public class RegexTest3 {
    5.     public static void main(String[] args) {
    6.         checkPhone();
    7.     }
    8. ​
    9.     public static void checkPhone(){
    10.         while (true) {
    11.             System.out.println("请您输入您的电话号码(手机|座机): ");
    12.             Scanner sc = new Scanner(System.in);
    13.             String phone = sc.nextLine();
    14.             // 18676769999  010-3424242424 0104644535
    15.             if(phone.matches("(1[3-9]\\d{9})|(0\\d{2,7}-?[1-9]\\d{4,19})")){
    16.                 System.out.println("您输入的号码格式正确~~~");
    17.                 break;
    18.             }else {
    19.                 System.out.println("您输入的号码格式不正确~~~");
    20.             }
    21.         }
    22.     }
    23. }
    24. 使用正则表达式校验邮箱是否正确
    25.  
    26. public class RegexTest3 {
    27.     public static void main(String[] args) {
    28.         checkEmail();
    29.     }
    30. ​
    31.     public static void checkEmail(){
    32.         while (true) {
    33.             System.out.println("请您输入您的邮箱： ");
    34.             Scanner sc = new Scanner(System.in);
    35.             String email = sc.nextLine();
    36.             /**
    37.              * dlei0009@163.com
    38.              * 25143242@qq.com
    39.              * itheima@itcast.com.cn
    40.              */
    41.             if(email.matches("\\w{2,}@\\w{2,20}(\\.\\w{2,10}){1,2}")){
    42.                 System.out.println("您输入的邮箱格式正确~~~");
    43.                 break;
    44.             }else {
    45.                 System.out.println("您输入的邮箱格式不正确~~~");
    46.             }
    47.         }
    48.     }
    49. }
    50. ​
     

     

    5.4 正则表达式信息爬取
     

    正则表达式的第二个作用：在一段文本中查找满足要求的内容
     

    我们还是通过一个案例给大家做演示：案例需求如下
     

     

    1. /**
    2.  * 目标：掌握使用正则表达式查找内容。
    3.  */
    4. public class RegexTest4 {
    5.     public static void main(String[] args) {
    6.         method1();
    7.     }
    8. ​
    9.     // 需求1：从以下内容中爬取出，手机，邮箱，座机、400电话等信息。
    10.     public static void method1(){
    11.         String data = " 来黑马程序员学习Java，\n" +
    12.                 "        电话：1866668888，18699997777\n" +
    13.                 "        或者联系邮箱：boniu@itcast.cn，\n" +
    14.                 "        座机电话：01036517895，010-98951256\n" +
    15.                 "        邮箱：bozai@itcast.cn，\n" +
    16.                 "        邮箱：dlei0009@163.com，\n" +
    17.                 "        热线电话：400-618-9090 ，400-618-4000，4006184000，4006189090";
    18.         // 1、定义爬取规则
    19.         String regex = "(1[3-9]\\d{9})|(0\\d{2,7}-?[1-9]\\d{4,19})|(\\w{2,}@\\w{2,20}(\\.\\w{2,10}){1,2})"
    20.                 + "|(400-?\\d{3,7}-?\\d{3,7})";
    21.         // 2、把正则表达式封装成一个Pattern对象
    22.         Pattern pattern = Pattern.compile(regex);
    23.         // 3、通过pattern对象去获取查找内容的匹配器对象。
    24.         Matcher matcher = pattern.matcher(data);
    25.         // 4、定义一个循环开始爬取信息
    26.         while (matcher.find()){
    27.             String rs = matcher.group(); // 获取到了找到的内容了。
    28.             System.out.println(rs);
    29.         }
    30.     }
    31. }
     

     

    5.5 正则表达式搜索、替换
     

    接下来，我们学习一下正则表达式的另外两个功能，替换、分割的功能。需要注意的是这几个功能需要用到Stirng类中的方法。
     

     

    1. /**
    2.  * 目标：掌握使用正则表达式做搜索替换，内容分割。
    3.  */
    4. public class RegexTest5 {
    5.     public static void main(String[] args) {
    6.         // 1、public String replaceAll(String regex , String newStr)：按照正则表达式匹配的内容进行替换
    7.         // 需求1：请把下面字符串中的不是汉字的部分替换为 “-”
    8.         String s1 = "古力娜扎ai8888迪丽热巴999aa5566马尔扎哈fbbfsfs42425卡尔扎巴";
    9.         System.out.println(s1.replaceAll("\\w+", "-"));
    10.         
    11.         // 需求2(拓展)：某语音系统，收到一个口吃的人说的“我我我喜欢编编编编编编编编编编编编程程程！”，需要优化成“我喜欢编程！”。
    12.         String s2 = "我我我喜欢编编编编编编编编编编编编程程程";
    13.         System.out.println(s2.replaceAll("(.)\\1+", "$1"));
    14. ​
    15.         // 2、public String[] split(String regex)：按照正则表达式匹配的内容进行分割字符串，反回一个字符串数组。
    16.         // 需求1：请把下面字符串中的人名取出来，使用切割来做
    17.         String s3 = "古力娜扎ai8888迪丽热巴999aa5566马尔扎哈fbbfsfs42425卡尔扎巴";
    18.         String[] names = s3.split("\\w+");
    19.         System.out.println(Arrays.toString(names));
    20.     }
    21. }
     

     

     

     

     

     

    
                
    
                    
    
                
    • 

                
  • 

                    相关阅读:
    
                    
线程池的实现                            
    
NR SRS power control                            
    
在工作流引擎设计领域，是否自动计算未来的处理人的设计模式有哪些？                            
    
国内数据防泄漏产品选型指南                            
    
轻量级的资源授权：基于 OAuth 规范                            
    
超纯水如何除硼，除硼树脂技术分析                            
    
《Web安全基础》05. XSS · CSRF · SSRF · RCE                            
    
fork函数相关资源复制问题验证                            
    
WPF Image设置为圆形，并有折叠                            
    
Python中的字典(Dictionary)学习                            
    
                        
                
    • 
                
  • 
                    原文地址：https://blog.csdn.net/weixin_68522070/article/details/136282766
                
    •