JLUVicent

47全排列II&46全排列&491递增子序列

 
  • 2023年 03月15日
  • 0 阅读

day29

491.递增子序列

题目链接：491. 递增子序列

解题思路：参考 视频

要去重横向的重复元素，因此用一个集合来保存已经用过的元素，然后进行去重，同一父节点下的同层上使用过的元素就不能再使用了

在本题中我的思路是用一个函数来判断是否为递增序列，其实可以在函数中就可以判断，nums[i]和path.back()的大小。直接计算即可。

491. 递增子序列1

class Solution {
public:

    // 判断是否为递增序列
    // bool isIncrease(vector<int>& path){
    //     if( path.size() <= 1) return false;
    //     for( int i = 1; i < path.size(); i++){
    //         if( path[i] < path[i-1]){
    //             return false;
    //         }
    //     }
    //     return true;
    // }

    //全局变量
    vector<int> path;
    vector<vector<int>> result;
    // // 返回值和参数
    // void backtracking(vector<int>& nums,int startIndex){

    //     if(isIncrease(path)) result.push_back(path);
    //     unordered_set<int> uset;        //对于每一层递归都会重新进行记录 注意这个集合是在每层递归之前
    //     for( int i = startIndex; i < nums.size(); i++){
    //         // 收集结果
    //         // 定义集合
            
    //         // if( i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
    //         if( uset.find(nums[i]) != uset.end()) continue;
    //         uset.insert(nums[i]);
    //         path.push_back(nums[i]);
    //         backtracking( nums, i+1);   //递归
    //         path.pop_back();    //回溯
    //     }  
    // }

    void backtracking( vector<int>& nums, int startIndex){
        if ( path.size() > 1){
            result.push_back(path);
        }
        unordered_set<int> uset;
        for( int i = startIndex; i < nums.size(); i++){
            // 去重
            if(( !path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()){ continue; }	//path.empty()是1，取非就是0

            uset.insert(nums[i]);   //添加用过的元素
            path.push_back(nums[i]);
            backtracking( nums, i+1);
            path.pop_back();
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking( nums,0);
        return result;
    }
};

46.全排列

题目链接：46. 全排列

解题思路：参考 视频

注意和之前组合的区别，首先组合需要startIndex为了去重，防止出现[1,2],[2,1]这种情况，而在组合中只需要使用一个used数组来标记使用过的数组而不需要去重

注意：树的横向遍历就是for循环，纵向遍历就是递归，注意两者的区别，其他的根据递归/回溯三部曲就能解决

46.全排列

image-20230315202641242

class Solution {
public:

    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums, vector<bool> used){
        // 终止条件
        if( path.size() == nums.size()){
            result.push_back(path);
            return;
        }

        // 单层逻辑
        for( int i = 0; i < nums.size(); i++){
            // 判断是否使用过
            if( used[i] ) continue;
            path.push_back(nums[i]);
            used[i] = true;     //用过的元素赋1
            backtracking( nums,used);
            path.pop_back();
            used[i] = false;    //回溯
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {

        vector<bool> used(nums.size(),false);
        backtracking( nums,used);
        return result;

    }
};

47.全排列II

题目链接：47. 全排列 II

解题思路：参考 视频

去重之前一定要对元素先进行排序，进而才能通过相邻节点判断是否重复使用了

// 两种去重逻辑都是可以的
// 第一种：树枝去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}

47.全排列II3

// 第二种 数层去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

47.全排列II2

两种情况都是可以的，但是树层去重的效率更高，不用重复去重

47.全排列II1

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums, vector<bool> used){
        // 确定终止条件
        if( path.size() == nums.size()){
            result.push_back( path );
            return;
        }
        for ( int i = 0; i < nums.size(); i++){
            if(( i > 0 && nums[i] == nums[i-1] && used[i-1]) || used[i]) continue;   //去重
            // if( used[i] ) continue;
            path.push_back(nums[i]);
            used[i] = true;
            backtracking( nums,used );
            path.pop_back();    //回溯
            used[i] = false;//回溯
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());  //需要先对数组进行排序
        vector<bool> used(nums.size(),false);
        backtracking( nums,used);
        return result;

    }
};
搜索