集合2

②Collection集合的迭代器对象:
  在根接口(无下标)中使用了一种公共的遍历方式:迭代器遍历(和下标无关)。
如图所示:

注意点:
  Iterator的对象就是迭代器对象(仓库管理员)!只关心有人来仓库取数据或者存数据,判断有的话取走,没有的话报错。
2. 一个集合的迭代器对象是集合自带的!
3. 对象.hasNext();—-判断有没有下一个元素
4. 对象.next();—-取出下一个元素
5. Iterator接口的实现类实现,3和4就是接口的其中两个常用方法。

具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
//创建一个集合对象(多态)
Collection<String> names=new ArrayList<String>();
//添加
names.add("郭德纲");
names.add("刘德华");
names.add("柳岩");
names.add("范伟");

//获取names集合的迭代器对象
Iterator<String> it=names.iterator(); //要和上面集合元素String类型一致
//标准代码(迭代器循环取值):
while(it.hasNext()) //判断有没有下一个元素-对象.hasNext();
{
String s=it.next(); //取出下一个元素-对象.next();
System.out.println(s);
}
}
}

代码结果:
郭德纲
刘德华
柳岩
范伟


三、Iterator接口:
  该接口规定了迭代集合所需要的方法:
  1. 对象.hasNext();—-判断有没有下一个元素
  2. 对象.next();—-取出下一个元素   


四、并发修改异常(ConcurrentModificationException)
  使用Iterator对象/增强for循环遍历集合出现“itcast”字符串 -> 向集合中增加一个“ITCAST(大写)”字符串

举例

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
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
//定义一个集合
Collection<String> its=new ArrayList<String>();
its.add("alibaba");
its.add("tenxun");
its.add("itcast"); //出现了小写的“itcast”字符串
its.add("baidu");
its.add("sohu");
its.add("netease");

//迭代器遍历集合
//获取集合的迭代器对象
Iterator<String> it =its.iterator();

//循环遍历
while(it.hasNext())
{
String itname=it.next();
if("itcast".equals(itname)) //避免问题(常量在前面就不会有null的情况)
{
its.add("ITCAST"); //通过集合去添加
}
}

}
}

代码结果:
Exception in thread “main” java.util.ConcurrentModificationException(出现异常)
at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
at java.util.ArrayList$Itr.next(Unknown Source)
at Main.main(Main.java:21)

分析Concurrent(并发)Modification(修改)Exception(异常):
  JAVA规定,如果一个集合使用迭代器遍历,那么在遍历的过程中不允许修改集合的长度(add/clear/remove)。


五、增强for循环(底层为迭代器)

例如:

1
2
3
4
5
6
7
8
9
10
11
 //普通循环遍历数组
for(int i=0;i<a.length;i++)
{
System.out.println(a[i]);
}

//增强for循环遍历数组
for(i:a)
{
System.out.println(i);
}

  遍历集合还是在使用迭代器遍历,那么在遍历的过程中不允许修改集合的长度(add/clear/remove)。

1
2
3
4
5
6
7
8
9
10
11
12
13
  //增强for循环遍历集合
Collection<String> names=new ArrayList<String>(); //定义
names.add("abc");
names.add("jack");
names.add("rose");
names.add("tom");
//循环遍历
for(String name:names)
{
System.out.println(name);
}
}
}

泛型

一、泛型(JDK1.5的一个新特性)
  泛泛的类型,不确定的类型,可以用应用于不同的类、接口、方法等。

格式

<E>

(E)只是一个类型符号,本质是一个变量,等待接收的是一种数据类型。

1.使用泛型的好处

  • 将运行时期的ClassCastException转换为编译时期的编译错误。
  • 避免类型强转的麻烦。

举例:

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
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
demo01();
demo02();
}

//不使用泛型(不写<E>)
public static void demo01() {
ArrayList names=new ArrayList();
names.add(123);
names.add(true);
names.add("asd");

for(Object i:names)
{
String s=(String)i; //强制类型转换
System.out.println(s);
}
}

//使用泛型
public static void demo02() {
ArrayList<String> names=new ArrayList<String>();  //使用泛型进行创建
names.add("123");
names.add("asded0");
names.add("asd");

for(String i:names)
{
System.out.println(i);
}
}
}

代码结果分析:
执行demo01()方法:
不使用泛型的话,编译时期没有错误,但是执行就会报错。
  Exception in thread “main” java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String
at Main.demo01(Main.java:17)
at Main.main(Main.java:4)

执行demo02()方法:
使用泛型()的话,可以将其转换到编译时期出错。
  123
  asded0
  asd

扩展:
可以使用迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
public class Main {
public static void main(String[] args) {
demo01();
}
//使用迭代器
public static void demo01() {
ArrayList<String> names=new ArrayList<String>(); //定义names对象
names.add("123"); //使用add方法
names.add("asded0");
names.add("asd");
Iterator<String> s=names.iterator(); //对象生成迭代器
while(s.hasNext()) //判断是否由下一个
{
String a=s.next(); //当前位置的值传给a
System.out.println(a); //输出a然后指针自动后移下一个
}
}
}

二、泛型类
格式:
**   public class 类名<E>
**
 注:当你创建类对象的时候,会确定对应的E是那个类型,增加了你的多项选择!

举例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main {
public static void main(String[] args) {
//创建一个Person
Person p=new Person();
p.setAaa("123"); //报错(只有int可以)


}
}

public class Person{
E aaa;
public int getAaa() {
return aaa;
}

public int setAaa(int aaa) {
this.aaa = aaa;
}

}

  如果这样,p。setAaa方法会报错,因为set方法要返回的是int型,而我定义的p对象调用方法给的是String类型的,会报错。

使用泛型类:
1. Person后面加一个<E>
2. 然后将set和get方法返回值都改为E

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
public class Main {
public static void main(String[] args) {
//创建一个Person
Person p=new Person();
p.setAaa("123");

//创建一个Person<E>
Person<String> pp=new Person<String>;
pp.setAaa("ASD"); //可以设置String的

//创建一个Person<E>
Person<Integer> pp=new Person<Integer>;
pp.setAaa(123); /可以设置int的
}
}

public class Person<E>{
E aaa;

public E getAaa() {
return aaa;
}

public void setAaa(E aaa) {
this.aaa = aaa;
}
}

三、泛型方法(少用)
格式:
**   public <T> 返回值类型 方法名(T t);
**
 注:当你调用方法,传递参数的时候确定。

1
2
3
4
5
6
7
8
//Main方法调用
Person<String> pp2=new Person<String>();
pp2.show("asd");

//Person类里面的一个泛型方法:
public <T> void show(T t) {
System.out.println(t);
}

四、泛型接口
格式:
**   public interface 接口名 <E>
**

  1. 当子类实现接口时候,确定接口的泛型。
  2. 当子类实现接口时候,还是不确定泛型,把接口的泛型继续实现下来(就跟抽象类一样,如果实现类没有覆盖重写所有的抽象方法,那么继续让它的实现类实现)

蓝桥杯

  小目标:从今天开始争取每天做一道蓝桥杯题目(用JAVA做!),希望今年能够进国赛!!!

一、矩阵相乘(去年校赛卡住的题目)
问题描述
  给定一个N阶矩阵A,输出A的M次幂(M是非负整数)
  例如:
  A =
  1 2
  3 4
  A的2次幂
  7 10
  15 22
  输入格式
  第一行是一个正整数N、M(1<=N<=30, 0<=M<=5),表示矩阵A的阶数和要求的幂数
  接下来N行,每行N个绝对值不超过10的非负整数,描述矩阵A的值
  输出格式
  输出共N行,每行N个整数,表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开
  样例输入
  2 2
  1 2
  3 4
  样例输出
  7 10
  15 22

思路
  我先定义两个数组,a数组用来存放一开始的值,然后通过定义num不断地将更新的值放入后面的t数组之中,就可以减少不断的用新的数组去存旧数组的值,保证减少算法时间和空间复杂度。

代码实现

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
import java.util.Scanner;
public class Collection {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int n=input.nextInt(); //定义矩阵的行和列
int m=input.nextInt(); //定义矩阵乘方次数
int[][] a=new int[n][n]; //定义原始数组
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
a[i][j] = input.nextInt(); //输入数组元素
}
}
int[][] t=new int[n][n]; //最终存放的数组
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int num=0;
for(int k=0;k<n;k++)
{
num+=a[i][k]*a[k][j]; //利用矩阵相乘原理得到新的数组所对应的位置的值
}
t[i][j]=num; //将相乘结果传给数组t
}
}

for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
System.out.print(t[i][j]+" ");
}
System.out.println(); //保证每行分割
}

}
}

代码结果如下


二、斐波拉契数列(基础题)
问题描述
  Fn除以10007的余数是多少。
  说明:在本题中,答案是要求Fn除以10007的余数,因此我们只要能算出这个余数即可,而不需要先计算出Fn的准确值,再将计算的结果除以10007取余数,直接计算余数往往比先算出原数再取余简单。
  样例1输入
  10
  样例1输出
  55
  样例2输入
  22
  样例2输出
  7704 
  数据规模与约定
1 <= n <= 1,000,000。

