912.排序数组

给你一个整数数组 nums，请你将该数组升序排列。
你必须在不使用任何内置函数的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

解题思路

先来总结一下

十大排序算法~

排序算法	「平均」时间复杂度	「最坏」时间复杂度	「最好」时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定	数据量小、基本有序
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定	数据量小
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定	数据量小、基本有序
希尔排序	O(nlogn)	O(nlog^2n)	O(nlog^2n)	O(1)	不稳定	大数据
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定	链表排序
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn)	不稳定	处理大数据最常用
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定	优先队列
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定	数据范围较小、整数分布集中
桶排序	O(n+k)	O(n+k)	O(n^2)	O(n+k)	稳定	数据分布均匀
基数排序	O(n×k)	O(n×k)	O(n+k)	O(n+k)	稳定	非比较排序

其他总结

1️⃣按稳定性分类
在排序前后，相等元素的相对顺序是否保持不变，如果相对顺序不变，则该排序算法是稳定的，否则是不稳定的。

稳定排序：冒泡/插入/归并/基数
不稳定排序：选择/快速/堆

2️⃣排序算法优劣的衡量标准：
🔹 时间复杂度 排序速度（比较&移动次数）
🔹 空间复杂度 占内存辅助空间的大小
🔹 稳定性 A与B的关键字相等，排序后A、B的先后次序保持不变

3️⃣按排序类别分类

插入：插入/希尔
选择：选择/堆
交换：冒泡/快速
归并：归并
基数：基数

完整代码

1232.缀点成线

给定一个数组 coordinates ，其中 coordinates[i] = [x, y] ， [x, y] 表示横坐标为 x、纵坐标为 y 的点。请你来判断，这些点是否在该坐标系中属于同一条直线上。

2 <= coordinates.length <= 1000

coordinates[i].length == 2

-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4

coordinates 中不含重复的点

解题思路

我本来是想着soeasy，用y/x对比斜率就行了，然后发现部分样例通不过。定睛一看，发现直线不一定过原点…

那么就不使用斜率，而是使用斜率交叉乘法：如果所有点都在同一条直线上，那么对于任意两点P1(x1,y1)、P2(x2,y2)、P3(x3,y3)之间的斜率必须相等。也就是(y2-y1)/(x2-x1)=(y3-y1)/(x3-x1)。为避免除法带来的浮点误差，用交叉相乘验证更好。
并且注意！
因为我的验证方法需要三个点，但是这道题有可coordinates,length=2的情况，那就直接返回true，因为两点确定一条直线。

完整代码

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x1,y1,x2,y2;
        x1=coordinates[0][0];
        y1=coordinates[0][1];
        x2=coordinates[1][0];
        y2=coordinates[1][1];
        if(coordinates.size()==2){
            return true;
        }
        for(int i=2;i<coordinates.size();i++){
            int x3=coordinates[i][0];
            int y3=coordinates[i][1];
            if((y2-y1)*(x3-x1)!=(x2-x1)*(y3-y1)){
                return false;
            }
        }
        return true;
    }
};

2597.美丽子集的数目

给你一个由正整数组成的数组 nums 和一个正整数 k 。
如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个美丽子集。
返回数组 nums 中非空且美丽的子集数目。
nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

提示：

1 <= nums.length <= 18

1 <= nums[i], k <= 1000

解题思路

涉及子集相关问题，一般有两种方法：

回溯
位运算
本题选择回溯算法。因为该方法可在生成子集时剪枝。

假设 nums = [2, 4, 6]，我们希望生成所有子集,那么回溯的选择路径如下：

          dfs(0)
        /        \
    不选2        选2
     / \         /  \
  不选4  选4   不选4  选4
  ...

完整代码

class Solution {
public:
    int ans=0;
    void dfs(int index,vector<int>& nums,unordered_map<int,int>& freq,int k){
        if(index==nums.size()){
            ans++;
            return;
        }
        dfs(index+1,nums,freq,k);
        if(freq[nums[index]-k]==0 && freq[nums[index]+k]==0){
            freq[nums[index]]++;
            dfs(index+1,nums,freq,k);
            freq[nums[index]]--;
        }
    }
    int beautifulSubsets(vector<int>& nums, int k) {
        unordered_map<int,int> freq;
        dfs(0,nums,freq,k);
        return ans-1;
    }
};

2070.每一个查询的最大美丽值

又美丽了家人们🤣

给你一个二维整数数组 items ，其中 items[i] = [pricei, beautyi] 分别表示每一个物品的价格和美丽值。
同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值是多少。如果不存在符合条件的物品，那么查询的结果为 0 。
请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。

提示：
-1 <= items.length, queries.length <= 105
-items[i].length == 2
-1 <= pricei, beautyi, queries[j] <= 109

解题思路

二分查找

