蓝桥杯校赛

一、分核桃

  • 问题描述
    小张是软件项目经理,他带领3个开发组。工期紧,今天都在加班呢。为鼓舞士气,小张打算给每个组发一袋核桃(据传言能补脑)。他的要求是:
  1. 各组的核桃数量必须相同
  2. 各组内必须能平分核桃(当然是不能打碎的)
  3. 尽量提供满足1,2条件的最小数量(节约闹革命嘛)

输入格式
输入包含三个正整数a, b, c,表示每个组正在加班的人数,用空格分开(a,b,c<30)
输出格式
输出一个正整数,表示每袋核桃的数量。

样例输入1
2 4 5
样例输出1
20

样例输入2
3 1 1
样例输出2
3

  • 问题分析:
      很明显是两个两个人求最小公倍数的问题。
  • 1.暴力法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package xiaosai;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int a=input.nextInt();
int b=input.nextInt();
int c=input.nextInt();

for(int i=1;i<1000;i++)
{
if(i%a==0&&i%b==0&&i%c==0) //最小的值应该满足同时可以整除三个数字
{
System.out.println(i);
break;
}
}

}
}
  • 2.最小公倍数法:
  1. 求两个数的最大值
  2. 从最大值开始循环找到第一个能够同时整除的数字。
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
package xiaosai;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int a=input.nextInt();
int b=input.nextInt();
int c=input.nextInt();//输入三个数字
int flag=0;//定义变量存储合适的那个值

int d=zuida(a,b);//求前两数的最大值
for(int i=d;;i++)//从前两数的最大值开始
{
if(i%a==0&&i%b==0) //只要能够整除
{
flag=i;//flag存储当前符合的最小公倍数
break;
}
}

int e=zuida(flag,c); //求第二次的最大值
for(int i=e;;i++) //从最大值开始
{
if(i%flag==0&&i%c==0)//只要能够整除
{
flag=i;//存储最终满足的值
break;
}
}

System.out.println(flag); //输出答案

}

public static int zuida(int i,int j) { //求两个数的最大值
return i>j?i:j;
}

}
  • 代码结果:


二、字符删除

  • 问题描述
    编写一个程序,先输入一个字符串str(长度不超过20),再输入单独的一个字符ch,然后程序会把字符串str当中出现的所有的ch字符都删掉,从而得到一个新的字符串str2,然后把这个字符串打印出来。  

输入格式:输入有两行,第一行是一个字符串(内部没有空格),第二行是一个字符。  
输出格式:经过处理以后的字符串。

样例输入
123-45-678-
样例输出
12345678

  • 问题分析:
    将字符串转为数组(toCharArray()),然后依次循环和ch字符对比,不相等就输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package xiaosai;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String str=input.nextLine(); //输入一个字符串
char ch=input.next().charAt(0); //输入一个字符
char[] a=str.toCharArray(); //字符串转数组

for(int i=0;i<a.length;i++)
{
if(a[i]!=ch)
System.out.print(a[i]); //不相等就输出

}

}
}
  • 代码结果:


三、区间K大数查询

  • 问题描述
    给定一个序列,每次询问序列中第l个数到第r个数中第K大的数是哪个。

输入格式
  第一行包含一个数n,表示序列长度。
  第二行包含n个正整数,表示给定的序列。
  第三个包含一个正整数m,表示询问个数。

  接下来m行,每行三个数l,r,K,表示询问序列从左往右第l个数到第r个数中,从大往小第K大的数是哪个。序列元素从1开始标号。

输出格式
  总共输出m行,每行一个数,表示询问的答案。
样例输入
5
1 2 3 4 5
2
1 5 2
2 3 2
样例输出
4
2
数据规模与约定
  对于30%的数据,n,m<=100;
  对于100%的数据,n,m<=1000;

  • 问题分析:
      定义一个数组a先往里面放值,然后定义一个r-l+1长的数组b存放要截取的数组,然后定义一个ans数组存放每一次循环判断的最k大值(很关键),然后输入l,r,k之后按顺序存放进数组b,一定要记得sort一下(不一定存放的数组就是顺序的!!!),最后将最k大值放入ans数组!
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
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();//输入数组的长度
int[] a = new int[n];//定义一个n长度的数组a
for(int i=0;i<n;i++)
{
a[i] = in.nextInt(); //一位一位输入内容
}
int m = in.nextInt();//定义找几次
int[] ans = new int[m];//按照m定义长度数组ans
for(int i=0;i<m;i++)//找几次就循环几次
{
int l = in.nextInt();//输入要选的左边值
int r = in.nextInt();//输入要选的右边值
int k = in.nextInt();//输入要选的第k大值
int[] b = new int[r-l+1];//定义一个截取范围的数组b
for(int j=0;j<r-l+1;j++)//从0到最大值赋值
{
b[j]=a[j+l-1];//依次将对应的值放入b数组中
}
Arrays.sort(b);//一定要记得排序(输入的数字不一定按顺序排列)
ans[i]=b[r-l+1-k];//把那个最k大值放入ans数组值中
}

for(int i=0;i<m;i++)
{
System.out.println(ans[i]);//依次输出的就是找几次的对应的答案
}

}

}
  • 代码结果:


四、阶乘(第一个非0数)

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

样例输入
6
样例输出
2

由于只需要阶乘后的最后一个非0数,所以每次阶乘后,如果尾数是0的直接/10。

  • 问题分析:
  1. 先编写一个递归方法求每一个数对应的阶乘。
  2. 将结果暂存在数组内,然后设置变量m来遍历直至第一个非0数就跳出判断。

解法一(30%):

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
package xiaosai;
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[] a=new int[1000];
a[0]=jiecheng(n);
int m=1;
for(int i=0;;i++)
{
m=a[0]%10;
if(m!=0)
{
System.out.println(m);
break;
}
a[0]=a[0]/10;
}
}

public static int jiecheng(int n) {
if(n==0||n==1)
return 1;
else
return n*jiecheng(n-1);
}
}
  • 问题分析:
  1. 和解法一相似使用数组一个数字存放数组一个元素之中得到结果。
  2. 循环每次判断结果和考虑进位问题以此类推得到结果,最终还是循环判断非0数。

解法二(100%):

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
package xiaosai;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int a[]= new int[4000];
a[0]=1;
int r1=0;//考虑进位情况
for(int i=2;i<=n;i++) {
for(int j=0;j<4000;j++) {
r1=a[j]*i+r1;
a[j]=r1%10; //如果发生进位将个位赋给当前位置,十位或者和百位一起加到下一次数组乘法
r1=r1/10; //依次类推
}
}
int s=0;
for(int i=3999;i>=0;i--) {
if(a[i]!=0) {
System.out.print(a[i]); //从后往前倒排,然后判断首位不为空则输出
s=i; //同时记录下标
break;
}
}

}
}
  • 问题分析:
  1. 像解法一一样,如果用int型和递归方法会导致超时等问题,所以考虑使用BigDecimal类型存放结果。
  2. 考虑将结果用tosrtring方法转化为字符串,通过

charAt方法来循环判断是否为0找到最终结果。

解法三(100%):

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
package xiaosai;
import java.util.Scanner;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
BigDecimal sum = BigDecimal.ONE;//使用BigDecimal类型存放答案
for(int i = 1; i <= n; i++)
{
sum = sum.multiply(BigDecimal.valueOf(i));//使用乘法(不使用递归方法!)
}

String S = sum.toString(); //将结果转化为字符串
for(int i = S.length()-1; i >= 0; i--)
{
if(S.charAt(i) != '0')//遇到第一个非0的数字输出
{
System.out.println(S.charAt(i));
break;
}
}

}
}

代码结果如下:


五、最长子序列

  • 问题描述
    给定一个长为n的序列,求它的最长上升子序列的长度。
    输入格式
      输入第一行包含一个整数n。
      第二行包含n个整数,为给定的序列。
    输出格式
      输出一个非负整数,表示最长上升子序列的长度。
    样例输入
    5
    1 3 2 5 4
    样例输出
    3
    数据规模和约定
      0<n<=1000,每个数不超过10^6。

  • 问题分析:
    例如:数列(1, 7, 3, 5, 9, 4, 8)的有序上升子序列,像(1, 7), (3, 4, 8)和许多其他的子序列。在所有的子序列中,最长的上升子序列的长度是4,如(1, 3, 5, 8)

  • 动态规划

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
package xiaosai;
import java.math.*;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] arr = new int[10002];//arr数组表示输入的序列
int[] dp = new int[10002];//dp数组中存放上升序列的长度,dp[i]表示以arr[i]结尾的子序列的最大长度
for(int i = 1;i <= n;i++) {//输入序列
arr[i]= input.nextInt();
}

int result = -1;//记录dp中最大的值
for(int i = 1;i <= n;i++)
{//按顺序计算dp[i]的值
dp[i] = 1;//假设该子序列中只有arr[i],故长度为1,即其自身成为一个子序列
for(int j = 1;j < i;j++)
{//如果在i之前有比arr[i]小的数(arr[j]),并且把该数(arr[i])放到以arr[j]结尾的子序列末尾后,//其长度比当前以arr[i]结尾的子序列长度要长
if(arr[i] > arr[j] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;//把arr[i]放到以arr[j]结尾的子序列之后,原来的长度+1
}
}
result = Math.max(result, dp[i]);//找出在dp数组中最大的一个,即子序列长度最长的一个
}
System.out.println(result);
}
}

代码结果如下:

线程状态

一、线程状态
在API中java.lang.Thread.state介绍了六种线程状态!

参考视频:
https://www.bilibili.com/video/av62541169/?p=312

  1. new Thread/Thread子类();—>新建状态
  2. 执行start()方法
    • 抢到cpu—>运行状态(Runnable)run()方法结束/stop()过时就会到死亡状态(Terminated)
    • 没抢到cpu—>阻塞状态(Blockerd)
  3. 执行sleep(long)方法 / wait(long)方法—>睡眠/休眠状态(Timed_waiting)
    • 睡眠结束,cpu不空闲—>阻塞状态
    • 睡眠结束,cpu空闲—>运行状态
  4. 执行Object.wait(无参数)—>无限/永久等待状态
  5. 执行Object.notify()—>只有这个方法才能唤醒。

二、等待唤醒案例

  • 等待唤醒案例:线程之间的通信
      创建一个顾客线程(消费者):告知老板需要包子的种类和数量,调用wait方法,放弃cpu的执行,进入到WAITING状态(无限等待)
      创建一个老板线程(生产者):花了s秒生产包子,包子做好,调用notify()方法,唤醒顾客吃包子。
  • 注意点:
  1. 顾客和老板线程必须使用同步代码块包裹,而且保证只有一个在执行。(使用同步技术-synchronized(对象)形式)
  2. 同步使用的锁对象必须保证唯一。(只有一个obj对象)
  3. 只有锁对象才可以使用wait和notify方法。(代码中obj.wait()方法/obj.notify()方法)

Object类中的方法:

  1. void wait()
    在其他线程调用此对象的notify()方法/notifyAll()方法前,导致当前线程等待。
  2. void notify()
    唤醒在此对象监控器上等待的单个线程
    会继续执行wait()方法之后的代码
  • 具体实现:
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
package dengdaihuanxing;
public class Main {
public static void main(String[] args) {
//创建锁对象(唯一)
Object obj=new Object();
//创建一个顾客线程(消费者)---匿名内部类
new Thread(){
@Override
public void run() {
//保证只有一个执行---同步技术
synchronized(obj) {
System.out.println("告知老板要的包子的种类和数量:");
//调用wait方法---进入无限等待状态
try
{
obj.wait(); //锁对象才可以调用wait方法
}
catch (InterruptedException e)
{
e.printStackTrace();
}
//唤醒之后执行的代码
System.out.println("包子已经做好了,可以吃了!");
}
}
}.start();

//创建一个老板线程(生产者)
new Thread() {
@Override
public void run() {
//花五秒钟做包子
try
{
Thread.sleep(5000);
}
catch (InterruptedException e)
{
e.printStackTrace();
}
//保证只有一个执行---同步技术
synchronized(obj) {
System.out.println("老板5秒后做好包子,可以来吃包子了");
//调用notify()方法唤醒吃包子
obj.notify();//锁对象才可以调用notify方法
}
}
}.start();
}
}

代码结果如下:

1
2
3
4
告知老板要的包子的种类和数量:
(不用输入等待5秒后就会弹出下面的结果)
老板5秒后做好包子,可以来吃包子了
包子已经做好了,可以吃了!