思路:
递归(不推荐)
Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。
代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;
public class Collection {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
a[1]=a[2]=1;
int m=feibo(n)%10007; //最终的值除以10007求余数
System.out.println(m);

}

public static int feibo(int n){
if(n==1||n==2) //前两个的值需要给出,才能依次算出后面的值
return 1;
else
return (feibo(n-1)+feibo(n-2)); //递归主要思路
}
}

代码结果如下:

动态规划
动态规划和递归有很大的相同处,但是动态规划而言,起码性能很高,不会出现提交代码系统超时的问题,而且很容易想到和实现。
将前两项赋值为1,然后从第三项开始是前两项加,假设算前三项,第一项为l,第二项为r,第三项为l+r。然后要计算第四项的时候,我们需要将第二项的r就成了计算第四项的l,那么第三项的sum就成了第四项计算时候的r,因此不断地替换计算,动态规划的思路就是往前推,求上一个结果的答案,然后依次推出接下来答案的结果。
代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
public class Collection {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
int m=feibo(n-1,a)%10007; //题目要求对10007取余
System.out.println(m);
}
public static int feibo(int n,int[] a){
int l=1,r=1,sum=0;
if(n<=1)
return n;
for(int i=2;i<=n;i++)
{
sum=l+r; //前两项之和
l=r; //将现在的第二项变成计算下一项的左边值
r=sum; //将现在的和变成计算下一项的右边值
}
return sum;
}
}

代码结果如下:


三、字母图形
问题描述
  利用字母可以组成一些美丽的图形,下面给出了一个例子:
  ABCDEFG
  BABCDEF
  CBABCDE
  DCBABCD
  EDCBABC
这是一个5行7列的图形,请找出这个图形的规律,并输出一个n行m列的图形。
  
输入格式
  输入一行,包含两个整数n和m,分别表示你要输出的图形的行数的列数。
输出格式
  输出n行,每个m个字符,为你的图形。
  
  样例输入
  5 7
  样例输出
  ABCDEFG
  BABCDEF
  CBABCDE
  DCBABCD
  EDCBABC
数据规模与约定
1 <= n, m <= 26。

思路:
  肯定需要使用二维数组去存放最后的字母图形,使用二重循环去遍历每一个位置。通过规律可以得到只要i和j的差的绝对值为哪个数就对应字母表中和A的差距位置,因此利用数组下标去判断绝对值为1就输出B,2就输出C,以此类推。
  假设i为2,j为3:
  则判断a[2][3]的位置存放的应该就是 2-3的绝对值为1所以存放B。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
int[][] a=new int[n][m];
char[] b={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; //用下标方便的放入相对于的值

for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int c=i-j; //求下标之差(可能有负数)
int d=(Math.abs(c))%26; //求下标之差的绝对值(如果大于26行就需要求余)
System.out.print(b[d]);
}
System.out.println();
}
}
}

代码结果如下:

编程出现的问题:

  1. 定义26个字母的数组的时候写错了,导致只有百分之30的准确性。
  2. 这个题目限制了行数为26,但是如果行数太多的话下标的d就需要对26取余数(int d=(Math.abs(c))%26;)。
  3. 输出格式之间没有空格,当时打了空格,只有百分之10的准确性。

四、十进制转十六进制
问题描述
  十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号,分别表示十进制数的0至15。十六进制的计数方法是满16进1,所以十进制数16在十六进制中是10,而十进制的17在十六进制中是11,以此类推,十进制的30在十六进制中是1E。
  给出一个非负整数,将它表示成十六进制的形式。
输入格式
  输入包含一个非负整数a,表示要转换的数。0<=a<=2147483647
输出格式
  输出这个整数的16进制表示
样例输入
30
样例输出
1E

思路:
不再像c语言那样手写,我们可以考虑直接通过使用toHexString()方法转换成十六进制、使用toUpperCase()方法将小写字母转换为大写字母。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
long n=input.nextLong(); //定义了一个long型的数字
System.out.printf(Long.toHexString(n).toUpperCase()); //转换为十六进制数并且为大写字母



}
}

代码结果如下:


五、十六进制转十进制
问题描述
  从键盘输入一个不超过8位的正的十六进制数字符串,将它转换为正的十进制数后输出。
  注:十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F表示。
样例输入
FFFF
样例输出
65535

思路:
利用JAVA中parseLong(要被转换的数,被转换的数位几进制)方法
例如要将16进制的FFFF转换就需要输入n=FFFF然后调用praseLong函数(num,16)。

代码实现:

1
2
3
4
5
6
7
8
9
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String num=input.nextLine();
Long da=Long.parseLong(num,16);
System.out.println(da);
}
}

代码结果如下:


六、集合运算
问题描述
给出两个整数集合A、B,求出他们的交集、并集以及B在A中的余集。
输入格式
  第一行为一个整数n,表示集合A中的元素个数。
  第二行有n个互不相同的用空格隔开的整数,表示集合A中的元素。
  第三行为一个整数m,表示集合B中的元素个数。
  第四行有m个互不相同的用空格隔开的整数,表示集合B中的元素。
  集合中的所有元素均为int范围内的整数,n、m<=1000。
输出格式
  第一行按从小到大的顺序输出A、B交集中的所有元素。
  第二行按从小到大的顺序输出A、B并集中的所有元素。
  第三行按从小到大的顺序输出B在A中的余集中的所有元素。
样例输入
5
1 2 3 4 5
5
2 4 6 8 10
样例输出
2 4
1 2 3 4 5 6 8 10
1 3 5
样例输入
4
1 2 3 4
3
5 6 7
样例输出
1 2 3 4 5 6 7
1 2 3 4

思路:
  一开始没想到集合!!想着暴力循环找到的相同的就是交集,然后A里面有的B没有的就是差集,并就是A和差集之和。
  最后看大佬的思路才发现用集合,我选择使用Set集合(set存放的是不重复的元素)。

  1. add()增加元素
  2. retain()求交集
  3. remove求差集
  4. add两次求并集(存放不重复的元素!)

代码实现:

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
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main{
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
Set<Integer> result=new HashSet<Integer>();//存放最终结果
Set<Integer> set1=new HashSet<Integer>();//第一个
Set<Integer> set2=new HashSet<Integer>();//第二个
int n=input.nextInt();//输入第一个集合的长度
for (int i = 0; i < n; i++)
{
set1.add(input.nextInt());//add输入集合的元素
}
int m=input.nextInt(); //输入第二个集合的长度
for (int i = 0; i < m; i++)
{
set2.add(input.nextInt());//add输入集合的元素
}

result.clear(); //清空结果集合
result.addAll(set1);//将第一个集合的元素放进去
result.retainAll(set2);//retain求两个的交集
System.out.println("交集 = " + result);

result.clear();//清空(为下一个要求服务)
result.addAll(set1);//将第一个集合的元素放进去
result.addAll(set2);//将第二个集合的元素放进去(不会把重复的放进去)
System.out.println("并集 = " + result);

result.clear();//清空(防止上面的过程干扰)
result.addAll(set1);//将第一个集合的元素放进来
result.removeAll(set2);//将相同的元素排除掉
System.out.println("差集 = "+result);
}
}

代码结果如下:

  • 因为这个题目需要让集合中的元素一个一个输出,因此需要增强for循环
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
	  result.clear();   //清空结果集合
result.addAll(set1);//将第一个集合的元素放进去
result.retainAll(set2);//retain求两个的交集

for(int i:result)
System.out.print(i+" ");

System.out.println();


result.clear();//清空(为下一个要求服务)
result.addAll(set1);//将第一个集合的元素放进去
result.addAll(set2);//将第二个集合的元素放进去(不会把重复的放进去)

for(int i:result)
System.out.print(i+" ");

System.out.println();


result.clear();//清空(防止上面的过程干扰)
result.addAll(set1);//将第一个集合的元素放进来
result.removeAll(set2);//将相同的元素排除掉

for(int i:result)
System.out.print(i+" ");

System.out.println();

}
}

代码结果如下:


七、报时助手
问题描述
  给定当前的时间,请用英文的读法将它读出来。
  时间用时h和分m表示,在英文的读法中,读一个时间的方法是:
  如果m为0,则将时读出来,然后加上“o’clock”,如3:00读作“three o’clock”。
  如果m不为0,则将时读出来,然后将分读出来,如5:30读作“five thirty”。
  时和分的读法使用的是英文数字的读法,其中0~20读作:
  0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。
  30读作thirty,40读作forty,50读作fifty。
  对于大于20小于60的数字,首先读整十的数,然后再加上个位数。如31首先读30再加1的读法,读作“thirty one”。
  按上面的规则21:54读作“twenty one fifty four”,9:07读作“nine seven”,0:15读作“zero fifteen”。
输入格式
  输入包含两个非负整数h和m,表示时间的时和分。非零的数字前没有前导0。h小于24,m小于60。
输出格式
  输出时间时刻的英文。
样例输入
0 15
样例输出
zero fifteen