首先复习一下二分查找，我又忘了咋写。另一篇copy来的

要查找的目标target

索引index

左、右指示符left、right

中间指示符mid
主要思路就是计算mid的位置：
1️⃣nums[mid] == target 🤭找到了
2️⃣nums[mid] < target → target在left的右边 → left右移 👉️left=mid+1;
3️⃣nums[mid] > target → target在right的左边 → right左移 👉️right=mid-1;

//形参：vector<int>nums,int target
int left=0;
int right=nums.size()-1;
while(left<=right){
    int mid=left+(right-left)/2;
    if(nums[mid]=target){
        return mid;
    }
    else if(nums[mid]<target){
        left=mid+1;
    }
    else{
        right=mid-1;
    }
    return index;
}

本题思路

方法一

完球，力扣的急速判题卡死了😂第一个方法直观而且没用二分，美美超时。

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        vector<int> answer(queries.size(),0);
        for(int j=0;j<queries.size();j++){
            int target=queries[j];
            int maxnum=0;
            for(int i=0;i<items.size();i++){
                if(items[i][0]<=target){
                    maxnum=max(maxnum,items[i][1]);
                }
            }
            answer[j]=maxnum;
        }
        return answer;
    }
};

方法二

老老实实用二分。注意：二分查找的前提是有序。

先按照price递增排序;
定义美丽数组;
遍历items:存储当前遍历到的最大美丽值;
定义答案数组;
遍历querties：二分查找

二分查找目标🤟items[i][0] <= queries[j] 的最大 i
有点绕了，兄弟兄弟…

完整代码

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        sort(items.begin(),items.end());
        vector<int>maxbeauty(items.size());
        maxbeauty[0]=items[0][1];
        for(int i=1;i<items.size();i++){
            maxbeauty[i]=max(maxbeauty[i-1],items[i][1]);
        }
        vector<int>answer(queries.size(),0);
        for(int j=0;j<queries.size();j++){
            int target=queries[j];
            int left=0;
            int right=items.size()-1;
            int index=-1;
            while(left<=right){
                int mid=left+(right-left)/2;
                if(items[mid][0]<=target){
                    index=mid;
                    left=mid+1;
                }
                else{
                    right=mid-1;
                }
            }
            if(index!=-1){
                answer[j]=maxbeauty[index];
            }
        }
        return answer;
    }
};

2269.找到一个数字的 K 美丽值

给你一个下标从0开始的整数数组nums。对于每个下标i（1 <= i <= nums.length - 2），nums[i] 的美丽值等于：
2，对于所有 0 <= j < i 且 i < k <= nums.length - 1 ，满足 nums[j] < nums[i] < nums[k]
1，如果满足 nums[i - 1] < nums[i] < nums[i + 1] ，且不满足前面的条件
0，如果上述条件全部不满足
返回符合 1 <= i <= nums.length - 2 的所有 nums[i] 的美丽值的总和。

提示：

3 <= nums.length <= 105

1 <= nums[i] <= 105

解题思路

难点在于nums[i]的美丽值为2的情况：
突然想起来高中数学老师的口头禅：“大于大的，小于小的”。
nums[i]需要满足：比其左侧所有的nums[j]更大，以及比其右侧所有的nums[k]更小。
即大于左侧最大值，小于右侧最小值。

*max_element(arr.begin(),arr.end())求数组最大值
*min_element(arr.begin(),arr.end())求数组最小值

？超时了😇我还说想清楚了不难呢…

class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int maxval,minval,ans=0;
        for(int i=1;i<nums.size()-1;i++){
            maxval=*max_element(nums.begin(),nums.begin()+i);
            minval=*min_element(nums.begin()+i+1,nums.end());
            if(maxval<nums[i] && minval>nums[i]){
                ans+=2;
            }
            else if(nums[i-1]<nums[i] && nums[i+1]>nums[i]){
                ans+=1;
            }
        }
        return ans;
    }
};

改进方法就是：左侧最大值和右侧最小值各自都用一个数组存起来所有i的情况，再进行条件判断。同时可以存一个，另一个随每次判断进行更新就好。

定义左侧最大int数组leftMax;
遍历i从1到nums.size()：
    leftMax[i]=max(左侧最大数组[i-1],原数组[i-1]);
int 美丽值;
定义右侧最小int变量rightMin并初始化为原数组[length()-1];
遍历i从length()-2到0:
    如果（条件一）：
        美丽值+=2;
    否则如果（条件2）：
        美丽值+=1;
    更新右侧最小值=min（右侧最小值，原数组[i]）;
返回美丽值

完整代码

