发表于

写在前面

众所周知规范的HTTP接口由请求方式、请求参数、请求地址、响应数据、统一异常拦截构成。所以本文从这五个方面入手，规范接口，减少前后端联调时间！本文基于REST的风格规范后端接口，对REST的说明可以参考这篇文章：www.ruanyifeng.com/blog/2011/0…

请求方式

使用HTTP的请求方式代表操作资源的动作，定义接口时要根据业务选择适合的请求方式,常见的HTTP请求有5种：

1
2
3
4
5
markdown复制代码1. GET: 从服务器查询出一个或多个数据
2. PUT： 更新服务器完整资源
3. PATCH: 更新服务器部分资源
4. POST: 新增资源
5. DELETE: 删除资源

请求地址

请求地址就是URL，我们已经用HTTP请求代表操作资源的动作了，所以我们在URL中就不应该出现动作。

假设场景设计一个接口操作公司的部门和员工，下面给出规范的URL的例子：

查询示例

1
2
3
4
5
6
7
8
bash复制代码1. 查询所有部门
GET  /department
2. 根据部门编号查询部门信息
GET  /department/{id}
3. 根据部门编号,员工编号查询员工
GET /account/{id}/department/{id}
4. 分页查询部门
GET  /department?currentPage=1&pageSize=10

新增示例

1
2
3
4
bash复制代码1. 新增部门
POST /department
2. 新增员工
POST /account

更新示例

1
2
3
4
bash复制代码1. 更新部门除主键的所有信息
PUT  /department
2. 更新部门的名称
PUT /department

删除示例

1
2
3
4
5
bash复制代码1. 删除部门
DELETE /department/{id}

1. 删除某部门中名叫狗剩的员工
DELETE /account/{name}/department/{id}

请求参数

新增和更新

前端在调用新增和更新接口时传递的是一个对象，所以当请求参数个数等于1时，可以直接接收此参数，当参数大于1时需要新建一个DTO对象来接收。

方便接口调用方调用，我们要把对象和属性写上详细的swagger注释（
该类的作用、该值的作用、格式规则、示例)。

具体示例参考下面代码,节约篇幅省去了getter和setter:

1
2
3
4
5
6
7
8
9
kotlin复制代码@ApiModel("部门对象")
public class DepartmentDto {
    @ApiModelProperty(value ="部门id、不得超过6位",example = "1")
    private Integer id;
    @ApiModelProperty(value ="部门名称、不得超过10位",example = "市场部")
    private String name;


}

查询和删除

查询和删除不能新建一个对象来接受，所以只能在接口处定义swagger注释（该值的作用、格式规则、示例)，并且描述该接口的作用、错误码的返回、成功的返回；

1
2
3
4
5
6
7
8
9
10
less复制代码 @ApiOperation(value = "根据部门id查询部门信息", notes = "根据部门id查询部门信息")
    @GetMapping("/{id}")
    @ApiResponses(value = {@ApiResponse(code = 200, message = "查询成功"),
            @ApiResponse(code = 500, message = "systemError<br>"
                    + "lengthError<br>")})
    @ApiImplicitParam(name = "id",value = "部门id、不得超过6位",example = "1")
    public Result<DepartmentDto> getList(@PathVariable("id") String id){
        //假装查询哈
        return Result.success("查询成功",new DepartmentDto());
    }

响应数据

前后端分离时，我们需要定义统一的返回数据格式，并且对异常也要全局拦截。

统一返回数据对象

统一返回对象应包括以下字段，code：Http状态码、message:错误码、data:返回数据。

  • 这三个字段应加上swagger注释；
  • 构造方法私有化、新建静态的构建方法以便快速得到;
  • 为打印日志方便可以重写toString方法;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
kotlin复制代码@ApiModel("统一返回对象")
public class Result<T> {

    @ApiModelProperty("HTTP 请求状态码")
    private String code;
    @ApiModelProperty("返回的错误码")
    private String message;
    @ApiModelProperty("返回数据")
    private T data;
    private static final String success = HttpStatus.OK.value()+"";
    private static final String fail = HttpStatus.INTERNAL_SERVER_ERROR.value()+"";

    private Result(String code, String message, T t) {
        this.code = code;
        this.message = message;
        this.data = t;
    }

    public static Result success(String message,Object data){
        return new Result(success,message,data);
    }
}

全局异常拦截

异常码

新建一个异常码的枚举，方便管理存储和返回异常；代码中含有no和code的字段，code用于返回前端，no的可以由自己的业务规则生成，将这个no打印在日志中，方便日后排查问题；

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
typescript复制代码public enum ExceptionEnum {

	SYSTEM_ERROR("010-1000000","systemError");


	private final String no;
	private final String code;



	ExceptionEnum(String no, String code) {
		this.no = no;
		this.code = code;
	}

	public String getNo() {
		return no;
	}


	public String getCode() {
		return code;
	}

	@Override
	public String toString() {
		return this.code;
	}

}

全局异常类

新建全局异常码枚举，使用异常码管理异常；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
scala复制代码public class BusinessException extends RuntimeException {
	
	private static final long serialVersionUID = 1L;
	private ExceptionEnum exceptionEnum;
	private Object data ;

    /**
     * Instantiates a new Iam base exception.
     */
    public BusinessException() {
    	
    }


  
    public BusinessException(ExceptionEnum exceptionEnum) {
        super(exceptionEnum.getCode());
        this.exceptionEnum = exceptionEnum;
    }
}

异常拦截

全局异常拦截，如果是业务异常则返回业务返回的错误码；如果是系统内部的错误比如空指针异常等等则抛出系统异常(这样处理是为了统一返回，方便前端处理，空指针异常只是示例，如果真的抛出空指针异常就要好好思考下为什么没判空！！！)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
kotlin复制代码@RestControllerAdvice
public class GlobalExceptionHandler {

    @ExceptionHandler(Exception.class)
    public Result exception(Exception e) {
        return Result.fail(ExceptionEnum.SYSTEM_ERROR.getCode());
    }

    @ExceptionHandler(BusinessException.class)
    public Result exception(BusinessException e) {
        return Result.fail(e.getCode());
    }

}

接口规范示例

GET 和DELETE 接口示例

添加@ApiOperation 描述该方法

添加@ApiResponses 描述成功和失败的message 、Http请求的状态码

添加@ApiImplicitParam 描述传入参数、格式限制、默认值

1
2
3
4
5
6
7
8
9
10
less复制代码 @ApiOperation(value = "根据部门id查询部门信息", notes = "根据部门id查询部门信息")
    @GetMapping("/{id}")
    @ApiResponses(value = {@ApiResponse(code = 200, message = "查询成功"),
            @ApiResponse(code = 500, message = "systemError<br>"
                    + "lengthError<br>")})
    @ApiImplicitParam(name = "id",value = "部门id、不得超过6位",example = "1")
    public Result<DepartmentDto> getList(@PathVariable("id") String id){
        //假装查询哈
        return Result.success("查询成功",new DepartmentDto());
    }

POST、PUT、PATCH接口示例

1
2
3
4
5
6
7
8
9
less复制代码@ApiOperation(value = "新增部门信息", notes = "新增部门信息")
    @PostMapping("/")
    @ApiResponses(value = {@ApiResponse(code = 200, message = "新增成功"),
            @ApiResponse(code = 500, message = "systemError<br>"
                    + "lengthError<br>")})
    public Result add(@RequestBody DepartmentDto dto){
        //假装新增哈
        return Result.success("新增成功",null);
    }

API文档

按照上述的代码所写，得到的swagger文档如图：

代码

示例代码已经上传至www.fizzed.top/archives/ji…

写在最后

欢迎大家关注我的公众号【有一只基的程序猿】，一起交流Java、大数据，文章对应的脑图也会放在公众号里。 点关注，不迷路！！！

博客地址: www.fizzed.top

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

动态规划

1.1 动态规划

什么是动态规划，就是利用已知的条件，推出未知的条件

动态规划最重要的就是要找出状态转移方程，根据前面已经求出的状态，找到状态转移方程，从前面的状态转移到后面的状态

一维动态规划

70. 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

例子1

Input: 2

output: 2

解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶。

例子2

Input: 3

output: 3

解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

思考

这基本上是最经典的动态规划题目，动态规划的关键是确立动态转移方程

这里很明显可以看出dp[n] = dp[n-1]+dp[n-2],也就是爬n个台阶的方法等于爬n-1个台阶的方法和爬n-2个台阶的方法

实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
js复制代码/**
 * @param {number} n
 * @return {number}
 */
// Runtime: 72 ms, faster than 88.54% of JavaScript online submissions for Climbing Stairs.
// Memory Usage: 38.3 MB, less than 56.43% of JavaScript online submissions for Climbing Stairs.
export default (n) => {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (n === 2) return 2;
  let pre1 = 1;
  let pre2 = 2;
  for (let i = 3; i <= n; i++) {
    const temp = pre2;
    pre2 = pre1 + pre2;
    pre1 = temp;
  }
  return pre2;
};

时间复杂度O（n）， 空间复杂度O（1）

198. 打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

例子1

Input: [1,2,3,1]

output: 4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

例子2

Input: [2,7,9,3,1]

output: 12

解释： 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12

提示：

1 0 <= nums.length <= 100

2 0 <= nums[i] <= 400

思考

这基本上是最经典的动态规划题目，动态规划的关键是确立动态转移方程

动态规划一般是利用已知的前面保存的状态推出下面的状态

假设dp[n]是数组长度为n的房屋可以盗窃的最大金额，那么现在可以思考下当dp[n+1]的时候，可以盗窃的最大金额是什么呢？

可以很容易的想到dp[n+1]要么不盗窃n+1的房屋的金额，那么肯定是等于dp[n],要么盗窃n+1房屋的金额，那么当盗窃n+1房屋金额的时候，总盗窃金额是dp[n+1] = dp[n-2]+(n+1)房屋的金额

实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */
// Runtime: 68 ms, faster than 97.89% of JavaScript online submissions for House Robber.
// Memory Usage: 38.2 MB, less than 91.14% of JavaScript online submissions for House Robber.
export default (nums) => {
  if (!nums) return 0;
  if (nums.length === 1) return nums[0];
  if (nums.length === 2) return Math.max(nums[0], nums[1]);

  let preN2money = nums[0];
  let preN1money = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    const temp = preN1money;
    preN1money = Math.max(preN1money, preN2money + nums[i]);
    preN2money = temp;
  }
  return preN1money;
};

时间复杂度O（n）， 空间复杂度O（1）

198. 打家劫舍II

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

例子1

Input: nums = [2,3,2]

output: 3

解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

例子2

Input: nums = [1,2,3,1]

output: 4

解释： 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

例子3

Input: nums = [0]

output: 0

提示：

1 0 <= nums.length <= 100

2 0 <= nums[i] <= 1000

思考

这里基本上延续上面的打家劫舍的题目，但是和上面不一样的是这里是一个循环，从末尾又连到了开始，所以这里该如何解决呢？

如果想要解决一个问题，首先就要明白问题是什么？如果把问题定义的很清楚，也就离解决问题不远了

那这里和打家劫舍有哪些不同呢？

如果想不到，可以写个测试用例，自己看看，比如房屋的金额分别是[2,3,2],我们会得到什么结果呢？

走到这里，相信基本上已经明白了问题在哪了，我们如果按照打家劫舍的解法去做，可以发现因为我们不确定从第一家还是第二家开始打劫，所以如果我们从第一家开始打劫的话，打劫到最后一家的时候，因为最后一家和第一家相连，所以就触发了报警

所以问题也就清楚了，我们如何确定当打劫到到最后一家的时候，如何确定我们没有打劫第一家呢？

应该很容易想到我们如果从第二家开始打劫，一直到最后一家，肯定不会触发报警。

但是从第二家开始是不是就是结果呢？

我们能不能也从第一家开始打劫呢?如果从第一家开始打劫，我们是不是打劫到倒数第二家就可以了？

可以发现这两种情况的最大的，就是我们可以打劫到的最大金额。

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */
// Runtime: 68 ms, faster than 98.02% of JavaScript online submissions for House Robber II.
// Memory Usage: 38.5 MB, less than 53.03% of JavaScript online submissions for House Robber II.
export default (nums) => {
  if (!nums) return 0;
  if (nums.length === 1) return nums[0];
  if (nums.length === 2) return Math.max(nums[0], nums[1]);
  let preN2money = nums[0];
  let preN1money = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length - 1; i++) {
    const temp = preN1money;
    preN1money = Math.max(preN1money, preN2money + nums[i]);
    preN2money = temp;
  }
  let preN2money2 = nums[1];
  let preN1money1 = Math.max(nums[1], nums[2]);
  for (let i = 3; i < nums.length; i++) {
    const temp = preN1money1;
    preN1money1 = Math.max(preN1money1, preN2money2 + nums[i]);
    preN2money2 = temp;
  }
  return Math.max(preN1money1, preN1money);
};

时间复杂度O（n）， 空间复杂度O（1）

343. 整数拆分

题目描述

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

例子1

Input: 2

output: 1

解释：2 = 1 + 1, 1 × 1 = 1。

例子2

Input: 10

output: 36

解释：10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

思考

1 题目本身的状态转移方程一眼就可以看出来
dp[i] = Math.max(dp[i], dp[i-j] * d[j])

但是这里隐藏着一个坑，如果想不到，思路是对的，但是测试用例应该还是过不了的？

因为这里dp[j]可能比j小，dp[i-j]也可能比i-j小

比如dp[4]本来最大的值应该是2 * 2 ,但是
dp[2] * dp [2] =1， dp[3] * dp [1] = 3

很明显不对

实现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
js复制代码/**
 * @param {number} n
 * @return {number}
 */
// Input: 2
// Output: 1
// Explanation: 2 = 1 + 1, 1 × 1 = 1.

// Input: 10
// Output: 36
// Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
// Runtime: 72 ms, faster than 98.97% of JavaScript online submissions for Integer Break.
// Memory Usage: 38.3 MB, less than 82.47% of JavaScript online submissions for Integer Break.
export default (n) => {
  if (n <= 1) return 0;
  if (n === 2) return 1;
  const dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    for (let j = 1; 2 * j <= i; j++) {
      const maxJ = Math.max(j, dp[j]);
      const maxDis = Math.max(i - j, dp[i - j]);
      dp[i] = Math.max(dp[i], maxJ * maxDis);
    }
  }
  // console.log(dp);
  return dp[n];
};

时间复杂度O（n * lgn）， 空间复杂度O（n）

650. 只有两个键的键盘

题目描述

最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：

1 Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。

2 Paste (粘贴) : 你可以粘贴你上一次复制的字符。

给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。

例子1

Input: 3

output: 3

解释：
最初, 我们只有一个字符 ‘A’。

第 1 步, 我们使用 Copy All 操作。

第 2 步, 我们使用 Paste 操作来获得 ‘AA’。

第 3 步, 我们使用 Paste 操作来获得 ‘AAA’。

说明：
1 n 的取值范围是 [1, 1000] 。

思考

1 题目比较简单，就是单纯的dp

我刚开始实现的时候，只是考虑了偶数的情况，没有考虑到奇数也可以被整除的

比如当n=9的时候，9也是可以整除到3的。

参考实现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
js复制代码/**
 * @param {number} n
 * @return {number}
 */
// Runtime: 88 ms, faster than 53.27% of JavaScript online submissions for 2 Keys Keyboard.
// Memory Usage: 39.3 MB, less than 31.78% of JavaScript online submissions for 2 Keys Keyboard.
export default (n) => {
  const dp = new Array(n + 1).fill(Number.MAX_VALUE);
  dp[0] = 0;
  dp[1] = 0;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    if (i % 2 === 0) {
      dp[i] = Math.min(dp[i], dp[i / 2] + 2, i);
    } else {
      dp[i] = Math.min(dp[i], i);
      for (let k = 3; k < Math.floor(i / 2); k++) {
        if (i % k === 0) {
          dp[i] = Math.min(dp[i], dp[k] + i / k);
        }
      }
    }
  }
  return dp[n];
};

时间复杂度O（n ^ 2）， 空间复杂度O（1）

376. 摆动序列

题目描述

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

例子1

Input: [1,7,4,9,2,5]

output: 6

解释：整个序列均为摆动序列。

例子2

Input: [1,17,5,10,13,15,10,5,16,8]

output: 7

解释：这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

例子3

Input: [1,2,3,4,5,6,7,8,9]

output: 2

解释：比如[1,2]就是一个摆动序列

思考

1 如果是单纯的增长或者减少使用动态规划比较简单，但是这里是一个摆动序列，可能就比较麻烦了

这种涉及到几种状态的，可以拆开

这里就是拆开两种状态，分别动态规划

参考实现1

压缩空间的参考实现2

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */

// Runtime: 76 ms, faster than 72.34% of JavaScript online submissions for Wiggle Subsequence.
// Memory Usage: 38.5 MB, less than 44.68% of JavaScript online submissions for Wiggle Subsequence.
export default (nums) => {
  if (nums.length === 0 || !nums) return 0;
  if (nums.length <= 1) return 1;
  if (nums.length === 2) {
    return nums[0] !== nums[1] ? 2 : 1;
  }
  const len = nums.length;
  const up = new Array(len).fill(0);
  const down = new Array(len).fill(0);

  up[0] = 1;
  down[0] = 1;

  for (let i = 1; i < len; i++) {
    if (nums[i] > nums[i - 1]) {
      up[i] = down[i - 1] + 1;
      down[i] = down[i - 1];
    } else if (nums[i] < nums[i - 1]) {
      down[i] = up[i - 1] + 1;
      up[i] = up[i - 1];
    } else {
      down[i] = down[i - 1];
      up[i] = up[i - 1];
    }
  }

  return Math.max(down[nums.length - 1], up[nums.length - 1]);
};

时间复杂度O（n）， 空间复杂度O（n）

实现2

1
2
3
4
5
6
7
8
9
10
11
12
js复制代码// Runtime: 76 ms, faster than 72.34% of JavaScript online submissions for Wiggle Subsequence.
// Memory Usage: 38.5 MB, less than 36.17% of JavaScript online submissions for Wiggle Subsequence.
export default (nums) => => {
  if (nums.length < 2) return nums.length;
  let down = 1;
  let up = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) up = down + 1;
    else if (nums[i] < nums[i - 1]) down = up + 1;
  }
  return Math.max(down, up);
};

时间复杂度O（n）， 空间复杂度O（1）

413. 等差数列划分

题目描述

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:

1, 3, 5, 7, 9

7, 7, 7, 7

3, -1, -5, -9

数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。

如果满足以下条件，则称子数组(P, Q)为等差数组：

元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

例子1

Input: A = [1, 2, 3, 4]

output: 3

解释：A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

思考

1 第一种dp[n]表示n结尾的一共有多少种排列，所以dp[n+1]呢？

这里应该很容易想到dp[n+1] 等于dp[n]和以n+1结尾的数字可以组成的等差数列的和。

不过这里需要注意的是虽然给出的测试用例是排好序的，但是实际上并没有排好序，所以不要按照排好序来处理

可以看下实现1

2 这里如果换一种看法，如果让dp[n]还是表示以下标为n结尾一共有多少种排列？

那么dp[n+1]有多少种呢？

如果想不到，可以试试测试用例[1,2,3,4,5]

分别写下dp[1],dp[2]..dp[5]的结果，看下有什么规律

所以很容易看到dp[n+1] = dp[n]+1,最后因为我们统一的是每个位置的排列数，所以最后求和就可以了

可以看下实现2，明显可以看出实现2比实现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
27
28
29
js复制代码/**
 * @param {number[]} A
 * @return {number}
 */
// Runtime: 84 ms, faster than 18.63% of JavaScript online submissions for Arithmetic Slices.
// Memory Usage: 41.1 MB, less than 5.88% of JavaScript online submissions for Arithmetic Slices.
export default (A) => {
  if (!A || A.length < 3) return [];
  let dp = [];
  if (A[2] - A[1] === A[1] - A[0]) {
    dp.push([A[0], A[1], A[2]]);
  }
  for (let i = 3; i < A.length; i++) {
    const tempArr = [];
    tempArr.push(A[i]);
    const val = A[i] - A[i - 1];
    for (let k = i - 1; k >= 0; k--) {
      if (tempArr[0] - A[k] === val) {
        tempArr.unshift(A[k]);
        if (tempArr.length >= 3) {
          dp.push([...tempArr]);
        }
      } else {
        break;
      }
    }
  }
  return dp.length;
};

时间复杂度O（n^2）， 空间复杂度O（n^2）

实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
js复制代码// Runtime: 76 ms, faster than 76.47% of JavaScript online submissions for Arithmetic Slices.
// Memory Usage: 38.4 MB, less than 51.96% of JavaScript online submissions for Arithmetic Slices.
export default (A) => {
  if (!A || A.length < 3) return [];
  const len = A.length;
  const dp = new Array(len).fill(0);
  for (let i = 2; i < len; ++i) {
    if (A[i] - A[i - 1] === A[i - 1] - A[i - 2]) {
      dp[i] = dp[i - 1] + 1;
    }
  }
  // console.log(dp);
  return dp.reduce((a, b) => a + b);
};

时间复杂度O（n）空间复杂度O（n）

53. 最大子序和

题目描述

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

进阶：

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

例子1

Input: [-2,1,-3,4,-1,2,1,-5,4]

output: 6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

例子2

Input: [1]

output: 1

例子3

Input: [0]

output: 0

例子4

Input: [-1]

output: -1

例子5

Input: [-2147483647]

output: -2147483647

提示：

1 1 <= nums.length <= 2 * 10^4

2 -2^31 <= nums[i] <= 2^31 - 1

思考

1 第一种dp[n]表示n结尾的一共有多少种排列，所以dp[n+1]呢？

这里应该很容易想到dp[n+1] 等于dp[n]和以n+1结尾的数字可以组成的等差数列的和。

不过这里需要注意的是虽然给出的测试用例是排好序的，但是实际上并没有排好序，所以不要按照排好序来处理

可以看下实现1

2 这里如果换一种看法，如果让dp[n]还是表示以下标为n结尾一共有多少种排列？

那么dp[n+1]有多少种呢？

如果想不到，可以试试测试用例[1,2,3,4,5]

