字符串----hiho字符串(尺取法)
2023-03-14 09:45:23 时间
注意:这道题的解法和最短摘要一样,都是采用尺取法解决问题,注意这儿题目要求恰好包含,也就是说这个hiho字符串必须包含2个'h'、1个'i'和1个'o'。一个不能多,一个也不能少。
1 import java.util.Scanner; 2 3 public class HihoStr { 4 public static void main(String[] args) { 5 Scanner scanner = new Scanner(System.in); 6 String str = scanner.nextLine(); 7 char[]w = str.toCharArray(); 8 sovel(w); 9 } 10 11 private static void sovel(char[] w) { 12 int min = Integer.MAX_VALUE; 13 int j = -1; 14 for (int i = 0; i < w.length; i++) { 15 char c = w[i]; 16 if(check(c)){ //i停下 17 if (j==-1) { // j的第一次定位 18 j = i+1; 19 } 20 while(j<w.length){ 21 char c2 = w[j]; 22 if (check(c2)&&containsAll(w,i,j)) { // 全部囊括 23 if (check(w,i,j)&&j-i+1<min) { // 更新min 24 min = j-i+1; 25 } 26 break; // j停下 27 } 28 j++; 29 } 30 } 31 } 32 System.out.println(min==Integer.MAX_VALUE?-1:min); 33 } 34 35 private static boolean containsAll(char[] w, int i, int j) { 36 int c1=0,c2=0,c3=0; 37 for (int k = i; k <= j; k++) { 38 if(w[k]=='h') c1++; 39 if(w[k]=='i') c2++; 40 if(w[k]=='o') c3++; 41 } 42 return c1>=2&&c2>=1&&c3>=1; 43 } 44 45 /** 46 * 检查字符序列是否恰好包含2个h,一个i,一个o 47 * @param w 48 * @param i 49 * @param j 50 * @return 51 */ 52 private static boolean check(char[] w, int i, int j) { 53 int c1=0,c2=0,c3=0; 54 for (int k = i; k <= j; k++) { 55 if(w[k]=='h') c1++; 56 if(w[k]=='i') c2++; 57 if(w[k]=='o') c3++; 58 } 59 return c1==2&&c2==1&&c3==1; 60 } 61 62 private static boolean check(char c) { 63 return c=='h'||c=='i'||c=='o'; 64 } 65 66 }
结果:
尺取法的模型:根据区间的特征交替推进左右端点求解问题,其高效的原因在于避免了大量的无效枚举,其区间枚举都是根据区间特征有方向的枚举,如果胡乱使用尺取法的话会使得枚举量减少,因而很大可能会错误,所以关键的一步是进行问题的分析!下面分析一下尺取法的过程:
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的