发表于 | 分类于 ，

　　最近做笔试题碰到了一道经典的算法题：旅行者过桥问题。想起之前在笔试的过程中也碰到了这道题，于是决定整理一下。

问题

　　在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。假设N <= 1000。

思路

　　拿到此题的第一个想法肯定是贪心，但整个贪心的具体过程确并不简单。设最快的两个人过桥所需的时间为A、B，最慢的两个人过桥所需的时间为X、Y。首先需要明白的是肯定要桥对面的过桥所需时间最小的人送电筒回来。我们考虑首先让最慢的两个人过桥，而让最慢的两个人过桥有两种情况。
　　情况一：让最快的人（A）送最慢的两个人过桥：首先让A与Y过桥，过桥所需时间为Y；然后让A送电筒回来，所需时间为A；然后让A与X过桥，所需时间为X；然后让A送电筒回来。此时X与Y都过了桥，所需总时长为：Y+A+X+A=2A+X+Y。
　　情况二：让最快的两个人（A和B）送最慢的两个人过桥：首先A与B过桥，所需时间为B；然后A送电筒回来，所需时间为A；然后让X和Y一起过桥，所需时间为Y；然后让B送电筒回来，所需时间为B。此时X与Y都过了桥，所需总时长为：B+A+Y+B=2B+Y。
　　在让最慢的两个人过桥的过程中，我们要取这两种情况的最小值计算。
　　同时边界情况为：只有三个时，总时长为三者时长之和；只有两个人时，总时长为用时较多的人的时长；只有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
package com.wh.problems.huya;

import java.util.Arrays;
import java.util.Scanner;

public class Bridge {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] time = new int[n];
		for(int i = 0;i < n;i++) {
			time[i] = sc.nextInt();
		}
		Arrays.sort(time);
		int minTime = 0;
		int i = n-1;
		for(;i > 2;i -= 2) {
			minTime += Math.min(2*time[0]+time[i-1]+time[i], time[0]+2*time[1]+time[i]);
		}
		if (i == 2) {
			minTime += time[0]+time[1]+time[2];
		}else if (i==1) {
			minTime += time[1];
		}else {
			minTime += time[0];
		}
		System.out.println(minTime);
	}
}

参考链接

https://www.jianshu.com/p/84608db757b4

发表于 | 分类于 ，

一、预备知识

　　了解红黑树之前，我们需要明白何为二叉查找树，何为平衡二叉查找树，何为左旋、右旋和双旋。
下面给出左旋、右旋和双旋转的简单示意图：
左旋：
　　当平衡二叉树中插入节点后，右子树的高度与左子树的高度之差大于2，则需进行左旋。
图示：
　　
右旋：
　　当平衡二叉树中插入节点后，左子树的高度与右子树的高度之差大于2，则需进行右旋。
图示：

双旋转：
　　拿左旋情况来说，如果当前根结点的右子树的左子树的高度大于右子树，则在需要先对根结点的右子树进行右旋转，再整体左旋。

代码实现：
GitHub

二、红黑树

1.概念
红黑树同样是平衡二叉查找树，只是其实现平衡的算法不同，且不满足绝对平衡。其插入删除涉及到旋转的操作更少。
红黑树在结点中增加了一个存储位用来存储颜色，可以是RED或者BLACK，通过颜色及性质的约束，其可以保证它的最长路径不超过最短路径的二倍。

2.性质

  • 每个节点颜色不是黑色就是红色
  • 根结点是黑色的
  • 如果一个结点是红色，那么它的子节点必定是黑色。（也就是没有连续的红结点）
  • 每个叶子结点都是黑色
  • 任意结点到每个叶子结点的路径都包含数量相同的黑节点。

3.插入操作
插入操作首先需要定位插入的位置，然后通过旋转、染色的操作实现自平衡。查找插入的位置并不难。
找到插入的位置后，我们需要明白插入的结点必定为红色（如果为黑色，黑色平衡被打破，很难处理）。
插入操作分为很多种情况，但整体上可分为三种：不需要处理、

不需要处理的情况：

  • 红黑树为空树：直接把插入节点设为根结点，并且将其颜色染为黑色。
  • 插入结点的父节点为黑结点：直接插入
  • 插入结点已存在：把插入结点的颜色设为当前结点的颜色，更新当前结点的值为插入结点的值。

插入结点的父结点为红结点：
首先我们要明白如果父结点为红结点，那么该父结点肯定不是根结点，也就是说待插入结点肯定存在祖父结点，且祖父结点肯定为黑色。
根据待插入结点的叔叔结点的不同情况，可分为如下几种情况：
1）叔叔结点存在且为红色
这种情形的处理办法为：将祖父结点PP染红，父结点和叔叔染黑，使其变为红黑黑的结构。如下图所示：


进行此操作后，如果祖父结点的父结点为黑色，则不需再进行进一步操作。如果祖父结点的父结点为红色，则还需把祖父结点当做新插入的结点左自平衡处理，直到平衡为止。
也就是说红黑树的生长是自底向上的。
如果祖父结点刚好为根结点，则需要把祖父结点染黑。这是唯一会增加红黑树黑色结点层数的情况。

2）叔叔结点不存在或为黑结点，父结点是祖父结点的左子结点

  • 插入结点是其父结点的左子结点：进行右旋
    具体步骤为：将P染为黑色，PP染为红色，右旋。
  • 插入结点是其父结点的右子结点：对P左旋使其转换为上一情形

3）叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点。
此情况与情况2）相反。

参考

https://blog.csdn.net/tanrui519521/article/details/80980135
https://blog.csdn.net/qq_37934101/article/details/81160254
https://www.jianshu.com/p/e136ec79235c

发表于 | 分类于 ，

什么是工厂设计模式？

　　工厂设计模式就是用来生产对象的，它使用一个单独的类来生产对象，而不是让调用者直接使用new来创建对象。

优缺点

　　工厂设计模式使得创建对象的逻辑不会暴露，并且其最大的优点便是使得程序员与对象进行解耦。
　　其主要缺点为没增加一个产品，就要增加对应的实现类和对象实现工厂，增加了系统复杂度。

分类

　　1.简单工厂
　　2.抽象工厂

简单工厂

创建产品接口：

1
2
3
public interface Shape {
	void draw();
}