思路:
  分为判断分钟是否为0的情况:如果为0就直接判断小时输出“小时+o’clock”;如果不为0就要分为判断小时和分钟然后依次输出。主要是提前要用String数组分别存放好0-20 和 20 30 40 50的英文字母。

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
import java.util.Scanner;
public class ReflectTest {
public static void main(String[] args) {
//用a和b的字符串数组存放时刻时间
String a[]={"zero","one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty"};
String b[]={"twenty","thirty","forty","fifty"};


//设置h和m为输入的分钟和小时数
Scanner input=new Scanner(System.in);
int h=input.nextInt();
int m=input.nextInt();

if(m==0)//如果分钟为0的话就是只有小时 后面加o'clock
{
switch(h/10)//判断输出
{
case 0:System.out.println(a[h%10]+" "+"o'clock");break; //直接在a数组找
case 1:System.out.println(a[h]+" "+" "+"o'clock");break;//直接在a数组找
case 2:System.out.println(b[0]+" "+a[h%10]+" "+"o'clock");break; //twenty+个位的
}
}

else
{
switch(h/10)//和if条件里面的相同
{
case 0:System.out.print(a[h%10]);break;
case 1:System.out.print(a[h]);break;
case 2:System.out.print(b[0]+" "+a[h%10]);break;
}

switch(m/10)
{
case 0:System.out.print(" "+a[m%10]);break;
case 1:System.out.print(" "+a[m]);break;//直接在a数组找
case 2:System.out.print(" "+b[0]+" "+a[m%10]);break;
case 3:System.out.print(" "+b[1]+" "+a[m%10]);break;
case 4:System.out.print(" "+b[2]+" "+a[m%10]);break;
case 5:System.out.print(" "+b[3]+" "+a[m%10]);break;
}

}

}
}

八、集合运算
问题描述
给出两个整数集合A、B,求出他们的交集、并集以及B在A中的余集。
输入格式
第一行为一个整数n,表示集合A中的元素个数。
第二行有n个互不相同的用空格隔开的整数,表示集合A中的元素。
第三行为一个整数m,表示集合B中的元素个数。
第四行有m个互不相同的用空格隔开的整数,表示集合B中的元素。
集合中的所有元素均为int范围内的整数,n、m<=1000。
输出格式
第一行按从小到大的顺序输出A、B交集中的所有元素。
第二行按从小到大的顺序输出A、B并集中的所有元素。
第三行按从小到大的顺序输出B在A中的余集中的所有元素。
样例输入
5
1 2 3 4 5
5
2 4 6 8 10
样例输出
2 4
1 2 3 4 5 6 8 10
1 3 5
样例输入
4
1 2 3 4
3
5 6 7
样例输出
1 2 3 4 5 6 7
1 2 3 4

解题思路:
  本来打算使用数组去做,发现一排序之后相同的数字不一样在一个位置而且比较麻烦。所以我选择了用集合(TreeSet)
–>交集:使用一个tempA复制了a->然后用a移除所有b中和a相同的,然后用tempA把剩下的移除之后就剩下交集。
–>并集:使用addALL(b)就可以吧不重复的b放进去
–>差集:使用removeALL(b)把A和B相同的移过以外的元素。

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
package lianxi;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
TreeSet<Integer> treeSetA=new TreeSet<Integer>();//第一个集合A
int n=input.nextInt();
for(int i=0;i<n;i++)
{
treeSetA.add(input.nextInt());
}

TreeSet<Integer> treeSetB=new TreeSet<Integer>();//第二个集合B
int m=input.nextInt();
for(int i=0;i<m;i++)
{
treeSetB.add(input.nextInt());
}

input.close();
printDivide(treeSetA, treeSetB);
printAdd(treeSetA, treeSetB);
printRemain(treeSetA, treeSetB);
}
public static void printDivide(TreeSet<Integer> a,TreeSet<Integer> b)
{
TreeSet<Integer> tempA=(TreeSet<Integer>) a.clone();//第三个集合是复制a集合的
a.removeAll(b);
tempA.removeAll(a);
for (int i : tempA) {
System.out.print(i + " ");
}
System.out.println();
}

public static void printAdd(TreeSet<Integer> a,TreeSet<Integer> b)
{
a.addAll(b);
for(int i:a)
{
System.out.print(i+" ");
}
System.out.println();

}


public static void printRemain(TreeSet<Integer> a, TreeSet<Integer> b)
{
a.removeAll(b);
for (int i : a) {
System.out.print(i + " ");
}
System.out.println();
}

}

代码结果如下:


九、大等于n的最小完全平方数 **
**问题描述

  输出大等于n的最小的完全平方数。
  若一个数能表示成某个自然数的平方的形式,则称这个数为完全平方数
  Tips:注意数据范围
输入格式
  一个整数n
输出格式
  大等于n的最小的完全平方数
样例输入
71711
样例输出
71824
数据规模和约定
  n是32位有符号整数

思路:
  这道题目主要是将n先分为小于等于0和大于0的数两类,小于等于0的数最小的完全平方数就是0;而大于等于0的数需要让x转换成long型去比对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
double x=Math.sqrt(n);//取double类型的x
long j=0;
if(n<=0) //第一种情况结果为0
{
j=0;
System.out.println(j*j);
}
else//第二种情况结果要从x转换为long之后一个一个挪直到结果
{
if((long)x*(long)x==n)
j= (long)x;
else
j=(long)x+1;
System.out.println(j*j);

}

}
}

代码结果如下:


十、阿尔法乘积
问题描述
  计算一个整数的阿尔法乘积。对于一个整数x来说,它的阿尔法乘积是这样来计算的:如果x是一个个位数,那么它的阿尔法乘积就是它本身;否则的话,x的阿尔法乘积就等于它的各位非0的数字相乘所得到的那个整数的阿尔法乘积。例如:4018224312的阿尔法乘积等于8,它是按照以下的步骤来计算的:
  4018224312 → 418224312 → 3072 → 372 → 42 → 4*2 → 8
  编写一个程序,输入一个正整数(该整数不会超过6,000,000),输出它的阿尔法乘积。
  输入格式:输入只有一行,即一个正整数。
  输出格式:输出相应的阿尔法乘积。
  输入输出样例
样例输入
4018224312
样例输出
8

思路如下:
  发现这个题目就是不停的乘不停的乘,一开始本来用数组但是发现两个while循环之后答案只有70%的准确率(就是因为int不能满足题意,所以改用函数+定义long型)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
long n=input.nextLong();//输入的数定义为long型
System.out.println(f(n));
}

public static long f(long n) {//不断地输入n
if(n<10) //满足乘积最终为个位数
return n;
long sum=1;
while(n>0)
{
if(n%10!=0) //拆开的目前位数字不为0
sum*=n%10; //不断乘积得到目前阶段的积
n/=10; //拆数(拆的更小)
}
return f(sum);//不停地递归找答案
}

}

代码结果如下:


十一、求阶乘最右边的第一个非0数(BigDecimal)
一个整数n的阶乘可以写成n!,它表示从1到n这n个整数的乘积。阶乘的增长速度非常快,例如,13!就已经比较大了,已经无法存放在一个整型变量中;而35!就更大了,它已经无法存放在一个浮点型变量中。因此,当n比较大时,去计算n!是非常困难的。幸运的是,在本题中,我们的任务不是去计算n!,而是去计算n!最右边的那个非0的数字是多少。例如,5!=12345=120,因此5!最右边的那个非0的数字是2。再如,7!=5040,因此7!最右边的那个非0的数字是4。再如,15!= 1307674368000,因此15!最右边的那个非0的数字是8。请编写一个程序,输入一个整数n(0<n<=100),然后输出n!最右边的那个非0的数字是多少。
输入:
  7
输出:
  4

思路如下:
  使用BigDecimal类定义一个sum得出结果用。
然后通过 valueof() 方法制造BigDecimal类的对象,通过multiply方法从1乘到n的结果返回给sum。
然后将结果通过toString()方法转成字符串,倒序判断是不是为0最后得出结果。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.math.BigDecimal;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n=input.nextInt();
BigDecimal sum=BigDecimal.ONE;//设置为1
for(int i=1;i<=n;i++)
{
sum=sum.multiply(BigDecimal.valueOf(i));//1*2*3*...*n就是一直到n(阶乘)
}
String s=sum.toString(); //转为字符串
for(int i=s.length()-1;i>=0;i--)
{
if(s.charAt(i)!='0')
{
System.out.println(s.charAt(i));
break ;
}
}
}
}

代码结果如下:


十二、二进制—>十进制
问题描述
  编写一个程序,输入一个二进制的字符串(长度不超过32),然后计算出相应的十进制整数,并把它打印出来。
  输入格式:输入为一个字符串,每个字符都是’0’或’1’,字符串的长度不超过32。
  输出格式:输出一个整数。
  输入输出样例
样例输入
1101
样例输出
13

思路:
方法1.使用字符串n输入一连串2进制数字,然后通过BigInteger类对象创建BigInteger(n,2)即可得到答案。
方法2.通过字符串转字符数组,然后从最后面到最前面循环,不断地sum求和就可以了。

方法1代码实现:

1
2
3
4
5
6
7
8
9
10
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String n=input.next();
BigInteger s=new BigInteger(n,2);//使用new就行
System.out.println(s);
}
}

