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

输入一个序列,返回所有可能的出栈序列

oh my god,我终于相信了墨菲定律

回溯法
从给定的字符串str中选取字符,并以不同的顺序压入栈中,然后依次从栈中弹出字符到临时字符串tem中,直到tem与str完全相同为止。每次当tem与str长度相同时(所有元素的一个排列),就将tem作为一个可能的序列添加到结果集res中。

1、结束条件:如果临时字符串tem的大小与给定字符串str的大小相同,说明已经成功生成了一个与str相同的序列,此时将这个序列添加到结果集res中,并返回。
2、栈非空时的操作:如果栈不为空,那么从栈顶取出一个字符添加到tem中,并递归调用stackSeq函数来继续处理剩余的情况。递归调用返回后,需要“撤销”这次操作,即把之前从栈顶取出的字符重新压回栈中,并从tem中移除这个字符,以便尝试其他可能的序列。
3、插入操作:如果索引index还没有遍历完str中的字符,那么就将str[index]压入栈中,并递增index,然后递归调用stackSeq函数。递归调用返回后,同样需要“撤销”这次操作,即弹出栈顶的字符,并递减index。

void stackSeq(stack<char> &st, string str, int &index, string &tem, vector<string> &res) {//定义结束条件if (tem.size() == str.size()){res.push_back(tem);return;}//只要栈不为空,就出栈if (st.size()>0){tem += st.top();st.pop();stackSeq(st,str,index,tem,res);st.push(tem.back());//撤回出栈操作tem.pop_back();//回溯}//只要有可以插入的元素,就选择插入if (index < str.size()) {st.push(str[index]);index++;stackSeq(st, str, index, tem, res);st.pop();index--;}
}

http://www.mrgr.cn/news/6488.html

相关文章:

  • ansible之playbook
  • 背包问题【算法 07】
  • 钓鱼的常见几种方式
  • Android Room DataBase
  • LP2801A/B/C/D/E 输出电压可调3.3V~24V,输出电流100mA~400mA
  • 一款好看的WordPress REST API 主题
  • 微知-PCIe配置空间中哪个字段表示设备类型?有哪三种类型?哪个字段表示厂商ID
  • oracle 事务回滚
  • 在Flux和Ideogram 2.0的竞争压力下,Midjourney每日开放25张免费额度
  • function call使用基础
  • 汇编语言:adc指令 和 sbb指令
  • 【前端基础篇】JavaScript基础介绍
  • 【知识图谱】2.知识抽取与知识存储
  • Java设计模式之策略模式详细讲解和案例示范
  • Objective-C中的查询大师:深入探索NSPredicate与NSExpression
  • EPCE-HDR
  • 基于单片机的仿生水母水下机器人设计
  • 电机学习记录
  • java整合Redis
  • 大话设计模式解读06-原型模式