分别写下dp[1],dp[2]..dp[5]的结果，看下有什么规律

所以很容易看到dp[n+1] = dp[n]+1,最后因为我们统一的是每个位置的排列数，所以最后求和就可以了

可以看下实现2，明显可以看出实现2比实现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
27
28
29
js复制代码/**
 * @param {number[]} A
 * @return {number}
 */
// Runtime: 84 ms, faster than 18.63% of JavaScript online submissions for Arithmetic Slices.
// Memory Usage: 41.1 MB, less than 5.88% of JavaScript online submissions for Arithmetic Slices.
export default (A) => {
  if (!A || A.length < 3) return [];
  let dp = [];
  if (A[2] - A[1] === A[1] - A[0]) {
    dp.push([A[0], A[1], A[2]]);
  }
  for (let i = 3; i < A.length; i++) {
    const tempArr = [];
    tempArr.push(A[i]);
    const val = A[i] - A[i - 1];
    for (let k = i - 1; k >= 0; k--) {
      if (tempArr[0] - A[k] === val) {
        tempArr.unshift(A[k]);
        if (tempArr.length >= 3) {
          dp.push([...tempArr]);
        }
      } else {
        break;
      }
    }
  }
  return dp.length;
};

时间复杂度O（n^2）， 空间复杂度O（n^2）

实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
js复制代码// Runtime: 76 ms, faster than 76.47% of JavaScript online submissions for Arithmetic Slices.
// Memory Usage: 38.4 MB, less than 51.96% of JavaScript online submissions for Arithmetic Slices.
export default (A) => {
  if (!A || A.length < 3) return [];
  const len = A.length;
  const dp = new Array(len).fill(0);
  for (let i = 2; i < len; ++i) {
    if (A[i] - A[i - 1] === A[i - 1] - A[i - 2]) {
      dp[i] = dp[i - 1] + 1;
    }
  }
  // console.log(dp);
  return dp.reduce((a, b) => a + b);
};

时间复杂度O（n）空间复杂度O（n）

279. 完全平方数

题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

例子1

Input: n = 12

output: 3

解释：12 = 4 + 4 + 4.

例子2

Input: n = 13

output: 2

解释：13 = 4 + 9.

思考

1 动态规划最重要的是什么？

一般主要是找到状态转移方程，这里的状态转移其实也很简单

这里我是怎么想出来的呢？

观察测试用例

// Input: n = 12

// output: 3

// 解释：12 = 4 + 4 + 4.

//

// 例子2

// Input: n = 13

// output: 2

// 解释：13 = 4 + 9.

可以看到dp[13]是dp[4] + 3 * 3,dp[12] 是dp[8] + 2 * 2,而dp[8] = dp[4] + 2 * 2

所以这里的状态转移方程就是dp[n] = Math.min(dp[n-i]+1),并且n = n- i* i + 1

可以参考下实现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
27
28
29
30
31
32
33
34
35
36
37
38
js复制代码/**
 * @param {number} n
 * @return {number}
 */

// Input:  n = 12<br/>
// output: 3<br/>

// 解释：12 = 4 + 4 + 4.
// <br/>

// 例子2<br/>
// Input:  n = 13 <br/>
// output: 2<br/>
// 解释：13 = 4 + 9.

// dp[13] = dp[]

// dp[1] = 1
// dp[2] = 1+1
// dp[n] = dp[n-]
export default (n) => {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (n === 2) return 2;
  const dp = [];
  dp[0] = 0;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = Number.MAX_VALUE;
    const sqrtN = Math.floor(Math.sqrt(i));
    for (let j = 1; j <= sqrtN; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
};

时间复杂度O（1到n的根号的和）， 空间复杂度O（n）

646. 最长数对链

题目描述

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

例子1

Input: [[1,2], [2,3], [3,4]]

output: 2

解释：最长的数对链是 [1,2] -> [3,4]

提示：

给出数对的个数在 [1, 1000] 范围内。

思考

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
js复制代码/**
 * @param {number[][]} pairs
 * @return {number}
 */
//  Runtime: 92 ms, faster than 92.21% of JavaScript online submissions for Maximum Length of Pair Chain.
//  Memory Usage: 42.8 MB, less than 74.03% of JavaScript online submissions for Maximum Length of Pair Chain.
export default (pairs) => {
  if (!pairs || pairs.length === 0) return [];

  if (pairs.length === 1 || pairs.length === 2) return [pairs[0]];
  pairs.sort((a, b) => a[0] - b[0]);
  const dp = [pairs[0]];
  // console.log(pairs);
  for (let i = 1; i < pairs.length; i++) {
    if (pairs[i][0] > dp[dp.length - 1][1]) {
      dp.push(pairs[i]);
    } else if (pairs[i][1] < dp[dp.length - 1][1]) {
      dp[dp.length - 1] = pairs[i];
    }
  }
  // console.log(dp);
  return dp.length;
};

时间复杂度O（n）， 空间复杂度O（n）

91. 解码方法

题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码：

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

题目数据保证答案肯定是一个 32 位的整数。

例子1

Input: s = “12”

output: 2

解释：它可以解码为 “AB”（1 2）或者 “L”（12）

例子2

Input: s = “226”

output: 3

解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

例子3

Input: s = “0”

output: 0

例子4

Input: s = “1”

output: 1

例子5

Input: s = “2”

output: 1

思考

1 刚开始思考，通过”226” 这个测试用例，很容易的可以得出状态转移方程是dp[n] = dp[n-1] + dp[n-2] 或者dp[n] = dp[n-1]

本题的难度不在于状态转移方程的思考，而是在于各种不同情况的处理

比如这里你可以思考下以下测试用例如何处理

“12” => 2

“226” => 3

“00” => 0

“2101” => 1

“27” => 1

“1201234” => 3

“10011” => 0

“123123” => 9

“230” => 0

正常的思考路程肯定是处理各种情况，可以参考实现1

2 通过上面的情况，可以发现各种情况需要各种处理，代码虽然不是很复杂，但是需要处理的各种情况，都需要处理，代码显得冗余，而且不优雅，显得代码难看

可以把上面的各种情况进行统一处理下

这里我们需要思考下为什么上面的情况那么复杂，需要处理的情况为什么那么多？

可以发现就是“0”的各种情况，所以需要各种特殊处理

这里有两种情况

如果当前的数字不是0，那没什么说的，最基本的是dp[i] += dp[i-1]

然后就是要处理要不要再加上dp[i-2],换句话说就是最后两个数字是不是在1到26之间，如果在1到26之间，就需要加上dp[i-2],如果不在，则不需要

可以参考实现2，可以看到代码简洁了很多

实现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
js复制代码/**
 * @param {string} s
 * @return {number}
 */
// dp[3] = dp[1]+dp[2]
// Runtime: 104 ms, faster than 22.88% of JavaScript online submissions for Decode Ways.
// Memory Usage: 42.5 MB, less than 15.00% of JavaScript online submissions for Decode Ways.
export default (s) => {
  if (s.length === 1 && +s > 0) {
    return 1;
  } else if (s.length === 1 || s[0] === "0") {
    return 0;
  }
  const dp = [];
  dp[0] = +s[0] > 0 ? 1 : 0;
  dp[1] = +s[1] > 0 ? dp[0] + 1 : dp[0];

  if (+s.substring(0, 2) > 26 && +s[0] > 0 && s[1] !== "0") {
    dp[1] = 1;
  } else if (+s.substring(0, 2) > 26 && +s[0] > 0 && s[1] === "0") {
    return 0;
  }

  for (let i = 2; i < s.length; i++) {
    if (s[i] === "0" && +s.substring(i - 1, i + 1) < 27 && +s.substring(i - 1, i + 1) > 9) {
      dp[i] = dp[i - 2];
    } else if (+s[i - 1] > 0 && +s[i] > 0 && +s.substring(i - 1, i + 1) > 10 && +s.substring(i - 1, i + 1) < 27) {
      dp[i] = dp[i - 1] + dp[i - 2];
    } else if ((+s[i - 1] === 0 && +s[i] > 0) || (+s[i - 1] > 0 && +s[i] > 0 && +s.substring(i - 1, i + 1) > 26)) {
      dp[i] = dp[i - 1];
    } else if ((+s[i] === 0 && +s.substring(i - 1, i + 1) > 26) || (+s[i - 1] === 0 && +s[i] === 0)) {
      return 0;
    }
  }
  // console.log(dp);
  return dp[dp.length - 1];
};

时间复杂度O（n）， 空间复杂度O（n）

实现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
js复制代码/**
 * @param {string} s
 * @return {number}
 */
export default (s) => {
  if (s.length === 0) return 0;

  const len = s.length;
  const dp = new Array(len + 1).fill(0);

  dp[0] = 1;
  // 当有一个字符的时候
  dp[1] = s[0] === "0" ? 0 : 1;

  for (let i = 2; i <= len; i++) {
    // 如果不等于0，肯定是等于dp[n-1]
    if (s[i - 1] !== "0") {
      dp[i] += dp[i - 1];
    }
    // console.log(dp[i], i);
    // 如果等于0或者小于6的情况下加上dp[n-2]
    if (s[i - 2] === "1" || (s[i - 2] === "2" && s[i - 1] <= "6")) {
      dp[i] += dp[i - 2];
    }
    // console.log(dp[i], i);
  }
  // console.log(dp);
  return dp[len];
};

时间复杂度O(n), 空间复杂度O(n)

139. 单词拆分

题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

1 拆分时可以重复使用字典中的单词。

2 你可以假设字典中没有重复的单词。

例子1

Input: s = “leetcode”, wordDict = [“leet”, “code”]

output: true

解释：返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

例子2

Input: s = “applepenapple”, wordDict = [“apple”, “pen”]

output: true

解释：返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。

例子3

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]

output: false

思考

1 这里使用动态规划比较简单，很容易就可以想到dp[n]表示长度为n的字符串是否可以用wordDict表示，那么dp[n+1]呢？

这里应该比较简单,可以想下dp[n+1]什么时候为true，什么时候为false呢？

那肯定是如果发从s[n+1]到s[i]的字符串可以用wordDict表示，同时dp[i-1]也可以表示的时候，那么dp[n+1]肯定是true了。

实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
js复制代码/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */

// Runtime: 88 ms, faster than 57.62% of JavaScript online submissions for Word Break.
// Memory Usage: 40.5 MB, less than 62.66% of JavaScript online submissions for Word Break.
export default (s, wordDict) => {
  // dp[i] 表示s中前i个字符是否可以在wordDict中表示
  const dp = new Array(s.length).fill(0);

  for (let i = 0; i < s.length; i++) {
    for (let j = i; j >= 0; j--) {
      const subStr = s.substring(j, i + 1);
      if (wordDict.includes(subStr) && ((dp[j - 1] === 1 && j > 0) || j === 0)) {
        dp[i] = 1;
      }
    }
  }
  return dp[s.length - 1];
};

时间复杂度O（n * n * wordDict.length），

空间复杂度O（n）

300. 最长上升子序列

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

例子1

Input:

[10,9,2,5,3,7,101,18]

output: 4

解释： 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

例子2

Input:

nums = [0,1,0,3,2,3]

output: 4

例子3

Input:

nums = [7,7,7,7,7,7,7]

output: 1

提示：

1 1 <= nums.length <= 2500

2 -10^4 <= nums[i] <= 10^4<br

思考

1 题目使用动态规划，dp[i]表示以nums[i]结尾的增长子数列

然后很容易就可以发现状态转移方程dp[i] 等于 i 前面所有小于nums[i]的子数列的最大值

代码比较简单，参考实现1

2 然后题目还要求实现O（n * lgn）的时间复杂度，涉及到lgn肯定是二分查找，可以在哪里查找呢？

在原数组中查找肯定不可能，那在哪里查找呢？可以发现在上面实现1中为什么是O(n * n)? 有哪些可以改进呢？

可以发现上面就是因为需要不断去遍历前面的结果，那么我们是否可以改进下，重新定义dp[i]的含义，让dp[i]表示包含i+1个数字的增长数列。

那么dp就是一个nums中增长子数列，现在已经知道dp[i],那么如何更新dp呢？

现在有新的nums[i+1]了，那么如何更新dp呢？

可以发现在dp中使用二分查找找到nums[i+1]的位置，根据什么查找位置呢？

就是nums[i+1]在dp中的位置pos，等于nums[i+1]>dp[pos] && nums[i+1]<dp[pos+1]，或者直接替换dp[dp.length-1]

num dp

10 [10] 10加入dp

9 [9] 9加入的时候，发现9比10小，为了更长子数列，9替换10

2 [2] 2加入的时候，发现2比9小，为了更长子数列，2替换 9

5 [2，5] 5 加入，发现比大，变为 [2，5]

3 [2,3] 3比5小

7 [2,3,7] 7 比 3大

101 [2,3,7,101] 101比7大

18 [2,3,7,18] 18比101小

可以参考实现2

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */
//  [10,9,2,5,3,7,101,18]
//  4
// Runtime: 184 ms, faster than 18.89% of JavaScript online submissions for Longest Increasing Subsequence.
// Memory Usage: 39.6 MB, less than 25.03% of JavaScript online submissions for Longest Increasing Subsequence.
export default (nums) => {
  const len = nums.length;
  const dp = new Array(len).fill(1);
  let max = 1;
  for (let i = 1; i < nums.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[j] + 1, dp[i]);
        max = Math.max(dp[i], max);
      } else if (nums[i] === nums[j]) {
        dp[i] = Math.max(dp[i], dp[j]);
        max = Math.max(dp[i], max);
      }
    }
  }
  return max;
};

时间复杂度O（n * n), 空间复杂度O（ n）

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {number}
 */
//  [10,9,2,5,3,7,101,18]
//  4

const binarySearchPosition = (dp, target, high) => {
  let low = 0;
  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (target === dp[mid]) return mid;
    else if (target < dp[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return low;
};
// [10, 9, 2, 5, 3, 7, 101, 18];
// Runtime: 84 ms, faster than 90.03% of JavaScript online submissions for Longest Increasing Subsequence.
// Memory Usage: 40.2 MB, less than 19.47% of JavaScript online submissions for Longest Increasing Subsequence.
export default (nums) => {
  const len = nums.length;
  if (!nums || len === 0) return 0;
  if (len === 1) return 1;
  let dp = new Array(len).fill(Number.MAX_VALUE);
  for (let i = 0; i < len; i++) {
    let pos = binarySearchPosition(dp, nums[i], i);
    dp[pos] = nums[i];
    console.log(dp);
  }

  for (let i = dp.length - 1; i >= 0; i--) {
    if (dp[i] !== Number.MAX_VALUE) return i + 1;
  }

  return 0;
};

时间复杂度O（n * lgn），空间复杂度O(n)

二维动态规划

1143. 最长公共子序列

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

例子1

Input: text1 = “abcde”, text2 = “ace”

output: 3

解释：最长公共子序列是 “ace”，它的长度为 3。

例子2

Input: text1 = “abc”, text2 = “abc”

output: 3

解释：最长公共子序列是 “abc”，它的长度为 3。

例子3

Input: text1 = “abc”, text2 = “def”

output: 0

解释：两个字符串没有公共子序列，返回 0。

提示：

1 1 <= text1.length <= 1000

2 1 <= text2.length <= 1000

3 输入的字符串只含有小写英文字符。

思考

1 这里是求公共子序列，动态规划中一般dp[i]是指i结尾的子序列

因为这里涉及到两个字符串，很容易想到使用二维动态规划
dp[i][j]

dp[i][j] 可以用来表示第一个字符串中i结尾和第二个字符串j结尾的包含的公共子序列

那么状态转移方程是什么呢？

可以看下测试用例text1 = “abcde”, text2 = “ace”

可以看到dp[1][1] = 1，因为”a”等于“a”，那么接下来问题就来了？

dp[i+1][j] 是什么？

dp[i][j+1]是什么？

dp[i][j]是什么？

可以看到dp[2][1]=1,dp[1][2] =1 ,dp[2][2] = 1

那么有什么关系呢？

可以看到如果dp[i+1]等于dp[j+1],那么 dp[i+1][j+1]=dp[i][j]+1,如果dp[i+1]不等于dp[j+1]，那么dp[i+1][j+1]要么等于dp[i+1][j]要么等于dp[i][j+1]，也就是dp[i+1][j+1]=Math.max(dp[i+1][j],dp[i][j+1])

有了状态转移方程，代码就很容易了

参考实现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
27
28
js复制代码/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */

//  Runtime: 116 ms, faster than 62.14% of JavaScript online submissions for Longest Common Subsequence.
//  Memory Usage: 48.4 MB, less than 91.40% of JavaScript online submissions for Longest Common Subsequence.
// export default (text1, text2) => {
  const m = text1.length;
  const n = text2.length;
  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(0);
  }
  // console.log(dp);
  for (let i = 1; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  // console.log(dp);
  return dp[m][n];
};

时间复杂度O（m * n), 空间复杂度O（m * n）

583. 两个字符串的删除操作

题目描述

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

例子1

Input: “sea”, “eat”

output: 2

解释：第一步将”sea”变为”ea”，第二步将”eat”变为”ea”

提示：

1 给定单词的长度不超过500。

2 给定单词中的字符只含有小写字母。

思考

1 这里是上面的1143的变种题目，可以想下两者有那些不同?
做题不是目的，举一反三才是本质

那么两者有哪些不一样呢？

我们可以从1143得到那些提示，如何修改才能解决本题呢？

从上面的1143可以得出我们同样可以定义dp[i][j],但是这里的状态转移方程是什么呢？

很容易想到，如果word1[i]等于word[j],那么dp[i][j] 就等于dp[i-1][j-1]

这里比较困难的是如何处理word1[i]不等于word[j]的时候，如何处理呢？

可以想下

这里可以提供一个思路，一般二维动态规划的状态转移方程，dp[i][j] 一般和dp[i-1][j],dp[i][j-1],
dp[i-1][j-1] 有关

然后应该可以得出
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;

参考实现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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
js复制代码/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */

// "sea", "eat";

// Runtime: 108 ms, faster than 93.48% of JavaScript online submissions for Delete Operation for Two Strings.
// Memory Usage: 45 MB, less than 75.00% of JavaScript online submissions for Delete Operation for Two Strings.
export default (word1, word2) => {
  if (word1 === word2) {
    return 0;
  }
  if (word1.length === 0) {
    return word2.length;
  }
  if (word2.length === 0) {
    return word1.length;
  }
  const m = word1.length;
  const n = word2.length;
  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(0);
  }
  for (let i = 1; i <= n; i++) {
    dp[0][i] = i;
  }
  for (let i = 1; i <= m; i++) {
    dp[i][0] = i;
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
      }
    }
  }
  // console.log(dp);
  return dp[m][n];
};

时间复杂度O（m * n), 空间复杂度O（m * n）

64. 最小路径和

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

例子1

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

output: 7

解释：因为路径 1→3→1→1→1 的总和最小。

例子2

Input: grid = [[1,2,3],[4,5,6]]

output: 12

提示：

1 m == grid.length

2 n == grid[i].length<br
3 1 <= m, n <= 200

4 0 <= grid[i][j] <= 100

思考

1 题目比较简单，状态转移方程很容易就可以看出来

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

参考实现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
27
28
29
30
31
32
js复制代码/**
 * @param {number[][]} grid
 * @return {number}
 */
// Runtime: 84 ms, faster than 68.34% of JavaScript online submissions for Minimum Path Sum.
// Memory Usage: 41.1 MB, less than 30.49% of JavaScript online submissions for Minimum Path Sum.
export default (grid) => {
  const m = grid.length;
  const n = grid[0].length;
  if (m === 1 && n === 1) {
    return grid[0][0];
  }
  const dp = [];
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n).fill(0);
  }
  dp[0][0] = grid[0][0];
  for (let i = 1; i < n; i++) {
    dp[0][i] = dp[0][i - 1] + grid[0][i];
  }
  for (let i = 1; i < m; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0];
  }

  // dp[0];
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }
  return dp[m - 1][n - 1];
};

时间复杂度O（m * n), 空间复杂度O（m * n）

542. 01 矩阵

题目描述

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

例子1

Input:

[[0,0,0],
[0,1,0],
[0,0,0]]

output:
[[0,0,0],
[0,1,0],
[0,0,0]]

例子2

Input:

[[0,0,0],
[0,1,0],
[1,1,1]]

output:
[[0,0,0],
[0,1,0],
[1,2,1]]

提示：

1 给定矩阵的元素个数不超过 10000。

2 给定矩阵中至少有一个元素是 0。<br
3 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

思考

1 状态转移方程很好找，如果matrix[i][j]等于1，则dp[i][j]是四个方向中最小的值加1

但是很明显这样不对，因为就会形成循环了

那么如果避免死循环呢

后来想到了可以先从上到下遍历一遍，然后再从下到上遍历一遍，可是发现这样有个情况不是很好处理，那就是不管从上到下，还是从下到上，到matrix[0][0]等于0的时候，如何设置dp[0][0]?

可以想想应该如何设置？

后来才发现，因为是需要找到最小的，我们刚开是就直接设置dp的每个值是MAX_VALUE就可以了，如果从上到下，肯定能找到最小的

当时陷入了一个怪区，总是希望先设置完dp[0][0],才能从上到下遍历

参考实现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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
js复制代码/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
// Runtime: 148 ms, faster than 96.10% of JavaScript online submissions for 01 Matrix.
// Memory Usage: 46.8 MB, less than 79.22% of JavaScript online submissions for 01 Matrix.
export default (matrix) => {
  const m = matrix.length;
  const n = matrix[0].length;
  if (m === 0) {
    return [[]];
  }
  const dp = [];
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n).fill(Number.MAX_VALUE);
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === 0) {
        dp[i][j] = 0;
      } else {
        if (i > 0) {
          dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
        }
        if (j > 0) {
          dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
        }
      }
    }
  }
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      if (matrix[i][j] != 0) {
        if (i < m - 1) {
          dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
        }
        if (j < n - 1) {
          dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
        }
      }
    }
  }
  return dp;
};

时间复杂度O（m * n), 空间复杂度O（m * n）

221. 最大正方形

题目描述

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

例子1

38121a5f0e1ab3a7c6a38bc5aff97e91.jpeg

