台州网站定制_江门市新会区_汽车营销策划方案ppt_熊猫关键词挖掘工具

子串

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]);}}}
};