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’所在的行/列首元素置为0if(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;}
};