递归算法学习——电话号码的字母组成,括号生成,组合

这篇具有很好参考价值的文章主要介绍了递归算法学习——电话号码的字母组成,括号生成,组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

递归算法学习——电话号码的字母组成,括号生成,组合,算法学习——递归,学习,学习笔记,c++,算法,深度优先

目录

一,电话号码的字母组合

1.题意

2.例子

3.题目接口

 4.解题代码和思路

代码:

思路:

二,括号的生成

1.题意

2.例子

3.题目接口

四,解题代码和思路

1.先写代码:

2.思路

三,组合

1.题意

2.例子

3.题目接口

4.解题代码


一,电话号码的字母组合

1.题意

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

递归算法学习——电话号码的字母组成,括号生成,组合,算法学习——递归,学习,学习笔记,c++,算法,深度优先

2.例子

递归算法学习——电话号码的字母组成,括号生成,组合,算法学习——递归,学习,学习笔记,c++,算法,深度优先

比如以上例子,2对应的字母组合是"abc",3对应的字母组合是"def"。所以,这里便有两组字母组合,这两组字母组合的互相的两两搭配便是我们要找的答案。

3.题目接口

class Solution {
public:
    vector<string> letterCombinations(string digits) {

    }
};

 4.解题代码和思路

代码:
class Solution {
    string arr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//字母映射
    vector<string>ret;//存结果的数组
    string path;//整合结果
     
public:
    vector<string> letterCombinations(string digits) {
       if(digits.size()==0)
       {
           return ret;
       }

       dfs(digits,0);
       return ret;
    }

    void dfs(string& digits,int pos)
    {
        if(path.size()==digits.size())//当path的长度和digits的长度相等的时候便可以加入到结果中
        {
            ret.push_back(path);
            return;
        }
        
        string ch = arr[digits[pos]-'0'];

        for(int i = 0;i<ch.size();i++)
        {
            path.push_back(ch[i]);
            dfs(digits,pos+1);//深度优先遍历,通过下标来控制遍历的起始位置
            path.pop_back();
        }

    }
};
思路:

要解决这道题,首先便要搞一个能够映射的数组arr。这个数组一共有十位,前两位是空的。后八位便以电话键的数字为下标,字母为内容一一映射:

 string arr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

然后便是两个全局变量的设计,全局变量的使用只是为了能够让函数传参更加方便罢了。

在这里最重要的还是dfs函数的设计。

1.首先是函数头:

因为两个全局变量的设计,让我们的dfs函数的传参变得比较简单,只需要传入两个参数,一个是digits,另一个是下标pos:

   void dfs(string& digits,int pos)

2.递归的结束条件:

递归的结束条件就是上面的例子中所说的那样,当整合结果的path的长度等于digits的长度时便可以将结果留到ret里。然后再返回到上一层。

if(path.size()==digits.size())
        {
            ret.push_back(path);
            return;
        }

3.函数体的设计

要想设计好函数体,首先便要知道这个函数应该如何运行才能得到我们想要的结果。以digits==“23”为例。2:abc,3:def。结果为:["ad","ae","af","bd","be","bf","cd","ce","cf"]

画出决策树:

递归算法学习——电话号码的字母组成,括号生成,组合,算法学习——递归,学习,学习笔记,c++,算法,深度优先

从这个树形结构可以看出,在每一层要处理的节点的个数就是每一个string的个数。比如“abc”有三个字母组成,在这里便要处理3个节点。下一层的“def”也是。所以,处理每一层便可以使用for循环。于是得到下面的代码:

string ch = arr[digits[pos]-'0'];//得到每一层的string

        for(int i = 0;i<ch.size();i++)//层遍历
        {
            path.push_back(ch[i]);
            dfs(digits,pos+1);//深度优先遍历,通过下标来控制下一层得到的是下一个string成员
            path.pop_back();
        }

层遍历加上深度优先遍历便构成这段代码的函数体。

二,括号的生成

1.题意

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

2.例子

递归算法学习——电话号码的字母组成,括号生成,组合,算法学习——递归,学习,学习笔记,c++,算法,深度优先

以n=3为例子,那这个函数便要找出三个左括号:"("与三个右括号:")"的所有搭配。如上图所示。

3.题目接口

class Solution {
public:
    vector<string> generateParenthesis(int n) {

    }
};

四,解题代码和思路

1.先写代码:
class Solution {
    vector<string>ret;//存放最后的结果
    string path;//记录每一个得到的结果
    int right = 0;//记录有右括号的个数
    int left = 0;//记录左括号的个数
public:
    vector<string> generateParenthesis(int n) {
       dfs(n);
       return ret;
    }

    void dfs(int& n)
    {
        if(path.size()==2*n)
        {
            ret.push_back(path);
            return;
        }

        if(left<n)
        {
            path.push_back('(');
            left++;
            dfs(n);
            path.pop_back();
            left--;
        }

        if(right<left)
        {
            path.push_back(')');
            right++;
            dfs(n);
            path.pop_back();
            right--;
        }
    }

};
2.思路

先来讲一讲这道题的关键问题:括号的有效性。先以n==3为例子,这个时候左括号和右括号在什么时候插入到path中才是合法的呢?这就要从左右括号的插入顺序和数量来讨论了。