方法2代码实现:
注意:
1.一定要将字符1转为数字1!!! ——-(int)a[i]-48
2.pow()用于求2的多少次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String n=input.next();//输入一个字符串
int sum=0;
char[] a=n.toCharArray();//字符串转成字符数组(相反就用valueOf()方法)
for(int i=a.length-1;i>=0;i--)//倒序寻找(方便2的0次方增大)
{
sum+=((int)a[i]-48)*Math.pow(2,a.length-i-1);//一定要记得将字符1强制类型转换后减去48(0的ASCII码)*2的对应次方
}
System.out.println(sum);
}
}

十三、阶乘末尾(求末尾len位)
问题描述
  给定n和len,输出n!末尾len位。
输入格式
  一行两个正整数n和len。
输出格式
  一行一个字符串,表示答案。长度不足用前置零补全。
样例输入
6 5
样例输出
00720
数据规模和约定
  n<=30, len<=10。

思路:
  和之前的题目一样需要考虑用BigDecimal类定义一个s大数,然后调用multiply方法计算阶乘,可以直接通过输出s得到阶乘的结果。但是这个题目需要将其转换为字符串然后转换为字符数组对比长度和len大小。如果长度>len就直接输出就行,如果小于的话需要在前面输出cha这么多个0才行。

代码实现:

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
import java.math.BigDecimal;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int len=input.nextInt();
BigDecimal s=BigDecimal.ONE;//设定一个大数s
for(int i=1;i<=n;i++)
{
s=s.multiply(s.valueOf(i));//利用乘法方法 然后从1*2*...n
}
String s1=s.toString();//转成字符串s1
char[] a=s1.toCharArray();//转为字符数组a
int cha=a.length-len;
if(cha<0)
{
int jueduizhi=Math.abs(cha);
while(jueduizhi--!=0)
{
System.out.print("0"); //差记为补几个0在前面
}

for(int i=0;i<a.length;i++)
{
System.out.print(a[i]); //补了0之后再输出其他的数字
}
}
else //如果长度够长
{
for (int i=cha;i<a.length;i++)
{
System.out.print(a[i]); //直接从cha的位置正序输出
}
}

}

}

代码结果如下:


十四题、明明的随机数
问题描述
  明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式
  输入有2行,第1行为1个正整数,表示所生成的随机数的个数:
  N
  第2行有N个用空格隔开的正整数,为所产生的随机数。
输出格式
  输出也是2行,第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。
样例输入
10
20 40 32 67 40 20 89 300 400 15
样例输出
8
15 20 32 40 67 89 300 400

思路:
  我发现动态的和数据有关的一定要去使用集合!!!集合的动态变换比较方便!这道题目就用TreeSet集合(可以自动排序加减少重读的内容)。
  然后使用while循环不断地判断是不是有下一个,用add方法去添加内容,然后添加之后size方法输出不重复的排序之后的集合长度,for循环输出每一个内容。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()) //判断是否有下一个
{
int num=input.nextInt();
TreeSet<Integer> set=new TreeSet<>(); //TreeSet集合存储
for(int i=0;i<num;i++)
{
set.add(input.nextInt()); //输入内容
}

System.out.println(set.size()); //自动排序然后删除重复值之后的长度

for(int i:set)
{
System.out.print(i+" "); //增强for循环去输出结果
}

}

}
}

代码结果如下:


十五、 黑色星期五(使用Calendar)
问题描述
  有些西方人比较迷信,如果某个月的13号正好是星期五,他们就会觉得不太吉利,用古人的说法,就是“诸事不宜”。请你编写一个程序,统计出在某个特定的年份中,出现了多少次既是13号又是星期五的情形,以帮助你的迷信朋友解决难题。
  输入输出样例
  样例输入
  1998
  样例输出
  3

思路:
使用JAVA中Calendar类可以很方便的得出结果,使用getInstance()方法获取一个默认时区的日历,通过set方法寻找第一个条件某个月的13号,然后通过对比Calendar类中固定的DAT_OF_WEEK==6(周五)从而满足两个条件。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n=input.nextInt();
int sum=0;//计数
Calendar c=Calendar.getInstance();//获得一个时区默认的日历
for(int i=1;i<13;i++)
{
c.set(n,i,13); //寻找每个月的13号日子
if(c.get(Calendar.DAY_OF_WEEK)==6) //1是周日 2是周一 3是周二...6是周五
sum++; //如果c获得的是周五就增加一个
}
System.out.println(sum);
}
}

代码结果如下:


十六、身份证号码升级
问题描述
  从1999年10月1日开始,公民身份证号码由15位数字增至18位。(18位身份证号码简介)。升级方法为:
  1、把15位身份证号码中的年份由2位(7,8位)改为四位。
  2、最后添加一位验证码。验证码的计算方案:
  将前 17 位分别乘以对应系数 (7 9 10 5 8 4 2 1 6 3 7 9 10 5 8 4 2) 并相加,然后除以 11 取余数,0-10 分别对应 1 0 x 9 8 7 6 5 4 3 2。
  请编写一个程序,用户输入15位身份证号码,程序生成18位身份证号码。假设所有要升级的身份证的四位年份都是19××年
输入格式
  一个15位的数字串,作为身份证号码
输出格式
  一个18位的字符串,作为升级后的身份证号码
样例输入
110105491231002
样例输出
11010519491231002x
数据规模和约定
  不用判断输入的15位字符串是否合理

思路:
  考虑要用字符串s将15位身份证号码输入进去,然后转成字符数组a,设置一个数组b去一个一个从a拿到(赋值-48)。然后例如:49-1949我就是将4直接加190转换成194之后每一位去乘相应的系数得到最后一位,然后switch语句判断得到答案(x先用-1替换掉),最后依次输出b数组。

代码实现如下:

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
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s=input.next();//用字符串输入15位身份证
char[] a=s.toCharArray();//转成字符数组
int[] b=new int[16];//用16位去表示结果(17-1917只把1编程191)
for(int i=0;i<a.length;i++)
{
b[i]=a[i];//把每一位传给int型数组b
b[i]=b[i]-48;//必须减48才能从字符转为数字的0/1...9
}
b[6]=b[6]+190;//将第一位x直接变成19x
b[15]=(b[0]*7)+(b[1]*9)+(b[2]*10)+(b[3]*5)+(b[4]*8)+(b[5]*4)+2+9+((b[6]%10)*6)+(b[7]*3)+(b[8]*7)+(b[9]*9)+(b[10]*10)+(b[11]*5)+(b[12]*8)+(b[13]*4)+(b[14]*2);//注意我现在的只有16位(每一位对应的乘要变化)
b[15]=b[15]%11;//计算出来之后对11取余
switch (b[15])//依次判断出最后一位是什么
{
case 0:b[15]=1;break;
case 1:b[15]=0;break;
case 2:b[15]=-1;break; //先用-1代替x
case 3:b[15]=9;break;
case 4:b[15]=8;break;
case 5:b[15]=7;break;
case 6:b[15]=6;break;
case 7:b[15]=5;break;
case 8:b[15]=4;break;
case 9:b[15]=3;break;
case 10:b[15]=2;break;
}

for(int i=0;i<b.length;i++)
{
if(i!=15)
System.out.print(b[i]);//输出除过最后一位的数字
else //判断最后一位
if(b[15]==-1)
System.out.print("x");//这里将-1换成x
else
System.out.println(b[15]);//其他的就按照switch语句的答案输出
}

}
}

代码结果如下:


十七、不同单词个数统计(split()方法)
问题描述
  编写一个程序,输入一个句子,然后统计出这个句子当中不同的单词个数。例如:对于句子“one little two little three little boys”,总共有5个不同的单词:one, little, two, three, boys。
  说明:(1)由于句子当中包含有空格,所以应该用gets函数来输入这个句子;(2)输入的句子当中只包含英文字符和空格,单词之间用一个空格隔开;(3)不用考虑单词的大小写,假设输入的都是小写字符;(4)句子长度不超过100个字符。
  输入格式:输入只有一行,即一个英文句子。
  输出格式:输出只有一行,是一个整数,表示句子中不同单词的个数。
输入输出样例
样例输入
one little two little three little boys
样例输出
5

思路:
  主要是用nextLine()输入!!!(next会把单词之间的空格当做结束符),然后通过split()方法将s隔开成一个一个单词存放在String字符串数组之中,这一步其实可以输出a.length得到长度。但是这个题目必须要输出不重复单词的个数,可以通过二重循环将相同的单词其中一个变成空格(可以二次使用split方法)
  然后只要数组不为空就可以sum加一个,最终sum值就是答案。
代码实现:

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
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.nextLine();//用nextLine格式输入要判断的字符串
String[] a = s.split(" ");//用split方法得到每个单词
int sum = 0;//计数
for (int i = 0; i < a.length; i++)
{
for (int j = i + 1; j < a.length; j++)//二重循环依次判断
{
if (a[i].equals(a[j]))
{
a[j] = " ";//将相同的其中一个单词换成空格
}
}
}
for (int i = 0; i < a.length; i++)
{
if(a[i]!=" ")
sum++;//输出不是空格的位置的单词数量
}
System.out.println(sum);
}
}

代码结果如下:


十八、判断回文(字符串)
问题描述:
编程判断一个字符串是否是回文,当字符串是回文时,输出字符串:yes!,否则输出字符串:no!。所谓回文即正向与反向的拼写都一样,如adgda。  长度在100以内,且全为小写字母
样例输入
adgda
样例输出
yes!

