第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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; } }
验证结果，通过：
