1、移除元素
1.1 删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
慢指针指向第一个元素，快指针指向第二个元素
如果快指针不等于前一个指针指向的值，慢指针向前移动，并且把快指针的值赋给慢指针
如果相同，不操作，快指针继续前进
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slowIndex=0;
for(int i=1;i<nums.size();i++){
if(nums[i]!=nums[slowIndex]){
slowIndex++;
nums[slowIndex]=nums[i];
}
}
return slowIndex+1;
}
};1.2 比较含退格的字符串
https://leetcode.cn/problems/backspace-string-compare/description/
class Solution {
public:
bool backspaceCompare(string S, string T) {
string s;
string t;
for(int i=0;i<S.size();i++){
if(S[i]!='#') s+=S[i];
else if(!s.empty()){
s.pop_back();
}
}
for(int i=0;i<T.size();i++){
if(T[i]!='#') t+=T[i];
else if(!t.empty()){
t.pop_back();
}
}
if(s==t) return true;
return false;
}
};1.3 有序数组的平方
https://leetcode.cn/problems/squares-of-a-sorted-array/description/
因为题目说的是非递减顺序
指针分别指向第一个和最后一个的
比较大小如果最左边的大就平方放到一个新数组里面，然后指针向右边移动一位，数组指针--
最右边的大就平方放到数组指针指向的位置，然后指针向左移动一位，数组指针--
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n=nums.size();
vector<int> ans(n);
int left=0,right=n-1;
int index=n-1; // 指向数组的最后一位
while(left<=right){
if(abs(nums[left])>abs(nums[right])){
ans[index]=nums[left]*nums[left];
index--;
left++;
}else{
ans[index]=nums[right]*nums[right];
index--;
right--;
}
}
return ans;
}
};2、长度最小的数组
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
两个for循环暴力解决
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum=0; // 子数列的和
int length=0; // 子数列的长度
int result = INT32_MAX;
for(int i=0;i<nums.size();i++){
sum=0;
for(int j=i;j<nums.size();j++){
sum+=nums[j];
if(sum>=target){
length = j - i + 1;
result = result < length ? result : length;
break;
}
}
}
return result == INT32_MAX ? 0 : result;
}
};滑动窗口
先固定好重点位置，然后一步一步的移动起始位置
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum=0; // 子数列的和
int length=0; // 子数列的长度
int result = INT32_MAX;
int i=0;
for(int j=0;j<nums.size();j++){
sum += nums[j];
while(sum>=target){
length = j-i+1;
result = result < length ? result : length;
sum = sum - nums[i];
i++;
}
}
return result == INT32_MAX ? 0 : result;
}
};2.1 水果成篮
https://leetcode.cn/problems/fruit-into-baskets/description/
如果进来的是新水果，当前的品种数+1
如果不是新水果，当前的计数+1
当品种超过两个的时候
左指针开始移动，如果j对应的数字的数量-1后为0，减少品种数
如果不是0，继续向右移动左指针
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int ans = 0;
unordered_map<int, int> cnt;
for (int i = 0, j = 0, s = 0; i < fruits.size(); i++) {
if (cnt[fruits[i]] == 0) // 新的水果种类
s++; // 增加品种数
cnt[fruits[i]]++; // 增加当前水果的计数
while (s > 2) { // 当品种超过两个时，缩小窗口
cnt[fruits[j]]--;
if (cnt[fruits[j]] == 0) // 如果某个种类的水果数量为0，则减少品种数
s--;
j++; // 移动左指针
}
ans = max(ans, i - j + 1); // 更新最大窗口长度
}
return ans;
}
};
3、螺旋矩阵II
https://leetcode.cn/problems/minimum-window-substring/description/
注意括号 左闭右开
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res (n,vector<int>(n,0)); //定义一个2维数组
int startx=0,starty=0; // 定义起始位置
int loop = n/2; // 定义转几圈
int mid = n/2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
int count=1;
int offset=1;
int i,j;
while(loop--){
i=startx;
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;
}
};3.1 螺旋矩阵
https://leetcode.cn/problems/spiral-matrix/description/
先定义上下左右的起始位置
第一行：
i从最左边开始，最大到右边界。下面要换到第二行了，所以t++。
最外面的一列
最下面一行
b不变，i--
最左边一列
l不变，i--
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(matrix.empty()) return {};
int l=0,r=matrix[0].size()-1,t=0,b=matrix.size()-1; // 定义上下左右的起始位置
vector<int> ans;
while (true){
for(int i = l;i <= r;i++) ans.push_back(matrix[t][i]);
t++;
if(t>b) break;
for(int i = t;i<=b;i++) ans.push_back(matrix[i][r]);
r--;
if(r<l) break;
for(int i=r;i>=l;i--) ans.push_back(matrix[b][i]);
b--;
if(b<t) break;
for(int i=b;i>=t;i--) ans.push_back(matrix[i][l]);
l++;
if(l>r) break;
}
return ans;
}
};3.2 螺旋遍历二维数组
https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/description/
一定要注意while的循环条件，如果写while(1)会报错
从左往右
int i=l;i<=r;i++ t++
从上往下
int i=t;i<=b;i++ r--;
从右往左
int i=r;i>=l;i-- b--;
从下往上
int i=b;i>=t;i-- l++
class Solution {
public:
vector<int> spiralArray(vector<vector<int>>& array) {
vector<int> res;
if (array.empty() || array[0].empty()) return res;
int l = 0, t = 0; // 左边界和上边界
int r = array[0].size() - 1; // 右边界
int b = array.size() - 1; // 下边界
while (l <= r && t <= b) {
// 从左往右
for (int i = l; i <= r; i++) {
res.push_back(array[t][i]);
}
t++;
if (t > b) break;
// 从上往下
for (int i = t; i <= b; i++) {
res.push_back(array[i][r]);
}
r--;
if (r < l) break;
// 从右往左
for (int i = r; i >= l; i--) {
res.push_back(array[b][i]);
}
b--;
if (b < t) break;
// 从下往上
for (int i = b; i >= t; i--) {
res.push_back(array[i][l]);
}
l++;
}
return res;
}
};
评论区