LeetCode.1143.最长公共子序列（中等）

计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
实现 NumMatrix 类：
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。
阅读全文 »

LeetCode.931.下降路径最小和（中等）

发表于 2020-08-10 更新于 2022-07-04 分类于 LeetCode Disqus：

题目

LeetCode.931.下降路径最小和（中等）

给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径的最小和。

下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

阅读全文 »

LeetCode.1314.矩阵区域和（中等）

发表于 2020-08-10 更新于 2022-07-04 分类于 LeetCode Disqus：

题目

LeetCode.1314.矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

i - k <= r <= i + k,
j - k <= c <= j + k 且
(r, c) 在矩阵内。

阅读全文 »

LeetCode.264.丑数 II（中等）

发表于 2020-08-09 更新于 2022-07-04 分类于 LeetCode Disqus：

题目

264. 丑数 II（中等）

给你一个整数 n ，请你找出并返回第 n 个丑数。
丑数就是只包含质因数 2、3 和/或 5 的正整数。
提示：1 <= n <= 1690

阅读全文 »

Kotlin协程原理

发表于 2020-08-09 更新于 2022-07-04 分类于 Kotlin Disqus：

概述

优势

协程核心优势是结构化编程，每个协程都是一个逻辑调度流，并加以各种自定义的控制。
代码结构清晰，可读性增强，便于调试和测试。

协程核心实现

Kotlin协程的实现的核心是围绕Continuation对象和挂起函数展开的。

要理解协程的各个原理和机制，首先要搞明白挂起函数的原理，再搞懂启动一个协程具体的执行步骤和底层实现，然后才能理解其他的机制，比如线程切换、拦截器、任务取消、异常处理等机制。

比如说取消，如果调用了一个系统的挂起函数，是支持取消的，当取消Job的时候，挂起函数就不执行它的Continuation的回调方法，挂起函数后续的逻辑也就不会执行了。

挂起函数和Continuation

挂起函数在编译后，都会给函数增加一个Continuation的参数，Continuation类代表就是一个异步回调，里面的resumeWith()方法就是代表一般意义上回调对象里的onSuccess或者onFail。

回调的onSuccess后执行的是什么呢？
执行的是调用挂起函数的后续逻辑，Continuation等于是把逻辑流给封装了一下。

Continuation是怎么做到封装挂起函数后续逻辑的？

这要从协程的启动说起。

通过CoroutineScope的launch()方法启动一个协程的时候，观察launch函数的参数，协程体代码是写在一个suspend修饰过的lambda表达式里面的，这个suspend lambda最终会编译为一个SuspendLambda类。

launch函数中执行协程，最终是通过调用SuspendLambda类的create()函数返回一个Continuation对象，再调用这个Continuation的resume()方法来执行。

SuspendLambda的create()方法返回的Continuation对象就是创建一个SuspendLambda对象返回，SuspendLambda其实是继承Continuation对象的，所以可以被作为Continuation返回；
其resumeWith的方法实现是在继承链中的BaseContinuationImpl对象中，这里会调用invokeSuspend()方法，invokeSuspend()是实现在SuspendLambda中的，协程体里的代码都是在invokeSuspend()中的。

如果在协程体里调用了别的挂起函数，之前说了会需要传一个Continuation对象，传的就是SuspendLambda本身；

如果挂起函数的逻辑要切线程，不在同一个栈中执行，会返回一个挂起的枚举常量，然后invokeSuspend()方法就直接return了，不执行后续的逻辑。

等到这个挂起函数执行完了，会调用Continuation的resumeWith()恢复后续逻辑执行，就会又执行到SuspendLambda的invokeSuspend()方法，执行协程体的后续代码。

状态机

这里是通过状态机来控制执行逻辑，简单理解就是一个读取状态的switch语句，编译时会把挂起函数前后的逻辑划分到不同的状态下，分在不同的case中执行，每次执行一个挂起函数，都会改变状态，每次重新调用invokeSuspend()的时候，会走到switch语句的不同的case，以执行不同的逻辑。

这里使用状态机还有个好处就是，如果协程体里执行了100个挂起函数，给这100个挂起函数传递Continuation参数的时候，只需要传递SuspendLambda一个实例，而不用创建100个Continuation对象，这样节约内存，所以保证了高性能。

suspendCoroutine

还有一个神奇的函数是suspendCoroutine，函数有个参数是一个带Continuation参数的lambda表达式，也是crossline内联的，这个方法的作用是获取到代表后续执行逻辑的Continuation对象，这个方法是suspend修饰的，并且是内联的，因为方法和lambda都是内联的，所以最后lambda里的代码会直接贴到suspendCoroutine的调用处。

因为函数又是suspend的，所以会把SuspendLambda对象传给挂起函数的Continuation参数，SuspendLambda就获取到了后续的代码执行逻辑，其实就是状态机的一个case。

调度器 - 线程切换

线程切换的生效靠的是拦截器机制，每次启动协程的时候，会在创建SuspendLambda之后，调用一下SuspendLambda的intercept()方法，调用intercept()返回的Continuation的resume()来启动协程。

intercept()里面会去到context中去寻找key为CoroutineInterceptor的对象，也就是拦截器对象。
存在的话，会调用一下interceptContinuation()方法，把当前的SuspendLambda传递过去，返回一个新的Continuation对象。

我们一般做协程的线程调度的时候，会在launch的时候传递一个Dispatchers.Default或Dispatchers.IO，这两个对象都是CoroutineDispatcher的实现类，会以CoroutineInterceptor为Key存储在coroutineContext中。

然后就会在intercept()取出来调用，CoroutineDispatcher中会返回一个新的Continuation对象，对原始的Continuation对象也就是SuspendLambda做一个代理，新的Continuation对象里会用线程池来控制原始的Continuation的resumeWith()的执行时机，从而实现了线程的调度。