算法训练营第二十八天 | LeetCode 77 组合(剪枝优化)、LeetCode 216 组合总和III、LeetCode 17 电话号码的字母组合

本文主要是介绍算法训练营第二十八天 | LeetCode 77 组合(剪枝优化)、LeetCode 216 组合总和III、LeetCode 17 电话号码的字母组合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode 77 组合(剪枝优化)

当我们到达某一层,后面的结点数已经不能满足条件时。可以进行剪枝操作。

代码如下:

class Solution {
private:vector<int> path;vector<vector<int>> res;void backtracking(int n, int index, int k) {if (path.size() == k) {res.push_back(path);return;}if (index == n + 1) return;for (int i = index; i <= n; i++) {if (n - i + 1 < k - path.size()) return;path.push_back(i);backtracking(n, i + 1, k);path.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {backtracking(n, 1, k);return res;}
};

主要在for循环中加了一个判断条件。

LeetCode 216 组合总和III

其实也很简单,回溯问题主要是要掌握递归模板,之后的过程就是在凑参数、返回条件和递归逻辑了。具体可以去看看代码随想录里面讲解,会很懂很多。有很多图片,比如下面这个

代码如下:

class Solution {
private:vector<int> path;vector<vector<int>> res;void backtracking(int k, int num, int index) {if (path.size() == k) {if (num == 0) {res.push_back(path);}return;}for (int i = index; i <= 9; i++) {if (9 - i + 1 < k - path.size()) return;path.push_back(i);backtracking(k, num - i, i + 1);path.pop_back();}}
public:vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 1);return res;}
};

LeetCode 17 电话号码的字母组合

这题本身其实不难,不过有点绕。要用一个字符串类型向量记录每个电话号码数字对应的几个字符组成的字符串,在回溯的时候对应查找,作为查找表使用。

转化时用到stoi和atoi,都报错,最后用字符串减法,直接每个字符-'0'解决了问题。查资料可以发现,两者都是适配于字符串类型而非单个字符的,差别在于一个是c语言函数,一个是C++下的string类里的函数。

代码如下:

class Solution {
private:string path;vector<string> res;void backtracking(string digits, int index, vector<string>& s) {if (path.size() == digits.size()) {res.push_back(path);return;}int i_index = digits[index] - '0';for (int i = 0; i < s[i_index].length(); i++) {string temp = path;path += s[i_index][i];backtracking(digits, index + 1, s);path = temp;}}
public:vector<string> letterCombinations(string digits) {if (digits.size() == 0) return res;vector<string> s(10, "");s[2] = "abc"; s[3] = "def"; s[4] = "ghi"; s[5] = "jkl"; s[6] = "mno";s[7] = "pqrs"; s[8] = "tuv"; s[9] = "wxyz";backtracking(digits, 0, s);return res;}
};

这篇关于算法训练营第二十八天 | LeetCode 77 组合(剪枝优化)、LeetCode 216 组合总和III、LeetCode 17 电话号码的字母组合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/989025

相关文章

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Deepseek使用指南与提问优化策略方式

《Deepseek使用指南与提问优化策略方式》本文介绍了DeepSeek语义搜索引擎的核心功能、集成方法及优化提问策略,通过自然语言处理和机器学习提供精准搜索结果,适用于智能客服、知识库检索等领域... 目录序言1. DeepSeek 概述2. DeepSeek 的集成与使用2.1 DeepSeek API

Tomcat高效部署与性能优化方式

《Tomcat高效部署与性能优化方式》本文介绍了如何高效部署Tomcat并进行性能优化,以确保Web应用的稳定运行和高效响应,高效部署包括环境准备、安装Tomcat、配置Tomcat、部署应用和启动T... 目录Tomcat高效部署与性能优化一、引言二、Tomcat高效部署三、Tomcat性能优化总结Tom

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》:本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧,

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏?常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏?2.1 使用 J