最近的一些文章都可能会很碎,写到哪里是哪里,过一阵子会具体的整理一遍,这里其它的类型题先往后排一排,因为蓝桥最后考的也就是对题目逻辑的理解能力,也就是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;
}
}
验证结果,通过: