LeetCode Hot100 11~20
目录
- 子串
- 11. 滑动窗口最大值
- 12. 最小覆盖子串
- 数组
- 13. 最大子数组和
- 14. 合并区间
- 15. 翻转数组
- 16. 除数字自身以外的乘积
- 17. 缺失的第一个正数
- 矩阵
- 18. 矩阵置零
- 19. 螺旋矩阵
- 20 旋转图像90度
子串
11. 滑动窗口最大值
本题使用deque来维护一个单调队列 注意删除元素和添加元素的时机即可
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
deque<int> dq;
// 我们首先将前面K个数字加进去
for (int i = 0; i < k; i++) {
while(!dq.empty() && nums[i] > dq.back()) {
dq.pop_back();
}
dq.push_back(nums[i]);
}
ans.push_back(dq.front());
for (int i = k; i < nums.size(); i++) {
if (nums[i - k] == dq.front()) {
dq.pop_front();
}
while(!dq.empty() && nums[i] > dq.back()) {
dq.pop_back();
}
dq.push_back(nums[i]);
ans.push_back(dq.front());
}
return ans;
}
};
12. 最小覆盖子串
类似滑动窗口问题 再加上一个欠账表就可以解决 类似前面的最小子数组问题
public:
string minWindow(string s, string t) {
unordered_map<char , int> unmapBill;
for (auto ch : t) {
unmapBill[ch]++;
}
int lnBill = t.size();
int L = 0;
int R = 0;
int minL = 0;
int minR = 0;
int minWin = INT_MAX;
while (R < s.size()) {
if (unmapBill.count(s[R])) {
if (unmapBill[s[R]] > 0) {
lnBill--;
}
unmapBill[s[R]]--;
}
while(lnBill == 0) {
if ((R - L) < minWin) {
minL = L;
minR = R;
minWin = R - L;
}
if (unmapBill.count(s[L])) {
unmapBill[s[L]]++;
if (unmapBill[s[L]] > 0) {
lnBill++;
}
}
L++;
}
R++;
}
if(minWin == INT_MAX) {
return "";
}
string ans = s.substr(minL , minWin + 1);
return ans;
}
};
数组
13. 最大子数组和
很简单的动态规划
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size() , 0);
dp[0] = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (dp[i-1] < 0) {
dp[i] = nums[i];
}else {
dp[i] = dp[i-1] + nums[i];
}
}
int lnmax = dp[0];
for (auto x : dp) {
if (x > lnmax) {
lnmax = x;
}
}
return lnmax;
}
};
14. 合并区间
很简单的贪心问题 需要注意的是
- 我们如果要降序排序 第一个元素要小于第二个元素
- 合并区间的时候要注意右边界
bool compare(vector<int>& v1 , vector<int>& v2) {
if (v1[0] != v2[0]) {
return v1[0] < v2[0];
}else {
return v1[0] < v2[0];
}
}
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() == 1) {
return intervals;
}
vector<vector<int>> ans;
sort(intervals.begin() , intervals.end() , compare);
ans.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] <= ans.back()[1]) {
int R = max(intervals[i][1] , ans.back()[1]);
ans.back()[1] = R;
}else {
ans.push_back(intervals[i]);
}
}
return ans;
}
};
15. 翻转数组
很简单的一个脑筋急转弯 需要注意 beigin() 到 end() 是左闭右开
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n; // 确保k小于数组的大小
reverse(nums.begin(), nums.end()); // 翻转整个数组
reverse(nums.begin(), nums.begin() + k); // 翻转前k个元素
reverse(nums.begin() + k, nums.end()); // 翻转剩余元素
}
};
16. 除数字自身以外的乘积
这道题属于是知道了前后缀积就简单 前后缀积相乘就能得到答案
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
// 前缀 后缀积
vector<int> vPre(nums.size(), 1);
vector<int> vSub(nums.size(), 1);
vector<int> ans(nums.size() , 0);
for (int i = 1; i < nums.size(); i++) {
vPre[i] = vPre[i-1] * nums[i-1];
}
for (int i = nums.size() - 2 ; i >= 0 ; i--) {
vSub[i] = vSub[i+1] * nums[i + 1];
}
for (int i = 0; i < nums.size() ;i++) {
int lnans = vPre[i] * vSub[i];
ans[i] = lnans;
}
return ans;
}
};
17. 缺失的第一个正数
如果能用哈希表就用哈希表
不能的话就在原数组上交换
需要注意三点
- 交换的条件
- 避免重复 进入死循环
- 最后ans = I + 1；
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < nums.size(); i++) {
while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
swap(nums[i] , nums[nums[i] - 1]);
}
}
int ans = n + 1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != i + 1) {
ans = i + 1;
break;
}
}
return ans;
}
};
矩阵
18. 矩阵置零
使用第一行第一列来进行标记
在更新的时候要从第一行 第一列开始 避免破坏我们之前记录的值
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
// 行列记录 行标列标
int m = matrix.size();
int n = matrix[0].size();
bool cow = false;
bool rol = false;
for (int i = 0 ; i < m ; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
if (i == 0) {
cow = true;
}
if (j == 0) {
rol = true;
}
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1 ; j < n; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
for (int i = 0; i < m; i++) {
if (rol) {
matrix[i][0] = 0;
}
}
for (int j = 0; j < n; j++) {
if (cow) {
matrix[0][j] = 0;
}
}
}
};
19. 螺旋矩阵
只需要设置四个变量 然后四个方向依次遍历即可
#include <vector>
using namespace std;
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
int m = matrix.size(); // 行数
int n = matrix[0].size(); // 列数
int left = 0, right = n - 1, top = 0, bottom = m - 1;
while (left <= right && top <= bottom) {
// 从左到右
for (int i = left; i <= right; i++) {
ans.push_back(matrix[top][i]);
}
top++;
// 从上到下
for (int i = top; i <= bottom; i++) {
ans.push_back(matrix[i][right]);
}
right--;
// 从右到左
if (top <= bottom) {
for (int i = right; i >= left; i--) {
ans.push_back(matrix[bottom][i]);
}
}
bottom--;
//从下到上
if (left <= right) {
for (int i = bottom; i >= top; i--) {
ans.push_back(matrix[i][left]);
}
}
left++;
}
return ans;
}
};
20 旋转图像90度
记住公式 先上下翻转 再对角线翻转
上下翻转的时候注意 小于 N/2
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size() ;
// 上下翻转
for (int i = 0; i < n / 2; i++) {
swap(matrix[i] , matrix[n - i - 1]);
}
// 对角线反转
for (int i = 0; i < matrix.size(); i++) {
for (int j = i; j < matrix[0].size(); j++) {
swap(matrix[i][j] , matrix[j][i]);
}
}
}
};