三、Object类中wait带参方法和notify方法

  • 进入TimeWaiting(计时等待)有两种方式:
  1. 使用sleep(long m),在毫秒值结束之后,线程–>Runnable/Blocked状态。
  2. 使用wait(long m):wait方法如果在毫秒值结束之后,还没有被notify方法唤醒,就会自动醒来。
  • 唤醒的方法
  1. notify(): —>唤醒单个线程
  2. notify()All: —>唤醒所有线程

线程安全

一、安全问题
假如一个电影院有一部电影100张票:

  1. 只有一个窗口卖1-100的票(单线程):不会出现线程问题。
  2. 有三个窗口卖不同范围的票(多线程):不会出现线程问题,没有访问共享数据,不会产生问题。
  3. 有三个窗口卖的都是1-100的票(多线程):会出现线程访问共享数据–>线程安全问题
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
//子类!!!!!
public class RunnableImpl implements Runnable {
//定义一个多线程共享的票源:
private int ticket=100;
//设置线程任务:卖票
@Override
public void run() {
while(true)
{
//先判断票是否存在
if(ticket>0)
{
//提高安全问题出现的概率,让程序睡眠
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO 自动生成的 catch 块
e.printStackTrace();
}
//票存在,卖票 ticket--;
System.out.println(Thread.currentThread().getName()+"-->正在卖第"+ticket+"张票");
ticket--;
}
}
}
}

//测试类!!!!!!!!!!!!!!!!!
/*
模拟卖票案例
创建3个线程,同时开始,对共享的票进行出售
*/
public class ShiXian {
public static void main(String[] args) {
//创建Runnable接口的实现类对象
RunnableImpl run=new RunnableImpl();

//三个线程争夺CPU
Thread t0=new Thread(run);//抢夺到CPU的执行权-进入到run方法之后执行if语句就会睡眠,失去cpu的执行权
Thread t1=new Thread(run);
Thread t2=new Thread(run);

//调用start()方法开启多线程
t0.start();
t1.start();
t2.start();
}
}

代码结果如下:
Thread-1–>正在卖第100张票
Thread-2–>正在卖第100张票
Thread-0–>正在卖第100张票

Thread-1–>正在卖第3张票
Thread-0–>正在卖第3张票
Thread-2–>正在卖第1张票
Thread-1–>正在卖第0张票
Thread-0–>正在卖第1张票
(出现了同时卖出去票的问题!!!!!!)


二、线程同步(解决方案)

  1. 同步代码块
  2. 同步方法
  3. 锁机制(Lock接口)
  • 同步代码块(synchronized):
1
2
3
 synchronized(同步锁){
需要同步操作的代码
}

注意:

  1. 锁对象可以是任意的对象
  2. 保证多个线程使用的是同一个锁对象
  3. 锁对象的作用:
    把同步代码块锁住:只让一个线程在同步代码块中执行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class RunnableImpl implements Runnable {
//定义一个多线程共享的票源:
private int ticket=100;

//创建一个锁对象
Object obj=new Object();

//设置线程任务:卖票
@Override
public void run() {
while(true)
{

synchronized (obj) //synchronized(锁对象)
{

//还是原来的那些if语句和sleep语句
}

}
}
}

代码结果如下:
Thread-0–>正在卖第100张票
Thread-2–>正在卖第99张票
Thread-2–>正在卖第98张票
…(省略)
Thread-2–>正在卖第4张票
Thread-2–>正在卖第3张票
Thread-2–>正在卖第2张票
Thread-2–>正在卖第1张票


  • 同步方法
  1. 访问了共享数据的代码–>方法
  2. 方法上+synchronized修饰符

格式:定义方法的格式

1
修饰符 synchronized 返回值类型 方法名(参数列表){}
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
package duoxianchegn;

public class RunnableImpl implements Runnable {
//定义一个多线程共享的票源:
private int ticket=100;

//设置线程任务:卖票
@Override
public void run() {
while(true)
{
payTicket(); //调用这个方法!

}
}

//提出来一个payTicket()方法用于把共享的代码锁起来
public synchronized void payTicket() {
//先判断票是否存在
if(ticket>0)
{
//提高安全问题出现的概率,让程序睡眠
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO 自动生成的 catch 块
e.printStackTrace();
}
//票存在,卖票 ticket--;
System.out.println(Thread.currentThread().getName()+"-->正在卖第"+ticket+"张票");
ticket--;
}

}
}

代码结果如下:
Thread-0–>正在卖第100张票
Thread-2–>正在卖第99张票
Thread-2–>正在卖第98张票
…(省略)
Thread-2–>正在卖第4张票
Thread-2–>正在卖第3张票
Thread-2–>正在卖第2张票
Thread-2–>正在卖第1张票


  • 锁机制(Lock锁)
    java.util.concurrent.locks.lock接口

  • lock接口(比synchronized更好)
     1. 使用获取锁void lock()/释放锁void unlock()方法。
     2. 实现类ReentrantLock implements Lock接口

  • 使用步骤:

  1. 在成员位置–>ReentrantLock对象
  2. 在可能会出现安全问题的代码调用Lock方法获取锁
  3. 在可能会出现安全问题的代码调用Lock方法释放锁
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.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class RunnableImpl implements Runnable {
//定义一个多线程共享的票源:
private int ticket=100;
//定义一个对象
Lock l=new ReentrantLock();

//设置线程任务:卖票
@Override
public void run() {
while(true)
{
l.lock();//加一个锁
//先判断票是否存在
if(ticket>0)
{
//提高安全问题出现的概率,让程序睡眠
try {
Thread.sleep(10);
} catch (InterruptedException e) {
// TODO 自动生成的 catch 块
e.printStackTrace();
}
//票存在,卖票 ticket--;
System.out.println(Thread.currentThread().getName()+"-->正在卖第"+ticket+"张票");
ticket--;
}
l.unlock();//释放一个锁
}
}
}

JAVA-多线程

第10章_多线程


本章专题与脉络

第3阶段:Java高级应用-第10章


我们之前学习的程序在没有跳转语句的情况下,都是由上至下沿着一条路径依次执行。现在想要设计一个程序,可以同时有多条执行路径同时执行。比如,一边游戏,一边qq聊天,一边听歌,怎么设计?

c3dcb61e3b

要解决上述问题,需要使用多进程 */ *多线程来解决。

1. 相关概念

1.1 程序、进程与线程

  • 程序(program):为完成特定任务,用某种语言编写的一组指令的集合。即指一段静态的代码,静态对象。

  • 进程(process):程序的一次执行过程,/ 正在内存中运行的应用程序。如:运行中的QQ,运行中的网易音乐播放器。

    • 每个进程都有一个独立的内存空间,系统运行一个程序即是一个进程从创建、运行到消亡的过程。(生命周期)
    • 程序是静态的,进程是动态的
    • 进程作为操作系统调度分配资源的最小单位(/系统运行程序的基本单位),系统在运行时会为每个进程分配不同的内存区域。
    • 现代的操作系统,大都是支持多进程的,支持同时运行多个程序。比如:现在我们上课一边使用编辑器,一边使用录屏软件,同时还开着画图板,dos窗口等软件。
  • 线程(thread):进程可进一步细化为线程,是程序内部的一条执行路径。一个进程中至少有一个线程。

    • 一个进程同一时间若并行执行多个线程,就是支持多线程的。

      image-20220331233204504
    • 线程作为CPU调度和执行的最小单位

    • 一个进程中的多个线程共享相同的内存单元,它们从同一个堆中分配对象,可以访问相同的变量和对象。这就使得线程间通信更简便、高效。但多个线程操作共享的系统资源可能就会带来安全的隐患

    • 下图中,红框的蓝色区域为线程独享,黄色区域为线程共享。

    image-20220514175737426

    注意:

    不同的进程之间是不共享内存的。

    进程之间的数据交换和通信的成本很高。

1.2 查看进程和线程

我们可以在电脑底部任务栏,右键—–>打开任务管理器,可以查看当前任务的进程:

1、每个应用程序的运行都是一个进程

2、一个应用程序的多次运行,就是多个进程

1563267431480

3、一个进程中包含多个线程

1563270525077

1.3 线程调度

  • 分时调度

    所有线程轮流使用 CPU 的使用权,并且平均分配每个线程占用 CPU 的时间。

  • 抢占式调度

    优先级高的线程较大概率优先使用 CPU。如果线程的优先级相同,那么会随机选择一个(线程随机性),Java使用抢占式调度

1.4 多线程程序的优点

背景:以单核CPU为例,只使用单个线程先后完成多个任务(调用多个方法),肯定比用多个线程来完成用的时间更短,为何仍需多线程呢?

多线程程序的优点:

  1. 提高应用程序的响应。对图形化界面更有意义,可增强用户体验。[可以一边聊天,一边学习]

  2. 提高计算机系统CPU的利用率

  3. 改善程序结构。将既长又复杂的进程分为多个线程,独立运行,利于理解和修改

1.5 补充概念

1.5.1 单核CPU和多核CPU

单核CPU,在一个时间单元内,只能执行一个线程的任务。例如,可以把CPU看成是医院的医生诊室,在一定时间内只能给一个病人诊断治疗。所以单核CPU就是,代码经过前面一系列的前导操作(类似于医院挂号,比如有10个窗口挂号),然后到cpu处执行时发现,就只有一个CPU(对应一个医生),大家排队执行。

这时候想要提升系统性能,只有两个办法,要么提升CPU性能(让医生看病快点),要么多加几个CPU(多整几个医生),即为多核的CPU。

问题:多核的效率是单核的倍数吗?譬如4核A53的cpu,性能是单核A53的4倍吗?理论上是,但是实际不可能,至少有两方面的损耗。

  • 一个是多个核心的其他共用资源限制。譬如,4核CPU对应的内存、cache、寄存器并没有同步扩充4倍。这就好像医院一样,1个医生换4个医生,但是做B超检查的还是一台机器,性能瓶颈就从医生转到B超检查了。
  • 另一个是多核CPU之间的协调管理损耗。譬如多个核心同时运行两个相关的任务,需要考虑任务同步,这也需要消耗额外性能。好比公司工作,一个人的时候至少不用开会浪费时间,自己跟自己商量就行了。两个人就要开会同步工作,协调分配,所以工作效率绝对不可能达到2倍。

1.5.2 并行与并发

  • 并行(parallel):指两个或多个事件在同一时刻发生(同时发生)。指在同一时刻,多条指令多个CPU同时执行。比如:多个人同时做不同的事。

    image-20231017195504293

    image-20220513181758585
  • 并发(concurrency):指两个或多个事件在同一个时间段内发生。即在一段时间内,多条指令单个CPU快速轮换、交替执行,使得在宏观上具有多个进程同时执行的效果。

    image-20220513181815978

在操作系统中,启动了多个程序,并发指的是在一段时间内宏观上有多个程序同时运行,这在单核 CPU 系统中,每一时刻只能有一个程序执行,即微观上这些程序是分时的交替运行,只不过是给人的感觉是同时运行,那是因为分时交替运行的时间是非常短的。

而在多核 CPU 系统中,则这些可以并发执行的程序便可以分配到多个CPU上,实现多任务并行执行,即利用每个处理器来处理一个可以并发执行的程序,这样多个程序便可以同时执行。目前电脑市场上说的多核 CPU,便是多核处理器,核越多,并行处理的程序越多,能大大的提高电脑运行的效率。

2.创建和启动线程

2.1 概述

  • Java语言的JVM允许程序运行多个线程,使用java.lang.Thread类代表线程,所有的线程对象都必须是Thread类或其子类的实例。

  • Thread类的特性

    • 每个线程都是通过某个特定Thread对象的run()方法来完成操作的,因此把run()方法体称为线程执行体
    • 通过该Thread对象的start()方法来启动这个线程,而非直接调用run()
    • 要想实现多线程,必须在主线程中创建新的线程对象。

2.2 方式1:继承Thread类

Java通过继承Thread类来创建启动多线程的步骤如下:

  1. 定义Thread类的子类,并重写该类的run()方法,该run()方法的方法体就代表了线程需要完成的任务
  2. 创建Thread子类的实例,即创建了线程对象
  3. 调用线程对象的start()方法来启动该线程

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//自定义线程类
public class MyThread extends Thread {
//定义指定线程名称的构造方法
public MyThread(String name) {
//调用父类的String参数的构造方法,指定线程的名称
super(name);
}
/**
* 重写run方法,完成该线程执行的逻辑
*/
@Override
public void run() {
for (int i = 0; i < 10; i++) {
System.out.println(getName()+":正在执行!"+i);
}
}
}