Input:

matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]

output: 4

例子2

7a1e23b526e764e795e12ef50d9bea3f.jpeg

Input:

matrix = [[“0”,”1”],[“1”,”0”]]

output: 1

例子3

Input:

matrix = matrix = [[“0”]]

output: 0

提示：

1 m == matrix.length

2 n == matrix[i].length<br
3 1 <= m, n <= 300

4 matrix[i][j] 为 ‘0’ 或 ‘1’

思考

1 题目使用动态规划，这里一看就是使用二维动态规划

dp[i][j]表示以matrix[i][j]为结尾的1的最大正方形

那么状态转移方程呢？

这里状态转移方程从逻辑上很容易发现，但是在代码中很难实现

刚开始我想求dp[i][j]的值，分别以
dp[i-1][j-1],dp[i][j-1],dp[i-1][j]分别计算出包含matrix[i][j]的最大正方形，可是发现代码写起来特别乱，及时一些测试用例可以过，但是很多测试过不了

这里的难点就是如何确立简单的状态转移方程？

不过这里确实不好想到，最多可能就是使用测试用例，一个个总结规律

假设dp[i][j]的最大正方形是k^2,那么充分条件为 dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j] 的值必须 都不小于 (k − 1)^2，否则 (i, j) 位置不可以构成一个边长为 k 的正方形。

所以如果dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j]三个值中的最大正方形的边长最小值为 k − 1，也就是三者的最大正方形都不小于(k − 1)^2，则
dp[i][j] 位置一定且最大可以构成一个边长为 k 的正方形，因为dp[i][j]的最大正方形是k^2

51dc1ef58e498a3a99383fcc0b07d10f.png

代码比较简单，参考实现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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
js复制代码/**
 * @param {character[][]} matrix
 * @return {number}
 */

// Runtime: 84 ms, faster than 94.48% of JavaScript online submissions for Maximal Square.
// Memory Usage: 42.2 MB, less than 29.75% of JavaScript online submissions for Maximal Square.

export default (matrix) => {
  const m = matrix.length;
  const n = matrix[0].length;
  if (m === 0 || n === 0) {
    return 0;
  }
  const dp = [];
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n).fill(0);
  }

  let max = 0;
  for (let i = 0; i < n; i++) {
    dp[0][i] = +matrix[0][i];
    max = Math.max(max, dp[0][i]);
  }

  for (let i = 0; i < m; i++) {
    dp[i][0] = +matrix[i][0];
    max = Math.max(max, dp[i][0]);
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === "1") {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;
      }
      max = Math.max(max, dp[i][j]);
    }
  }
  return max * max;
};

时间复杂度O（m * n), 空间复杂度O（m * n）

72. 编辑距离

题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

1
2
3
复制代码插入一个字符
删除一个字符
替换一个字符

例子1

Input: word1 = “horse”, word2 = “ros”

output: 3

解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)

rorse -> rose (删除 ‘r’)

rose -> ros (删除 ‘e’)

例子2

Input:word1 = “intention”, word2 = “execution”

output: 5

解释：
intention -> inention (删除 ‘t’)

inention -> enention (将 ‘i’ 替换为 ‘e’)

enention -> exention (将 ‘n’ 替换为 ‘x’)

exention -> exection (将 ‘n’ 替换为 ‘c’)

exection -> execution (插入 ‘u’)

提示：

1 0 <= word1.length, word2.length <= 500

2 word1 和 word2 由小写英文字母组成

思考

1 已经做了这么多动态规划的题目，很容易想到dp[i][j] 表示word1的i个字符变成word2的j个字符最小距离

接下来就是寻找动态转移方程了

很容易想到有两种情况

当word1[i] 等于word2[j]的时候，

dp[i][j] = dp[i-1][j-1]

当word1[i] 不等于word2[j]的时候，

因为这里有三种操作，
如果增加那么

dp[i][j] = dp[i][j-1]+1

如果删除
dp[i][j] = dp[i-1][j]+1

如果替换
dp[i][j] = dp[i-1][j-1]+1

可以参考实现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
27
28
29
30
31
32
33
34
35
js复制代码/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */

// (word1 = "horse"), (word2 = "ros");
// Runtime: 124 ms, faster than 40.13% of JavaScript online submissions for Edit Distance.
// Memory Usage: 42.8 MB, less than 90.97% of JavaScript online submissions for Edit Distance.
export default (word1, word2) => {
  const m = word1.length;
  const n = word2.length;

  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(0);
  }
  for (let i = 0; i <= n; i++) {
    dp[0][i] = i;
  }
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i;
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  // console.log(dp);
  return dp[m][n];
};

时间复杂度O（m * n ）， 空间复杂度O（ m * n）

10. 正则表达式匹配

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*‘ 的正则表达式匹配。 

1
2
arduino复制代码'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

例子1

Input: s = “aa” p = “a”

output: false

解释：
“a” 无法匹配 “aa” 整个字符串。

例子2

Input: s = “aa” p = “a*“

output: true

解释：
因为 ‘ * ‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

例子3

Input: s = “ab” p = “.*“

output: true

解释：
“.*” 表示可匹配零个或多个（’*’）任意字符（’.’）。

例子4

Input: s = “aab” p = “cab”

output: true

解释：
因为 ‘*‘ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

例子5

Input: s = “mississippi” p = “misis*p\.”

output: false

说明：
1 0 <= s.length <= 20

2 0 <= p.length <= 30

3 s 可能为空，且只包含从 a-z 的小写字母。

4 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 * 。

5 保证每次出现字符 * 时，前面都匹配到有效的字符

思考

1 说实话这题本来还是很有难度的

如果第一次见到该题目，没法实现也很正常

这里那里比较难呢？

难在各种状态如何相互改变，各种条件是否都考虑到了，是否各种情况都考虑到了。

如果单纯看题目，本身其实也不是很难，就是要考虑各种情况，在各种情况下应该如何处理，但是很可能考虑的情况不完全或者考虑错误，很容易就测试用例过不了

这里大体上有两种定义dp[i][j]的定义方法，

一种dp[i][j]表示p的长度i匹配s的长度为j

一种dp[i][j]表示s的长度j匹配p的长度为i

两种思路差不多，但是感觉第一种比较符合逻辑，从下到上匹配比较符合常规思维

这里需要注意的几点是

1 为了考虑s为“”的情况，所以定义了一个dp[p.length + 1][s.length + 1]

这里也说明一种情况，在二维动态规划中一般都是定义这种

刚开始的时候，我本来想定义dp[p.length][s.length]在边界的情况下不是很好处理，所以可以记住以后凡是二维动态规划的时候都定义这种二维数组

2 就是各种情况下的处理，这个确实不是很好处理，但是如何看下代码你会发现很简单

参考实现1

实现2定义dp的方式刚好和实现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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
js复制代码/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */

// Runtime: 92 ms, faster than 93.90% of JavaScript online submissions for Regular Expression Matching.
// Memory Usage: 41.5 MB, less than 53.93% of JavaScript online submissions for Regular Expression Matching.
export default (s, p) => {
  const m = p.length;
  const n = s.length;

  const dp = [];

  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(false);
  }

  dp[0][0] = true;

  for (let i = 1; i <= m; i++) {
    if (p[i - 1] === "*") {
      if (i >= 2) {
        dp[i][0] = dp[i - 2][0];
      }
    }
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[i - 1] === ".") {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (p[i - 1] === "*") {
        if (i >= 2) {
          dp[i][j] = dp[i - 2][j] || dp[i - 1][j];
        } else {
          dp[i][j] = dp[i - 1][j];
        }
        if (dp[i][j - 1] && (p[i - 2] === "." || p[i - 2] === s[j - 1])) {
          dp[i][j] = true;
        }
      } else {
        if (p[i - 1] === s[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        }
      }
    }
  }

  return dp[m][n];
};

时间复杂度O（n * m）， 空间复杂度O（n * m）

实现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
js复制代码/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */

// dp[i][j];
// Runtime: 92 ms, faster than 93.90% of JavaScript online submissions for Regular Expression Matching.
// Memory Usage: 42.1 MB, less than 42.54% of JavaScript online submissions for Regular Expression Matching.
export default (s, p) => {
  const m = s.length;
  const n = p.length;
  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(false);
  }

  dp[0][0] = true;

  for (let i = 1; i <= n; i++) {
    if (p[i - 1] == "*") {
      dp[0][i] = dp[0][i - 2];
    }
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      //如果是.则只要dp[i - 1][j - 1] 为true则为true
      if (p[j - 1] == ".") {
        dp[i][j] = dp[i - 1][j - 1];
        // p[j-1]等于字母
      } else if (p[j - 1] != "*") {
        dp[i][j] = dp[i - 1][j - 1] && p[j - 1] == s[i - 1];
        // p[j-1] 等于“*”,
      } else if (p[j - 2] != s[i - 1] && p[j - 2] != ".") {
        dp[i][j] = dp[i][j - 2];
      } else {
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i][j - 2];
      }
    }
  }
  return dp[m][n];
};

时间复杂度O（n * m）， 空间复杂度O（n * m）

0和1背包问题

背包问题是很经典的动态规划问题

有 N 个物品和容量为 W 的背包，每个物品都有
自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物 品只能选择 0 个或 1 个，则问题称为 0-1 背包问题

0和1背包问题如果使用动态规划应该很容易解决，dp[i][j]表示把i个物品放到容量为j的背包的最大的价值

然后就是定义状态转移方程。

这里很容易想到第i件物品，我们只有两种选择，一种是不放入背包中，那么dp[i][j] = dp[i-1][j]

第二种选择就是我们把i件物品放入到背包中，那么
dp[i][j] = dp[i-1][j-wi]+vi,wi是第i件物品的体积，vi是第i件物品的价值，也就是说如果我们把第i件物品放入的时候，那么此时整个背包的价值就等于dp[i-1][j-wi]加上vi（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
js复制代码/**
 * @param {number[]} weights
 * @param {number[]} values
 * @param {number} n
 * @param {number} w
 * @return {number}
 */
export default (weights, valuse, n, w) => {
  const dp = [];
  for (let i = 0; i <= n; i++) {
    dp[i] = new Array(w + 1).fill(0);
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= w; j++) {
      if (j >= weights[i-1]) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i-1]] + valuse[i-1]);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][w];
};

时间复杂度O( w * n ),空间复杂度O( w * n )

当然基本上所有的动态规划都可以优化空间，可以看下当二维的时候，如下图

eaa65db96f879d3f7a8330abac561a46.png

此时的状态转移方程是

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + valuse[i]);

可以看到我们当求i=2的状态的时候，只需要记录i=1的状态就可以了，也就是可以使用一维数组表示

假设此时i=1的时候，背包容量分别是1，2，3，4，5的时候的背包价值dp=[2，3，4，5，6]，那么如果求出当i=2的时候的不同体积背包的价值呢，也就是dp的各个位置的值呢

假设此时有一个i物品的体积是2，价值是3<b
此时的还是有两种状态，要么放入i这件物品，要么不放入，

那么此时如何更新dp呢？

可以看到dp[j]要么等于不放入i物品的前一个dp[j]，要么等于放入i物品的时候，dp[i-wi]+vi。

此时状态转移方程是dp[j] =Math.max(dp[j],dp[i-wi]+vi)

但是如果正序修改dp的时候，此时可能发现dp[i-wi]可能已经放入了i物品了。所以状态转移方程就有问题了。

所以必须从后从前遍历 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
js复制代码/**
 * @param {number[]} weights
 * @param {number[]} values
 * @param {number} n
 * @param {number} w
 * @return {number}
 */
export default (weights, valuse, n, w) => {
  const dp = new Array(w + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    for (let j = w; j >= 0; j--) {
      if (j >= weights[i-1]) {
        dp[j] = Math.max(dp[j], dp[j - weights[i-1]] + valuse[i-1]);
      }
    }
  }
  return dp[w];
};

时间复杂度O(w * n ),空间复杂度O(w )

416. 分割等和子集

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意：

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

例子1

Input: [1, 5, 11, 5]

output: true

解释： 数组可以分割成 [1, 5, 5] 和 [11].

例子2

Input: [1, 2, 3, 5]

output: false

解释： 数组不能分割成两个元素和相等的子集.

思考

1 这里要转换成0和1背包问题，其实还是有些难度，如何想到如何转换成0和1背包就按照0和1背包问题解决就可以了

主要是问题是一共有nums.length个数字，每个数字就涉及到选择或者不选择，这些可以当做0和1背包的物品

那么什么当做0和1背包的体积呢？

这是比较关键的，想下什么可以当做0和1背包的体积

这里一个比较重要的转换是就是所有数字的和的一半可以当做背包的体积。

我们选择任何数字，只要和等于所有数字的和的一半就可以了

这样就转换成了0和1背包的问题了

没有优化空间的，可以看下实现1

优化空间的，可以看下实现2

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {boolean}
 */
// [1,5,11,5]
// 155 11
// 1235

// [1, 2, 3, 5];
// [1, 1, 2, 2];
// Runtime: 244 ms, faster than 45.49% of JavaScript online submissions for Partition Equal Subset Sum.
// Memory Usage: 70.8 MB, less than 31.03% of JavaScript online submissions for Partition Equal Subset Sum.
export default (nums) => {
  const len = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 !== 0) return false;
  const target = sum / 2;
  const dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(target + 1).fill(false);
  }
  for (let i = 0; i < len; ++i) {
    dp[i][0] = true;
  }
  for (let i = 1; i < len; i++) {
    for (let j = 0; j <= target; ++j) {
      if (j >= nums[i - 1]) {
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
      if (j === target && dp[i][j]) {
        return true;
      }
    }
  }
  // console.log(dp);
  return dp[len - 1][target];
};

时间复杂度O（n^2）， 空间复杂度O（n^2）

实现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
js复制代码/**
 * @param {number[]} nums
 * @return {boolean}
 */
// [1,5,11,5]
// 155 11
// 1235

// [1, 2, 3, 5];
// [1, 1, 2, 2];
// Runtime: 108 ms, faster than 91.72% of JavaScript online submissions for Partition Equal Subset Sum.
// Memory Usage: 40.9 MB, less than 75.58% of JavaScript online submissions for Partition Equal Subset Sum.
export default (nums) => {
  const len = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 !== 0) return false;
  const target = sum / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i < len; i++) {
    for (let j = target; j >= 0; j--) {
      if (j >= nums[i - 1]) { 
        dp[j] = dp[j] || dp[j - nums[i - 1]];
      } else {
        dp[j] = dp[j];
      }
      if (j === target && dp[j]) {
        return true;
      }
    }
  }
  // console.log(dp);
  return dp[target];
};

时间复杂度O（n^2）， 空间复杂度O（n^2）

494. 目标和

题目描述

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

例子1

Input: nums: [1, 1, 1, 1, 1], S: 3

output: 5

解释：
-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

提示 

1
2
3
yaml复制代码数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。

思考

1 这里也是典型的0和1背包问题变形，也就是要么选择+nums[i]或者选择-nums[i]

状态转移方程也好解决 

1
2
3
4
5
6
7
ini复制代码if (j + nums[i - 1] < maxN) {
    dp[i][j] += dp[i - 1][j + nums[i - 1]];
}
// 选择+nums[i - 1]
if (j - nums[i - 1] >= 0) {
    dp[i][j] += dp[i - 1][j - nums[i - 1]];
}

这里的难点是如何处理负数的情况？

如果没想清楚，可以看下代码，其实就是定义所有数据的和的两倍大小，这样就保证了-sum到sum都能包含进去

另外就是如何表示负数，刚开始的时候，我是想是否小于sum，来确定不同的状态转移方程，因为当是负数的情况下，状态转移方程是不一样的

比如nums: [1, 1, 1, 1, 1], S: 3
当求dp[2][5] = dp[1][4]+dp[1][6],但是实际上是不正确的，因为j<=sum的时候实际上表示的是负数

后来看了题解，原来是把当j=sum的时候表示0，j等于sum+1的时候表示正数1，当j等于sum-1的时候表示-1，这样就特别容易处理了

这里可以学习到表示从-sum到sum如何使用数组表示的方法

可以参考实现1

空间优化，参考实现2

实现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
js复制代码/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */

// Runtime: 176 ms, faster than 76.29% of JavaScript online submissions for Target Sum.
// Memory Usage: 44.4 MB, less than 52.32% of JavaScript online submissions for Target Sum.
export default (nums, S) => {
  let sum = 0;
  for (let i of nums) {
    sum += i;
  }

  // 如果大于最大的和小于最小的
  if (S > sum || S < -sum) {
    return 0;
  }
  const dp = [];
  const len = nums.length;
  const maxN = 2 * sum + 1;
  for (let i = 0; i <= len; i++) {
    dp[i] = new Array(maxN).fill(0);
  }
  // 这里指全部选择负数的时候，只有一种选择
  dp[0][0 + sum] = 1;
  for (let i = 1; i <= nums.length; i++) {
    for (let j = 0; j < maxN; j++) {
      // 选择-nums[i - 1]
      if (j + nums[i - 1] < maxN) {
        dp[i][j] += dp[i - 1][j + nums[i - 1]];
      }
      // 选择+nums[i - 1]
      if (j - nums[i - 1] >= 0) {
        dp[i][j] += dp[i - 1][j - nums[i - 1]];
      }
    }
  }
  // console.log(dp);
  return dp[nums.length][sum + S];
};

时间复杂度O（n * m）， 空间复杂度O（n * m）

实现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
js复制代码/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */

// Runtime: 96 ms, faster than 96.39% of JavaScript online submissions for Target Sum.
// Memory Usage: 44.7 MB, less than 41.49% of JavaScript online submissions for Target Sum.
export default (nums, S) => {
  let sum = 0;
  for (let i of nums) {
    sum += i;
  }

  //
  if (S > sum || S < -sum) {
    return 0;
  }
  const len = 2 * sum + 1;
  let dp = new Array(len).fill(0);
  // 所有都选择负数
  dp[sum] = 1;

  for (let i = 0; i < nums.length; i++) {
    const next = new Array(len).fill(0);
    for (let k = 0; k < len; k++) {
      if (dp[k] != 0) {
        // 如果k有n中选择，那么当选择+ nums[i]的时候，肯定有n种，当选择- nums[i]的时候，肯定也有n种
        next[k + nums[i]] += dp[k];
        next[k - nums[i]] += dp[k];
      }
    }
    dp = next;
  }
  return dp[sum + S];
};

时间复杂度O（n * m）， 空间复杂度O（n ）

474. 一和零

题目描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

例子1

Input: strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3

output: 4

解释： 最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

例子2

Input: strs = [“10”, “0”, “1”], m = 1, n = 1

output: 2

解释： 最大的子集是 {“0”, “1”} ，所以答案是 2 。

提示：

1 1<= strs.length <= 600

2 1<= strs[i].length <= 100

3 strs[i] 仅由 ‘0’ 和 ‘1’ 组成

4 <= m, n <= 100

思考

1 这里题目感觉还是比较难的，如果是第一次接触，直接看答案就可以

这里涉及到一个三维数组，这种解法虽然说是0和1背包问题，但是实际上如果你理解为递归更容易理解

假设我们有一个函数memo是计算strs[i]开始的返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1

所以此时就有两种选择，要么加入strs[i]，要么不加入strs[i]，所以这里状态改变方程就是

Math.max(1 + memo(i), memo(i));

可以看下实现1

2 第二种方法就是定义dp[m][n] 表示已经遍历过strs从0到i的最大的子集的长度

那么状态转移方程是啥？

这里是三维降低到二维，可以类比想一下0和1背包问题从二维降低到一维的情况

所以这里dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]) (zeros 表示strs[i]中0的长度， ones表示表示strs[i]中1的长度)

可以参考实现2

实现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
js复制代码/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */

// ["10", "0001", "111001", "1", "0"];
// 5;
// 3;

// ["011111", "001", "001"], 4, 5;
const memo = (dp, start, m, n, size, strs) => {
  if (start >= size || m < 0 || n < 0) return 0;
  if (m === 0 && n === 0) return 0;
  // console.log(dp[start][m], start, m, n);
  if (dp[start][m][n] != -1) return dp[start][m][n];

  let res = 0;
  let i = start;
  let ones = 0;
  for (let k1 = 0; k1 < strs[i].length; k1++) {
    if (strs[i][k1] === "1") {
      ones++;
    }
  }
  let zeros = strs[i].length - ones;
  if (zeros <= m && ones <= n) {
    // 如果选择，则选择其中选择或者不选择中的最大的
    res = Math.max(1 + memo(dp, i + 1, m - zeros, n - ones, size, strs), memo(dp, i + 1, m, n, size, strs));
  } else {
    // 如果不符合规则，则直接下一个
    res = memo(dp, i + 1, m, n, size, strs);
  }
  dp[start][m][n] = res;
  return res;
};
// Runtime: 496 ms, faster than 34.21% of JavaScript online submissions for Ones and Zeroes.
// Memory Usage: 103 MB, less than 28.95% of JavaScript online submissions for Ones and Zeroes.
export default (strs, m, n) => {
  const len = strs.length;
  const dp = [];
  for (let i = 0; i < len; i++) {
    dp[i] = [];
    for (let k = 0; k <= m; k++) {
      dp[i][k] = new Array(n + 1).fill(-1);
    }
  }
  return memo(dp, 0, m, n, len, strs);
};

时间复杂度O（strs的长度 * strs[i]的长度）， 空间复杂度O（strs的长度 * m * n）

实现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
js复制代码/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */

// Runtime: 140 ms, faster than 92.11% of JavaScript online submissions for Ones and Zeroes.
// Memory Usage: 40.9 MB, less than 78.95% of JavaScript online submissions for Ones and Zeroes.
export default (strs, m, n) => {
  const len = strs.length;
  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = new Array(n + 1).fill(0);
  }

  for (let i = 0; i < len; i++) {
    let ones = 0;
    for (let k1 = 0; k1 < strs[i].length; k1++) {
      if (strs[i][k1] === "1") {
        ones++;
      }
    }
    let zeros = strs[i].length - ones;
    for (let k2 = m; k2 >= zeros; --k2) {
      for (let j = n; j >= ones; --j) {
        dp[k2][j] = Math.max(dp[k2][j], 1 + dp[k2 - zeros][j - ones]);
      }
    }
  }
  return dp[m][n];
};

