热门标签 | HotTags
当前位置:  开发笔记 > 人工智能 > 正文

java经典问题:连个字符串互为回环变位

连个字符串互为回环变位经常出现在java程序员面试中,这个是考验程序员的解题思路和方法的最经典的一题,小编为大家详细分析一下,一起来学习吧。

本次给大家带来的是关于判断连个字符串是否互为回环变位(Circular Rotaion)的java程序员面试经常出现的题型,给大家做了两种方式的解答,希望能帮助到你。

一般情况下都是笔试或者是直接上机操作,题型一般都是:如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t,那么 s 就被称为 t 的回环变位(circular rotation)。

A string s is a circular rotation of a string t if it matches when the characters are circularly shifted by any number of positions;
e.g., ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences.
Write a program that checks whether two given strings s and t are circular.

关于解答方面,我给在这里给出了2种方式:
解法一:
将s拆分成左右两部分,然后另令s'=右+左,遍历所有情况。如果是回环字符串的话,其中会有 s'=t 的情况。

public static boolean isCircularRotation(String s, String t) {
    if (s.length() != t.length())
      return false;
    int sLen = s.length();
    for (int i = 0; i <= sLen; i++) {
      // 注意subString的后角标的界限
      String sLeft = s.substring(0, i);
      String sRigth = s.substring(i + 1, sLen);
      if ((sRigth + sLeft).equals(t))
        return true;
    }
    return false;
  }

解法二:(巧妙)

public static boolean isCircularRotation_1(String s, String t) {
  return (s.length() == t.length() && (t + t).contains(s));
}

以上就是基本快速的两种解决方式,关于这个问题,再给大家看一篇很详细的判断字符串回环变位解决思路:

如果字符串s中的字符循环移动任意位置之后能够得到另一字符串t,那么s就被称为t的回环变位。例如,ACTGACG 就是 TGACGAC 的一个回环变位,反之亦然。判定这个条件在基因组序列中的研究是十分重要的。编写一个算法检查两个给定的字符串s和t是否互为回环变位。

这是我在《算法(第四版)》里看到的一道练习题 ,当时的第一想法就是遍历字符串 t,从不同的索引位置将字符串t分解成两个子串,交换顺序拼接后再与s相比是否相等。算法如下:

 public static boolean isCircularRotation(String s, String t) {
    if (s.length() != t.length()) {
      return false;
    }
    int length = s.length();
    for (int i = 1; i <= length; i++) {
      String left = s.substring(0, i);
      String right = s.substring(i, length);
      if ((right + left).equals(t)) {
        return true;
      }
    }
    return false;
  }

后来看答案,提示说可以用一行代码就能搞定了。当时想了想,感觉不太可能,就作罢了。今天重新开始学习这本书的时候,再次看到这道题,突然有了想法代码如下:

public static boolean isCircularRotation(String s, String t) {
    return s.length() == t.length() && (t + t).contains(s);
  }

解释:如果字符串s和t互为回环变位,则s可分解为“AB”,t可分解为“BA”。那么t与自身拼接后则为“BABA”,显然是会包含s的。这种思路比较巧妙,当然了,自认为算法效率并没有什么提高。

为什么大家都会对这个经典的JAVA问题困惑着?最主要的原因就是解题的思路问题:

容易想复杂的"回环变位",思路错误,问题就会复杂化,一起来看下经典的误区和最终想明白以后的解法。

题目描述很简单:
如果字符串s重的字符循环移动任意位置之后能够得到另一个字符串t,那么s就被成为s的回环变位(circular rotation) 举例省略…
问题:请编写一个程序检查2个给定的字符串s和t是否互为回环变位。
提示:判断条件只需要一行代码

看到题目当时满脑子想的都是双重循环啊,游标移动啊各种i,j,k……
结果来一句这样的提示,当时我就受不了了,决定去看一下答案….

答案是这样的

(s.length() == t.length()) && (s.concat(s).indexOf(t) >= 0)

乍一看,好像真的可以…顿时鄙视了自己的各种游标循环i,j,k…
(虽然可能底层也是各种循环游标i,j,k,但是别人都实现了的基类直接用明显更省事…)

但是也发现自己对String类的concat函数和indexOf的各种重载不懂

一下是jdk文档的描述

public String concat(String str)将指定字符串连接到此字符串的结尾。 
如果参数字符串的长度为 0,则返回此 String 对象。否则,创建一个新的 String 对象,用来表示由此 String 对象表示的字符序列和参数字符串表示的字符序列连接而成的字符序列。

示例: 

 "cares".concat("s") returns "caress"
 "to".concat("get").concat("her") returns "together"

参数:
str - 连接到此 String 结尾的 String。 
返回:
一个字符串,它表示在此对象字符后连接字符串参数字符而成的字符。
public int indexOf(String str)返回指定子字符串在此字符串中第一次出现处的索引。返回的整数是 
 this.startsWith(str, k)
 为 true 的最小 k 值。 

参数:
str - 任意字符串。 
返回:
如果字符串参数作为一个子字符串在此对象中出现,则返回第一个这种子字符串的第一个字符的索引;如果它不作为一个子字符串出现,则返回 -1。

关于这个问题,已经在上文章阐述的非常清楚了,大家如果对此还有任何的疑问,可以在本文下方留言讨论。


推荐阅读
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 本文探讨了Hive中内部表和外部表的区别及其在HDFS上的路径映射,详细解释了两者的创建、加载及删除操作,并提供了查看表详细信息的方法。通过对比这两种表类型,帮助读者理解如何更好地管理和保护数据。 ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现,详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]
  • 本文详细探讨了Java中的24种设计模式及其应用,并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类,帮助开发者更好地理解和应用这些模式,提升代码质量和可维护性。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 探讨一个显示数字的故障计算器,它支持两种操作:将当前数字乘以2或减去1。本文将详细介绍如何用最少的操作次数将初始值X转换为目标值Y。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 本文探讨如何设计一个安全的加密和验证算法,确保生成的密码具有高随机性和低重复率,并提供相应的验证机制。 ... [详细]
  • 深入解析:手把手教你构建决策树算法
    本文详细介绍了机器学习中广泛应用的决策树算法,通过天气数据集的实例演示了ID3和CART算法的手动推导过程。文章长度约2000字,建议阅读时间5分钟。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • 在给定的数组中,除了一个数字外,其他所有数字都是相同的。任务是找到这个唯一的不同数字。例如,findUniq([1, 1, 1, 2, 1, 1]) 返回 2,findUniq([0, 0, 0.55, 0, 0]) 返回 0.55。 ... [详细]
  • 理解存储器的层次结构有助于程序员优化程序性能,通过合理安排数据在不同层级的存储位置,提升CPU的数据访问速度。本文详细探讨了静态随机访问存储器(SRAM)和动态随机访问存储器(DRAM)的工作原理及其应用场景,并介绍了存储器模块中的数据存取过程及局部性原理。 ... [详细]
  • 本文探讨了卷积神经网络(CNN)中感受野的概念及其与锚框(anchor box)的关系。感受野定义了特征图上每个像素点对应的输入图像区域大小,而锚框则是在每个像素中心生成的多个不同尺寸和宽高比的边界框。两者在目标检测任务中起到关键作用。 ... [详细]
author-avatar
手机用户2502903761
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有