九度OJ-1120:全排列

2024-08-23 02:48
文章标签 排列 oj 九度 1120

本文主要是介绍九度OJ-1120:全排列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  本题最初打算用深度优先搜索+回溯法来做。后来不论怎么修改都是TLE。最后没有办法上网搜索学习了一下STL的next_permutation函数来做这题。


题目描述:

给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。
我们假设对于小写字母有'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成立。

样例输入:
abc
样例输出:
abc
acb
bac
bca
cab
cba
提示:

每组样例输出结束后要再输出一个回车。

来源:
2008年北京大学图形实验室计算机研究生机试真题
答疑:
解题遇到问题?分享解题心得?讨论本题请访问: http://t.jobdu.com/thread-7843-1-1.html


#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXSIZE 10
using namespace std;int main(){char str[MAXSIZE];int len;while (scanf("%s",str)!=EOF){len=strlen(str);do{printf("%s\n",str);}while (next_permutation(str,str+len));printf("\n");}return true;
}
/**************************************************************Problem: 1120User: bit3125Language: C++Result: AcceptedTime:350 msMemory:1020 kb
****************************************************************/


这篇关于九度OJ-1120:全排列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

PHP字符串全排列

方法一: $str = 'abc';$a =str_split($str);perm($a, 0, count($a)-1);function perm(&$ar, $k, $m) {if($k == $m){ echo join('',$ar), PHP_EOL;}else {for($i=$k; $i<=$m; $i++) {swap($ar[$k], $ar[$i]);perm($ar

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模:题目要求给出一个数组的所有排列组合,属于典型的全排列问题,这可以用回溯法来解决。回溯法通过递归的方式,依次将数组中的每个元素放入排列中,直到生成

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II 1.题目 1.1递增子序列 题目链接:491. 非递减子序列 - 力扣(LeetCode) 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0491.%E9%80%92%E

python 实现第k个字典排列算法

第k个字典排列算法介绍 "第k个字典排列"算法通常指的是在给定的字符集合(例如,字符串中的字符)中,找到所有可能排列的第k个排列。这个问题可以通过多种方法解决,但一个常见且高效的方法是使用“下一个排列”算法的变种,或称为“第k个排列”的直接算法。 方法一:使用“下一个排列”的变种 生成所有排列:首先生成所有排列,但显然这种方法对于较大的输入集合是不切实际的,因为它涉及到大量的计算和存储。 排序

九度1077(最大序列和)

题目链接:点击打开链接 解题思路: 很经典的一道题。首先考虑一下细节问题,当序列都是0时,显然最后要输出0;当序列都是负数时,显然要输出最大的数。 细节处理完了,就可以回到正常轨道。我们开两个变量,分别保存当前的序列和与之前的最大值,我们更新当前序列和的条件是如果当前序列和是负数的时候,那我们必须更新,否则一定会使最后结果减小。更新过程中还要更新之前最大值即可。 完整代码:

哈理工OJ 2179(深搜)

组合 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 7(5 users)Total Accepted: 6(5 users)Rating: Special Judge: No Description 给出一个正整数N,从集合{1,2,3..N} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

C++解决:求排列数

描述 输入两个整数m,n,求m个数字中选n个数的排列数。(1<=n<=m<=50) 输入描述 两个正整数m和n。 输出描述 一个正整数表示排列数。 用例输入 1  6 5 用例输出 1  720 AC code #include<bits/stdc++.h>using namespace std;int fun(int n) {int sum=1;for(int i=n

每日一题~cf 970 div3 (A思维,B小模拟,C二分,D排列数建图成环,E 26个字母暴力+前缀和,F 逆元,G 数论gcd )

A 题意: 有 a 个1 ,b 个2.问是否能将这些数划分为两个数值相等的集合。 输出 YES 或者 NO —————— 问题等价于 将数组 分成两个数值相同的数组。所以sum 应该是偶数。也就是说 1 的个数是偶数。在i1的个数是偶数的情况下,将 2 分成两份,如果2 的个数是偶数,OK。如果是奇数那么需要1来补齐,如果1 的个数大于等于2那么可以补齐。(1 的个数是偶数,需要2个1来补齐,剩下

OJ-0905

题目 示例1: 输入:10 10 56 34 99 1 87 8 99 3 255 6 99 5 255 4 99 7 255 2 99 9 255 213 4输出:99 示例2: 输入:10 10 255 34 0 1 255 8 0 3 255 6 0 5 255 4 0 7 255 2 0 9 255 213 5输出:255 import java.util.