时间复杂度O（strs.length * m * n）， 空间复杂度O（m * n）

完全背包问题

有 N 个物品和容量为 W 的背包，每个物品都有
自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品可以选择多次，那么这里就是完全背包问题

完全背包问题和0和1背包问题差不多，解决思路也是类似，dp[i][j]表示把i个物品放到容量为j的背包的最大的价值

然后就是定义状态转移方程。

这里很容易想到第i件物品，在0和1背包的时候，我们只有两种选择，但是在完全背包的时候，我们是有多种选择的，要么选择一次，要么选择两次，要么选择三次，如果背包体积无穷大，我们甚至可以选择无数次

那么状态方程如何确定呢？

很容易想到

dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wi*k]+vi * k) k>=1 && wi * k <=j

但是还是很复杂，不是很好解决

3651c5000d7b865c4e80b339c5e45d73.png

可以看下上图，此时
dp[2][5] = Math.max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)

那么应该如何改进上面的状态转移方程呢？

此时我们可以改下上面的状态转移方程，变成如下

dp[2][5] = Math.max(dp[1][5], Math.max(dp[1][3] , dp[1][1] + 3) + 3)

然后又以为知道

dp[2][3]= Math.max(dp[1][3] , dp[1][1] + 3)

所以此时

dp[2][5] = Math.max(dp[1][5],dp[2][3] + 3)

类似下图：

f8ae7d2aaa4bf1f21e49d3123cda9888.png

所以最后状态转移方程变成了

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-wi]+vi)

代码如下：

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
js复制代码/**
 * @param {number[]} weights
 * @param {number[]} values
 * @param {number} n
 * @param {number} w
 * @return {number}
 */
export default (weights, valuse, n, w) => {
  const dp = [];
  for (let i = 0; i <= n; i++) {
    dp[i] = new Array(w + 1).fill(0);
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= w; j++) {
      // 如果选择，
      if (j >= weights[i - 1]) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + valuse[i - 1]);
      } else {
        //如果不选择
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n][w];
};

类似于0和1背包，这里也可以进行空间压缩，可以看下下图，这里也只需要使用一维数组就可以了,但是注意这里是使用了正向遍历

d45486323001474fc1356bcd90ec425f.png

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
js复制代码/**
 * @param {number[]} weights
 * @param {number[]} values
 * @param {number} n
 * @param {number} w
 * @return {number}
 */
export default (weights, valuse, n, w) => {
  const dp = new Array(w + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= w; j++) {
      // 如果选择，
      if (j >= weights[i - 1]) {
        dp[j] = Math.max(dp[j], [j - weights[i]] + valuse[i]);
      }
    }
  }
  return dp[w];
};

322. 零钱兑换

题目描述

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

你可以认为每种硬币的数量是无限的。

例子1

Input: coins = [1, 2, 5], amount = 11

output: 3

解释： 11 = 5 + 5 + 1。

例子2

Input:coins = [2], amount = 3

output: -1

例子3

Input:coins = [1], amount = 0

output: 0

例子4

Input:coins = [1], amount = 1

output: 1

例子5

Input:coins = [1], amount = 2

output: 2

提示：

1 1 <= coins.length <= 12

2 1 <= coins[i] <= 2^31 - 1

3 0 <= amount <= 10^4

思考

1 这是典型的完全背包问题，所以可以直接按照完全背包来解决就可以了

这里的技巧就是因为需要寻找最小的个数，所以应该如何设置最大数值呢？

可以看下代码中如何设置的

另外这里可能还要一点就是如何设置边界情况，就是二维数组dp
当i=0和当j=0的时候，应该如何设置？

这里如何边界情况设置不对的话，下面的测试用例是不过的

[186, 419, 83, 408], 6249 结果是20

其它的都比较简单，可以参考实现1

2 这里也可以优化空间，优化空间有个技巧，就是自己画图，把dp的图每步的画出来，可以看下那些不需要，那些需要，就很容易可以看出那些可以优化

这里可能状态转移
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1) 有点不是很好理解

很多人认为得是dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1， dp[i-2* coins[j]] +2 …) 一直到0

其实这里dp[i - coins[j]] 已经包含后面的情况

比如这里coins[j] =2 ,如果按照这个

dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1， dp[i-2* coins[j]] +2 …)

dp[5]= Math.min(dp[5], dp[3]+1， dp[1]+2)

然后会发现
dp[5]= Math.min(dp[5], (dp[3]， dp[1]+1) + 1 )
而dp[3] = Math.min(dp[3]， dp[1]+1),所以还是转换为了
dp[5]= Math.min(dp[5], dp[3]+1)

可以参考实现2

