题目

LeetCode.51.N皇后（困难）

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

提示：

• 1 <= n <= 9
• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

题目

LeetCode.343.整数拆分（中等）

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

Dagger2 缺点

1. 学习和科普成本极高，API使用非常繁琐。
2. 配置越多，生成的辅助代码越多，会导致：
   • 增加编译时间。
   • 增加Apk体积。

Koin 优势

1. 开发者需要理解的概念很少，最核心就是理解Scope一个概念，其他看看文档个和源码可以秒懂。
2. 在kotlin语法下（如扩展、委托），API极度简洁、无感、易用。
3. 无反射，无运行时性能损耗。
4. 没有辅助代码生成，纯粹在代码层做配置，所以不会增长编译时间，不会增大APK体积。

Koin基本原理

• 要注入的对象都定义在Module对象中，一个Module包含多个对象。
• Module对象都存储在一个的Scope对象里，一个Scope包含多个Module实例。
• 所有的Scope都存储在一个Koin对象里，一个Koin包含多个Scope实例。
• Koin对象就是一个容器，可以保持一个单例，也可以创建多个Koin实例。
• 获取要注入的对象，先获取容器，再查找目标Scope，最后调用Scope的get()方法获取对象。

Scope代表作用域，不同作用域下定义两个一样的对象声明，最终会产生不同的对象。

通过Kotlin的委托、扩展、DSL等语法，可以把对象的注入获取封装成简洁、无感知的形式。

其他所有的功能扩展，都是以上面的基本流程展开的，有了主线逻辑，其他都很好懂。

LeakCanary怎么使用的？入口在哪？

https://square.github.io/leakcanary/getting_started/

在gradle配置中引入依赖后就自动启用了LeakCanary

LeakCanary 会自动检测下列对象的泄露：

1. destroyed Activity instances
2. destroyed Fragment instances
3. destroyed fragment View instances
4. cleared ViewModel instances

手动观测一个对象的泄露，通过以下方法调用：AppWatcher.objectWatcher.watch(myDetachedView, “View was detached”)

LeakCanary基本原理

1. RefWatcher.watch() 创建一个 KeyedWeakReference 到要被监控的对象。
2. 然后在后台线程检查引用是否被清除，如果没有，调用GC。
3. 如果引用还是未被清除，把 heap 内存 dump 到 APP 对应的文件系统中的一个 .hprof 文件中。
4. 在另外一个进程中的 HeapAnalyzerService 有一个 HeapAnalyzer 使用HAHA 解析这个文件。
5. 得益于唯一的 reference key, HeapAnalyzer 找到 KeyedWeakReference，定位内存泄漏。
6. HeapAnalyzer 计算 到 GC roots 的最短强引用路径，并确定是否是泄漏。如果是的话，建立导致泄漏的引用链。
7. 引用链传递到 APP 进程中的 DisplayLeakService， 并以通知的形式展示出来。

为什么引入依赖后就自动启用LeakCanary了？

因为在AndroidManifest里注册了名为AppWatcherInstaller$LeakCanaryProcess的ContentProvider，App启动时会自动调用ContentProvider的onCreate()方法

在这里会调用AppWatcher.manualInstall(application)， 这就是LeakCanary启动的入口。

ContentProvider.onCreate()调用时机是：

Application.attachBaseContext() > ContentProvider.onCreate() ->Application.onCreate()

AppWatcher.manualInstall(application)做了什么？

主要是调用了

1. ActivityDestroyWatcher.install(application, objectWatcher, configProvider)
2. FragmentDestroyWatcher.install(application, objectWatcher, configProvider)
3. onAppWatcherInstalled(application)

ActivityDestroyWatcher.install()做的是什么？

1. 调用了application.registerActivityLifecycleCallbacks()，监听onActivityDestroyed()
2. 在onActivityDestroyed()中调用objectWatcher.watch(activity)，监听被destroyed的activity是否发生内存泄漏

FragmentDestroyWatcher.install()做了什么？

1. 调用了application.registerActivityLifecycleCallbacks()，监听onActivityCreated()
2. 在onActivityCreated()中调用activity.supportFragmentManager.registerFragmentLifecycleCallbacks()，监听onFragmentCreated()、onFragmentViewDestroyed()、onFragmentDestroyed()
3. onFragmentCreated()中调用ViewModelClearedWatcher.install()，监听被clear的ViewModel是否会发生泄漏
4. onFragmentViewDestroyed()中调用objectWatcher.watch(fragment.view)，监听fragment的view是否发生内存泄漏
5. onFragmentDestroyed()中调用objectWatcher.watch(fragment)，监听fragment是否发生内存泄漏