class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        vector<int> leftMax(nums.size(),0);
        for(int i=1;i<nums.size();i++){
            leftMax[i]=max(leftMax[i-1],nums[i-1]);
        }
        int ans=0;
        int rightMin=nums[nums.size()-1];
        for(int i=nums.size()-2;i>0;i--){
            if(leftMax[i]<nums[i] && nums[i]<rightMin){
                ans+=2;
            }
            else if(nums[i-1]<nums[i] && nums[i]<nums[i+1]){
                ans+=1;
            }
            rightMin=min(rightMin,nums[i]);
        }
        return ans;
    }
};

杨辉三角（一维数组版）

完整代码

void Print_TR(int n){
    int arr[n]={1};
    for(int i=0;i<n;i++){
        for(int j=i;j>0;j--){
            arr[j]+=arr[j-1];
        }
        //打印
        for(int j=0;j<=i;j++){
            printf("%d ",arr[j]);
        }
        printf("\n");
    }
}

2610.转换二维数组

给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：

二维数组应该只包含数组 nums 中的元素。

二维数组中的每一行都包含不同的整数。

二维数组的行数应尽可能少。
返回结果数组。如果存在多种答案，则返回其中任何一种。
请注意，二维数组的每一行上可以存在不同数量的元素。

1 <= nums.length <= 200

1 <= nums[i] <= nums.length

解题思路

用哈希表！😎统计元素出现次数，定义一个一维数组存每行元素。每用一个元素。哈希表中该元素次数–（当次数为0时）从表中删除该元素。

这里看题解涉及到stl迭代器it的用法：对于定义一个哈希表:unordered_map<int,int>cnt

当用auto:it遍历cnt.begin()到!=cnt.end()时
it->first即为哈希表键值对(key,value)中的key。本题中即为元素本身
it->second即为哈希表键值对(key,value)中的value。本题中即为元素的出现次数

完整代码

感谢灵神题解，教会我很多

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        unordered_map<int,int> cnt;
        vector<vector<int>> ans;
        for(int x:nums){
            cnt[x]++;
        }
        while(!cnt.empty()){
            vector<int>row;
            for(auto it=cnt.begin();it!=cnt.end();){
                row.push_back(it->first);
                if(--it->second==0){
                    it=cnt.erase(it);
                }
                else{
                    it++;
                }
            }
            ans.push_back(row);
        }
        return ans;
    }
};

2643.一最多的行

给你一个大小为 m x n 的二进制矩阵 mat ，请你找出包含最多 1 的行的下标（从 0 开始）以及这一行中 1 的数目。
如果有多行包含最多的 1 ，只需要选择行下标最小的那一行。
返回一个由行下标和该行中 1 的数量组成的数组。

提示：

m == mat.length

n == mat[i].length

1 <= m, n <= 100

mat[i][j] 为 0 或 1

解题思路

最轻松的一集😂但是我写的代码略史山，还有优化空间。

完整代码

这里直接用int ones = count(mat[i].begin(), mat[i].end(), 1); 统计1的个数可以减少一次遍历。

class Solution {
public:
    vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
        vector<int> cnt(100,0),ans;
        int index=0;
        for(int i=0;i<mat.size();i++){
            for(int j=0;j<mat[i].size();j++){
                if(mat[i][j]==1){
                    cnt[i]++;
                }
            }
        }
        int maxnum=cnt[0];
        for(int i=0;i<cnt.size();i++){
            if(cnt[i]>maxnum){
                maxnum=cnt[i];
                index=i;
            }
        }
        ans.push_back(index);
        ans.push_back(cnt[index]);
        return ans;
    }
};

661.图片平滑器

图像平滑器是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。
每个单元格的平均灰度定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。
如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。
给你一个表示图像灰度的m x n整数矩阵img，返回对图像的每个单元格平滑处理后的图像。

提示:

m == img.length

n == img[i].length

1 <= m, n <= 200

0 <= img[i][j] <= 255

解题思路

关键知道矩阵边界，也就是不全加9个数的情况怎么算。我一开始还想着一个个情况穷举😂其实3*3区域安心两层遍历就行，对于这道题不会超时。
***刷题以来第一次碰到四层循环能通过的。。。***不看题解都不敢想像这个方法。

完整代码

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int m,n;
        m=img.size();
        n=img[0].size();
        vector<vector<int>>ans(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int sum,cnt;
                sum=cnt=0;
                for(int r=i-1;r<=i+1;r++){
                    for(int c=j-1;c<=j+1;c++){
                        if(0<=r && r<m && 0<=c && c<n){
                            sum+=img[r][c];
                            cnt++;
                        }
                    }
                }
                ans[i][j]=cnt>0?sum/cnt:img[i][j];
            }
        }
        return ans;
    }
};

27171.对角线上不同值的数量差

给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。
矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算：
令 topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上不同值的数量。
令 bottomRight[r][c] 为矩阵 grid 中单元格 (r, c) 右下角对角线上不同值的数量。
然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| 。
返回矩阵 answer 。
矩阵对角线是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。
如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ，则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角线。类似地，可以定义右下对角线。