实现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
js复制代码/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
// Runtime: 184 ms, faster than 25.00% of JavaScript online submissions for Coin Change.
// Memory Usage: 44.9 MB, less than 19.34% of JavaScript online submissions for Coin Change.
export default (coins, amount) => {
  const len = coins.length;
  const max = amount + 1;
  const dp = [];
  if (amount === 0) return 0;
  for (let i = 0; i <= len; i++) {
    dp[i] = new Array(max).fill(max);
  }
  // coins.sort((a, b) => a - b);
  for (let i = 0; i <= len; i++) {
    dp[i][0] = 0;
  }
  for (let i = 0; i <= amount; i++) {
    dp[0][amount] = max;
  }
  for (let i = 1; i <= len; i++) {
    for (let j = 0; j <= amount; j++) {
      if (j >= coins[i - 1]) {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  return dp[len][amount] === max ? -1 : dp[len][amount];
};

时间复杂度O（m * n ）， 空间复杂度O（ m * n）

实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
js复制代码/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
// [1, 2, 5], 11;
// Runtime: 124 ms, faster than 63.93% of JavaScript online submissions for Coin Change.
// Memory Usage: 42.7 MB, less than 88.09% of JavaScript online submissions for Coin Change.
export default (coins, amount) => {
  const Max = amount + 1;
  const dp = new Array(amount + 1).fill(Max);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (i >= coins[j]) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
};

时间复杂度O（ m * n）， 空间复杂度O（n）

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

前言

本文基于 SpringCloud, 用户发起点赞、取消点赞后先存入 Redis 中，再每隔两小时从 Redis读取点赞数据写入数据库中做持久化存储。

点赞功能在很多系统中都有，但别看功能小，想要做好需要考虑的东西还挺多的。

点赞、取消点赞是高频次的操作，若每次都读写数据库，大量的操作会影响数据库性能，所以需要做缓存。

至于多久从 Redis 取一次数据存到数据库中，根据项目的实际情况定吧，我是暂时设了两个小时。

项目需求需要查看都谁点赞了，所以要存储每个点赞的点赞人、被点赞人，不能简单的做计数。

文章分四部分介绍：

1.Redis 缓存设计及实现

2.数据库设计

3.数据库操作

4.开启定时任务持久化存储到数据库

一、Redis 缓存设计及实现

1.1 Redis 安装及运行

Redis 安装请自行查阅相关教程。

1
复制代码说下Docker 安装运行 Redis

docker run -d -p 6379:6379 redis:4.0.8
如果已经安装了 Redis，打开命令行，输入启动 Redis 的命令

1
vbscript复制代码redis-server

1.2 Redis 与 SpringBoot 项目的整合

1.在 pom.xml 中引入依赖

1
2
3
4
xml复制代码<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

2.在启动类上添加注释 @EnableCaching

1
2
3
4
5
6
7
8
9
10
11
less复制代码@SpringBootApplication
@EnableDiscoveryClient
@EnableSwagger2
@EnableFeignClients(basePackages = "com.solo.coderiver.project.client")
@EnableCaching
publicclass UserApplication {

    public static void main(String[] args) {
        SpringApplication.run(UserApplication.class, args);
    }
}

3.编写 Redis 配置类 RedisConfig

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
ini复制代码import com.fasterxml.jackson.annotation.JsonAutoDetect;
import com.fasterxml.jackson.annotation.PropertyAccessor;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.springframework.boot.autoconfigure.condition.ConditionalOnMissingBean;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.data.redis.serializer.Jackson2JsonRedisSerializer;

import java.net.UnknownHostException;


@Configuration
publicclass RedisConfig {

    @Bean
    @ConditionalOnMissingBean(name = "redisTemplate")
    public RedisTemplate<String, Object> redisTemplate(
            RedisConnectionFactory redisConnectionFactory)
            throws UnknownHostException {

        Jackson2JsonRedisSerializer<Object> jackson2JsonRedisSerializer = new Jackson2JsonRedisSerializer<Object>(Object.class);
        ObjectMapper om = new ObjectMapper();
        om.setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
        om.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL);
        jackson2JsonRedisSerializer.setObjectMapper(om);

        RedisTemplate<String, Object> template = new RedisTemplate<String, Object>();
        template.setConnectionFactory(redisConnectionFactory);
        template.setKeySerializer(jackson2JsonRedisSerializer);
        template.setValueSerializer(jackson2JsonRedisSerializer);
        template.setHashKeySerializer(jackson2JsonRedisSerializer);
        template.setHashValueSerializer(jackson2JsonRedisSerializer);
        template.afterPropertiesSet();
        return template;
    }


    @Bean
    @ConditionalOnMissingBean(StringRedisTemplate.class)
    public StringRedisTemplate stringRedisTemplate(
            RedisConnectionFactory redisConnectionFactory)
            throws UnknownHostException {
        StringRedisTemplate template = new StringRedisTemplate();
        template.setConnectionFactory(redisConnectionFactory);
        return template;
    }
}

至此 Redis 在 SpringBoot 项目中的配置已经完成，可以愉快的使用了。

1.3 Redis 的数据结构类型

Redis 可以存储键与5种不同数据结构类型之间的映射，这5种数据结构类型分别为String（字符串）、List（列表）、Set（集合）、Hash（散列）和 Zset（有序集合）。

下面来对这5种数据结构类型作简单的介绍：

1.4 点赞数据在 Redis 中的存储格式

用 Redis 存储两种数据，一种是记录点赞人、被点赞人、点赞状态的数据，另一种是每个用户被点赞了多少次，做个简单的计数。

由于需要记录点赞人和被点赞人，还有点赞状态（点赞、取消点赞），还要固定时间间隔取出 Redis 中所有点赞数据，分析了下 Redis 数据格式中 Hash 最合适。

因为 Hash 里的数据都是存在一个键里，可以通过这个键很方便的把所有的点赞数据都取出。这个键里面的数据还可以存成键值对的形式，方便存入点赞人、被点赞人和点赞状态。

设点赞人的 id 为 likedPostId，被点赞人的 id 为 likedUserId ，点赞时状态为 1，取消点赞状态为 0。将点赞人 id 和被点赞人 id 作为键，两个 id 中间用 :: 隔开，点赞状态作为值。

所以如果用户点赞，存储的键为：likedUserId::likedPostId，对应的值为 1 。取消点赞，存储的键为：likedUserId::likedPostId，对应的值为 0 。取数据时把键用 :: 切开就得到了两个id，也很方便。

在可视化工具 RDM 中看到的是这样子

1.5 操作 Redis

将具体操作方法封装到了 RedisService 接口里

RedisService.java

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
arduino复制代码import com.solo.coderiver.user.dataobject.UserLike;
import com.solo.coderiver.user.dto.LikedCountDTO;

import java.util.List;

publicinterface RedisService {

    /**
     * 点赞。状态为1
     * @param likedUserId
     * @param likedPostId
     */
    void saveLiked2Redis(String likedUserId, String likedPostId);

    /**
     * 取消点赞。将状态改变为0
     * @param likedUserId
     * @param likedPostId
     */
    void unlikeFromRedis(String likedUserId, String likedPostId);

    /**
     * 从Redis中删除一条点赞数据
     * @param likedUserId
     * @param likedPostId
     */
    void deleteLikedFromRedis(String likedUserId, String likedPostId);

    /**
     * 该用户的点赞数加1
     * @param likedUserId
     */
    void incrementLikedCount(String likedUserId);

    /**
     * 该用户的点赞数减1
     * @param likedUserId
     */
    void decrementLikedCount(String likedUserId);

    /**
     * 获取Redis中存储的所有点赞数据
     * @return
     */
    List<UserLike> getLikedDataFromRedis();

    /**
     * 获取Redis中存储的所有点赞数量
     * @return
     */
    List<LikedCountDTO> getLikedCountFromRedis();

}

实现类 RedisServiceImpl.java

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
ini复制代码import com.solo.coderiver.user.dataobject.UserLike;
import com.solo.coderiver.user.dto.LikedCountDTO;
import com.solo.coderiver.user.enums.LikedStatusEnum;
import com.solo.coderiver.user.service.LikedService;
import com.solo.coderiver.user.service.RedisService;
import com.solo.coderiver.user.utils.RedisKeyUtils;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.Cursor;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.ScanOptions;
import org.springframework.stereotype.Service;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

@Service
@Slf4j
publicclass RedisServiceImpl implements RedisService {

    @Autowired
    RedisTemplate redisTemplate;

    @Autowired
    LikedService likedService;

    @Override
    public void saveLiked2Redis(String likedUserId, String likedPostId) {
        String key = RedisKeyUtils.getLikedKey(likedUserId, likedPostId);
        redisTemplate.opsForHash().put(RedisKeyUtils.MAP_KEY_USER_LIKED, key, LikedStatusEnum.LIKE.getCode());
    }

    @Override
    public void unlikeFromRedis(String likedUserId, String likedPostId) {
        String key = RedisKeyUtils.getLikedKey(likedUserId, likedPostId);
        redisTemplate.opsForHash().put(RedisKeyUtils.MAP_KEY_USER_LIKED, key, LikedStatusEnum.UNLIKE.getCode());
    }

    @Override
    public void deleteLikedFromRedis(String likedUserId, String likedPostId) {
        String key = RedisKeyUtils.getLikedKey(likedUserId, likedPostId);
        redisTemplate.opsForHash().delete(RedisKeyUtils.MAP_KEY_USER_LIKED, key);
    }

    @Override
    public void incrementLikedCount(String likedUserId) {
        redisTemplate.opsForHash().increment(RedisKeyUtils.MAP_KEY_USER_LIKED_COUNT, likedUserId, 1);
    }

    @Override
    public void decrementLikedCount(String likedUserId) {
        redisTemplate.opsForHash().increment(RedisKeyUtils.MAP_KEY_USER_LIKED_COUNT, likedUserId, -1);
    }

    @Override
    public List<UserLike> getLikedDataFromRedis() {
        Cursor<Map.Entry<Object, Object>> cursor = redisTemplate.opsForHash().scan(RedisKeyUtils.MAP_KEY_USER_LIKED, ScanOptions.NONE);
        List<UserLike> list = new ArrayList<>();
        while (cursor.hasNext()){
            Map.Entry<Object, Object> entry = cursor.next();
            String key = (String) entry.getKey();
            //分离出 likedUserId，likedPostId
            String[] split = key.split("::");
            String likedUserId = split[0];
            String likedPostId = split[1];
            Integer value = (Integer) entry.getValue();

            //组装成 UserLike 对象
            UserLike userLike = new UserLike(likedUserId, likedPostId, value);
            list.add(userLike);

            //存到 list 后从 Redis 中删除
            redisTemplate.opsForHash().delete(RedisKeyUtils.MAP_KEY_USER_LIKED, key);
        }

        return list;
    }

    @Override
    public List<LikedCountDTO> getLikedCountFromRedis() {
        Cursor<Map.Entry<Object, Object>> cursor = redisTemplate.opsForHash().scan(RedisKeyUtils.MAP_KEY_USER_LIKED_COUNT, ScanOptions.NONE);
        List<LikedCountDTO> list = new ArrayList<>();
        while (cursor.hasNext()){
            Map.Entry<Object, Object> map = cursor.next();
            //将点赞数量存储在 LikedCountDT
            String key = (String)map.getKey();
            LikedCountDTO dto = new LikedCountDTO(key, (Integer) map.getValue());
            list.add(dto);
            //从Redis中删除这条记录
            redisTemplate.opsForHash().delete(RedisKeyUtils.MAP_KEY_USER_LIKED_COUNT, key);
        }
        return list;
    }
}

用到的工具类和枚举类

RedisKeyUtils, 用于根据一定规则生成 key

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typescript复制代码publicclass RedisKeyUtils {

    //保存用户点赞数据的key
    publicstaticfinal String MAP_KEY_USER_LIKED = "MAP_USER_LIKED";
    //保存用户被点赞数量的key
    publicstaticfinal String MAP_KEY_USER_LIKED_COUNT = "MAP_USER_LIKED_COUNT";

    /**
     * 拼接被点赞的用户id和点赞的人的id作为key。格式 222222::333333
     * @param likedUserId 被点赞的人id
     * @param likedPostId 点赞的人的id
     * @return
     */
    public static String getLikedKey(String likedUserId, String likedPostId){
        StringBuilder builder = new StringBuilder();
        builder.append(likedUserId);
        builder.append("::");
        builder.append(likedPostId);
        return builder.toString();
    }
}

LikedStatusEnum 用户点赞状态的枚举类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ini复制代码package com.solo.coderiver.user.enums;

import lombok.Getter;

/**
 * 用户点赞的状态
 */
@Getter
publicenum LikedStatusEnum {
    LIKE(1, "点赞"),
    UNLIKE(0, "取消点赞/未点赞"),
    ;

    private Integer code;

    private String msg;

    LikedStatusEnum(Integer code, String msg) {
        this.code = code;
        this.msg = msg;
    }
}

二、数据库设计

数据库表中至少要包含三个字段：被点赞用户id，点赞用户id，点赞状态。再加上主键id，创建时间，修改时间就行了。

建表语句

1
2
3
4
5
6
7
8
9
10
11
sql复制代码create table `user_like`(
    `id` int not null auto_increment,
    `liked_user_id` varchar(32) not null comment '被点赞的用户id',
    `liked_post_id` varchar(32) not null comment '点赞的用户id',
    `status` tinyint(1) default'1' comment '点赞状态，0取消，1点赞',
    `create_time` timestamp not nulldefault current_timestamp comment '创建时间',
  `update_time` timestamp not nulldefault current_timestamp on update current_timestamp comment '修改时间',
    primary key(`id`),
    INDEX `liked_user_id`(`liked_user_id`),
    INDEX `liked_post_id`(`liked_post_id`)
) comment '用户点赞表';

对应的对象 UserLike

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
kotlin复制代码import com.solo.coderiver.user.enums.LikedStatusEnum;
import lombok.Data;

import javax.persistence.Entity;
import javax.persistence.GeneratedValue;
import javax.persistence.GenerationType;
import javax.persistence.Id;

/**
 * 用户点赞表
 */
@Entity
@Data
publicclass UserLike {

    //主键id
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Integer id;

    //被点赞的用户的id
    private String likedUserId;

    //点赞的用户的id
    private String likedPostId;

    //点赞的状态.默认未点赞
    private Integer status = LikedStatusEnum.UNLIKE.getCode();

    public UserLike() {
    }

    public UserLike(String likedUserId, String likedPostId, Integer status) {
        this.likedUserId = likedUserId;
        this.likedPostId = likedPostId;
        this.status = status;
    }
}

三、数据库操作

操作数据库同样封装在接口中

LikedService

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
java复制代码import com.solo.coderiver.user.dataobject.UserLike;
import org.springframework.data.domain.Page;
import org.springframework.data.domain.Pageable;

import java.util.List;

publicinterface LikedService {

    /**
     * 保存点赞记录
     * @param userLike
     * @return
     */
    UserLike save(UserLike userLike);

    /**
     * 批量保存或修改
     * @param list
     */
    List<UserLike> saveAll(List<UserLike> list);


    /**
     * 根据被点赞人的id查询点赞列表（即查询都谁给这个人点赞过）
     * @param likedUserId 被点赞人的id
     * @param pageable
     * @return
     */
    Page<UserLike> getLikedListByLikedUserId(String likedUserId, Pageable pageable);

    /**
     * 根据点赞人的id查询点赞列表（即查询这个人都给谁点赞过）
     * @param likedPostId
     * @param pageable
     * @return
     */
    Page<UserLike> getLikedListByLikedPostId(String likedPostId, Pageable pageable);

    /**
     * 通过被点赞人和点赞人id查询是否存在点赞记录
     * @param likedUserId
     * @param likedPostId
     * @return
     */
    UserLike getByLikedUserIdAndLikedPostId(String likedUserId, String likedPostId);

    /**
     * 将Redis里的点赞数据存入数据库中
     */
    void transLikedFromRedis2DB();

    /**
     * 将Redis中的点赞数量数据存入数据库
     */
    void transLikedCountFromRedis2DB();

}

LikedServiceImpl 实现类

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
typescript复制代码import com.solo.coderiver.user.dataobject.UserInfo;
import com.solo.coderiver.user.dataobject.UserLike;
import com.solo.coderiver.user.dto.LikedCountDTO;
import com.solo.coderiver.user.enums.LikedStatusEnum;
import com.solo.coderiver.user.repository.UserLikeRepository;
import com.solo.coderiver.user.service.LikedService;
import com.solo.coderiver.user.service.RedisService;
import com.solo.coderiver.user.service.UserService;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.domain.Page;
import org.springframework.data.domain.Pageable;
import org.springframework.stereotype.Service;
import org.springframework.transaction.annotation.Transactional;

import java.util.List;

@Service
@Slf4j
publicclass LikedServiceImpl implements LikedService {

    @Autowired
    UserLikeRepository likeRepository;

    @Autowired
    RedisService redisService;

    @Autowired
    UserService userService;

    @Override
    @Transactional
    public UserLike save(UserLike userLike) {
        return likeRepository.save(userLike);
    }

    @Override
    @Transactional
    public List<UserLike> saveAll(List<UserLike> list) {
        return likeRepository.saveAll(list);
    }

    @Override
    public Page<UserLike> getLikedListByLikedUserId(String likedUserId, Pageable pageable) {
        return likeRepository.findByLikedUserIdAndStatus(likedUserId, LikedStatusEnum.LIKE.getCode(), pageable);
    }

    @Override
    public Page<UserLike> getLikedListByLikedPostId(String likedPostId, Pageable pageable) {
        return likeRepository.findByLikedPostIdAndStatus(likedPostId, LikedStatusEnum.LIKE.getCode(), pageable);
    }

    @Override
    public UserLike getByLikedUserIdAndLikedPostId(String likedUserId, String likedPostId) {
        return likeRepository.findByLikedUserIdAndLikedPostId(likedUserId, likedPostId);
    }

    @Override
    @Transactional
    public void transLikedFromRedis2DB() {
        List<UserLike> list = redisService.getLikedDataFromRedis();
        for (UserLike like : list) {
            UserLike ul = getByLikedUserIdAndLikedPostId(like.getLikedUserId(), like.getLikedPostId());
            if (ul == null){
                //没有记录，直接存入
                save(like);
            }else{
                //有记录，需要更新
                ul.setStatus(like.getStatus());
                save(ul);
            }
        }
    }

    @Override
    @Transactional
    public void transLikedCountFromRedis2DB() {
        List<LikedCountDTO> list = redisService.getLikedCountFromRedis();
        for (LikedCountDTO dto : list) {
            UserInfo user = userService.findById(dto.getId());
            //点赞数量属于无关紧要的操作，出错无需抛异常
            if (user != null){
                Integer likeNum = user.getLikeNum() + dto.getCount();
                user.setLikeNum(likeNum);
                //更新点赞数量
                userService.updateInfo(user);
            }
        }
    }
}

数据库的操作就这些，主要还是增删改查。

四、开启定时任务持久化存储到数据库

定时任务 Quartz 很强大，就用它了。

Quartz 使用步骤：

1.添加依赖

1
2
3
4
xml复制代码<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-quartz</artifactId>
</dependency>

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
kotlin复制代码package com.solo.coderiver.user.config;

import com.solo.coderiver.user.task.LikeTask;
import org.quartz.*;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
publicclass QuartzConfig {

    privatestaticfinal String LIKE_TASK_IDENTITY = "LikeTaskQuartz";

    @Bean
    public JobDetail quartzDetail(){
        return JobBuilder.newJob(LikeTask.class).withIdentity(LIKE_TASK_IDENTITY).storeDurably().build();
    }

    @Bean
    public Trigger quartzTrigger(){
        SimpleScheduleBuilder scheduleBuilder = SimpleScheduleBuilder.simpleSchedule()
//                .withIntervalInSeconds(10)  //设置时间周期单位秒
                .withIntervalInHours(2)  //两个小时执行一次
                .repeatForever();
        return TriggerBuilder.newTrigger().forJob(quartzDetail())
                .withIdentity(LIKE_TASK_IDENTITY)
                .withSchedule(scheduleBuilder)
                .build();
    }
}

3.编写执行任务的类继承自 QuartzJobBean

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
java复制代码package com.solo.coderiver.user.task;

import com.solo.coderiver.user.service.LikedService;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang.time.DateUtils;
import org.quartz.JobExecutionContext;
import org.quartz.JobExecutionException;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.scheduling.quartz.QuartzJobBean;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * 点赞的定时任务
 */
@Slf4j
publicclass LikeTask extends QuartzJobBean {

    @Autowired
    LikedService likedService;

    private SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

    @Override
    protected void executeInternal(JobExecutionContext jobExecutionContext) throws JobExecutionException {

        log.info("LikeTask-------- {}", sdf.format(new Date()));

        //将 Redis 里的点赞信息同步到数据库里
        likedService.transLikedFromRedis2DB();
        likedService.transLikedCountFromRedis2DB();
    }
}

在定时任务中直接调用 LikedService 封装的方法完成数据同步。

以上就是点赞功能的设计与实现，不足之处还请各位大佬多多指教。

另外，点赞/取消点赞 跟 点赞数 +1/ -1 应该保证是原子操作 , 不然出现并发问题就会有两条重复的点赞记录 , 所以要给整个原子操作加锁 . 同时需要在Spring Boot 的系统关闭钩子函数中补充同步redis中点赞数据到mysql中的过程 . 不然有可能出现距离上一次同步1小时59分的时候服务器更新 , 把整整两小时的点赞数据都给清空了 . 如果点赞设计到比较重要活动业务的话这就很尴尬了 .

我这边整理了一份2020Java面试题资料，（包括Java核心知识点、面试专题和20年最新的互联网真题、电子书等）有需要的朋友可以关注公众号【程序媛小琬】即可获取。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于 Java / Kotlin 语言，为你分享常见的数据结构与算法问题，及其解题框架思路。

本文是数据结构与算法系列的第 9 篇文章，完整文章目录请移步到文章末尾~

前言

  • 今天，我们来讨论一个非常实用的数据结构——二叉堆（Binary Heap，简称：堆），它最主要的应用场景有 堆排序 & 优先队列 & Top K & 最大索引堆。与堆相关算法题目基本属于中等难度，在算法面试中也比较常见，建议应试者着重学习；
  • 在这篇文章里，我将梳理堆的 基本知识 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

目录

  1. 基本概念
  • 逻辑结构

二叉堆（Binary Heap） 是一种特殊的完全二叉树，即：每个节点都大于等于（或者小于等于）子节点。需要注意的是，兄弟节点的相对大小是不重要的。

具体来说，如果每个节点都大于等于子节点，这种堆称为 大顶堆 / 最大堆；如果每个节点都小于等于子节点，这种堆称为 小顶堆 / 最小堆。

  • 物理结构

树可以采用数组 & 链表两种存储方式，对于二叉堆（完全二叉树）来说，数组存储方式是空间利用率最高的存储方式。因此通常来说，二叉堆是基于数组的数据结构。

  1. 堆的基本操作

这一节，我们先来讨论堆的三个基本操作 —— 上浮 & 下沉 & 建堆，这三个操作的目的其实都是堆化（Heapify）。建堆的作用是把一组数据转换为满足堆性质的数据结构，而上浮 和 下沉的作用是在堆结构变化之后，适当地调整节点使其重新满足堆的性质 。

提示： 为了专注于讨论二叉堆的相关内容，在这一节里我们不考虑泛型，同时以大顶堆为例子。

2.1 上浮（添加元素）

往堆里添加元素时，需要执行上浮操作，具体步骤如下：

  • 1、新元素放在数组末尾（注意：是有效数据的末尾，而不是数组物理区域的末尾）；
  • 2、与父节点比较，如果不满足堆的性质，则交换父子节点；
  • 3、重复步骤 2，直到满足堆的性质。

提示： 从数组末尾开始上浮，数组交换和一定的次数最少。

引用自 time.geekbang.org/column/arti… —— 王争 著

结合代码可能更容易理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
arduino复制代码根节点存储在第 [0] 位

public class Heap {

    private Integer[] data;
    private int count;

    添加元素
    private void insert(Integer x) {
        int i = count;
        data[count++] = x;
        siftup(i);
    }

    上浮操作
    private void siftup(int k) {
        while (k > 0 && data[(k - 1) / 2] < data[k]) {
            swap(data, (k - 1) / 2, k);
            k /= 2;
        }
    }
}

这段代码存在着一些不必要的赋值操作，可以优化，优化后目标元素只会赋值一次到最终位置：

参考 JDK 1.5 java.util.PriorityQueue.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ini复制代码添加元素
private void insert(Integerx) {
    int i = count;
    data[count++] = x;
    siftup(i, x);
}

上浮操作
private void siftup(int k, Integer x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Integer parentE = data[parent];
        if (parentE >= x)
            break;
        data[k] = parentE;
        k = parent;
    }
    data[k] = x;
}

2.2 下沉（取出元素）

往堆里取出元素时，需要执行下沉操作，具体步骤如下：

  • 1、取出堆顶元素，即数组第 1 个元素（索引为 0 或 1，取决于具体实现）；
  • 2、数组最后一个元素放到数组 1 个元素的位置；
  • 3、与子节点比较，如果不满足堆的性质，则交换父节点与子节点中最小的那个；
  • 4、重复步骤 3，直到满足堆的性质。

提示： 从数组头部开始下沉，数组交换和一定的次数最少，同时能够避免出现 数组空洞。

引用自 time.geekbang.org/column/arti… —— 王争 著

另外，需要注意到叶子节点是没有子节点的，不需要执行下沉操作，可以提前结束。（根节点存储在第 [0] 位时，叶子节点下标为count2到count−1\frac{count} {2} 到 count-12count到count−1，根节点存储在第 [1] 位时，叶子节点下标为 count2+1到count\frac{count}{2} + 1 到 count2count+1到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
33
ini复制代码根节点存储在第 [0] 位

public class Heap {

    private Integer[] data;
    private int count;

    取出堆顶元素
    int poll() {
        int k = --count;
        int result = data[0];
        int x = data[k];
        data[k] = null;
        if (k != 0) {
            siftdownV2(0);
        }
        return result;
    }
    
    下沉操作
    void siftdown(int k) {
        int half = count / 2;
        while (k < half) {
            int minPos = k;
            if (data[k * 2 + 1] < data[k]) minPos = k * 2 + 1;
            if (data[k * 2 + 2] < count && data[k * 2 + 2] < data[k]) minPos = k * 2 + 2;
            if (minPos == k)
                break;
            swap(data, k, minPos);
            k = minPos;
        }
    }
}

这段代码存在着一些不必要的赋值操作，可以优化，优化后目标元素只会赋值一次到最终位置：

参考 JDK 1.5 java.util.PriorityQueue.java

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
ini复制代码取出堆顶元素
private int poll() {
    int k = --count;
    int result = data[0];
    int x = data[k];
    data[k] = null;
    if (k != 0) {
        siftdown(0, x);
    }
    return result;
}

下沉操作
private void siftdown(int k, int x) {
    注意：叶子节点没有子节点，不需要下沉
    int half = count >>> 1;
    while (k < half) {
    int child = (k << 1) + 1; // assume left child is least
    Integer childE = data[child];
    int right = child + 1;
    if (right < count && childE > data[right])
        childE = data[child = right];
        if (x < childE)
            break;
        data[k] = childE;
        k = child;
    }
    data[k] = x;
}

2.3 建堆

前面讲的上浮和下沉操作的前提是数组本身是堆化的，那么这一节我们就来讨论 建堆 这一操作。

建堆可以分为 原地建堆 & 非原地建堆，原地建堆指的是将一个数组原地堆化的过程，而非原地建堆指的是输入数据一个个添加到数组中的过程。可以观察到， 非原地建堆其实就是不断添加元素执行下沉操作的过程，等同于 第 2.1 节 上浮操作，所以我们主要是分析原地建堆。

原地建堆可以用两种方法实现，分别为 从下往上堆化 & 从上往下堆化 ：

  • 从下往上堆化

这种方法先将下标为 0 的第一个元素视为大小为 1 的堆，随后将下标从1到count−11到count -11到count−1的元素依次执行上浮操作。这个过程也相当于不断向这个初始大小为 1 的堆里添加元素。

  • 从上往下堆化

这种方法先将叶子节点视为大小为 1 的堆，随后将下标从count2−1递减到0\frac{count}{2}-1递减到02count−1递减到0的节点执行下沉操作。

2.4 复杂度分析

  • 时间复杂度
+ 上浮 & 下沉：沿着树根节点到叶子节点的路径进行比较和交换。而一个包含 n 个节点的二叉树，树的高度为 lgnlgnlgn，所以**时间复杂度为O(lgn)O(lgn)O(lgn)**；
+ 建堆：**建堆的时间复杂度是O(n)O(n)O(n)**，推导过程可以看参考资料，这个结论还是比较重要的。
  • 空间复杂度
    堆化的过程中只是用了常量级变量，因此空间复杂度为O(1)O(1)O(1)。
  1. 堆的应用 —— 堆排序

堆排序（Heap Sort） 指的是借助二叉堆实现的原地排序算法，它是一种时间复杂度为 O(nlgn)O(nlgn)O(nlgn)的不稳定的排序算法，快速排序有几分相似之处，后文我也会分析它们之间的区别。

总的来说，堆排序的过程可以分为 建堆 & 排序 两个步骤：

3.1 建堆

建堆的过程在 第 2.3 节讨论过了，假设我们要进行递增排序的话，我们就需要建立一个大顶堆（每个节点都大于等于子节点）。

特别提示： 完成建堆后，数据处于 堆有序 状态，但不是 有序 状态，堆有序其实只是指数据满足堆的性质（每个节点都大于等于或小于等于子节点）。

3.2 排序

建立大顶堆后，现在我们来进行排序操作，具体操作如下：

  • 1、堆顶元素，交换到数组末尾位置，此时，最大的元素已经完成排序；
  • 2、执行下沉操作，将数组前 n - 1 个数据重新堆化；
  • 3、重复步骤 1 和 步骤 2，直到堆的大小为 1。

整个过程相当于执行 n 次 取出堆顶元素的操作，直到最后堆的大小为 1 时，数组完成排序。

引用自 time.geekbang.org/column/arti… —— 王争 著

3.3 复杂度分析

  • 时间复杂度

下沉操作的时间复杂度是O(lgn)O(lgn)O(lgn)，总共执行 n 次，因此总体的时间复杂度为O(nlgn)O(nlgn)O(nlgn)；

  • 空间复杂度

堆排序是原地排序，建堆和排序的过程中只是用了常量级变量，因此总体的空间复杂度为O(1)O(1)O(1)。

3.4 堆排序与快速排序对比

前面提到了堆排序和快速排序的相似之处，那么两者有何不同的？

  • 数据访问方式不同

快速排序是从数组下标依次递增访问数据，而堆排序是跳着访问的，后者更不利于命中 CPU 缓存行。

  • 数据交换次数不同

堆排序进行堆化时，可能会改变数据原本的相对顺序，将原本相对有序的数组变得更加无序。这反而增加了逆序度，增加了执行交换操作的次数。

考虑到这两个因素，我们不难理解为什么 JDK 的 java.util.Arrays.sort()会选择使用快速排序，而不是堆排序了。

当然了，堆排序也不是完全没有价值，有一种场景堆排序就 “秒杀” 快速排序。那就是只需要取得前 k 个有序的数据时，即 Top k 问题，使用堆排序（或者称为大小为 k 优先队列），时间复杂度仅为O(nlgk)O(nlgk)O(nlgk)。

  1. 堆的应用 —— 优先队列

与优先对列相似的有一种数据结构：队列，虽然它们的名称很相似，但是本质上区别是很大的：

数据结构 描述
队列 先进先出（FIFO），出队顺序由时间顺序决定
优先队列 出队顺序与入队顺序无关，而由优先级顺序决定

4.1 优先队列的实现

狭义上，优先队列指的是基于二叉堆实现的数据结构。而广义上，凡是能够实现按优先级顺序出队的数据结构都可以称为优先队列（例如 Android 领域熟知的 MessageQueue）。

提示： 当你看到优先队列这个词的时候，如果没有特殊上下文语境，指的就是基于堆实现的优先队列。

一般来说，优先队列有以下三种实现：

底层实现 入队 出队 举例
普通数组 O(1)O(1)O(1) O(n)O(n)O(n)（扫描整个数组选择最高优先级） /
顺序数组 O(n)O(n)O(n)（入队时维护顺序，下标靠前优先级越高） O(1)O(1)O(1)（取出数组下标为 0 的元素） Android MessageQueue
堆 O(lgn)O(lgn)O(lgn) O(lgn)O(lgn)O(lgn) Java PriorityQueue

可以观察到，基于堆的优先队列平衡了入队与出队的时间复杂度。

4.2 优先队列的优点

使用优先队列可以实现 高性能的定时器。

假设我们有一个定时器 / 消息器，里面存储是等待执行的定时任务，最笨的方法是每隔一小段时间扫描整个任务列表，筛选出到达执行时间的任务。这样做有两大弊端：

  • 1、无效轮询：任务的执行时间可能还差很久，前面的扫描都是无效的；
  • 2、扫描耗时：如果任务列表非常庞大，一趟扫描会非常耗时。

而如果使用优先队列，则可以规避这两个弊端，即不需要轮询，也不需要扫描整个任务列表。

需要做的是维护定时任务列表的执行优先顺序，每次从优先队列中取出队首的任务。然后计算该任务执行时间与当前时间的差值，把这个差值作为等待时间，等待这个时间之后再回来执行任务（如果等待过程中对任务列表进行操作，则需要提前唤醒）。

Android 领域的小伙伴应该对 MessageQueue 优先队列有深刻理解。虽然它并不是一个基于堆的优先队列，但是思路是一致的：如果当前时间还未到达队首消息的执行时间，那么当前线程等待，而不是轮询判断。

  1. 堆的应用 —— Top K 问题

5.1 题目描述

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

Top K 问题是一个超高频的面试算法问题，难度属于中等，它的解法有很多个，最笨的方法是先将整个数组执行快速排序，再返回排序后前 k 个数，时间复杂度为O(nlgn)O(nlgn)O(nlgn)。在这里我们主要讲使用二叉堆的解法。

5.2 解法步骤

步骤分解如下：

  • 1、将数组前 k 个数添加到堆，建立一个大小为 k 的大顶堆；
  • 2、依次遍历数组后续的数，如果该数比堆顶的数更小，则将堆顶元素弹出，而该数添加到堆中；
  • 3、重复步骤 2，直到所有数据处理完毕，最终堆中元素就是最小的 k 个数。

可以发现基于二叉堆的思路是 使用大顶堆维护数据的最小的 k 个数，每次将一个数与堆顶元素比较。如果该数小于堆顶元素，说明堆顶元素不是最小 k 小个数，应当从堆里弹出，而该数添加到堆里。

5.3 复杂度分析

  • 时间复杂度

建堆的时间复杂度是O(k)O(k)O(k)，而取堆顶元素和插入元素的时间复杂度为O(lgk)O(lgk)O(lgk)，因此总的时间复杂度为O(nlnk)O(nlnk)O(nlnk)，优于快速排序O(nlgn)O(nlgn)O(nlgn)；

  • 空间复杂度

维护了一个大小为 k 的二叉堆，空间复杂度为O(k)O(k)O(k)。

  1. 最大索引堆

Editting…

参考资料

推荐阅读

数据结构与算法系列完整目录如下（2023/07/11 更新）：

Java & Android 集合框架系列文章: 跳转阅读

LeetCode 上分之旅系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

最近陆陆续续有不少园友加我好友咨询 redis 集群搭建的问题，我觉得一定是之前写的这篇 《基于Docker的Redis集群搭建》 文章有问题了，所以我花了几分钟浏览之前的文章总结了下面几个问题：

  • redis 数量太少，只创建了 3 个实例；
  • 由于只有 3 个实例，所以全部只能是主节点，无法体现集群主从关系；
  • 如何搭建主从集群？如何分配从节点？

基于之前的文章，我想快速的过一下这几个问题，本文基于 Docker + Redis 5.0.5 版本，通过 cluster 方式创建一个 6 个 redis 实例的主从集群，当然文章会指出相应的参数说明，这样即便是创建 9 个实例的集群方式也是一样的。

1、拉取 Redis 镜像

基于 Redis：5.0.5 版本，执行如下指令：

1
复制代码docker pull redis:5.0.5

2、创建 6 个 Redis 容器

创建 6 个Redis 容器：

  • redis-node1：6379
  • redis-node2：6380
  • redis-node3：6381
  • redis-node4：6382
  • redis-node5：6383
  • redis-node6：6384

执行命令如下：

1
2
3
4
5
6
7
8
9
10
11
bash复制代码docker create --name redis-node1 --net host -v /data/redis-data/node1:/data redis:5.0.5 --cluster-enabled yes --cluster-config-file nodes-node-1.conf --port 6379

docker create --name redis-node2 --net host -v /data/redis-data/node2:/data redis:5.0.5 --cluster-enabled yes --cluster-config-file nodes-node-2.conf --port 6380

docker create --name redis-node3 --net host -v /data/redis-data/node3:/data redis:5.0.5 --cluster-enabled yes --cluster-config-file nodes-node-3.conf --port 6381

docker create --name redis-node4 --net host -v /data/redis-data/node4:/data redis:5.0.5 --cluster-enabled yes --cluster-config-file nodes-node-4.conf --port 6382

docker create --name redis-node5 --net host -v /data/redis-data/node5:/data redis:5.0.5 --cluster-enabled yes --cluster-config-file nodes-node-5.conf --port 6383

docker create --name redis-node6 --net host -v /data/redis-data/node6:/data redis:5.0.5 --cluster-enabled yes --cluster-config-file nodes-node-6.conf --port 6384

部分参数解释：

  • –cluster-enabled：是否启动集群，选值：yes 、no
  • –cluster-config-file 配置文件.conf ：指定节点信息，自动生成
  • –cluster-node-timeout 毫秒值： 配置节点连接超时时间
  • –appendonly：是否开启持久化，选值：yes、no

执行命令截图：

3、启动 Redis 容器

执行命令如下：

1
sql复制代码docker start redis-node1 redis-node2 redis-node3 redis-node4 redis-node5 redis-node6

启动截图如下：

4、组建 Redis 集群

进入任意一个 Redis 实例：

1
2
bash复制代码# 这里以 redis-node1 实例为例
docker exec -it redis-node1 /bin/bash

执行组件集群的命令：

1
2
bash复制代码# 组建集群,10.211.55.4为当前物理机的ip地址
redis-cli --cluster create 10.211.55.4:6379 10.211.55.4:6380 10.211.55.4:6381 10.211.55.4:6382 10.211.55.4:6383 10.211.55.4:6384 --cluster-replicas 1

执行命令截图如下：

创建成功后，通过 redis-cli 查看一下集群节点信息：

1
2
ruby复制代码root@CentOS7:/data# redis-cli
127.0.0.1:6379> cluster nodes

执行命令截图如下：

5、关于Redis集群搭建

我们再回到创建集群的命令上：

1
css复制代码redis-cli --cluster create 10.211.55.4:6379~6384 --cluster-replicas 1

大家着重看这个参数 –cluster-replicas 1，参数后面的数字表示的是主从比例，比如这里的 1 表示的是主从比例是 1:1，什么概念呢？

也就是 1 个主节点对应几个从节点，现有 6 个实例，所以主从分配就是 3 个 master 主节点，3 个 slave 从节点。

主节点最少3个，3个才能保证集群的健壮性。

如果 –cluster-replicas 2 呢？

那么主从比例就是 1:2，也就是 1 个主节点对于应 2 个从节点。

即：3(master) + 6(slave) = 9个 Redis 实例。

如果不足 9个 Redis 实例，但是参数指定为 2 会怎么样？

报错信息如下：

提示已经很清楚了，Redis集群至少需要3个主节点。那么从节点就需要有6个，所以最后说：至少需要9个节点。

好的，至少3个主节点的要求我不继续刚了，但是我想4个主节点，2个从节点，这总该可以了吧？

4个主节点满足你：

1
2
bash复制代码# 进入一个启动的 reids 实例，这里以 redis-node1 实例为例
docker exec -it redis-node1 /bin/bash

执行组建集群的命令：

1
css复制代码redis-cli --cluster create 10.211.55.4:6379 10.211.55.4:6380 10.211.55.4:6381 10.211.55.4:6382  --cluster-replicas 0

指定4个没有从节点的主节点，这样你就有4个主节点了：

剩下的两个从节点怎么办呢？手动添加。

怎么添加？手动添加！

看到这些 master 节点的 id 了吗，只需要把 slave 指定给他们就可以了。

继续执行如下命令：

1
2
3
csharp复制代码redis-cli --cluster add-node 10.211.55.4:6383 10.211.55.4:6379  --cluster-slave --cluster-master-id b0c32b1dae9e7b7f7f4b74354c59bdfcaa46f30a

redis-cli --cluster add-node 10.211.55.4:6384 10.211.55.4:6379  --cluster-slave --cluster-master-id 111de8bed5772585cef5280c4b5225ecb15a582e

将两个 Redis 实例塞给其他主节点了：

最后我们进入 redis-cli，通过 cluster nodes 查看一下节点信息：

看到这，你学废了吗？再学不废，下期我可要录视频了。。。

本文首发于博客园：www.cnblogs.com/niceyoo/p/1…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

)​为什么呢～为什么呢～～