测试类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class TestMyThread {
public static void main(String[] args) {
//创建自定义线程对象1
MyThread mt1 = new MyThread("子线程1");
//开启子线程1
mt1.start();

//创建自定义线程对象2
MyThread mt2 = new MyThread("子线程2");
//开启子线程2
mt2.start();

//在主方法中执行for循环
for (int i = 0; i < 10; i++) {
System.out.println("main线程!"+i);
}
}
}
image-20220401221215860

注意:

  1. 如果自己手动调用run()方法,那么就只是普通方法,没有启动多线程模式。

  2. run()方法由JVM调用,什么时候调用,执行的过程控制都有操作系统的CPU调度决定。

  3. 想要启动多线程,必须调用start方法。

  4. 一个线程对象只能调用一次start()方法启动,如果重复调用了,则将抛出以上的异常“IllegalThreadStateException”。

2.3 方式2:实现Runnable接口

Java有单继承的限制,当我们无法继承Thread类时,那么该如何做呢?在核心类库中提供了Runnable接口,我们可以实现Runnable接口,重写run()方法,然后再通过Thread类的对象代理启动和执行我们的线程体run()方法

步骤如下:

  1. 定义Runnable接口的实现类,并重写该接口的run()方法,该run()方法的方法体同样是该线程的线程执行体。

  2. 创建Runnable实现类的实例,并以此实例作为Thread的target参数来创建Thread对象,该Thread对象才是真正
    的线程对象。

  3. 调用线程对象的start()方法,启动线程。调用Runnable接口实现类的run方法。

代码如下:

1
2
3
4
5
6
7
8
public class MyRunnable implements Runnable {
@Override
public void run() {
for (int i = 0; i < 20; i++) {
System.out.println(Thread.currentThread().getName() + " " + i);
}
}
}

测试类:

1
2
3
4
5
6
7
8
9
10
11
12
public class TestMyRunnable {
public static void main(String[] args) {
//创建自定义类对象 线程任务对象
MyRunnable mr = new MyRunnable();
//创建线程对象
Thread t = new Thread(mr, "长江");
t.start();
for (int i = 0; i < 20; i++) {
System.out.println("黄河 " + i);
}
}
}

通过实现Runnable接口,使得该类有了多线程类的特征。所有的分线程要执行的代码都在run方法里面。

在启动的多线程的时候,需要先通过Thread类的构造方法Thread(Runnable target) 构造出对象,然后调用Thread对象的start()方法来运行多线程代码。

实际上,所有的多线程代码都是通过运行Thread的start()方法来运行的。因此,不管是继承Thread类还是实现
Runnable接口来实现多线程,最终还是通过Thread的对象的API来控制线程的,熟悉Thread类的API是进行多线程编程的基础。

说明:Runnable对象仅仅作为Thread对象的target,Runnable实现类里包含的run()方法仅作为线程执行体。
而实际的线程对象依然是Thread实例,只是该Thread线程负责执行其target的run()方法。

image-20220401222212377

2.4 变形写法

使用匿名内部类对象来实现线程的创建和启动

1
2
3
4
5
6
7
8
9
//第一种方式
new Thread("新的线程!"){
@Override
public void run() {
for (int i = 0; i < 10; i++) {
System.out.println(getName()+":正在执行!"+i);
}
}
}.start();
1
2
3
4
5
6
7
8
9
//第二种方式
new Thread(new Runnable(){
@Override
public void run() {
for (int i = 0; i < 10; i++) {
System.out.println(Thread.currentThread().getName()+":" + i);
}
}
}).start();

2.5 对比两种方式

联系

Thread类实际上也是实现了Runnable接口的类。即:

1
public class Thread extends Object implements Runnable{}   //代理模式

区别

  • 继承Thread:线程代码存放Thread子类run方法中。

  • 实现Runnable:线程代码存在接口的子类的run方法。

实现Runnable接口比继承Thread类所具有的优势

  • 避免了单继承的局限性
  • 多个线程可以共享同一个接口实现类的对象,非常适合多个相同线程来处理同一份资源。
  • 增加程序的健壮性,实现解耦操作,代码可以被多个线程共享,代码和线程独立。

2.6 练习

创建两个分线程,让其中一个线程输出1-100之间的偶数,另一个线程输出1-100之间的奇数。

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
//实现输出偶数
class PrintNumber2 implements Runnable{ //1.创建一个子类实现Runnable接口
//2.实现接口中的run() --->将此线程要执行的操作声明在此方法体中
@Override
public void run(){
for (int i=0;i<=100;i++) {
if(i%2==0){
System.out.println(Thread.currentThread().getName()+":"+i);
}
}
}
}
//实现输出奇数
class PrintNumber3 implements Runnable{ //1.创建一个子类实现Runnable接口
//2.实现接口中的run() --->将此线程要执行的操作声明在此方法体中
@Override
public void run(){
for (int i=0;i<=100;i++) {
if(i%2!=0){
System.out.println(Thread.currentThread().getName()+":"+i);
}
}
}
}
//
public class EvenNumberTest2 {
public static void main(String[] args) {
//3.创建当前实现类的对象
PrintNumber2 printNumber2=new PrintNumber2();
//4.将此对象作为参数传递给Thread的构造器中,创建Thread类的实例
Thread thread=new Thread(printNumber2);
//5.Thread类的实例调用start()
thread.start();

//3.创建当前实现类的对象
PrintNumber3 printNumber3=new PrintNumber3();
//再创建一个线程
//4.将此对象作为参数传递给Thread的构造器中,创建Thread类的实例
Thread thread2=new Thread(printNumber3);
//5.Thread类的实例调用start()
thread2.start();
}
}

image-20231018154959304

3. Thread类的常用结构

3.1 构造器

  • public Thread() :分配一个新的线程对象。
  • public Thread(String name) :分配一个指定名字的新的线程对象。
  • public Thread(Runnable target) :指定创建线程的目标对象,它实现了Runnable接口中的run方法
  • public Thread(Runnable target,String name) :分配一个带有指定目标新的线程对象并指定名字。

3.2 常用方法系列1

  • public void run() :此线程要执行的任务在此处定义代码。
  • public void start() :导致此线程开始执行; Java虚拟机调用此线程的run方法。
  • public String getName() :获取当前线程名称。
  • public void setName(String name):设置该线程名称。
  • public static Thread currentThread() :返回对当前正在执行的线程对象的引用。在Thread子类中就是this,通常用于主线程和Runnable实现类
  • public static void sleep(long millis) :使当前正在执行的线程以指定的毫秒数暂停(暂时停止执行)。
  • public static void yield():yield只是让当前线程暂停一下,让系统的线程调度器重新调度一次,希望优先级与当前线程相同或更高的其他线程能够获得执行机会,但是这个不能保证,完全有可能的情况是,当某个线程调用了yield方法暂停之后,线程调度器又将其调度出来重新执行。

3.3 常用方法系列2

  • public final boolean isAlive():测试线程是否处于活动状态。如果线程已经启动且尚未终止,则为活动状态。

  • void join() :等待该线程终止。

    void join(long millis) :等待该线程终止的时间最长为 millis 毫秒。如果millis时间到,将不再等待。

    void join(long millis, int nanos) :等待该线程终止的时间最长为 millis 毫秒 + nanos 纳秒。

  • public final void stop():已过时,不建议使用。强行结束一个线程的执行,直接进入死亡状态。run()即刻停止,可能会导致一些清理性的工作得不到完成,如文件,数据库等的关闭。同时,会立即释放该线程所持有的所有的锁,导致数据得不到同步的处理,出现数据不一致的问题。

  • void suspend() / void resume() : 这两个操作就好比播放器的暂停和恢复。二者必须成对出现,否则非常容易发生死锁。suspend()调用会导致线程暂停,但不会释放任何锁资源,导致其它线程都无法访问被它占用的锁,直到调用resume()。已过时,不建议使用。

3.4 常用方法系列3

每个线程都有一定的优先级:

优先级相同的线程 —> 分时调度策略
优先级高的线程 —> 抢占式策略,获得较多的执行机会。
每个线程默认:和创建它的父线程优先级相同。

  • Thread类的三个优先级常量:
    • MAX_PRIORITY(10):最高优先级 【max_priority】
    • MIN _PRIORITY (1):最低优先级 【min_priority】
    • NORM_PRIORITY (5):普通优先级,默认情况下main线程具有普通优先级。 【norm_priority】
  • public final int getPriority() :返回线程优先级
  • public final void setPriority(int newPriority) :改变线程的优先级,范围在[1,10]之间。

练习:获取main线程对象的名称和优先级。

声明一个匿名内部类继承Thread类,重写run方法,在run方法中获取线程名称和优先级。设置该线程优先级为最高优先级并启动该线程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class MainTest {
public static void main(String[] args) {
//直接在构造器内部重写Runnable接口 实现run方法
Thread t= new Thread(new Runnable() {
@Override
public void run() {
System.out.println("获取main线程对象的名称和优先级");
System.out.println();
}
});
System.out.println(t.getName());
System.out.println(t.getPriority());
System.out.println("--------------");
//currentThread()是一个静态方法
System.out.println(Thread.currentThread().getName());
System.out.println(Thread.currentThread().getPriority());
}
}
最终输出:
Thread-0
5
--------------
main
5

案例:

  • 声明一个匿名内部类继承Thread类,重写run方法,实现打印[1,100]之间的偶数,要求每隔1秒打印1个偶数。

  • 声明一个匿名内部类继承Thread类,重写run方法,实现打印[1,100]之间的奇数,

    • 当打印到5时,让奇数线程暂停一下,再继续。
    • 当打印到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
public class MainTest {
public static void main(String[] args) {
Thread t1=new Thread(new Runnable(){
@Override
public void run(){
//打印1-100的偶数
for (int i=2;i<=100;i+=2) {
try {
//每隔1秒就打印一个
Thread.sleep(1000); //可能存在异常
} catch (InterruptedException e) {
throw new RuntimeException(e); //手动抛出异常 try-catch捕获异常
}
System.out.println(i);
}
}
});
t1.start();

Thread t2=new Thread(new Runnable() {
@Override
public void run() {
//打印1-100的奇数
for (int i=1;i<=100;i+=2) {
System.out.println(i);
if(i==5){
Thread.yield();
try {
t1.join(); //可能存在异常
} catch (InterruptedException e) {
throw new RuntimeException(e); //手动抛出异常 try-catch捕获异常
}
}
}
}
});
t2.start();

}
}

img

3.5 守护线程(看门狗)

有一种线程,它是在后台运行的,它的任务是为其他线程提供服务,这种线程被称为“守护线程”。
JVM的垃圾回收线程就是典型的守护线程。

守护线程有个特点,就是如果所有非守护线程都死亡,那么守护线程自动死亡。形象理解:兔死狗烹鸟尽弓藏

调用setDaemon(true)方法可将指定线程设置为守护线程。必须在线程启动之前设置,否则会报IllegalThreadStateException异常。

调用isDaemon()可以判断线程是否是守护线程。

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 TestThread {
public static void main(String[] args) {
//创建线程对象
MyDaemon m = new MyDaemon();
//设置为true
m.setDaemon(true); //指定线程为守护线程[必须在线程启动之前设置] --否则会报IllegalThreadStateException异常
//启动线程
m.start();
//输出1-100
for (int i = 1; i <= 100; i++) {
System.out.println("main:" + i);
}
}
}