思路:
  我考虑的是输入字符串s1和s2对比,s1就用字符串转字符串数组的方式转成字符串数组a,然后反序得到b,从而字符串数组转字符串s2,然后进行对比。
字符串—->字符串数组/字符数组:

1
2
3
String s=input.next();
char[] a=s.toCharArray();//字符数组
String[] a=s.split("");//字符串数组("里面随自己")

字符串数组—->字符串

1
2
3
4
5
6
7
String[] b=new String[n];
StringBuffer s=new StringBuffer();
for(String i:b)
{
s.append(i);
}
System.out.println(s.toString());//要用toString方法才能转成字符串

代码实现:

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

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s1 = input.next();//输入要判断的字符串s1
String[] a = s1.split("");//利用split方法隔成字符串数组a
String[] b = new String[a.length];//创建一个字符串数组b
int j = 0;
for (int i = a.length - 1; i >= 0; i--)
{
b[j++] = a[i]; //反序把a输入到b里面
}

StringBuffer s2 = new StringBuffer();//使用StringBuffer 创建一个字符串s2
for (String i : b)
{
s2.append(i);//增强for循环将字符串数组转成字符串
}


if(s1.equals(s2.toString()))//必须将s2.toString才可以判断
{
System.out.println("yes!");
}
else
{
System.out.println("no!");
}

}
}

代码结果如下:


十九、十六进制转10/8进制
  用户输入三个字符,每个字符取值范围是0-9,A-F。然后程序会把这三个字符转化为相应的十六进制整数,并分别以十六进制,十进制,八进制输出,十六进制表示成3位,八进制表示成4位,若不够前面补0。(不考虑输入不合法的情况)
输入
  1D5
输出
(注意冒号后面有一个空格)
  Hex: 0x1D5
  Decimal: 469
  Octal: 0725
思路:
16进制就是直接输出;10进制就是用Long型的parseLong方法;8进制就是使用Integer的toOctalString()方法,但是里面的属性是Integer的valueOf方法(s,16)。

代码实现:

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
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.next();
System.out.println("Hex: Ox" + s);

Long shi = Long.parseLong(s, 16);//转成十进制
System.out.println("Decimal: " + shi);

String ba = Integer.toOctalString(Integer.valueOf(s, 16));//转成8进制
char[] a = ba.toCharArray();
int cha = 4 - a.length;
if (cha == 0)
{
System.out.println("Octal: " +ba);
}
if (cha == 1)
{
System.out.println("Octal: 0" +ba);
}
if (cha == 2)
{
System.out.println("Octal: 00" +ba);
}
if (cha == 3)
{
System.out.println("Octal: 000" +ba);
}

}
}

代码结果如下:


二十、删除重复元素(使用数组下标)
问题描述
  为库设计新函数DelPack,删除输入字符串中所有的重复元素。不连续的重复元素也要删除。
  要求写成函数,函数内部使用指针操作。
样例输入
1223445667889
样例输出
13579
样例输入
else
样例输出
ls
数据规模和约定
  字符串数组最大长度为100。

思路分析:
  通过数组下标,所有的先为0而后面将字符串出现一次增加一次,当最后为1就输出(可以去掉出现两次以上的元素)

代码结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s=input.next();
int[] a=new int[10001];
for(int i=0;i<s.length();i++)
{
a[s.charAt(i)]++;//字符串的每一次为字符对应的下标数组元素从1变
}

for(int i=0;i<s.length();i++)
{
if(a[s.charAt(i)]==1)//只让出现一次的元素输出
{
System.out.print(s.charAt(i));
}
}


}
}

代码结果如下:


集合1

一、JAVA的集合
  Java集合类是一种特别有用的工具类,可用于存储数量不确定的对象(对象的引用),并可以实现常用 的数据结构,如栈、队列等。除此之外,Java集合还可用于保存具有映射关系的关联数组。Java集合大致可分为List、Set、Queue和Map四种体系。

  • List:代表有序、 重复的集合
  • Set:代表无序、不可重复的集合
  • Map:代表具有映射关系的集合
  • Queue:代表一种队列集合实现(Java5之后)

JAVA的集合类与数组的区别

  1. 数组一旦确定之后不能更改大小,所以JAVA引出了集合类的东西来满足存放长度不确定的对象(对象的引用)。
  2. JAVA的集合类只能存放对象,数组也可以存放基本类型数据。

二、Connection接口(根接口)

①常用的方法:

  1. public boolean add(E e); 给定的对象放到当前集合中。
  2. public void clear(); 清空当前集合中的所有元素。
  3. public boolean remove(E e); 把给定的对象在当前集合中删除。
  4. public boolean contains(E e); 判断当前集合是否包含给定的对象。
  5. public boolean isEmpty(); 判断当前集合是否为空。
  6. public int size(); 返回集合中元素的个数。
  7. public Object[] toArray(); 把集合中的元素存储到数组中。

具体实现:

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
import java.util.ArrayList;
import java.util.Collection;

public class Main {
public static void main(String[] args) {
//创建一个集合对象(多态)
Collection<String> names=new ArrayList<String>();
//添加
names.add("郭德纲");
names.add("刘德华");
names.add("柳岩");
names.add("范伟");

//删除
System.out.println(names); 输出[郭德纲, 刘德华, 柳岩, 范伟]
boolean a=names.remove("郭德纲");
System.out.println(a); //输出true
System.out.println(names); //输出[刘德华, 柳岩, 范伟]

//获取长度
int size=names.size();
System.out.println(size); //输出3

//清空集合中所有元素
names.clear();

//判断是否为空
boolean b=names.isEmpty();
System.out.println(b); //输出true

}
}

代码结果:

[郭德纲, 刘德华, 柳岩, 范伟]
true
[刘德华, 柳岩, 范伟]
3
true


Lambda表达式

一、介绍接口实现的三种方法,引出Lambda表达式。

  定义接口(comparator):

1
2
3
interface comparator{ 
int compare(int a,int b); //抽象方法
}

  定义实现类(Mycomparator):

1
2
3
4
5
6
class Mycomparator implements comparator{  //实现类必须实现接口里面的所有抽象方法
@override
public int compare(int a,int b){
return a-b;
}
}

  • 1.使用接口实现类
    1
    2
    3
    4
    5
    6
    public class ChengXu{
    public static void main(String[] args){
    comparator comparator1=new Mycomparator(); //多态(左边父类,右边子类) 编译在左,实现在右
    comparator1.compare;
    }
    }

  • 2.使用匿名接口类
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public class ChengXu{
    public static void main(String[] args){
    comparator comparator2=new comparator(){ //哪个接口要实现就写哪个接口的匿名抽象类
    @override
    public int compare(int a,int b){
    return a-b;
    }
    }
    }
    }

  • 3.使用Lambda表达式
    1
    2
    3
    4
    5
    public class ChengXu{
    public static void main(String[] args){
    comparator comparator3=(a,b) ->a-b;
    }
    }

二、Lambda表达式的基本语法
1.Lambda表达式只能描述只有一个抽象方法的接口(@FunctionalInterface注释)。
2.也可以用于集合类中遍历集合元素。
3.包含三个部分

  1. 形参列表:允许省略参数类型。(一个参数的话可以省略形参的圆括号)。
  2. 箭头(->):必须有英文画线和大于符号组成。
  3. 代码块:如果只有一句,省略”{}”。
  4. java8中引入了一个新的操作符”->”(箭头操作符/Lambda操作符),将Lambda表达式拆分为两个部分:
  5. 左边:Lambda表达式的参数列表(实现的抽象方法参数相同)
  6. 右边:Lambda表达式中所需要的功能(方法体)

三、函数式接口
  代表只含有一个抽象方法接口(默认方法、类方法可以有很多)。
  JAVA8专门为函数式接口提供了@FunctionalInterface注解。放在接口定义的前面,用于告诉编译器执行更为严格检查,不是函数式接口就会报错。


例如:

1
2
3
4
5
6
Runnable r=()->{
for(int i=0;i<100;i++)
{
System.out.println();
}
};

解释:
Lambda表达式实现的是匿名方法(只能实现特定函数式接口的唯一方法),因此就有两个限制

  1. Lambda表达式的目标类型必须是明确的函数式接口。(我觉得最适合的就是(参数列表强制类型转换))
  2. Lambda表达式只能为函数式接口创建对象。

Java在java.util.function包下面预定义了很多函数式接口

  1. XxxFunction:这类接口中通常有一个apply()抽象方法,对参数处理后返回一个新的值。
  2. XxxConsumer:这类接口中通常有一个accept()抽象方法,对参数处理后但是不返回新的值。
  3. XxxPredicate:这类接口中通常有一个test()抽象方法,对参数进行某种处理后返回一个boolean值,用于筛选数据。
  4. XxxSupplier:这类接口中通常有一个getAsXxx()抽象方法,不需要输入一个值通过某种算法返回一个值。

四、方法引用和构造器引用
  如果Lambda表达式的代码块只有一条代码,那么就可以在代码块中使用方法引用和构造器引用。

人机交互实验

