day06_算法训练

一. Stream流

1.1 Stream流概述

概念: jdk1.8以后提供的新的API, 主要用于批量操作数据(集合的另外一种操作方式),代码非常简洁

流式处理思想:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

2.2 Stream对象获取

1.单列集合的Stream流对象获取

2.双列集合的Stream流对象获取

3.数组的Stream流对象获取

4.散装数据的Stream流对象获取

public class Test {public static void main(String[] args) {//1.创建单列集合Collection<String> names = new ArrayList<>();//2.Stream流对象的获取: stream()Stream<String> s1 = names.stream();System.out.println(s1);//3.创建双列集合对象Map<String,String> wifes = new HashMap<>();//4.Stream流对象获取: 把双列集合转换成单列集合(根据双列集合获取其键的集合或者是键值对的结合)获取Stream<String> s2 = wifes.keySet().stream();System.out.println(s2);Stream<Map.Entry<String, String>> s3 = wifes.entrySet().stream();System.out.println(s3);//5.创建数组对象String[] strs = {"张三三","李四四","王五五"};//6.获取流对象: Arrays.stream(数组)Stream<String> s4 = Arrays.stream(strs);System.out.println(s4);//7.借助于Stream接口的静态方法of,获取散装数据对应的流对象Stream<String> s5 = Stream.of("张三三", "李四四", "王五五");System.out.println(s5);}
}

3.3 Stream流常用方法

中间方法: 如果该方法的返回值类型是Stream

Stream filter(Predicate predicate): 对数据进行过滤操作

Stream limit(long n): 取数据源中前n个数据

Stream skip(long n): 跳过数据源中前n个数据

Stream distinct(): 去重重复的元素

Stream sorted(): 排序

终结方法:如果该方法的返回值类型不是Stream

void foreach(Comsumer c): 把最终留下的数据挨个遍历

int count(): 统计个数

静态方法:

Stream concat(Stream s1,Stream s2): 合并s1和s2可操作的数据到一个流中

注意: 同一个Stream流对象,只能调用一次方法(中间还是终结)

public class Test {public static void main(String[] args) {//创建集合,获取Stream流对象List<Integer> nums = new ArrayList<>();nums.add(4);nums.add(6);nums.add(3);nums.add(2);nums.add(5);//获取流对象Stream<Integer> s1 = nums.stream();//取出所有的偶数/*Predicate: 提供判断规则的接口boolean test(数据): 重写test的方法,如果test的方法返回true,则该数据满足条件,否则不满足条件*//*Stream<Integer> s2 = s1.filter(new Predicate<Integer>() {@Overridepublic boolean test(Integer integer) {//判断规则return integer % 2 == 0;}});*//*Stream<Integer> s2 = s1.filter((Integer integer)->{return integer % 2 == 0;});*/Stream<Integer> s2 = s1.filter(integer ->integer % 2 == 0);//注意: 同一个Stream流对象,只能调用一次方法(中间还是终结),//取出所有偶数中大于2的数据/*Stream<Integer> s3 = s2.filter(new Predicate<Integer>() {@Overridepublic boolean test(Integer integer) {return integer > 2;}});*/Stream<Integer> s3 = s2.filter(integer -> integer > 2);//数据所有满足条件的数据/*Consumer: 提供数据的消费规则的接口void accept(数据): 重写accept方法, accept方法的方法体就是该数据的消费逻辑*//*s2.forEach(new Consumer<Integer>() {@Overridepublic void accept(Integer integer) {//消费的逻辑System.out.println("当前数据为: " + integer);}});*/s3.forEach(new Consumer<Integer>() {@Overridepublic void accept(Integer integer) {//消费的逻辑System.out.println("当前数据为: " + integer);}});}
}


public class Test2 {public static void main(String[] args) {//创建集合,获取Stream流对象List<Integer> nums = new ArrayList<>();nums.add(4);nums.add(6);nums.add(3);nums.add(2);nums.add(5);//获取流对象//Stream<Integer> s1 = nums.stream();//Stream<Integer> s2 = s1.filter(integer -> integer % 2 == 0);//Stream<Integer> s3 = s2.filter(integer -> integer > 2);/*s3.forEach(new Consumer<Integer>() {@Overridepublic void accept(Integer integer) {//消费的逻辑System.out.println("当前数据为: " + integer);}});*///Stream流的链式调用书写方式  终极写法nums.stream().filter(integer -> integer % 2 == 0).filter(integer -> integer > 2).forEach(integer -> System.out.println("当前数据为: " + integer));}
}

public class Test3 {public static void main(String[] args) {//创建两个集合对象List<Integer> nums1 = new ArrayList<>();nums1.add(2);nums1.add(4);nums1.add(6);nums1.add(8);nums1.add(10);List<Integer> nums2 = new ArrayList<>();nums2.add(1);nums2.add(3);nums2.add(5);nums2.add(7);nums2.add(9);nums2.add(9);//limit方法: 获取nums1中的前3个数据nums1.stream().limit(3).forEach(num -> System.out.println(num));//skip方法: 获取nums2中的后3个数据nums2.stream().skip(2).forEach(num -> System.out.println(num));//distinct方法: 去重System.out.println("===================");nums2.stream().distinct().forEach(num -> System.out.println(num));//concat方法: 合并两个流, 将集合nums1和nums2中的数据合并System.out.println("=========================");Stream.concat(nums1.stream(), nums2.stream()).forEach(num -> System.out.println(num));//sorted方法:对流可操作的元素排序,将集合nums1和nums2中的数据合并,并排序System.out.println("=======================");//Stream.concat(nums1.stream(),nums2.stream()).sorted().forEach(num-> System.out.println(num));Stream.concat(nums1.stream(), nums2.stream()).sorted((o1, o2) -> o2 - o1).forEach(num -> System.out.println(num));//count方法: 统计当前流中可操作的数据个数, 将集合nums1和nums2中的数据合并,并统计个数输出long count = Stream.concat(nums1.stream(), nums2.stream()).count();System.out.println(count);}
}

二. 刷题

案例1：打印折纸的次数

需求：世界最高山峰是珠穆朗玛峰(8844.43米=8844430毫米)，假如我有一张足够大的纸，它的厚度是0.1毫米。

请问，我折叠多少次，可以折成珠穆朗玛峰的高度?

public class Test01 {/*需求：世界最高山峰是珠穆朗玛峰(8844.43米=8844430毫米)，假如我有一张足够大的纸，它的厚度是0.1毫米。请问，我折叠多少次，可以折成珠穆朗玛峰的高度?*/public static void main(String[] args) {/*1.定义变量,把数据记录下来2.while循环模拟折叠过程*///1.定义变量,记录珠峰高度和纸的厚度double mountainHeight = 8844430;double paperThickness = 0.1;//2.定义变量,记录折叠的次数int count = 0;//3.循环折叠: 3.1 纸张厚度翻番, 3.2 折叠次数增1/*while (true){//当满足某些条件的时候,break结束循环//3.1 纸张厚度翻番paperThickness *= 2;//3.2 折叠次数增1count++;//判断纸张厚度是否达到了珠峰的高度if (paperThickness >= mountainHeight){//是 结束循环break;}}*/while (paperThickness < mountainHeight) {//3.1 纸张厚度翻番paperThickness *= 2;//3.2 折叠次数增1count++;}System.out.println(count);}
}

案例2：逢七过

朋友聚会的时候可能会玩一个游戏：逢7过

游戏规则：从任意一个数字开始报数，当你要报的数字是包含7或者是7的倍数时都要说过：过

需求：使用程序在控制台打印出1-100之间的满足逢七必过规则的数据

public class Test02 {/*朋友聚会的时候可能会玩一个游戏：逢7过游戏规则：从任意一个数字开始报数，当你要报的数字是包含7或者是7的倍数时都要说过：过需求：使用程序在控制台打印出1-100之间的满足逢七必过规则的数据*/public static void main(String[] args) {/*1.得到1~100之间的每个数字 for2.判断当前数字是不是包含7或者7的倍数3.如果满足,输出该数据*///1.得到1~100之间的每个数字 forfor (int i = 1; i <= 100; i++) {//2.判断当前数字是不是包含7或者7的倍数/*i 1位数(7), 2位数,3位数(100)两位数: 拿到各位的数字和十位的数字分别判断是不是7178: 个位8: 178%10   十位: 178/10---17%10--->7*/int ge = i % 10;int shi = i / 10 % 10;if (i % 7 == 0 || (ge == 7 || shi == 7)){System.out.println(i);}}}
}

案例3：猜数字小游戏

需求：程序自动生成一个1-100之间的随机数字，使用程序实现猜出这个数字是多少？

public class Test03 {//需求：程序自动生成一个1-100之间的随机数字，使用程序实现猜出这个数字是多少？public static void main(String[] args) {/*1.生成1~100之间的随机数2.借助于Scanner获取用户猜的数字 while3.比对两个数字猜大了:继续猜猜小了:继续猜猜对了:结束*///1.生成1~100之间的随机数Random random = new Random();int randomNumber = random.nextInt(100) + 1; // 生成1到100的随机数//System.out.println(randomNumber);//2.借助于Scanner获取用户猜的数字 whileScanner sc = new Scanner(System.in);while (true){System.out.println("请输入您要猜的数据[1~100]: ");int inputNumber = sc.nextInt();//3.比对两个数字if (inputNumber > randomNumber){//猜大了:继续猜System.out.println("猜大了:继续猜");}else if (inputNumber < randomNumber){//猜小了:继续猜System.out.println("猜小了:继续猜");}else{//猜对了:结束System.out.println("猜对了:游戏结束，欢迎下次使用！");break;}}}
}

案例4：求平方根

给你一个int范围内的非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不要用Java已经提供的API

比如：输入：x = 4 输出：2

比如：输入：x = 8 输出：2

解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。


public class Test04 {/*给你一个int范围内的非负整数 x ，计算并返回的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。注意：不要用Java已经提供的API比如：输入：x = 4	输出：2比如：输入：x = 8	输出：2解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。*/public static void main(String[] args) {System.out.println(calculate(4));//2System.out.println(calculate(8));//2System.out.println(calculate(16));//4System.out.println(calculate(15));//3System.out.println(calculate(0));//0System.out.println(calculate(1));//1}//定义一个方法，去任意非负整数的 整数平方根public static int calculate(int x) {//求if (x==0){return 0;}if (x==1){return 1;}/*1019 整数平方根  3130*30=90031*31=96131.xx*31.xx = 101932*32=102433*33=108935*35=122540*40=1600x 整数平方根找一个最大的数字的平方 < x从小往大找  0,1,2,3...从大往小找: 不知道从哪开始确定:从小往大找  0,1,2,3...  目标: 找一个最大的数字的平方 < x标准: 从小往大找,找到的第一个数字的平方>x,  该数字-1*/int target = -1;//1.找到从0开始到x之间的每一个数字for (int i = 0; i <= x; i++) {//2.判断当前i的平方是不是大于xif (i * i > x){target = i-1;break;}}return target;}}

案例5：两数相除

需求：

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。

例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的商。

public class Test05 {/*需求：给你两个整数，被除数dividend和除数divisor。将两数相除，要求 不使用 乘法、除法和取余运算。整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。返回被除数dividend除以除数divisor得到的 商 。*/public static void main(String[] args) {System.out.println(calculate(11, 2));System.out.println(calculate(-11, -2));System.out.println(calculate(-11, 2));System.out.println(calculate(11, -2));System.out.println(calculate(0, -2));}//定义方法,完成需求: 求两个整数的商public static int calculate(int divided, int divisor) {//异或判断同号或异号//求商/*9÷3:转化为 9 是几个3相加的结果9 - 3 = 6  16 - 3 = 3  23 - 3 = 0  30 - 3 = -3只要拿着被除数不断的减除数,直到差为0为止7÷2:转化为 7 是 几个2相加的结果7 - 2 = 5 15 - 2 = 3 23 - 2 = 1 31 - 2 = -1如果不等你整除: 拿着被除数不断的减除数,直到差为负数为止*///定义变量,记录商(统计减了多少次)int count = 0;if (divided >= 0 && divisor > 0) {//1.使用while循环,模拟减多次while (true) {divided = divided - divisor;//判断divided是不是负数if (divided < 0) {//不用再减了,结束循环break;}//统计变量+1count++;}} else if (divided < 0 && divisor < 0) {divided = -divided;divisor = -divisor;//1.使用while循环,模拟减多次while (true) {divided = divided - divisor;//判断divided是不是负数if (divided < 0) {//不用再减了,结束循环break;}//统计变量+1count++;}} else if (divided < 0 && divisor > 0) {divided = -divided;//1.使用while循环,模拟减多次while (true) {divided = divided - divisor;//判断divided是不是负数if (divided < 0) {//不用再减了,结束循环break;}//统计变量+1count++;}count = -count;}else{divisor = -divisor;//1.使用while循环,模拟减多次while (true) {divided = divided - divisor;//判断divided是不是负数if (divided < 0) {//不用再减了,结束循环break;}//统计变量+1count++;}count = -count;}//返回商return count;}}

案例6：求质数

需求1：键盘录入一个正整数 x ，判断该整数是否为一个质数(质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数)。

需求2：给定一个范围，比如100~1000，统计这个范围内有多少个质数。


public class Test06 {/*需求1：键盘录入一个正整数 x ，判断该整数是否为一个质数。需求2：给定一个范围，比如100~1000，统计这个范围内有多少个质数。*/public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入一个整数: ");int num = sc.nextInt();System.out.println(isPrimeNumber(num));//得到100~1000之间的每个数字int count = 0;for (int i = 100; i <= 1000; i++) {if (isPrimeNumber(i)) {//是质数count++;}}System.out.println(count);}//定义方法,判断某个数是不是质数public static boolean isPrimeNumber(int num) {//合法性的校验if (num <= 1) {return false;}//是不是质数: 2~num-1 中的某个数能不能整除numboolean flag = true;//默认num是质数for (int i = 2; i < num; i++) {if (num % i == 0) {//num不是质数flag = false;}}return flag;}}

案例7：2 的幂

定义一个方法，传递一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2的x次方，则认为 n 是 2 的幂次方。

扩展：3的幂 4的幂

比如：

输入：n = 1
输出：true
解释：2的0次方 = 1输入：n = 16
输出：true
解释：2的4次方 = 16输入：n = 3
输出：false

public class Test07 {/*定义一个方法，传递一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。如果存在一个整数 x 使得n == 2的x次方，则认为 n 是 2 的幂次方。扩展：3的幂  4的幂*/public static void main(String[] args) {System.out.println(judge(1));System.out.println(judge(2));System.out.println(judge(4));System.out.println(judge(6));System.out.println(judge(8));}//定义一个方法，传递一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。public static boolean judge(int n) {//合法性校验if (n <= 0){return  false;}//是不是2的幂次方/*1616/2=88/2=44/2=22/2=16464/2=3232/2=1616/2=88/2=44/2=22/2=11818/2=9如果某个数是2的幂次方,如果当前数字可以被2整除,那么不断的对2做除法,最终得到1*/while (true) {//1.判断当前n能不能对2做除法运算  n % 2 == 0if (n % 2 == 0) {//2.用 n 对 2做除法运算n = n / 2;}else{break;}}return n == 1;}}

案例8：数组排序

定义一个数组：{3,10,7,9,5,1,2,8}

需求1：利用冒泡排序将数组按照从小到大的形式进行排列

需求2：利用选择排序将数组按照从小到大的形式进行排列

public class Test08 {/*定义一个数组：{3,10,7,9,5,1,2,8}需求1：利用**冒泡排序**将数组按照从小到大的形式进行排列需求2：利用**选择排序**将数组按照从小到大的形式进行排列*/public static void main(String[] args) {int[] arr = {3,10,7,9,5,1,2,8};//bubble(arr);select(arr);System.out.println(Arrays.toString(arr));}public static void bubble(int[] arr) {//对arr进行冒泡排序/*过程: 1.每次确定一个待排序数据范围内的最大的值放到待排序数据范围的最右侧, 2.从左往右,在待排序数据范围内,数据两两比较,如果前面的比后面的大,则两个数据交换位置{3,10,7,9,5,1,2,8}第一次:待排序的数据 {3,10,7,9,5,1,2,8} {3,7,10,9,5,1,2,8} {3,7,9,10,5,1,2,8} {3,7,9,5,10,1,2,8} {3,7,9,5,1,10,2,8} {3,7,9,5,1,2,10,8} {3,7,9,5,1,2,8,10}第二次: 10已经确定了 arr.length-1待排序的数据(0~arr.length-2) {3,7,9,5,1,2,8,10}  {3,7,5,9,1,2,8,10} {3,7,5,1,9,2,8,10} {3,7,5,1,2,9,8,10} {3,7,5,1,2,8,9,10}第三次: 9,10已经确定了待排序的数据(0~arr.length-3) {3,7,5,1,2,8,9,10}  {3,5,7,1,2,8,9,10} {3,5,1,7,2,8,9,10} {3,5,1,2,7,8,9,10}.....第七次:{1,2,3,5,7,8,9,10}注意:每一轮排序,只能确定待排序范围内最右侧的元素需要排:n-1次,排n次也可以下一轮排序,待排序的范围比上一轮少一个,如果上一轮是0,n 下一轮就是0,n-1*///1.确定排序的次数for (int i = 0; i < arr.length; i++) {//第1次,第2次...第n次//2.确定每次待排序的索引范围/*i = 0, 第1次,(0,arr.length-1)  (0,arr.length-1-0)i = 1, 第2次,(0,arr.length-2)  (0,arr.length-1-1)i = 2, 第3次,(0,arr.length-3)  (0,arr.length-1-2)....i和待排序范围的关系为  (0,arr.length-1-i)*///3.遍历待排序范围内的元素,拿着当前元素和下一个元素比较for (int j = arr.length-1; j < (arr.length - 1 - i); j++) {//4.如果当前元素 > 下一个元素 交换位置if (arr[j] > arr[j + 1]) {//交换j索引和j+1索引处的元素int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}public static void select(int[] arr){/*选择排序: 每一次选择过程,都是选择待排序范围内,最小的元素,和待排序范围内的最左侧的元素进行交换位置{3,10,7,9,5,1,2,8}第一次:待排序的数据范围(0,arr.length-1) {3,10,7,9,5,1,2,8} 最小元素:1 所在的索引5, 交换索引0和索引5的元素  {1,10,7,9,5,3,2,8}第二次:待排序的数据范围(1,arr.length-1) {1,10,7,9,5,3,2,8} 最小元素:2 所在的索引6, 交换索引?和索引6的元素  {1,2,7,9,5,3,10,8}第三次待排序的数据范围(2,arr.length-1) {1,2,7,9,5,3,10,8} 最小元素:3 所在的索引5, 交换索引? 和索引5处的元素{1,2,3,9,5,7,10,8}....第n-1次{1,2,3,5,7,8,9,10}注意:要选择 n-1轮, n轮也可以*///1.确定排序多少轮for (int i = 0; i < arr.length; i++) {//2.确定待排序范围/*当i = 0,第一次,(0,arr.length-1)当i = 1,第二次,(1,arr.length-1)当i = 2,第三次,(2,arr.length-1)...(i,arr.length-1)*///3.找到待排序范围内,最小元素所在的索引//定义变量,记录最小元素所在的索引int index = i;//默认认为索引i处的元素就是最小值所在的索引for (int j = i+1; j < arr.length; j++) {//比较索引index处的元素和索引j处的元素的大小if (arr[j] < arr[index]){index = j;//修正}}//4.交换最左侧的元素(i)和最小值的元素(index)int temp = arr[i];arr[i] = arr[index];arr[index] = temp;}}}

案例9：查找数据

定义一个数组：{1,2,3,4,5,6,7,8,9,10}，利用二分查找法，查找其中任意数据的索引

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

代码示例：

public class Test09 {/*定义一个数组：{1,2,3,4,5,6,7,8,9,10}，利用二分查找法，查找其中任意数据的索引*/public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};System.out.println(findIndex(arr,14));}//定义一个方法,在某个数组中查询指定数据所在的索引public static int findIndex(int[] arr, int target) {//二分查找//1.定义两个指针,默认分别指向数组的头部和尾部int left = 0, right = arr.length - 1;//2.定义变量,记录目标值在数组中出现的索引int index = -1;//默认为-1.代表不存在//3.多次比较,多次移动while (true) {//1.确保 right >= leftif (right < left) {break;}//2.找到中间值int mid = (left + right) / 2;//3.进行比对if (target > arr[mid]){//向右走left = mid+1;}else if (target < arr[mid]){//向左走right = mid-1;}else{//找到了index = mid;break;}}return index;}
}

案例10：整数反转（大整数算法）

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

暂时不用考虑数据太大的问题，把本题的核心思路写出来即可

比如：

输入：x = 123
输出：321

输入：x = -123
输出：-321

输入：x = 120
输出：21

输入：x = 0
输出：0

要注意，考虑到特殊情况：数字大于2147483647，反转之后就超出范围了，此时就要返回0

= -1;//默认为-1.代表不存在
//3.多次比较,多次移动
while (true) {
//1.确保 right >= left
if (right < left) {
break;
}

        //2.找到中间值int mid = (left + right) / 2;//3.进行比对if (target > arr[mid]){//向右走left = mid+1;}else if (target < arr[mid]){//向左走right = mid-1;}else{//找到了index = mid;break;}}return index;
}

}


## 案例10：整数反转（大整数算法）给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。暂时不用考虑数据太大的问题，把本题的核心思路写出来即可比如：	输入：x = 123
	输出：321	输入：x = -123
	输出：-321	输入：x = 120
	输出：21	输入：x = 0
	输出：0要注意，考虑到特殊情况：数字大于2147483647，反转之后就超出范围了，此时就要返回0