玉环哪里有做网站,上海有多少家公司和企业,做棋牌网站违法吗,自己建网站做代理商OD统一考试 分值#xff1a; 200分 题解#xff1a; Java / Python / C 题目描述
有一个考古学家发现一个石碑#xff0c;但是很可惜发现时其已经断成多段。 原地发现N个断口整齐的石碑碎片#xff0c;为了破解石碑内容#xff0c;考古学家希望有程序能帮忙计算复原后的石… OD统一考试 分值 200分 题解 Java / Python / C 题目描述
有一个考古学家发现一个石碑但是很可惜发现时其已经断成多段。 原地发现N个断口整齐的石碑碎片为了破解石碑内容考古学家希望有程序能帮忙计算复原后的石碑文字组合数你能帮忙吗
备注 如果存在石碑碎片内容完全相同则由于碎片间的顺序不影响复原后的碑文内容仅相同碎片间的位置变化不影响组合
输入描述
第一行输入NN表示石碑碎片的个数 第二行依次输入石碑碎片上的文字内容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(ListString 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, collectif len(collect) n: # 组合完成result .join(collect)if result ! last_result: # 避免重复的结果输出last_result resultprint(last_result)returnprev Nonefor i in range(n):if used[i] or cs[i] prev: # 元素被选中或元素相同continueused[i] Truecollect.append(cs[i])backtrack()collect.pop()prev cs[i]used[i] Falsebacktrack()
C
#include iostream
#include vector
#include algorithm
#include numericusing namespace std;void backtrack(const vectorstring cs, int n, vectorbool used, vectorstring 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;vectorstring cs(n);for (int i 0; i n; i) {cin cs[i];}sort(cs.begin(), cs.end());vectorbool used(n, false);vectorstring collect;string lastResult;backtrack(cs, n, used, collect, lastResult);return 0;
}
相关练习题
题号题目难易LeetCode 面试题 08.07面试题 08.07. 无重复字符串的排列组合中等LeetCode 4747. 全排列 II中等LeetCode LCR 083LCR 083. 全排列中等
整理题解不易 如果有帮助到您请给点个赞 ❤️ 和收藏 ⭐让更多的人看到。