页面介绍:主要是电影资源网,分为热映部分和广告部分以及热门电影部分。
然后使用CSS的标题框模块等增强H5代码形成的框架感(我主要给最下面的底部和导航弄了CSS格式)。

主页面H5和CSS的代码如下:

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
<!DOCTYPE html >
<html >

<!--head部分-->
<head>
<meta charset=UTF-8">

<!--设置各种格式-->
<style>
ul {
list-style-type: none;
margin: 0;
padding: 0;
overflow: hidden;
background-color: white;<!--导引行字背景-->
}

li {
float: left;
}

li a {
display: gray;
color: blue;<!--字体颜色-->
text-align: center;
padding: 14px 16px;
text-decoration: none;
}

li a:hover {
background-color: red;<!--选中后背景-->
}

<!--底部的格式-->
#bottom{
margin:30px auto 0px auto;
width:1200px;
height:40px;
line-height:40px;
border-top:1px solid #CCCCCC;
}

#bottom .copyright{
float:left;
color:#999999;
font-family:"微软雅黑";
font-size:14px;}


</style>

</head>


<!--body部分-->
<body>

<!--头部显示 电影资源网-->
<ul>
<br></br>
<li><a href="javascript:;">电影购票</a></li>
<li><a href="detail/dianying.html">电影</a></li>
<li><a href="javascript:;">电视剧</a></li>
<li><a href="javascript:;">少儿</a></li>
<li><a href="javascript:;">其他</a></li>
<li><a href="javascript:;">圈子</a></li>
<li><a href="javascript:;">最热电影</a></li>
</ul>

<!--正在热映部分-->
<div id="main">
<div id="left">
<div class="is-on">
<div class="hd">
<h2>正在热映</h2>
<div class="right">
<a class="leftBtn" href="javascript:;"></a>
<a class="rightBtn" href="javascript:;"></a>
</div>
</div>
<div class="bd">
<div class="container">
<ul>

<li>
<a href="detail/mnyys.html"><img src="images/1.jpg" alt="" />
</a>
<p><a href="detail/mnyys.html">美女与野兽</a>

<span class="score">7.2分</span></p>


</li>

<li>
<a href="detail/thwj.html"><img src="images/2.jpg" alt="" />
</a>
<p><a href="detail/thwj.html">头号玩家</a>

<span class="score">8.7分</span></p>


</li>

<li>
<a href="detail/fwhyj.html"><img src="images/3.jpg" alt="" />
</a>
<p><a href="detail/fwhyj.html">飞屋环游记</a>

<span class="score">8.9分</span></p>


</li>

<li>
<a href="detail/mtyj.html">
<img src="images/4.jpg" alt="" />
</a>
<p><a href="detail/mtyj.html">摩天营救</a>

<span class="score">8.6分</span></p>

</li>

<li>
<a href="detail/yhhwd.html"><img src="images/5.jpg" alt="" />
</a>
<p><a href="detail/yhhwd.html">银河护卫队</a>

<span class="score">8.0分</span></p>

</li>
</ul>
</div>
</div>
</div>

<!--中间广告部分-->
<div class="banner">
<a href="javascript:;"><img src="images/banner2.jpg" /></a>
</div>

<!--热门电影部分-->
<div class="hot-film">
<div class="hot-film-top">
<h2>热门电影</h2>
<ul>
<li><a>热门</a></li>
<li><a>最新</a></li>
<li><a>更多</a></li>
<br></br>
</ul>
</div>
<div class="hot-film-main">
<div class="hot-film-list">
<ul>
<li>
<a href="detail/thwj.html">
<img src="images/2.jpg" alt="" />
</a>
<p><a href="detail/thwj.html">头号玩家</a>
<span class="score">8.7分</span></p>
</li>

<li>
<a href="detail/fwhyj.html">
<img src="images/3.jpg" alt="" />
</a>
<p><a href="detail/fwhyj.html">飞屋环游记</a>
<span class="score">8.9分</span></p>
</li>

<li>
<a href="detail/yhhwd.html">
<img src="images/5.jpg" alt="" />
</a>
<p><a href="detail/yhhwd.html">银河护卫队</a>
<span class="score">8.0分</span></p>
</li>

<li>
<a href="detail/crzdy2.html">
<img src="images/1.jpg" alt="" />
</a>
<p><a href="detail/mnyys.html">美女与野兽</a>
<span class="score">8.7分</span></p>
</li>

<li>
<a href="detail/jtmdt.html">
<img src="images/4.jpg" alt="" />
</a>
<p><a href="detail/mtyj.html">摩天营救</a>
<span class="score">7.5分</span></p>
</li>

</ul>
</div>


</div>
</div>
</div>


<!--最下面的部分-->

<div id="bottom">
<span class="copyright">电影资源网 </span>
</div>

</body>

</html>

主页面截图:


二级页面显示其中一个电影的具体情况:

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
101
<!DOCTYPE html >
<html >
<head>
<meta charset=utf-8" />
<title>飞屋环游记的介绍</title>
<style>
ul {
list-style-type: none;
margin: 0;
padding: 0;
overflow: hidden;
background-color: white;<!--导引行字背景-->
}

li {
float: left;
}

li a {
display: gray;
color: blue;<!--字体颜色-->
text-align: center;
padding: 14px 16px;
text-decoration: none;
}

li a:hover {
background-color: red;<!--选中后背景-->
}

<!--底部的格式-->
#bottom{
margin:30px auto 0px auto;
width:1200px;
height:40px;
line-height:40px;
border-top:1px solid #CCCCCC;
}

#bottom .copyright{
float:left;
color:#999999;
font-family:"微软雅黑";
font-size:14px;}

</style>

</head>

<body>
<ul>
<br></br>
<li><a href="javascript:;">电影购票</a></li>
<li><a href="javascript:;">电影</a></li>
<li><a href="javascript:;">电视剧</a></li>
<li><a href="javascript:;">少儿</a></li>
<li><a href="javascript:;">其他</a></li>
<li><a href="javascript:;">圈子</a></li>
<li><a href="javascript:;">最热电影</a></li>
</ul>


<div id="left">
<h1>
<span>飞屋环游记</span>
<span>(2010)</span>
</h1>
<div class="subject">
<div class="mainpic">
<img src="../images/3.jpg" />
</div>
<div >
<span>导演</span>: 彼特·道格特 / 鲍勃·彼德森<br/>
<span>编剧</span>: 鲍勃·彼德森 / 彼特·道格特 / 汤姆·麦卡锡<br/>
<span><span>主演</span>: 爱德华·阿斯纳 / 克里斯托弗·普卢默 / 乔丹·长井 / 鲍勃·彼德森 / 戴尔里·林多 / 杰罗姆·兰福特</span><br/>
<span>类型:</span> 剧情 / 喜剧 / 动画 / 冒险<br/>
<span>制片国家/地区:</span> 美国<br/>
<span>语言:</span> 英语<br/>
<span>片长:</span> 96分钟<br/>
</div>
<div>
<span >飞屋环游记的剧情简介:</span>
<div>
  小男孩卡尔(Carl Fredricksen)怀揣着对于冒险的热爱偶遇假小子艾丽(Ellie),而艾丽把整个屋子当成一艘大飞船游戏居然使他对这个女孩子有些着迷,相同的爱好最终使两个人成为了一生的爱侣。
<br />
  他们有一个梦想,那就是有朝一日要去南美洲的“仙境瀑布”探险,但直到艾丽去世,这个梦想也未能实现。终于有一天,曾经专卖气球的老人卡尔居然用五颜六色的气球拽着他的房子飞上了天空,他决定要去实现他们未曾实现的梦想。令卡尔始料不及的是,门廊居然搭上了一个自称是“荒野开拓者”的小男孩小罗(Russell),小罗的喋喋不休让卡尔对这个小胖墩格外讨厌。
<br />
  一老一少在飞行中经过了千难万险终于看到了传说中的“仙境瀑布”,在相处过程中卡尔发现小罗其实是个惹人怜爱的孩子。在步行穿越一座森林时,他们遇到了不会飞的大鸟凯文(Kevin)和一只会说话的狗狗逗逗(Dug),让老人惊讶的是他们还遇到了他少年的崇拜偶像——探险家查尔斯·蒙兹(Charles Muntz),而且他发现蒙兹居然是一个为达目的不择手段的坏人。这时,老人离自己的梦想之地只有一步之遥……
<br />
  本片荣获第82届奥斯卡最佳动画长片、最佳配乐2项大奖。
</div>
</div>
</div>
</div>


<div id="bottom">
<span class="copyright">电影资源网</span>

</body>
</html>

二级页面截图:


导航行的“电影”部分:

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
<!DOCTYPE html >
<html >
<head>
<meta charset=utf-8" />
<title>飞屋环游记的介绍</title>
<style>
ul {
list-style-type: none;
margin: 0;
padding: 0;
overflow: hidden;
background-color: white;<!--导引行字背景-->
}

li {
float: left;
}

li a {
display: gray;
color: blue;<!--字体颜色-->
text-align: center;
padding: 14px 16px;
text-decoration: none;
}

li a:hover {
background-color: red;<!--选中后背景-->
}