提示：

m == grid.length

n == grid[i].length

1 <= m, n, grid[i][j] <= 50

解题思路

几个地方思考的时候容易卡住：

1️⃣不同值是什么意思？
我一开始理解的是对于grid[i][j]，它的左对角线上和它不同的元素数量叫做topleft，右对角线上和它不同的元素数量叫做bottomright，然后就自以为大彻大悟☝️🤓~~美美去打代码然后寄了~~。

个人理解中，实际上这里的不同值的意思是：对于这半拉对角线上的所有元素而言的种类数量。

比如全是1，那就1种，topleft=1；
如果有1有0，那就是2种，topleft=2。
右对角线同理.

2️⃣如何统计“不同值”？
这里选用基于红黑树的std::set而不是之前我们常用的unordered_map。因为对于本题，只需要判断「是否不同」而不需要记录「不同的次数」。
对于setmyset 而言：

如果rfind.find(grid[r][c])==rfind.end()即为不同值
新的不同值用myset.insert()添加
myset.size()获得不同值的数量

完整代码

class Solution {
public:
    vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
        int m,n;
        m=grid.size();
        n=grid[0].size();
        vector<vector<int>> answer(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int lcnt,rcnt;
                lcnt=rcnt=0;
                set<int> lfind,rfind;
                //左对角线
                int r=i-1;
                int c=j-1;
                while(r>=0 && c>=0){
                    if(「」){
                        lcnt++;
                    }
                    lfind.insert(grid[r][c]);
                    r--;
                    c--;
                }
                //右对角线
                r=i+1;
                c=j+1;
                while(r<m && c<n){
                    if(rfind.find(grid[r][c])==rfind.end()){
                        rcnt++;
                    }
                    rfind.insert(grid[r][c]);
                    r++;
                    c++;
                }
                answer[i][j]=abs(lcnt-rcnt);
            }
        }
        return answer;
    }
};

3375.使数组的值全部为K的最少操作次数

给你一个整数数组 nums 和一个整数 k 。
如果一个数组中所有严格大于 h 的整数值都相等，那么我们称整数 h 是合法的。
比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个合法整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是合法整数。
你可以对 nums 执行以下操作：
选择一个整数 h ，它对于当前 nums 中的值是合法的。
对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。
你的目标是将 nums 中的所有元素都变为 k ，请你返回最少操作次数。如果无法将所有元素都变 k ，那么返回 -1 。

解题思路

呃(⊙﹏⊙)自认为语文水平还不错，但是这题目着实看不懂…

看了评论区&题解佬们的耐心讲解，我浅总结一下：

函数返回
返回将nums所有元素变为k的最少操作次数，变不了返回-1。
元素变k的前提
nums中>k的所有元素都相等，将这些元素全变为k。
无法满足返回-1是什么情况
如果nums中但凡有元素小于k，那么一定不中。
最少操作次数
~~关键来了~~数组中所有大于k的元素种类。对，就这样就行😅

完整代码

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int cnt=0;
        unordered_set<int>hashset;
        for(int num:nums){
            if(num<k){
                return -1;
            }
            else{
                if(hashset.find(num)==hashset.end() && num>k){
                    hashset.insert(num);
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

2563.统计公平数对的数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回公平数对的数目。
如果 (i, j) 数对满足以下情况，则认为它是一个公平数对：

0 <= i < j < n，且

lower <= nums[i] + nums[j] <= upper

提示：

1 <= nums.length <= 105

nums.length == n

-109 <= nums[i] <= 109

-109 <= lower <= upper <= 109

解题思路

PS：因为实习鸽了五个工作日的我想了想又苟回来日更辣！！！现在是2025年4月19！等做到1000题再停更，主打一个保持编码的思维和手感😼~~毕竟斥巨资开了力扣年卡不写一年也太亏了~~

完整代码

力扣算法

912.排序数组

解题思路

十大排序算法~

其他总结

完整代码

1232.缀点成线

解题思路

完整代码

2597.美丽子集的数目

解题思路

完整代码

2070.每一个查询的最大美丽值

解题思路

二分查找

本题思路

方法一

方法二

完整代码

2269.找到一个数字的 K 美丽值

解题思路

完整代码

杨辉三角（一维数组版）

完整代码

2610.转换二维数组

解题思路

完整代码

2643.一最多的行

解题思路

完整代码

661.图片平滑器

解题思路

完整代码

27171.对角线上不同值的数量差

解题思路

完整代码

3375.使数组的值全部为K的最少操作次数

解题思路

完整代码

2563.统计公平数对的数目

解题思路

完整代码

专题2️⃣ ⋮ 贪心算法

Leetcode ⋮ 字符串