考古学家 - 华为OD统一考试
OD统一考试
分值: 200分
题解: Java / Python / C++
题目描述
有一个考古学家发现一个石碑,但是很可惜发现时其已经断成多段。
原地发现N
个断口整齐的石碑碎片,为了破解石碑内容,考古学家希望有程序能帮忙计算复原后的石碑文字组合数,你能帮忙吗?
备注: 如果存在石碑碎片内容完全相同,则由于碎片间的顺序不影响复原后的碑文内容,仅相同碎片间的位置变化不影响组合
输入描述
第一行输入N
,N
表示石碑碎片的个数
第二行依次输入石碑碎片上的文字内容S
共有N
组
输出描述
输出石碑文字的组合(按照升序排列),行尾无多余空格
示例1
输入:
3
a b c
输出:
abc
acb
bac
bca
cab
cba
示例2
输入:
3
a b ab
输出:
aab
aba
baa
示例3
输入:
3
a b a
输出:
aabb
abab
abba
baab
baba
题解
这是一个典型的排列组合问题,可以使用回溯算法来生成所有可能的组合。
代码大致描述:
- 主函数
main
中,读取石碑碎片的个数N和每个碎片的文字内容S,并进行排序,以便后续生成有序的排列组合。。- 创建一个用于标记是否使用过的数组
used
和一个用于存储当前组合的容器collect
,以及一个记录上次结果的字符串lastResult
。- 调用
backtrack
函数进行回溯,生成所有可能的排列组合。- 在
backtrack
函数中,检查当前组合的长度是否等于石碑碎片的个数N,如果是则拼接成字符串并输出(避免重复输出相同的排列组合)。- 递归调用
backtrack
函数,尝试不同的组合。- 在每次递归调用前,标记当前石碑碎片为已使用,以防止重复使用。
- 递归调用后,将标记恢复,进行下一轮尝试。
这样,通过回溯算法,可以遍历所有可能的排列组合,最终输出升序排列的石碑文字组合。
Java
import java.util.*;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
String[] cs = new String[n];
for (int i = 0; i < n; i++) cs[i] = in.next();
Arrays.sort(cs);
Solution solution = new Solution(cs, n);
solution.backtrack(new ArrayList<>());
}
}
class Solution {
private final String[] cs;
private final int n;
private String lastResult;
private boolean[] used;
public Solution(String[] cs, int n) {
this.cs = cs;
this.n = n;
this.used = new boolean[n];
}
public void backtrack(List<String> collect) {
if (collect.size() == n) {
String result = String.join("", collect);
if (!result.equals(lastResult)) { // 避免重复的结果输出
System.out.println(result);
lastResult = result;
}
return;
}
String prev = ""; // 记录上次有效的选择
for (int i = 0; i < n; i++) {
if (used[i] || Objects.equals(cs[i], prev)) continue;
used[i] = true;
collect.add(cs[i]);
backtrack(collect);
prev = cs[i];
collect.remove(collect.size() - 1);
used[i] = false;
}
}
}
Python
n = int(input())
cs = input().split()
cs.sort()
last_result = None
used, collect = [False] * n, []
def backtrack():
global last_result, used, collect
if len(collect) == n: # 组合完成
result = "".join(collect)
if result != last_result: # 避免重复的结果输出
last_result = result
print(last_result)
return
prev = None
for i in range(n):
if used[i] or cs[i] == prev: # 元素被选中或元素相同
continue
used[i] = True
collect.append(cs[i])
backtrack()
collect.pop()
prev = cs[i]
used[i] = False
backtrack()
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
void backtrack(const vector<string>& cs, int n, vector<bool>& used, vector<string>& collect, string& lastResult) {
if (collect.size() == n) {
string result = accumulate(collect.begin(), collect.end(), string(""));
if (result != lastResult) {
cout << result << endl;
lastResult = result;
}
return;
}
string prev = "";
for (int i = 0; i < n; i++) {
if (used[i] || cs[i] == prev) continue;
used[i] = true;
collect.push_back(cs[i]);
backtrack(cs, n, used, collect, lastResult);
prev = cs[i];
collect.pop_back();
used[i] = false;
}
}
int main() {
int n;
cin >> n;
vector<string> cs(n);
for (int i = 0; i < n; i++) {
cin >> cs[i];
}
sort(cs.begin(), cs.end());
vector<bool> used(n, false);
vector<string> collect;
string lastResult;
backtrack(cs, n, used, collect, lastResult);
return 0;
}
相关练习题
题号 | 题目 | 难易 |
---|---|---|
LeetCode 面试题 08.07 | 面试题 08.07. 无重复字符串的排列组合 | 中等 |
LeetCode 47 | 47. 全排列 II | 中等 |
LeetCode LCR 083 | LCR 083. 全排列 | 中等 |
🙏整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏
原文地址:https://blog.csdn.net/user_longling/article/details/135536045
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!