移除元素
思路：使用双指针算法，分别维护一个快指针和一个慢指针，如果需要当前元素需要删除就只移动快指针，否则快慢指针同时移动，并将快指针元素放到慢指针处。
注意数组不用满足单调性
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int j = 0;
for (int i = 0; i < nums.size(); i ++) {
if (val != nums[i]) {
nums[j ++] = nums[i];
}
}
return j;
}
};
练习题目：
删除有序数组中的重复项
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int j = 1;
for (int i = 1; i < nums.size(); i ++) {
if (nums[i] != nums[i - 1]) {
nums[j ++] = nums[i];
}
}
return j;
}
};
先将所有的零删除并统计零的个数，最后将数组的后面添加零
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cnt = 0, j = 0;
for (int i = 0; i < nums.size(); i ++) {
if (nums[i] != 0) {
nums[j ++] = nums[i];
} else {
cnt ++;
}
}
for (int i = nums.size() - 1, k = 0; k < cnt; k ++, i --) {
nums[i] = 0;
}
}
};
模拟栈构建字符串，精妙
class Solution {
public:
string tackle(string s) {
string res;
for (int i = 0; i < s.size(); i ++) {
if (s[i] != '#') {
res.push_back(s[i]);
} else if (!res.empty()) {
res.pop_back();
}
}
return res;
}
bool backspaceCompare(string s, string t) {
return tackle(s) == tackle(t);
}
};
有序数组的平方
最朴素的想法-平方后进行排序
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for (int i = 0; i < nums.size(); i ++) {
nums[i] *= nums[i];
}
sort(nums.begin(), nums.end());
return nums;
}
};
因为数组是有序的，所以最大的数只能在数组的两头产生，我们使用双指针进行枚举即可。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int>res(n);
int pos = n - 1;
for (int i = 0, j = n - 1; i <= j; ) {
if (nums[i] * nums[i] >= nums[j] * nums[j]) {
res[pos --] = nums[i] * nums[i];
i ++;
} else {
res[pos --] = nums[j] * nums[j];
j --;
}
}
return res;
}
};
长度最小的子数组
维护一个滑动窗口，在每次添加元素和删除元素的时候都进行检查即可得到最短的长度。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int length = n + 1;
for (int i = 0, j = 0, cnt = 0; i < n; i ++) {
cnt += nums[i];
if (cnt >= target) {
length = min(length, i - j + 1);
while (cnt >= target && j <= i) {
cnt -= nums[j ++];
if (cnt >= target) length = min(length, i - j + 1);
}
}
}
return length == n + 1 ? 0 : length;
}
};
904. 水果成篮
感觉很好的一道题目
滑动窗口的思想，但是不同的地方在于本题中我们可以存放两种不同的数，所以我们可以使用map来进行存放，这样就能知道当前篮子中存在多少中数了。
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size();
unordered_map<int,int>mp;
int cnt = 0;
for (int i = 0, j = 0; i < n; i ++) {
mp[fruits[i]] ++;
while (mp.size() > 2) {
auto it = mp.find(fruits[j ++]);
it->second --;
if (it->second == 0) mp.erase(it);
}
cnt = max(cnt, i - j + 1);
}
return cnt;
}
};
本题的思想不难想到，就是在维护滑动窗口的时候用两个哈希表去判断当前是否满足条件，注意在写check函数的时候不要将两个哈希表作为参数传进去，否则会超时。
class Solution {
public:
unordered_map <char,int>cnt, mp;
bool check() {
for (const auto &x : cnt) {
if (mp[x.first] < x.second) return false;
}
return true;
}
string minWindow(string s, string t) {
int n = s.size(), m = t.size();
for (int i = 0; i < m; i ++) {
cnt[t[i]] ++;
}
int l = -1, c = n + 1;
for (int i = 0, j = 0; i < n; i ++) {
mp[s[i]] ++;
while (check() && j <= i) {
if (c > i - j + 1) l = j, c = i - j + 1;
mp[s[j ++]] --;
}
}
return l == -1 ? "" : s.substr(l, c);
}
};
螺旋矩阵
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>>res(n, vector<int>(n));
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int d = 1;
int x = 0, y = 0, a = 0, b = 0;
for (int i = 0; i < n * n; i ++) {
res[x][y] = i + 1;
a = a + dx[d], b = b + dy[d];
if (a < 0 || a >= n || b < 0 || b >= n || res[a][b]) {
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
return res;
}
};
class Solution {
public:
vector<int> spiralArray(vector<vector<int>>& array) {
if (array.size() == 0 || array[0].size() == 0) return {};
int n = array.size(), m = array[0].size();
vector<vector<int>>visited(n, vector<int>(m));
vector<int>res;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int d = 1, x = 0, y = 0, a, b;
for (int i = 0; i < n * m; i ++) {
res.push_back(array[x][y]);
visited[x][y] = true;
a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= n || b < 0 || b >= m || visited[a][b]) {
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
return res;
}
};
