笔试题33——双队列解决全排列拼接问题

  • Post author:
  • Post category:其他



题目描述:


有5个歌单,编号分别为A、B、C、D、E,每个歌单有三首不同的歌。当输入一些歌单名称的时候,每个歌单中输出一首歌到播放列表,并输出所有满足条件的播放列表。


输入描述:


输入一个仅包含且不重复的A-E的字符串


输出描述:


输出所有满足条件的播放列表(输出需要有序,字母必须大写)


输入:


AC


输出:


A1C1 A1C2 A1C3 A2C1 A2C2 A2C3 A3C1 A3C2 A3C3


思路:


设置两个队列q1,q2,遍历第一个字母,把拼接好字符串存入q1; 遍历下个字母时,从q1取出字符串,然后拼接上数字,放入q2中;最后,q1取完后,把q2的字符串存到q1;接着遍历下一个字母执行同样操作直到结束。

核心代码如下:

#include  <iostream>
#include  <cstring>
#include  <string>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
	string str;
	cin >> str;
	queue<string> q1;
	queue<string> q2;
	for (int i = 0; i < str.size(); i++) {
		if (q1.empty()) {
			for (int j = 1; j <= 3; j++) {
				string s;
				s += str[i];
				s += (j + '0'); //ss += to_string(j);
				q1.push(s);
			}
		}
		else {
			while (!q1.empty()) {			
				for (int j = 1; j <= 3; j++) {	
					string s = q1.front();
					s += str[i];
					s += (j + '0'); //ss += to_string(j);
					q2.push(s);
				}
				q1.pop();
			}
		}
		while (!q2.empty()) {
			q1.push(q2.front());
			q2.pop();
		}
	}

	while (!q1.empty()) {
		cout << q1.front();
		q1.pop();
		if (q1.empty())
			cout << endl;
		else
			cout << " ";
	}	
	return 0;
}



版权声明:本文为qq_27952053原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。