力扣刷题记录10.22

k

2024/10/22

（1）回溯

1、全排列

方法一：建立数组记录是否已经在排列中。

通过递归 Lambda 表达式的方式定义了 dfs 函数。这种写法的重点是允许你在 Lambda 表达式中递归调用自己。

• 这里 dfs 是 Lambda 表达式的第一个参数，auto&& 是一种万能引用（Universal Reference）。这样做的目的是允许 Lambda 表达式递归调用自己。由于 Lambda 没有函数名，如果你想在内部递归调用自己，就需要显式传递自己给自己。
• 这个部分表示捕获列表。& 表示捕获外部作用域的所有变量（通过引用）。这允许 Lambda 表达式在函数内部访问并修改外部变量。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int> > res;
        vector<int> path(n),on_path(n);
        auto dfs=[&](auto&& dfs,int i){
            if(i==n){
                res.emplace_back(path);
                return;
            }
            for(int j=0;j<n;j++){
                if(!on_path[j]){
                    on_path[j]=1;
                    path[i]=nums[j];
                    dfs(dfs,i+1);
                    on_path[j]=0;
                }
            }
        };
        dfs(dfs,0);
        return res; 
    }
};

方法二：（看不大懂咧）

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

2、子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

⚠️错误示范：

• res没有初始化成有一个空子集，循环直接结束，over。
• 遍历的时候直接修改了res的长度，遍历会持续继续下去不会停止。

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    for(auto i:nums){
        for(auto j:res){
            j.push_back(i);
            res.push_back(j);
        }
    }
    return res;
}

🔸方法一：（正确版）

首先初始化成一个含有空子集的向量（注意题目空子集也是子集）。然后每次遍历nums数组，再遍历当前的res数组，将res数组中的向量添加进num中的元素后再添加进res中，这样就可以保证每个子集都被涵盖到。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res={{}};
        for(auto i:nums){
            int n=res.size();
            for(int j=0;j<n;j++){
                vector<int> tmp=res[j];
                tmp.push_back(i);
                res.push_back(tmp);
            }
        }
        return res;
    }
};

方法二、三时间复杂度更高，就不赘述了。

3、组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

🔸方法一：选或不选

从数组的第零个数开始遍历，有两种选择：

• 不选这个数，直接开始遍历下一个数。
• 选择这个数，dfs第二个参数表示还差多少凑够。减去这个数的大小后，继续从这个数遍历，表示可以继续选这个数。

遍历后需要”恢复现场“，也就是把这个数再弹走。

如果num==0表示这个序列可行；如果i已经等于数组长度或者num<0表示不用再继续遍历。

✅剪枝：将数组排序，如果在递归的时候发现num<当前元素，那么由于后面的数字会更大，就不需遍历了。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        range::sort(candidates);
        vector<vector<int>> res;
        vector<int> path;
        auto dfs=[&](auto&& dfs,int i,int num){
            if(num==0){
                res.push_back(path);
                return;
            }
            if(i==candidates.size()|| num<candidate[i]){
                return;
            }

            dfs(dfs,i+1,num);

            path.push_back(candidates[i]);
            dfs(dfs,i,num-candidates[i]);
            path.pop_back();
        };
        dfs(dfs,0,target);
        return res;
    }
};

4、括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

思路很简单：

如果括号数等于指定个数就不继续dfs；

右括号数小于左括号数的时候才能填右括号（括号需要合法）；

基于上条右括号数小于等于左括号，故而只需判断l<n的情况。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string ans;
        auto dfs=[&](auto&& dfs,int l,int r){
            if(l==n&&r==n){
                res.push_back(ans);
                return;
            }
            if(l<n){
                ans+='(';
                dfs(dfs,l+1,r);
                ans.pop_back();
            }
            if(r<l){
                ans+=')';
                dfs(dfs,l,r+1);
                ans.pop_back();
            }
        };
        dfs(dfs,0,0);
        return res;
    }
};

（2）二分法

1、 寻找旋转排序数组中的最小值

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n=nums.size();
        int l=0,r=n-1,mid;
        while(l<r){
            mid=l+(r-l)/2;
            if(nums[mid]>nums[r]){
                l=mid+1;
            }
            else if(nums[mid]<nums[r]){
                r=mid;
            }
        }
        return nums[mid];
    }
};