石碑文字全排列重组（华为od机考题）

2024-08-26 21:44
文章标签 文字 华为 排列 od 考题 重组 石碑

本文主要是介绍石碑文字全排列重组（华为od机考题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1.原题

有一个考古学家发现一个石碑，
但是很可惜，发现时其已经断成多段，
原地发现n个断口整齐的石碑碎片。
为了破解石碑内容，
考古学家希望有程序能帮忙计算复原后的石碑文字组合数，
你能帮忙吗？
[递归, 字符串, 哈希表]

2.题目理解

有n个碎片（字符可能重复），对这些碎片进行全排列然后输出。

二、思路与代码过程

1.思路

递归 回溯

2.代码过程

①main函数

public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入碎片的块数n：");int n = sc.nextInt();System.out.println("请依次输入碎片上的文字：");sc.nextLine();String[] words = sc.nextLine().split(" ");long factorial = factorial(n);System.out.println("当前碎片有"+factorial+"种排列方式");Arrays.sort(words);  // 排序以处理重复元素ArrayList<String> reStrings = new ArrayList<>();StringBuilder reString = new StringBuilder();boolean[] used = new boolean[n];ArrayList<String> ReStrings = BackTrack(reStrings, reString, words, used);for (String s : ReStrings) {System.out.println(s);}}

②数量计算（写来好玩的）

//计算阶乘public static long factorial(int n) {return LongStream.rangeClosed(1, n).reduce(1, (a, b) -> a * b);}

③BackTrack函数