创建产品实现类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Rectangle implements Shape{
	@Override
	public void draw() {
		System.out.println("draw Rectangle");
	}
}
public class Square implements Shape{
	@Override
	public void draw() {
		System.out.println("draw square");
	}
}
public class Circle implements Shape{
	@Override
	public void draw() {
		System.out.println("draw Circle");
	}
}

创建工厂类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class ShapeFactory {
	public Shape getShape(String shapeType) {
		if (shapeType == null) {
			return null;
		}else if (shapeType.equalsIgnoreCase("rectangle")) {
			return new Rectangle();
		}else if (shapeType.equalsIgnoreCase("square")) {
			return new Square();
		}else if (shapeType.equalsIgnoreCase("circle")) {
			return new Circle();
		}
		return null;
	}
}

测试：

1
2
3
4
5
6
7
public class Test {
	public static void main(String[] args) {
		ShapeFactory shapeFactory = new ShapeFactory();
		Shape rect = shapeFactory.getShape("rectangle");
		rect.draw();
	}
}

应用场景

抽象工厂

　　与简单工厂模式不同的是，抽象工厂模式多出了一个超级工厂（工厂接口），围绕超级工厂类，创建其他工厂类，再围绕工厂类，创建实体类。
　　抽象工厂可以生产一组相关（不止一类）的产品。
创建产品1接口及实现类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Cpu {
	void run();
	class Cpu6 implements Cpu{
		@Override
		public void run() {
			System.out.println("Cpu6");
		}
	}
	class Cpu8 implements Cpu{
		@Override
		public void run() {
			System.out.println("Cpu8");
		}
	}
}

创建产品2接口及实现类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Screen {
	void size();
	class Screen5 implements Screen{
		@Override
		public void size() {
			System.out.println("5寸");
		}
	}
	class Screen6 implements Screen{
		@Override
		public void size() {
			System.out.println("6寸");
		}
	}
}

超级工厂：

1
2
3
4
public interface PhoneFactory {
	Cpu getCpu();
	Screen getScreen();
}

A工厂：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class APhoneFactory implements PhoneFactory{

	@Override
	public Cpu getCpu() {
		return new Cpu.Cpu6();
	}

	@Override
	public Screen getScreen() {
		// TODO Auto-generated method stub
		return new Screen.Screen5();
	}
	
}

B工厂

1
2
3
4
5
6
7
8
9
10
11
12
13
public class BPhoneFactory implements PhoneFactory{

	@Override
	public Cpu getCpu() {
		return new Cpu.Cpu8();
	}

	@Override
	public Screen getScreen() {
		return new Screen.Screen6();
	}

}

参考：

https://www.runoob.com/design-pattern/factory-pattern.html
https://www.jianshu.com/p/38493eb4ffbd
https://xin-tan.com

发表于 | 分类于 ，

　　从学习MySQL开始join的用法都一直弄地不是很清楚，今天重新梳理一遍。

建表

　　建立老师表（teacher）与学生表（student），一个老师对应多个学生。使用tid做外键。