原因：

1、为了线程安全

2、因为要实现字符串池

什么是字符串池： java中的字符串池是存储在Java堆内存中的字符串池

)​

字符串池就像一个公共的大相册，每一个字符串就是一张照片，当你需要哪张照片的时候，发现相册里有这张照片，就可以直接拿过来用。如果相册中没有你想要的照片，你可以自己拍一张，然后把照片放到相册中（放到字符串池），自己和其他人都可以拿来用了。

3、为了实现String可以创建HashCode不可变性

正文开始

我们先来看一下String的源码（万物皆可看源码～～）

​

可以看到，String是被final修饰的类，那final是干什么的呢？

  • 首先你要理解final的用途，在分析String为什么要用final修饰，final可以修饰类，方法和变量，并且被修饰的类或方法，被final修饰的类不能被继承，即它不能拥有自己的子类，被final修饰的方法不能被重写， final修饰的变量，无论是类属性、对象属性、形参还是局部变量，都需要进行初始化操作。
  • 在了解final的用途后，再看String为什么要被final修饰：主要是为了”安全性“和”效率“的缘故

final修饰的String，代表了String的不可继承性，final修饰的char[]代表了被存储的数据不可更改性。但是：虽然final代表了不可变，但仅仅是引用地址不可变，并不代表了数组本身不会变,请看下面图片

​

可能你会有这个疑问，final修饰的不是不可以改变吗！为什么用final修饰了一个数组 final int[] array = {1, 2, 3, 4, 5}; 还可以用修改数据？那String底层其实是数组，这还算不可变吗？

再举个例子～:

1
2
3
4
5
6
7
8
9
10
11
12
13
arduino复制代码//实例1
public static void main(String[] args) {
		final List<String> stringList = new ArrayList();
		stringList.add("a");
		stringList.add("b");
		System.out.println(stringList.toString());
	}

//实例2
public static void main(String[] args) {
		final List<String> stringList = new ArrayList();
		stringList = new ArrayList<>();
	}

  • 在实例1中，我们用final修饰了一个集合‘stringList’，并对集合进行add()操作，执行成功。
  • 在实例2中，我们对集合进行变更，执行失败。

原因：final修饰的集合‘stringList’是一个引用，而这个引用指向了‘stringList’，在往集合里添加数据的时候，并没有影响到‘stringList’引用地址。而当我们 stringList = new ArrayList<>(); 为什么就不可以了呢？ 因为这就相当于修改引用地址，是不可以的。final的意思是地址不能改，但是地址指向的内容可以改。

我们看一下上面的源码截图，在String的源码中是这样定义的：

1
arduino复制代码private final char value[];

数组是私有方法，所以起作用的还有private，正是因为两者保证了String的不可变性。

那么为什么保证String不可变呢,因为**只有当字符串是不可变的，字符串池才有可能实现（**跟我们文章开头举的例子一样，可以理解为一个缓存区，如果字符串可变，如果在其它地方也有引用，指向的引用发生了变更，会发生混乱）。字符串池的实现可以在运行时节约很多heap空间，因为不同的字符串变量都指向池中的同一个字符串。但如果字符串是可变的，那么String interning将不能实现，因为这样的话，如果变量改变了它的值，那么其它指向这个值的变量的值也会一起改变。

HashCode不可变性

因为字符串是不可变的，所以在它创建的时候HashCode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。

我们来实际看一下，是不是一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typescript复制代码public static void main(String[] args) {
		String a = "a";
		String b = "a";
		String c = new String("a");
		String d = new String("a");
		// 输出Hashcode
		System.out.println("a-hc :" + a.hashCode());
		System.out.println("b-hc :" + b.hashCode());
		System.out.println("c-hc :" + c.hashCode());
		System.out.println("d-hc :" + d.hashCode());
		// 输出引用地址
		printAddresses("a", a);
		printAddresses("b", b);
		printAddresses("c", c);
		printAddresses("d", d);

	}

输出结果

1
2
3
4
5
6
7
8
makefile复制代码a-hc :97
b-hc :97
c-hc :97
d-hc :97
a: 7aada3af8
b: 7aada3af8
c: 7aada3b28
d: 7aada3b40

我们看到，得出来的HashCode是一样的，但是为什么得出来的地址不一样？

扩展

因为直接定义的String m = “a”; 是储存在常量存储区中的字符串常量池中；而new String(“a”)是存储在堆中，所以地址不一样。

好了今天就讲到这里，本人水平一般，能力有限，如果有不足的地方，希望大家多多指点，我们一起进步！

本文也参考了文章：www.jianshu.com/p/9c7f5daac…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

现在很多公司都有做接口测试的要求，这时很多之前一直做功能测试的伙伴们就比较措手不及了，所以就需要来学习接口测试了，今天就给大家讲解一下接口测试的知识。

一、接口测试的意义

1、什么是接口测试呢？

接口测试是测试系统组件间接口的一种测试，接口测试主要用于检测外部系统与系统之间以及内部各个子系统之间的交互点联系，测试的重点是要检查数据的交换，传递和控制管理过程，以及系统间的相互逻辑依赖关系等。

2、那为什么要做接口测试呢？

（1）举个例子来说，就举大家都很熟悉的淘宝网来说吧，在淘宝网不断发展历史过程中，最先出现的是功能测试和性能测试，然后才是自动化测试，但测试技术发展到今天，淘宝网的架构已经不再是以前传统的 MVC 结构了，整个系统架构不断向着分布式、业务中心化和高可用性的方向发展，淘宝网现今的系统架构纷繁复杂，系统间的各种接口庞杂繁多，传统的功能测试、性能测试和自动化测试已经难以满足系统发展的需求，这时就迫切需要一种更加有效实用且可以持续进行的测试方式来保证整个系统架构的质量。

（2）接口测试就是在这种需求下应运而生，首先，随着系统复杂程度的不断上升，传统的测试方法测试成本急剧增加，测试效率且大幅下降（数据模型推算，底层的一个bug能够引发上层的 8 个左右bug，而且底层的bug很容易引起全网的宕机；相反的接口测试能够提供系统复杂度上升的情况下低成本高效率的解决方案。

（3）其次接口测试不同于传统开发的单元测试，接口测试是站在用户的角度对系统接口进行全面高效持续的检测测试。

（4）最后接口测试是自动化并且持续集成的，这也是为什么接口测试能够低成本高效率的根源。

（5）总之接口测试是保证高复杂性系统质量的内在要求和低成本的经济利益的驱动作用下的最佳解决方案，接口测试是一个完整的体系，也包括功能测试、性能测试

3）接口测试的适用范围

（1）接口测试一般应用于多系统间交互开发，或者拥有多个子系统的应用系统开发的测试。 接口测试适用于为其他系统提供服务的底层框架系统和中心服务系统，主要测试这些系统对外部提供的接口，验证其正确性和稳定性。接口测试同样适用于一个上层系统中的服务层接口，越往上层，其测试的难度越大。接口测试在淘宝网的应用是一个自下而上的发展过程。

（2）接口测试实施在多系统多平台的构架下，有着极为高效的成本收益比。接口测试天生为高复杂性的平台带来高效的缺陷检测和质量监督能力。平台越复杂，系统越庞大，做接口测试的效果就越明显。

二、做接口测试的目的

1、接口测试的战略方针

（1）接口测试的核心战略在于：以保证系统的正确和稳定为核心，以持续集成为手段，提高测试效率，提升用户体验，降低产品研发成本为目的。

（2）核心：保证系统的稳定质量管理的目标是保证系统的正确和稳定，接口测试作为软件质量管理的一部分也是能保证系统的正确和稳定的，更准确的说法是保证系统服务端的正确和稳定，一个系统的服务端，越接近底层，对系统的影响就越大，甚至有可能牵一发而动全身，服务端的一个缺陷可能会引起客户端的几个甚至十几个缺陷，更可怕的是服务端的缺陷有可能引起整个系统的崩溃，这对整个系统来说，损失将是不可估量的，因此服务端接口的质量将直接影响到系统的正确和稳定。

（3）手段：持续集成什么是以持续集成为手段，关键在于“持续构建”、“业务”、“集成化”以及“文档体系”，我们需要让被测代码进行持续构建集成，我们需要用业务化的思维去考虑接口定义的合理性，我们需要从性能、安全的角度去思考代码的正确性，我们还需要从集成化的角度去甄别接口间数据传递的正确性，我们更需要确定我们的测试范围，也就是我们要测什么、不要测什么。

（3）目的：提高测试效率，提升用户体验，降低产品研发成本，接口测试要为代码的编写保驾护航，增强开发人员和测试人员的自信，让隐含的BUG提前暴露出来，要让开发人员在第一时间修复 BUG，要让功能测试人员和性能测试人员在测试的时候更加顺手，最大限度减少底层 BUG 的出现数量，要让产品研发的流程更加敏捷，要缩短产品的研发周期，最后在产品上线以后，要让用户用得更加顺畅，同时也要让用户感觉产品服务零缺陷。

（4）另外在这个战略过程中，我们需要几类资源作为支撑，下面做简单描述。 首先在这个战略中最重要的一点是要强调团队的重要性，特别是团队中需要有合理的人力资源配置，在这个团队中，需要全才，也需要专才，需要技术专家，也需要业务专家，既需要高效的执行者，也需要有效的管理者，任何人在这个团队中都可以发挥重要作用。

（5）其次要充分重视文档的重要性，包括需求文档，开发技术方案，测试技术方案，测试用例文档等等，完善这些文档可以大大减少软件工程周期中各个团队配合障碍，也可以降低后期软件维护成本。

（6）因此贯彻和落实接口测试的战略可以最大程度地提高软件质量的稳定性。

2、接口测试的各阶段发展和目标

简要讲述一个接口测试团队从建立初期到发展起来经历了哪些阶段，以及我们期望将来做成什么样子。

（1）摸索阶段：一个全新的团队在成立之初一般都会经历一个比较长期的摸索过程，在这个阶段内我们会尝试不同的技术、框架和流程规范。直到在这些方面都找到了比较适合团队自身特点的方案了， 那么这个阶段的目标就算是达到了。

（2）稳定提高阶段： 摸索阶段过后就应该会进入一个稳定提高期，经历了摸索阶段过后，团队的技术、框架和流程规范都应该有了一个基本的定型。这个时候团队的目标就是通过不同的项目实践来不断优化这些定型后的东西，最终总结出一套最佳方案出来。这套方案应该能够成为其它项目测试活动的参照，甚至是依据标准。这个时候呢，我们会发现所有的项目都在有序、统一、高效、可靠的进行。

（3）扩大影响，组织共赢阶段 ：那么到达上面这个目标之后是不是就是接口测试团队的终点呢？显然不是的，不要忘了，到目前为止，无论你在接口测试的工作上做得再好，那也仅仅只局限在接口测试本身上而已，我们不应该满足于此。通常来说接口测试团队在整个质量保证团队中占据了众多的核心技术人员。他们擅长使用各种技术来解决问题，甚至比开发团队做得还还要好。拥有如此多的技术资源， 如果我们不懂得合理利用，那真的是一种很大的浪费。在做好接口测试本身的基础上，我们还应该积极了解其它测试团队面临哪些问题，这些问题是不是可以利用技术手段来解决，如果可以，我们是否可以为他们实现一些实用的工具来帮助他们解决问题或者提高工作效率；我们自己的技术是否有需要分享给其它测试团队，甚至是整个软件团队，以帮助他们更好地完成工作。总之，我们应该思考如何更有效、更合理地利用接口测试团队的资源，来提高整个测试团队的业绩，这不仅会扩大接口测试团队本身的影响力，还让接口测试团队成为整个部门的核心竞争力，同时它还能创造了一个共赢的局面。

（4）另一方面，在工作的流程上，各个测试角色是可以互补的，接口测试的设计、测试用例可以跟功能和性能测试共享，接口测试的报告可以作为功能测试的重要参考，让其了解底层都经历了哪些测试，哪里是 bug 的密集区，哪里相对安全一些。在功能测试工程师找到 bug 之后， 接口测试工程师可以用代码直接覆盖这个 bug 产生的代码，使这个 bug 永远不会出现第二次。 接口测试人员还可以直接绕过页面，对底层系统进行性能和压力的测试，在测试过程中各个角色之间的密切配合，也减少了测试的成本，提供系统全方位的质量保障。

三、接口测试的工具

接口测试的工具：apipost、jmeter

apipost是国产的主要针对的接口测试和接口文档生成的工具

jmeter怎是一个很好的性能测试工具，主要针对性能测试中的压力测试等

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

广告、增值服务、佣金，是互联网企业最常见的三种盈利手段。在这3大经典中，又以广告所占的市场份额最大，几乎是绝大部分互联网平台最主要的营收途径，业务的重要性不言而喻。

从技术角度来说，广告业务涉及到 AI算法、大数据处理、检索引擎、高性能和高可用的工程架构 等多个方向，同样有着不错的技术吸引力。

我从去年开始接触广告业务，到现在差不多一年时间了。这篇文章将结合我的个人经验，同时参考业界的优秀案例，阐述下广告系统的架构实践方案，希望让大家有所收获。内容包括以下3部分：

  • 广告业务简介
  • 面临的技术挑战
  • 广告系统架构详解

01 广告业务简介

广告，可以说无处不在。微信、抖音、B站、百度、淘宝等等，这些占据用户时间最长的 APP， 到处都能看到广告的影子。

我们每天随处可见的广告，它背后的业务逻辑到底是什么样的呢？在分享广告系统的架构之前，先给大家快速普及下业务知识。

1.1 广告业务的核心点是平衡

为什么说广告业务的核心点是「平衡」？可以从广告的标准定义来理解。

广告被定义为：广告主以付费方式通过互联网平台向用户传播商品或者服务信息的手段。这个定义中涉及到 广告主、平台、用户3个主体，但是这3个主体的利益关注点各不相同。

  • 广告主：关注ROI，花了钱是否能带来预期收益
  • 平台：拥有流量，关注收益能否最大化
  • 用户：关注体验，广告是否足够精准？是否影响到了正常功能的使用？

有时候这三者的利益是冲突的，比如平台增加了广告位数量，收益肯定增加，但用户体验可能变差，因此广告业务最终要寻找的是三方的平衡。

站在平台的角度来看广告业务，它在保证用户体验的同时，要兼顾绝大部分广告主的ROI（确保他们是可以赚到钱的），在此基础上再考虑将平台的收入最大化，这样才是一个健康的广告生态。

1.2 从收入的分解公式认清广告的本质

广告业务发展了几十年，广告费用的结算方式也诞生了很多种，我们最常见的有以下几种：

  • CPT：按时间计费，独占性包时段包位置
  • CPM：按照每千次曝光计费
  • CPC：按照点击计费
  • CPA：按照行为计费（比如下载、注册等）

之所以有不同的结算方式，其实也是随着广告市场的发展逐渐衍生出来的，最开始流量稀缺，平台占优势，再到今天逐渐成了买方市场，广告主作为需求方的谈判权变大。

上面这个图可以看出，由于CPA代表了广告主最终想要的转化效果，因此按CPA结算时对广告主最有利，但是对平台最不利。结算方式演进到今天，其实也是一种平衡，所以处于平衡点附近的CPM和CPC是最常见的结算方式。

以CPC为例，收入可分解成下面这个公式：

其中，PV表示系统的访问量，PVR和ASN表示广告的填充率，CTR表示广告的点击率，ACP表示广告的平均点击价格。

上述各个指标都可以通过一系列的广告策略来提升。 比如填充率可通过开发更多的广告主来实现， CTR可通过AI算法做到精准投放来提升， ACP可通过精准流量溢价或者提升广告主ROI来完成。

掌握上面这个收入分解公式，对于理解广告业务至关重要，任何业务上的动作几乎都能关联到这个公式的某个指标上。

1.3 广告的核心业务流程

广告业务发展到今天，随着广告主对投放效果的诉求不断加强，精准定向以及实时竞价是目前最主流的业务形态。

对互联网平台来说，初期一般都是采用「 自营的竞价广告网络 」来实现商业变现，简单理解：就是利用平台自有的流量以及自主开发的广告主来实现业务闭环。 本文所分享的广告架构主要针对这种业务形态 ，它的核心业务流程如下图所示。

  • 广告主先通过投放平台发布广告，可设置一系列的定向条件，比如投放城市、投放时间段、人群标签、出价等。
  • 投放动作完成后，广告会被存放到广告库、同时进入索引库，以便能被广告检索引擎召回。
  • C端请求过来后，广告引擎会完成召回、算法策略、竞价排序等一系列的逻辑，最终筛选出Top N个广告，实现广告的千人千面。
  • 用户点击广告后，会触发广告扣费流程，这时候平台才算真正获得收益。

上面是广告业务的核心流程，随着平台流量以及广告主规模进一步增大，往往会从「自营型竞价网络」逐渐向「联盟广告以及RTB实时竞价」方向发展，类似于阿里妈妈、 腾讯广点通、头条巨量引擎，此时业务复杂度和技术架构会再上一个台阶，本文不作展开，后续再跟大家详细分享。

02 面临的技术挑战

对广告业务有了初步了解后，再来看下广告系统面临的技术挑战：

1、高并发：广告引擎和C端流量对接，请求量大（平峰往往有上万QPS），要求实时响应，必须在几十毫秒内返回结果。

2、业务逻辑复杂：一次广告请求，涉及到多路召回、算法模型打分、竞价排序等复杂的业务流程，策略多，执行链路长。

3、稳定性要求高：广告系统直接跟收入挂钩，广告引擎以及计费平台等核心系统的稳定性要求很高，可用性至少要做到3个9。

4、大数据存储和计算：随业务发展，推广数量以及扣费订单数量很容易达到千万甚至上亿规模，另外收入报表的聚合维度多，单报表可能达到百亿级别的记录数。

5、账务的准确性：广告扣费属于金融性质的操作，需要做到不丢失、不重复，否则会损害某一方的利益。另外，如果收入数据不准确，还可能影响到业务决策。

03 广告系统架构详解

了解了广告业务的目标和技术挑战后，接下来详细介绍下广告系统的整体架构和技术方案。

上面是我们公司目前的广告系统架构图，这个架构适用于广告业务初期，针对的是「自营型的竞价网络和站内流量」，不涉及联盟广告。

下面针对各个子系统做下说明：

  • 广告投放系统：供广告主使用，核心功能包括会员续费、广告库管理、设定推广条件、设置广告出价、查看投放效果等。
  • 广告运营后台：供平台的产品运营使用，核心功能包括广告位管理、广告策略管理、以及各种运营工具。
  • 广告检索平台：承接C端的高并发请求，负责从海量广告库中筛选出几个或者几十个广告，实时性要求高，这个平台通常由多个微服务组成。
  • AB实验平台：广告业务的稳定器，任何广告策略上的调整均可以通过此平台进行灰度实验，观察收入指标的变化。
  • 广告计费平台：面向C端，负责实时扣费，和收入直接挂钩，可用性要求高。
  • 账务管理中心：广告业务中的财务系统，统管金额相关的业务，包括充值、冻结、扣费等。
  • 大数据平台：整个广告系统的底盘，需要聚合各种异构数据源，完成离线和实时数据分析和统计，产出业务报表，生产模型特征等。

3.1 广告数据的存储

广告系统要存储的数据多种多样，特点各不相同，采用的是多模的数据存储方式。

  • OLTP场景，包括广告库、创意库、会员库、广告产品库、广告策略库等，这些都存储在MySQL中，数据规模较大的广告库和创意库，按照广告主ID Hash做分库分表。
  • OLAP场景，涉及到非常多的报表，聚合维度多，单表的记录数可能达到百亿级别，底层采用HDFS和HBase存储。
  • 面向广告检索场景的索引数据，包括正排索引和倒排索引，采用Redis和ES来存储。

存储上还需要解决的一个问题是：广告的同步问题。广告投放完成后，首先会存储在MySQL数据库中，接下来需要把广告实时传输到检索系统中，完成正排索引以及倒排索引的更新。

索引更新服务，有几个要点说明下：

  • 各个业务系统在推广、余额等信息变更时，发MQ消息，索引更新服务订阅MQ来感知变化，完成增量同步。
  • 变更的消息体中，不传递实际变更的字段，仅通知有变化的广告ID，索引更新服务实时读取最新数据完成更新，这样可以有效的解决消息乱序引起的数据不一致问题。
  • 当更新索引的并发达到一定量级后，可通过合并相同广告的变更、或者将倒排和正排更新分离的方式来提升整体的更新速度。

