第十四届蓝桥杯集训——练习解题阶段(无序阶段)-Java全排列公式
【摘要】 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-Java全排列公式
字符串全排列
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-Java全排列公式
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
全排列题目要求
题目解析
从字符串数组中每次选取一个元素，作为结果中的第一个元素;然后，对剩余的元素全排列
全排列
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
公式：全排列数f(n)=n!(定义0!=1)
例如：如果是对任意的三个字符进行全排列，也就是3!=6，当然，如果是相同的就只有1次
String s="我爱你";
三个字符，全排列，6中结果
我爱你
我你爱
爱我你
爱你我
你爱我
你我爱
三个相同字符串，就一次
爱爱爱
那么我们要编辑出这种排列方法：
首先判断是否字符串相同：
方案1：
package com.item.action;
public class Demo1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "说说说说说";
for (int j = 0; j < 10; j++) {
long start = System.nanoTime();
char[] cs = s.toCharArray();
// 我们要判断字符串中是否有不相同的字符
boolean isf=false;
for (int i = 0; i < cs.length - 1; i++) {
if (cs[i] != cs[i + 1]) {
isf=true;
break;
}
}
long end = System.nanoTime();
System.out.println("char数组消耗时间：" + (end - start));
System.out.println(isf?"字符串不相同":"字符串都相同");
}
}
}
消耗时间：
方案2：
package com.item.action;
public class Demo2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "说说说说说";
for (int j = 0; j < 10; j++) {
long start = System.nanoTime();
// 我们要判断字符串中是否有不相同的字符
boolean isf=false;
for (int i = 0; i < s.length()-1; i++) {
if (s.charAt(i) != s.charAt(i+1)) {
isf=true;
break;
}
}
long end = System.nanoTime();
System.out.println("charAt消耗时间：" + (end - start));
System.out.println(isf?"字符串不相同":"字符串都相同");
}
}
}
消耗时间
根据方案1与方案2对比，我们知道charAt相对效率较高，我们使用第二种方法。
全排列示例代码
package com.item.action;
import java.util.ArrayList;
public class Demo3 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "说你爱我";
// 先进行判断是否相同字符串，后进行全排列
// 我们这里操作的都是char所以使用==，如果使用字符串s.equals(str)
boolean isf = true;
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) != s.charAt(i + 1)) {
isf = false;
break;
}
}
if (isf) {
System.out.println(s);// 因为只有1种排列
return;
}
// 全排列
f(s.toCharArray(), 0, s.length() - 1);
}
private static void f(char[] cs, int from, int to) {
// TODO Auto-generated method stub
// 写递归先写终止条件
if (from == to) {
System.out.println(cs);
}
for (int i = from; i <= to; i++) {
// 交换节点
changeIndex(cs, i, from);
// 递归·排序
f(cs, from + 1, to);
// 还原节点
changeIndex(cs, from, i);
}
}
private static void changeIndex(char[] cs, int from, int to) {
// TODO Auto-generated method stub
char temp = cs[from];
cs[from] = cs[to];
cs[to] = temp;
}
}
六种
判断是否正确
根据【公式：全排列数f(n)=n!(定义0!=1)】判断是否全排列完成。
示例字符串【说你爱我】，4个字。
阶乘可得：
package com.item.action;
public class Demo4 {
public static void main(String[] args) {
// TODO Auto-generated method stub
//计算阶乘
System.out.println(dfs(4));
}
private static int dfs(int i) {
// TODO Auto-generated method stub
if(i==1) {
return 1;
}
return i*dfs(i-1);
}
}
阶乘结果：
全排列代码验证：
package com.item.action;
import java.util.ArrayList;
public class Demo3 {
static ArrayList<char[]> list = new ArrayList<>();
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "说你爱我";
// 先进行判断是否相同字符串，后进行全排列
// 我们这里操作的都是char所以使用==，如果使用字符串s.equals(str)
boolean isf = true;
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) != s.charAt(i + 1)) {
isf = false;
break;
}
}
if (isf) {
System.out.println(s);// 因为只有1种排列
return;
}
// 全排列
f(s.toCharArray(), 0, s.length() - 1);
System.out.println("长度："+list.size());
}
private static void f(char[] cs, int from, int to) {
// TODO Auto-generated method stub
// 写递归先写终止条件
if (from == to) {
System.out.println(cs);
list.add(cs);
}
for (int i = from; i <= to; i++) {
// 交换节点
changeIndex(cs, i, from);
// 递归·排序
f(cs, from + 1, to);
// 还原节点
changeIndex(cs, from, i);
}
}
private static void changeIndex(char[] cs, int from, int to) {
// TODO Auto-generated method stub
char temp = cs[from];
cs[from] = cs[to];
cs[to] = temp;
}
}
验证结果，通过：
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）