1
2
3
4
5
6
7
8
9
CREATE TABLE `student` (
  `id` int(3) NOT NULL AUTO_INCREMENT,
  `name` varchar(10) NOT NULL,
  `age` int(3) NOT NULL,
  `tid` int(3) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `tid` (`tid`),
  CONSTRAINT `student_ibfk_1` FOREIGN KEY (`tid`) REFERENCES `teacher` (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
1
2
3
4
5
CREATE TABLE `teacher` (
  `id` int(3) NOT NULL AUTO_INCREMENT,
  `name` varchar(3) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

　　插入数据：

SELECT语句顺序

　　首先复习一下SELECT语句的编写顺序：

1
select(distinct) from join on where group by having union order by limit

CROSS JOIN（笛卡尔积）

　　笛卡尔积会将两个表强行凭借，不管两表是否有对应关系。也就是说如果A表有m条记录，B表有n条记录，则执行CROSS JOIN后会查出m*n条记录。

1
SELECT * FROM student (CROSS JOIN) teacher
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
id  name    age tid id  name(1)
1	张三	18	2	1	李老师
1	张三	18	2	2	张老师
1	张三	18	2	3	王老师
1	张三	18	2	4	魏老师
1	张三	18	2	5	杜老师
1	张三	18	2	6	石老师
2	李四	19	3	1	李老师
2	李四	19	3	2	张老师
2	李四	19	3	3	王老师
2	李四	19	3	4	魏老师
2	李四	19	3	5	杜老师
2	李四	19	3	6	石老师
3	王五	20	1	1	李老师
3	王五	20	1	2	张老师
3	王五	20	1	3	王老师
3	王五	20	1	4	魏老师
3	王五	20	1	5	杜老师
3	王五	20	1	6	石老师
4	小明	17	4	1	李老师
4	小明	17	4	2	张老师
4	小明	17	4	3	王老师
4	小明	17	4	4	魏老师
4	小明	17	4	5	杜老师
4	小明	17	4	6	石老师
5	李力	16		1	李老师
5	李力	16		2	张老师
5	李力	16		3	王老师
5	李力	16		4	魏老师
5	李力	16		5	杜老师
5	李力	16		6	石老师
6	杜四	20		1	李老师
6	杜四	20		2	张老师
6	杜四	20		3	王老师
6	杜四	20		4	魏老师
6	杜四	20		5	杜老师
6	杜四	20		6	石老师

七种JOIN理论

左外连接


　　左外连接：LEFT (OUTER) JOIN，其中OUTER可以省略，是外连接的一种。左外连接会将左边的记录全部显示出来，右表只显示符合条件的记录，右表记录不足
的地方均为空。

1
SELECT * FROM student s LEFT JOIN teacher t ON s.tid = t.id;

　　执行结果：

1
2
3
4
5
6
7
id  name    age tid id  name(1)
1	张三	18	2	2	张老师
2	李四	19	3	3	王老师
3	王五	20	1	1	李老师
4	小明	17	4	4	魏老师
5	李力	16			
6	杜四	20

右外连接


　　right (outer) join,与左外连接相反，右外连接会将右表所有记录显示出来，左表只显示符合条件的记录。

1
SELECT * FROM student s RIGHT JOIN teacher t ON s.tid = t.id

　　执行结果：

1
2
3
4
5
6
7
id  name    age tid id  name(1)
3	王五	20	1	1	李老师
1	张三	18	2	2	张老师
2	李四	19	3	3	王老师
4	小明	17	4	4	魏老师
				    5	杜老师
				    6	石老师

左连接


　　左连接即左表独有的部分。需要在左外连接的基础上加where语句实现。

1
SELECT * FROM student s LEFT JOIN teacher t ON s.tid=t.id WHERE t.id IS NULL;
1
2
3
id  name    age tid id  name(1)
5	李力	16			
6	杜四	20

右连接


　　与左连接相反，右连接即为右表独有的部分。需要在右外连接的基础上加上where语句实现。

1
SELECT * FROM student s RIGHT JOIN teacher t ON s.tid=t.id WHERE s.id IS NULL;
1
2
3
id  name    age tid id  name(1)
				    5	杜老师
				    6	石老师

内连接


　　inner join on，返回符合条件的记录，即返回图中交集。

1
SELECT * FROM student s INNER JOIN teacher t ON s.tid = t.id;
1
2
3
4
5
id  name    age tid id  name(1)
3	王五	20	1	1	李老师
1	张三	18	2	2	张老师
2	李四	19	3	3	王老师
4	小明	17	4	4	魏老师

全连接


　　MySQL不提供全连接的关键字，但可通过union联合去重的特性模拟，即联合左外连接与右外连接。

1
2
SELECT * FROM student s LEFT JOIN teacher t ON s.tid=t.id UNION
SELECT * FROM student s RIGHT JOIN teacher t ON s.tid=t.id;
1
2
3
4
5
6
7
8
9
id  name    age tid id  name(1)
1	张三	18	2	2	张老师
2	李四	19	3	3	王老师
3	王五	20	1	1	李老师
4	小明	17	4	4	魏老师
5	李力	16			
6	杜四	20			
				    5	杜老师
				    6	石老师

差集：


　　差集即两表全连接去除重合部分，可以利用union联合左连接右连接实现。

1
2
3
SELECT * FROM student s LEFT JOIN teacher t ON s.tid=t.id WHERE t.id IS NULL
UNION
SELECT * FROM student s RIGHT JOIN teacher t ON s.tid=t.id WHERE s.id IS NULL;SELECT * FROM student s RIGHT JOIN teacher t ON s.tid=t.id WHERE s.id IS NULL;
1
2
3
4
5
id  name    age tid id  name(1)
5	李力	16			
6	杜四	20			
				    5	杜老师
				    6	石老师

参考：

https://www.cnblogs.com/fudashi/p/7491039.html
https://blog.csdn.net/plg17/article/details/78758593

注：文中表格中的空格均表示null

发表于 | 分类于 ，

一、基本概念：

　　线程同步：
　　线程安全：当多个线程访问某个类时，这个类都始终能表现出正确的行为，那么就称这个类是线程安全的。
　　线程与进程：

二、线程创建

　　三种方式

三、线程状态

　　五种状态

四、线程控制基本方法

　　阻塞线程的方法：
　　　　join():合并线程，当前线程会等待调用该方法的线程执行完毕后才会执行
　　　　sleep():使线程进入阻塞状态，但是不会交出锁。由于线程进入了阻塞态，即使没有其他等待执行的线程，该线程也不会获得执行。
　　　　yield():使线程进入就绪态，该方法也不会交出锁。但由于线程是进入了就绪态，如果当前没有其他执行的线程，则该线程会获得执行。
wait():
notify():

一、synchronized

　　1.synchronized锁的是对象。
　　　　对于代码块，synchronized(o){}锁的是括号中的对象，可以使用this锁住当前对象
　　　　对于普通方法上加synchronized关键字，锁的是该方法所在的对象，也即相当于使用synchronized(this){}
　　　　对于静态方法上加synchronized关键字，锁的是类对象。
细粒度、粗粒度？？？
　　2.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
public class Syn1 implements Runnable{
	int count = 0;
	@Override
	public void run() {
		for(int i = 0;i < 1000;i++) {
			count++;
		}
		System.out.println(Thread.currentThread().getName()+"线程执行结束");
	}
	public static void main(String[] args) {
		Syn1 s1 = new Syn1();
		new Thread(s1).start();
		new Thread(s1).start();
		new Thread(s1).start();
		new Thread(s1).start();
		new Thread(s1).start();
		try {
			Thread.sleep(3000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println(s1.count);
	}
}

　　　　执行结果：

　　　　分析原因：
　　　　　　从Java的内存模型角度分析，各个线程拥有自己的工作区，对象存在于主存。线程工作时需要从主存中拷贝对象数据的副本，修改完成后再写入主存。
　　　　如果代码中一个线程拿到了主存中的数据100，但还没有修改，此时再发生线程切换，另一个线程也拿到了主存中的数据100，一个线程修改完成后将101
　　　　写入主存，另一个线程修改完成后同样是101，写入主存。如此一来主存中本应该变成102的数据确变成了101，数据出现了错误。即count++并不是一个原子操作。
　　　　
　　　　加入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
public class Syn1 implements Runnable{
	int count = 0;
	@Override
	public void run() {
		for(int i = 0;i < 1000;i++) {
			synchronized (this) {
				count++;
			}
		}
		System.out.println(Thread.currentThread().getName()+"线程执行结束");
	}
	public static void main(String[] args) {
		Syn1 s1 = new Syn1();
		new Thread(s1).start();
		new Thread(s1).start();
		new Thread(s1).start();
		new Thread(s1).start();
		new Thread(s1).start();
		try {
			Thread.sleep(1000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println(s1.count);
	}
}

　　3.synchronized使用常见问题
　　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
public class Syn2 {
	public synchronized void m1() {
		System.out.println(Thread.currentThread().getName() + "m1 start");
		try {
			Thread.sleep(10000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println(Thread.currentThread().getName() + "m1 end");
	}
	public void m2() {
		try {
			Thread.sleep(5000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println(Thread.currentThread().getName() + "m2");
	}
	public static void main(String[] args) {
		Syn2 s = new Syn2();
		new Thread(()->s.m1(),"t1").start();
		new Thread(()->s.m2(),"t2").start();
	}
}

　　　　运行结果：

1
2
3
t1m1 start
t2m2
t1m1 end

　　　　可见m1获得锁之后，m2仍然能正常执行。

　　2）如果只在写方法上加锁，在读方法上不加锁，则容易产生脏读的现象（读取未提交数据）
　　　　如果在写的数据提交前后各读取一次，则可能读取的数据
　　
　　3）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
public class Syn4 {
	public synchronized void m1() {
		System.out.println("m1 start");
		try {
			Thread.sleep(2000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		m2();
	}
	public synchronized void m2() {
		System.out.println("m2 start");
		try {
			Thread.sleep(2000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println("m2 end");
	}
	public static void main(String[] args) {
		new Syn4().m1();
	}
}

　　4）程序执行过程中，如果同步代码块中出现异常，锁会被释放

　　5）synchronized粒度问题
　　　　在保证线程安全的前提下，应尽量缩小synchronized代码块的范围，这样可以提高并发。

　　

　　7）锁锁定某对象o，如果o的属性发生了改变，不会影响锁的使用，如果对象o变成了另外一个对象，则锁状态改变，原本抢到的锁作废，线程会去抢新锁。
　　如下列代码，执行s.o = new Object();后，t1仍然锁住的是旧对象，而t2则抢到了新对象的锁，因此两个线程都获得了各种的锁，因而都可以执行了。

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 Syn5 {
	Object o = new Object();
	public void m1() {
		synchronized (o) {
			while(true) {
				try {
					Thread.sleep(1000);
				} catch (InterruptedException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				System.out.println(Thread.currentThread().getName());
			}
		}
	}
	public static void main(String[] args) {
		Syn5 s = new Syn5();
		Thread t1 = new Thread(()->s.m1(),"t1");
		t1.start();
		try {
			Thread.sleep(2000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Thread t2 = new Thread(()->s.m1(),"t2");
		s.o = new Object();
		t2.start();
		try {
			Thread.sleep(2000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

二、volatile

　　1.volatile的可见性
　　　　在多线程的环境中，当一个线程修改了主存中的某个数据的值，另一个线程不一定会马上知道，也就是并不一定马上会从主存中更新该数据的值（特别是
在改线程所在的cpu特别忙的情况下）。而对变量使用volatile关键字则会保证所有线程都会读到变量的修改值。
　　　　例如在以下程序中如果不加入volatile关键字，程序会一直执行下去，即使在主线程中running变量被修改为了false，但此时另一个线程并不会更新
running变量。而加了volatile关键字后，线程中的running变量会强制更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Volatile1 {
	volatile boolean running = true;
	public void m1() {
		System.out.println("m1 start");
		while(running) {}
		System.out.println("m2 end");
	}
	public static void main(String[] args) {
		Volatile1 v = new Volatile1();
		new Thread(()->v.m1()).start();;
		try {
			Thread.sleep(1000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		v.running = false;
	}
}

　　2.volatile不可保证原子性
　　　　对应count++问题，volatile并不能保证count的正确性。

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
public class Volatile2 implements Runnable{
	volatile int count = 0;
	public void run() {
		for(int i = 0;i < 1000;i++) {
			count++;
		}
	}
	public static void main(String[] args) {
		Volatile2 v = new Volatile2();
		Thread t1 = new Thread(v);
		Thread t2 = new Thread(v);
		Thread t3 = new Thread(v);
		Thread t4 = new Thread(v);
		Thread t5 = new Thread(v);
		t1.start();
		t2.start();
		t3.start();
		t4.start();
		t5.start();
		try {
			t1.join();
			t2.join();
			t3.join();
			t4.join();
			t5.join();			
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.out.println(v.count);
	}
}

　　synchronized与volatile对比

三、AtomXXX类

　　AtomXXX类是一类在java.util.concurrent下封装好的类，其方法本身就具有原子性，且其效率比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
public class Atom1 implements Runnable{
	AtomicInteger count = new AtomicInteger(0);
	@Override
	public void run() {
		for(int i = 0;i < 1000;i++) {
			count.incrementAndGet();
		}
		
	}
	public static void main(String[] args) {
		Atom1 a = new Atom1();
		List<Thread> list = new ArrayList<>();
		for(int i = 0;i < 5;i++) {
			list.add(new Thread(a));
		}
		list.forEach((o)->o.start());
		list.forEach((o)->{
			try {
				o.join();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		});
		System.out.println(a.count);
	}
}

四、死锁

　　当多个线程各自锁定一个资源等待对方锁定的资源时会发生死锁，典型的有哲学家进餐问题。
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
58
59
60
61
62
63
64
65
66
public class DeadLock {
	public static String obj1 = "obj1";
	public static String obj2 = "obj2";
	public static void main(String[] args) {
		MyThread1 thread1 = new MyThread1();
		MyThread2 thread2 = new MyThread2();
		new Thread(thread1).start();
		new Thread(thread2).start();
	}
}
class MyThread1 implements Runnable{

	@Override
	public void run() {
		System.out.println(new Date().toString()+"thread1开始执行");
		while(true) {
			synchronized(DeadLock.obj1) {
				System.out.println("t1获得obj1");
				try {
					Thread.sleep(2000);
				} catch (InterruptedException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				synchronized(DeadLock.obj2) {
					try {
						Thread.sleep(2000);
					} catch (InterruptedException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
					System.out.println("t1获得obj2");
				}
			}
		}
	}
	
}
class MyThread2 implements Runnable{

	@Override
	public void run() {
		System.out.println(new Date().toString()+"thread2开始执行");
		while(true) {
			synchronized(DeadLock.obj2) {
				System.out.println("t2获得obj2");
				try {
					Thread.sleep(2000);
				} catch (InterruptedException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				synchronized(DeadLock.obj1) {
					try {
						Thread.sleep(2000);
					} catch (InterruptedException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
					System.out.println("t2获得obj1");
				}
			}
		}
	}
	
}

2.死锁避免：

  • 保持获取锁的顺序一致
  • 尽量使用开放调用
  • 使用定时锁

3.死锁诊断
　　可通过JVM的线程转储信息来分析死锁。

4.其他活跃性危险
　　饥饿：当线程由于无法访问它所需要的资源而不能继续执行时，就发生了饥饿。常见的有线程优先级使用不当，优先级低的线程始终得不到CPU的执行时会导致该线程饥饿。我们应该尽量保持各线程优先级相同。

　　思考角度：
　　　　内存角度
　　　　线程重入
　　　　延迟角度
　　　　线程调度异步性

发表于 | 分类于 ，

图简介：

　　图的表示方式：
　　　　邻接矩阵
　　　　邻接表
　　图的代码实现：

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
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Graph {
	// 存储定点集合
	private ArrayList<String> vertexList;
	// 存储图对应的邻接矩阵
	private int[][] edges;
	// 表示边的数目
	private int numOfEdges;
	// 标记结点是否被访问过
	private boolean[] isVisited;
	// 构造器
	public Graph(int n) {
		vertexList = new ArrayList<>(n);
		edges = new int[n][n];
		numOfEdges = 0;
		isVisited = new boolean[n];
	}
	
	// 插入节点
	public void insertVertex(String vertex) {
		vertexList.add(vertex);
	}
	// 添加边
	public void insertEdge(int v1,int v2,int weight) {
		edges[v1][v2] = weight;
		edges[v1][v2] = weight;
		numOfEdges++;
	}
	// 得到第一个邻接结点的下标w
	public int getFirstNeighbor(int index) {
		for(int j = 0;j < vertexList.size();j++) {
			if (edges[index][j] > 0) {
				return j;
			}
		}
		return -1;
	}
	// 根据前一个邻接结点的下标来获取下一个邻接结点
	public int getNextNeighbor(int v1,int v2) {
		for(int j = v2+1;j < vertexList.size();j++) {
			if (edges[v1][j] > 0) {
				return j;
			}
		}
		return -1;
	}
}

深度优先搜索（DFS）：

　　深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接
结点作为初始结点，访问它的第一个邻接结点。可以理解为：每次都在访问完当前结点后首先访问当前结点的第一个结点。
　　很明显，深度优先遍历是一个递归的过程。

算法步骤：

　　1.访问初始结点v，并标记结点v为已访问
　　2.查找v的第一个邻接结点w
　　3.若w存在，则继续执行4，如果w不存在，则回到第一步，将从v的下一个节点继续。
　　4.若w未被访问，对w进行深度优先遍历递归
　　5.查找节点v的w邻接结点的下一个邻接结点，转到步骤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
private void dfs(boolean[] isVisited,int i) {
	// 首先输出初始结点
	System.out.print(vertexList.get(i) + " ");
	// 将结点设置为已访问
	isVisited[i] = true;
	// 查找结点i的第一个邻接结点
	int w = getFirstNeighbor(i);
	while(w != -1) {
		if (!isVisited[w]) {
			dfs(isVisited, w);
		}
		w = getNextNeighbor(i, w);
	}
	
}

// 对dfs进行一个重载，遍历我们所有的结点，并进行dfs
public void dfs() {
	// 遍历所有的结点，进行dfs(回溯)
	for(int i = 0;i < vertexList.size();i++) {
		if (!isVisited[i]) {
			dfs(isVisited,i);
		}
	}
}

广度优先搜索（BFS）

　　图的广度优先搜索类似于树的层序遍历，即访问初始结点后，再依次访问初始结点的邻接结点，当前结点的所有邻接结点访问完成之后，再访问第一个邻接
结点的所有结点，以此类推。

算法算法步骤

　　1.访问初始结点v并标记为已访问
　　2.结点v入队列
　　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
// bfs
private void bfs(boolean[] isVisited,int i) {
	int u; // 表示队列头结点
	int w; // 表示邻接结点
	Queue<Integer> queue = new LinkedList<>();
	System.out.println(vertexList.get(i));
	isVisited[i] = true;
	queue.add(i);
	while(!queue.isEmpty()) {
		u = queue.poll();
		w = getFirstNeighbor(u);
		while(w != -1) {
			if (!isVisited[w]) {
				System.out.println(vertexList.get(w));
				isVisited[w] = true;
				queue.add(w);
			}
			w = getNextNeighbor(u, w);
		}
	}
}
public void bfs() {
	for(int i = 0;i < vertexList.size();i++) {
		if (!isVisited[i]) {
			bfs(isVisited, i);
		}
	}
}

普里姆算法（Prim）

　　普里姆算法用来求图的最小生成树。该算法的核心思想为贪心。
　　该算法首先从某一起始结点出发，遍历邻接结点，找出最小的边，并把该结点标记为已访问；然后再以这两个结点为起始结点，分别遍历它们的邻接结点，找出最小的边，
并把该结点标记为已访问，以此类推。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Prim {
	public void prim(Graph graph,int v) {
		int[] isVisited = new int[graph.getSize()];
		isVisited[v] = 1;
		// 
		int h1 = -1;
		int h2 = -1;
		int minWeight = 10000;
		for(int k = 1;k < graph.getSize();k++) {
			for(int i = 0;i < graph.getSize();i++) {
				for(int j = 0;j < graph.getSize();j++) {
					if (isVisited[i] == 1 && isVisited[j] == 0 && graph.getWeight(i, j) < minWeight) {
						minWeight = graph.getWeight(i, j);
						h1 = i;
						h2 = j;
					}
				}
			}
			System.out.println("边<"+graph.getByIndex(h1)+","+graph.getByIndex(h2)+">权值："+minWeight);
			isVisited[h2] = 1;
			minWeight = 10000;
		}
	}

克鲁斯卡尔（Kruskal）算法

　　该算法也是用来求最小生成树，该算法同样用到了贪心思想。
　　该算法的实现为：首先要对图的所有边权值进行排序，然后依次从小到大取边组成最小生成树，在取的同时还要进行判断是否构成回路的操作，如果构成了回路则要跳过该条边。
　　注意：判断是否构成回路的算法是理解难点。

代码实现：

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
public class Kruskal {
	public void kruskal(Graph graph) {
		int index = 0;
		int[] ends = new int[graph.getSize()];
		EData[] result = new EData[graph.getSize()-1];
		
		EData[] edges = graph.getEdges();
		System.out.println("图的边的集合"+Arrays.toString(edges));
		graph.sortEdges(edges);
		System.out.println("排序后边的集合："+Arrays.toString(edges));
		for(int i = 0;i < graph.getNumOfedges();i++) {
			int p1 = graph.getPosition(edges[i].start);
			int p2 = graph.getPosition(edges[i].end);
			int m = graph.getEnd(ends, p1);
			int n = graph.getEnd(ends, p2);
			System.out.println("m:"+m+" n:" + n);
			if (m != n) {
				result[index++] = edges[i];
				ends[m] = n;
			}
		}
		System.out.println(Arrays.toString(ends));
		System.out.println("kruskal:"+Arrays.toString(result));
	}
}

迪杰斯特拉（Dijkstra）算法：

　　该算法用来求某一结点到其他结点的最短路径。
　　该算法用到了BFS的思想。它以起始点为中心，向外层层扩展。每次先获取到各结点路径中最短的路径，再在此最短路径基础上更新到其他路径的最短路径。

代码实现：

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 Dijkstra {
	public void dijkstra(Graph graph,int v) {
		int n = graph.getSize();
		// 出发点到各顶点的最短距离
		int[] minPath = new int[n];
		// 各顶点的前驱节点下标
		int[] preNode = new int[n];
		// 是否已找到初始顶点到各顶点的最短路径，0表示未找到，1表示已找到。
		int[] finded = new int[n];
		for(int i = 0;i < n;i++) {
			finded[i] = 0;
			minPath[i] = graph.getWeight(v, i);
			preNode[i] = 0;
		}
		minPath[v] = 0;
		finded[v] = 1;
		int k = 0;
		int min = 10000;
		for(int i = 1;i < n;i++) {
			// 这里为了方便用10000表示无穷大
			min = 10000;
			// 在未找出最小路径的结点中找出路径最小的结点，将其作为初始结点，进行层序遍历，找出最短路径。
			for(int j = 0;j < n;j++) {
				if (finded[j] == 0 && minPath[j] < min) {
					k = j;
					min = minPath[j];
				}
			}
			// 将结点k标记为已找到
			finded[k] = 1;
			for(int j = 0;j < n;j++) {
				if (finded[j] == 0 && (min+graph.getWeight(k, j)) < minPath[j]) {
					minPath[j] = min+graph.getWeight(k, j);
					preNode[j] = k;
				}
			}
		}
		System.out.println(Arrays.toString(minPath));
	}
}

弗洛伊德（Floyd）算法：

　　核心思想：选取中间结点，比较两个结点本身路径长度与经过中间节点的路径的大小，如果经过中间结点的距离更小， 则更新最短路径矩阵和最短路径前驱结点矩阵。 　　

代码实现：

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 Floyd {
	public void floyd(Graph graph) {
		int n = graph.getSize();
		// 最短路径长度矩阵
		int[][] minPath = new int[n][n];
		// 最短路径前驱结点矩阵
		int[][] preNode = new int[n][n];
		// 初始化最短路径长度矩阵和最短路径前驱结点矩阵
		for(int i = 0;i < n;i++) {
			for(int j = 0;j < n;j++) {
				minPath[i][j] = graph.getWeight(i, j);
				preNode[i][j] = j;
			}
		}
		// 核心思想：选取中间结点，比较两个结点本身路径长度与经过中间节点的路径的大小，如果经过中间结点的距离更小，
		// 则更新最短路径矩阵和最短路径前驱结点矩阵。
		for(int k = 0;k < n;k++) {
			for(int i = 0;i < n;i++) {
				for(int j = 0;j < n;j++) {
					if (minPath[i][j] > minPath[i][k] + minPath[k][j]) {
						minPath[i][j] = minPath[i][k] + minPath[k][j];
						preNode[i][j] = k;
					}
				}
			}
		}
		System.out.println("最短路径矩阵：");
		for(int[] link:minPath) {
			System.out.println(Arrays.toString(link));
		}
		System.out.println("最短路径前驱结点矩阵");
		for(int[] link:preNode) {
			System.out.println(Arrays.toString(link));
		}
	}
}

发表于 | 分类于 ，

简介

　　最近在学习操作系统这门课程，在学习的过程中遇到了生产者与消费者模式这个知识。同样的，在以前学习Java多线程编程时也遇到过相同的知识点。这让我
不得不对这个知识点深入的理一理。
　　什么是消费者与生产者模式？在操作系统这门课中，这是一个描述进程之间的问题。系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品
放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。生产者与消费者共享一个初始为空，大小为n的缓冲区。而且两个进程要满足：只有缓冲区没满时，
生产者才能把产品放入缓冲区，否则阻塞等待；同样只有缓冲区不为空时，消费者才能从中取出产品，否则阻塞等待。
　　综上所述，我们必须使这两个进程满足：1.互斥地访问缓冲区；2.两个进程之间保证两个同步关系：缓冲区满时，需要消费者消费后生产者才能生产；缓冲区为
空时，生产者生产后，消费者才能消费。理清了进程之间的关系后，即可利用信号量进制进行实现。
　　而在多线程中的消费者与生产者问题仅仅是将进程换做了线程，实现方式也由操作系统中的原语实现方式该为了Java代码方式实现。

代码实现：

1.synchronized、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
93
94
95
96
97
98
99
public class ProducerConsumerWithWaitNotify {
	public static void main(String[] args) {
		Resource resource = new Resource();
		ProducerThread p1 = new ProducerThread(resource);
		ProducerThread p2 = new ProducerThread(resource);
		ProducerThread p3 = new ProducerThread(resource);
		ConsumerThread c1 = new ConsumerThread(resource);
//		ConsumerThread c2 = new ConsumerThread(resource);
//		ConsumerThread c3 = new ConsumerThread(resource);
		new Thread(p1).start();
		new Thread(p2).start();
		new Thread(p3).start();
		new Thread(c1).start();
//		new Thread(c2).start();
//		new Thread(c3).start();
	}
}

/**
 * 公共资源类
 * @author aaa3
 *
 */
class Resource{
	// 当前缓存区中的初始资源数
	private int num = 0;
	// 当前缓冲区中剩余空间
	private int size = 10;
	// synchronized加锁使得多个线程只能互斥地访问缓存区
	public synchronized void remove() {
		if (num > 0) {
			num--;
			System.out.println("消费者" + Thread.currentThread().getName()+
					"消耗一件资源" + "当前缓冲区还有"+num+"资源");
			// 相当于原语V操作
			notifyAll();
		// 相当于原语P操作
		}else {
			try {
				wait();
				System.out.println("消费者" + Thread.currentThread().getName()+"线程进入等待状态");
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}
	public synchronized void add() {
		if (num < size) {
			num++;
			System.out.println(Thread.currentThread().getName()+"生产一个资源，当前缓冲区有"+num+"个资源");
			notifyAll();
		}else {
			try {
				wait();
				System.out.println(Thread.currentThread().getName()+"线程进入等待状态");
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}
}
class ConsumerThread implements Runnable{
	private Resource resource;
	public ConsumerThread(Resource resource) {
		this.resource = resource;
	}
	@Override
	public void run() {
		while(true) {
			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			resource.remove();
		}
	}
}
class ProducerThread implements Runnable{
	private Resource resource;
	public ProducerThread(Resource resource) {
		this.resource = resource;
	}
	@Override
	public void run() {
		while(true) {
			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			resource.add();;
		}
	}
}

2.阻塞队列BlockingQueue实现方式

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
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class ProducerConsumerWithBlockingQueue {
	public static void main(String[] args) {
		Resource1 resource1 = new Resource1();
		Producer p1 = new Producer(resource1);
		Consumer c1 = new Consumer(resource1);
		Producer p2 = new Producer(resource1);
		Producer p3 = new Producer(resource1);
		Producer p4 = new Producer(resource1);
		Producer p5 = new Producer(resource1);
		new Thread(p1).start();
		new Thread(p2).start();
		new Thread(p3).start();
		new Thread(p4).start();
		new Thread(p5).start();
		new Thread(c1).start();
	}
}
class Producer implements Runnable{
	private Resource1 resource;
	public Producer(Resource1 resource) {
		this.resource = resource;
	}
	@Override
	public void run() {
		while(true) {
			try {
				Thread.sleep(3000);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			resource.add();			
		}
	}
}
class Consumer implements Runnable{
	private Resource1 resource;
	public Consumer(Resource1 resource) {
		this.resource = resource;
	}
	@Override
	public void run() {
		while(true) {
			try {
				Thread.sleep(3000);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			resource.take();			
		}
	}
}
class Resource1{
	private BlockingQueue<Integer> blockingQueue = new LinkedBlockingQueue<>(10);
	public void add() {
		try {
			blockingQueue.put(1);
			System.out.println("生产者"+Thread.currentThread().getName()+
					"生产一件产品，当前资源池有"+blockingQueue.size()+"件产品");
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	public void take() {
		try {
			blockingQueue.take();
			System.out.println("消费者"+Thread.currentThread().getName()+
					"消费一件产品，当前资源池有"+blockingQueue.size()+"件产品");
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

参考链接

《王道操作系统考研》
https://www.cnblogs.com/fankongkong/p/7339848.html

发表于 | 分类于 ，

动态规划概述：

　　动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。它利用各阶段之间的关系，逐个求解，最终求得全局最优解。在设计动态规划算法时，需要确认原问题与子问题、动态规划状态、边界状态值、状态转移方程等关键要素。
　　动态规划与分治算法类似，基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但动态规划与分治
算法不同的是，适用于动态规划求解的问题，经分解得到的子问题往往不是互相独立的。（即下一阶段的求解是建立在上一个子阶段的解的基础之上的。）

动态规划题目常见类型：

按问题特性分：
　　1.计数型
　　　　有多少种方式/方法...？
　　2.求最值
　　3.求存在性
　　　　是否能？能不能？（true or false）
按求解过程（状态方程）分：
　　1.数组型
　　2.背包型
　　3.字符串型

求解思路与步骤：

　　1.分析题目是否是动态规划题目
　　2.确定原问题与子问题
　　3.确定状态
　　4.确定边界状态的值
　　5.找出状态转移方程
　　6.code
　　注意：在解题过程可以先枚举找出状态转移关系，同时注意应用“选与不选”的思路

例题分析：

数组类型DP

　　1.爬楼梯（LeetCode70）
　　　　分析：计数型问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求n阶台阶的走法，子问题为求1阶台阶、2阶台阶、…、n-1阶台阶的走法
　　　　确定状态：此题状态单一，第i个状态即为i阶台阶的所有走法数量。
　　　　边界状态：i=1时，dp[i]=1，i=2时，dp[i]=2；
　　　　状态转移方程：dp[i] = dp[i-1]+dp[i-2];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int climbStairs1(int n) {
	int[] dp = new int[n];
	if (n == 1) {
		return 1;
	}
	if (n == 2) {
		return 2;
	}
	dp[0] = 1;
	dp[1] = 2;
	for(int i = 2;i < n;i++) {
		dp[i] = dp[i-1]+dp[i-2];
	}
	return dp[n-1];
}

　　2.打家劫舍
　　　　你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求到第n个房屋的最大收益，子问题为求第1个房屋的最大收益、第2个房屋的最大收益、…、第n-1个房屋的最大收益
　　　　确定状态：此题状态单一，第i个状态即为第i个房屋的最大收益.
　　　　边界状态：i=1时，dp[i]=nums[0]，i=2时，dp[i]=Math.max(nums[0], nums[1])；
　　　　状态转移方程：dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])(包含第i个房屋偷或者不偷两种选择);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  public int rob(int[] nums) {
      if (nums == null || nums.length < 1) {
	return 0;
}
      if (nums.length == 1) {
	return nums[0];
}
      if (nums.length == 2) {
	return Math.max(nums[0], nums[1]);
}
      int[] dp = new int[nums.length];
      dp[0] = nums[0];
      dp[1] = Math.max(nums[0], nums[1]);
      for(int i = 2;i < dp.length;i++) {
      	dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
      }
      return dp[dp.length-1];
  }

　　3.最大字段和
　　　　给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求以第n个数字结尾的最大字段和，子问题为求以第1、2、…、n-1个数字结尾的最大字段和。注意dp[n]并不是前n个数字组成的数组的最大字段和，即不是最终答案
　　　　确定状态：第i个状态即为以第i个数字结尾的最大字段和
　　　　边界状态：i=1时，dp[i]=nums[0]
　　　　状态转移方程：dp[i] = nums[i](dp[i-1] <= 0) or num[i]+dpi-1(包含第i个房屋偷或者不偷两种选择);

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray1(int[] nums) {
	int ans = nums[0];
	int sum = 0;
	for(int num:nums) {
		if (sum > 0) {
			sum += num;
		}else {
			sum = num;
		}
		ans = Math.max(ans, sum);
	}
	return ans;
}

　　4.零钱兑换（LeetCode322）
　　　　给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能
组成总金额，返回 -1。

　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为总金额为n时，最少需要的硬币个数，子问题为总金额为1、2、…n-1时，最少需要的硬币个数
　　　　确定状态：第i个状态即为总金额为i时最少所需的硬币个数。
　　　　边界状态：i=0时，dp[i]=0
　　　　状态转移方程：dp[i] = min(dp[i-ooins[j]])+1;
　　　　注意：此题不能从数组着手，从数组着手无法确定状态转移方程。同时注意考虑有的金额无法凑出的情况，此时需要返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int coinChange1(int[] coins, int amount) {
    int[] dp = new int[amount+1];
    for(int i = 0;i < amount+1;i++) {
    	dp[i] = -1;
    }
    dp[0] = 0;
    for(int i = 1;i < amount+1;i++) {
    	for(int j = 0;j < coins.length;j++) {
    		if (i - coins[j] >= 0 && dp[i-coins[j]] != -1) {
	if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1) {
		dp[i] = dp[i - coins[j]] + 1;
	}
}
    	}
    }
    return dp[amount];
}

　　扩展：零钱兑换问题在特定的零钱组合（任意面额是比自己小的面额的倍数关系）下是可以使用贪心算法进行解题，但同样在很多零钱组合下使用贪心算法解此类题是错误的。

　　5.三角形最小路径和（LeetCode120）
　　
　　6.最长上升子序列（LeetCode300，与LeetCode674对比）
　　　　给定一个无序的整数数组，找到其中最长上升子序列的长度。

　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求以第n个数为结尾的最长上升子序列的长度，子问题为求以第1、2、…、n-1个数为结尾的最长上升子序列的长度。
　　　　确定状态：第i个状态即为以第i个数为结尾的最长上升子序列的长度。
　　　　边界状态：i=0时，dp[i]=1
　　　　状态转移方程：dp[i] = max(dp[0]+1(num[i]>num[0]),dp[1]+1(num[i]>num[1])…dp[i-1]+1(num[i-1]>num[i-1]))
　　　　注意：此题与最大字段和类似，dp[i]并不表示最终的结果。很多动态规划题都是如此

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// dp
   public int lengthOfLIS(int[] nums) {
   	if (nums == null || nums.length < 1) {
		return 0;
	}
       int[] dp = new int[nums.length];
       for(int i = 0;i < dp.length;i++) {
       	dp[i] = 1;
       }
       int result = dp[0];
       for(int i = 1;i < dp.length;i++) {
       	for(int j = 0;j < i;j++) {
       		if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
       	}
       	if (result < dp[i]) {
			result = dp[i];
		}
       }
       return result;
   }

　　　　优化：尽管使用了动态规划，但此题的时间复杂度仍然有O(n2)，时间复杂度偏高。我们可以采用动态规划+二分查找的方式进行优化。
　　　　我们利用一个数组dp[i]存储到第i个数字的最长上升子序列，因此，循环过程中，每到来一个数字m，如果该数字大于数组末尾数字，则可直接添加在数组的末尾，否则的话，我们需要从头扫描dp，当遇到第一个大于等于m的数字时，我们需要利用m替换掉该数字。如此以来，虽然数组中所存储的不一定是最长上升子序列，但数组中所含元素的个数一定是最长上升子序列。而从头扫描dp个过程可用二分查找实现，因此时间复杂度可以降低到O(nlogn)。
　　　　其实这种思路的本质是把最终所求值用数组的长度来表示了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  // dp+二分查找
  public int lengthOfLIS1(int[] nums) {
  	if (nums == null || nums.length < 1) {
	return 0;
}
  	int[] dp = new int[nums.length];
  	int len = 0;
  	for(int num:nums) {
  		int i = Arrays.binarySearch(dp, 0, len, num);
  		if (i < 0) {
		i = -i-1;
	}
  		dp[i] = num;
  		if (i == len) {
		len++;
	}
  	}
  	return len;
  }

　　7.最小路径和
　　　　给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
　　　　说明：每次只能向下或者向右移动一步。

　　　　分析：最值问题，适合动态规划解决。
　　　　原问题与子问题：原问题为求以第n个数为结尾的最长上升子序列的长度，子问题为求以第1、2、…、n-1个数为结尾的最长上升子序列的长度。
　　　　确定状态：第i个状态即为以第i个数为结尾的最长上升子序列的长度。
　　　　边界状态：i=0时，dp[i]=1
　　　　状态转移方程：dp[i] = max(dp[0]+1(num[i]>num[0]),dp[1]+1(num[i]>num[1])…dp[i-1]+1(num[i-1]>num[i-1]))
　　　　注意：此题与最大字段和类似，dp[i]并不表示最终的结果。很多动态规划题都是如此

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// dp
   public int lengthOfLIS(int[] nums) {
   	if (nums == null || nums.length < 1) {
		return 0;
	}
       int[] dp = new int[nums.length];
       for(int i = 0;i < dp.length;i++) {
       	dp[i] = 1;
       }
       int result = dp[0];
       for(int i = 1;i < dp.length;i++) {
       	for(int j = 0;j < i;j++) {
       		if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
       	}
       	if (result < dp[i]) {
			result = dp[i];
		}
       }
       return result;
   }

　　8.地下城游戏（LeetCode174）

背包型DP

0-1背包

完全背包

参考链接

背包九讲

发表于 | 分类于 ，

题目：

　　给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：

　　做出这道题需要理解：在每个波谷买入并且在每个波谷之后的波峰卖出（交易多次）所获得的收益肯定是大于或等于在最低点买入在最高点卖出（交易一次）所
获得的收益。明白了这一点就很好做出此题，即算出每个波谷波峰直接的差值，并相加即可。

代码：

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
// 贪心算法
public int maxProfit2(int[] prices) {
	if (prices == null || prices.length < 2) {
		return 0;
	}
	int valley = prices[0];
	int peak = prices[0];
	int maxPro = 0;
	int i = 0;
	while(i < prices.length - 1) {
		while(i < prices.length - 1 && prices[i] >= prices[i+1]) {
			i++;
		}
		valley = prices[i];
		while(i < prices.length - 1 && prices[i] <= prices[i+1]) {
			i++;
		}
		peak = prices[i];
		maxPro += peak-valley;
	}
	return maxPro;
}
// 优化方案
public int maxProfit1(int[] prices) {
	if (prices == null || prices.length < 2) {
		return 0;
	}
	int maxPro = 0;
	for(int i = 0;i < prices.length-1;i++) {
		if (prices[i] < prices[i+1]) {
			maxPro += prices[i+1] - prices[i];
		}
	}
	return maxPro;
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

原题链接：

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

发表于 | 分类于 ，

题目：

　　给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

思路：

　　我们需要找到数组中最低的波谷和之后最高的波峰。我们需要维护一个最低股票价格minPrice和最大收益maxPrice，并实时更新。minPrice很容易求出，而
maxPrice=max(前一天的最大收益，今天的股票价格-minPrice)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
// DP
public static int maxProfit1(int[] prices) {
	int maxPro = 0;
	int minPrice = Integer.MAX_VALUE;
	for(int num:prices) {
		if (num < minPrice) {
			minPrice = num;
		}else {
			maxPro = Math.max(maxPro, num-minPrice);
		}
	}
	return maxPro;
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

原题链接：

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/