1.首先得是顺序:第一个插入的括号必须为左括号。这个该如何控制呢?实现这个逻辑的代码如下:

 if(right<left)
        {
            path.push_back(')');
            right++;
            dfs(n);
            path.pop_back();
            right--;
        }

只有在右括号的数量小于左括号时才能插入右括号,这也就保证了path第一个插入的括号是(。

2.括号的数量,因为右括号的数量在递归的过程中是一直小于或者等于left的。所以控制了左括号的数量小于n便是控制了有括号的数量小于n。所以代码如下:

       if(left<n)//控制左括号数量
        {
            path.push_back('(');
            left++;
            dfs(n);
            path.pop_back();
            left--;
        }

当n==2时,决策树:

递归算法学习——电话号码的字母组成,括号生成,组合,算法学习——递归,学习,学习笔记,c++,算法,深度优先

三,组合

1.题意

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

2.例子

递归算法学习——电话号码的字母组成,括号生成,组合,算法学习——递归,学习,学习笔记,c++,算法,深度优先

这道题对我们的要求便是要求出在1~n之间按k个数的组合。并且一个组合和另一个组合的数字不同才能叫做不同的组合。顺序不同不能叫做组合。文章来源地址https://www.toymoban.com/news/detail-691238.html

3.题目接口

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {

    }
};

4.解题代码

class Solution {
public:
vector<vector<int>>ret;
vector<int>path;
    vector<vector<int>> combine(int n, int k) {
       dfs(n,k,1);
       return ret;
    }

    void dfs(int& n,int& k,const int& pos)//用引用要加const,不加就是权限的放大。
    {
        if(path.size()==k)
        {
            ret.push_back(path);
            return;
        }
       
       for(int i = pos;i<=n;i++)//用下标来控制剪枝
       {
           path.push_back(i);
           dfs(n,k,i+1);
           path.pop_back();
       }


    }
};

到了这里,关于递归算法学习——电话号码的字母组成,括号生成,组合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 稀碎从零算法笔记Day45-LeetCode:电话号码的字母组合

    题型:映射、回溯算法、递归 链接:17. 电话号码的字母组合 - 力扣(LeetCode) 来源:LeetCode 给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合。答案可以按  任意顺序  返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例

    2024年04月11日
    浏览(39)
  • 【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合

    📖题目描述 题目出处 :电话号码的字母组合 示例: 📖题解  这是一道典型的排列组合问题,根据输入,我们需要找到所有的组合。下面以输入字符串 digits = \\\"23\\\" 为例来讲解这道题目。 图解: 分析:  首先要知道输入的字符串 \\\"23\\\" 中的数字字符分别对应哪些字符串,其中

    2024年02月16日
    浏览(39)
  • 17. 电话号码的字母组合

    给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例 1: 示例 2: 示例 3: 提示: 0 = digits.length = 4 digits[i] 是范围 [\\\'2\\\', \\\'9\\\'] 的一个数字。 解答

    2024年02月15日
    浏览(42)
  • 17. 电话号码的字母组合(回溯)

    从第一个数字开始遍历其对应的字母,将其加入StringBuffer中,继续深度优先搜索,当访问到最后一个数字的时候,将StringBuffer存储到ans中,然后回溯到下一个对应字母。 拓展: StringBuffer中的删除对应字符的方法是 deleteCharAt()

    2024年01月15日
    浏览(43)
  • leetcode 17 电话号码字母组合

    给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例 1: 输入:digits = “23” 输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 示

    2024年01月18日
    浏览(38)
  • leetcode 17. 电话号码的字母组合

             该题也是经典回溯题。 与之前做的组合有两点不同: 之前的组合题是求同一集合的组合,而本题是求不同集合的组合。 本题还需要有一个将字符串数字转换为手机号9键对应字符集的过程。         下面上代码:         如果面试中的话要注意判断异常输入的情

    2024年02月16日
    浏览(41)
  • Leetcode 17 电话号码的字母组合

    理解题意 :         给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合                 本质上:数字代表着一个字母集合                 数字的个数决定了递归的深度,即树的深度                 数字代表的字母组合决定了当前树的宽度

    2024年02月05日
    浏览(40)
  • leetcode:电话号码的字母组合(详解)

    给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合。答案可以按  任意顺序  返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例 1: 示例 2: 示例 3: 提示: 0 = digits.length = 4 digits[i]  是范围  [\\\'2\\\', \\\'9\\\']  的一个数字。  

    2024年02月11日
    浏览(58)
  • 【leetcode C++】电话号码的字母组合

    给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。     . - 力扣(LeetCode) 这道题明显是需要互相匹配,如 字符串 “23”, 对应 “abc” 和 “def”。 这个

    2024年03月10日
    浏览(43)
  • 代码随想录阅读笔记-回溯【电话号码的字母组合】

    题目 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入:\\\"23\\\" 输出:[\\\"ad\\\", \\\"ae\\\", \\\"af\\\", \\\"bd\\\", \\\"be\\\", \\\"bf\\\", \\\"cd\\\", \\\"ce\\\", \\\"cf\\\"]. 说明:尽管上面的答案是按字典序排列的,但是你可以任意

    2024年04月13日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包