<!--底部的格式-->
#bottom{
margin:30px auto 0px auto;
width:1200px;
height:40px;
line-height:40px;
border-top:1px solid #CCCCCC;
}

#bottom .copyright{
float:left;
color:#999999;
font-family:"微软雅黑";
font-size:14px;}

</style>

</head>

<body>
<ul>
<br></br>
<li><a href="javascript:;">电影购票</a></li>
<li><a href="javascript:;">电影</a></li>
<li><a href="javascript:;">电视剧</a></li>
<li><a href="javascript:;">少儿</a></li>
<li><a href="javascript:;">其他</a></li>
<li><a href="javascript:;">圈子</a></li>
<li><a href="javascript:;">最热电影</a></li>
</ul>


<!--电影部分-->

<div id="left">
<div class="is-on">
<div class="hd">
<h2>电影大全</h2>
<div class="right">
<a class="leftBtn" href="javascript:;"></a>
<a class="rightBtn" href="javascript:;"></a>
</div>
</div>
<div class="bd">
<div class="container">
<ul>

<li>
<a href="detail/mnyys.html"><img src="images/1.jpg" alt="" />
</a>
<p><a href="detail/mnyys.html">美女与野兽</a>

<span class="score">7.2分</span></p>


</li>

<li>
<a href="detail/thwj.html"><img src="images/2.jpg" alt="" />
</a>
<p><a href="detail/thwj.html">头号玩家</a>

<span class="score">8.7分</span></p>


</li>

<li>
<a href="detail/fwhyj.html"><img src="images/3.jpg" alt="" />
</a>
<p><a href="detail/fwhyj.html">飞屋环游记</a>

<span class="score">8.9分</span></p>


</li>

<li>
<a href="detail/mtyj.html">
<img src="images/4.jpg" alt="" />
</a>
<p><a href="detail/mtyj.html">摩天营救</a>

<span class="score">8.6分</span></p>

</li>

<li>
<a href="detail/yhhwd.html"><img src="images/5.jpg" alt="" />
</a>
<p><a href="detail/yhhwd.html">银河护卫队</a>

<span class="score">8.0分</span></p>

</li>
</ul>
</div>
</div>

<div id="bottom">
<span class="copyright">电影资源网</span>

</body>
</html>

电影部分截图:


回溯算法

回溯法:
回溯在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就 “回溯” 返回,尝试别的路径。按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,
回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

例子:
八皇后问题
在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?
思路:
通过分析题目可以得到,就是每一行就必须有一个皇后。
①第一种想法是假设8*8的棋盘是一个矩阵形式,那么假设皇后i和皇后j的位置为(i,Xi)和(j,Xj),只要保证两个坐标的点斜率不是1和-1就行。
②采用回溯法:
假设现在有四个皇后需要放置:
(1)假设第一个皇后放在第一行第一列的位置,那么第二行的皇后就只能放在第二行第三列/第四列位置。
(2)现在让第二个皇后放在第二行第三列的位置,那么第三行的皇后就没有位置可以放了,没有满足题意的位置了。

因此我们需要返回考虑第二个皇后的安置问题:
(2)现在让第二个皇后放在第二行第四列的位置,那么第三行的皇后就可以放在第三行第二列位置。
(3)第三行皇后放置后,第四行皇后又没位置了。

因此需要不断地去尝试,选择路径去放置

具体实现:

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
public class BaHuangHou{	
public static void main(String[] args) {
int a[]=new int[4];
int number=4,count=0;
operate(0);
System.out.println(count);
}

public static boolean panduan(int n) {
for(int i=0;i<n;i++)
if((a[i]==a[n])||(Math.abs(n-i)==Math.abs(a[i]-a[n]))) //判断下一个皇后是否和上一个皇后在同一行或者是对角线
return false;

return true;
}

public static void operate(int n) { //放置一个皇后
if(n==number)
{
count++;
}
else if(n<number)
{
for(int i=0;i<number;i++)
{
a[n]=i;
if(panduan(n)) //判断是否可以放置
operate(n+1);
}
}
}


}

代码结果如下:

贪心算法

贪心算法:
  又称贪婪算法。重复地使用一个贪婪规则(确定一个符合的准则)去挑选解的一部分,从局部最优解逐步达到全局最优
  贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
例如:
背包问题:
有三个参赛者:A,B,C;
每个比赛者一个包(包的载重量为20kg)
给定N个物品,每个物品有一定的质量和价值
规则:
  1.物品可以切一部分放入
  2.包装的物品的总质量不超过包的载重量
  3.包里装的物品的价值之和最高者获胜
假设:物品n=3,包的载重量c=20
物品1:V=25,M=18
物品2:V=24,M=15
物品3:V=15,M=10

思路:
A考虑优先放入价值高的物品:
  max=25+24(2/15)=28.2;
B考虑优先放入重量低的物品:
  max=15+24
(10/15)=31;
C考虑优先放入性价比高的物品:
  max=24+15(5/10)=31.5;
*
所以说我们对于此题选择C考虑的方法为解决题目的贪心规则。**

一、两地调度:
公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0],飞往 B 市的费用为 costs[i][1]。
返回将每个人都飞到某座城市的最低费用,要求每个城市都有 N 人抵达。
示例:
  输入:[[10,20],[30,200],[400,50],[30,20]]
输出:110
解释:
  第一个人去 A 市,费用为 10。
  第二个人去 A 市,费用为 30。
  第三个人去 B 市,费用为 50。
  第四个人去 B 市,费用为 20。

思路:
  我们可以考虑先让公司指派2N个人全都去A城,然后计算从A和B出发的金钱差额放入数组里面,排序之后将数组前一半的人替换到B去,这样可以保证有N个人去A,其他人去B。然后也可以保证最低费用。

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
import java.util.Scanner;
import java.util.Arrays;
public class DiYiGe{
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
int[][] a=new int[n][m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
a[i][j]=input.nextInt(); //双层循环读取分别去A和B的花费
}
}
System.out.println(min(a));
}

public static int min(int[][] a) {
int m=a.length; //原数组的长度
int b[] = new int[m]; //对应存放每个人去A和B的消耗差
int sum = 0;
for(int i=0;i<m;i++){
b[i] = a[i][1]-a[i][0]; //计算从A到B城的消耗差
sum +=a[i][0]; //加上所有人到A城的费用
}
Arrays.sort(b); //将差距
for(int i=0;i<m/2;i++)
sum+=b[i]; //减去应到B城的人员的额外消耗
return sum;
}
}

代码结果如下:


二、柠檬水找零:
  在柠檬水摊上,每一杯柠檬水的售价为 5 美元。
  顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。
每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。
  注意,一开始你手头没有任何零钱。

示例:
  输入:[5,5,5,10,20]
  输出:true
解释:
  前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。
  第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
  第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
  由于所有客户都得到了正确的找零,所以我们输出 true。

思路:先收前面的人钱,然后保证手里有零钱,如果需要找20的话,先考虑找10元大的钱,保证5元够用。

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
import java.util.Scanner;
public class NingMeng {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<n;i++)
{
a[i]=input.nextInt();
}
System.out.println(Change(a));
}

public static boolean Change(int[] a) {
int money[] = new int[3]; // 利用下标存放5/10/20元的数量
money[0]++; //存放5元的个数
for (int i=1;i<a.length;i++) {
switch (a[i]) { //依次找零
case 5:
money[0]++; //如果是5元直接+1
break;
case 10:
money[1]++; //十元的话+1
money[0]--; //找零5元
if (money[0] < 0) {
return false; //不能成功找零
}
break;
case 20:
money[2]++; //如果是20元直接+1
if (money[1]>0) { //如果有10元找一张 10元-1 5元-1
money[1]--;
money[0]--;
}
else {
money[0] -= 3; //如果找5元 5元-3
}

if (money[0] < 0) {
return false;
}
break;
}
}
return true;
}
}

代码结果如下:


三、跳台阶
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
例如:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
说明:假设你总是可以到达数组的最后一个位置。
思路:
假如a={2,3,1,1,4,2,1}那么最符合题意的就是2跳到3的位置然后跳到4然后跳到终点。
现在当处于第一个位置2的时候考虑是跳到3还是1,显然跳到3更好一点,那么跳到3之后考虑跳到1还是1还是4,因此选择4的位置,最后选择跳到终点。
->我们考虑下一个要跳跃的点就必须是保证上一次和这一次的跳跃点距离最远,这样可以保证输出少。

贪心算法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  public int jump(int[] a) {
int sum = 0;
int zy = 0; // 能跳到的最远距离
int max = 0; // 下一步可以跳到的最远距离
for(int i = 0; i < a.length - 1; i++)
{
max = Math.max(max, i + a[i]);
// 更新当前点
if(i == zy)
{
zy = max;
sum++;
}
}
return sum;
}

以爬楼梯为例

一、爬楼梯
题目:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
思路:
  此题目和铺地板等题目一样,都有两种方式解决。
  ①递归:递归思路为不断递归方法,求F(i)时候就要求F(i-1)和F(i-2);
  ②动态规划:规划方程F(i)=F(i-1)+f(i-2);(i从2开始)
