算法康复训练12

1. 知识点总结

题目	难度	知识点
颜色分类	🐸	非要说起来的话，官方题解需要回炉
子集	🐸	DP

2. 分题题解

2.1 颜色分类

控制住自己想用sort的原始冲动，

冒泡排序：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len=nums.size();
        int low=0;
        int high=len-1;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(nums[i]>nums[j]){
                    swap(nums[i],nums[j]);
                }
            }
        }
    }
};

当然另一种方法，统计0，1，2个数然后重写整个数组$O(n)$，这里不列了

还有就是官方题解，yyds!

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len=nums.size();
        int p0=0,p1=0;
        for(int i=0;i<len;i++){
            if(nums[i]==1){
                swap(nums[i],nums[p1]);
                p1++;
            }else if(nums[i]==0){
                swap(nums[i],nums[p0]);
                if(p0<p1){
                    swap(nums[i],nums[p1]);
                }
                p1++;
                p0++;
            }
        }
    }
};

2.2 子集

简单的DP，注意空集需要自己加~

每当我写一道middle我都感觉再自我麻痹啊哈哈，等考试周过了刷一下hard

class Solution {
public:
    vector<vector<int> >ans;
    vector<int>v;
    vector<int>temp;
    int len;
    void dfs(int id){
        temp.push_back(v[id]);
        ans.push_back(temp);
        for(int i=id+1;i<len;i++){
            dfs(i);
        }
        temp.pop_back();
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        v=nums;
        ans.push_back({});
        len=v.size();
        for(int i=0;i<len;i++){
            dfs(i);
        }
        return ans;
    }
};

3. 参考资料

无