private static ArrayList<String> BackTrack(ArrayList<String> reStrings, StringBuilder reString,String[] words, boolean[] used) {if (reString.toString().split(" ").length == words.length) {reStrings.add(reString.toString().trim());  // 去掉末尾的空格} else {for (int i = 0; i < words.length; i++) {if (used[i]) continue;if (i > 0 && words[i].equals(words[i - 1]) && !used[i - 1]) continue;reString.append(words[i]).append(" ");used[i] = true;BackTrack(reStrings, reString, words, used);// 回溯reString.setLength(reString.length() - words[i].length() - 1);  // 1 for spaceused[i] = false;}}return reStrings;}

三、运行结果

1.运行截图

2.带数据分析运行结果

请输入碎片的块数n：
3
请依次输入碎片上的文字：
i o u
当前碎片有6种排列方式
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：i 
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：i o 
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：i o u 
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：i o u
当前reStrings为：[i o u]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：i o 
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：i 
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：i u 
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：i u o 
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：i u o
当前reStrings为：[i o u, i u o]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：i u 
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：i 
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：o 
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：o i 
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：o i u 
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：o i u
当前reStrings为：[i o u, i u o, o i u]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：o i 
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：o 
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：o u 
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：o u i 
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：o u i
当前reStrings为：[i o u, i u o, o i u, o u i]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：o u 
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：o 
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：
当前i为：2，word为：u,使用状况为：false
组合中，当前i为：u
组合后，当前reString为：u 
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：u i 
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：true
当前i：i被用过啦！
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：u i o 
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：u i o
当前reStrings为：[i o u, i u o, o i u, o u i, u i o]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：u i 
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：u 
当前i为：1，word为：o,使用状况为：false
组合中，当前i为：o
组合后，当前reString为：u o 
=======进入回溯啦======
-----------------BackTrack Start------------------
正在组合哦！
当前i为：0，word为：i,使用状况为：false
组合中，当前i为：i
组合后，当前reString为：u o i 
=======进入回溯啦======
-----------------BackTrack Start------------------
完成了一条组合：u o i
当前reStrings为：[i o u, i u o, o i u, o u i, u i o, u o i]
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：u o 
当前i为：1，word为：o,使用状况为：true
当前i：o被用过啦！
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：u 
当前i为：2，word为：u,使用状况为：true
当前i：u被用过啦！
-----------------BackTrack End------------------
=======回溯完成啦======
撤销后当前的reString为：
-----------------BackTrack End------------------
i o u
i u o
o i u
o u i
u i o
u o i

3.带数据分析完整代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.LongStream;public class test36 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入碎片的块数n：");int n = sc.nextInt();System.out.println("请依次输入碎片上的文字：");sc.nextLine();String[] words = sc.nextLine().split(" ");long factorial = factorial(n);System.out.println("当前碎片有"+factorial+"种排列方式");Arrays.sort(words);  // 排序以处理重复元素ArrayList<String> reStrings = new ArrayList<>();StringBuilder reString = new StringBuilder();boolean[] used = new boolean[n];ArrayList<String> ReStrings = BackTrack(reStrings, reString, words, used);for (String s : ReStrings) {System.out.println(s);}}//计算阶乘public static long factorial(int n) {return LongStream.rangeClosed(1, n).reduce(1, (a, b) -> a * b);}private static ArrayList<String> BackTrack(ArrayList<String> reStrings, StringBuilder reString,String[] words, boolean[] used) {System.out.println("-----------------BackTrack Start------------------");if (reString.toString().split(" ").length == words.length) {System.out.println("完成了一条组合："+reString.toString().trim());//reStrings.add(reString.toString().trim());  // 去掉末尾的空格System.out.println("当前reStrings为：" +reStrings);//} else {System.out.println("正在组合哦！");//for (int i = 0; i < words.length; i++) {System.out.println("当前i为："+i+"，word为："+words[i]+",使用状况为："+used[i]);//if (used[i]){System.out.println("当前i："+words[i]+"被用过啦！");//continue;}if (i > 0 && words[i].equals(words[i - 1]) && !used[i - 1]){//处理重复System.out.println("当前i为："+words[i]+"和前面的重复啦，跳过哦！");continue;}System.out.println("组合中，当前i为："+words[i]);//reString.append(words[i]).append(" ");System.out.println("组合后，当前reString为："+reString);//used[i] = true;System.out.println("=======进入回溯啦======");BackTrack(reStrings, reString, words, used);System.out.println("=======回溯完成啦======");// 回溯reString.setLength(reString.length() - words[i].length() - 1);  // 1 for spaceSystem.out.println("撤销后当前的reString为："+reString);used[i] = false;}}System.out.println("-----------------BackTrack End------------------");return reStrings;}
}

这篇关于石碑文字全排列重组（华为od机考题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1109769。

相关文章

高效录音转文字：2024年四大工具精选！

高效录音转文字：2024年四大工具精选！

在快节奏的工作生活中，能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候，一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具！ 365在线转文字 直达链接：https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具，它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件，只
阅读更多...
为什么现在很多人愿意选择做债务重组？债重组真的就这么好吗？

为什么现在很多人愿意选择做债务重组？债重组真的就这么好吗？

债务重组，起初作为面向优质企业客户的定制化大额融资策略，以其高效周期著称，一个月便显成效。然而，随着时代的车轮滚滚向前，它已悄然转变为负债累累、深陷网贷泥潭者的救赎之道。在此路径下，个人可先借助专业机构暂代月供，经一段时间养护征信之后，转向银行获取低成本贷款，用以替换高昂网贷，实现利息减负与成本优化的双重目标。 尽管债务重组的代价不菲，远超传统贷款成本，但其吸引力依旧强劲，背后逻辑深刻。其一
阅读更多...
828华为云征文｜华为云Flexus X实例docker部署rancher并构建k8s集群

828华为云征文｜华为云Flexus X实例docker部署rancher并构建k8s集群

828华为云征文｜华为云Flexus X实例docker部署rancher并构建k8s集群 华为云最近正在举办828 B2B企业节，Flexus X实例的促销力度非常大，特别适合那些对算力性能有高要求的小伙伴。如果你有自建MySQL、Redis、Nginx等服务的需求，一定不要错过这个机会。赶紧去看看吧！ 什么是华为云Flexus X实例 华为云Flexus X实例云服务是新一代开箱即用、体
阅读更多...
PHP字符串全排列

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.全排列

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模：题目要求给出一个数组的所有排列组合，属于典型的全排列问题，这可以用回溯法来解决。回溯法通过递归的方式，依次将数组中的每个元素放入排列中，直到生成
阅读更多...
华为OD机试真题-学生方阵-2024年OD统一考试（E卷）

华为OD机试真题-学生方阵-2024年OD统一考试（E卷）

题目描述 学校组织活动，将学生排成一个矩形方阵。 请在矩形方阵中找到最大的位置相连的男生数量。这个相连位置在一个直线上，方向可以是水平的，垂直的，成对角线的或者呈反对角线的。 注:学生个数不会超过10000 输入描述 输入的第一行为矩阵的行数和列数， 接下来的 n行为矩阵元素，元素间用""分隔。 输出描述 输出一个整数，表示矩阵中最长的位
阅读更多...
华为 HCIP-Datacom H12-821 题库 (13)

华为 HCIP-Datacom H12-821 题库 (13)

有需要题库的可以看主页置顶 1.可以携带外部路由的 tag 标签信息的是以下哪一类 LSA? A、4 类 LSA B、5 类 LSA  C、3 类 LSA  D、2 类 LSA 答案：B 解析： 暂无解析 2..两台路由器直连，并设定网络类型为 p2p 建立OSPF 邻居。那么两台路由器传输 OSPF 报文的目的 IP 地址是以下哪一项？ A、使用组播地址 224.0.0.6 B
阅读更多...
4G模块、WIFI模块、NBIOT模块通过AT指令连接华为云物联网服务器（MQTT协议）

4G模块、WIFI模块、NBIOT模块通过AT指令连接华为云物联网服务器（MQTT协议）

MQTT协议概述 MQTT（Message Queuing Telemetry Transport）是一种轻量级的消息传输协议，它被设计用来提供一对多的消息分发和应用之间的通讯，尤其适用于远程位置的设备和高延迟或低带宽的网络。MQTT协议基于客户端-服务器架构，客户端可以订阅任意数量的主题，并可以发布消息到这些主题。服务器（通常称为MQTT Broker）则负责接受来自客户端的连接请求，并转发消
阅读更多...
华为23年笔试题

华为23年笔试题

消息传输 题目描述 在给定的 m x n (1 <= m, n <= 1000) 网格地图 grid 中，分布着一些信号塔，用于区域间通信。 每个单元格可以有以下三种状态：  值 0 代表空地，无法传递信号；  值 1 代表信号塔 A，在收到消息后，信号塔 A 可以在 1ms 后将信号发送给上下左右四个方向的信号塔； 值 2 代表信号塔 B，在收到消息后，信号塔 B 可以在 2ms
阅读更多...
代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II

代码随想录刷题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
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2