leetcode-hot-100

128. 最长连续序列（C++使用set实现）

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //使用set集合实现
        unordered_set<int> s;
        
        for(int i = 0;i < nums.size();i++){
            s.insert(nums[i]);
        }

        int result = 0;

        for(int i = 0;i < nums.size();i++){
            if(!s.count(nums[i] - 1)){//表示s中没有前一个元素
                int curr = nums[i];
                int tmp = 0;
                while(s.count(curr)){
                    tmp += 1;
                    curr += 1;
                }
                result = max(result, tmp);
            }
        }

        return result;

    }
};

283. 移动零（C++使用快慢指针实现）

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //使用快慢指针
        int left = 0;
        int right = 0;

        while(right < nums.size()){
            if(nums[right] != 0){
                nums[left] = nums[right];
                left++;
            }
            right ++;
        }


        for(int i = left;i < nums.size();i++){
            nums[i] = 0;
        }

    }
};

11. 盛最多水的容器（C++贪心算法实现）

class Solution {
public:
    int maxArea(vector<int>& height) {
        //思路：使得长方形的宽度更大，高度更宽
        int result = INT32_MIN;

        //使用贪心算法
        int left = 0;
        int right = height.size() - 1;

        while(left <= right){
            int w = right - left;
            int h = min(height[right], height[left]);
            result = max(result, w * h);
            //尽可能地保留更高的不变
            if(height[left] < height[right]){
                left++;
            }else{
                right--;
            }
        }

        return result;

    }
};

15. 三数之和（C++去重实现）

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //思路：需要满足nums[i] + nums[j] + nums[k] == 0
        //那么，等价于：nums[i] + nums[j] = -nums[k]

        //首先排序
        sort(nums.begin(), nums.end());

        vector<vector<int>> result;

        for(int i = 0;i < nums.size();i++){

            //首先判断首个元素是否大于0，如果是，那么直接break
            if(nums[i] > 0){
                break;
            }

            //去重
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }

            //使用双指针
            //从i+1开始找
            int l = i + 1;
            int r = nums.size() - 1;

            while(l < r){
                //得到三数之和
                int tmp = nums[i] + nums[l] + nums[r];

                if(tmp == 0){
                    //去重，将右边相等的元素删除掉
                    while(l < r && nums[r] == nums[r - 1]){
                        r --;
                    }

                    //将左边相等的元素删除掉
                    while(l < r && nums[l] == nums[l + 1]){
                        l++;
                    }

                    //将结果放到result数组中
                    result.push_back({nums[i], nums[l], nums[r]});
                    //right --
                    r--;
                    //left ++
                    l++;
                }else if(tmp > 0){//应当r--，使得总和尽可能地减小
                    r--;
                }else{//当tmp < 0的时候，应当left++，使得总和尽可能地增大
                    l++;
                }
            }
        }

        return result;
    }
};

3. 无重复字符的最长子串（C++实现，使用set保存当前最长的记录）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //思路：使用set保存当前最长的子串

        if(s.size() == 0){
            return 0;
        }

        if(s.size() == 1){
            return 1;
        }

        unordered_set<char> mySet;

        //使用双指针实现
        int left = 0;
        int right = left;
        
        int tmp = 0;
        int result = 0;

        while(left <= right && right < s.size()){
            if(!mySet.count(s[right])){
                mySet.insert(s[right]);
                right++;
                result = max(result, right - left);
            }else{//找到了得到set的长度
                mySet.erase(s[left]);
                left++;
            }
        }

        return result;
    }
};

560. 和为 K 的子数组（C++使用前缀和实现）

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //思路：使用map记录nums中出现的sum的次数
        unordered_map<int, int> keep;

        int sum = 0;

        int result = 0;

        //初始化keep[0] = 1
        keep[0] = 1;

        for(int i = 0;i < nums.size();i++){
            sum += nums[i];
            result += keep[sum - k];
            keep[sum] ++;
        }

        return result;
    }
};

53. 最大子数组和（C++贪心算法实现）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;

        for(int i = 0;i < nums.size();i++){
            count += nums[i];
            
            if(result < count){
                result = count;
            }

            if(count <= 0){
                count = 0;//从i + 1开始
            }
        }
        return result;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;

        for(auto& it: nums){
            count += it;
            result = max(result, count);

            if(count < 0){
                count = 0;
            }
        }

        return result;
    }
};

56. 合并区间（C++使用贪心算法实现）

class Solution {
public:
    //cmp()函数用于按照区间的左边进行排序
    static bool cmp(const vector<int>& a, const vector<int>& b){
        return a[0] < b[0];//按照区间左边界升序排序
    }

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> result;

        //记录开始区间的左边界和有边界
        int left = intervals[0][0];
        int right = intervals[0][1];

        //将第一个区间放入到result中
        result.push_back(intervals[0]);

        //从index = 1开始遍历
        for(int i = 1;i < intervals.size();i++){
            //如果当前区间的左边界小于上一个区间的右边界
            if(intervals[i][0] <= right){
                //定义tmp数组
                vector<int> tmp;
                tmp.push_back(left);
                tmp.push_back(max(right, intervals[i][1]));
                //弹出上一个区间
                result.pop_back();
                //将当前区间添加到result中
                result.push_back(tmp);

                //更新right
                right = max(right, intervals[i][1]);
            }else{//表示当前区间与上一个区间没有交集，直接加入即可
                result.push_back(intervals[i]);
                //更新left和right
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }

        return result;
    }
};

