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

            result = max(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) 
    {
        sort(intervals.begin(),intervals.end());
        int start = intervals[0][0];
        int end = intervals[0][1];

        vector<vector<int>> result;
        for(int i = 1;i<intervals.size();++i)
        {
            if(end<intervals[i][0])
            {
                result.push_back(vector<int>{start,end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
            else
                end = max(end,intervals[i][1]);
        }
        result.push_back(vector<int>{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) 
    {
        if(k>nums.size())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;
    }
};

9、搜索插入位置

（1）题目描述以及输入输出

(1)题目描述:
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

(2)输入输出描述：
输入: nums = [1,3,5,6], target = 5
输出: 2

关键思路：
二分查找，找到返回mid,找不到返回left

（2）代码块

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int left = 0;
        int right = nums.size()-1;

        int mid;
        while(left<=right)
        {
            mid = (left+right)/2;
            if(nums[mid]<target)
                left = mid+1;
            else if(nums[mid]>target)
                right = mid-1; 
            else
                return mid;  
        }
        return right+1;
    }
};

10、搜索二维矩阵

（1）题目描述以及输入输出

(1)题目描述:
给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

(2)输入输出描述：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

关键思路：
二分查找，遍历每行，每行使用二分查找

（2）代码块

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) 
    {
        int m = matrix.size();
        int n = matrix[0].size();
        int left,right,mid;
        for(int i = 0;i<m;++i)
        {
            left = 0;
            right = n-1;
            if(matrix[i][0] > target)
                return false;
            while(left<=right)
            {
                mid = (left+right)/2;
                if(matrix[i][mid] > target)right = mid-1;
                else if(matrix[i][mid] < target)left = mid+1;
                else return true;
            }
        }
        return false;
    }
};

11、在排序数组中查找元素的第一个和最后一个位置

（1）题目描述以及输入输出

(1)题目描述:
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

(2)输入输出描述：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

关键思路：
逐个遍历

（2）代码块

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        int end = -1;
        int start = -1;
        bool start_flag = true;
        for(int i = 0;i<nums.size();++i)
        {
            if(nums[i] == target && start_flag)
            {
                start = i;
                start_flag = false;
            }
            else if(nums[i] == target && !start_flag)
            {
                end =  i;
            }
        }
        return {start,end};
    }
};