去什么网站可以做ctf的题目,网站建设网络安全,制作网站中英文字体不能为,网站建设教程txt最近在学校上短学期课程#xff0c;做程序设计题#xff0c;一下子回忆起了大一学数据结构与算法的日子#xff01;
这十天我会记录一些做题的心得#xff0c;今天带来的是对于最长子序列长度题型的解题框架#xff1a;滑动窗口
本质就是双指针算法#xff1a;
通过le…最近在学校上短学期课程做程序设计题一下子回忆起了大一学数据结构与算法的日子
这十天我会记录一些做题的心得今天带来的是对于最长子序列长度题型的解题框架滑动窗口
本质就是双指针算法
通过left和right指针构建一个左闭右开的窗口windowleft, right]
首先通过right指针向右expand窗口
窗口满足题设条件的话就一直expand直到条件被打破。
此时窗口不满足题设条件需要通过left指针向右shrink窗口直到再次满足题设条件。 题目变化变的就是如何maintain这个窗口而已。
k int fun(int* A, int N,int S) {
// sliding window// The window we maintain is like [left, right)int left 0, right 0;int windowSum 0;int Max 0;while(right N) {// right expandingwindowSum A[right];Max windowSum S right - left Max ? right - left : Max;// shrinkingwhile(left right windowSum S) {windowSum - A[left];}}return Max;
} int fun(int* A, int N,int S) {
// sliding window// The window we maintain is like [left, right)int left 0, right 0;int Max 0;// maintain the local minimum and local maximumint winMin A[0];int winMax A[0];while(right N) {// right expandingif(A[right] winMax) {winMax A[right];}else if(A[right] winMin) {winMin A[right];}right;Max winMax - winMin S right - left Max ? right - left : Max;// shrinkingwhile(left right winMax - winMin S) {
// Dont forget to initialize the local value before setting.left;winMin A[left];winMax A[right];
// set the maximum and minimum in the new windowfor(int i left; i right; i) {if(A[i] winMax) {winMax A[i];}else if(A[i] winMin) {winMin A[i];}}}}return Max;
}