ViewModelClearedWatcher.install()做了什么？

通过以fragment为容器，创建一个ViewModelProvider实例，再创建一个ViewModelClearedWatcher实例，ViewModelClearedWatcher是一个ViewModel；

构造ViewModelClearedWatcher时，会获取到以fragment为容器的所有的ViewModel实例，然后在ViewModelClearedWatcher的onCleared()中objectWatcher.watch()观察fragment下的所有的ViewModel实例，检查是否有ViewModel实例发生内存泄漏

onAppWatcherInstalled()做了什么？

会调用InternalLeakCanary.invoke(application)

如何判断一个对象无法被GC机制回收？

创建一个持有要检测对象的WeakReference，然后主动触发一次GC，如果这个对象能被回收，则WeakReference.get()会为null，并且这个WeakReference实例会被放到创建WeakReference对象时给构造函数传的ReferenceQueue中。

WeakReference的特点就是，只要发生垃圾回收，WeakReference持有的对象引用就为null，并且ReferenceQueue中会存入这个WeakReference；没有发生垃圾回收，ReferenceQueue中不会存入WeakReference对象。

如果主动触发GC后，ReferenceQueue中没有监测的对象对应的WeakReference，说明该对象发生了内存泄漏。

AppWatcher.objectWatcher.watch(watchedObject: Any, description: String)做了什么？

1. 创建了一个KeyedWeakReference对象，存入一个名为watchedObjects，map，key就是UUID.randomUUID()随机生成的，唯一标识watchedObject，value类型是KeyedWeakReference

2. 主线程中延迟一段时间（AppWatcher.config.watchDurationMillis，默认为5秒）后，然后调用moveToRetained(key)

3. 先通过removeWeaklyReachableObjects()清理掉watchedObjects这个map中已经被垃圾回收的对象

4. 如果再发现map里的这个KeyedWeakReference对象还存在，就标记其为retained状态，具体会赋值KeyedWeakReference的retainedUptimeMillis为当前时间，记录下被认为是retained状态时发生的时间；也就是认为没有被垃圾回收，这里其实有两种情况，一种是垃圾回收还没有发生，一种是垃圾回收发生了但是没有回收掉。

5. 再通知所有的OnObjectRetainedListener有对象没有被回收

KeyedWeakReference是WeakReference子类，多了4个属性

1. key：UUID.randomUUID().toString()生成的随机字符串，唯一标识当前引用对象
2. description：描述当前对象为什么被观测
3. watchUptimeMillis：被watch的时间
4. retainedUptimeMillis：当前对象被认为是保留的（retained）状态时所处的时间

在watch()和moveToRetained()的一开始都会调用removeWeaklyReachableObjects()

removeWeaklyReachableObjects()是做什么的？

如果ReferenceQueue存在了某个Reference，说明已经被垃圾回收了，不需要监测内存泄漏了，从watchedObjects中移除这个Reference对象

ReferenceQueue中的Reference对象什么时候被清理？

每次从ReferenceQueue调用poll()方法，取出元素就是去除了队首元素

哪些地方注册了OnObjectRetainedListener，都做了什么?

InternalLeakCanary实现了OnObjectRetainedListener接口，在OnObjectRetainedListener.onObjectRetained()被调用时调用了scheduleRetainedObjectCheck()，然后又会调用heapDumpTrigger.scheduleRetainedObjectCheck() -> HeapDumpTrigger.checkRetainedObjects()

延迟时间为0，立刻调用

InternalLeakCanary.invoke(application)做了什么？

主要就是一件事：

在App可见或不可见时，调用HeapDumpTrigger.onApplicationVisibilityChanged(applicationVisible)

App可见的定义是：有Activity走了onStart()但还没有走onStop()

App不可见的定义是：所有Activity走过onStop()

在App不可见时，调用HeapDumpTrigger.scheduleRetainedObjectCheck() -> HeapDumpTrigger.checkRetainedObjects()

延迟时间为AppWatcher.config.watchDurationMillis，默认为5秒

HeapDumpTrigger.checkRetainedObjects()做了什么？

获取ObjectWatcher.watchedObjects里retained的对象的个数，如果存在retained的对象，也就说明有观察的对象还没有被回收，没有被垃圾回收其实有两种情况，一种是垃圾回收还没有发生，一种是垃圾回收发生了但是没有回收掉；这里就主动调用gcTrigger.runGc()触发一次垃圾回收。

