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
题解——单调栈典型题——求最近的更小元素力扣最近的每日一题经常出单调栈、单调队列这一类题，听上去唬人，但是知道它们的作用后，基本是套模板了。
思路如果我们枚举所有子数组，再逐个求最小值，显然是行不通的。应该逆 ...
leetcode 862. 和至少为 K 的最短子数组
题目描述leetcode862. 和至少为 K 的最短子数组
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
示例 1：
输入：nums = [1], k = 1
输出：1
示例 2：
输入：nums = [1,2], k = 4
输出：-1
示例 3：
输入：nums = [2,-1,2], k = 3
输出：3
提示：
1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109
题解——单调队列详解今天正好趁着这道题学习了一下单调队列，把过程中我的一些理解记录下来，如有不对的地方，希望大佬们指出。
单调队列与单调栈的区别与联系相比于单调队列，单调栈要常见得多。需要指出的是，这两者并不像栈与队列那样有着截然相反的操作(事实上，单调队列用的并不是 ...
数据结构与算法Week7——贪心算法
贪心算法这周的作业题是三道贪心题。说实话，事先没见过，要独立想出来还是很难的。毕竟贪心就是这样，就好像你明知道前面有一扇门，却在上面摸索半天，也找不到门把手在哪里。贪心也很想脑筋急转弯，假如没有灵机一动，想不到那个方法，就得一直坐牢下去。所以很多算法竞赛也喜欢考贪心，来考察变通能力。
很难说要怎样训练贪心题，或许寻求的就是一种感觉吧(就像语文一样)。找规律也很重要，再有就是数学推理能力。
拿这次的三道作业题举个例子，都是很经典的贪心题。
题目一——活动选择原题链接——435. 无重叠区间 - 力扣（LeetCode）
这道题，如果采用暴力求解，最坏时间复杂度甚至可以达到O(2^n)，在n很大时，是很吓人的。而贪心算法可以将复杂度降到O(nlogn)+O(n)，其中O(nlogn)是排序的时间复杂度。
我们的贪心策略是：在每次添加活动时，总是保证结束时间尽量早，这可以保证后续能尽可能多地添加活动。而何时开始，对后续添加是无影响的，只影响自己能不能向里面添加。依据这种策略，我们将每个活动按照结束时间排序，并依次检验开始时间是否大于目前的结束时间，如果满足，就添加进去(这个就是满足条件的结 ...
leetcode 901. 股票价格跨度
题目描述leetcode901. 股票价格跨度
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
示例：
输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75 ...
数据结构与算法Week6——广义表的深度
广义表的深度广义表的定义本周的数据结构与算法继续学习数组和广义表。主要讲了广义表。广义表是一种比较抽象的数据结构，它包含两个部分：原子和表。相较于链表和容器而言，它的元素不止一种，而且由于表可以嵌套，一张广义表是递归定义的。广义表主要应用于LISP语言(实际上LISP语言也只有广义表)。
广义表的表示通常，表用大写字母表示，而原子用小写字母表示，并用括号来体现层次。几个例子如下图：
注意，广义表的递归可以没有出口，比如图中E表。
广义表的深度将广义表的深度定义为所有元素深度的最大值，直观体现就是括号嵌套的最大层数，对于上面的例子，深度如下：A 1, B 1, C 2, D 3, E inf，而这周的编程题便是求广义表的深度。题目如下：
首先考虑每个表中包含的表都在之前输入，那么，我们只需要遍历输入，同时维护一个depth，遇到左括号+1，遇到右括号-1，遇到其他表先加后减，同时在每一步取MAX，最终结果就是这张表的深度，存下来为后面做准备。
然而，未必恰好是这样输入的。很有可能内部的表要在后面输入，比如下面的情况。
123A=(B,C)C=(a)B=(a,B)
应该输出
123i ...
leetcode 779. 第K个语法符号
题目描述leetcode 779. 第K个语法符号
我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）
示例 1:
输入: n = 1, k = 1
输出: 0
解释: 第一行：0
示例 2:
输入: n = 2, k = 1
输出: 0
解释:
第一行: 0
第二行: 01
示例 3:
输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01
提示:
1 <= n <= 30
1 <= k <= 2n - 1
题解——脑筋急转弯：作图理解，c++一行思路先做出前几行的图看一看，可以生成如下一棵满二叉树
可以 ...
leetcode 902. 最大为 N 的数字组合
题目描述leetcode902. 最大为 N 的数字组合
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
示例 1：
输入：digits = ["1","3","5","7"], n = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2：
输入：digits = ["1","4","9"], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位 ...
数据结构与算法Week5——差分数组
差分数组以本周的练习题引入本周数据结构继续学习数组，主要讲了什么数组的压缩存储，也就是对特殊矩阵(对称矩阵)以及稀疏矩阵怎样减少区间消耗的问题。不过不太好用OJ考察，所以做的题目仍然是对数组的简单处理，第三题有点意思，可以做一些延伸。题目如图。
容易想到，讲师的数目的限制来自于课程重叠。也就是说，如果我们求出课程的最大重叠，也就是讲师的最小数目。观察数据范围，由于时间被限制在0~24了，我们可以对每个时刻，统计正在上的课，最大值就是答案。
需要注意的是，题目认为老师可以立即去上下一节课，也就是说：0~1,1~2这样的情况，只需要1名老师即可。所以，我们可以认为，上课的时间是[begin,end)，一个左闭右开区间，所以，我们维护一个长为24的数组(0~23)，对每一节课，把[begin,end)中的时间++，然后返回最大值即可。最坏时间复杂度O(24*N)。代码如下：
12345678910111213141516#include <bits/stdc++.h>using namespace std;int main(){ vector<int> ...
