1. 知识点总结

题目	难度	知识点
全排列	🐸（STL）/🐸🐸（搜索）	全排列(还是要回炉不用STL)
旋转图像	🐸	找规律(数学,极坐标运算)
字母异位词分组	🐸	STL(map)
最大子数组和	🐸	分治(或者其他)分治忘记了属实该打

2. 分题题解

2.1 全排列

用了next_permutation(),emm，肯定要回炉的，这个虽然用起来简单，但是万一被禁用了有得好受的

执行用时：4 ms, 在所有 C++ 提交中击败了60.69%的用户

内存消耗：7.4 MB, 在所有 C++ 提交中击败了81.84%的用户

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>>ans;
        do{
            ans.push_back(nums);
        }while(next_permutation(nums.begin(),nums.end()));
        return ans;
    }
};

2.2 旋转图像

【坐标旋转-数学】

完全不记得公式了，┭┮﹏┭┮愧对高中老师……

推出旋转九十度：（row,col）-> (col,n-1-row)

执行用时：4 ms, 在所有 C++ 提交中击败了47.02%的用户

内存消耗：6.7 MB, 在所有 C++ 提交中击败了96.00%的用户

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //难点：原地旋转:n-1,n-2,……1
        int n=matrix.size();
        for(int row=0;row<n/2;row++){
            for(int col=row;col<n-row-1;col++){
               // cout<<"row:"<<row<<" "<<"col:"<<col<<endl;
                //对于(row,col)进行矩阵内部的旋转(row,col)->(col,n-1-row)
                //(row,col)->(col,n-1-row)->(n-1-row,n-1-col)->(n-1-col,row)->(row,col)
                int temp1=matrix[row][col];
                int temp2=matrix[col][n-1-row];
                int temp3=matrix[n-1-row][n-1-col];
                int temp4=matrix[n-1-col][row];
               // cout<<temp1<<" "<<temp2<<" "<<temp3<<" "<<temp4<<endl;
                matrix[row][col]=temp4;
                matrix[col][n-1-row]=temp1;
                matrix[n-1-row][n-1-col]=temp2;
                matrix[n-1-col][row]=temp3;
            }

        }
    }
};

2.3 字母异位词分组

本来以为需要对原始序列进行去重,结果发现多此一举了,盘复了一下unique的用法,虽然但是我觉得原题描述的不准确,应该要去重才对叭

执行用时：32 ms, 在所有 C++ 提交中击败了58.05%的用户

内存消耗：19.4 MB, 在所有 C++ 提交中击败了38.94%的用户

class Solution {
public:
    
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        
        vector<vector<string>>ans;
       
        //然后按照字母组合排序
        map<string,vector<string>>mp;
        for(int i=0;i<strs.size();i++){
            string temp=strs[i];
            sort(strs[i].begin(),strs[i].end());
            mp[strs[i]].push_back(temp);
        }
        //转存答案
        for(map<string,vector<string> >::iterator it=mp.begin();it!=mp.end();it++){
            ans.push_back(it->second);
        }
        return ans;
    }
};

2.4 最大子数组和

经典的简单题,一种是遍历思想的O(n)解法,一种是分治

惭愧的是分治完全思路(昂,向算法老师默默鞠躬😅)

执行用时：92 ms, 在所有 C++ 提交中击败了56.99%的用户

内存消耗：66.1 MB, 在所有 C++ 提交中击败了77.36%的用户

class Solution {
public:
 //分治法
   
    int maxSubArray(vector<int>& nums) {
        int len=nums.size();
        int max_ans=-INT_MAX;
        int temp_sum=0;
        bool flag=false;
        int max_single=-INT_MAX;
        for(int i=0;i<len;i++){
            max_single=max(max_single,nums[i]);
            if(temp_sum+nums[i]<0){
                temp_sum=0;
            }else{
                temp_sum+=nums[i];
                 if(temp_sum>max_ans){
                    max_ans=temp_sum;
                    flag=true;
                }
            }
        }
        if(!flag){
            max_ans=max_single;
        }
        return max_ans;
    }
};

补充一下官方给的分治的思路(其实不是最优解):

执行用时：116 ms, 在所有 C++ 提交中击败了11.32%的用户

内存消耗：66.1 MB, 在所有 C++ 提交中击败了55.73%的用户

class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) {
            return (Status) {a[l], a[l], a[l], a[l]};
        }
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};