代码随想录算法训练营一刷总结

不知不觉两个月过去了，陆陆续续还是把代码随想录一刷结束，很早之前就知道代码随想录的存在，但是一直没有能一股气把所有题目过一遍，刚开学的时候正好看到算法训练营的报名，想着趁此机会让自己的算法刷题踏上正轨，作为结尾，把这段时间的题目好好整理一遍思路，作为后面刷题的基石

我的整理方式是模拟实战做题时的感受，主要想法是提取问题本质尽可能化为具象的数学模型
往后会持续更新，主要是记录实战过程中遇到的题目将其归类到后面的思想方法中去。

二分查找

解决问题：
给定一个 $n$ 个元素有序的（升序）整型数组 $nums$ 和一个目标值 $target$ ，写一个函数搜索 $nums$ 中的 $target$，如果目标值存在返回下标，否则返回 -1
二分查找的意义在于通过二分将遍历的复杂度$O(n)$降低为$O({\log }_{2}n)$，故二分的优化意义大于对问题的解决意义
借助题目展现代码细节
704. 二分查找
在实现代码的过程中用到了循环不变量的概念，在这里体现为区间，我们整个过程中查找的区间的定义是什么？如果我们的定义是$[left,right]$,那么此时的代码实现为：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int middle = (left + right) / 2; //关于middle的两种写法在之前的文章有讨论
            if (nums[middle] == target) return middle;
            else if (nums[middle] > target) {
                right = middle - 1;
            }
            else {
                left = middle + 1;
            }
        }
        return -1;
    }
};

关于$middle$的两种写法
再借助一道其他题目体会
34. 在排序数组中查找元素的第一个和最后一个位置
题目描述：
给你一个按照非递减顺序排列的整数数组 $nums$，和一个目标值 $target$。请你找出给定目标值在数组中的开始位置和结束位置,如果数组中不存在目标值 $target$，返回 $[-1,-1]$。你必须设计并实现时间复杂度为 $O(lo{g}_{k}n)$的算法解决此问题。
我们的关注点需要集中于如何将本题转化为原有题目的模型
原问题$⟺$查找目标值的区间$⟺$查找第一个小于目标值与第一个大于目标值的位置
如是我们明白二分查找真正常用的是查找特定区间而非特定值
我们尝试去推导这个问题：
记住一句话，二分查找本质是分而治之，我们不仅要关心查找的位置，更要关心这个位置两边元素的特征，以左闭右闭为例，$right$代表的是在其右边(包括自己)的元素都大于等于$target$（此处理论上是大于，但是在区间问题中应有所变化）,$left$代表的是在其左边的元素（包括自己）都小于$target$，而这个特点在整个循环过程中没有发生改变，我们能否利用这一点推导出我们想要的区间位置?
很显然最后的结果一定是$left$的位置即是第一个$target$的位置
同理当我们改变$left$和$right$的含义之后，我们可以得到类似的结果
那么我们得到代码实现结果：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        vector<int> result(2, -1);
        bool tmp = false;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] == target) {
                tmp = true;
                break;
            }
            else if (nums[middle] > target) {
                right = middle - 1;
            }
            else {
                left = middle + 1;
            }
        }
        if (!tmp) return result;
        left = 0;
        right = nums.size() - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] >= target) {
                right = middle - 1;
            }
            else {
                left = middle + 1;
            }
        }
        result[0] = left;
        left = 0;
        right = nums.size() - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            }
            else {
                left = middle + 1;
            }
        }
        result[1] = right;
        return result;
    }
};

双指针

双指针法（快慢指针法）在数组和链表的操作中非常常见
双指针法本质是改变了遍历方式，使得遍历过程无回溯，故而降低了时间复杂度，我们不妨将数组的一般遍历看作$right$指针不动的特殊双指针
1.同向双指针
2.异向双指针
例题：345. 反转字符串中的元音字母

给你一个字符串 $s$ ，仅反转字符串中的所有元音字母，并返回结果字符串。元音字母包括 ${}^{\prime }{a}^{\prime }{,}^{\prime }{e}^{\prime }{,}^{\prime }{i}^{\prime }{,}^{\prime }{o}^{\prime }{,}^{\prime }{u}^{\prime }$，且可能以大小写两种形式出现不止一次。

反转元音字母$⟺$反转序列中的特殊字符$⟺$反转序列
在此题中，我们需要改变的无非是增加一些$left$与$right$指针的移动条件
简而言之，双指针的问题的关键就在于指针移动的条件

class Solution {
public:
    string reverseVowels(string s) {
        int left = 0, right = s.size() - 1;
        unordered_set<char> hashset = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        while (left <= right) {
            if (hashset.count(s[left]) <= 0) {
                left++;
            }
            else if (hashset.count(s[right]) <= 0) {
                right--;
            }
            else {
                char temp = s[left];
                s[left] = s[right];
                s[right] = temp;
                left++;
                right--;
            }
        }
        return s;
    }
};