class MyDaemon extends Thread {
public void run() {
while (true) {
System.out.println("我一直守护者你...");
try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}

image-20231019100823015

4. 多线程的生命周期

Java语言使用Thread类及其子类的对象来表示线程,在它的一个完整的生命周期中通常要经历如下一些状态:

4.1 JDK1.5之前:5种状态

线程的生命周期有五种状态:新建(New)、就绪(Runnable)、运行(Running)、阻塞(Blocked)、死亡(Dead)。CPU需要在多条线程之间切换,于是线程状态会多次在运行、阻塞、就绪之间切换。

image-20220401002307038

1.新建

当一个Thread类或其子类的对象被声明并创建时,新生的线程对象处于新建状态。此时它和其他Java对象一样,仅仅由JVM为其分配了内存,并初始化了实例变量的值。此时的线程对象并没有任何线程的动态特征,程序也不会执行它的线程体run()。

2.就绪

但是当线程对象调用了start()方法之后,就不一样了,线程就从新建状态转为就绪状态。JVM会为其创建方法调用栈和程序计数器,当然,处于这个状态中的线程并没有开始运行,只是表示已具备了运行的条件,随时可以被调度。至于什么时候被调度,取决于JVM里线程调度器的调度。

注意:

程序只能对新建状态的线程调用start(),并且只能调用一次,如果对非新建状态的线程,如已启动的线程或已死亡的线程调用start()都会报错IllegalThreadStateException异常。

3.运行

如果处于就绪状态的线程获得了CPU资源时,开始执行run()方法的线程体代码,则该线程处于运行状态。如果计算机只有一个CPU核心,在任何时刻只有一个线程处于运行状态,如果计算机有多个核心,将会有多个线程并行(Parallel)执行。

当然,美好的时光总是短暂的,而且CPU讲究雨露均沾。对于抢占式策略的系统而言,系统会给每个可执行的线程一个小时间段来处理任务,当该时间用完,系统会剥夺该线程所占用的资源,让其回到就绪状态等待下一次被调度。此时其他线程将获得执行机会,而在选择下一个线程时,系统会适当考虑线程的优先级。

4.阻塞

当在运行过程中的线程遇到如下情况时,会让出 CPU 并临时中止自己的执行,进入阻塞状态:

  • 线程调用了sleep()方法,主动放弃所占用的CPU资源;
  • 线程试图获取一个同步监视器,但该同步监视器正被其他线程持有;
  • 线程执行过程中,同步监视器调用了wait(),让它等待某个通知(notify);
  • 线程执行过程中,同步监视器调用了wait(time)
  • 线程执行过程中,遇到了其他线程对象的加塞(join);
  • 线程被调用suspend方法被挂起(已过时,因为容易发生死锁);

当前正在执行的线程被阻塞后,其他线程就有机会执行了。针对如上情况,当发生如下情况时会解除阻塞,让该线程重新进入就绪状态,等待线程调度器再次调度它:

  • 线程的sleep()时间到;
  • 线程成功获得了同步监视器;
  • 线程等到了通知(notify);
  • 线程wait的时间到了
  • 加塞的线程结束了;
  • 被挂起的线程又被调用了resume恢复方法(已过时,因为容易发生死锁);

5.死亡

线程会以以下三种方式之一结束,结束后的线程就处于死亡状态:

  • run()方法执行完成,线程正常结束
  • 线程执行过程中抛出了一个未捕获的异常(Exception)或错误(Error)
  • 直接调用该线程的stop()来结束该线程(已过时)

4.2 JDK1.5及之后:6种状态

在java.lang.Thread.State的枚举类中这样定义:

1
2
3
4
5
6
7
8
public enum State {
NEW,
RUNNABLE,
BLOCKED,
WAITING,
TIMED_WAITING,
TERMINATED;
}

image-20231019103232090

  • NEW(新建):线程刚被创建,但是并未启动。还没调用start方法。
  • RUNNABLE(可运行):这里没有区分就绪和运行状态。因为对于Java对象来说,只能标记为可运行,至于什么时候运行,不是JVM来控制的了,是OS来进行调度的,而且时间非常短暂,因此对于Java对象的状态来说,无法区分。
  • Terminated(被终止):表明此线程已经结束生命周期,终止运行。
  • 重点说明,根据Thread.State的定义,阻塞状态分为三种BLOCKEDWAITINGTIMED_WAITING
    • BLOCKED(锁阻塞):在API中的介绍为:一个正在阻塞、等待一个监视器锁(锁对象)的线程处于这一状态。只有获得锁对象的线程才能有执行机会。
      • 比如,线程A与线程B代码中使用同一锁,如果线程A获取到锁,线程A进入到Runnable状态,那么线程B就进入到Blocked锁阻塞状态。
    • TIMED_WAITING(计时等待):在API中的介绍为:一个正在限时等待另一个线程执行一个(唤醒)动作的线程处于这一状态。
      • 当前线程执行过程中遇到Thread类的sleepjoin,Object类的wait,LockSupport类的park方法,并且在调用这些方法时,设置了时间,那么当前线程会进入TIMED_WAITING,直到时间到,或被中断。
    • WAITING(无限等待):在API中介绍为:一个正在无限期等待另一个线程执行一个特别的(唤醒)动作的线程处于这一状态。
      • 当前线程执行过程中遇到遇到Object类的wait,Thread类的join,LockSupport类的park方法,并且在调用这些方法时,没有指定时间,那么当前线程会进入WAITING状态,直到被唤醒。
        • 通过Object类的wait进入WAITING状态的要有Object的notify/notifyAll唤醒;
        • 通过Condition的await进入WAITING状态的要有Condition的signal方法唤醒;
        • 通过LockSupport类的park方法进入WAITING状态的要有LockSupport类的unpark方法唤醒
        • 通过Thread类的join进入WAITING状态,只有调用join方法的线程对象结束才能让当前线程恢复;

说明:当从WAITING或TIMED_WAITING恢复到Runnable状态时,如果发现当前线程没有得到监视器锁,那么会立刻转入BLOCKED状态。

image-20220524203355448

我们在翻阅API的时候会发现Timed Waiting(计时等待) 与 Waiting(无限等待) 状态联系还是很紧密的,
比如Waiting(无限等待) 状态中wait方法是空参的,而timed waiting(计时等待) 中wait方法是带参的。
这种带参的方法,其实是一种倒计时操作,相当于我们生活中的小闹钟,我们设定好时间,到时通知,可是
如果提前得到(唤醒)通知,那么设定好时间在通知也就显得多此一举了,那么这种设计方案其实是一举两
得。如果没有得到(唤醒)通知,那么线程就处于Timed Waiting状态,直到倒计时完毕自动醒来;如果在倒
计时期间得到(唤醒)通知,那么线程从Timed Waiting状态立刻唤醒。

举例:

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
public class ThreadStateTest {
public static void main(String[] args) throws InterruptedException {
SubThread t = new SubThread();
System.out.println(t.getName() + " 状态 " + t.getState());
t.start();

while (Thread.State.TERMINATED != t.getState()) {
System.out.println(t.getName() + " 状态 " + t.getState());
Thread.sleep(500);
}
System.out.println(t.getName() + " 状态 " + t.getState());
}
}
//继承Thread类
class SubThread extends Thread {
@Override
public void run() {
while (true) {
for (int i = 0; i < 10; i++) {
System.out.println("打印:" + i);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
break;
}
}
}

命令行演示:

image-20220524195035355

5. 线程安全问题及解决

当我们使用多个线程访问同一资源(可以是同一个变量、同一个文件、同一条记录等)的时候,若多个线程只有读操作,那么不会发生线程安全问题。但是如果多个线程中对资源有读和写的操作,就容易出现线程安全问题。

举例:

image-20220401233218326

类比:

5.1 同一个资源问题和线程安全问题

案例:

火车站要卖票,我们模拟火车站的卖票过程。因为疫情期间,本次列车的座位共100个(即,只能出售100张火车票)。我们来模拟车站的售票窗口,实现多个窗口同时售票的过程。注意:不能出现错票、重票。

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
方式一:实现接口
//实现接口
class SaleTicket implements Runnable{
int ticket=100;
//实现接口的run方法
@Override
public void run() {
while(true){
if(ticket>0){
try {
Thread.sleep(10); //要让线程休眠10毫秒
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
System.out.println(Thread.currentThread().getName()+"售票,票号为"+ticket);
ticket--; //卖出去就少一张余额
}else{
break; //卖完了
}
}
}
}

public class WindowTest {
public static void main(String[] args) {
SaleTicket s=new SaleTicket();
Thread t1=new Thread(s);
Thread t2=new Thread(s);
Thread t3=new Thread(s);
//给线程设置名称
t1.setName("窗口1");
t2.setName("窗口2");
t3.setName("窗口3");
t1.start();
t2.start();
t3.start();
}
}
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
方式二:继承Thread类
package thread;
class Window extends Thread{
static int ticket = 100; //静态属性
@Override
public void run() {
while(true){
if(ticket > 0){
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + "售票,票号为:" + ticket);
ticket--;
}else{
break;
}
}
}
}

public class WindowTest1 {
public static void main(String[] args) {
Window w1 = new Window();
Window w2 = new Window();
Window w3 = new Window();
w1.setName("窗口1");
w2.setName("窗口2");
w3.setName("窗口3");
w1.start();
w2.start();
w3.start();
}
}

但是会出现一些安全问题:

image-20231019144713478

5.1.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
25
26
//方法一 继承Thread类
class Window extends Thread {
public void run() {
int ticket = 100;
while (ticket > 0) {
System.out.println(getName() + "卖出一张票,票号:" + ticket);
ticket--;
}
}
}

public class SaleTicketDemo1 {
public static void main(String[] args) {
Window w1 = new Window();
Window w2 = new Window();
Window w3 = new Window();

w1.setName("窗口1");
w2.setName("窗口2");
w3.setName("窗口3");

w1.start();
w2.start();
w3.start();
}
}

结果:发现卖出300张票。

问题:局部变量是每次调用方法都是独立的,那么每个线程的run()的ticket是独立的,不是共享数据。

5.1.2 不同对象的实例变量不共享

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
package com.atguigu.unsafe;

class TicketWindow extends Thread {
private int ticket = 100;

public void run() {
while (ticket > 0) {
System.out.println(getName() + "卖出一张票,票号:" + ticket);
ticket--;
}
}
}

public class SaleTicketDemo2 {
public static void main(String[] args) {
TicketWindow w1 = new TicketWindow();
TicketWindow w2 = new TicketWindow();
TicketWindow w3 = new TicketWindow();

w1.setName("窗口1");
w2.setName("窗口2");
w3.setName("窗口3");

w1.start();
w2.start();
w3.start();
}
}

结果:发现卖出300张票。

问题:不同的实例对象的实例变量是独立的。

5.1.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
package com.atguigu.unsafe;

class TicketSaleThread extends Thread {
private static int ticket = 100;

public void run() {
while (ticket > 0) {
try {
Thread.sleep(10);//加入这个,使得问题暴露的更明显
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(getName() + "卖出一张票,票号:" + ticket);
ticket--;
}
}
}

public class SaleTicketDemo3 {
public static void main(String[] args) {
TicketSaleThread t1 = new TicketSaleThread();
TicketSaleThread t2 = new TicketSaleThread();
TicketSaleThread t3 = new TicketSaleThread();

t1.setName("窗口1");
t2.setName("窗口2");
t3.setName("窗口3");

t1.start();
t2.start();
t3.start();
}
}

运行结果:

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
窗口1卖出一张票,票号:100
窗口2卖出一张票,票号:100
窗口3卖出一张票,票号:100
窗口3卖出一张票,票号:97
窗口1卖出一张票,票号:97
窗口2卖出一张票,票号:97
窗口1卖出一张票,票号:94
窗口3卖出一张票,票号:94
窗口2卖出一张票,票号:94
窗口2卖出一张票,票号:91
窗口1卖出一张票,票号:91
窗口3卖出一张票,票号:91
窗口3卖出一张票,票号:88
窗口1卖出一张票,票号:88
窗口2卖出一张票,票号:88
窗口3卖出一张票,票号:85
窗口1卖出一张票,票号:85
窗口2卖出一张票,票号:85
窗口3卖出一张票,票号:82
窗口1卖出一张票,票号:82
窗口2卖出一张票,票号:82
窗口2卖出一张票,票号:79
窗口3卖出一张票,票号:79
窗口1卖出一张票,票号:79
窗口3卖出一张票,票号:76
窗口1卖出一张票,票号:76
窗口2卖出一张票,票号:76
窗口1卖出一张票,票号:73
窗口2卖出一张票,票号:73
窗口3卖出一张票,票号:73
窗口2卖出一张票,票号:70
窗口1卖出一张票,票号:70
窗口3卖出一张票,票号:70
窗口2卖出一张票,票号:67
窗口3卖出一张票,票号:67
窗口1卖出一张票,票号:67
窗口1卖出一张票,票号:64
窗口3卖出一张票,票号:64
窗口2卖出一张票,票号:64
窗口2卖出一张票,票号:61
窗口3卖出一张票,票号:61
窗口1卖出一张票,票号:61
窗口1卖出一张票,票号:58
窗口2卖出一张票,票号:58
窗口3卖出一张票,票号:58
窗口2卖出一张票,票号:55
窗口1卖出一张票,票号:55
窗口3卖出一张票,票号:55
窗口3卖出一张票,票号:52
窗口1卖出一张票,票号:52
窗口2卖出一张票,票号:52
窗口2卖出一张票,票号:49
窗口1卖出一张票,票号:49
窗口3卖出一张票,票号:49
窗口2卖出一张票,票号:46
窗口3卖出一张票,票号:46
窗口1卖出一张票,票号:46
窗口2卖出一张票,票号:43
窗口3卖出一张票,票号:43
窗口1卖出一张票,票号:43
窗口3卖出一张票,票号:40
窗口1卖出一张票,票号:40
窗口2卖出一张票,票号:40
窗口2卖出一张票,票号:37
窗口3卖出一张票,票号:37
窗口1卖出一张票,票号:37
窗口2卖出一张票,票号:34
窗口1卖出一张票,票号:34
窗口3卖出一张票,票号:34
窗口3卖出一张票,票号:31
窗口2卖出一张票,票号:31
窗口1卖出一张票,票号:31
窗口1卖出一张票,票号:28
窗口2卖出一张票,票号:28
窗口3卖出一张票,票号:28
窗口2卖出一张票,票号:25
窗口1卖出一张票,票号:25
窗口3卖出一张票,票号:25
窗口2卖出一张票,票号:22
窗口3卖出一张票,票号:22
窗口1卖出一张票,票号:22
窗口3卖出一张票,票号:19
窗口1卖出一张票,票号:19
窗口2卖出一张票,票号:19
窗口2卖出一张票,票号:16
窗口3卖出一张票,票号:16
窗口1卖出一张票,票号:16
窗口2卖出一张票,票号:13
窗口1卖出一张票,票号:13
窗口3卖出一张票,票号:13
窗口2卖出一张票,票号:10
窗口1卖出一张票,票号:10
窗口3卖出一张票,票号:10
窗口3卖出一张票,票号:7
窗口1卖出一张票,票号:7
窗口2卖出一张票,票号:7
窗口3卖出一张票,票号:4
窗口1卖出一张票,票号:4
窗口2卖出一张票,票号:4
窗口3卖出一张票,票号:1
窗口2卖出一张票,票号:1
窗口1卖出一张票,票号:1

结果:发现卖出近100张票。

问题1:但是有重复票或负数票问题。

原因:线程安全问题

问题2:如果要考虑有两场电影,各卖100张票等

原因:TicketThread类的静态变量,是所有TicketThread类的对象共享

5.1.4 同一个对象的实例变量共享

示例代码:多个Thread线程使用同一个Runnable对象

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
package com.atguigu.safe;

class TicketSaleRunnable implements Runnable {
private int ticket = 100;

public void run() {
while (ticket > 0) {
try {
Thread.sleep(10);//加入这个,使得问题暴露的更明显
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + "卖出一张票,票号:" + ticket);
ticket--;
}
}
}

public class SaleTicketDemo4 {
public static void main(String[] args) {
TicketSaleRunnable tr = new TicketSaleRunnable();
Thread t1 = new Thread(tr, "窗口一");
Thread t2 = new Thread(tr, "窗口二");
Thread t3 = new Thread(tr, "窗口三");

t1.start();
t2.start();
t3.start();
}
}

结果:发现卖出近100张票。

问题:但是有重复票或负数票问题。

原因:线程安全问题

5.1.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
48
49
50
51
52
53
54
55
56
57
package com.atguigu.unsafe;

//1、编写资源类
class Ticket {
private int ticket = 100;

public void sale() {
if (ticket > 0) {
try {
Thread.sleep(10);//加入这个,使得问题暴露的更明显
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + "卖出一张票,票号:" + ticket);
ticket--;
} else {
throw new RuntimeException("没有票了");
}
}

public int getTicket() {
return ticket;
}
}

public class SaleTicketDemo5 {
public static void main(String[] args) {
//2、创建资源对象
Ticket ticket = new Ticket();

//3、启动多个线程操作资源类的对象
Thread t1 = new Thread("窗口一") {
public void run() {
while (true) {
ticket.sale();
}
}
};
Thread t2 = new Thread("窗口二") {
public void run() {
while (true) {
ticket.sale();
}
}
};
Thread t3 = new Thread(new Runnable() {
public void run() {
ticket.sale();
}
}, "窗口三");


t1.start();
t2.start();
t3.start();
}
}

结果:发现卖出近100张票。

问题:但是有重复票或负数票问题。

原因:线程安全问题

5.2 同步机制解决线程安全问题

要解决上述多线程并发访问一个资源的安全性问题:也就是解决重复票与不存在票问题,Java中提供了同步机制
(synchronized)来解决。

1563372934332

根据案例简述:

窗口1线程进入操作的时候,窗口2和窗口3线程只能在外等着,窗口1操作结束,窗口1和窗口2和窗口3才有机会进入代码去执行。也就是说在某个线程修改共享资源的时候,其他线程不能修改该资源,等待修改完毕同步之后,才能去抢夺CPU资源,完成对应的操作,保证了数据的同步性,解决了线程不安全的现象。

为了保证每个线程都能正常执行原子操作,Java引入了线程同步机制。注意:在任何时候,最多允许一个线程拥有同步锁,谁拿到锁就进入代码块,其他的线程只能在外等着(BLOCKED)。

5.2.1 同步机制解决线程安全问题的原理

同步机制的原理,其实就相当于给某段代码加“锁”,任何线程想要执行这段代码,都要先获得“锁”,我们称它为同步锁。因为Java对象在堆中的数据分为分为对象头、实例变量、空白的填充。而对象头中包含:

  • Mark Word:记录了和当前对象有关的GC、锁标记等信息。
  • 指向类的指针:每一个对象需要记录它是由哪个类创建出来的。
  • 数组长度(只有数组对象才有)

哪个线程获得了“同步锁”对象之后,”同步锁“对象就会记录这个线程的ID,这样其他线程就只能等待了,除非这个线程”释放“了锁对象,其他线程才能重新获得/占用”同步锁“对象。

5.2.2 同步代码块和同步方法

  • 同步代码块:synchronized 关键字可以用于某个区块前面,表示只对这个区块的资源实行互斥访问。
    格式:
1
2
3
synchronized(同步监视器/同步锁){
     需要同步操作的代码
}
  • 同步方法:synchronized 关键字直接修饰方法,表示同一时刻只有一个线程能进入这个方法,其他线程在外面等着。
1
2
3
public synchronized void method(){
    可能会产生线程安全问题的代码
}

5.2.3 同步锁机制

在《Thinking in Java》中,是这么说的:对于并发工作,你需要某种方式来防止两个任务访问相同的资源(其实就是共享资源竞争)。 防止这种冲突的方法就是当资源被一个任务使用时,在其上加锁。第一个访问某项资源的任务必须锁定这项资源,使其他任务在其被解锁之前,就无法访问它了,而在其被解锁之时,另一个任务就可以锁定并使用它了。

5.2.4 synchronized的锁是什么

同步锁对象可以是任意类型,但是必须保证竞争“同一个共享资源”的多个线程必须使用同一个“同步锁对象”。

对于同步代码块来说,同步锁对象是由程序员手动指定的(很多时候也是指定为this或类名.class),但是对于同步方法来说,同步锁对象只能是默认的:

  • 静态方法:当前类的Class对象(类名.class)

  • 非静态方法:this

5.2.5 同步操作的思考顺序

1、如何找问题,即代码是否存在线程安全?(非常重要)
(1)明确哪些代码是多线程运行的代码
(2)明确多个线程是否有共享数据
(3)明确多线程运行代码中是否有多条语句操作共享数据

2、如何解决呢?(非常重要)
对多条操作共享数据的语句,只能让一个线程都执行完,在执行过程中,其他线程不可以参与执行。
即所有操作共享数据的这些语句都要放在同步范围中

3、切记:

范围太小:不能解决安全问题

范围太大:因为一旦某个线程抢到锁,其他线程就只能等待,所以范围太大,效率会降低,不能合理利用CPU资源。

5.2.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
28
29
30
31
32
package com.atguigu.safe;

class TicketSaleThread extends Thread{
private static int ticket = 100;
public void run(){//直接锁这里,肯定不行,会导致,只有一个窗口卖票
while (ticket > 0) {
saleOneTicket();
}
}

public synchronized static void saleOneTicket(){//锁对象是TicketSaleThread类的Class对象,而一个类的Class对象在内存中肯定只有一个
if(ticket > 0) {//不加条件,相当于条件判断没有进入锁管控,线程安全问题就没有解决
System.out.println(Thread.currentThread().getName() + "卖出一张票,票号:" + ticket);
ticket--;
}
}
}
public class SaleTicketDemo3 {
public static void main(String[] args) {
TicketSaleThread t1 = new TicketSaleThread();
TicketSaleThread t2 = new TicketSaleThread();
TicketSaleThread t3 = new TicketSaleThread();

t1.setName("窗口1");
t2.setName("窗口2");
t3.setName("窗口3");

t1.start();
t2.start();
t3.start();
}
}
示例二:非静态方法加锁
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
public class SaleTicketDemo4 {
public static void main(String[] args) {
TicketSaleRunnable tr = new TicketSaleRunnable();
Thread t1 = new Thread(tr, "窗口一");
Thread t2 = new Thread(tr, "窗口二");
Thread t3 = new Thread(tr, "窗口三");

t1.start();
t2.start();
t3.start();
}
}

class TicketSaleRunnable implements Runnable {
private int ticket = 100;

public void run() {//直接锁这里,肯定不行,会导致,只有一个窗口卖票
while (ticket > 0) {
saleOneTicket();
}
}

public synchronized void saleOneTicket() {//锁对象是this,这里就是TicketSaleRunnable对象,因为上面3个线程使用同一个TicketSaleRunnable对象,所以可以
if (ticket > 0) {//不加条件,相当于条件判断没有进入锁管控,线程安全问题就没有解决
System.out.println(Thread.currentThread().getName() + "卖出一张票,票号:" + ticket);
ticket--;
}
}
}
示例三:同步代码块
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
public class SaleTicketDemo5 {
public static void main(String[] args) {
//2、创建资源对象
Ticket ticket = new Ticket();

//3、启动多个线程操作资源类的对象
Thread t1 = new Thread("窗口一") {
public void run() {//不能给run()直接加锁,因为t1,t2,t3的三个run方法分别属于三个Thread类对象,
// run方法是非静态方法,那么锁对象默认选this,那么锁对象根本不是同一个
while (true) {
synchronized (ticket) {
ticket.sale();
}
}
}
};
Thread t2 = new Thread("窗口二") {
public void run() {
while (true) {
synchronized (ticket) {
ticket.sale();
}
}
}
};
Thread t3 = new Thread(new Runnable() {
public void run() {
while (true) {
synchronized (ticket) {
ticket.sale();
}
}
}
}, "窗口三");


t1.start();
t2.start();
t3.start();
}
}

//1、编写资源类
class Ticket {
private int ticket = 1000;

public void sale() {//也可以直接给这个方法加锁,锁对象是this,这里就是Ticket对象
if (ticket > 0) {
System.out.println(Thread.currentThread().getName() + "卖出一张票,票号:" + ticket);
ticket--;
} else {
throw new RuntimeException("没有票了");
}
}

public int getTicket() {
return ticket;
}
}

5.3 练习

银行有一个账户。
有两个储户分别向同一个账户存3000元,每次存1000,存3次。每次存完打印账户余额。

问题:该程序是否有安全问题,如果有,如何解决?

【提示】
1,明确哪些代码是多线程运行代码,须写入run()方法 —deposit存钱方法【因为可能会出现存钱异常】
2,明确什么是共享数据。 —balance余额
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
35
36
37
38
39
40
41
42
43
44
45
46
47
class Account{ //账户
private double balance;//余额
//set和get方法
public double getBalance() {
return balance;
}
public void setBalance(double balance) {
this.balance = balance;
}
//存款方法 --要写成同步方法
public synchronized void deposit(double money){ //非静态方法默认是this 因为account是唯一的 所以可以
this.balance+=money;
System.out.println(Thread.currentThread().getName()+"充了1000元,现在余额是:"+this.getBalance());
}
}

class Customer extends Thread{
//有一个账户对象
Account account;
//有参构造器
public Customer(Account account){
this.account=account;
}
public Customer(Account account,String name){
super(name);
this.account=account;
}
@Override
public void run(){
//存钱的操作要放入run方法
for(int i=0;i<3;i++){
account.deposit(1000);
}
}

}

public class AccountTest {
public static void main(String[] args) {
//创建账户类对象
Account account = new Account();
Customer customer1 = new Customer(account,"甲");
Customer customer2 = new Customer(account,"乙");
customer1.start();
customer2.start();
}
}

image-20231019162559285

6. 再谈同步

6.1 单例设计模式的线程安全问题

6.1.1 饿汉式没有线程安全问题

饿汉式:在类初始化时就直接创建单例对象,而类初始化过程是没有线程安全问题的

形式一:

1
2
3
4
5
6
7
8
9
public class HungrySingle {
private static HungrySingle INSTANCE = new HungrySingle(); //对象是否声明为final 都可以

private HungrySingle(){}

public static HungrySingle getInstance(){
return INSTANCE;
}
}

形式二:

1
2
3
4
5
6
7
8
9
/*
public class HungryOne{
public static final HungryOne INSTANCE = new HungryOne();
private HungryOne(){}
}*/

public enum HungryOne{
INSTANCE
}

测试类:

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
package com.atguigu.single.hungry;

public class HungrySingleTest {

static HungrySingle hs1 = null;
static HungrySingle hs2 = null;

//演示存在的线程安全问题
public static void main(String[] args) {

Thread t1 = new Thread() {
@Override
public void run() {
hs1 = HungrySingle.getInstance();
}
};

Thread t2 = new Thread() {
@Override
public void run() {
hs2 = HungrySingle.getInstance();
}
};

t1.start();
t2.start();

try {
t1.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
try {
t2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}

System.out.println(hs1);
System.out.println(hs2);
System.out.println(hs1 == hs2);//true
}

}

6.1.2 懒汉式线程安全问题

懒汉式:延迟创建对象,第一次调用getInstance方法再创建对象

形式一:

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
package com.atguigu.single.lazy;

public class LazyOne {
private static LazyOne instance;

private LazyOne(){}

//方式1:
public static synchronized LazyOne getInstance1(){
if(instance == null){
instance = new LazyOne();
}
return instance;
}
//方式2:
public static LazyOne getInstance2(){
synchronized(LazyOne.class) {
if (instance == null) {
instance = new LazyOne();
}
return instance;
}
}
//方式3:
public static LazyOne getInstance3(){
if(instance == null){
synchronized (LazyOne.class) {
try {
Thread.sleep(10);//加这个代码,暴露问题
} catch (InterruptedException e) {
e.printStackTrace();
}
if(instance == null){
instance = new LazyOne();
}
}
}

return instance;
}
/*
注意:上述方式3中,有指令重排问题
mem = allocate(); 为单例对象分配内存空间
instance = mem; instance引用现在非空,但还未初始化
ctorSingleton(instance); 为单例对象通过instance调用构造器
从JDK2开始,分配空间、初始化、调用构造器会在线程的工作存储区一次性完成,然后复制到主存储区。但是需要
volatile关键字,避免指令重排。
*/

}

形式二:使用内部类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package com.atguigu.single.lazy;

public class LazySingle {
private LazySingle(){}

public static LazySingle getInstance(){
return Inner.INSTANCE;
}

private static class Inner{
static final LazySingle INSTANCE = new LazySingle();
}

}

内部类只有在外部类被调用才加载,产生INSTANCE实例;又不用加锁。

此模式具有之前两个模式的优点,同时屏蔽了它们的缺点,是最好的单例模式。

此时的内部类,使用enum进行定义,也是可以的。

测试类:

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
package com.atguigu.single.lazy;

import org.junit.Test;

public class TestLazy {
@Test
public void test01(){
LazyOne s1 = LazyOne.getInstance();
LazyOne s2 = LazyOne.getInstance();

System.out.println(s1);
System.out.println(s2);
System.out.println(s1 == s2);
}

//把s1和s2声明在外面,是想要在线程的匿名内部类中为s1和s2赋值
LazyOne s1;
LazyOne s2;
@Test
public void test02(){
Thread t1 = new Thread(){
public void run(){
s1 = LazyOne.getInstance();
}
};
Thread t2 = new Thread(){
public void run(){
s2 = LazyOne.getInstance();
}
};

t1.start();
t2.start();

try {
t1.join();
t2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}

System.out.println(s1);
System.out.println(s2);
System.out.println(s1 == s2);
}


LazySingle obj1;
LazySingle obj2;
@Test
public void test03(){
Thread t1 = new Thread(){
public void run(){
obj1 = LazySingle.getInstance();
}
};
Thread t2 = new Thread(){
public void run(){
obj2 = LazySingle.getInstance();
}
};

t1.start();
t2.start();

try {
t1.join();
t2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}

System.out.println(obj1);
System.out.println(obj2);
System.out.println(obj1 == obj2);
}
}

6.2 死锁

不同的线程分别占用对方需要的同步资源不放弃,都在等待对方放弃自己需要的同步资源,就形成了线程的死锁。

thread-lock

【小故事】

面试官:你能解释清楚什么是死锁,我就录取你!
面试者:你录取我,我就告诉你什么是死锁!
….
恭喜你,面试通过了

一旦出现死锁,整个程序既不会发生异常,也不会给出任何提示,只是所有线程处于阻塞状态,无法继续。

举例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
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
public class DeadLockTest {
public static void main(String[] args) {

StringBuilder s1 = new StringBuilder();
StringBuilder s2 = new StringBuilder();

new Thread() {
public void run() {
synchronized (s1) {
s1.append("a");
s2.append("1");

try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}

synchronized (s2) {
s1.append("b");
s2.append("2");

System.out.println(s1);
System.out.println(s2);

}
}
}
}.start();

new Thread() {
public void run() {
synchronized (s2) {
s1.append("c");
s2.append("3");

try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}

synchronized (s1) {
s1.append("d");
s2.append("4");

System.out.println(s1);
System.out.println(s2);

}

}
}
}.start();

}
}

举例2:

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
class A {
public synchronized void foo(B b) {
System.out.println("当前线程名: " + Thread.currentThread().getName()
+ " 进入了A实例的foo方法"); // ①
try {
Thread.sleep(200);
} catch (InterruptedException ex) {
ex.printStackTrace();
}
System.out.println("当前线程名: " + Thread.currentThread().getName()
+ " 企图调用B实例的last方法"); // ③
b.last();
}

public synchronized void last() {
System.out.println("进入了A类的last方法内部");
}
}

class B {
public synchronized void bar(A a) {
System.out.println("当前线程名: " + Thread.currentThread().getName()
+ " 进入了B实例的bar方法"); // ②
try {
Thread.sleep(200);
} catch (InterruptedException ex) {
ex.printStackTrace();
}
System.out.println("当前线程名: " + Thread.currentThread().getName()
+ " 企图调用A实例的last方法"); // ④
a.last();
}

public synchronized void last() {
System.out.println("进入了B类的last方法内部");
}
}

public class DeadLock implements Runnable {
A a = new A();
B b = new B();

public void init() {
Thread.currentThread().setName("主线程");
// 调用a对象的foo方法
a.foo(b);
System.out.println("进入了主线程之后");
}

public void run() {
Thread.currentThread().setName("副线程");
// 调用b对象的bar方法
b.bar(a);
System.out.println("进入了副线程之后");
}

public static void main(String[] args) {
DeadLock dl = new DeadLock();
new Thread(dl).start();
dl.init();
}
}

举例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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class TestDeadLock {
public static void main(String[] args) {
Object g = new Object();
Object m = new Object();
Owner s = new Owner(g,m);
Customer c = new Customer(g,m);
new Thread(s).start();
new Thread(c).start();
}
}
class Owner implements Runnable{
private Object goods;
private Object money;

public Owner(Object goods, Object money) {
super();
this.goods = goods;
this.money = money;
}

@Override
public void run() {
synchronized (goods) {
System.out.println("先给钱");
synchronized (money) {
System.out.println("发货");
}
}
}
}
class Customer implements Runnable{
private Object goods;
private Object money;

public Customer(Object goods, Object money) {
super();
this.goods = goods;
this.money = money;
}

@Override
public void run() {
synchronized (money) {
System.out.println("先发货");
synchronized (goods) {
System.out.println("再给钱");
}
}
}
}

诱发死锁的原因:

  • 互斥条件【一定会存在,因为同步机制】
  • 占用且等待
  • 不可抢夺(或不可抢占)
  • 循环等待

以上4个条件,同时出现就会触发死锁。

解决死锁:破坏2,3,4其中一个

死锁一旦出现,基本很难人为干预,只能尽量规避。可以考虑打破上面的诱发条件。

针对条件1:互斥条件基本上无法被破坏。因为线程需要通过互斥解决安全问题。

针对条件2:可以考虑一次性申请所有所需的资源,这样就不存在等待的问题。

针对条件3:占用部分资源的线程在进一步申请其他资源时,如果申请不到,就主动释放掉已经占用的资源。

针对条件4:可以将资源改为线性顺序。申请资源时,先申请序号较小的,这样避免循环等待问题。

6.3 JDK5.0新特性:Lock(锁)

  • JDK5.0的新增功能,保证线程的安全。与采用synchronized相比,Lock可提供多种锁方案,更灵活、更强大。Lock通过显式定义同步锁对象来实现同步。同步锁使用Lock对象充当。

  • java.util.concurrent.locks.Lock接口是控制多个线程对共享资源进行访问的工具。锁提供了对共享资源的独占访问,每次只能有一个线程对Lock对象加锁,线程开始访问共享资源之前应先获得Lock对象。

  • 在实现线程安全的控制中,比较常用的是ReentrantLock,可以显式加锁、释放锁。

    • ReentrantLock类实现了 Lock 接口,它拥有与 synchronized 相同的并发性和内存语义,但是添加了类似锁投票、定时锁等候和可中断锁等候的一些特性。此外,它还提供了在激烈争用情况下更佳的性能。
  • Lock锁也称同步锁,加锁与释放锁方法,如下:

    • public void lock() :加同步锁。
    • public void unlock() :释放同步锁。
  • 代码结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class A{
//1. 创建Lock的实例,必须确保多个线程共享同一个Lock实例
private final ReentrantLock lock = new ReenTrantLock();
public void m(){
//2. 调动lock(),实现需共享的代码的锁定
lock.lock();
try{
//保证线程安全的代码;
}
finally{
lock.unlock();
}
}
}

注意:如果同步代码有异常,要将unlock()写入finally语句块。

举例:

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
class Window implements Runnable{
int ticket = 100;
//1. 创建Lock的实例,必须确保多个线程共享同一个Lock实例
private final ReentrantLock lock = new ReentrantLock();
public void run(){

while(true){
try{
//2. 调动lock(),实现需共享的代码的锁定
lock.lock();
if(ticket > 0){
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(ticket--);
}else{
break;
}
}finally{
//3. 调用unlock(),释放共享代码的锁定
lock.unlock();
}
}
}
}

public class ThreadLock {
public static void main(String[] args) {
Window t = new Window();
Thread t1 = new Thread(t);
Thread t2 = new Thread(t);
t1.start();
t2.start();
}
}

synchronized与Lock的对比

  1. Lock是显式锁(手动开启和关闭锁,别忘记关闭锁),synchronized是隐式锁,出了作用域、遇到异常等自动解锁
  2. Lock只有代码块锁,synchronized有代码块锁和方法锁
  3. 使用Lock锁,JVM将花费较少的时间来调度线程,性能更好。并且具有更好的扩展性(提供更多的子类),更体现面向对象。
  4. (了解)Lock锁可以对读不加锁,对写加锁,synchronized不可以
  5. (了解)Lock锁可以有多种获取锁的方式,可以从sleep的线程中抢到锁,synchronized不可以

说明:开发建议中处理线程安全问题优先使用顺序为:

• Lock —-> 同步代码块 —-> 同步方法

7. 线程的通信

7.1 线程间通信

为什么要处理线程间通信:

当我们需要多个线程来共同完成一件任务,并且我们希望他们有规律的执行,那么多线程之间需要一些通信机制,可以协调它们的工作,以此实现多线程共同操作一份数据。

比如:线程A用来生产包子的,线程B用来吃包子的,包子可以理解为同一资源,线程A与线程B处理的动作,一个是生产,一个是消费,此时B线程必须等到A线程完成后才能执行,那么线程A与线程B之间就需要线程通信,即—— 等待唤醒机制。

7.2 等待唤醒机制

这是多个线程间的一种协作机制。谈到线程我们经常想到的是线程间的竞争(race),比如去争夺锁,但这并不是故事的全部,线程间也会有协作机制。

在一个线程满足某个条件时,就进入等待状态(wait() / wait(time)), 等待其他线程执行完他们的指定代码过后再将其唤醒(notify());或可以指定wait的时间,等时间到了自动唤醒;在有多个线程进行等待时,如果需要,可以使用 notifyAll()来唤醒所有的等待线程。wait/notify 就是线程间的一种协作机制。

  1. wait:线程不再活动,不再参与调度,进入 wait set 中,因此不会浪费 CPU 资源,也不会去竞争锁了,这时的线程状态是 WAITING 或 TIMED_WAITING。它还要等着别的线程执行一个特别的动作,也即“通知(notify)”或者等待时间到,在这个对象上等待的线程从wait set 中释放出来,重新进入到调度队列(ready queue)中
  2. notify:则选取所通知对象的 wait set 中的一个线程释放;
  3. notifyAll:则释放所通知对象的 wait set 上的全部线程。

注意:

被通知的线程被唤醒后也不一定能立即恢复执行,因为它当初中断的地方是在同步块内,而此刻它已经不持有锁,所以它需要再次尝试去获取锁(很可能面临其它线程的竞争),成功后才能在当初调用 wait 方法之后的地方恢复执行。

总结如下:

  • 如果能获取锁,线程就从 WAITING 状态变成 RUNNABLE(可运行) 状态;
  • 否则,线程就从 WAITING 状态又变成 BLOCKED(等待锁) 状态

7.3 举例

例题:使用两个线程打印 1-100。线程1, 线程2 交替打印

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
public class replaceTest {
public static void main(String[] args) {
//3.创建实现类的对象
replace r=new replace();
//执行两个线程
//4.执行start方法
Thread t1=new Thread(r);
t1.start();
//4.执行start方法
Thread t2=new Thread(r);
t2.start();
}
}

class replace implements Runnable{ //1.实现Runnable接口
int i=1;
//2.重写run方法
@Override
public void run(){
while(true){
synchronized (this) {
notify(); //唤醒
if(i<=100){
System.out.println(Thread.currentThread().getName() + ":" + i++);
}else{
break;
}
try { //会抛出异常要记得捕获异常
wait(); //等待
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}

7.4 调用wait和notify需注意的细节

  1. wait方法与notify方法必须要由同一个锁对象调用。因为:对应的锁对象可以通过notify唤醒使用同一个锁对象调用的wait方法后的线程。
  2. wait方法与notify方法是属于Object类的方法的。因为:锁对象可以是任意对象,而任意对象的所属类都是继承了Object类的。
  3. wait方法与notify方法必须要在同步代码块或者是同步函数中使用。因为:必须要通过锁对象调用这2个方法。否则会报java.lang.IllegalMonitorStateException异常。

7.5 生产者与消费者问题

等待唤醒机制可以解决经典的“生产者与消费者”的问题。生产者与消费者问题(英语:Producer-consumer problem)/限缓冲问题(英语:Bounded-buffer problem),是一个多线程同步问题的经典案例。该问题描述了两个(多个)共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。

生产者的主要作用是生成一定量的数据放到缓冲区中,然后重复此过程。与此同时,消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据,消费者也不会在缓冲区中空时消耗数据。

举例:

生产者(Productor)将产品交给店员(Clerk),而消费者(Customer)从店员处取走产品,店员一次只能持有固定数量的产品(比如:20),如果生产者试图生产更多的产品,店员会叫生产者停一下,如果店中有空位放产品了再通知生产者继续生产;如果店中没有产品了,店员会告诉消费者等一下,如果店中有产品了再通知消费者来取走产品。

类似的场景,比如厨师和服务员等。

生产者与消费者问题中其实隐含了两个问题:

  • 线程安全问题:因为生产者与消费者共享数据缓冲区,产生安全问题。不过这个问题可以使用同步解决。
  • 线程的协调工作问题:
    • 要解决该问题,就必须让生产者线程在缓冲区满时等待(wait),暂停进入阻塞状态,等到下次消费者消耗了缓冲区中的数据的时候,通知(notify)正在等待的线程恢复到就绪状态,重新开始往缓冲区添加数据。同样,也可以让消费者线程在缓冲区空时进入等待(wait),暂停进入阻塞状态,等到生产者往缓冲区添加数据之后,再通知(notify)正在等待的线程恢复到就绪状态。

代码实现:

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
public class ProducerConsumerTest {
public static void main(String[] args) {
Clerk clerk=new Clerk();
Producer p1=new Producer(clerk);
p1.setName("生产者1");
Consumer c1=new Consumer(clerk);
c1.setName("消费者1");
Consumer c2=new Consumer(clerk);
c1.setName("消费者2");
p1.start();
c1.start();
c2.start();
}
}
class Clerk{ //店员
private int productNum=0; //商品数量

//增加产品数量方法
public synchronized void addProduct() throws InterruptedException { //共享数据是productNum 所以要将方法改为同步方法
if(productNum>=20){
//等待
wait();
}else{
productNum++;
System.out.println(Thread.currentThread().getName() + "生产了第" + productNum + "个产品");
//只要生产了一个那就唤醒消费者消费
notify();
}
}
//减少产品数量方法
public synchronized void minusProduct() throws InterruptedException { //共享数据是productNum 所以要将方法改为同步方法
if(productNum<=0){
wait();
}else{
System.out.println(Thread.currentThread().getName() + "消费了第" + productNum + "个产品");
productNum--;
//只要消费了一个那就唤醒生产者生产
notifyAll();
}
}

}

class Producer extends Thread{ //生产者
private Clerk clerk;
public Producer(Clerk clerk){
this.clerk=clerk;
}
@Override
public void run(){ //生产
while(true){
System.out.println("生产者开始生产产品");
//sleep一会吧
try {
Thread.sleep(50);
} catch (InterruptedException e) {
e.printStackTrace();
}
//消费产品
try {
clerk.addProduct(); //生产商品
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
}

class Consumer extends Thread{ //消费者
private Clerk clerk;
public Consumer(Clerk clerk){
this.clerk=clerk;
}
@Override
public void run(){ //消费
while(true){
System.out.println("消费者开始消费产品");
//sleep一会吧
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
//消费产品
try {
clerk.minusProduct(); //消费商品
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
}

7.6 面试题:区分sleep()和wait()

相同点:一旦执行,都会使得当前线程结束执行状态,进入阻塞状态。

不同点:

① 定义方法所属的类:sleep():Thread中定义。 wait():Object中定义

② 使用范围的不同:sleep()可以在任何需要使用的位置被调用; wait():必须使用在同步代码块或同步方法中

③ 都在同步结构中使用的时候,是否释放同步监视器的操作不同:sleep():不会释放同步监视器 ;wait():会释放同步监视器

④ 结束等待的方式不同:sleep():指定时间一到就结束阻塞。 wait():可以指定时间/无限等待直到notify或notifyAll。

7.7 是否释放锁的操作

任何线程进入同步代码块、同步方法之前,必须先获得对同步监视器的锁定,那么何时会释放对同步监视器的锁定呢?

7.7.1 释放锁的操作

当前线程的同步方法、同步代码块执行结束。

当前线程在同步代码块、同步方法中遇到break、return终止了该代码块、该方法的继续执行。

当前线程在同步代码块、同步方法中出现了未处理的Error或Exception,导致当前线程异常结束。

当前线程在同步代码块、同步方法中执行了锁对象的wait()方法,当前线程被挂起,并释放锁。

7.7.2 不会释放锁的操作

线程执行同步代码块或同步方法时,程序调用Thread.sleep()、Thread.yield()方法暂停当前线程的执行。

线程执行同步代码块时,其他线程调用了该线程的suspend()方法将该该线程挂起,该线程不会释放锁(同步监视器)。

  • 应尽量避免使用suspend()和resume()这样的过时来控制线程。

8. JDK5.0新增线程创建方式

8.1 新增方式一:实现Callable接口

  • 与使用Runnable相比, Callable功能更强大些
    • 相比run()方法,可以有返回值
    • 方法可以抛出异常
    • 支持泛型的返回值(需要借助FutureTask类,获取返回结果)
  • Future接口(了解)
    • 可以对具体Runnable、Callable任务的执行结果进行取消、查询是否完成、获取结果等。
    • FutureTask是Futrue接口的唯一的实现类
    • FutureTask 同时实现了Runnable, Future接口。它既可以作为Runnable被线程执行,又可以作为Future得到Callable的返回值
  • 缺点:在获取分线程执行结果的时候,当前线程(或是主线程)受阻塞,效率较低。
  • 代码举例
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
/*
* 创建多线程的方式三:实现Callable (jdk5.0新增的)
*/
//1.创建一个实现Callable的实现类
class NumThread implements Callable {
//2.实现call方法,将此线程需要执行的操作声明在call()中
@Override
public Object call() throws Exception {
int sum = 0;
for (int i = 1; i <= 100; i++) {
if (i % 2 == 0) {
System.out.println(i);
sum += i;
}
}
return sum;
}
}


public class CallableTest {
public static void main(String[] args) {
//3.创建Callable接口实现类的对象
NumThread numThread = new NumThread();

//4.将此Callable接口实现类的对象作为传递到FutureTask构造器中,创建FutureTask的对象
FutureTask futureTask = new FutureTask(numThread);
//5.将FutureTask的对象作为参数传递到Thread类的构造器中,创建Thread对象,并调用start()
new Thread(futureTask).start();


// 接收返回值
try {
//6.获取Callable中call方法的返回值
//get()返回值即为FutureTask构造器参数Callable实现类重写的call()的返回值。
Object sum = futureTask.get();
System.out.println("总和为:" + sum);
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
}
}

}

8.2 新增方式二:使用线程池

现有问题:

如果并发的线程数量很多,并且每个线程都是执行一个时间很短的任务就结束了,这样频繁创建线程就会大大降低系统的效率,因为频繁创建线程和销毁线程需要时间。

那么有没有一种办法使得线程可以复用,即执行完一个任务,并不被销毁,而是可以继续执行其他的任务?

思路:提前创建好多个线程,放入线程池中,使用时直接获取,使用完放回池中。可以避免频繁创建销毁、实现重复利用。类似生活中的公共交通工具。

线程池的理解

好处:

  • 提高响应速度(减少了创建新线程的时间)

  • 降低资源消耗(重复利用线程池中线程,不需要每次都创建)

  • 便于线程管理

    • corePoolSize:核心池的大小
    • maximumPoolSize:最大线程数
    • keepAliveTime:线程没有任务时最多保持多长时间后会终止

线程池相关API

  • JDK5.0之前,我们必须手动自定义线程池。
    从JDK5.0开始,Java内置线程池相关的API。
    java.util.concurrent包下提供了线程池相关API:ExecutorServiceExecutors
  • ExecutorService:真正的线程池接口。常见子类ThreadPoolExecutor
    • void execute(Runnable command) :执行任务/命令,没有返回值,一般用来执行Runnable
    • <T> Future<T> submit(Callable<T> task):执行任务,有返回值,一般又来执行Callable
    • void shutdown() :关闭连接池
  • Executors:一个线程池的工厂类,通过此类的静态工厂方法可以创建多种类型的线程池对象。
    • Executors.newCachedThreadPool():创建一个可根据需要创建新线程的线程池
    • Executors.newFixedThreadPool(int nThreads); 创建一个可重用固定线程数的线程池
    • Executors.newSingleThreadExecutor() :创建一个只有一个线程的线程池
    • Executors.newScheduledThreadPool(int corePoolSize):创建一个线程池,它可在延迟后运行命令/定期执行

代码举例:

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
class NumberThread implements Runnable{

@Override
public void run() {
for(int i = 0;i <= 100;i++){
if(i % 2 == 0){
System.out.println(Thread.currentThread().getName() + ": " + i);
}
}
}
}

class NumberThread1 implements Runnable{

@Override
public void run() {
for(int i = 0;i <= 100;i++){
if(i % 2 != 0){
System.out.println(Thread.currentThread().getName() + ": " + i);
}
}
}
}

class NumberThread2 implements Callable {
@Override
public Object call() throws Exception {
int evenSum = 0;//记录偶数的和
for(int i = 0;i <= 100;i++){
if(i % 2 == 0){
evenSum += i;
}
}
return evenSum;
}

}

public class ThreadPoolTest {
public static void main(String[] args) {
//1. 提供指定线程数量的线程池
ExecutorService service = Executors.newFixedThreadPool(10);
ThreadPoolExecutor service1 = (ThreadPoolExecutor) service;
// //设置线程池的属性
// System.out.println(service.getClass());//ThreadPoolExecutor
service1.setMaximumPoolSize(50); //设置线程池中线程数的上限

//2.执行指定的线程的操作。需要提供实现Runnable接口或Callable接口实现类的对象
service.execute(new NumberThread());//适合适用于Runnable
service.execute(new NumberThread1());//适合适用于Runnable

try {
Future future = service.submit(new NumberThread2());//适合使用于Callable
System.out.println("总和为:" + future.get());
} catch (Exception e) {
e.printStackTrace();
}
//3.关闭连接池
service.shutdown();
}
}

image-20231020102356783

List接口

一、List接口
java.util.List接口 extends Collection接口

特点:

  1. 有序的集合(存储和取出元素的顺序一致)
  2. 索引,包括了一些有索引的方法
  3. 存储重复的元素
  4. 实现类
    Arraylist(底层采用数组结构,查询快,增删慢),
    LinkedList(底层采用链表结构,查询慢,增删快),
    Vector(底层采用数组结构,查询快,增删慢)

举例:

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
import java.util.*;
public class Main extends Object{
public static void main(String[] args) {
//创建一个List集合对象(多态)
List<String> list=new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("a");
System.out.println(list);
System.out.println("!!!!!!!!!!!!!!!!!!!");


//使用增强for循环
for(String i:list)
{
System.out.println(i);
}

System.out.println("!!!!!!!!!!!!!!!!!!!");


//使用迭代器
Iterator<String> lists=set.iterator();
while(sets.hasNext())
{
String a=lists.next();
System.out.println(a);
}

}
}

代码结果如下:
[a, b, c, d, a] (重复的a可以打印出来!!!)
!!!!!!!!!!!!!!!!!!!
a
b
c
d
a
!!!!!!!!!!!!!!!!!!!
a
b
c
d
a


特定(索引)的方法:

  1. public void add(int index,E element);将指定元素添加到集合的指定位置
  2. public E get(int index);返回指定位置元素
  3. public E remove(int index);移除指定位置元素(返回被移除的元素)  需要赋给一个变量
  4. public E set(int index,E element);替换指定位置元素(返回之前的元素)  需要赋给一个变量

举例:

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.*;
public class Main extends Object{
public static void main(String[] args) {
//创建一个List集合对象(多态)

List<String> list=new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("a");
System.out.println(list); //[a, b, c, d, a]

//public void add(int index,E element); 添加
list.add(3,"woaini"); //形参为给第几个位置添加什么字符串
System.out.println(list); //[a, b, c, woaini, d, a]

//public E remove(int index); 移除(返回被移除的元素)
String yuanlai1=list.remove(2); //形参是int型
System.out.println("被移除的是:"+yuanlai1); //输出字符串必须要用"+"符号
System.out.println(list); //[a, b, woaini, d, a]


//public E set(int index,E element); 替换(返回之前的元素)
String yuanlai2=list.set(1, "aa");
System.out.println("被替换的是:"+yuanlai2); //输出字符串必须要用"+"符号
System.out.println(list); //[a, aa, woaini, d, a]

//public E get(int index); 返回
String zhiding=list.get(4); //5就会导致"java.lang.IndexOutOfBoundsException"异常
System.out.println("指定的是:"+zhiding); //指定的是:a

}
}

代码结果如下:
[a, b, c, d, a]
[a, b, c, woaini, d, a]
被移除的是:c
[a, b, woaini, d, a]
被替换的是:b
[a, aa, woaini, d, a]
指定的是:a


二、ArrayList集合(实现类)
  它的方法和List定义的基本一致(基本被用于接口的实现类)!


三、LinkedList集合
  LinkedList集合的底层结构是链表结构,方便元素的增、删、添、首尾操作

方法:

  1. 除了和List接口中的方法(继承)+特有的方法;
  2. 特有(首尾操作)的方法:
    第一组:
    void addFirst(E e);
    void addLast(E e);
    第二组(返回移除的元素):
    E removeFirst();
    E removeLast();
    第三组(返回特定的元素):
    E getFirst();
    E getLast();
    第四组:
    E pop(); //弹出,删除集合中的第一个元素
    void push(E 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
public class Main extends Object{
public static void main(String[] args) {
LinkedList<String> list=new LinkedList<String>();

//使用父类的添加方法
list.add("123");
list.add("WWW");
list.add("12SW");
System.out.println(list); //[123, WWW, 12SW]
System.out.println("!!!!!!!!!!!");

//使用LinkedList的特定方法添加
list.addFirst("ASD");
list.addFirst("AHHAHAHA"); //[AHHAHAHA, ASD, 123, WWW, 12SW] 会不断地当第一个!!
System.out.println(list); //[AHHAHAHA, ASD, 123, WWW, 12SW]
System.out.println("!!!!!!!!!!!");

//删除元素
String shanchu=list.removeFirst(); //删除第一个AHHAHAHA
System.out.println(shanchu);
System.out.println(list); //[ASD, 123, WWW, 12SW]
System.out.println("!!!!!!!!!!!");

//获取元素
String get=list.getLast(); //获取最后一个元素
System.out.println(get); //12SW
System.out.println(list);
System.out.println("!!!!!!!!!!!");

//pop弹出
String pop=list.pop(); //弹出第一个元素
System.out.println(pop); //ASD
System.out.println(list);
System.out.println("!!!!!!!!!!!");

//push推入
list.push("MAMMAMAM");
System.out.println(list); //[MAMMAMAM, 123, WWW, 12SW]
System.out.println("!!!!!!!!!!!");

}
}

代码结果如下:
添加了三个元素:
[123, WWW, 12SW]
!!!!!!!!!!!

通过addFirst添加了第一个元素
[AHHAHAHA, ASD, 123, WWW, 12SW]
!!!!!!!!!!!

通过removeFirst第一个元素
AHHAHAHA
[ASD, 123, WWW, 12SW]
!!!!!!!!!!!

通过getLast获取最后一个元素
12SW
[ASD, 123, WWW, 12SW]
!!!!!!!!!!!

通过pop弹出第一个元素
ASD
[123, WWW, 12SW]
!!!!!!!!!!!

通过push推入第一个元
[MAMMAMAM, 123, WWW, 12SW]
!!!!!!!!!!!


四、Vector
  jdk1.2(现在是1.9)之后被ArrayList类取代。

Set集合

一、Set集合的特点:

  1. java.util.Set接口 extends Collection接口
  2. 不允许存储重复的元素
  3. 没有索引,没有带索引的方法,也不能使用普通的for循环。(和Collection接口方法一样)

二、java.util.HashSet<E>

  1. java.util.HashSet集合 implements Set接口
  2. 不允许存储重复的元素
  3. 没有索引,没有带索引的方法,必须使用增强for循环。(和Collection接口方法一样)
  4. 是一个无序的集合(存储元素和取出元素的顺序可能不同)
  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
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Set<Integer> set=new HashSet<>(); //生成一个set集合的对象
//使用add方法 //和Collection接口方法一样
set.add(1);
set.add(2);
set.add(3);
set.add(1);

//使用迭代器;
Iterator<Integer> set2=set.iterator();
while(set2.hasNext())
{
int s=set2.next();
System.out.println(s);
}

System.out.println("!!!!!!!!!!!"); //分隔符,比较和增强for循环的区别

//增强for循环
for(int i:set)
{
System.out.println(i); //set为上面set集合的对象
}

}
}

结果分析
1
2
3
!!!!!!!!!!!
1
2
3
(没有出现第四个重复的元素1!!!)


三、HashSet集合存储数据的结构(哈希表)
  哈希值:一个十进制的整数,由系统随机给出(对象的地址值,是一个逻辑地址,是模拟出来的地址,不是数据实际存储的物理地址)。
  在Object类有一个方法可以获取对象的哈希值:hashCode();

hashCode方法的源码:
public native int hashCode();
native:代表该方法调用的是本地操作系统的方法。

1
2
3
4
5
6
7
8
9
10
11
public class Main extends Object{  //写继承Object类更加明显看出是Object类的方法
public static void main(String[] args) {
Main i=new Main();
int a=i.hashCode(); //调用方法
System.out.println(a); //2018699554(逻辑地址)

Main j=new Main();
int b=j.hashCode(); //调用方法
System.out.println(b); //1311053135(逻辑地址)
}
}

toString方法的源码:
return getClass().getName()+”@”+Integer.toHexString(hashCode());  输出为“类名@十六进制数字”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main extends Object {
public static void main(String[] args) {
Main i=new Main();
int a=i.hashCode();
System.out.println(a); //2018699554

Main j=new Main();
int b=j.hashCode(); //1311053135
System.out.println(b);

/*toString方法的源码:
return getClass().getName()+"@"+Integer.toHexString(hashCode()); //“类名@十六进制数字”
*/
System.out.println(i); //Main@7852e922
System.out.println(j); //Main@4e25154f

}
}

四、哈希表
jdk1.8版本之
  哈希表=数组+链表
jdk1.8版本之
  哈希表=数组+链表
  哈希表+数组+红黑树(提高查询速度)
数组结构相同哈希值的元素分为一组
链表结构//红黑树相同哈希值的元素连接一起

步骤:

  1. 将数据存储到集合中,先计算元素的哈希值。
  2. 然后按照哈希值将其放入不同的数组中,相同的就连接在一起。
  3. 如果连接的元素>=8 —-链表->红黑树(一层红色结点,一层黑色结点)


五、Set集合存储元素不重复的原理

举例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;
public class Main extends Object{
public static void main(String[] args) {
HashSet<String> set=new HashSet<>();
String s1=new String("abc");
String s2=new String("abc");
set.add(s1); //会调用元素的hashCode方法和equals方法判断是否重复
set.add(s2);
set.add("重地");
set.add("通话");
set.add("abc");
System.out.println(set); //只输出 [重地, 通话, abc]
}
}

结果分析:
set.add(s1);  
  add方法调用s1的hashCode方法 -> 计算字符串”abc”的哈希值(96354) -> 在集合中找是否有96354这个哈希值的元素 -> 没有就把s1存储到集合中

set.add(s2); 
  add方法调用s2的hashCode方法 -> 计算字符串”abc”的哈希值(96354) -> 在集合中找是否有96354这个哈希值的元素 -> 有就是哈希冲突(值相同,元素不同) -> 调用s2.equals(s1)返回true  -> 不会将s2存储到集合中

set.add("重地");
  add方法调用”重地”的hashCode方法 -> 计算字符串”重地”的哈希值(1179395) -> 在集合中找是否有1179395这个哈希值的元素 -> 没有就把”重地”存储到集合中

set.add("通话");
  add方法调用”通话”的hashCode方法 -> 计算字符串”通话”的哈希值(1179395) -> 在集合中找是否有1179395这个哈希值的元素 -> 有就是哈希冲突(值相同,元素不同) -> “通话”.equals(“重地”)返回false -> 将”通话”存储到集合中


六、HashSet存储自定义类型元素

必须重写HashSet()和equals()方法。


七、LinkedHashSet<E>
LinkedHashSet集合(具有可预知的迭代顺序) extends HashSet集合(具有可预知的迭代顺序)

  1. 底层实现是一个哈希表结构(查询速度非常快)
  2. 哈希表=数组+链表/红黑树+链表(记录元素的存储顺序)

例子:

1
2
3
4
5
6
7
8
9
10
11
import java.util.*;
public class Main extends Object{
public static void main(String[] args) {
LinkedHashSet<String> set=new LinkedHashSet<>();
set.add("www");
set.add("abc");
set.add("abc");
set.add("itcast");
System.out.println(set); //输出[www, abc, itcast]
}
}

正则表达式(regex)

一、正则表达式(所有编程语言支持)
  正则表达式:是一个字符串(“正则表达式内容”)

  • 普通字符串内容只是内容,而正则表达式的内容是规则
  • 正则表达式用来匹配普通字符串 (boolean b=”普通字符串” 匹配”正则表达式” )
  • 代码实现:

String类中:
  public boolean matches(String regex);
boolean b=”普通字符串”.matches(“正则表达式”);

  • 练习校验qq号码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {
public static void main(String[] args) {
qq();
}

/*QQ号码满足的规则:
*1.必须是0-9的数字
*2.开头必须是1-9的数字(没有0)
*3.位数必须是5-12位
*/
public static void qq()
{
String qq="3457437467"; //普通字符串
String regex=("[1-9][0-9]{4,11}"); //正则表达式 []表示一位的范围,{X,Y}表示从x到y位的数字范围。
boolean b=qq.matches(regex); //使用matches方法
System.out.println(b);
}
}
  • 代码实现:

String类中:
  public String[] split(String regex);

  • 切割电话:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Main {
public static void main(String[] args) {
split01();
}

public static void split01() {
String phone= "2345--4564----6546----------1345";
String[] phones=phone.split("-+"); //表示多个-字符。
for(int i=0;i<phones.length;i++)
{
System.out.println(phones[i]);
}
}

}

注意事项:

  1. “.”在正则表达式中表示任意字符
  2. “+”在正则表达式中表示连续的多个字符

集合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));
}
}


}
}

代码结果如下:


,