• 中文
    • English
  • 注册
  • 查看作者
  • 《算法第四版》课后练习题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
  • 2.6k
  • 请登录之后再进行评论

    登录
    单栏布局 侧栏位置: