合并两个有序数组
两个按非递减顺序排列的整数数组nums1和nums，另有两个整数m和n，分别表示nums1和nums2中的元素数组。
请合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
直接合并后排序
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i = 0; i < n; i++){
nums1[m + i] = nums2[i];
}
sort(nums1.begin(), nums1.end());
}
};
双指针
合并后排序没有利用数组nums1与nums已经被排序的性质。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int sorted[m+n];
int index = 0, i = 0, j = 0;
while(i < m && j < n){
if(nums1[i] <= nums2[j]){
sorted[index++] = nums1[i++];
}else{
sorted[index++] = nums2[j++];
}
}
while(i < m){
sorted[index++] = nums1[i++];
}
while(j < n){
sorted[index++] = nums2[j++];
}
for(i=0; i<m+n; i++){
nums1[i] = sorted[i];
}
}
};
逆向双指针
之所以要使用临时变量，是因为如果直接合并到nums1中，nums1中的元素可能在取出之前被覆盖。
如何直接避免覆盖nums1中的元素呢？
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int index = m + n -1, i = m-1, j = n-1;
while(i >= 0 && j >= 0){
if(nums1[i] >= nums2[j]){
nums1[index--] = nums1[i--];
}else{
nums1[index--] = nums2[j--];
}
}
while(i >= 0){
nums1[index--] = nums1[i--];
}
while(j >= 0){
nums1[index--] = nums2[j--];
}
}
};
移除元素
给一个数组nums和一个值val，需要移除所有数值等于val的元素，并返回不同于val的元素的数量。
双指针
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0;
int right = 0;
int n = nums.size();
while(right < n){
if(nums[right] != val){
nums[left++] = nums[right];
}
right++;
}
return left;
}
};
双指针优化
如果要移除的元素在数组的开头，例如序列[1,2,3,4,5]，当val为1时，我们需要把每一个元素都左移一位。
注意元素顺序可以改变，那么直接将5移动到序列开头。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0;
int right = nums.size()-1;
while(left <= right){
if(nums[left] == val){
nums[left] = nums[right];
right--;
}else{
left++;
}
}
return left;
}
};
删除有序数组中的重复项
原地删除重复出现的元素，使每个元素只出现一次。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int left = 0;
int right = 1;
int n = nums.size();
while(right < n){
if(nums[left] != nums[right]){
left++;
nums[left] = nums[right];
}
right++;
}
return left+1;
}
};
三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
int n = triangle[0].size();
vector<vector<int>> dp(m);
for(int i=0; i<m ;i++){
dp[i] = vector<int>(i+1,0);
}
dp[0][0] = triangle[0][0];
for(int i=1; i<m; i++){
for(int j=0; j<=i; j++){
if(j == 0){
dp[i][j] = dp[i-1][j] + triangle[i][j];
}else if(j == i){
dp[i][j] = dp[i-1][j-1] + triangle[i][j];
}else{
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])+triangle[i][j];
}
}
}
return *std::min_element(dp[m-1].begin(), dp[m-1].end());
}
};
最大正方形
暴力法
使用dp[i][j]表示以（i,j）为右下角，且只包含1的正方形的边长最大值。如果我们能计算出所有dp[i][j]的值，那么其中的最大值即为矩阵中只包含1的正方形的边长的最大值，其平方就是最大正方形的面积。
对于每个位置(i,j)，检查在矩阵中该位置的值：
- 如果该位置的值是0，则dp[i][j]=0，因为当前位置不可能在由1组成的正方形中；
- 如果该位置的值是1，则dp[i][j]的值由其上方，左方和左上方决定。
此外，还需要考虑边界条件，如果i和j中至少有一个为0，则以此位置为右下角的最大正方形的边长只能是1，因此dp[i][j] = 1。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int maxSide = 0;
int rows = matrix.size(), columns = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(columns));
for(int i=0; i<rows; i++){
for(int j=0; j<columns; j++){
if(matrix[i][j] == '1'){
if(i == 0 || j == 0){
dp[i][j] = 1;
}else{
dp[i][j] = min(min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) + 1;
}
maxSide = max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
};
课程表
这学期必须学numCourses门课程，选修某些课程之前需要一些先修课程。
本题是一道经典的拓扑排序问题。
给定一个包含n个节点的有向图G，我们给出它的节点编号的一种排列，如果满足：
对于图G中的任意一条有向边(u,v)，u在排列中都出现在v的签名。那么称该排列是图G的拓扑排序。
深度优先搜索
我们可以将深度优先搜索的流程与拓扑排序的求解联系起来，用一个栈存储所有已经搜索完成的节点。
对于一个节点u，如果它的所有相邻节点都已经搜索完成，那么回溯到u的时候，u本身也会变成一个已经搜索完成的节点。
多数元素
给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于n/2的元素。
哈希表
使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。
我们用一个循环遍历数组nums，并将数组中的每个元素加入哈希映射中。
同样在遍历数组nums时候使用打擂台的方式，维护最大值，这样就省去了最后对哈希映射的遍历。
相同的树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == nullptr && q == nullptr){
return true;
}
if((p == nullptr && q != nullptr) || (p != nullptr && q == nullptr)){
return false;
}
bool leftCheck = isSameTree(p->left, q->left);
bool rightCheck = isSameTree(p->right, q->right);
return leftCheck && rightCheck && (p->val == q->val);
}
};
![[ICS] Modbus未授权攻击S7协议漏洞利用](https://img-blog.csdnimg.cn/img_convert/b56c60c312288a5c430d374d2db43b99.jpeg)
