算法学习——LeetCode力扣回溯篇3

在这里插入图片描述

491. 非递减子序列

491. 非递减子序列 - 力扣（LeetCode）

描述

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示

1 <= nums.length <= 15
-100 <= nums[i] <= 100

代码解析

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    
    void backtracking(vector<int>& nums , int indnx )
    {
    	//小于2的不加入结果，至少两个
        if(path.size()>=2) result.push_back(path);
        if(indnx >= nums.size()) return;
		//用set统计每一层相同值元素的使用
        unordered_set<int> uset;
        for(int i =indnx ; i<nums.size(); i++)
        {
        	//如果当前值小于上一个，或者这个值在该层用过了，跳过
            if(path.empty() == 0 && nums[i] < path.back() 
                || uset.find(nums[i]) != uset.end()) 
            continue;
            //将该使用过的存入set，标记使用过
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums,i+1 );
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};

46. 全排列

46. 全排列 - 力扣（LeetCode）

描述

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同

代码解析

回溯法

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int> &nums)
    {
        if(path.size() == nums.size())
        {
            result.push_back(path);
            return;
        } 
        for(int i = 0 ; i<nums.size() ; i++)
        {
           auto it = find(path.begin(),path.end(),nums[i]);
           //如果这个元素在这个树枝之前用过，就跳出
           if(it == path.end()) 
           {
               path.push_back(nums[i]);
           }else
           {
               continue;
           }
            backtracking(nums);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> permute(vector<int>& nums) {
        backtracking(nums);
        return result;
    }
};

回溯标记法

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    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] == true) continue; // path里已经收录的元素，直接跳过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

47. 全排列 II

47. 全排列 II - 力扣（LeetCode）

描述

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

示例

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示

1 <= nums.length <= 8
-10 <= nums[i] <= 10

代码解析

回溯标记法（不去重，时间复杂度高）

在插入之前做一个find查找，找不到相同的插入

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums , vector<bool>& used)
    {
        if(path.size() == nums.size())
        {
            if(find(result.begin() , result.end() , path) == result.end() ) result.push_back(path);
            return;
        }

        for(int i=0 ; i<nums.size() ;i++)
        {
            if(used[i] == 1) continue;

            used[i]=1;
            path.push_back(nums[i]);
            backtracking(nums,used);
            path.pop_back();
            used[i]=0;
        }
        return;
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        backtracking(nums,used);
        return result;
    }
};

回溯去重

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    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++) {
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) //去重
            {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

树层去重

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
{
    continue;
}

在这里插入图片描述

树枝去重

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true)
{
    continue;
}

在这里插入图片描述

332. 重新安排行程

332. 重新安排行程 - 力扣（LeetCode）

描述

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例

示例 1：
在这里插入图片描述

输入：tickets = [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]]
输出：[“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]

示例 2：

在这里插入图片描述

输入：tickets = [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]
输出：[“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]
解释：另一种有效的行程是 [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”] ，但是它字典排序更大更靠后。

提示

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi

代码解析

回溯遍历（超时）

回溯遍历每一种可能
当出现第一种可能的路线，之间加入。
当出现新的可能路线，与老路线对比，如果字典排序小于，则替换老路线

class Solution {
public:
    vector<string> resul;
    vector<string> path;
    void backtraking(vector<vector<string>>& tickets , string Indnx ,  vector<bool> &used)
    {
    	//找到路线，看是否替换老的路径
    	//如果没有老路径直接加入，如果相同就返回，如果不同路径按照字典比较
        if(path.size()==tickets.size()+1)
        {
            if(resul.empty()==1) 
            {
                resul = path;
                return;
            }
            else if(resul == path) return;
            else 
            {
                for(int j=0 ;j<path.size();j++)
                {
                    for(int k=0 ;k<3;k++)
                    {
                        if(resul[j][k] == path[j][k]) continue;
                        else if(resul[j][k] < path[j][k])return;
                        else if(resul[j][k] > path[j][k]) 
                        {
                            resul.clear();
                            resul = path;
                            return;
                        }
                    }
                }
            }
            // cout<<"resu: ";
            // for(auto i:resul) cout<<i<<' ';
            // cout<<endl;
            return;
        }

        for(int i=0 ; i<tickets.size();i++)
        {
        	//如果当前机票使用过，或者当前机票目的地不对，跳过
            if(used[i]==true || tickets[i][0] != Indnx) continue;
            //如果当前机票可用，则加入路径
            if(used[i]== false && tickets[i][0] == Indnx)
            {
                used[i] = true;
                path.push_back(tickets[i][1]);
                //递归，确定递归找的新机票。下一站机票的开始机场，就是当前机票的目的地机场
                backtraking(tickets,tickets[i][1],used);
                used[i] = false;
                path.pop_back();
            }
        }
        return;
        
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<bool> used(tickets.size(),false);
        path.push_back("JFK");
        backtraking(tickets,"JFK",used);
        return resul;
    }
};

排序再回溯

先对输入票排序，其中排序按照票的目的地的字典减少排序（因为出发点是确定的，目的地多种找最优解）
之后回溯遍历找路线，发现的第一个路线即为最优路线

class Solution {
public:
	//按飞机票目的地（字符串vector第二个参数）字典减小排序
     class compare
    {
    public:
        bool operator()( const vector<string> tickets1 ,const  vector<string> tickets2 )
        {
           
            if((tickets1[1])[0]  < (tickets2[1])[0]) return 1;
            else if((tickets1[1])[0]  == (tickets2[1])[0])
            {
                if((tickets1[1])[1]  < (tickets2[1])[1]) return 1;
                else if((tickets1[1])[1]  == (tickets2[1])[1])
                {
                    if((tickets1[1])[2]  < (tickets2[1])[2]) return 1;
                    else return 0;
                }
                 return 0;
            }
            return 0;
           
        }
    };
    vector<string> resul;
    vector<string> path;
    bool find = false;
    void backtraking(vector<vector<string>>& tickets , string Indnx ,  vector<bool> &used)
    {
    	//找到一个路径就不找了，直接是最优路径
        if(find == true ) return;
        if(path.size()==tickets.size()+1)
        {
                resul = path;
                find =true;
                return;
        }

        for(int i=0 ; i<tickets.size();i++)
        {
            if(used[i]==true || tickets[i][0] != Indnx) continue;
            if(used[i]== false && tickets[i][0] == Indnx)
            {
                used[i] = true;
                path.push_back(tickets[i][1]);
                backtraking(tickets,tickets[i][1],used);
                used[i] = false;
                path.pop_back();
            }
        }
        return;
        
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<bool> used(tickets.size(),false);
        sort(tickets.begin(),tickets.end(),compare());
        // for(auto i:tickets) 
        // {
        //      cout<<'[';
        //     for(auto j:i)
        //     {
        //          cout<<j<<' ';
        //     }
        //      cout<<']';
        // }
           
        path.push_back("JFK");
        backtraking(tickets,"JFK",used);
        return resul;
    }
};