[保研/考研机试] KY43 全排列 北京大学复试上机题 C++实现

题目链接:

全排列icon-default.png?t=N6B9https://www.nowcoder.com/share/jump/437195121692001512368

描述

给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z',而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入描述:

输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在1到6之间。

输出描述:

输出这个字符串的所有排列方式,每行一个排列。要求字母序比较小的排列在前面。字母序如下定义: 已知S = s1s2...sk , T = t1t2...tk,则S < T 等价于,存在p (1 <= p <= k),使得 s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。 每组样例输出结束后要再输出一个回车。

示例1

输入:

abc

输出:

abc
acb
bac
bca
cab
cba

方法一 递归:

思路:

  1. 定义递归函数 generatePermutations,其中参数 prefix 表示当前已生成的前缀,参数 remaining 表示剩余的字符。
  2. 如果剩余字符串只有一个字符,将前缀和剩余字符拼接输出。
  3. 否则,遍历剩余字符,分别将当前字符作为前缀的一部分,然后递归调用生成剩余部分的全排列。
  4. main 函数中,读入输入的字符串,调用递归函数生成全排列。

源代码:

#include<iostream>
using namespace std;// 递归函数,用于生成字符串的全排列
void generatePermutations(string prefix, string remaining) {if (remaining.size() == 1) {// 如果剩余字符串只有一个字符,将前缀和剩余字符拼接输出cout << prefix + remaining << endl;return;}// 遍历剩余字符,分别将当前字符作为前缀的一部分,继续递归生成全排列for (int i = 0; i < remaining.size(); i++) {string newPrefix = prefix + remaining[i]; // 当前字符作为前缀的一部分string newRemaining = remaining; // 拷贝剩余字符串newRemaining.erase(i, 1); // 删除当前字符,得到新的剩余字符串generatePermutations(newPrefix, newRemaining); // 递归调用生成全排列}
}int main() {string s;cin >> s; // 输入字符串generatePermutations("", s); // 调用递归函数生成全排列return 0;
}

方法二 使用内置全排列函数:

next_permutation 函数的作用:

  • next_permutation 是 C++ 标准库中的一个函数,用于生成给定序列的下一个排列,以字典序的方式。
  • 如果当前排列是字典序的最后一个排列,next_permutation 返回 false,否则返回 true 并生成下一个排列。
  • 在生成下一个排列时,会将当前排列修改为下一个排列。
  • next_permutation 函数接受两个迭代器作为参数,表示需要生成排列的范围。

源代码:

#include <iostream>
#include <algorithm> // 包含了 sort 和 next_permutation 函数
using namespace std;int main() {string s;while (cin >> s) { // 循环读取输入的字符串cout << s << endl; // 输出初始字符串sort(s.begin(), s.end()); // 将字符串按照字典序排序// 使用 next_permutation 生成剩余的全排列并输出for (; next_permutation(s.begin(), s.end());) {cout << s << endl;}cout << endl; // 每组样例输出结束后输出一个回车}return 0;
}

提交结果:

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/96977.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从零实战SLAM-第四课(相机成像及常用视觉传感器)

在七月算法报的班&#xff0c;老师讲的蛮好。好记性不如烂笔头&#xff0c;关键内容还是记录一下吧&#xff0c;课程入口&#xff0c;感兴趣的同学可以学习一下。 --------------------------------------------------------------------------------------------------------…

[保研/考研机试] 杨辉三角形 西北工业大学复试上机题 C++实现

题目描述 Time Limit: 1000 ms Memory Limit: 256 mb 输入n值&#xff0c;使用递归函数&#xff0c;求杨辉三角形中各个位置上的值。 输入描述: 一个大于等于2的整型数n 输出描述: 题目可能有多组不同的测试数据&#xff0c;对于每组输入数据&#xff0c; 按题目的要求输…

符号随机梯度下降算法SIGNSGD

考虑随机优化问题&#xff1a; 符号随机梯度下降(SIGNSGD)算法&#xff1a; 假设基础&#xff1a; 收敛定理&#xff1a; 联邦优化&#xff1a;

08-微信小程序视图层

08-微信小程序视图层 文章目录 视图层 ViewWXML数据绑定列表渲染条件渲染模板引用importimport 的作用域include WXSS尺寸单位样式导入内联样式选择器全局样式与局部样式 WXS注意事项页面渲染数据处理 视图层 View 框架的视图层由 WXML 与 WXSS 编写&#xff0c;由组件来进行…

国产32位单片机XL32F001,带1 路 12bit ADC,I2C、SPI、USART 等外设

XL32F001 系列单片机采用高性能的 32 位 ARM Cortex-M0内核&#xff0c;宽电压工作范围的 MCU。嵌入 24KbytesFlash 和 3Kbytes SRAM 存储器&#xff0c;最高工作频率 24MHz。包含多种不同封装类型多款产品。芯片集成 I2C、SPI、USART 等通讯外设&#xff0c;1 路 12bit ADC&am…

idea中Maven报错Unable to import maven project: See logs for details问题的解决方法

idea中Maven报错Unable to import maven project: See logs for details问题的解决方法。 在查看maven的环境配置和idea的maven配置后&#xff0c;发现是idea 2020版本和maven 3.9.3版本的兼容性问题。在更改为Idea自带的maven 3.6.1版本后问题解决&#xff0c;能成功下载jar包…

如何修复损坏的DOC和DOCX格式Word文件?

我们日常办公中&#xff0c;经常用到Word文档。但是有时会遇到word文件损坏、无法打开的情况。这时该怎么办&#xff1f;接着往下看&#xff0c;小编在这里就给大家带来最简单的Word文件修复方法&#xff01; 很多时候DOC和DOCX Word文件会无缘无故的损坏无法打开&#xff0c;一…

Aurix TC3xx系列MCU ResourceM模块配置(多核资源分配)

文章目录 1 前言2 配置方法 >>返回总目录<< 1 前言 为减轻主核的负载率或者平衡各个核的资源分配&#xff0c;通常需要把一些MCU内部资源分配到从核上&#xff0c;在EB tresos工具中&#xff0c;通过ResourceM模块实现多核资源分配。 2 配置方法 ResourceMMaste…

16.5.4 【Linux】SELinux 政策内的规则管理

SELinux 各个规则的布林值查询 getsebool 如果想要查询系统上面全部规则的启动与否 &#xff08;on/off&#xff0c;亦即布林值&#xff09;&#xff0c;很简单的通过 sestatus-b 或 getsebool -a 均可&#xff01; SELinux 各个规则规范的主体程序能够读取的文件 SELinux typ…

如何用轻叶H5制作一份调查问卷

在营销落地页中&#xff0c;问卷类H5是一种制作简单&#xff0c;易于传播的落地页&#xff0c;通过精巧的设计和严密的逻辑设置&#xff0c;问卷类H5的投放效果也是不容小觑的。 问卷类H5在制作中有以下不可缺少的要素&#xff1a; 清晰的标题和简要的说明 标题应该简明扼要地…

Springboot 实践(5)springboot添加资源访问目录及目录测试

前文讲解了swagger测试服务控制器&#xff0c;实现了数据库数据访问&#xff0c;这些功能都是运行在后台服务器上&#xff0c;实际用户并不能直接调用接口获取数据&#xff0c;即使用户能够利用接口获取到数据&#xff0c;数据也是结构化数据&#xff0c;不能争取转化成用户使用…

码银送书第五期《互联网广告系统:架构、算法与智能化》

广告平台的建设和完善是一项长期工程。例如&#xff0c;谷歌早于2003年通过收购Applied Semantics开展Google AdSense 项目&#xff0c;而直到20年后的今天&#xff0c;谷歌展示广告平台仍在持续创新和提升。广告平台是负有营收责任的复杂在线平台&#xff0c;对其进行任何改动…

MATLAB打开excel读取写入操作例程

本文使用素材含代码测试用例等 MATLAB读写excel文件历程含&#xff0c;内含有测试代码资源-CSDN文库 打开文件 使用uigetfile函数过滤非xlsx文件&#xff0c;找到需要读取的文件&#xff0c;首先判断文件是否存在&#xff0c;如果文件不存在&#xff0c;程序直接返回&#x…

容器技术发展和编排技术演进之路

目录 Jail 时代 1979 年 贝尔实验室发明 chroot 2000 年 FreeBSD 4.0 发行 FreeBSD Jail 2001 年 Linux VServer 发行 2004 年 Solaris Containers 发行 云时代 2006 年 google 推出 Process Containers 2008 年 LXC 推出 2011 年 CloudFoundry 推出 Warden 2013 年 LMCTFY 启动…

mybatis-plus 根据指定字段 批量 删除/修改

mybatis-plus 提供了根据id批量更新和修改的方法,这个大家都不陌生 但是当表没有id的时候怎么办 方案一: 手写SQL方案二: 手动获取SqlSessionTemplate 就是把mybatis plus 干的事自己干了方案三 : 重写 executeBatch 方法结论: mybatis-plus 提供了根据id批量更新和修改的方法,…

VR数字工厂多元化展现,打造数字企业工厂名片

5G时代&#xff0c;各种营销都在走数字化的路子&#xff0c;VR数字工厂用VR赋能工厂数字升级&#xff0c;将企业环境、工厂生产、产品研发、质检运输等流程&#xff0c;无死角720度的展示在客户面前&#xff0c;不仅可以提升自身企业的实力&#xff0c;还可以提高客户的信任感。…

arduino Xiao ESP32C3 oled0.96 下雪花

Xiao ESP32C3使用oled 0.96实现下雪的功能 雪花下落的时候, 随机生成半径和位置 sandR和sandX,sandY 保存雪花下落位置的时候, 将其周边一圈设置为-1, 标记为有雪花 其他雪花下落的时候, 其他雪花的一圈如果遇到-1, 则停止下落, 并重复2 #include "oled.h" void …

微软商店的ubuntu 连不上网Temporary failure in name resolution

背景&#xff1a;win10 下载docker时需要wsl2&#xff0c;下了个微软商店的Ubuntu 。写这篇文章的原因是当时查了资料ubuntu的问题和微软下载的Ubuntu还是有一些区别&#xff0c;问题不好解决&#xff0c;故写此文。 问题&#xff1a;用命令ifconfig eth0 down后再执行ifconfi…

1391. 检查网格中是否存在有效路径;2502. 设计内存分配器;1638. 统计只差一个字符的子串数目

核心思想&#xff1a;并查集。枚举网格中的块&#xff0c;把能连通的连通在一起&#xff0c;最后看&#xff08;0&#xff0c;0&#xff09;和&#xff08;m-1,n-1&#xff09;是否连通&#xff0c;然后网格中的每个点坐标是二维的&#xff0c;然后通过x*ny转换为一维&#xff…

【C++】C++入门基础:引用详解

本篇继续分享关于C入门的相关知识&#xff0c;有关命名空间、缺省参数和函数重载的部分欢迎阅读我的上一篇文章【C】C入门基础详解&#xff08;1&#xff09;_王笃笃的博客-CSDN博客 继续我们的学习 引用 在C语言中我们接触过指针&#xff0c;很多人都或多或少为他感到头痛过…