Problem: 1411. 给 N x 3 网格图涂色的方案数
1. 有向图路径数量
在这个问题中，我们可以将网格图的每一行都可以抽象成一个顶点(vertex),我们可以将这个问题抽象成:
有向图G（V,E)
- V代表顶点集，
- E代表边集，其中的每个元素代表{from_state,to_state},from_state的下一行可以是to_state 如下图所示:
我们要求的就是: 从这个图中的每个点出发，能够走出多少条长度为n - 1的路径
EmTaint 的工作价值
-
解决固件后端间接调用难以解析的问题 Linux-based 固件后端大量存在间接调用（indirect calls），传统方法无法解析，导致大量潜在漏洞路径无法被发现。 EmTaint 针对这一核心难点提出改进，使得更多真实的可疑路径能够被揭示。
-
提升变量别名（variable alias）场景下的数据流分析能力 变量别名频繁出现会导致数据流追踪断裂，隐含漏洞路径无法识别。 EmTaint 通过改进分析机制，使得在别名复杂的情况下仍能保持可靠的数据流追踪。
-
减少传统方法带来的误识别问题 之前的研究依赖启发式方式识别“中介污点源（mediate taint source）”，可能误识别，从而产生大量误报（false positives）。 EmTaint 通过更精确的分析方式避免此类启发式错误，使结果更准确。
-
揭示传统方法遗漏的大量潜在漏洞路径 由于未处理间接调用和别名问题，现有方法会遗漏许多真实路径（false negatives）。 EmTaint 提供更完整的路径覆盖，使漏洞挖掘更全面。
OctopusTaint 的工作价值
-
采用静态污点分析的方法，同时融合数据流的分析
-
解决间接调用问题
-
可追踪 NVRAM 的变形 taint，识别用户自定义 taint source
-
强化 Sanitization 检测
LLMSecConfig的工作价值
-
继承了LLM的静态分析工具，用于容器编排{Container Orchestrators[CO]}
-
通过现实的配置展示其有效性 （使用了1000个docker配置）
-
公开了数据集和实现方法 (source:https://figshare.com/s/2a9be8ccfbec9d8ba199)
Problem: 1526. 形成目标数组的子数组最少增加次数
递归方法
假设有如下的一个序列:[2,4,3,2,2,1,2,3,2,1]
解决思路: 对于每个索引,找到从它往后最后一个数值大于等于它的索引,对于这个图是这样的
这个过程比较好实现,单调栈就可以了
设定一个dfs(left,right,level)->result , 这里, dfs代表的是[left,right]内在level高度下,最少需要多少次.入口为dfs(0,n - 1,0); 在每一个递归中,有如下情况:
对于PART1,它对于整体的贡献等于 dfs(0,2,2) + 1 这样看不太明显,我们可以画出dfs(0,2,2)的样子:
这样依次递归,可以得出dfs(0,2,2) = 2 问题: 这里的1是什么 这里的一是指: 相对于这个part右侧第一块的高度和这个part整体高度的差值.对于PART1而言,等于 2 - min(2,1) <=> target[0] - min(target[0],target[5]),所以说 如果我们去除1 + dfs(0,2,2) 实际上我们会得到这样的图:
我们在计算PART2时,可以忽略PART1的那一部分,因为此时dfs(0,9,0) = dfs(5,9,0) PART2对于整体的贡献 = target[5] - min(target[5],level) + dfs(6,8,1) = 3 所以说,CONTRIBUTE(PART1) + CONTRIBUTE(PART2) = 6
复杂度
时间复杂度: 𝑂(𝑛) dfs(left,right,level) 每次必然内缩,整个算法每一个idx只会走过一次. 空间复杂度: 𝑂(𝑛)
cppclass Solution {
public:
int minNumberOperations(vector<int>& target) {
int n = target.size();
vector<int> right_bound(n);
vector<int> consume(n);
stack<int> stk;
for(int i = 0;i < n;i++){
while(!stk.empty() and target[stk.top()] > target[i]){
int idx = stk.top();
right_bound[idx] = i - 1;
stk.pop();
}
stk.emplace(i);
}
while(!stk.empty()){
int idx = stk.top();
right_bound[idx] = n - 1;
stk.pop();
}
function<int(int,int,int)> dfs = [&](int left,int right,int level){
if(left > right){
return 0;
}
int ptr = left;
int res = 0;
while(ptr <= right){
int l = ptr;
int r = min(right,right_bound[ptr]);
ptr = r + 1;
int r_next = (r == right) ? level : target[r + 1];
int standard = target[l] - min(target[l],r_next);
int num = target[l];
while(l <= right and target[l] == num){
l++;
}
while(r >= left and target[r] == num){
r--;
}
res += standard + dfs(l,r,num);
}
return res;
};
return dfs(0,n - 1,0);
}
};
差分数组
这是一个典型的差分数组的题目,这里不再赘述,只需要统计sum(i if diff[i] > 0 for i in range(0,n))就可以了.
这里的关键之处在于对于任意的[0,r],都有target[r] >= 0,这就保证了,diff前r项中为正的数值一定大于等于为负的数值.
对于这个想法,假设: 对于任意r>=0,remain(0,r)代表只在这一范围内操作,返回值代表没有参与操作的剩余正数之和,这里remain(0,r)一定存在解,让其 >= 0.
要想证明这个,需要证明remain(0,r1) >= sum(abs(diff[i]) for i in range(r2 + 1,r)) (rn代表离r第n远的正数索引)
因为 target[0] + sum(abs(diff[i]) for i in range(1,rn - 1)) >= 0 (target[i] >= 0)
所以 remain(0,rn) >= target[rn],以此类推, remain(0,r1) >= target[r1] remain(0,r1) - sum(abs(diff[i]) for i in range(r2 + 1,r)) >= target[r] >= 0 ,假设成立,[0,r]一定有解,能够将所有diff[i]<0抵消掉.这也是下面统计正数之和能够成立的关键所在.
基于上面的想法,我们对于每个diff[i] >= 0 让其去优先抵消离他最近的diff[i] < 0的地方,通过贪心的方法,找出最优解.
cppclass Solution {
public:
int minNumberOperations(vector<int>& target) {
int n = target.size();
vector<int> diff(n,0);
int res = 0;
diff[0] = target[0];
if(diff[0] > 0){
res += diff[0];
}
for(int i = 1;i < n;i++){
diff[i] = target[i] - target[i - 1];
if(diff[i] > 0){
res += diff[i];
}
}
return res;
}
};
作者：barrenham
链接：https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/solutions/3819236/di-gui-chai-fen-shu-zu-by-tender-jonesn4-ox18/ 来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
