• 中文
    • English
  • 注册
  • 赞助本站

    • 支付宝
    • 微信
    • QQ

    感谢一直支持本站的所有人!

    • 查看作者
    • 《算法第四版》课后练习题1.2.6答案

      习题1.2.6

      如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t,那么 s 就被称为 t 的回环变位(circular rotation)。例如,ACTGACG就是TGACGAC的一个回环变位,反之亦然。判定这个条件在基因组序列的研究中是很重要的。编写一个程序检查两个给定的字符串 s 和 t 是否互为回环变位。提示:答案只需要一行用到indexOf() ,length() 和字符串连接的代码。

      要点分析

      1.  length()

      该方法用于计算字符串的长度,如果s和t这两个字符串长度都不一样,就不可能是回环变位。

      2.  indexOf()方法

      indexOf()方法用于返回一个指定字符在此字符串中第一次出现的索引。

      3.  String.contains()方法

      String.contains()方法用于检查两个字符串是否有包含关系。

      4.  substring()

      该方法用于根据指定索引范围截取字符串

      5.  charAt()

      charAt()方法用于返回指定索引位置的字符

      6.  代码实现

      public class Test {
          public static void main(String[] args) {
              String s = "1234561";
              System.out.println(s.length());
              System.out.println(s.indexOf("345"));
              System.out.println(s.contains("123456"));
              System.out.println(s.substring(2));
              System.out.println(s.substring(2,5));
              System.out.println(s.charAt(0));
      
          }
      }
      
      输出:
      7
      2
      true
      34561
      345
      1

      7.  方法一

      为什么上面介绍了这么多方法呢,因为这道题有很多种好玩的做法。方法一也就是最笨的方法,将字符串s,依次遍历,每次遍历的时候,都将字符串拆成两份,然后再组成一份看是否和t相等。当然遍历也有两种方法,本文答案第二种方法的遍历更加简单[1] 

      8.  方法二

      也就是课本中给的提示,用indexOf方法。该方法非常的有意思,只用一行代码就解决了问题[2]。该方法的原理如下。

      比如字符串s为ABC,而字符串t为BCA,因为t + t 为BCABCA ,所以t + t 是包含字符串s的

      那么(t + t).indexOf(s)的返回值必大于等于0,也就是说(t + s).indexOf(s) >= 0) 则s和t为回环变位。这个方法简直太有趣了。同理,我们可以将indexOf换成contains方法,原理是一样的,也就是方法三。

      参考答案

      /**
       * @description:
       * @author: ZhangJia
       * @create: 2018-08-07 17:05
       **/
      public class Six {
          public static void main(String[] args) {
              String s = "ACTGACG";
              String t = "ACGACTR";
      //        String t = "TGACGAC";
      
              System.out.println(isCircularRotation(s, t));
              System.out.println(isCircularRotation1(s, t));
              System.out.println(isCircularRotation2(s, t));
              System.out.println(isCircularRotation3(s, t));
      
          }
      
          /**
           * @description: 依次遍历法1
           * @param: s 字符串s
           * @param: t 字符串t
           * @return: s 和 t 是否互为回环变位
           */
      
          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;
          }
      
          /**
           * @description: 依次遍历法2
           * @param: s 字符串s
           * @param: t 字符串t
           * @return: s 和 t 是否互为回环变位
           */
      
          public static boolean isCircularRotation1(String s, String t) {
              if (s.length() != t.length()) return false;
      
              for (int i = 0, len = t.length(); i < len; i++) {
                  if (s.equals(t)) return true;
                  s = s.substring(1) + s.charAt(0);
              }
      
              return false;
          }
      
      
          /**
           * @description: indexof方法
           * @param: s 字符串s
           * @param: t 字符串t
           * @return: s 和 t 是否互为回环变位
           */
          public static boolean isCircularRotation2(String s, String t) {
              return (s.length() == t.length()) && ((t + t).indexOf(s) >= 0);
          }
      
          /**
           * @description: contains方法
           * @param: s 字符串s
           * @param: t 字符串t
           * @return: s 和 t 是否互为回环变位
           */
          public static boolean isCircularRotation3(String s, String t) {
              return s.length() == t.length() && (t + t).contains(s);
          }
      
      
      }
      
      输出:
      true
      true
      true
      true

      参考资料

      [1] 简书:风亡小窝

      [2] CSDN:pomony1

    • 0
    • 0
    • 0
    • 1.4k
    • 请登录之后再进行评论

      登录
    • 做任务
    • 实时动态
    • 偏好设置
    • 返回顶部
    • 单栏布局 侧栏位置: