Javase复习day21算法、arrays、Lamdba表达式

常见算法

查找算法

基本查找 

package search;public class BasicSearchDemo1 {public static void main(String[] args) {//基本算法（顺序查找）int[] arr = {131,23,57,37,95,48,57,43};System.out.println(basicSearch(arr, 43));}public static boolean basicSearch(int[] arr,int number){for (int i = 0; i < arr.length; i++) {if (arr[i]==number){return true;}}return false;}
}

课堂练习1

课堂练习2

package search;import java.util.ArrayList;public class BasicSearchDemo2 {public static void main(String[] args) {//基本算法（顺序查找）int[] arr = {131,23,57,37,95,48,57,43,23};System.out.println(basicSearch1(arr, 43));System.out.println(basicSearch2(arr, 23));}public static int basicSearch1(int[] arr,int number){for (int i = 0; i < arr.length; i++) {if (arr[i]==number){return i;}}return -1;}public static ArrayList<Integer> basicSearch2(int[] arr, int number){ArrayList<Integer> list = new ArrayList<>();for (int i = 0; i < arr.length; i++) {if (arr[i]==number){list.add(i);}}return list;}
}

二分查找（折半查找）

package search;public class BinarySearchDemo1 {public static void main(String[] args) {//二分查找int[] arr = {7,23,79,81,103,127,131,147};System.out.println(basicSearch(arr, 127));}public static int basicSearch(int[] arr,int number){int min = 0;int max = arr.length;while (max>=min){int mid = (min+max)/2;if (number>arr[mid]){min = mid+1;} else if (number<arr[mid]) {max = mid-1;}else {return mid;}}return -1;}
}

二分查找小结

二分查找的改进

插值查找

斐波那契查找

二分查找的小结

分块查找

package search;public class BlockSearchDemo {public static void main(String[] args) {//初步将其分块int[] arr = {16,5,9,12, 21,18,32,23,37,26,45,34,50,48,61,52,73,66};Block b1 = new Block(21,0,5);Block b2 = new Block(45,6,11);Block b3 = new Block(73,12,17);//定义数组来管理Block[] blocks = {b1,b2,b3};//记录要查找的数据int number = 73;//调用方法传递索引表、数组、查询的元素int index = getIndex(blocks,arr,number);System.out.println(index);}private static int getIndex(Block[] blocks, int[] arr, int number) {int indexBock = findIndexBock(blocks, number);if (indexBock==-1){//表示没有返回-1return -1;}//将对应块的起始索引和结束索引取出来int startIndex = blocks[indexBock].getStartIndex();int endIndex = blocks[indexBock].getEndIndex();//遍历到则存在for (int i = startIndex; i <= endIndex; i++) {if (arr[i]==number){return i;}}return -1;}//定义一个方法用来确认number的块public static int findIndexBock(Block[] blocks,int number){//二分查找进行操作int min = 0;int max = blocks.length;while (max>=min){int mid = (min+max)/2;if (number>blocks[mid].getMax()){min = mid+1;} else if (number<=blocks[mid].getMax()) {return mid;}}return -1;//顺序查找
//        for (int i = 0; i < blocks.length; i++) {
//            if (blocks[i].getMax()>=number){
//                return i;
//            }
//        }
//        return -1;}}
//定义一个类记录分块情况
class Block{private int max;private int startIndex;private int endIndex;public Block() {}public Block(int max, int startIndex, int endIndex) {this.max = max;this.startIndex = startIndex;this.endIndex = endIndex;}/*** 获取* @return max*/public int getMax() {return max;}/*** 设置* @param max*/public void setMax(int max) {this.max = max;}/*** 获取* @return startIndex*/public int getStartIndex() {return startIndex;}/*** 设置* @param startIndex*/public void setStartIndex(int startIndex) {this.startIndex = startIndex;}/*** 获取* @return endIndex*/public int getEndIndex() {return endIndex;}/*** 设置* @param endIndex*/public void setEndIndex(int endIndex) {this.endIndex = endIndex;}public String toString() {return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";}
}

扩展的分块查找（无规律的数据）

package search;public class BlockSearchDemo2 {public static void main(String[] args) {//初步将其分块int[] arr = {27,22,30,40,36,13,19,16,20,7,10,43,50,48};Block2 b1 = new Block2(22,40,0,4);Block2 b2 = new Block2(13,20,5,8);Block2 b3 = new Block2(7,10,9,10);Block2 b4 = new Block2(43,50,11,13);//定义数组来管理Block2[] blocks = {b1,b2,b3,b4};//记录要查找的数据int number = 40;//调用方法传递索引表、数组、查询的元素int index = getIndex(blocks,arr,number);System.out.println(index);}private static int getIndex(Block2[] blocks, int[] arr, int number) {int indexBock = findIndexBock(blocks, number);if (indexBock==-1){//表示没有返回-1return -1;}//将对应块的起始索引和结束索引取出来int startIndex = blocks[indexBock].getStartIndex();int endIndex = blocks[indexBock].getEndIndex();//遍历到则存在for (int i = startIndex; i <= endIndex; i++) {if (arr[i]==number){return i;}}return -1;}//定义一个方法用来确认number的块public static int findIndexBock(Block2[] blocks,int number){//        由于分布没有顺序不能使用二分查找所以使用顺序查找for (int i = 0; i < blocks.length; i++) {if (blocks[i].getMax()>=number&&blocks[i].getMin()<=number){return i;}}return -1;}}
//定义一个类记录分块情况
class Block2{private int max;private int min;private int startIndex;private int endIndex;public Block2() {}public Block2( int min,int max, int startIndex, int endIndex) {this.max = max;this.min = min;this.startIndex = startIndex;this.endIndex = endIndex;}/*** 获取* @return max*/public int getMax() {return max;}/*** 设置* @param max*/public void setMax(int max) {this.max = max;}/*** 获取* @return min*/public int getMin() {return min;}/*** 设置* @param min*/public void setMin(int min) {this.min = min;}/*** 获取* @return startIndex*/public int getStartIndex() {return startIndex;}/*** 设置* @param startIndex*/public void setStartIndex(int startIndex) {this.startIndex = startIndex;}/*** 获取* @return endIndex*/public int getEndIndex() {return endIndex;}/*** 设置* @param endIndex*/public void setEndIndex(int endIndex) {this.endIndex = endIndex;}public String toString() {return "Block{max = " + max + ", min = " + min + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";}
}

扩展的分块查找（查找过程中还需要添加数据）

排序算法

冒泡排序

package sort;public class BubbleDemo1 {public static void main(String[] args) {int[] arr = {2,4,5,3,1};int[] arr2 = bubble(arr);for (int i = 0; i < arr2.length; i++) {System.out.print(arr2[i]+" ");}}private static int[] bubble(int[] arr) {//表示执行多少轮for (int j = 0; j < arr.length-1; j++) {/*** 每一轮如何找到该轮的最大值* -1 表示 防止索引越界*  -j 提高效率，已经排序的位置不需要再比较*/for (int i = 0; i < arr.length -1-j; i++) {if (arr[i] > arr[i+1]){int temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}}return arr;}
}

选择排序

package sort;public class SelectionDemo {public static void main(String[] args) {int[] arr = {2,10,5,3,1};int[] arr2 = selection(arr);for (int i = 0; i < arr2.length; i++) {System.out.print(arr2[i]+" ");}}private static int[] selection(int[] arr) {//使用0索引与后面比较for (int i = 0; i < arr.length-1; i++) {//int j = i+1减少不必要的比较提高效率for (int j = i+1; j < arr.length; j++) {if (arr[i]>arr[j]){int temp= arr[i];arr[i] = arr[j];arr[j] = temp;}}}return arr;}}

插入排序

交换位置时从后往前进行遍历，最终确定自己的位置。

package sort;public class InsertDemo {//插入排序public static void main(String[] args) {int[] arr = {1,5,10,3,20,7,40,54,4,6,23,47};int[] arr2 = inserta(arr);for (int i = 0; i < arr2.length; i++) {System.out.print(arr2[i]+" ");}}private static int[] inserta(int[] arr) {//快速排序//先确定无序的位置,无序的起始索引int start = -1;for (int i = 0; i < arr.length; i++) {if (arr[i]>arr[i+1]){start = i+1;break;}}for (int i = start; i < arr.length; i++) {//j 进行操作防止i 改变后导致程序无法运行int j = i;//当前一个数比当前的数大时两数交换位置，并将指针即j前移一位while (j>0&&arr[j]<arr[j-1]){int temp = arr[j];arr[j] = arr[j-1];arr[j-1]=temp;j--;}}return arr;}
}

快速排序

递归

注意

递归一定要有出口，否则就会内存溢出。

作用

练习

package sort;public class RecursionDemo2 {//求1-100的和public static void main(String[] args) {int n =100;int sun = sum1(100);System.out.println(sun);}private static int sum1(int i) {if (i==1){return 1;}return i+sum1(i-1);}
}

练习二

package sort;public class RecursionDemo3 {//求5的阶乘public static void main(String[] args) {int factorial = factorial(5);System.out.println(factorial);}private static int factorial(int i) {if (i==1){return 1;}return i*factorial(i-1);}
}

快速排序

package sort;public class QuickDemo {public static void main(String[] args) {//快速排序int[] arr = {7,4,2,8,5,9,12,35,45,98,34,76};quickSort(arr, 0, arr.length-1);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+" ");}}private static void quickSort(int[] arr, int i, int j) {//快排第一轮int start = i;int end = j;//设置递归的条件if(start>end){return;}int Benchmark = arr[i];while (start != end){//先寻找比基准数小的，用end记录下标while (true){if (end<=start||arr[end]<Benchmark){break;}end--;}//在寻找比基准数大的，用start记录下标while (true){if (end<=start||arr[start]>Benchmark){break;}start++;}//换位值int temp = arr[start];arr[start] = arr[end];arr[end] = temp;}int temp = arr[i];arr[i] = arr[end];arr[end] = temp;//开始进行递归调用quickSort(arr,i,start-1);quickSort(arr,start+1,j);}
}

排序总结

Arrays

arrays即操作数组的工具类。

方法

sort中的指定规则排序

package ArraysDemo;import java.util.Arrays;
import java.util.Comparator;public class ArraysDemo1 {public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7,8,9};System.out.println(Arrays.toString(arr));System.out.println(Arrays.binarySearch(arr, 4));System.out.println(Arrays.binarySearch(arr, 10));System.out.println(Arrays.binarySearch(arr, 0));System.out.println("=======================");int[] ints = Arrays.copyOf(arr, 4);System.out.println(Arrays.toString(ints));int[] ints1 = Arrays.copyOf(arr, 9);System.out.println(Arrays.toString(ints1));int[] ints2 = Arrays.copyOfRange(arr, 0, 9);System.out.println(Arrays.toString(ints2));System.out.println("=========================");//        Arrays.fill(arr,1);
//        System.out.println(Arrays.toString(arr));
//        Arrays.sort(arr,new Comparator<>());//o2-o1为降序排列，o1-o2为升序排列Integer[] arr2 = {1,2,3,4,5,6,7,8,9};Arrays.sort(arr2, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}});System.out.println(Arrays.toString(arr2));}
}

Lambda表达式

试水

package LambdaDemo;import java.util.Arrays;
import java.util.Comparator;public class Demo1 {public static void main(String[] args) {Integer[] arr = {1,2,3,7,4,9,6};//        Arrays.sort(arr, new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o1=o2;
//            }
//        });Arrays.sort(arr, (Integer o1, Integer o2) -> {return o1=o2;});System.out.println(Arrays.toString(arr));}
}

函数式编程

package LambdaDemo;public class Demo2 {public static void main(String[] args) {//正常情况method(new Swin() {@Overridepublic void swimming() {System.out.println("匿名内部类游泳~");}});//lambda表达式method(()->{System.out.println("lambda游泳~");});}public static void method(Swin swin){swin.swimming();}
}
interface Swin{public void swimming();
}

Lambda表达式的省略写法

核心思想：可推导，可省略。

package LambdaDemo;import java.util.Arrays;
import java.util.Comparator;public class Demo3 {public static void main(String[] args) {//正常情况method(new Swin1() {@Overridepublic void swimming() {System.out.println("匿名内部类游泳~");}});//lambda表达式method(()->{System.out.println("lambda游泳~");});//进行省略写法method(()-> System.out.println("lambda游泳省略写法~"));//多个形参的案例Integer[] arr2 = {1,2,3,4,5,6,7,8,9};//形参类型相同可以推导出来，省略//将大括号，return、分号一起省略。Arrays.sort(arr2, (o1,o2) -> o2-o1);System.out.println(Arrays.toString(arr2));}public static void method(Swin1 swin){swin.swimming();}
}
interface Swin1{public void swimming();
}

练习一：Lambda表达式简化Comparator接口的匿名形式

package LambdaDemo;import java.util.Arrays;
import java.util.Comparator;public class Demo4 {public static void main(String[] args) {String[] arr ={"aa","a","aaaa","aaa"};Arrays.sort(arr,( o1,o2) ->o1.length()-o2.length());System.out.println(Arrays.toString(arr));}
}

综合练习

练习一：按要求排序

package Test.Test1;import java.util.Arrays;
import java.util.Comparator;public class Test1 {public static void main(String[] args) {//创建几个对象Person p1 = new Person("xiaoli",20,175);Person p2 = new Person("aiaoli",20,175);Person p3 = new Person("biaoli",19,172);Person p4 = new Person("ciaoli",22,168);Person p5 = new Person("diaoli",20,168);Person p6 = new Person("eiaoli",20,165);Person p7 = new Person("fiaoli",20,175);//定义数组进行存储Person[] arr={p1,p2,p3,p4,p5,p6,p7};//进行排序//匿名内部类写法
//        Arrays.sort(arr, new Comparator<Person>() {
//            @Override
//            public int compare(Person o1, Person o2) {
//                //o1为要加入的
//                if (o1.getAge()>o2.getAge()){
//                    return 1;
//                } else if (o1.getAge()<o2.getAge()) {
//                    return -1;
//                }else {
//                    //年龄一样，按身高排序
//                    if (o1.getHight()>o2.getHight()){
//                        return 1;
//                    } else if (o1.getHight()<o2.getHight()) {
//                        return -1;
//                    }else {
//                        //按姓名的字母排序
//                        //获取姓名的首字母char o1n = o1.getName().charAt(0);char o2n = o2.getName().charAt(0);
//                        //可以使用字符串的比较方法来比较
//                      return o1.getName().compareTo(o2.getName());if (o1n>o2n){return 1;} else if (o1n<o2n) {return -1;}
//                    }
//
//                }
//            }
//        });//Lambda表达式写法Arrays.sort(arr, (o1,o2) ->{//o1为要加入的if (o1.getAge()>o2.getAge()){return 1;} else if (o1.getAge()<o2.getAge()) {return -1;}else {//年龄一样，按身高排序if (o1.getHight()>o2.getHight()){return 1;} else if (o1.getHight()<o2.getHight()) {return -1;}else {//按姓名的字母排序//可以使用字符串的比较方法来比较return o1.getName().compareTo(o2.getName());}}});//将数组转为字符串进行输出System.out.println(Arrays.toString(arr));}
}

实现方法二（教学的教简单）：

package Test.Test1;import java.util.Arrays;
import java.util.Comparator;public class Test2 {public static void main(String[] args) {//创建几个对象Person p1 = new Person("xiaoli",20,175);Person p2 = new Person("aiaoli",20,175);Person p3 = new Person("biaoli",19,172);Person p4 = new Person("ciaoli",22,168);Person p5 = new Person("diaoli",20,168);Person p6 = new Person("eiaoli",20,165);Person p7 = new Person("fiaoli",20,175);//定义数组进行存储Person[] arr={p1,p2,p3,p4,p5,p6,p7};//进行排序//匿名内部类写法
//        Arrays.sort(arr, new Comparator<Person>() {
//            @Override
//            public int compare(Person o1, Person o2) {
//                //比较年龄
//                double temp = o1.getAge()-o2.getAge();
//                //年龄相对，比较身高
//                temp = temp == 0? o1.getHight()-o2.getHight():temp;
//                //身高相等，比较姓名
//                temp = temp == 0? o1.getName().compareTo(o2.getName()):temp;
//                
//                //由于返回值类型为int所以进行判断
//                
//                if (temp<0){
//                    return -1;
//                } else if (temp>0) {
//                    return 1;
//                }else {
//                    return 0;
//                }
//            }
//        });//Lambda表达式写法Arrays.sort(arr, (o1,o2) -> {//比较年龄double temp = o1.getAge()-o2.getAge();//年龄相对，比较身高temp = temp == 0? o1.getHight()-o2.getHight():temp;//身高相等，比较姓名temp = temp == 0? o1.getName().compareTo(o2.getName()):temp;//由于返回值类型为int所以进行判断if (temp<0){return -1;} else if (temp>0) {return 1;}else {return 0;}});//将数组转为字符串进行输出System.out.println(Arrays.toString(arr));}
}

练习二：不死神兔

从第三个月开始这个月的数量都是前两个月的合。

package Test.Test2;public class Test {public static void main(String[] args) {//从第三个数据开始每个数据都是前两个数据之和//解法一：使用数组
//        int[] arr = new int[12];
//        arr[0]=1;
//        arr[1]=1;
//        for (int i = 2; i < arr.length; i++) {
//            arr[i] = arr[i-1]+arr[i-2];
//        }
//        System.out.println(arr[11]);//方法二：使用递归System.out.println(fi(12));}public static int fi(int n){if (n==1||n==2){return 1;}else {return fi(n-1)+fi(n-2);}}}

练习三：猴子吃桃子

package Test.Test3;public class Test3 {public static void main(String[] args) {System.out.println(fi(1));}public static int fi(int n){//进行校验if (n>=11||n<=0){return -1;}if (n==10){return 1;}else {return (fi(n+1)+1)*2;}}
}

练习四：爬楼梯

package Test.Test4;//可以看做斐波那契数列public class Test {public static void main(String[] args) {int fn = Fn(7);//21int fn1 = Fn(20);//10946System.out.println(fn);System.out.println(fn1);}public static int Fn(int n){if (n==1){return 1;}if (n==2){return 2;}return (Fn(n-1))+(Fn(n-2));}
}

课堂练习:可以一次爬三个台阶

package Test.Test4;public class Test {public static void main(String[] args) {int fn = Fn(7);//44int fn1 = Fn(20);//121415System.out.println(fn);System.out.println(fn1);}public static int Fn(int n){if (n==1){return 1;}if (n==2){return 2;}if (n==3){return 4;}return (Fn(n-1))+(Fn(n-2)+Fn(n-3));}
}