然后正常情况会调用dumpHeap()

GcTrigger.runGc()做了什么？

代码复制了android官方的代码

https://android.googlesource.com/platform/libcore/+/master/support/src/test/java/libcore/java/lang/ref/FinalizationTester.java

1. 先执行Runtime.getRuntime().gc()建议虚拟机发起垃圾回收，可能会执行，可能不会被执行
2. 然后Thread.sleep(100)等待100毫秒，让回收了对象进入创建WeakReference时传入的ReferenceQueue
3. 调用System.runFinalization()，强制调用已经失去强引用的对象的finalize()方法

HeapDumpTrigger.scheduleRetainedObjectCheck()有哪些地方调用？

InternalLeakCanary实现了OnObjectRetainedListener接口，在OnObjectRetainedListener.onObjectRetained()被调用时调用了scheduleRetainedObjectCheck()，然后又会调用heapDumpTrigger.scheduleRetainedObjectCheck() -> HeapDumpTrigger.checkRetainedObjects()

延迟时间为0，立刻调用

在App可见或不可见时，调用HeapDumpTrigger.onApplicationVisibilityChanged(applicationVisible)

在App不可见时，调用HeapDumpTrigger.scheduleRetainedObjectCheck() -> HeapDumpTrigger.checkRetainedObjects()

延迟时间为AppWatcher.config.watchDurationMillis，默认为5秒

HeapDumpTrigger.checkRetainedObjects()中会去调用checkRetainedCount(retainedReferenceCount, config.retainedVisibleThreshold)，根据LeakCanary.config.retainedVisibleThreshold的注释可知，dump heap会阻塞UI线程，为了减少对开发者的打扰，内存泄露的对象个数在一定数量之内不触发dump heap，checkRetainedObjects()就是做这个检查的。

如果内存泄露的对象个数在阈值允许的数量之内，会调用HeapDumpTrigger.scheduleRetainedObjectCheck()，延迟两秒执行，继续调用HeapDumpTrigger.checkRetainedObjects()

HeapDumpTrigger.checkRetainedObjects()中如果经过了checkRetainedCount()的校验后，决定dump heap了，但是发现距离上次dump heap的时间小于60秒，就不进行dump，延迟到距离上次dump的60秒以后再执行checkRetainedObjects()

在HeapDumpTrigger.dumpHeap()中，调用heapDumper.dumpHeap()返回NoHeapDump时，也就是dump heap失败时，会再调用scheduleRetainedObjectCheck()尝试再次dump heap，延迟时间5秒

AndroidHeapDumper.dumpHeap()做了什么？

按当前时间命名创建一个hprof文件

调用Debug.dumpHprofData()输出信息到创建的文件

LeakCanary做内存泄漏检测存在什么不足？

可见其对Activity是否泄漏的判断依赖VM会将可回收的对象加入WeakReference关联的ReferenceQueue这一特性，在Demo的测试过程中我们发现这中做法在个别系统上可能存在误报，原因大致如下：

• VM并没有提供强制触发GC的API，通过System.gc()或Runtime.getRuntime().gc()只能“建议”系统进行GC，如果系统忽略了我们的GC请求，可回收的对象就不会被加入ReferenceQueue
• 将可回收对象加入ReferenceQueue需要等待一段时间，LeakCanary采用延时100ms的做法加以规避，但似乎并不绝对管用
• 监测逻辑是异步的，如果判断Activity是否可回收时某个Activity正好还被某个方法的局部变量持有，就会引起误判
• 若反复进入泄漏的Activity，LeakCanary会重复提示该Activity已泄漏

对此我们做了以下改进：

• 增加一个一定能被回收的“哨兵”对象，用来确认系统确实进行了GC
• 直接通过WeakReference.get()来判断对象是否已被回收，避免因延迟导致误判
• 若发现某个Activity无法被回收，再重复判断3次，且要求从该Activity被记录起有2个以上的Activity被创建才认为是泄漏，以防在判断时该Activity被局部变量持有导致误判
• 对已判断为泄漏的Activity，记录其类名，避免重复提示该Activity已泄漏

参考：Matrix-Android-ResourceCanary

题目

LeetCode.221.最大正方形（中等）

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

题目

LeetCode.45.跳跃游戏 II（中等）

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。

题目

LeetCode.37.解数独（困难）

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

题目

LeetCode.30.串联所有单词的子串（困难）

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

题目

LeetCode.55.跳跃游戏（中等）

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

题目

LeetCode.32.最长有效括号（困难）

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。