LeetCode hot100---数组及矩阵专题(C++语言)
1、最大子数组和
（1）题目描述以及输入输出
(1)题目描述:
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
(2)输入输出描述：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6
关键思路：
使用局部最优解，从第一个元素开始遍历数组，前一元素大于0，就与当前元素相加。
获取完最优解后，更新最大和
（2）代码块
class Solution {
public:
int maxSubArray(vector<int>& nums)
{
int result= nums[0];
for(int i = 1;i<nums.size();++i)
{
if(nums[i-1] >0)nums[i] += nums[i-1]; // 局部最优
if(nums[i] > result)result = nums[i];// 更新最优结果
}
return result;
}
};
2、合并区间
（1）题目描述以及输入输出
(1)题目描述:
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
(2)输入输出描述：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
关键思路：
区间按照起始位置进行排序，初始化区间起始与终点值。
从第二个区间进行遍历，比较上个区间终点与本区间起始值关系。更新区间起始与终点
遍历结束要手动将最后一个区间起始与终点加进结果
（2）代码块
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals)
{
vector<vector<int>> result;
int start,end;
start = intervals[0][0];
end = intervals[0][1];// 初始化区间
for(int i = 1;i<intervals.size();++i)
{
if(end < intervals[i][0])// 比较本区间end与上一区间开始值的关系
{
result.push_back({start,end});
start = intervals[i][0];
end = intervals[i][1];
}
else
{
end = max(end,intervals[i][1]);
}
}
result.push_back({start,end});// 手动将最后区间起始值与终点值加入结果
return result;
}
};
3、轮转数组
（1）题目描述以及输入输出
(1)题目描述:
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
(2)输入输出描述：
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
关键思路：
使用三次reverse,先翻转整个数组，再翻转前k个元素，最后翻转剩余元素。
（2）代码块
class Solution {
public:
void rotate(vector<int>& nums, int k)
{
k %= nums.size();
reverse(nums.begin(),nums.end());
reverse(nums.begin(),nums.begin()+k);
reverse(nums.begin()+k,nums.end());
}
};
4、除自身以外数组的乘积
（1）题目描述以及输入输出
(1)题目描述:
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
(2)输入输出描述：
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
关键思路：
初始化前缀积以及后缀积为1。从第二个元素计算前缀积，从倒数第二个元素计算后缀积。
计算完将前缀积与后缀积相乘即可
（2）代码块
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums)
{
vector<int> result(nums.size(),1);
int left,right;
left = 1;
right = 1;
for(int i = 1;i<nums.size();++i)
{
left *= nums[i-1]; // 当前元素前缀积
result[i] = left;// 先保留前缀积
}
for(int i = nums.size()-2;i>=0;--i)
{
right *= nums[i+1]; // 当前元素后缀积
result[i]*=right;// 除此元素的乘积
}
return result;
}
};
5、矩阵置0
（1）题目描述以及输入输出
(1)题目描述:
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。
(2)输入输出描述：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
关键思路：
遍历矩阵，找到为0元素位置，将元素的行首元素、列首元素置为0。，如果是第一行或者第一列作标记单独处理。
从矩阵第二行、第二列遍历数组，若行/列首元素为0，则将该行、列全变为0
处理第一行或第一列的0。
（2）代码块
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix)
{
int colmark = false;
int rowmark = false;
for(int i = 0;i<matrix.size();++i)
{
for(int j = 0;j<matrix[0].size();++j)
{
if(matrix[i][j] == 0)
{
matrix[i][0] = 0;
matrix[0][j] = 0; // 将‘0’所在的行/列首元素置为0
if(i == 0)rowmark = true; // 单独处理第一行
if(j==0)colmark = true; // 单独处理第一列
}
}
}
for(int i = 1;i<matrix.size();++i)
{
for(int j = 1;j<matrix[0].size();++j)
{
if((matrix[i][0] == 0) || (matrix[0][j] == 0))
{
matrix[i][j] = 0;
}
}
}
for(int j=0;rowmark && j<matrix.size();++j)matrix[0][j] = 0; // 单独处理第一行
for(int i=0;colmark && i<matrix.size();++i)matrix[i][0] = 0; // 单独处理第一列
}
};
6、螺旋矩阵
（1）题目描述以及输入输出
(1)题目描述:
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
(2)输入输出描述：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
关键思路：
设置up down left right四个自变量，顺时针遍历，
上，up++;右，right--;下，down--;左，left++。
（2）代码块
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix)
{
vector<int> result;
int up = 0,down = matrix.size()-1,left = 0,right = matrix[0].size()-1;
while(1)
{
for(int i = left;i<=right;i++)result.push_back(matrix[up][i]);
if(++up>down)break;
for(int i = up;i<=down;i++)result.push_back(matrix[i][right]);
if(--right<left)break;
for(int i = right;i>=left;i--)result.push_back(matrix[down][i]);
if(--down < up)break;
for(int i = down;i>=up;i--)result.push_back(matrix[i][left]);
if(++left>right)break;
}
return result;
}
};
7、旋转图像
（1）题目描述以及输入输出
(1)题目描述:
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
(2)输入输出描述：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
关键思路：
现将矩阵进行转置，再进行水平翻转。
（2）代码块
class Solution {
public:
void rotate(vector<vector<int>>& matrix)
{
for(int i = 0;i<matrix.size();i++)
{
for(int j = 0;j<i;j++)
{
swap(matrix[i][j],matrix[j][i]);// 转置
}
}
for(int i = 0;i<matrix.size();i++)
{
for(int j = 0;j<matrix.size()/2;j++)
{
swap(matrix[i][j],matrix[i][matrix.size()-j-1]);// 水平翻转
}
}
}
};
8、搜索二维矩阵||
（1）题目描述以及输入输出
(1)题目描述:
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
(2)输入输出描述：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
关键思路：
遍历每行，对于每行的数组，采用二分查找的方式
（2）代码块
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
if(matrix.empty())return false;
for(int i = 0;i<matrix.size();i++)
{
int left = 0,right = matrix[0].size()-1;
if(target>=matrix[i][0] && target<=matrix[i][matrix[0].size()-1])
{
while(left<=right)
{
int mid = (left+right)/2;
if(target>matrix[i][mid])left = mid+1;
else if(target<matrix[i][mid])right = mid-1;
else return true;
}
}
else if(target < matrix[i][0])
break;
}
return false;
}
};
原文地址：https://blog.csdn.net/qq_54017644/article/details/142696159
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！