977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II ，总结
有序数组的平方
暴力
每个数平方之后，快排，O（n+logn）。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i = 0; i < nums.size(); i++) {
nums[i] = nums[i] * nums[i];
}
sort(nums.begin(), nums.end());
return nums;
}
};
双指针
依照左右两端绝对值最大，平方最大，从两边往中间搜索，需要新空间，O(n)。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector <int> ans(nums.size(), 0);
int left = 0;
int right = nums.size() - 1;
int index = right;
while(left <= right) {
int _left = nums[left] * nums[left];
int _right = nums[right] * nums[right];
if(_left <= _right) {
ans[index--] = _right;
right--;
}
else {
ans[index--] = _left;
left++;
}
}
return ans;
}
};
C#
public class Solution {
public int[] SortedSquares(int[] nums) {
int left = 0;
int right = nums.Length - 1;
int index = right;
int []ans = new int[nums.Length];
while(left <= right) {
int _left = nums[left] * nums[left];
int _right = nums[right] * nums[right];
if(_left <= _right) {
ans[index--] = _right;
right--;
} else {
ans[index--] = _left;
left++;
}
}
return ans;
}
}
长度最小的子数组
暴力
遍历两次，第一次遍历每个元素，第二次往后找连续元素。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int max = 10001;
for(int i = 0; i < nums.size(); i++) {
int ans = 0;
for(int j = i; j < nums.size(); j++) {
ans += nums[j];
if(ans >= target) {
if(j - i + 1 < max) {
max = j - i + 1;
}
break;
}
}
}
if(max == 10001) {
return 0;
} else {
return max;
}
return 0;
}
};
滑动窗口
一次遍历右指针不断移动窗口的终止位置，同时在保证窗口内元素值总和大于等于target的条件下不断收缩窗口的起始位置来更新窗口的起始位置，O(n)。滑动窗口的结束指针是for循环的遍历项，重点和难点是怎么在尾指针遍历的时候合理的移动头指针，比如这道题就是根据窗口区间和>=target来决定头指针的移动，进而决定区间的长度
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0;
int sum = 0;
int result = INT32_MAX;
for(int right = 0; right < nums.size(); right++) {
sum += nums[right];
while(sum >= target) {
result = result > right - left + 1 ? right - left + 1 : result;
sum -= nums[left++];
}
}
result = result == INT32_MAX ? 0 : result;
return result;
}
};
C#
public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int result = int.MaxValue;
for(int right = 0; right < nums.Length; right++) {
sum += nums[right];
while(sum >= target) {
result = result > right - left + 1 ? right - left + 1 : result;
sum -= nums[left++];
}
}
result = result == int.MaxValue ? 0 : result;
return result;
}
}
螺旋矩阵
模拟题，重点是定义清楚在四个方向上的循环区间和循环的次数，更新量。
- 每次填元素的区间都是左闭右开，这样循环一周下来是闭合的。
- 循环的次数是n / 2,因为每循环一次，一个方向就收缩两倍。
- 如果n是奇数，中间会空出来一格，补上。
模拟1
按照左上->右上->右下->左上的顺时针顺序来，这样的好处是，过程中i,j都可以重用，实际上startX,startY和n - offset就是每一个方向上遍历时的区间端点，他们是对称的，如果重用已经累加过的i，j，数组下标那相对简洁一些。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int startx = 0;
int starty = 0;
int loop = n / 2;
int cnt = 1;
int offset = 1;
vector<vector<int>> ans(n, vector<int>(n, 0));
while(loop --) {
int i, j;
//从左上到右上,i不变，j累加
for(j = starty ; j < n - offset; j++) {
ans[startx][j] = cnt++;
}
//从右上到右下，j不变，i累加
for(i = startx; i < n - offset; i++) {
ans[i][j] = cnt++;
}
//从右下到左下，i不变，j累减
for(; j > startx; j--) {
ans[i][j] = cnt++;
}
//从左下到左上，j不变，i累减
for(; i> starty; i--) {
ans[i][j] = cnt++;
}
startx++;
starty++;
offset++;
}
if(n % 2 == 1) {
ans[n / 2][n / 2] = cnt;
}
return ans;
}
};
模拟2
实际上循环的过程中，每一个方向遍历时，总有一个索引是不动的，这么写也一样。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int startx = 0;
int starty = 0;
int loop = n / 2;
int cnt = 1;
int offset = 1;
vector<vector<int>> ans(n, vector<int>(n, 0));
while(loop --) {
int i, j;
//从左上到右上,i不变，j累加
for(j = starty ; j < n - offset; j++) {
ans[startx][j] = cnt++;
}
//从右上到右下，j不变，i累加
for(i = startx; i < n - offset; i++) {
ans[i][n - offset] = cnt++;
}
//从右下到左下，i不变，j累减
for(; j > startx; j--) {
ans[n - offset][j] = cnt++;
}
//从左下到左上，j不变，i累减
for(; i> starty; i--) {
ans[i][starty] = cnt++;
}
startx++;
starty++;
offset++;
}
if(n % 2 == 1) {
ans[n / 2][n / 2] = cnt;
}
return ans;
}
};
C#
索引精简，注意交错数组的初始化和二维数组不一样，C#判断条件==0 ==1 不能不写。
public class Solution {
public int[][] GenerateMatrix(int n) {
//交错数组
int[][] ans = new int[n][];
for(int i = 0; i < n; i++)
ans[i] = new int[n];
int loop = n / 2;
int start = 0;
int end = n - 1;
int cnt = 1;
while(loop-- > 0) {
for(int i = start; i < end; i++) {
ans[start][i] = cnt++;
}
for(int i = start; i < end; i++) {
ans[i][end] = cnt++;
}
for(int i = end; i > start; i--) {
ans[end][i] = cnt++;
}
for(int i = end; i > start; i--) {
ans[i][start] = cnt++;
}
start++;
end--;
}
if(n % 2 == 1) {
ans[n / 2][n / 2] = cnt;
}
return ans;
}
}
二刷
有序数组的平方
两边的数绝对值最大，所以结果不是最左边就是最优先，注意要求从小到大，可以先开闭指定大小的数组，避免reverse;
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
class Soltuion {
public:
vector<int> doit(vector<int>& nums) {
int left = 0;
vector<int> res;
//vector <int> ans(nums.size(), 0);
int right = nums.size() - 1;
while (left <= right) {
int nleft = abs(nums[left]);
int nright = abs(nums[right]);
if ( nleft >= nright) {
res.push_back(nleft * nleft);
left++;
}
else {
res.push_back(nright * nright);
right--;
}
}
reverse(res.begin(), res.end());
return res;
}
};
int main() {
while (1) {
int temp = 0;
vector<int> res;
while (cin >> temp) {
res.push_back(temp);
}
Soltuion s1;
vector<int> ans = s1.doit(res);
for (auto item : ans) {
cout << item << " ";
}
cout << endl;
return 0;
}
}
长度最小的子数组
暴力遍历所有子数组会超时
int left = 0;
int right = 0;
int sum = 0;
int res = INT_MAX;
for (right; right < nums.size(); right++) {
sum += nums[right];
while (sum >= target) {
res = res > right - left + 1 ? right - left + 1 : res;
sum -= nums[left++];
}
}
return res == INT_MAX ? 0 : res;
}
滑动窗口，右边界进元素，左边界出元素，最好用for，右边界是遍历递增的，注意写法，先记录结果再收缩左边界会简洁一些。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0;
int right = 0;
int sum = 0;
int res = INT_MAX;
while (right < nums.size()) {
sum += nums[right];
/* while(left < nums.size() - 1 && sum - nums[left] >= target) {
sum -= nums[left++];
}
if (sum >= target) {
res = min(res, right - left + 1);
}
right++;*/
while (sum >= target) {
res = min(res, right - left + 1);
sum -= nums[left++];
}
right++;
}
return res == INT_MAX ? 0 : res;
}
};
水果成篮
滑动窗口，右边界移动还是遍历，把新水果的种类加入到map中计数，如果map中存在两个以上的key说明超了，开始收缩左边界，左边界收缩直到map中仅有两个key（当一个key的value为0时erase他），这题不用哈希表还真不好模拟，主要map.cnt > 2不借助容器不好整。
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Solution {
public:
int doit(vector<int>& fruits) {
int left = 0;
int right = 0;
unordered_map<int, int> map;
int res = 0;
int ans = INT_MIN;
for (right; right < fruits.size(); right++) {
map[fruits[right]]++;
while (map.size() > 2) {
auto it = map.find(fruits[left]);
--it->second;
if (it->second == 0) {
map.erase(it);
}
++left;
}
ans = right - left + 1 > ans ? right - left + 1 : ans;
}
return ans;
}
};
int main() {
vector<int> fruits;
int n = 0;
cin >> n;
int temp = 0;
for (int i = 0; i < n; i++) {
cin >> temp;
fruits.push_back(temp);
}
Solution s1;
cout << s1.doit(fruits);
return 0;
}
最小覆盖子串
感觉官方和题解里面的都不是很清晰，有关边界移动的思想都是差不多的，但落实到实现觉得自己这么写比较清晰，同时加了测试输出方便观察（ACM模式写的完整输入输出）。
- 难点一：判断符合最小覆盖的条件该怎么实现：使用一个Map即可（两个map比较有点浪费空间），首先记录t中各个字符出现的次数，在遍历s时，找到就-1，只要所有的map元素出现次数都为0，即代表符合条件。
- 难点二：窗口右边界通过for不断遍历元素，一直减map中的元素，那么左边界收缩移动对应的条件是：map中所有元素出现的次数都 <=0,代表每个t中元素都至少在窗口中出现对应需要的次数，可以多出现，可以恰好，如果恰好，可能前缀有不需要的元素需要剔除，如果多出现，需要剔除多余的元素，并将map计数+1（多一步操作，因此这两个if条件不能合并）。
- 难点三：也是测试样例不容易通过的一点：一旦左边界开始收缩，可能遇到一个不需要的元素，剔除完后面又是多余的元素，也可能剔除完多余的元素，后面又出现了不需要的元素，这两种情况可能交替出现，因此他俩应该是并列的if，外层用while控制不断循环，while的条件即map中所有元素出现的次数都<=0。
- 难点四: 记录结果，一旦左边界收缩结束，就应该记录结果，可以放在收缩外，但还要写一遍check条件，不如直接在while内收缩完毕break之前直接记录即可。
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Solution {
public:
bool check(unordered_map<char, int>& data) {
bool flag = true;
for (auto item : data) {
if (item.second > 0) { //数量恰好和多余都通过检验
flag = false;
}
}
if (flag)
cout << "true" << endl;
else
cout << "false" << endl;
return flag;
}
string doit(string s, string t) {
unordered_map<char, int> data;
for (const auto item : t) {
data[item]++;
}
int left = 0;
int ans = 0;
int minLen = INT_MAX;
string minSubstr;
for (int right = 0; right < s.size(); right++) {
auto it = data.find(s[right]);
//削减计数
if (it != data.end()) {
--it->second;
//cout << right << " " << it->first << " " << it->second << endl;
}
while (check(data)) {
//左边界收缩检查是否有多余的单词(t不需要的和需要担多的)
auto leftit = data.find(s[left]);
//t中找不到不需要
if (leftit == data.end()) {
//cout << "不需要，left移动:" << s[left] << " " << left << endl;
left++;
}
//t中找得到但s子串数量已够多余
else if(leftit->second < 0) {
left++;
++leftit->second;
//cout << "多余，left移动: " << left << "计数+1 " << leftit->first << " " << leftit->second << endl;
}
//收缩完成，保存本轮结果，跳出
else {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minSubstr = s.substr(left, right - left + 1);
//cout << "minLen: " << minLen << " " << minSubstr << endl;
}
break;
}
//cout << "当前left指针：" << left << "当前right： " << right << endl;
}
//cout << endl;
}
return minSubstr;
}
};
int main() {
string s;
string t;
cin >> s >> t;
Solution s1;
cout << s1.doit(s, t);
return 0;
}
螺旋矩阵
注意边界的可循环，左闭右开，二刷15min，用的for循环控制，用while (cnt < k * k)也可。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> ans(n, vector<int>(n, 0));
int k = 1;
for (int step = 0; step < (n / 2); step++) {
int line = step;
int column = step;
for (column; column < n - step - 1; column++) {
ans[line][column] = k++;
}
for (line; line < n - step - 1; line++) {
ans[line][column] = k++;
}
for (column; column > step; column--) {
ans[line][column] = k++;
}
for (line; line > step; line--) {
ans[line][column] = k++;
}
}
if (n % 2 == 1) {
ans[n / 2][n / 2] = k;
}
return ans;
}
};
数组小结
- 二分，常用左闭右闭，左闭右开，左开右闭和左闭右闭注意边界条件，核心是搜索区间的固定不变。
- 在排序数组中查找元素的第一个和最后一个位置，两次二分，为了找第一个和最后一个位置，收敛搜索区间，当找到元素时不停，控制mid分别向左或者向右即可。
- 搜索插入位置，二分找到第一个大于等于target的数（有序），区间是左闭右开（因为mid的可以取大于target的数），如果有目标，就直接返回，mid小于target，向右搜索，mid大于target，向左包括当前点搜索，最后截止时left = right （循环条件是left < right）,就是插入点。（三刷再想想）
- 删除元素，双快慢指针，可以在一次遍历完成两次遍历的事情，降复杂度。
- 有序数组的平方，双指针从两边往中间搜，也是一次遍历能干两次遍历的事情，设计方式不一样，这个是两边往中间。
- 长度最小的子数组，滑动窗口（双指针），尾指针遍历的同时，根据当前你窗口内和是否超过限制移动头指针，更新窗口区间和记录值。
- 水果成篮，滑动窗口，右边界移动向map中加入新水果的计数，当水果种类超过限制时，左边界收缩直到map中的key回到2，借助哈希表实现。
- 最小覆盖子数组，滑动窗口，右边界向map中加入可能符合需要字符的记录（实际实现在计数--），左边界触发收缩的条件是计数<=0,收缩有量两种情况，可能交替进行，外层while控制（水果成篮和长度最小子数组一层while就够，不像这么麻烦），同时注意满足条件要break，否则一直循环（因为条件符合也可能还可以收缩【有不需要的元素】，不能在while条件语句中以此跳出，必须单独考虑break），break之前记录最短子串。
- 螺旋矩阵，模拟，搞清楚左闭右开的循环区间，分清楚行列和子循环之间的递进关系（start++,end--）。
巧用双指针，让两次遍历数组的事情在一次遍历就可以完成是重点，代码随想录总结
- 三刷理解一下二分法扩展的几道题，控制收敛方向来确保是第一个找到的元素的思想。
京公网安备 11010502036488号