当前位置: 首页 > news >正文

代码随想录算法训练营Day24|216.组合总和III、17.电话号码的字母组合

组合总和III

216. 组合总和 III - 力扣(LeetCode)

        思路和昨日的组合题类似,但注意对回溯算法中,收获时的条件需要写对,path的长度要为k的同时,path中元素总和要为n。

class Solution {
public:vector<int> path;vector<vector<int>> paths;int sum = 0; // 维护当前路径的和void backtracking(int k, int n, int startindex) {if (path.size() == k && sum == n) {paths.push_back(path);return;}for (int i = startindex; i <= 9; i++) {path.push_back(i);sum += i; // 更新路径和backtracking(k, n, i + 1);sum -= i; // 回溯时,恢复路径和path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 1);return paths;}
};

算法的时间复杂度,在最差的情况需,我们需要生成所有C(9,n)个组合,并且对于每个组合,都需要进行k层递归,因此时间复杂度为O(C(9,n)*n)。

空间复杂度考虑递归栈,递归栈的最大深度为n,每个组合需要n个元素的存储空间,隐形空间复杂度是O(n)。

电话号码的字母组合

17. 电话号码的字母组合 - 力扣(LeetCode)

首先,考虑使用一个哈希表来存储数值(这里用数值方便些,之后用 i - '0'可以将char转换为整形)与字符的映射关系。

具体参考代码随想录 (programmercarl.com)

回溯三步法

1.确定回溯函数参数,我们每次回溯返回的值都会存放在一个path字符串中,并存在一个paths数组存放所有的组合结果中,我们用全局变量表示,此外,我们还需要一个变量index来指示现在遍历的位置。

2.确认终止条件。当index与需要遍历的字符长度相同时,就将值存入path中,并返回。

3.单层遍历逻辑,我们需要知道在当前index下的umap存储的字符串大小,然后对这个字符串中的字符进行递归遍历。之后对下一个字符进行处理,因为本题是求不同集合间的组合。

整体代码

class Solution {
public:vector<string> paths; // 用于存储所有可能的字母组合string path; // 用于存储当前的字母组合unordered_map<int, vector<char>> umap; // 创建一个映射表,将数字映射到对应的字母Solution() {umap[2] = {'a', 'b', 'c'}; // 数字2对应的字母umap[3] = {'d', 'e', 'f'}; // 数字3对应的字母umap[4] = {'g', 'h', 'i'}; // 数字4对应的字母umap[5] = {'j', 'k', 'l'}; // 数字5对应的字母umap[6] = {'m', 'n', 'o'}; // 数字6对应的字母umap[7] = {'p', 'q', 'r', 's'}; // 数字7对应的字母umap[8] = {'t', 'u', 'v'}; // 数字8对应的字母umap[9] = {'w', 'x', 'y', 'z'}; // 数字9对应的字母}void backtracking(const string& digits, int index) {// 如果当前组合的长度等于输入数字的长度,将当前组合添加到结果中if (index == digits.size()) {paths.push_back(path);return;}// 将当前处理的数字转换为对应的映射表中的字母int digit = digits[index] - '0'; // 遍历映射表中的字母,进行回溯for (int i = 0; i < umap[digit].size(); i++) {path.push_back(umap[digit][i]); // 添加字母到当前组合backtracking(digits, index + 1); // 处理下一个数字path.pop_back();}}vector<string> letterCombinations(string digits) {//输入为空,直接返回空的结果if (digits.empty()) {return paths;}backtracking(digits, 0);return paths;}
};

算法的时间复杂度参考在最坏情况下,每个数字对应最多4个字母,若输入数字的长度为n,则最坏情况下时间复杂度为O(4^n),因为每一步都有4种选择。代码随想录上是将3个字母和4个字母都区分了出来所以是O(3^m*4^n)

空间复杂度由两部分组成,一是递归的栈空间,二是存储结果的空间,栈空间最坏情况下与输入数字长度n成正比O(n)。存储空间取决于可能的组合数量,最坏情况下为O(4^n),总的空间复杂度为O(m+4^n)。

http://www.lryc.cn/news/359730.html

相关文章:

  • 【Python系列】Python 中方法定义与方法调用详解
  • Java 基础面试300题 (201-230)
  • Go-知识并发控制Context
  • Vue + Nodejs + socket.io 实现聊天
  • cocos creator 3.x实现手机虚拟操作杆
  • 【数据分享】中国电力年鉴(2004-2022)
  • 两个数组的交集Ⅱ-力扣
  • 【TCP协议中104解析】wireshark抓取流量包工具,群殴协议解析基础
  • [个人笔记] 记录docker-compose使用和Harbor的部署过程
  • 详细介绍运算符重载函数,清晰明了
  • 国内外知名的低代码开发平台下载地址
  • 【Pr学习】01新建项目起步
  • 【Redis延迟队列】redis中的阻塞队列和延迟队列
  • el-tree常用操作
  • SQL 语言:存储过程和触发器
  • Ubuntu Linux 24.04 使用certbot生成ssl证书
  • Vivado 比特流编译时间获取以及FPGA电压温度获取(实用)
  • Window下VS2019编译WebRTC通关版
  • 【云原生 | 60】Docker中通过docker-compose部署kafka集群
  • allure测试报告用例数和 pytest执行用例数不相同问题
  • Ubuntu 离线安装 gcc、g++、make 等依赖包
  • Vxe UI vxe-upload 上传组件,显示进度条的方法
  • 探索API接口:技术深度解析与应用实践
  • ARM-V9 RME(Realm Management Extension)系统架构之系统安全能力的系统隔离属性
  • 一个班有n个学生,需要把每个学生的简单材料(姓名和学号)输入计算机保存。然后可以通过输入某一学生的姓名查找其有关资料。
  • python的range() 函数
  • ClickHouse数据管理与同步的关键技术
  • 【一竞技DOTA2】东南亚Bleed战队官宣Emo正式加盟
  • 算法学习笔记(7.3)-贪心算法(最大切分乘问题)
  • 大型企业用什么文件加密软件,五款适合企业的文件加密软件