8/1 矩阵中战斗力最弱的 K 行
难度 EASY
每行的战斗力用二分查找，然后用堆得到最小的k个。
题解里看到一个很有趣的解法，由于题目数据的行列限制在100，可以二分统计每行战斗力，战斗力乘以100、加上行号后排序，这样就抵消了行号带来的影响，变成单纯的战斗力排序，排完后再对100取余，就恢复了行号。感觉这个思想可以学习一下，将数据乘以100就可以附加一个100以内的数而不造成影响。
8/2 网络延迟时间
难度 MEDI
经典dijkstra。网上找了C++的priority queue，要include <queue>
初始化：
priority_queue<数据类型, 容器类型, 比较方式>
数据类型就是元素是什么类型，容器类型一般就是这个数据类型的vector，好像deque也行比较方式就是greater<>和less<>，前者实现小根堆，后者实现大根堆。常用的函数是top()返回堆顶、empty()判断为空、emplace()插入、pop()弹出堆顶。本题用的就是：
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> que;
8/3 最短无序连续子数组
难度 MEDI
从左找到第一个不是升序的，从右找到第一个不是升序的。然后找到这段中的最大和最小，再往两边看。左边只要比最小的大就加入，右边比最大的小就加入，不满足时停止。这样就在O(n)的时间完成了。
中心思想就是，无序段最小元素左边更大的和最大元素右边更小的都要调整。
8/4 有效三角形的个数
难度 MEDI
看到范围到1000就用了桶排序，一个桶记录数字出现次数，一个桶记录前缀和。
遍历时用双指针遍历，情况比较多：
- i和j相同，剩下的用前缀和得到满足的有多少个，乘以Cn2，n为值为 i 的个数（i，i，k）
- i和j不同，剩下的不是j，用前缀和得到个数，乘以 i 和 j 的个数（i，j，k）
- i和j不同，剩下的是j，i 的个数乘以Cn2，n为值为 j 的个数（i，j，j）
这样虽然是O(n)但是常数较小（归并了所有值相同的），时间比较快、空间很拉。
8/5 找到最终的安全状态
难度 MEDI
反过来拓扑排序即可。。
8/6 访问所有节点的最短路径
难度 HARD
对于这种路径长度为1的最短路径，最容易理解的一个比较好的方法就是广度优先，初始时将所有节点加入队列，每次pop_front后把该节点能到的、且此前未经历过这样的状态的加入队列。由于广度优先的特性，此前进入队列的最短路径不会比当前的更大，所以如果经历过这样的状态就可以跳过，例如：先前有1→2→3，如果这次pop了1且有2→1→3，不用加入队列，因为1→2→3不会更差。
这一题的难点在于状态压缩。由于涉及到多个点，用数组涉及到拷贝，且带来了很大的空间复杂度开销。注意到节点个数≤12，就可以用一个32位数字表示状态。低n位每个比特代表是否经过这个节点，更高位存储节点号，把这样的数字用哈希表存下来就可以了。
8/7 环形数组是否存在循环
难度 MEDI
用了比较朴素的解法。一个visited数组标记当前num是否被访问过。从0到n循环时跳过visited的。对于每一个未visited的数进行如下循环，其中，用一个哈希表存储是否在本次循环中出现过：
- 移动到下一个
- 若正负异号，break
- 若是visited且未出现在这次循环，break（是已经找过的情况）
- 若在本次循环中出现过，如果长度为1就break，否则return true
- 否则，加入哈希表，且visited置为true
该解法的时间复杂度已经是O(n)，但空间复杂度较差，一个简单的优化是visited存储的是在哪一轮中被访问，这样就不用哈希表了。稍复杂的优化是用一个较大的OFFSET使得可以在原数组上标记，加减OFFSET不会对循环到的下一个位置产生影响，这样可以将空间复杂度降到O(1)。
官方题解的做法是快慢指针，两个指针指向当前数，快指针每次移动两次，慢指针移动一次。如果相遇就存在循环。
8/8 第 N 个泰波那契数
难度 EASY
动规做法是送分题。题解提供了一种矩阵快速幂的做法，这一题可以化为求特定矩阵的n次幂，使用快速幂算法可以将时间复杂度降低到O(logn)。
快速幂算法基于这样的原理：
例如，求5\^9，可以分解为5\^4*5\^4*5，而5\^4可以分解为5\^2*5\^2，这样循环下去。
/**
* 计算 x^n 的值，并将结果保存在 res 中
*/
long long res = 1;
// 进行快速幂运算，n 为当前的指数值，n 为 0 的时候运算结束
while (n) {
if (n & 1) {
// 如果 n 是奇数，那么需要将 x 存入运算结果中
res *= x;
}
// 更新当前的 x 的值
x *= x;
n >>= 1;
}
矩阵的快速幂与之类似。
学到了。。
8/9 超级丑数
难度 MEDI
之前做过的丑数II与这题一样，不过是由2，3，5变成了更长的质数数组。具体可以看4/11的。
8/10 等差数列划分
难度 MEDI
挺简单的，统计相邻数组元素之差即可。我用了数组记录，带来了空间复杂度，可以用单个元素记录降低复杂度。
8/11 等差数列划分 II - 子序列
难度 HARD
昨天的是相邻，今天的是子序列，与之相比最大的不同是元素之差不能只统计相邻。到这里我就卡住了，想到了dp但没有想到很好的方法。答案的做法非常巧妙：
在dp数组中dp[i][d]记录的是整数数组中以i为最后一项，d为公差构成的“伪等差”序列，即至少有两个（而不是三个）元素的序列，的数量。遍历时i从0到n，j从0到i，nums[i] - nums[j]即为这样的序列的公差，最终结果+= dp[j][d]，因为如果之前的是伪序列也会在此时增加一个元素变成序列，dp[i][d] += dp[j][d] + 1，这个1就是j、i这两项。
实际操作的时候，由于d的范围非常大且已经超过int，更好的做法是对于dp数组的第二维用哈希表存储。其实对于这种dp某一维度并不是数组下标而是某个并非从0到n都会出现的值都可以考虑用哈希表节省空间。
8/12 最长回文子序列
难度 MEDI
比较简单的dp，dp[i][j]记录从i到j段的最长回文子序列的长度。初始时dp[i][i] = 1。每次循环时，外部 j 从0到n，内部 i 从 j - 1 到0，dp的取值规则如下：
if(s[i] == s[j]){
dp[i][j] = dp[i + 1][j - 1] + 2; //去掉两头，长度+2
}
else{
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); //去掉一头中更长者
}
内部从高到低的循环就是为了保证在else情况下两个dp元素的值都已经被求过（两个元素对应的字符串都是i到j段向里缩，即左侧的向右，右侧的向左，那么对于循环来说，左侧的就要向左，右侧的向右）。
8/13 数字 1 的个数
难度 HARD
说是困难，其实就是数学题。。做法是统计每一位上出现1的次数。
以12345求10位上出现1的次数为例，这时候我们有k = 10，可以根据k划分得到两个数字123和45，当10位以上小于123时（0到122共123种情况），10位及以下可以任意选择，每一种情况10位可以出现k次1（10到19）；当10位以上等于123时，10位及以下被限制在0到45，记这个数为x。当x ≥ 20（k * 2）时，也可以出现k次1，小于10时一次都出现不了，10到20时出现x - k + 1次。这样，我们就求得了10位上出现1的次数。循环求每一位即可。
8/14 统计不开心的朋友
难度 MEDI
因为亲近的朋友是从0到n-1的序号组成，所以用这样的哈希表，key 是i * n + preferences[i][j]，value 是 j，就能记录 preferences[i][j] 对应的朋友是 i 第 j 喜欢的。我们对于每个人，先找到他现在匹配的朋友，再根据哈希表找到这个朋友是他第几喜欢的（即pos），遍历pos前的（即 i 更喜欢的那些人），找这些人的配对对象，如果不如 i ，则这些人不开心。
8/15 出界的路径数
难度 MEDI
挺简单的dp，dp[i][j][move]意为从点 (i, j) 出发移动move次可以出去的方法数，每次加上其余四个位置对应移动 move - 1 次的方法数
8/16 优美的排列
难度 MEDI
这道题没有想到太好的解决方法，参考了题解的动态规划+状态压缩。注意到n是≤15的，所以可以用1个整数来表示一种状态，即选取了整数中的若干个时的方法数，从而得到一个状态转移方程，参见优美的排列 官方题解的图。状态压缩是个好方法，但是总是想不起来用。。
8/17 学生出勤记录 I
难度 EASY
简单题，照着题干写就行
即日起由于准备迟来的本校夏令营（而且今年又没有机试）暂停每日一题的训练。希望一切顺利！