【DFS】困难的串
2023-03-14 09:45:06 时间
题目:
问题描述:如果一个字符串包含两个相邻的重复子串,则称它为容易的串,其他串称为困难的串。如:BB,ABCDACABCAB,ABCDABCD都是容易的,A,AB,ABA,D,DC,ABDAB,CBABCBA都是困难的。
输入正整数L,n,输出由前L个字符(大写英文字母)组成的,字典序第n小的困难的串。
例如,当L=3时,前7个困难的串分别为:A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA。
n 指定为4的话,输出ABAC。
代码:
1 import java.util.Scanner; 2 3 public class 困难的串 { 4 5 public static void main(String[] args) { 6 // int n = 10; 7 // int L = 4; 8 Scanner scanner = new Scanner(System.in); 9 int L = scanner.nextInt(); 10 int n = scanner.nextInt(); 11 dfs(L, n, ""); 12 // isHard("0123020120",1); 13 } 14 15 static int count; 16 17 private static void dfs(int l, int n, String prefix) { 18 19 // 尝试在prefix后追加一个字符 难点一:维持字典序 20 for (char i = 'A'; i < 'A' + l; i++) { 21 if (isHard(prefix, i)) {// 是困难的串,就组合起来输出 22 String x = prefix + i; 23 //System.out.println(x); 24 count++;// 计数 25 if (count == n){ 26 System.out.println(x); 27 System.exit(0); 28 } 29 30 dfs(l, n, x); 31 } 32 } 33 } 34 35 /** 36 * 难点二:判断prefix+i是否一个困难的串 37 * 1.遍历所有的长度为偶数的子串,看是否对称 38 * 2.prefix本身是一个困难的串 ABACA i 往后遍历逐步比较 39 * @param prefix 40 * @param i 41 * @return 42 */ 43 private static boolean isHard(String prefix, char i) { 44 int count = 0;// 截取的宽度 45 for (int j = prefix.length() - 1; j >= 0; j -= 2) { 46 final String s1 = prefix.substring(j, j + count + 1); 47 final String s2 = prefix.substring(j + count + 1) + i; 48 if (s1.equals(s2)) 49 return false; 50 count++; 51 } 52 return true; 53 } 54 }
结果:
相关文章
- 被历史遗忘的首批程序猿
- Linux OS||不响应SYN总结
- "永恒之蓝"勒索病毒凶猛 周一上班请用正确姿势打开电脑
- 不容错过 | “永恒之蓝”勒索病毒安全处置FAQ
- “永恒之蓝”勒索病毒安全事件应急指导手册(附工具包)
- “永恒之蓝”勒索软件样本分析及一线案例处置分享
- 如何在CentOS 5/6上安装EPEL 源
- EMR集群上capacity scheduler的ACL实现
- Linux Uptime 命令,让你知道你的系统运行了多久
- 为什么GNU grep如此之快?
- 如何在Linux中显示和设置主机名
- 容器镜像服务中源代码仓库常见问题汇总
- SBackup: 一个Linux下的简单备份软件
- 浏览器访问 HDFS 页面时,出现以下问题
- 永远不要在Linux执行的10个最危险的命令
- 如何在Linux平台上安装Ghost博客平台
- 如何在Linux上制作一个屏幕录像视频教程
- ps命令的10个例子
- Linux 面试基础问题 - 3
- Linux 下使用Trickle限制下载/上传带宽