数据结构与算法Week11&12——图
图与相关问题这两周学习了图，和一些图相关的问题。
基本概念图是一种非线性结构，与树相比，它可以是非连通的，也可以是有环的，所以图的问题要更为复杂。
图有很多术语，这里就不一一列举了，图的基本概念 - songguojun - 博客园这篇文章写得比较全面，可以去看看。
表示方法比较常用的有两种——邻接矩阵表示法和邻接表表示法。
邻接矩阵应当明确，我们要保存一张图，实际上就是要保存它的顶点和边，在不存在孤立点时，就相当于保存所有的边。而每两个顶点之间都可能有边。所以我们用一个二维矩阵G[n][n]来记录边的情况。G[i][j]=true代表有一条从i指向j的边，将G称为邻接矩阵。
邻接矩阵法的好处就是简单、直观，可以在O(1)的时间内检查两个顶点之间是否有边以及对边进行增删，而缺点就是空间浪费很大(尤其是对于稀疏图)，且不易于增删节点。
邻接表邻接表表示法，是对每一个节点记录它指向的节点，每个节点指向的节点数目各异，所以不能用静态数组保存，在C语言中要用链表或者动态数组，而C++中则可以直接用vector，保存为vector<vector<int>> G(n)，将G ...
leetcode 795. 区间子数组个数
题目描述leetcode795. 区间子数组个数
给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。
示例 1：
输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]
示例 2：
输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7
提示：
1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= left <= right <= 109
题解——枚举右端点，寻找左端点范围思路根据滑动窗口的思想，我们希望对于每一个右端点，找出满足要求的左端点的范围。假如记为[lower,upper]，那 ...
meet in the middle——折半搜索算法
meet in the middle——折半查找算法提出问题回溯法是一个很经典的算法了，也可以视为暴力搜索算法，一般时间复杂度会达到指数级甚至阶乘级，只能用于求解规模很小的问题。比如N皇后问题、迷宫问题、数独、0-1背包……当问题规模变大一些时，一般会考虑是否有重复搜索，尝试通过记忆化来剪枝，使其变为记忆化搜索，来减少子问题的重复搜索次数，比如爬台阶，这样的做法使时间复杂度达到与动态规划相同的量级，不过常数更大。
考虑这样一个问题：给定一个长度为n的数组，里面有正有负。现在想从表中选出任意多个数，使它们的和为0，问有多少种选法？
考虑退化问题，如果把要选出来的个数确定下来，比如为2、3、4……就变成经典问题——K数之和，暴力方法复杂度为O(N^k)，通过排序+双指针可以达到O(N^(k-1))。然而一旦不确定，就变成了0-1背包，对每个数都要考虑选与不选，时间复杂度为O(2^N)，才能找到所有组合。这一般能处理到N=20的情况，再大就无能为力了。
假如N=30，这种方法就完全不可行了吗？能否对上面的算法做一些优化呢？这就要用到本文说的meet in the middle算法了。
mee ...
在shell脚本中运行tmux&开机自动执行脚本
起因今天又收到了阿里云的邮件，说实例意外宕机然后又帮我重启了，让我去检查应用是否恢复。查看网站，倒是没有问题，然而code-server却登录不了。其实这也不出我所料，因为每次重启阿里云时，网站都会自动恢复，而code-server则要我去远程连接，重新敲命令来启动。
之前一直是这么干的，然而今天感觉太麻烦了，code-server能否也开机自启呢？经过一番周折，终于实现了。
第一步：用shell脚本启动code-server这一部分我很久之前就完成了，不过还是说一下。我将code-server的可执行文件放在家目录下，每次只要运行它就行了，不过还要指定访问端口，并且指定证书以支持https访问。编写的code-server.sh脚本如下，这倒没什么难的，不过是把手敲的命令放到文件里罢了。
1234567#! /bin/bash#设置密码export PASSWORD="******"#定位至文件夹cd ~/MyCode-server#运行code-server,指定ssl证书以及端口./code-server --cert **** --cert-key **** ...
leetcode 891. 子序列宽度之和
题目描述leetcode891. 子序列宽度之和
一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。
给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 109 + 7 取余 后的结果。
子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。
示例 1：
输入：nums = [2,1,3]
输出：6
解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。
示例 2：
输入：nums = [2]
输出：0
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 105
题解——贪心，直观解释思路我们知道，一个数组有2^n-1个非空子序列，枚举显然是不 ...
数据结构与算法Week10——期中考试
期中考试这篇文章是我对期中考试上机部分的题解。共有三道题。后两题都是比较简单的，但是第一题码量比较大，而且细节处理比较多，事实上，考试时第一题我花的时间是后两题加起来的三倍😂。而从结果来看，考试的八十余人中，后两题都拿到100的有30+，而第一题拿到100的仅有5人，当然，可能也有很多人卡在了处理输入数据上。所以我们倒着来看这三道题吧。
第三题
广义表的长度，定义为该表中元素的个数，特别地，一张子表视作一个元素，也就是说，(a,b,(a,b,c,(d)))的长度为3，因为它的元素是a，b和(a,b,c,(d))。所以我们的思路是，维护一个depth，表示嵌套的深度，只有深度为0(不考虑外层括号)时，才可能找到当前表的元素(字母或子表)，代码如下：
123456789101112131415#include <bits/stdc++.h>using namespace std;int main(){ string s; cin >> s; int ans = 0, depth = 0; for (int i = 3; i < ...
数据结构与算法Week9——树与森林
树与森林上周学习了二叉树，这是一种比较特殊的树，因为它至多只有两个孩子。而实际上，一般的树可以有多个孩子，这就使问题变得复杂了。首先要解决的是，如何表示一颗一般树？大致有双亲表示法、孩子链表法、孩子兄弟法三种。
树的三种表示方法双亲表示法顾名思义，就是给每个节点添加一个数据域，存放它的双亲的信息(说是双亲，其实只有一个)。这样的储存方法，给定一个节点，我们可以用O(1)的时间找到父亲，但却要遍历整颗树来找齐它的孩子。同时，由于没有自上而下的指针，我们至少要保存全部的叶节点，而现实中，是保存了全部的节点，并保存在一张表中。如图所示。
孩子链表表示法回顾二叉树的表示方法，我们是通过两个指针left和right来指示两个孩子，能否用在一般树中呢？有一个困难是：我们不知道每个节点可能有多少个孩子。所以，可以用一个vector<TreeNode*>来保存孩子指针们。不过，由于树结构可能面临频繁的增删，应该用链表代替数组，也就是list<TreeNode*>来保存孩子。如图所示。这种方法，我们只要保存根节点即可。
此外，如果知道了最大分叉数，就可以直接写成数组了，比如字典 ...
leetcode 1106. 解析布尔表达式
题目描述leetcode1106. 解析布尔表达式
给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。
有效的表达式需遵循以下约定：
"t"，运算结果为 True
"f"，运算结果为 False
"!(expr)"，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
"&(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 与的运算（AND）
"|(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 或的运算（OR）
示例 1：
输入：expression = "!(f)"
输出：true
示例 2：
输入：expression = "|(f,t)"
输出：true
示例 3：
输入：expression = "&(t,f)"
输出：false
示例 4：
输入：expressio ...
数据结构与算法Week8——二叉树
二叉树这周本来要期中考试的，结果几天前栖霞区出现了聚集性感染，又被迫线上课了，只好推迟考试，所以继续学习树相关的内容。我们目前学的树还仅限于二叉树，操作也只有创建、遍历两种，但实际上树的问题十分复杂，并且能由它引申出很多高级数据结构，比如前缀树、平衡树、红黑树、线段树……估计也不在这门课的学习范围内了吧（我也就略知一二，搜到板子会用而已）。
言归正传，这节课我们花了很多时间来讲先、中、后序遍历的非递归算法，以及树的**#号表示法**。
二叉树的遍历不同于线性结构（数组、链表）中每个元素最多有一个前驱和一个后继，二叉树中每个元素可以有两个后继，这导致二叉树的遍历也有好几种方法，可以分为深度优先遍历和广度优先遍历两大类，而深度优先遍历根据父节点何时遍历又可以分为先序遍历、中序遍历、后序遍历，广度优先遍历也叫层序遍历。注意，不特别说明，所有的遍历都是自左向右的。
用一个例子来说明他们的差别：
先序遍历结果：ABDFKICEHJG
中序遍历结果：DBKFIAHEJCG
后序遍历结果：DKIFBHJEGCA
层序遍历结果：ABCDFEGKIHJ
注意，父节点的遍历顺序是针对左右子树的，而不是左 ...
leetcode 907. 子数组的最小值之和
题目描述leetcode907. 子数组的最小值之和
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
示例 1：
输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
示例 2：
输入：arr = [11,81,94,43,3]
输出：444
提示：
1 <= arr.length <= 3 * 104
1 <= arr[i] <= 3 * 104
题解——单调栈典型题——求最近的更小元素力扣最近的每日一题经常出单调栈、单调队列这一类题，听上去唬人，但是知道它们的作用后，基本是套模板了。
思路如果我们枚举所有子数组，再逐个求最小值，显然是行不通的。应该逆 ...