189. 轮转数组（C++复制数组实现）

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        //思路：复制一份nums数组，然后在原地修改nums数组
        
        vector<int> tmpNums = nums;

        for(int i = 0;i < tmpNums.size();i++){
            //定义一个nums数组的新的index下标
            int index = (i + k) % tmpNums.size();
            nums[index] = tmpNums[i];
        }
    }
};

238. 除自身以外数组的乘积（C++先从左向右进行遍历，然后再从右向左进行遍历）

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        //思路：先从左向右进行遍历，累积left *= nums[i]
        //然后，再从右向左进行遍历，累积right *= nums[i]

        int left = 1;
        int right = 1;

        //初始化result为1
        vector<int> result(nums.size(), 1);
        //从左向右遍历
        for(int i = 0;i < nums.size();i++){
            result[i] *= left;
            left *= nums[i]; 
        }

        for(int j = nums.size() - 1;j >= 0;j--){
            result[j] *= right;
            right *= nums[j];
        }

        return result;
    }
};

41. 缺失的第一个正数（C++实现，先对nums数组进行排序，然后使用map去重，之后分多种情况进行判断）

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //思路：使用map来保存nums中的元素，用来去重
        //然后，使用map来进行判断
        //如果map的长度为1，且元素小于等于0，或大于1，那么直接返回1
        //如果map的长度不为1，那么判断map的最后一个元素是否小于等于0 或 大于1，是的话直接返回1

        //给nums数组进行排序
        sort(nums.begin(), nums.end());

        map<int, int> keep;
        
        for(int i = 0;i < nums.size();i++){
            keep[nums[i]] = 1;
        }

        //数值map的迭代器
        map<int,int> :: iterator iter;
        iter = keep.begin();

        if(keep.size() == 1){
            if(iter->first <= 0 || iter->first > 1){
                return 1;
            }else{
                return iter->first + 1;
            }
        }

        while(iter != keep.end()){
            if(iter->first <= 0){
                iter++;
            }else{
                break;
            }
        }

        if(iter->first != 1){
            return 1;
        }

        //如果等于keep.end()
        if(iter == keep.end()){
            return 1;//表示keep中全是负数，此时返回1
        }

        //否则判断是否为
        int shouldNum = iter->first + 1;
        iter++;

        while(iter != keep.end()){
            if(iter->first == shouldNum){
                shouldNum ++;
                iter++;
                continue;
            }else{
                return shouldNum;
            }
        }

        return nums[nums.size() - 1] + 1;
    }
};

73. 矩阵置零（C++使用标记数组实现）

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        
        int row = matrix.size();
        int col = matrix[0].size();

        //首先设置标记数组来记录哪些行和列需要设置为0
        vector<bool> row_zero(row, false);
        vector<bool> col_zero(col, false);

        //思路：遍历二维矩阵，然后对出现0元素的行和列进行循环设为0
        for(int i = 0;i < row; i++){
            for(int j  = 0;j < col;j++){
                if(matrix[i][j] == 0){
                    row_zero[i] = true;
                    col_zero[j] = true;
                }
            }
        }

        //将对应的行设置为0
        for(int i = 0;i < row_zero.size();i++){
            if(row_zero[i] == true){//需要设置为0
                for(int j = 0;j < col;j++){
                    matrix[i][j] = 0;
                }
            }
        }

        //将对应的列设置为0
        for(int j = 0;j < col_zero.size();j++){
            if(col_zero[j] == true){
                for(int i = 0;i < row;i++){
                    matrix[i][j] = 0;
                }
            }
        }
        
    }
};

54. 螺旋矩阵（C++大模拟实现）

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //思路：更改动态left/right/top/bottom
        int top = 0;
        int bottom = matrix.size() - 1;

        int left = 0;
        int right = matrix[0].size() - 1;

        vector<int> result;

        while(true){
            //首先从左向右遍历
            for(int j = left;j <= right;j++){
                result.push_back(matrix[top][j]);
            }

            //增加到下一行
            top++;

            if(top > bottom){
                break;
            }

            for(int i = top;i <= bottom;i++){
                result.push_back(matrix[i][right]);
            }

            //减少一列
            right --;

            if(right < left){
                break;
            }

            for(int j = right;j >= left;j--){
                result.push_back(matrix[bottom][j]);
            }

            //减少一行
            bottom--;


            if(bottom < top){
                break;
            }

            //遍历left对应的列
            for(int i = bottom;i >= top;i--){
                result.push_back(matrix[i][left]);
            }

            left ++;

            if(left > right){
                break;
            }
        }
        return result;
    }
};

48. 旋转图像（C++找规律实现）

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //思路：先复制一份matrix，然后找规律，原来的i,j位置的矩阵元素应当在新的矩阵的j,m-i-1处
        //其中，m为矩阵的行数
        int m = matrix.size();

        //复制一份矩阵
        auto matrix_new = matrix;

        for(int i = 0;i < m;i++){
            for(int j = 0;j < matrix[0].size();j++){
                matrix_new[j][m - i - 1] = matrix[i][j];
            }
        }

        matrix = matrix_new;
        
    }
};

240. 搜索二维矩阵 II（C++从左下角开始遍历）

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //思路：选择从左下角开始遍历是最方便快捷的
        int row = matrix.size() - 1;
        int col = 0;

        while(row >= 0 && col <= matrix[0].size() - 1){
            if(target < matrix[row][col]){
                row--;
            }else if(target > matrix[row][col]){
                col++;
            }else{
                return true;
            }
        }

        return false;

    }
};