黑马程序员技术交流社区

标题: 你能想到多少种算法？ [打印本页]
作者: 党巾水    时间: 2012-7-23 11:32
标题: 你能想到多少种算法？
本帖最后由 刘馨琪 于 2012-8-7 14:44 编辑

有字符串qwe1,qwe2。qwe1较短,qwe2较长,qwe1中的字母都在qwe2中出现了吗?

这个题不难，但是你能想到多少种算法？这是一个锻炼思路的机会，方法至少有3个。
作者: 梁小波    时间: 2012-7-23 11:49
这个是字符串检索的题，我记得以前做过
1.传统的做法：str1和str2的首字母比较，相同的话会比较第二个字母，直到最后，不同的话前面前面比较无效回头比较。
2.就是算法书上的经典的kmp算法了；你要分析str1（短的字符串）的字母出现情况，找到一个可返回的序列标记也就是一个数组。这样会高效一点，因为省去了重新回头比较；
3.貌似应该叫kd吧，记得在一本书上见过，是kmp的加强；原理好像还是字符串的正序反序比较，当时看太难，就没写代码；
貌似都是前人的算法，我记得当年就自己想出了第一种；
lz应该申请滔哥加分，这样大家写代码，积极性就高了！{:soso_e113:}
回去看一下kd。。。。
作者: 党巾水    时间: 2012-7-23 12:02
梁小波 发表于 2012-7-23 11:49
这个是字符串检索的题，我记得以前做过
1.传统的做法：str1和str2的首字母比较，相同的话会比较第二个字母 ...

除了这几个，还有别的算法。哈哈！找滔哥要分，就在这里要吧~不一定滔哥加分，哈哈，哪个版主在线啊？我响应号召在要分考试啊！
作者: 李伟    时间: 2012-7-23 12:36
//先使qwe1变成数组chs，然后遍历数组中的每一个字符，判断qwe2是否包含每一个字符，如果都包含，说明qwe1中的字母都在qwe2中出现了。
package cn.itcast.test;

public class StringDemo
{
        public static void main(String[] args)
        {
                String qwe1="oabcm";
                String qwe2="dbekamopcs";
                char[] chs=qwe1.toCharArray();
                for(int i=0;i<chs.length;i++)
                {
                        if(!qwe2.contains(chs+""))
                        {
                                System.out.println("no contains");
                            break;
                        }
                        if(i==chs.length-1)
                                System.out.println("contains");
                }
        }
}
作者: 李伟    时间: 2012-7-23 12:38
                       if(!qwe2.contains(chs[i]+""))
                        {
                                System.out.println("no contains");
                            break;
                        }
作者: 陈少文    时间: 2012-7-23 18:21
本帖最后由 陈少文 于 2012-7-23 18:30 编辑

方法1：

/*用indexOf函数
* 返回第一次出现的指定子字符串在此字符串中的索引。
*
*
* */
public class Demo1 {

        public static void main(String[] args) {
                String a = "abcdefg";
                String b = "abc";

                System.out.println(a.indexOf(b));
        }

}



方法2：

/*用到contains
*当且仅当此字符串包含 char 值的指定序列时，才返回 true。
*
*/

public class Demo2 {
        public static void main(String[] args) {
                String a = "abcdefg";
                String b = "abc";

                System.out.println(a.contains(b));

        }
}






方法3
  1. /*
  2. * 思路：把字符串a,和字符串b
  3. * 转换为字符数组
  4. * 然后把b字符数组的每一个元素在字符数组a中查找，并打印
  5. * 角标
  6. * 如果角标值为递增，说明字符串a,包含字符串b
  7. *
  8. *
  9. * */
  10. public class Demo3 {
  11. public static void main(String[] args)
  12. {
  13. String a= "abcdefg";
  14. String b= "abc";
  15. char[] chb = b.toCharArray();

  17. char[] cha = a.toCharArray();
  18. for(int i = 0;i<a.length();i++)
  19. {
  20. if(chb[0]==cha[i])
  21. {
  22. System.out.println(i);

  24. }
  25. if(chb[1]==cha[i])
  26. {
  27. System.out.println(i);

  29. }
  30. if(chb[2]==cha[i])
  31. {
  32. System.out.println(i);

  34. }

  36. }

  38. }

  40. }
复制代码


方法4：
  1. /*
  2. * 思路：字符串b,转为字符串数组。用循环，依次递增
  3. * 得到一个字符串，然后判断字符串a是否包含字符串b
  4. *
  5. * */

  7. public class Demo4 {
  8. public static void main(String[] args) {
  9. String a = "abcdefg";
  10. String b = "abc";

  12. char[] chb=b.toCharArray();
  13. for (int i = 0; i < chb.length; i++) {

  15. if (a.contains(chb[i]+""))
  16. {
  17. System.out.println("a包含b");
  18. break;
  19. }
  20. }

  22. }

  24. }
复制代码
作者: 黑马黄宏强    时间: 2012-7-23 22:30
思路：把两个字符串都都转换成char 数组，然后使用第一个字符串数组中的每个字符去跟第二个字符串的数组的每个元素对比，
找到了再拿第一个字符串的第二个元素去跟第二个数组对比，以此类推，如果其中有一次未找到直接返回false，如果都找到了返回true,
代码如下：
class EqualsTesl {
        public static void main (String [] args) {
                String s1 ="asd";
                String s2 = "asdgh";

                System.out.println(equals(s1,s2));
        }
       
        public static boolean equals(String s1, String s2) {
                char [] s1Char = new char[s1.length()];
                char [] s2Char = new char[s2.length()];
                for (int i = 0; i < s1.length(); i++) {
                        s1Char[i] = s1.charAt(i);
                }
                for (int i = 0; i < s2.length(); i++) {
                        s2Char[i] = s2.charAt(i);
                }
                for(int i = 0; i<s1Char.length; i++) {
                        for(int j = 0; j<s2Char.length; j++) {
                                if(!(s1Char[i]==s2Char[j])){
                                        if(j==(s2Char.length-1)) {
                                        return false;
                                        }
                                        continue;
                                }else{
                                        break;
                                }
                        }
                }
                return true;
        }
}

运行结果为：true



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2