回溯算法

2021/7/11 20:05:55

本文主要是介绍回溯算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

回溯算法

伪代码1:

result;//用于存放结果集

backTracking()
{
    if(满足结束条件)
    {
        将结果添加到结果集中;
        return;
    }

    for(选择in选择列表)
    {
        修改;
        backTracking();//回溯
        回改;
    }
}

LeetCode46-全排列:给定一个不含重复数字的数组 nums ,返回其所有可能的全排列。

class Solution {
public:
    vector<vector<int>> result;

    vector<vector<int>> permute(vector<int>& nums) 
    {
        backtracking(0,nums);//回溯
        return result;
    }

    //回溯
    void backtracking(int k,vector<int>& nums)
    {
        //if(满足结束条件)
        if(k==nums.size()-1)
        {
            result.push_back(nums);
            return;
        }

        //for(选择in选择列表)
        for(int i=k;i<nums.size();++i)
        {
            swap(nums[i],nums[k]);//修改
            backtracking(k+1,nums);//回溯
            swap(nums[i],nums[k]);//回改
        }
    }
};

LeetCode51-N皇后:将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击(任何两个皇后都不能处于同一条横行、纵行或斜线上)。给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

class Solution {
public:
    vector<vector<string>> result;

    vector<vector<string>> solveNQueens(int n) 
    {
        if(n==0)
            return {};

        int row=0;//行数
        //矩阵result的某一行
        vector<string> board(n,string(n,'.'));
        //列colomn,左斜ldiag,右斜rdiag;记录是否存在皇后
        vector<bool> colomn(n,false),ldiag(2*n-1,false),rdiag(2*n-1,false);

        BackTracking(colomn,ldiag,rdiag,board,row,n);//回溯

        return result;
    }

    //回溯
    void BackTracking(vector<bool>& colomn,vector<bool>& ldiag,vector<bool>& rdiag,vector<string>& board,int row,int n)
    {
        //满足结束条件已经遍历完了所有的行
        if(row>=n)
        {
            result.push_back(board);
            return;
        }
   
        for(int j=0;j<n;++j)//逐行判断,并插入皇后
        {
            if(colomn[j]||ldiag[row+j]||rdiag[n-row+j-1])
                continue;

            board[row][j]='Q';
            colomn[j]=ldiag[row+j]=rdiag[n-row+j-1]=true;//修改

            BackTracking(colomn,ldiag,rdiag,board,row+1,n);//回溯
            
            board[row][j]='.';
            colomn[j]=ldiag[row+j]=rdiag[n-row+j-1]=false;//回改
        }    
    }
};

LeetCode71-组合:给定两个整数 n 和 k,返回 1 ... 中所有可能的 k 个数的组合。

class Solution {
public:
    vector<vector<int>> result;

    vector<vector<int>> combine(int n, int k) 
    {       
        vector<int> comb(k,0);
        int count=0;

        BackTracking(comb,count,n,k,1);//回溯

        return result;
    }

    void BackTracking(vector<int>& comb,int count,int n,int k,int pos)
    {
        //if(满足结束条件),已经选了k个数
        if(count==k)
        {
            result.push_back(comb);
            return;
        }

        //for(选择in选择列表)
        for(int i=pos;i<=n;++i)
        {
            comb[count++]=i;//修改
            BackTracking(comb,count,n,k,i+1);//回溯
            --count;//回改
        }
    }
};

 

伪代码2:

result;//用于存放结果集

backTracking()
{
    if(满足结束条件)
    {
        将结果添加到结果集中;
        return;
    }

    for(选择in选择列表)
    {
        if(满足条件)
        {
            修改;
            backTracking();//回溯
            回改;
        }
        else
        {
          break;
        } 
    }
}

LeetCode93-复原IP地址:给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 IP 地址 。

class Solution {
public:
    vector<string> result;

    vector<string> restoreIpAddresses(string s) 
    {
        backtracking(s, 0, 0);//回溯

        return result;
    }
    
    //回溯
    void backtracking(string& s, int startIndex, int pointNum)
    {
        //if(满足结束条件),点的数量已经够了
        if(pointNum == 3)
        {
            //判断剩下的字符串是否符合条件
            if(isValid(s, startIndex, s.size() - 1))
                result.push_back(s);

            return;
        }

        //for(选择in选择列表)
        for(int i = startIndex; i < s.size(); i++)
        {
            if(isValid(s, startIndex, i))//i不同表示从不同的位置进行分割
            {
                s.insert(s.begin() + i + 1, '.');
                pointNum++;//修改

                backtracking(s, i + 2, pointNum);//回溯

                pointNum--;
                s.erase(s.begin() + i + 1);//回改
            }
            else 
                break;
        }
    }
    
    //判断该段字符串是否有效
    bool isValid(const string& s, int start, int end)
    {
        //s[start...end]以0开头并且不是0(含前导项0)  或者  起止范围不符合条件
        if(s[start] == '0' && start != end||start > end)
            return false;

        int num = 0;
        for(int i = start; i <= end; i++)
        {
            if(s[i] > '9' || s[i] < '0')//含有其他字符
                return false;

            num = num * 10 + (s[i] - '0');//计算该段字符串表示的数字的大小
            if(num > 255)
                return false;
        }

        return true;
    }

};

LeetCode131-分割回文串:给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。

class Solution {
public:
    vector<vector<string>> result;

    vector<vector<string>> partition(string s) 
    {
        if (s.empty())
            return {};

        vector<string> ans;

        backTracking(s, ans, 0);

        return result;
    }

    void backTracking(const string& s,  vector<string>& ans, int pos)
    {
        //if(满足结束条件)
        if (pos >= s.length())
        {
            result.push_back(ans);
            return;
        }

        //for(选择in选择列表)
        for (int i = pos; i < s.length(); ++i)
        {
            string currStr = s.substr(pos, i-pos+1);

            if (IsPalindrome(currStr))//是回文串,则进行回溯
            {
                ans.push_back(currStr);//修改
                backTracking(s, ans, i+1);//回溯
                ans.pop_back();//回改
            }
        }
    }

    //判断当前字符是否是回文:双指针做法
    inline bool IsPalindrome(const string& currStr)
    {
        int l = 0;//左指针
        int r = currStr.size()-1;//右指针
        // 双指针,从字符串两边收缩去检查
        while(l < r)
        {
            if (currStr[l] != currStr[r]) return false;
            l++; r--;
        }
        return true;
    }
};

 



这篇关于回溯算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程