3.2 广告检索平台的整体流程

广告检索平台负责承接C端的流量请求，从海量广告库中筛选出最合适的前N个广告，并在几十毫秒内返回结果，它是一个多级筛选和排序的过程。

Recall层侧重算法模型，Search层侧重业务。从下到上，计算复杂度逐层增加，候选集逐层减少。（说明：搜索广告场景和推荐广告场景在某些子模块上存在差异，但整体流程基本一致，这里不作展开）

性能设计是检索平台的重点，通常有以下手段：

  • 做好服务分层，各层均可水平扩展。
  • 采用Redis缓存，避免高并发请求直接打到数据库，缓存可按业务规划多套，进行分流。
  • 采用多线程并行化某些子流程，比如多路召回逻辑、多模型打分逻辑。
  • 热点数据进行本地缓存，比如广告位的配置信息以及策略配置信息，在服务启动时就可以预加载到本地，然后定时进行同步。
  • 非核心流程设置超时熔断走降级逻辑，比如溢价策略（不溢价只是少赚了，不影响广告召回）。
  • 和主流程无关的逻辑异步执行，比如扣费信息缓存、召回结果缓存等。
  • 精简RPC返回结果或者Redis缓存对象的结构，去掉不必要的字段，减少IO数据包大小。
  • GC优化，包括JVM堆内存的设置、垃圾收集器的选择、GC频次优化和GC耗时优化。

3.3 计费平台的技术方案

计费平台也是一个核心系统，主要完成实时扣费功能。比如CPC结算方式下，广告主设置的预算是50元，每次点击扣1元，当扣费金额达到预算时，需要将广告及时下线。

除此之外，计费平台还需要支持CPM、CPT等多种结算方式，以及支持反作弊、余额撞线处理、扣费订单的摊销和对账等功能。

计费平台的特点是：并发高、数据量大、同时可用性要求高，需要做到不少扣，不重复扣。下面以CPC实时点击扣费为例，详细说下技术方案。

首先，整个扣费流程做了异步化处理，当收到实时扣费请求后，系统先将扣费时用到的信息缓存到Redis，然后发送MQ消息，这两步完成后扣费动作就算结束了。

这样做的好处是：能确保扣费接口的性能，同时利用MQ的可靠性投递和重试机制确保整个扣费流程的最终一致性。

为了提高可用性，针对Redis和MQ不可用的情况均采用了降级方案。Redis不可用时，切换到TiKV进行持久化；MQ投递失败时，改成线程池异步处理。

另外，每次有效点击都需要生成1条扣费订单，面临大数据量的存储问题。目前我们采用的是MySQL分库分表，后期会考虑使用HBase等分布式存储。另外，订单和账务系统之间的数据一致性，采用大数据平台做天级别的增量抽取，通过Hive任务完成对账和监控。

3.4 OLAP海量数据报表的技术方案

数据报表是也是广告平台的核心业务，它是广告主、平台运营人员进行投放优化、业务决策的依据。 先来看下广告数据仓库的分层结构：

  • 源数据层：对应各种源数据，包括HDFS中实时采集的前后端日志，增量或者全量同步的MySQL业务数据表。
  • 数据仓库层：包含维度表和事实表，通常是对源数据进行清洗后的数据宽表，比如行为日志表、推广宽表、用户宽表等。
  • 数据集市层：对数据进行轻粒度的汇总表，比如广告效果表、用户行为的全链路表、用户群分析表等。
  • 数据应用层：上层应用场景直接使用的数据表，包括多维分析生成的各种收入报表、Spark任务产出的算法模型特征和画像数据等。

采用这样的分层结构，和软件分层思想类似，提高了数据的维护性和复用性。

再来看应用层报表部分面临的挑战： 聚合维度多， 需要分时、分广告位、分推广等几十个维度； 单表最大达到百亿级别；支持时间范围的实时查询。

这部分由公司的大数据部门维护，采用了开源的技术方案，离线部分使用Kylin，数据存储在HBase中；实时部分使用Flink和Spark Streaming，数据存储在Druid中。

写在最后

本文详细介绍了广告系统的初期架构和核心技术方案。随着业务演进，架构也会随之变得更加复杂，但是 大数据存储、高并发、高可用，始终是广告业务的技术难点 。

关于广告系统的稳定性保障、广告策略的可扩展性设计、RTB实时竞价的系统架构等有价值的内容，后续再分享给大家，欢迎关注我的公号。 针对本篇文章，如果有任何疑问或者建议，可以留言讨论 。

作者简介：985硕士，前亚马逊工程师，现58转转技术总监

欢迎关注我的个人公众号：IT人的职场进阶，精彩原创不断！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

前言

如果有些朋友以前没有使用过java8 stream这种链式编程方式做开发，想学习一下。
如果有些朋友只学习了一部分用法，想学习更多。
如果有些朋友想看看有没有好的示例适用于实际工作当中。
那么恭喜你，这篇文章非常适合你。

首先，我们一起看看stream的继承关系：

Stream、IntStream、LongStream、DoubleStream的父接口都是BaseStream。BaseStream的四个子接口方法都差不多，只是IntStream、LongStream、DoubleStream直接存储基本类型，可以避免自动装/拆箱，效率会更高一些。但是，我们实际上使用Stream更多一些。

我们再看看stream的工作流程图：

为什么要学stream的链式编程方式

业务需求1：指定一个字符串数组，找出里面相同的元素，并且统计重复的次数。

我们以前大概是这样做的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码public class CountTest {

    @Test
      public void testCount1() {
        List<String> list = Lists.newArrayList("a", "b", "ab", "abc", "a", "ab", "a", "abcd", "bd", "abc");

        Map<String, Long> countMap = new HashMap<>();
        for (String data : list) {
            Long aLong = countMap.get(data);
            if (Objects.isNull(aLong)) {
                countMap.put(data, 1L);
            } else {
                countMap.put(data, ++aLong);
            }
        }

        countMap.forEach((key, value) -> System.out.println("key:" + key + " value:" + value));
    }
}

执行结果：

1
2
3
4
5
6
java复制代码key:a value:3
key:ab value:2
key:b value:1
key:bd value:1
key:abc value:2
key:abcd value:1

我们再看看如果用java8的stream可以怎么做：

1
2
3
4
5
6
7
8
9
java复制代码public class CountTest {

    @Test
    public void testCount2() {
     List<String> list = Lists.newArrayList("a", "b", "ab",      "abc", "a", "ab", "a", "abcd", "bd", "abc");
        Map<String, Long> countMap =         list.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        countMap.forEach((key, value) ->         System.out.println("key:" + key + " value:" + value));
    }
}

执行结果：

1
2
3
4
5
6
makefile复制代码key:a value:3
key:ab value:2
key:b value:1
key:bd value:1
key:abc value:2
key:abcd value:1

我们可以看到testCount1和testCount2执行结果相同，仅仅一行代码：

1
ini复制代码Map<String, Long> countMap = list.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

就可以实现上面testCount1中多行代码的逻辑。

业务需求2：从一个指定的字符串数组中，查找指定的字符串是否存在

我们以前大概是这样做的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ini复制代码public class FindTest {

    @Test
    public void testFind1() {
        String findStr = "bd";
        List<String> list = Lists.newArrayList("a", "b", "ab", "abc", "a", "ab", "a", "abcd", "bd", "abc");
        boolean match = false;
        for (String data : list) {
            if (data.equals(findStr)) {
                match = true;
                break;
            }
        }
        //结果：match:true
        System.out.println("match:" + match);
    }
}

我们再看看如果用java8的stream可以怎么做：

1
2
3
4
5
6
7
8
9
10
11
typescript复制代码public class MatchTest {

    @Test
    public void testFind2() {
        String findStr = "bd";
        List<String> list = Lists.newArrayList("a", "b", "ab", "abc", "a", "ab", "a", "abcd", "bd", "abc");
        boolean match = list.stream().anyMatch(x -> x.equals(findStr));
        //结果：match:true
        System.out.println("match:" + match);
    }
}

我们可以看到调用testFind1和testFind2方法执行结果也是一样的。但是，用java8 stream的语法，又只用一行代码就完成功能了，真棒。

java8 stream超详细用法指南

stream的操作符大体上分为两种：中间操作符和终止操作符

中间操作：

1.filter(T-> boolean)

过滤数据，保留 boolean 为 true 的元素，返回一个集合

1
2
3
4
5
6
7
8
9
10
java复制代码public class FilterTest {
    @Test
    public void testFilter() {
        List<Integer> list = Lists.newArrayList(20, 23, 25, 28, 30, 33, 37, 40);
        //从指定数据集合中过滤出大于等于30的数据集合
        List<Integer> collect = list.stream().filter(x -> x >= 30).collect(Collectors.toList());
        //结果：[30, 33, 37, 40]
        System.out.println(collect);
    }
}

collect(Collectors.toList())可以把流转换为 List 类型，collect实际上是一个终止操作。

2.map(T -> R)

转换操作符，可以做数据转换，比如：把字符串转换成int、long、double，或者把一个实体转换成另外一个实体。包含：map，mapToInt、mapToLong、mapToDouble

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
java复制代码public class MapTest {


    @Test
    public void testMap() {
        List<String> list = Lists.newArrayList("1", "2", "3", "4", "5", "6");
        List<Long> collect1 = list.stream().map(x -> Long.parseLong(x)).collect(Collectors.toList());
        //结果：[1, 2, 3, 4, 5, 6]
        System.out.println(collect1);

        //结果：111111
        list.stream().mapToInt(x -> x.length()).forEach(System.out::print);
        System.out.println("");

        //结果：111111
        list.stream().mapToLong(x -> x.length()).forEach(System.out::print);
        System.out.println("");

        //结果：1.01.01.01.01.01.0
        list.stream().mapToDouble(x -> x.length()).forEach(System.out::print);
    }
}

3.flatMap(T -> Stream)

将流中的每一个元素 T 映射为一个流，再把每一个流连接成为一个流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码public class FlatMapTest {

    @Test
    public void testFlatMap() {
        List<List<String>>  list = new ArrayList<List<String>>(){{
            add(Lists.newArrayList("a","b","c"));
            add(Lists.newArrayList("d","e","f"));
            add(Lists.newArrayList("j","k","y"));
        }};
        //结果：[[a, b, c], [d, e, f], [j, k, y]]
        System.out.println(list);
        List<String> collect = list.stream().flatMap(List::stream).collect(Collectors.toList());
        //结果：[a, b, c, d, e, f, j, k, y]
        System.out.println(collect);
    }
}

我们可以看到flatMap可以轻松把字符串的二维数据变成一位数组。

4.distinct

去重，类似于msql中的distinct的作用，底层使用了equals方法做比较。

1
2
3
4
5
6
7
8
9
10
java复制代码public class DistinctTest {

    @Test
    public void testDistinct() {
        List<String> list = Lists.newArrayList("a", "b", "ab", "abc", "a", "ab", "a", "abcd", "bd", "abc");
        List<String> collect = list.stream().distinct().collect(Collectors.toList());
        //结果：[a, b, ab, abc, abcd, bd]
        System.out.println(collect);
    }
}

其实，去重还有另外一种办法，可以用Collectors.toSet()，后面会讲到。

5.sorted

对元素进行排序，前提是实现Comparable接口，当然也可以自定义比较器。

1
2
3
4
5
6
7
8
9
10
java复制代码public class SortTest {

    @Test
    public void testSort() {
        List<Integer> list = Lists.newArrayList(5, 3, 7, 1, 4, 6);
        List<Integer> collect = list.stream().sorted((a, b) -> a.compareTo(b)).collect(Collectors.toList());
        //结果：[1, 3, 4, 5, 6, 7]
        System.out.println(collect);
    }
}

6.limit

限流操作，有点类似于mysql中的limit功能，比如：有10个元素，只取前面3个元素

1
2
3
4
5
6
7
8
9
10
java复制代码public class LimitTest {

    @Test
    public void testLimit() {
        List<String> list = Lists.newArrayList("a", "b", "ab", "abc", "a", "ab", "a", "abcd", "bd", "abc");
        List<String> collect = list.stream().limit(3).collect(Collectors.toList());
        //结果：[a, b, ab]
        System.out.println(collect);
    }
}

7.skip

跳过操作，比如：有个10个元素，从第5个元素开始去后面的元素

1
2
3
4
5
6
7
8
9
10
java复制代码public class SkipTest {

    @Test
    public void testSkip() {
        List<String> list = Lists.newArrayList("a", "b", "ab", "abc", "a", "ab", "a", "abcd", "bd", "abc");
        List<String> collect = list.stream().skip(5).collect(Collectors.toList());
        //结果：[ab, a, abcd, bd, abc]
        System.out.println(collect);
    }
}

8.peek

挑出操作，

1
2
3
4
5
6
7
8
java复制代码public class PeekTest {
    @Test
    public void testPeek() {
        List<String> list = Lists.newArrayList("a", "b", "ab", "abc", "a", "ab", "a", "abcd", "bd", "abc");
        //结果：abababcaabaabcdbdabc
        list.stream().peek(x -> x.toUpperCase()).forEach(System.out::print);
    }
}

眼尖的朋友会发现，进行x.toUpperCase()转换为大写功能，但是实际上没有生效。把peek改成map方法试试：

1
2
3
4
5
6
7
8
java复制代码public class PeekTest {
    @Test
    public void testPeek() {
        List<String> list = Lists.newArrayList("a", "b", "ab", "abc", "a", "ab", "a", "abcd", "bd", "abc");
        //结果：ABABABCAABAABCDBDABC
        list.stream().map(x -> x.toUpperCase()).forEach(System.out::print);
    }
}

我们可以看到，用map操作转换成大写功能生效了，但是用peek操作却没有生效。peek只是对Stream中的元素进行某些操作，但是操作之后的数据并不返回到Stream中，所以Stream中的元素还是原来的元素。

终止操作：

1.forEach

遍历操作，包含：forEach 和 forEachOrdered

forEach：支持并行处理

forEachOrdered：是按顺序处理的，遍历速度较慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
java复制代码public class ForEachTest {

    @Test
    public void testForEach() {
        List<String> list = Lists.newArrayList("a", "b", "ab");
        //结果：a b ab
        list.stream().forEach(x-> System.out.print(x+' '));
        System.out.println("");

        //可以简化
        //结果：a b ab
        list.forEach(x-> System.out.print(x+' '));
        System.out.println("");

        //结果：a b ab
        list.stream().forEachOrdered(x-> System.out.print(x+' '));
    }
}

2.collect

收集操作，将所有的元素收集起来，Collectors 提供了非常多收集器。包含：toMap、toSet、toList、joining，groupingBy，maxBy，minBy等操作。

toMap：将数据流转换为map，里面包含的元素是用key/value的形式的

toSet：将数据流转换为set，里面包含的元素不可重复

toList：将数据流转出为list，里面包含的元素是有序的

joining：拼接字符串

groupingBy：分组，可以将list转换map

couting：统计元素数量

maxBy：获取最大元素

minBy：获取最小元素

summarizingInt: 汇总int类型的元素，返回IntSummaryStatistics，再调用具体的方法对元素进行统计：getCount（统计数量），getSum（求和），getMin（获取最小值），getMax（获取最大值），getAverage（获取平均值）

summarizingLong：汇总long类型的元素，用法同summarizingInt

summarizingDouble：汇总double类型的元素，用法同summarizingInt

averagingInt：获取int类型的元素的平均值，返回一个double类型的数据

averagingLong：获取long类型的元素的平均值，用法同averagingInt

averagingDouble：获取double类型的元素的平均值，用法同averagingInt

mapping：获取映射，可以将原始元素的一部分内容作为一个新元素返回

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
java复制代码public class CollectTest {

    @Data
    @AllArgsConstructor
    class User {
        private String name;
        private Integer age;
    }


    @Test
    public void testCollect() {
        List<String> list0 = Lists.newArrayList("a", "b", "ab");
        Map<String, String> collect0 = list0.stream().collect(Collectors.toMap(String::new, Function.identity()));
        //结果：{ab=ab, a=a, b=b}
        System.out.println(collect0);

        List<String> list = Lists.newArrayList("a", "b", "ab", "a", "b", "ab");
        List<String> collect1 = list.stream().collect(Collectors.toList());
        //结果：[a, b, ab, a, b, ab]
        System.out.println(collect1);

        //结果：[a, ab, b]
        Set<String> collect2 = list.stream().collect(Collectors.toSet());
        System.out.println(collect2);

        String collect3 = list.stream().collect(Collectors.joining(","));
        //结果：a,b,ab,a,b,ab
        System.out.println(collect3);

        Map<String, List<String>> collect4 = list.stream().collect(Collectors.groupingBy(Function.identity()));
        //结果：{ab=[ab, ab], a=[a, a], b=[b, b]}
        System.out.println(collect4);

        Long collect = list.stream().collect(Collectors.counting());
        //结果：6
        System.out.println(collect);

        String collect5 = list.stream().collect(Collectors.maxBy((a, b) -> a.compareTo(b))).orElse(null);
        //结果：b
        System.out.println(collect5);

        String collect6 = list.stream().collect(Collectors.minBy((a, b) -> a.compareTo(b))).orElse(null);
        //结果：a
        System.out.println(collect6);

        List<String> list2 = Lists.newArrayList("2", "3", "5");
        IntSummaryStatistics summaryStatistics = list2.stream().collect(Collectors.summarizingInt(x -> Integer.parseInt(x)));
        long sum = summaryStatistics.getSum();
        //结果：10
        System.out.println(sum);

        Double collect7 = list2.stream().collect(Collectors.averagingInt(x -> Integer.parseInt(x)));
        //结果：3.3333333333333335
        System.out.println(collect7);

        List<User> userList = new ArrayList<User>() {{
            add(new User("jack",23));
            add(new User("james",30));
            add(new User("curry",28));
        }};
        List<String> collect8 = userList.stream().collect(Collectors.mapping(User::getName, Collectors.toList()));
        //[jack, james, curry]
        System.out.println(collect8);
    }
}

3.find

查找操作，包含：findFirst、findAny

findFirst：找到第一个，返回的类型为Optional

findAny：使用 stream() 时找到的是第一个元素，使用 parallelStream() 并行时找到的是其中一个元素，返回的类型为Optional

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
java复制代码public class FindOpTest {

    @Test
    public void testFindOp() {
        List<String> list = Lists.newArrayList("a", "b", "ab", "abc", "bc", "ab");
        //查找第一匹配的元素
        String data1 = list.stream().findFirst().orElse(null);
        //结果: a
        System.out.println(data1);

        String data2 = list.stream().findAny().orElse(null);
        //结果: a
        System.out.println(data2);
    }
}

4.match

匹配操作，包含：allMatch、anyMatch、noneMatch

allMatch：所有元素都满足条件，返回boolean类型

anyMatch：任意一个元素满足条件，返回boolean类型

noneMatch：所有元素都不满足条件，返回boolean类型

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
java复制代码public class MatchTest {

    @Test
    public void testMatch() {
        List<Integer> list = Lists.newArrayList(2, 3, 5, 7);
        boolean allMatch = list.stream().allMatch(x -> x > 1);
        //结果：true
        System.out.println(allMatch);

        boolean allMatch2 = list.stream().allMatch(x -> x > 2);
        //结果：false
        System.out.println(allMatch2);

        boolean anyMatch = list.stream().anyMatch(x -> x > 2);
        //结果：true
        System.out.println(anyMatch);

        boolean noneMatch1 = list.stream().noneMatch(x -> x > 5);
        //结果：false
        System.out.println(noneMatch1);

        boolean noneMatch2 = list.stream().noneMatch(x -> x > 7);
        //结果：true
        System.out.println(noneMatch2);
    }
}

5.count

统计操作，效果跟调用集合的size()方法类似

1
2
3
4
5
6
7
8
9
10
java复制代码public class CountOpTest {

    @Test
    public void testCountOp() {
        List<String> list = Lists.newArrayList("a", "b", "ab");
        long count = list.stream().count();
        //结果：3
        System.out.println(count);
    }
}

6.min、max

min：获取最小值，返回Optional类型的数据

max：获取最大值，返回Optional类型的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码public class MaxMinTest {

    @Test
    public void testMaxMin() {
        List<Integer> list = Lists.newArrayList(2, 3, 5, 7);
        Optional<Integer> max = list.stream().max((a, b) -> a.compareTo(b));
        //结果：7
        System.out.println(max.get());

        Optional<Integer> min = list.stream().min((a, b) -> a.compareTo(b));
        //结果：2
        System.out.println(min.get());
    }
}

7.reduce

规约操作，将整个数据流的值规约为一个值，count、min、max底层就是使用reduce。

reduce 操作可以实现从Stream中生成一个值，其生成的值不是随意的，而是根据指定的计算模型。

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
java复制代码public class ReduceTest {

    @Test
    public void testReduce() {
        List<Integer> list = Lists.newArrayList(2, 3, 5, 7);
        Integer sum1 = list.stream().reduce(0, Integer::sum);
        //结果：17
        System.out.println(sum1);

        Optional<Integer> reduce = list.stream().reduce((a, b) -> a + b);
        //结果：17
        System.out.println(reduce.get());

        Integer max = list.stream().reduce(0, Integer::max);
        //结果：7
        System.out.println(max);

        Integer min = list.stream().reduce(0, Integer::min);
        //结果：0
        System.out.println(min);


        Optional<Integer> reduce1 = list.stream().reduce((a, b) -> a > b ? b : a);
        //2
        System.out.println(reduce1.get());
    }
}

8.toArray

数组操作，将数据流的元素转换成数组。

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码public class ArrayTest {

    @Test
    public void testArray() {
        List<String> list = Lists.newArrayList("a", "b", "ab");
        String[] strings = list.stream().toArray(String[]::new);
        //结果：a b ab
        for (int i = 0; i < strings.length; i++) {
            System.out.print(strings[i]+" ");
        }
    }
}

stream和parallelStream的区别
stream：是单管道，称其为流，其主要用于集合的逻辑处理。

parallelStream：是多管道，提供了流的并行处理，它是Stream的另一重要特性，其底层使用Fork/Join框架实现

