数据结构与算法汇总整理篇——数组与字符串双指针与滑动窗口的联系学习及框架思考
数组
数组精髓：循环不变量原则
数组是存放在连续内存空间上的相同类型数据的集合，通过索引(下标)访问元素，索引从0开始
随机访问快(O(1)时间复杂度)；插入删除慢(需要移动元素)；长度固定(部分语言中可动态调整)
其存储列表数据，可用于实现栈和队列；多维数组用于矩阵运算；缓存数据(buffer)
二分查找
(先右再左，闭区间变化在右，右边界差异)：
(1)左闭右闭
(1) while (left <= right) 要使⽤ <= ，因为left == right是有意义的，所以使⽤ <=
(2) if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]⼀定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
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;
}(2)左闭右开
(1) while (left < right)，这⾥使⽤ < ,因为left == right在区间[left, right)是没有意义的
(2) if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，⽽寻找区间是左闭右开区间，所以right更新为middle，即：下⼀个查询区间不会去⽐较nums[middle]
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;
}搜索插入位置
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int right = nums.size();int left = 0;int res = nums.size();while(left < right){int mid = left + ((right - left) >> 1);if(nums[mid] >= target){res = mid;right = mid;}else{left = mid +1;}}return res;}
};在有序数组中查找元素的第一个和最后一个位置
class Solution {public:vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n-1;while(left <= right){int mid = left + ((right - left) >> 1);if(nums[mid] == target){int l = mid, r = mid;while(l>=0 && nums[l] == target) l--;while(r < n && nums[r] == target) r++;return {l+1, r-1};}else if( nums[mid] > target){right = mid - 1;}else{left = mid + 1;}}return { -1, -1};}
};x的平方根
class Solution {
public:int mySqrt(int x) {int res = x;int left =0, right = x;while(left <= right){int mid = left + ((right - left) >> 1);if((long long)mid * mid <= x){ //往目标值靠近res =mid;left = mid + 1;}else{right = mid -1; //收缩}}return res;}
};有效的完全平方数
(开区间方法一般，容易缺失一些情况考虑)
class Solution {
public:bool isPerfectSquare(int num) {int left = 0, right = num;while(left <= right){int mid = left + ((right - left) >> 1);if((long)mid * mid < num){ left = mid + 1;}else if ((long)mid * mid > num){right = mid - 1;}else return true;}return false;}
};双指针
通过⼀个快指针和慢指针在⼀个for循环下完成两个for循环的⼯作
相向移动
有序数组的平方
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int len = nums.size();int index = len -1;vector<int> res(len,0);for(int i = 0, j = len -1; i <= j; ){ // 取等防止遗漏数据if(nums[i] * nums[i] > nums[j] * nums[j]){ // 需要从后处理起res[index--] = nums[i] * nums[i];i++;}else{res[index--] = nums[j] * nums[j];j--;}}return res;}vector<int> sortedSquares2(vector<int>& nums) {nums[0] = nums[0] * nums[0];int j;for(int i = 1; i < nums.size(); i++){int tmp = nums[i] * nums[i];for(j = i-1; j >= 0; j--){if(tmp < nums[j])nums[j+1] = nums[j]; // 大数往后插入elsebreak; //进行一次即可}nums[j+1] = tmp;}return nums;}
};同向移动
比较含退格的字符串
(退格问题也可以用栈完成)
class Solution {
public:bool backspaceCompare(string s, string t) {int sSkipNum = 0;int tSkipNum = 0;int i = s.size() -1;int j = t.size() - 1;while(1){while(i >= 0){if(s[i] == '#')sSkipNum++;else{if(sSkipNum) sSkipNum--;else break;}i--;}while(j >= 0){if(t[j] == '#')tSkipNum++;else{if(tSkipNum) tSkipNum--;else break;}j--;}if(i <0 || j < 0){ //长度不一break;}else if(s[i] != t[j]) //如果两个字符串相同，退格后也理应相同return false;i--;j--;}//同时遍历完毕if(i <0 && j < 0)return true;elsereturn false;}
};移动零
class Solution {
public:void moveZeroes(vector<int>& nums) {int len = nums.size(), left = 0, right = 0;// 右指针全遍历，左指针跟踪0while(right < len){if(nums[right]){swap(nums[left], nums[right]);left++;}right++;}}
};删除有序数组中的重复项
class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 1; //跟踪数据int fast = 1; //遍历for( ; fast < nums.size(); fast++){if(nums[fast] == nums[fast -1]){;}if(nums[fast] != nums[fast-1]){nums[slow++] = nums[fast];}}return slow;}
};移除元素
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0; //收集结果int fast = 0; //遍历for( ; fast < nums.size(); fast++){if(nums[fast] != val)nums[slow++] = nums[fast];}return slow;}
};滑动窗口
就是不断的调节⼦序列的起始位置和终⽌位置，从⽽得出我们要想的结果
滑动窗⼝的精妙之处在于根据当前⼦序列和⼤⼩的情况，不断调节⼦序列的起始位置
方法论
int left = 0, right = 0;while (right < s.size()) {// 增大窗口window.add(s[right]);right++;while (window needs shrink) {// 缩小窗口window.remove(s[left]);left++;}
}窗口控制技巧： 善于利用哈希表，这一数据结构。(哈希集合和哈希映射等)都可以做窗口
(第一层遍历右边界，第二层遍历左边界) 可以用哈希表来处理第二层的边界！
void slidingWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0; while (right < s.size()) {// c 是将移入窗口的字符char c = s[right];// 右移窗口right++;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/printf("window: [%d, %d)\n", left, right);/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d = s[left];// 左移窗口left++;// 进行窗口内数据的一系列更新...}}
}长度最小的子数组
class Solution {public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX;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;}
};水果成篮
class Solution {
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();vector<int> tree(100001, 0);int kind = 0;int left = 0;int res = 0;for(int right = 0; right < n; right++){tree[fruits[right]]++;if(tree[fruits[right]] == 1)kind++;while(kind > 2){ // 开始滑动tree[fruits[left]]--;if(tree[fruits[left]] == 0)kind--;left++; //子序列起始位置}res = max(res, right - left + 1);}return res == 0 ? 0 : res;}
};(右边界移动，左边界不动，左边界移动，右边界不动)
(右边界先移动，找到满足条件，左边界压缩搜索,最优解产生在左边界向右移动过程中)
最小覆盖子串
(s 中 覆盖 t)
class Solution {
public:string minWindow(string s, string t) {unordered_map<char, int> tmap, smap;int left = 0, correct = 0;string res = s;for(char item : t){tmap[item]++;}for(int right = 0; right < s.size(); ++right){smap[s[right]]++; //顺便统计词频if(tmap[s[right]] >= smap[s[right]]) //当前字符的词频++correct;while(smap[s[left]] > tmap[s[left]]) //左边界索引的词频--smap[s[left++]]; //同时左边界右移if(correct == t.size()){res = right - left +1 < res.size() ? s.substr(left, right - left +1) : res;}}return correct == t.size()? res : "";}
};无重复字符的最长子串
class Solution {
public:int lengthOfLongestSubstring(string& s) {unordered_map<char, int> hash_map; //char2indexint left = -1, res = 0, len = s.size();for(int i = 0; i < len; i++){if(hash_map.find(s[i]) != hash_map.end())left = max(left, hash_map.find(s[i])->second); //find 返回迭代器hash_map[s[i]] = i; //记录字符的索引值res = max(res, i-left);}return res;}
};多维数组模拟
螺旋矩阵II
class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int>(n,0));int count = 0;int loop = n/2;int mid = n/2;int startx = 0, starty = 0;int offset = 1;while(loop--){ //圈数int i = startx;int j = starty;for( ; j < n-offset; j++)res[i][j] = ++count; //向右for(; i < n -offset; i++)res[i][j] = ++count; //向下for( ; j > starty; j--)res[i][j] = ++count; //向左for(; i > startx; i--)res[i][j] = ++count; //向上startx++;starty++;offset++;}if(n%2)res[mid][mid] = ++count;return res;}vector<vector<int>> generateMatrix2(int n) {vector<vector<int>> res(n, vector<int>(n, 0));int top = 0, right = n -1, left = 0, bottom = n -1;int count = 0;while(true){for(int i =left; i <= right; ++i) res[top][i] = ++count;if(++top > bottom) break; // 收缩边界for(int i =top; i <= bottom; ++i) res[i][right] = ++count;if(--right < left) break;for(int i = right; i >= left; --i) res[bottom][i] = ++count;if(--bottom < top) break;for(int i = bottom; i>= top; --i) res[i][left] = ++count;if(++left > right) break;}return res;}
};旋转矩阵
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();//水平rotatefor(int i = 0; i < n/2; ++i){for(int j = 0; j < n; ++j){swap(matrix[i][j], matrix[n-1-i][j]);}}//主对角线rotatefor(int i = 0; i< n; ++i){for(int j = 0; j<i; ++j){swap(matrix[i][j], matrix[j][i]);}}}void rotate2(vector<vector<int>>& matrix) {int n = matrix.size();for(int i = 0; i< n/2; i++){for(int j = 0; j < (n+1)/2; j++){swap(matrix[i][j], matrix[j][n-i-1]);swap(matrix[i][j], matrix[n-i-1][n-j-1]);swap(matrix[i][j], matrix[n-j-1][i]);}}}
};字符串
字符串本质：近似为包含结束符的字符数组，字符的有序序列，用于文本数据。字符串通常是不可变的(immutable)
反转操作系列
关于交换
/* 数值交换 */
int tmp = s[i];
s[i] = s[j];
s[j] = tmp;/* 位运算 异或运算 */
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];反转字符串II
class Solution {private:void myrever(string& s, int start, int end){for(int i = start, j = end; i<j; i++, j--){s[i] ^= s[j];s[j] ^= s[i];s[i] ^= s[j];}}
public:string reverseStr(string s, int k) {int len = s.size();for(int i = 0; i < len; i += 2*k){if(i + k < len){myrever(s, i, i+k-1);}else{myrever(s, i, len-1);}}return s;}
};移除多余空格 (双指针)
void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。int slow = 0;for (int i = 0; i < s.size(); ++i) { if (s[i] != ' ') { //遇到⾮空格就处理，即删除所有空格。if (slow != 0) s[slow++] = ' '; //⼿动控制空格，给单词之间添加空格。 slow != 0说明不是第⼀个单词，需要在单词前添加空格。while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。s[slow++] = s[i++];}}}s.resize(slow); //slow的⼤⼩即为去除多余空格后的⼤⼩。
}反转字符串中的单词
class Solution {private:void my_rever(string& s, int start, int end){for(int i = start, j =end; i < j; i++, j--){swap(s[i], s[j]);}}void removeSpaces(string& s){int slow = 0;for(int fast = 0; fast < s.size(); fast++){if(s[fast] != ' '){if(slow != 0) s[slow++] = ' '; //中间补充单词间隔while(fast < s.size() && s[fast] != ' ') //内循环需要控制边界s[slow++] = s[fast++];}}s.resize(slow);}
public:string reverseWords(string s) {removeSpaces(s);my_rever(s, 0, s.size()-1);int word_start = 0;for(int i = 0; i <= s.size(); i++){ // 左闭右闭区间if(i == s.size() || s[i] == ' '){my_rever(s, word_start, i-1); //翻转，是左闭右闭 []的翻转。word_start = i+1;}}return s;}
};动态口令
(整体反转 + 局部反转)
class Solution {private:void str_reverse(string& s, int start, int end){for(int i = start, j = end; i < j; i++, j--){s[i] ^= s[j];s[j] ^= s[i];s[i] ^= s[j];}}
public:string dynamicPassword(string password, int target) {int len = password.size();str_reverse(password, 0, target-1);str_reverse(password, target, len-1);str_reverse(password, 0, len-1);return password;}
};