leecode代码模板

二分算法：

34. 在排序数组中查找元素的第一个和最后一个位置给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。示例 1：输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：输入：nums = [], target = 0
输出：[-1,-1]class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int start = searlower(nums, target);int end = searupper(nums, target);if(start == nums.size() || nums[start] != target || end == -1){return {-1, -1};}return {start, end};}int searlower(vector<int>& nums, int target){int left = 0, right = nums.size()-1;while(left <= right){int mid = left + (right - left) / 2;//循环不变量://未确定区间为[left, right]//nums[left - 1] < target//nums[right + 1] >= targetif(nums[mid] < target){left = mid + 1;}else{right = mid - 1;}}return left;}int searupper(vector<int>& nums, int target){int left = 0, right = nums.size()-1;while(left <= right){int mid = left + (right - left) / 2;//循环不变量://未确定区间为[left, right]//nums[left - 1] <= target//nums[right + 1] > targetif(nums[mid] <= target){left = mid + 1;}else{right = mid - 1;}}return right;}
};

定长滑动窗口：

//假设滑动窗口固定长度为： n ，则代码模板如下：
class Solution {
public:int SlideWindow(vector<int>& nums, int k) {int length = nums.size();//在进入循环之前，必须先初始化好窗口为最左侧位置的情况//并且维护好这种情况下的相关变量//这里要首先判断一下初始化的结果是否满足题意，然后下面的第一次循环就不必//遍历第一种情况了，这么做是也是为了满足循环不变量[i - n, i)//循环不变量：滑动窗口[i - n, i),窗口长度固定为 nfor (int i = n; i < length; i++) {//此时i位置为窗口本次循环的末位置下标，由于是开区间i，所以接下来要维护nums[i]的状态//而i-n位置为上一次循环的首位下标，我们通常也需要关注维护它的状态，使窗口左边界向右移动一位//以上操作进行完毕之后，此时窗口区间就变为闭区间[i - n + 1, i]了，长度还是n//下一次循环之前i++，区间再次变为半开半闭状态-[i - n, i)}return ...;}
};

不定长滑动窗口：

//不定长滑动窗口伪代码
class Solution {
public:int SlideWindow(string s) {// 同方向移动，起始的时候，都位于 0，表示我们定义搜索区间为 [left, right) ，此时区间为空区间int left = 0;int right = 0;while(right < Slen){//每一次循环的开始，都一定不满足条件//（因为上一次循环是从满足条件跳出while的）// 这里对状态做修改，好让程序在后面检测到满足条件while(满足条件){ // 对状态做修改，好让程序在后面检测到不满足条件left++;     //右移left}//记录当前最接近结果的值right++; //右移right}return maxlen;}
};