1
2
3
4
5
6
7
8
9
java复制代码public class StreamTest {

    @Test
    public void testStream() {
        List<Integer> list = Lists.newArrayList(1,2, 3,4, 5,6, 7);
        //结果：1234567
        list.stream().forEach(System.out::print);
    }
}
1
2
3
4
5
6
7
8
java复制代码public class ParallelStreamTest {
    @Test
    public void testParallelStream() {
        List<Integer> list = Lists.newArrayList(1,2, 3,4, 5,6, 7);
        //结果：5726134
        list.parallelStream().forEach(System.out::print);
    }
}

我们可以看到直接使用parallelStream的forEach遍历数据，是没有顺序的。

如果要让parallelStream遍历时有顺序怎么办呢？

1
2
3
4
5
6
7
8
9
java复制代码public class ParallelStreamTest {

    @Test
    public void testParallelStream() {
        List<Integer> list = Lists.newArrayList(1,2, 3,4, 5,6, 7);
        //结果：1234567
        list.parallelStream().forEachOrdered(System.out::print);
    }
}

parallelStream的工作原理：

实际工作中的案例

1.从两个集合中找相同的元素。一般用于批量数据导入的场景，先查询出数据，再批量新增或修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码public class WorkTest {

    @Test
    public void testWork1() {
        List<String> list1 = Lists.newArrayList("a", "b", "ab");
        List<String> list2 = Lists.newArrayList("a", "c", "ab");
        List<String> collect = list1.stream()
                .filter(x -> list2.stream().anyMatch(e -> e.equals(x)))
                .collect(Collectors.toList());
        //结果：[a, ab]
        System.out.println(collect);

    }
}

2.有两个集合a和b，过滤出集合a中有，但是集合b中没有的元素。这种情况可以使用在假如指定一个id集合，根据id集合从数据库中查询出数据集合，再根据id集合过滤出数据集合中不存在的id，这些id就是需要新增的。

1
2
3
4
5
6
7
8
9
10
java复制代码@Test
public void testWork2() {
    List<String> list1 = Lists.newArrayList("a", "b", "ab");
    List<String> list2 = Lists.newArrayList("a", "c", "ab");
    List<String> collect = list1.stream()
      .filter(x -> list2.stream().noneMatch(e -> e.equals(x)))
      .collect(Collectors.toList());
    //结果：[b]
    System.out.println(collect);
}

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
java复制代码  @AllArgsConstructor
  @Data
  class User {
      private String name;
      private Integer age;
  }

  @Test
  public void testWork3() {
      List<User> userList = new ArrayList<User>() {{
          add(new User("jack",23));
          add(new User("james",30));
          add(new User("curry",28));
          add(new User("tom",27));
          add(new User("sue",29));
      }};

      List<String> collect = userList.stream()
              .filter(x -> x.getAge() > 27)
              .sorted((a, b) -> a.getAge().compareTo(b.getAge()))
              .limit(2)
              .map(User::getName)
              .collect(Collectors.toList());
      //结果：[curry, sue]
      System.out.println(collect);
  }

4.统计指定集合中，姓名相同的人中年龄最小的年龄

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码@Test
public void testWork4() {
    List<User> userList = new ArrayList<User>() {{
        add(new User("tom", 23));
        add(new User("james", 30));
        add(new User("james", 28));
        add(new User("tom", 27));
        add(new User("sue", 29));
    }};

    userList.stream().collect(Collectors.groupingBy(User::getName))
            .forEach((name, list) -> {
                User user = list.stream().sorted((a, b) -> a.getAge().compareTo(b.getAge())).findFirst().orElse(null);
                //结果：name:sue,age:29
                //     name:tom,age:23
                //     name:james,age:28
                System.out.println("name:" + name + ",age:" + user.getAge());
            });
}

最后说一句(求关注，别白嫖我)

如果这篇文章对您有所帮助，或者有所启发的话，帮忙关注一下，您的支持是我坚持写作最大的动力。

求一键三连：点赞、转发、在看。

此外关注公众号：【苏三说技术】，在公众号中回复：面试、代码神器、开发手册、时间管理有超赞的粉丝福利，另外回复：加群，可以跟很多BAT大厂的前辈交流和学习。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

作者：小傅哥

博客：https://bugstack.cn

Github：https://github.com/fuzhengwei/CodeGuide/wiki

沉淀、分享、成长，让自己和他人都能有所收获！😄

一、前言

人看手机，机器学习！

正好是2020年，看到这张图还是蛮有意思的。以前小时候总会看到一些科技电影，讲到机器人会怎样怎样，但没想到人似乎被娱乐化的东西，搞成了低头族、大肚子！

当意识到这一点时，其实非常怀念小时候。放假的早上跑出去，喊上三五个伙伴，要不下河摸摸鱼、弹弹玻璃球、打打pia、跳跳房子！一天下来真的不会感觉累，但现在如果是放假的一天，你的娱乐安排，很多时候会让头很累！

就像，你有试过学习一天英语头疼，还是刷一天抖音头疼吗？或者玩一天游戏与打一天球！如果你意识到了，那么争取放下一会手机，适当娱乐，锻炼保持个好身体！

二、面试题

谢飞机，小记！，上次吃亏在线程上，这次不会一次坑掉两次吧！

谢飞机：你问吧，我准备好了！！！

面试官：嗯，线程池状态是如何设计存储的？

谢飞机：这！下一个，下一个！

面试官：Worker 的实现类，为什么不使用 ReentrantLock 来实现呢，而是自己继承AQS？

谢飞机：我…！

面试官：那你简述下，execute 的执行过程吧！

谢飞机：再见！

三、线程池讲解

1. 先看个例子

1
2
3
4
5
6
7
8
9
10
java复制代码ThreadPoolExecutor threadPoolExecutor = new ThreadPoolExecutor(10, 10, 0L, TimeUnit.MILLISECONDS, new ArrayBlockingQueue<>(10));
threadPoolExecutor.execute(() -> {
    System.out.println("Hi 线程池！");
});
threadPoolExecutor.shutdown();

// Executors.newFixedThreadPool(10);
// Executors.newCachedThreadPool();
// Executors.newScheduledThreadPool(10);
// Executors.newSingleThreadExecutor();

这是一段用于创建线程池的例子，相信你已经用了很多次了。

线程池的核心目的就是资源的利用，避免重复创建线程带来的资源消耗。因此引入一个池化技术的思想，避免重复创建、销毁带来的性能开销。

那么，接下来我们就通过实践的方式分析下这个池子的构造，看看它是如何处理线程的。

2. 手写一个线程池

2.1 实现流程

为了更好的理解和分析关于线程池的源码，我们先来按照线程池的思想，手写一个非常简单的线程池。

其实很多时候一段功能代码的核心主逻辑可能并没有多复杂，但为了让核心流程顺利运行，就需要额外添加很多分支的辅助流程。就像我常说的，为了保护手才把擦屁屁纸弄那么大！

图 21-1 线程池简化流程

关于图 21-1，这个手写线程池的实现也非常简单，只会体现出核心流程，包括：

  1. 有n个一直在运行的线程，相当于我们创建线程池时允许的线程池大小。
  2. 把线程提交给线程池运行。
  3. 如果运行线程池已满，则把线程放入队列中。
  4. 最后当有空闲时，则获取队列中线程进行运行。

2.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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
java复制代码public class ThreadPoolTrader implements Executor {

    private final AtomicInteger ctl = new AtomicInteger(0);

    private volatile int corePoolSize;
    private volatile int maximumPoolSize;

    private final BlockingQueue<Runnable> workQueue;

    public ThreadPoolTrader(int corePoolSize, int maximumPoolSize, BlockingQueue<Runnable> workQueue) {
        this.corePoolSize = corePoolSize;
        this.maximumPoolSize = maximumPoolSize;
        this.workQueue = workQueue;
    }

    @Override
    public void execute(Runnable command) {
        int c = ctl.get();
        if (c < corePoolSize) {
            if (!addWorker(command)) {
                reject();
            }
            return;
        }
        if (!workQueue.offer(command)) {
            if (!addWorker(command)) {
                reject();
            }
        }
    }

    private boolean addWorker(Runnable firstTask) {
        if (ctl.get() >= maximumPoolSize) return false;

        Worker worker = new Worker(firstTask);
        worker.thread.start();
        ctl.incrementAndGet();
        return true;
    }

    private final class Worker implements Runnable {

        final Thread thread;
        Runnable firstTask;

        public Worker(Runnable firstTask) {
            this.thread = new Thread(this);
            this.firstTask = firstTask;
        }

        @Override
        public void run() {
            Runnable task = firstTask;
            try {
                while (task != null || (task = getTask()) != null) {
                    task.run();
                    if (ctl.get() > maximumPoolSize) {
                        break;
                    }
                    task = null;
                }
            } finally {
                ctl.decrementAndGet();
            }
        }

        private Runnable getTask() {
            for (; ; ) {
                try {
                    System.out.println("workQueue.size：" + workQueue.size());
                    return workQueue.take();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    private void reject() {
        throw new RuntimeException("Error！ctl.count：" + ctl.get() + " workQueue.size：" + workQueue.size());
    }

    public static void main(String[] args) {
        ThreadPoolTrader threadPoolTrader = new ThreadPoolTrader(2, 2, new ArrayBlockingQueue<Runnable>(10));

        for (int i = 0; i < 10; i++) {
            int finalI = i;
            threadPoolTrader.execute(() -> {
                try {
                    Thread.sleep(1500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("任务编号：" + finalI);
            });
        }
    }

}

// 测试结果

任务编号：1
任务编号：0
workQueue.size：8
workQueue.size：8
任务编号：3
workQueue.size：6
任务编号：2
workQueue.size：5
任务编号：5
workQueue.size：4
任务编号：4
workQueue.size：3
任务编号：7
workQueue.size：2
任务编号：6
workQueue.size：1
任务编号：8
任务编号：9
workQueue.size：0
workQueue.size：0

以上，关于线程池的实现还是非常简单的，从测试结果上已经可以把最核心的池化思想体现出来了。主要功能逻辑包括：

  • ctl，用于记录线程池中线程数量。
  • corePoolSize、maximumPoolSize，用于限制线程池容量。
  • workQueue，线程池队列，也就是那些还不能被及时运行的线程，会被装入到这个队列中。
  • execute，用于提交线程，这个是通用的接口方法。在这个方法里主要实现的就是，当前提交的线程是加入到worker、队列还是放弃。
  • addWorker，主要是类 Worker 的具体操作，创建并执行线程。这里还包括了 getTask() 方法，也就是从队列中不断的获取未被执行的线程。

好，那么以上呢，就是这个简单线程池实现的具体体现。但如果深思熟虑就会发现这里需要很多完善，比如：线程池状态呢，不可能一直奔跑呀！？、线程池的锁呢，不会有并发问题吗？、线程池拒绝后的策略呢？，这些问题都没有在主流程解决，也正因为没有这些流程，所以上面的代码才更容易理解。

接下来，我们就开始分析线程池的源码，与我们实现的简单线程池参考对比，会更加容易理解😄！

3. 线程池源码分析

3.1 线程池类关系图

图 21-2 线程池类关系图

以围绕核心类 ThreadPoolExecutor 的实现展开的类之间实现和继承关系，如图 21-2 线程池类关系图。

  • 接口 Executor、ExecutorService，定义线程池的基本方法。尤其是 execute(Runnable command) 提交线程池方法。
  • 抽象类 AbstractExecutorService，实现了基本通用的接口方法。
  • ThreadPoolExecutor，是整个线程池最核心的工具类方法，所有的其他类和接口，为围绕这个类来提供各自的功能。
  • Worker，是任务类，也就是最终执行的线程的方法。
  • RejectedExecutionHandler，是拒绝策略接口，有四个实现类；AbortPolicy(抛异常方式拒绝)、DiscardPolicy(直接丢弃)、DiscardOldestPolicy(丢弃存活时间最长的任务)、CallerRunsPolicy(谁提交谁执行)。
  • Executors，是用于创建我们常用的不同策略的线程池，newFixedThreadPool、newCachedThreadPool、newScheduledThreadPool、newSingleThreadExecutor。

3.2 高3位与低29位

图 22-3 线程状态，高3位与低29位

1
2
3
4
5
6
7
8
9
java复制代码private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0));
private static final int COUNT_BITS = Integer.SIZE - 3;
private static final int CAPACITY   = (1 << COUNT_BITS) - 1;

private static final int RUNNING    = -1 << COUNT_BITS;
private static final int SHUTDOWN   =  0 << COUNT_BITS;
private static final int STOP       =  1 << COUNT_BITS;
private static final int TIDYING    =  2 << COUNT_BITS;
private static final int TERMINATED =  3 << COUNT_BITS;

在 ThreadPoolExecutor 线程池实现类中，使用 AtomicInteger 类型的 ctl 记录线程池状态和线程池数量。在一个类型上记录多个值，它采用的分割数据区域，高3位记录状态，低29位存储线程数量，默认 RUNNING 状态，线程数为0个。

3.2 线程池状态

图 22-4 线程池状态流转

图 22-4 是线程池中的状态流转关系，包括如下状态：

  • RUNNING：运行状态，接受新的任务并且处理队列中的任务。
  • SHUTDOWN：关闭状态(调用了shutdown方法)。不接受新任务，,但是要处理队列中的任务。
  • STOP：停止状态(调用了shutdownNow方法)。不接受新任务，也不处理队列中的任务，并且要中断正在处理的任务。
  • TIDYING：所有的任务都已终止了，workerCount为0，线程池进入该状态后会调 terminated() 方法进入TERMINATED 状态。
  • TERMINATED：终止状态，terminated() 方法调用结束后的状态。

3.3 提交线程(execute)

图 22-5 提交线程流程图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码public void execute(Runnable command) {
    if (command == null)
        throw new NullPointerException();
    int c = ctl.get();
    if (workerCountOf(c) < corePoolSize) {
        if (addWorker(command, true))
            return;
        c = ctl.get();
    }
    if (isRunning(c) && workQueue.offer(command)) {
        int recheck = ctl.get();
        if (! isRunning(recheck) && remove(command))
            reject(command);
        else if (workerCountOf(recheck) == 0)
            addWorker(null, false);
    }
    else if (!addWorker(command, false))
        reject(command);
}

在阅读这部分源码的时候，可以参考我们自己实现的线程池。其实最终的目的都是一样的，就是这段被提交的线程，启动执行、加入队列、决策策略，这三种方式。

  • ctl.get()，取的是记录线程状态和线程个数的值，最终需要使用方法 workerCountOf()，来获取当前线程数量。`workerCountOf 执行的是 c & CAPACITY 运算
  • 根据当前线程池中线程数量，与核心线程数 corePoolSize 做对比，小于则进行添加线程到任务执行队列。
  • 如果说此时线程数已满，那么则需要判断线程池是否为运行状态 isRunning(c)。如果是运行状态则把不能被执行的线程放入线程队列中。
  • 放入线程队列以后，还需要重新判断线程是否运行以及移除操作，如果非运行且移除，则进行拒绝策略。否则判断线程数量为0后添加新线程。
  • 最后就是再次尝试添加任务执行，此时方法 addWorker 的第二个入参是 false，最终会影响添加执行任务数量判断。如果添加失败则进行拒绝策略。

3.5 添加执行任务(addWorker)

图 22-6 添加执行任务逻辑流程

private boolean addWorker(Runnable firstTask, boolean core)

第一部分、增加线程数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码retry:
for (;;) {
    int c = ctl.get();
    int rs = runStateOf(c);
    // Check if queue empty only if necessary.
    if (rs >= SHUTDOWN &&
        ! (rs == SHUTDOWN &&
           firstTask == null &&
           ! workQueue.isEmpty()))
        return false;
    for (;;) {
        int wc = workerCountOf(c);
        if (wc >= CAPACITY ||
            wc >= (core ? corePoolSize : maximumPoolSize))
            return false;
        if (compareAndIncrementWorkerCount(c))
            break retry;
        c = ctl.get();  // Re-read ctl
        if (runStateOf(c) != rs)
            continue retry;
        // else CAS failed due to workerCount change; retry inner loop
    }
}

第一部分、创建启动线程

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
java复制代码boolean workerStarted = false;
boolean workerAdded = false;
Worker w = null;
try {
    w = new Worker(firstTask);
    final Thread t = w.thread;
    if (t != null) {
        final ReentrantLock mainLock = this.mainLock;
        mainLock.lock();
        try {
            int rs = runStateOf(ctl.get());
            if (rs < SHUTDOWN ||
                (rs == SHUTDOWN && firstTask == null)) {
                if (t.isAlive()) // precheck that t is startable
                    throw new IllegalThreadStateException();
                workers.add(w);
                int s = workers.size();
                if (s > largestPoolSize)
                    largestPoolSize = s;
                workerAdded = true;
            }
        } finally {
            mainLock.unlock();
        }
        if (workerAdded) {
            t.start();
            workerStarted = true;
        }
    }
} finally {
    if (! workerStarted)
        addWorkerFailed(w);
}
return workerStarted;

添加执行任务的流程可以分为两块看，上面代码部分是用于记录线程数量、下面代码部分是在独占锁里创建执行线程并启动。这部分代码在不看锁、CAS等操作，那么就和我们最开始手写的线程池基本一样了

  • if (rs >= SHUTDOWN &&! (rs == SHUTDOWN &&firstTask == null &&! workQueue.isEmpty()))，判断当前线程池状态，是否为 SHUTDOWN、STOP、TIDYING、TERMINATED中的一个。并且当前状态为 SHUTDOWN、且传入的任务为 null，同时队列不为空。那么就返回 false。
  • compareAndIncrementWorkerCount，CAS 操作，增加线程数量，成功就会跳出标记的循环体。
  • runStateOf(c) != rs，最后是线程池状态判断，决定是否循环。
  • 在线程池数量记录成功后，则需要进入加锁环节，创建执行线程，并记录状态。在最后如果判断没有启动成功，则需要执行 addWorkerFailed 方法，剔除到线程方法等操作。

3.6 执行线程(runWorker)

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
java复制代码final void runWorker(Worker w) {
    Thread wt = Thread.currentThread();
    Runnable task = w.firstTask;
    w.firstTask = null;
    w.unlock(); // 允许中断
    boolean completedAbruptly = true;
    try {
        while (task != null || (task = getTask()) != null) 
            w.lock();
            if ((runStateAtLeast(ctl.get(), STOP) ||
                 (Thread.interrupted() &&
                  runStateAtLeast(ctl.get(), STOP))) &&
                !wt.isInterrupted())
                wt.interrupt();
            try {
                beforeExecute(wt, task);
                Throwable thrown = null;
                try {
                    task.run();
                } finally {
                    afterExecute(task, thrown);
                }
            } finally {
                task = null;
                w.completedTasks++;
                w.unlock();
            }
        }
        completedAbruptly = false;
    } finally {
        processWorkerExit(w, completedAbruptly);
    }
}

其实，有了手写线程池的基础，到这也就基本了解了，线程池在干嘛。到这最核心的点就是 task.run() 让线程跑起来。额外再附带一些其他流程如下；

  • beforeExecute、afterExecute，线程执行的前后做一些统计信息。
  • 另外这里的锁操作是 Worker 继承 AQS 自己实现的不可重入的独占锁。
  • processWorkerExit，如果你感兴趣，类似这样的方法也可以深入了解下。在线程退出时候workers做到一些移除处理以及完成任务数等，也非常有意思

3.7 队列获取任务(getTask)

如果你已经开始阅读源码，可以在 runWorker 方法中，看到这样一句循环代码 while (task != null || (task = getTask()) != null)。这与我们手写线程池中操作的方式是一样的，核心目的就是从队列中获取线程方法。

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
java复制代码private Runnable getTask() {
    boolean timedOut = false; // Did the last poll() time out?
    for (;;) {
        int c = ctl.get();
        int rs = runStateOf(c);
        // Check if queue empty only if necessary.
        if (rs >= SHUTDOWN && (rs >= STOP || workQueue.isEmpty())) {
            decrementWorkerCount();
            return null;
        }
        int wc = workerCountOf(c);
        // Are workers subject to culling?
        boolean timed = allowCoreThreadTimeOut || wc > corePoolSize;
        if ((wc > maximumPoolSize || (timed && timedOut))
            && (wc > 1 || workQueue.isEmpty())) {
            if (compareAndDecrementWorkerCount(c))
                return null;
            continue;
        }
        try {
            Runnable r = timed ?
                workQueue.poll(keepAliveTime, TimeUnit.NANOSECONDS) :
                workQueue.take();
            if (r != null)
                return r;
            timedOut = true;
        } catch (InterruptedException retry) {
            timedOut = false;
        }
    }
}
  • getTask 方法从阻塞队列中获取等待被执行的任务，也就是一条条往出拿线程方法。
  • if (rs >= SHUTDOWN ...，判断线程是否关闭。
  • wc = workerCountOf(c)，wc > corePoolSize，如果工作线程数超过核心线程数量 corePoolSize 并且 workQueue 不为空，则增加工作线程。但如果超时未获取到线程，则会把大于 corePoolSize 的线程销毁掉。
  • timed，是 allowCoreThreadTimeOut 得来的。最终 timed 为 true 时，则通过阻塞队列的poll方法进行超时控制。
  • 如果在 keepAliveTime 时间内没有获取到任务，则返回null。如果为false，则阻塞。

四、总结

  • 这一章节并没有完全把线程池的所有知识点都介绍完，否则一篇内容会有些臃肿。在这一章节我们从手写线程池开始，逐步的分析这些代码在Java的线程池中是如何实现的，涉及到的知识点也几乎是我们以前介绍过的内容，包括：队列、CAS、AQS、重入锁、独占锁等内容。所以这些知识也基本是环环相扣的，最好有一些根基否则会有些不好理解。
  • 除了本章介绍的，我们还没有讲到线程的销毁过程、四种线程池方法的选择和使用、以及在CPU密集型任务、IO 密集型任务时该怎么配置。另外在Spring中也有自己实现的线程池方法。这些知识点都非常贴近实际操作。
  • 好了，今天的内容先扯到这，后续的内容陆续完善。如果以上内容有错字、流程缺失、或者不好理解以及描述错误，欢迎留言。互相学习、互相进步。

五、系列推荐

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%