获取两个字符串的最大公约数，比如 ijsfajk  和  qhsfqal 两个字符串的最大公约数为sf。  坐等大神支招

感觉先拿第一个字符串的第一个字母去和第二个字符串匹配，在匹配下一个，这样持续下去，中间判断什么时候结束，什么时候 跳

个人感觉大体思路是：
先将字符串转换成char数组
这样就可以使用循环控制一次比较的元素是一个、两个或者三个。
然后取数组元素的哈希码（如果一次比较两个元素，则哈希吗相加）进行比较
哈希吗相同则输出对应的元素
最后输出的就是最大公约数

这个视频里有这道题的讲解，嵌套for循环解决；

1. 
   
2. public class Demo6 {
   
3.         public static void main(String[] args) {
   
4.                 String str1 = "sddjjfdssd";
   
5.                 String str2 = "askjjablafadabcdwerewrew";
   
6.                
   
7.                 searhMaxString(str1, str2);
   
8.                
   
9.         }
   
10. 
    
11.         public static void searhMaxString(String str1, String str2) {
    
12.                 String strMin ;        //较长字符串
    
13.                 String strMax ;        //较短字符串
    
14.                
    
15.                 if(str1.length() > str2.length()){
    
16.                         strMax = str1;
    
17.                         strMin = str2;
    
18.                 }else{
    
19.                         strMax = str2;
    
20.                         strMin = str1;
    
21.                 }
    
22.                
    
23.                
    
24.                 //每次截取的长度
    
25.                 out:
    
26.                 for(int i =strMin.length() ; i > 0 ;i--){                //从大到小取
    
27.                         for(int j =0; j < strMin.length() - i;j++){
    
28.                                 String tmp = strMin.substring(j, j + i );                //依次截取不同长度不同位置的字符串
    
29.                                 if(strMax.contains(tmp)){
    
30.                                         System.out.println("最大的相同字符串是:" + tmp);
    
31.                                         break out;
    
32.                                 }
    
33.                         }
    
34.                 }
    
35.         }
    
36. }
    

复制代码

其实没什么难度啦,就是把最小的字符串挑出来,然后截取所有长度的字符串,长度从大到小排列,然后跟长字符串进行比较即可.

好厉害，牛人多

将两个字符串变成Char数组存入ArrayList中,
for循环嵌套,外层循环变量控制数组1的元素,
内层循环控制数组2的元素,
当两个元素相等时,存入数组3
把数组3遍历出来就~噢了~

这个是面试题？

hbcoding 发表于 2015-12-1 15:54
这个是面试题？

dui ,.,w 我遇到。。

学习了,得加油学习基础了

帮助信息 发表于 2015-12-1 16:52
dui ,.,w 我遇到。。

我自己试着做了一下，用了半个小时才做出来。感觉要是在面试中，加上紧张，肯定会花更长时间，还是挺难的。那你最后的面试分数是多少？

毕老师视频教程中讲的就是这个题把

这个字符串最大公约数怎么定义？是必须连续的吗！？

kunsongjack 发表于 2015-12-1 01:21

想问，如果我把那两个jj分开，为什么会只打印s,这样是不是说最大公约数就是s了？这不科学啊。我还是不太明白这里的最大公约数怎么定义，不是数学里的那么明确，求指教

这是我的代码，与楼上的解决思路略有不同：

1. //获取两个字符串的最大公约数，比如 ijsfajk 和 qhsfqal 两个字符串的最大公约数为sf
   
2. /*
   
3.   思路：1.循环遍历两个字符串中的各个字符，判断相等的字符；
   
4.         2.如果两个字符相等，则判断该字符在对应字符串中位置之后的字符是否相等，
   
5.                   如果是，将相等的部分连接在一起组成新的字符串存储起来；
   
6.                 3.再次回到循环，将新生成的子串同之前获取的子串的长度进行比较，选择较长的存储。
   
7.                 4.循环完毕，将最终的子串返回，即为最大公约数。
   
8. */
   
9. import java.lang.*;
   
10. public class Demo{
    
11.         public static void main(String[] args){
    
12.                 String arr1 = "abcdefg";
    
13.                 String arr2 = "yuabchdef";
    
14.                 String max = maxString(arr1,arr2);
    
15.                 System.out.println(max);
    
16.         }
    
17.         public static String maxString(String a,String b){
    
18.                 String temp = "";    //临时存储所获取的子串
    
19.                 String tem = "";     //存储当前最大长度的子串
    
20.                 //双重for循环遍历两个字符串中的各个字符
    
21.                 for(int i = 0;i<a.length();i++){
    
22.                         for(int j = 0;j<b.length();j++){
    
23.                         int m = i;
    
24.                         int n = j;
    
25.                         //判断第一个字符是否相等
    
26.                         if(a.charAt(m)==b.charAt(n)){
    
27.                                 temp = a.charAt(m)+"";
    
28.                                 //第一个字符相等时，判断之后的字符是否相等
    
29.                                 while(++m<a.length() && ++n<b.length()){
    
30.                                 if(a.charAt(m)==b.charAt(n)){
    
31.                                         temp += a.charAt(m);
    
32.                                 }
    
33.                                 }
    
34.                                 //和之前获取的子串长度相比较，获取长度大的子串
    
35.                                 if(temp.length()>tem.length())
    
36.                                         tem = temp;
    
37. 
    
38.                         }
    
39.                 }
    
40.                 }
    
41.                 return tem;
    
42.         }
    
43.        
    
44. }

复制代码

受上边两位的启发做出来的，不同的地方是使用的数组和索引

package cn.itcast_01;

/*
* 思路：
*                 A:将小串转换成char数组
*                 B:使用String构造方法构造子串（最大公约数）（可以使用长度参数来构造子字符串）
*                 C:在大串中查找子串的索引
*                 D:不存在，索引返回-1，存在返回真实索引
* 最大公约数：opfhapio
*/
public class FuxiDemo {

        public static void main(String[] args) {
                String maxStr = "dhfsdhifaospdifahfsdiopfhapiod";
                String minStr = "sdhfopfhapioas";
                method(maxStr, minStr);
        }

        private static void method(String s1, String s2) {
                String maxS;
                String minS;
               
                if (s1.length() > s2.length()) {
                        maxS = s1;
                        minS = s2;
                } else {
                        maxS = s2;
                        minS = s1;
                }
               
                char[] chs = minS.toCharArray();
               
                other:
                // 第一个for循环用于控制截取的子字符串长度
                for (int x = chs.length - 1; x > 0; x--) {
                        // 用于控制截取的字符串
                        for (int y = 0; y + x < chs.length; y++) {
                                String temp = new String(chs, y, x);
                                // 子串与大串比较，返回索引，判断索引是否为-1，不为-1则存在
                                int index = maxS.indexOf(temp);
                                if (index != -1) {
                                        System.out.println(temp);
                                        break other;
                                }
                        }
                }

        }
}

补充:如果这两个字符串假如是:
aabbcc
adbdc
那么最大的相同子字符串是三个:
a,b,c
所以建议用集合接收子字符串,然后根据长度排序.取出和最后一个相同长度(包括最后一个元素)的元素.打印

零尘 发表于 2015-12-2 19:05
补充:如果这两个字符串假如是:
aabbcc
adbdc

bug找到的不错,受教了

要是在面试中，有时间限制，再加上气氛的不同，怕一下想不到。