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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
asm()符号链接问题
最近在阅读并实操<<一个64位操作系统的设计与实现>>中,其中在4-11程序中, task.h 和 task.c 有那么几行代码:
c// task.h
#define switch_to(prev,next) \
do{ \
__asm__ __volatile__ ( "pushq %%rbp \n\t" \
"pushq %%rax \n\t" \
"movq %%rsp, %0 \n\t" \
"movq %2, %%rsp \n\t" \
"leaq 1f(%%rip), %%rax \n\t" \
"movq %%rax, %1 \n\t" \
"pushq %3 \n\t" \
"jmp __switch_to \n\t" \
"1: \n\t" \
"popq %%rax \n\t" \
"popq %%rbp \n\t" \
:"=m"(prev->thread->rsp),"=m"(prev->thread->rip) \
:"m"(next->thread->rsp),"m"(next->thread->rip),"D"(prev),"S"(next) \
:"memory" \
); \
}while(0)
// task.c
inline void __switch_to(struct task_struct *prev,struct task_struct *next)
{
init_tss[0].rsp0 = next->thread->rsp0;
set_tss64(init_tss[0].rsp0, init_tss[0].rsp1, init_tss[0].rsp2, init_tss[0].ist1, init_tss[0].ist2, init_tss[0].ist3, init_tss[0].ist4, init_tss[0].ist5, init_tss[0].ist6, init_tss[0].ist7);
__asm__ __volatile__("movq %%fs, %0 \n\t":"=a"(prev->thread->fs));
__asm__ __volatile__("movq %%gs, %0 \n\t":"=a"(prev->thread->gs));
__asm__ __volatile__("movq %0, %%fs \n\t"::"a"(next->thread->fs));
__asm__ __volatile__("movq %0, %%gs \n\t"::"a"(next->thread->gs));
color_printk(WHITE,BLACK,"prev->thread->rsp0:%#018lx\n",prev->thread->rsp0);
color_printk(WHITE,BLACK,"next->thread->rsp0:%#018lx\n",next->thread->rsp0);
}
在这里,作者编写了一个用于进行进程切换的程序,这里的逻辑是: 当内核试图进行进程切换时,最终会通过两个PCB块来交互,可以看作是两个进程的内核栈空间的交换.首先将需要的寄存器存到当前内核栈中,然后切换内核栈,在另一个栈中,在__switch_to中使用ret指令来实现rip的转移.如果按照C语言编译的思路来想,这里生成的obj文件应该能够识别出__switch_to符号.
看起来没什么问题,但是在GCC编译的过程中,总是出现
task.c:(.text+0xc07): undefined reference to `__switch_to' task.c:(.text+0xc07): relocation truncated to fit: R_X86_64_PLT32 against undefined symbol `__switch_to'
这里,真正的问题在于,__switch_to在编写过程中被inline了,这就导致在obj文件中,实际上不会导出其符号,在我这个版本的GCC中,好像是内联汇编（__asm）里的符号在编译阶段不会被“解析”成地址，只会被记录成未解析符号，最终由链接器来解决,这就导致这个程序无法通过链接器完成可执行文件的生成.
asm()的符号地址问题
同样是在4-11的程序中:
c
extern void kernel_thread_func(void);
__asm__ (
"kernel_thread_func: \n\t"
" popq %r15 \n\t"
" popq %r14 \n\t"
" popq %r13 \n\t"
" popq %r12 \n\t"
" popq %r11 \n\t"
" popq %r10 \n\t"
" popq %r9 \n\t"
" popq %r8 \n\t"
" popq %rbx \n\t"
" popq %rcx \n\t"
" popq %rdx \n\t"
" popq %rsi \n\t"
" popq %rdi \n\t"
" popq %rbp \n\t"
" popq %rax \n\t"
" movq %rax, %ds \n\t"
" popq %rax \n\t"
" movq %rax, %es \n\t"
" popq %rax \n\t"
" addq $0x38, %rsp \n\t"
/////////////////////////////////
" movq %rdx, %rdi \n\t"
" callq *%rbx \n\t"
" movq %rax, %rdi \n\t"
" callq do_exit \n\t"
);
这里的代码是:在内核创建新线程时，从调度器切换到这个函数后，恢复线程上下文寄存器，调用目标函数（线程主函数），然后安全退出线程。
但是在实际运行的过程中,总是出现#13 GP,一般保护性错误,通过排查发现,这个kernel_thread_func的地址十分奇怪0x00118000FFFF8000. 和.text不在一个地方.初步认为是asm()不属于任何一个函数导致的.(希望有人能解答吧QAQ)
解决方法
再开一个.S文件,在其中编写汇编逻辑,这样kernel_thread_func的地址就正常了.
所以说,在C语言的编写时,一定要让asm()在函数的内部,碰到这种情况,建议直接用.S代码来表示.