动态规划具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt(); //定义数组的长度
int[] a=new int[n];
a[0]=1; //要爬一层台阶,有一种方法
a[1]=2; //要爬两层台阶,有两种方法
System.out.println(climbStairs(n,a)); //传递a数组和要爬的层数
}
public static int climbStairs(int n,int[] a) {
if(n==1)
return 1; //如果爬一层楼就是1个方法
for(int i=2;i<n;i++)
{
a[i]=a[i-1]+a[i-2]; //相当于斐波拉契数列思想

}
return a[n-1]; //返回的一定是数组长度-1的值
}
}

代码结果如下:


二、买卖股票的最佳时机
题目:
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
例如:
  输入:7,1,5,3,6,4
  输出: 5
  解释:在第二天的时候买入,在第五天卖出,最大利润=6-1=5。
注意利润不能是7-1=6,因为卖出价格需要大于买入价格。
思路:
①拿到题目第一种思路就是暴力求解法,利用两重循环两个数进行比较,然后根据条件限制选出两个数值之间差距最大的两个数,即为买卖股票的最佳时机。
具体实现:

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
import java.util.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(maxProfit(a));
}
public static int maxProfit(int[] a) {
int max=0;
for(int i=0;i<a.length;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(j>=i) //后面的那个价格要比前面的高(保证不亏钱)
{
max=Math.max(max,(a[j]-a[i])); // 选出两者之间差距最大的即为最大利润
}
}
}
return max;
}
}

代码结果如下:

②第二种思路就是动态规划,这还是我参考别人的想法想到了。
当前的最大利润=max{前一个值的最大利润max,当前值-前面的最小值}。
max=Math.max(max,(a[i]-min)); (min初始值一定要为a[0],不然默认为0的话,最大利润永远为0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;
public class TouQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(rob(a));
}


public static int rob(int[] a) {
int max=0,min=a[0],i=0; //先让最小值为第一个值
for( i=0;i<a.length;i++)
{
min=Math.min(min,a[i]); //每次判断确定最小值
max=Math.max(max,(a[i]-min)); //判断当前的最大利润是前一个的利润还是当前减去前面的最小值哪个大
}
return max;
}
}

代码结果如下:


三、买卖股票的最佳时机II
题目:
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
思路:
①可以发现只要后边的值大于前面的值(上升状态):上升点(买入)到上升的最高点(卖出)就是获得的利润,然后计算总和所有的上升状态就可以得到最大利润。
具体实现:

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
import java.util.Scanner;
public class TouQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(rob(a));
}

public static int rob(int[] a) {
int i=0,sum=0;
for(i=1;i<a.length;i++)
{
if(a[i-1]<a[i]) //上升状态
{
sum+=a[i]-a[i-1]; //将所有上升状态的值都加起来
}
}
return sum;
}
}

代码结果如下:


四、打家劫舍
题目:
  你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
  给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例:
  输入:2,7,9,3,1
  输出:12
解释:先偷第一家的金额为2,然后偷第三家的金额为9,接着偷第五家的金额为1.
思路:
  此题为经典的动态规划问题,我一开始理解的就是要么奇数最大要么偶数最大就解决了,然后我就循环判断奇数总和与偶数总和的大小,但是发现还是有很大问题。
以三个为例:
  第一步:我们只偷第一家的,记作max=a[0];
  第二步:因为不能偷相邻的房间,我们要判断是第一家的还是第二家的金额大,记作max=Math.max(a[0],a[1]);
  第三步:考虑是第一家的金额+第三家的金额和第二家的金额那个大,记作max=Math.max(a[0]+a[2],a[1]);
  由此,我们可以用一个a数组存放输入的每家金额值,b数组去存放每一步取得的最大的金额:
  b[i]=Math.max((b[i-2]+a[i]),b[i-1]);

具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;
public class TouQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
for(int i=0;i<a.length;i++)
{
a[i]=input.nextInt();
}
System.out.println(rob(a));
}

public static int rob(int[] a) {
int[] b=new int[a.length];
b[0]=a[0]; //只能偷第一家
b[1]=Math.max(a[0],a[1]); //确定偷第二家的时候是哪一家比较有钱,确定从1还是2家开始
for(int i=2;i<a.length;i++)
{
b[i]=Math.max(b[i-2]+a[i],b[i-1]); //比较前一家的金额和之前一家加上现在一家的金额哪个大
}
return b[a.length-1]; //注意输出长度-1的值
}
}

代码结果如下:


动态规划

动态规划
  简单的说就是,大问题化解为小问题,然后小问题解决后组装成大问题,可以压缩解决大问题的时间。

动态规划和递归的区别:
  我自己学的时候,我对动态规划的感觉就是这明明就是递归嘛,但是当我解决了几道题之后发现还是有一定区别。
  两种想法都是将大问题分解为小问题,使用类似于分而治之的思想去解决问题。
  以斐波拉契数列为例,递归要算F(n)=F(n-1)+F(n-2);(n>2)就需要算n-1和n-2的解,依次解决的话就会重复计算中间的值,会导致计算量变大;而动态规划的话,会减少计算重复值,更优化。


举例:

一、斐波拉契数列
  题目:兔子繁殖问题:
  这是一个有趣的古典数学问题,著名意大利数学家Fibonacci曾提出一个问题:有一对小兔子,从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。按此规律,假设没有兔子死亡,第一个月有一对刚出生的小兔子,问第n个月有多少对兔子?
  这就是著名的斐波那契数列(Fibonacci sequence),该数列,又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……
  特点:这个数列从第3项开始,每一项都等于前两项之和。
  思路:
  ①递归:从第二项开始 F(n)=F(n-1)+F(n-2);
  ②动态规划:定义left,right以及sum三个变量,通过不断地更新和移位算出接下来的值,可以避免递归的重复计算。

  具体实现:
  ①递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
a[1]=a[0]=1;
System.out.println(FB(n));
}
public static int FB(int n) {
if(n<=1) //输入为0/1输出结果为0/1
return n;
else
return FB(n-1)+FB(n-2); //不断递归公式
}
}

  代码结果:
  !

  ②动态规划:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
public class FeiBoNaQie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
System.out.println(FB(n-1));
}
public static int FB(int n) {
if(n<=1)
return n;
int left=1,right=1;
int sum=0;
for(int i=2;i<=n;i++) //从第三个开始(0开始)为前两个之和
{
sum=left+right; //第三个为第一个数和第二个数之和
right=left; //第一个数指向第二个数位置
left=sum; //第三个数字指向第一个数位置
}
return sum;
}
}

  代码结果:
  !


二、跳台阶
  题目:
  一只青蛙一次可以跳上一级台阶,也可以跳上两级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
  思路:
  首先考虑需要跳两级台阶,那么第一种情况就是一次跳两级,第二种是一次跳一级。
  那么如果需要跳n级台阶,把跳法记作函数f(n):当n>2时,一是第一次跳一级,那么剩下的n-1级就需要f(n-1)。
二是第一次跳两级,那么剩下的n-2级就需要f(n-2)。所以整理可知,这实际上也是一个斐波拉数列!

  具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
public class TiaoTaiJie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
System.out.println(TaiJie(n-1));
}
public static int TaiJie(int n) {
if(n<=1)
return n;
int left=1,right=1;
int sum=0;
for(int i=2;i<=n;i++) //从第三个开始(0开始)为前两个之和
{
sum=left+right; //第三个为第一个数和第二个数之和
right=left; //第一个数指向第二个数位置
left=sum; //第三个数字指向第一个数位置
}
return sum;
}
}

  代码结果:
  !


三、变态跳台阶
  题目:
  在上题目的基础上,这次一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶….也可以跳上n级台阶。求青蛙上一个n级台阶总共有多少跳法。
  思路:
  我们可以依旧从最简单的二级开始考虑:
  如果我们需要跳上2级台阶,那么第一种方法是跳二级台阶,第二种是一次一级。
  如果是n级台阶,那么可以从n-1级跳一级上去,也可以从n-2级跳两级上去:
  因此 f(n)=f(n-1)+f(n-2)+…+f(1); (1)
  如果是n-1级台阶,那么可以从n-2级跳一级上去,也可以从n-3级跳两级上去:
  因此 f(n-1)=f(n-2)+f(n-3)+…+f(1); (2)
  则(1)和(2)式联立,我们可以得出f(n)=2*f(n-1);

  具体实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Scanner;
public class BianTaiTiaoTaiJie {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n];
System.out.println(BianTai(n));
}
public static int BianTai(int n) {
if(n==1)
return 1; //需要跳一级只有一种方法
if(n==2)
return 2; //需要跳二级有两种方法
else
return 2*BianTai(n-1);/return (int)Math.pow(2,n-1); //需要跳n级有n-1种方法(不断求解)
}
}

  代码结果:
  !


还有一些可以被动态规划解决的问题

  • 资源分配问题(求最优解/利益最大)
  • 铺地板(和跳台阶一样)
  • 矩阵覆盖(和跳台阶一样)
  • 借还滑板鞋(考虑最优解)
  • 最优二叉树搜索树

总结:

  • 碰到上面的例题时,需要考虑最优解使用递归/动态规划即可。但是递归不太推荐,性能没有动态规划好。
  • 需要从最简单然后推导出规律和推导公式。
  • 尽可能避免无所谓的复杂计算,得到加快算法求解的时间。
,