c++编程题-笔记

---

前言

这里是学习c++，练习一下算法题，简单的笔记

一、二分法

1、区分边界

情景：在有序且无重复元素的数组中（因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的），找满足某个条件的数的位置；

对于左闭右闭的区间里，也就是**[left, right]** ，默认升序数组。

// 版本一
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左区间，所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，所以[middle + 1, right]} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;}
};

对于在左闭右开的区间里，也就是**[left, right)** ，默认升序数组。

// 版本二
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <int middle = left + ((right - left) >> 1);if (nums[middle] > target) {right = middle; // target 在左区间，在[left, middle)中} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，在[middle + 1, right)中} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;}
};

int right = nums.size(); 是因为“ 左闭右开 ”，但是我得包含整个数组的元素，所以 right = nums.size() ，此时nums[1]~nums[-1]都可以取到，nums[ nums.size()]不会取到，且符合“ 左闭右开 ”。

二、双指针

1、左右指针

场景：左右双指针算法在解决问题的过程中会生成两个指针，一个指向头部，一个指向尾部，从两端向中间逼近，直到满足条件或者两个指针相遇为止. 二分查找就是一种左右双指针算法的应用场景，其他使用情况基本上可以总结为数组中元素组合问题。

i ：代表左指针，指向数组首部。
j ：代表右指针，指向数组尾部。

class Solution {
public:vector<int> sortedSquares(vector<int>& A) {int k = A.size() - 1;vector<int> result(A.size(), 0);//赋值为0for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素if (A[i] * A[i] < A[j] * A[j])  {result[k--] = A[j] * A[j];j--;}else {result[k--] = A[i] * A[i];i++;}}return result;}
};

2、快慢指针

场景：通过设置两个指针不断进行单向移动来解决问题的方法。

形式:两个指针分别指向不同的序列；两个指针指向同一个序列。比如：快速排序的划分过程。

实现：本来是双层for循环，O(n²)的时间复杂度。通过双指针算法可以优化到O(n)的时间复杂度。那是如何优化的时间复杂度呢？其实是当一个指针满足条件后才会单向移动，没有指针的回溯，而每次都会有指针的移动。简单说就是有个快指针可以不停的移动，有个慢指针需要符合条件后才能移动

①两个指针指向同一个序列

模板：

slow = 0 # 1for fast in range(len(nums)):if  是slow想要的元素：nums[slow] = nums[fast]  #  nums[slow+1] = nums[fast]slow += 1return slow， nums # slow+1， nums

fast 快指针：指向符合要求的值。
slow 慢指针：指向数组中需要更新的位置。

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
};

三、滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果，本质上还是双指针问题。

分清楚：

窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？

滑动窗口，快慢指针类型：

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

其中，i 是慢指针，j 是快指针，前窗口的值大于等于s了就移动慢指针，这里要用while循环，不能用if，这是关键点。

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX;//nums.size()+1即可int sum = 0; // 滑动窗口数值之和int i = 0; // 滑动窗口起始位置int subLength = 0; // 滑动窗口的长度for (int j = 0; j < nums.size(); j++) {sum += nums[j];// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件while (sum >= s) {subLength = (j - i + 1); // 取子序列的长度result = result < subLength ? result : subLength;sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}
};

四、模拟过程

坚持循环不变量原则，就是在循环中保持一定的规则、不变的因素。

例题1

vector<vector<int>> vc ：代表右下左上四个方向的dx与dy。

class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<int> v( n, 0 );vector<vector<int>> vv(n, v);vector<vector<int>> vc = {//int vc[][]{ 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 }};int x = 0;int y = 0;int tmp = 1;vv[x][y] = 1;while (1) {if (tmp == n * n) break;for (int i = 0; i < 4; i++) {int dx = vc[i][0];int dy = vc[i][1];while (x+dx >=0 && x+dx <n && y+dy >=0 && y+dy < n && tmp<= n*n) {//越界情况if (vv[x + dx][y + dy] != 0)//已经赋值过的情况break;x += dx;y += dy;tmp++;vv[x][y] = tmp;if (tmp == n * n) break;};}}return vv;}
};

五、前缀和

前缀和的思想是重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。
sum[ i ] :代表nums[]数组中，下标为0 - i 的元素之和。
or nums[] 数组中前 i 个元素之和，下标为 0~ i-1的元素之和。

例题1

sum[ i ] :代表nums[]数组中，下标为0 - i 的元素之和。
要求 区间下标 [2, 5] 的区间和，那么应该是 sum[5] - sum[1].

class Solution {
public:int takeSum(vector<int>nums, int n, int m) {int presum = 0;vector<int> pre(nums.size()-1 , 0);for(int i = 0; i < nums.size(); i++){presum += nums[i];pre[i] = presum;}return pre[m] - pre[n-1];};