[论坛提问] 面试题受阻

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

jiangshicun007 · jiangshicun007

jiangshicun007 发表于 2015-12-4 18:42
String str1 = "ijsfajk";
String str2 = "qhsfqal";
String str = "";

主要是考察你对双重循环的掌握程度

jiangshicun007 · jiangshicun007

String str1 = "ijsfajk";
String str2 = "qhsfqal";
String str = "";
TreeMap<Integer,String > map = new TreeMap<>();
ArrayList<Integer>list=new ArrayList<>();
for (int i = 0; i < str2.length(); i++) {
for (int j = i; j < str2.length(); j++) {
str = str2.substring(i, j + 1);
if (str1.contains(str)) {
map.put(str.length(), str);
}
}
}
for (int key : map.keySet()) {
list.add(key);
}
Collections.sort(list);
list.get(list.size()-1);
map.get(list.get(list.size()-1));
System.out.println(map.get(list.get(list.size()-1)));

乌鲁特 · 乌鲁特

哎，看书去了，T^T

许鹏飞 · 许鹏飞

找出字符串最小的那个定义成min最大的定义成max,然后对min进行截取,与max进行比较,直到相同就为最大公约数,

星晴。 · 星晴。

这个题目不错，记住了

sun4w · sun4w

这个很厉害要学习一下哈哈

yubail · yubail

来顶一下

Camwly · Camwly

好多大神啊

StringBOX · StringBOX

看着很难。。。。

牛德阳 · 牛德阳

一道想不出来不影响很大吧

lts0616 · lts0616

好吧看来自己真的得在多努力了

xiaolongwang · xiaolongwang

受18楼启发。完善后的代码如下
package cn.itcast_01;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;

/*
* 思路：
* A:将小串转换成char数组
* B:使用String构造方法构造子串（公约数）（可以使用长度参数来构造子字符串）
* C:在大串中查找子串的索引
* D:不存在，索引返回-1，存在返回真实索引
* E:将子串去重复、按长度从大到小存储在TreeSet集合中
* F:将子串的长度存储在ArrayList集合中，之后对集合进行去重复和排序
* G:获取ArrayList集合最大索引处的值，即为最大公约数的长度，按长度在TreeSet集合中找出最大公约数
* 最大公约数：opfhapio 和 opfhapii
*/
public class FuxiDemo {

public static void main(String[] args) {
String maxStr = "dhfsdhifaospdifahfsdiopfhapioddhfsdhifaospdifahfsdiopfhapiid";
String minStr = "sdhfopfhapioassdhfopfhapiias";
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;
}

// 这个集合用来存储所有公约数
TreeSet<String> ts = new TreeSet<String>(new Comparator<String>() {
public int compare(String s1, String s2) {
int num = s2.length() - s1.length();
int num2 = num == 0 ? s2.compareTo(s1) : num;
return num2;
}
});

// 这个集合用来存储公约数的长度
List<Integer> array = new ArrayList<Integer>();

char[] chs = minS.toCharArray();
// 第一个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) {
ts.add(temp);
array.add(temp.length());
continue;
}
}
}
// 对公约数的长度去重复、排序。最后索引位置的值即为最大公约数的长度
for (int x = 0; x < array.size() - 1; x++) {
for (int y = x + 1; y < array.size(); y++) {
if (array.get(x) == array.get(y)) {
array.remove(y);
y--;
}
}
}
Collections.sort(array);

System.out.println("公约数有：");
for (String s : ts) {
System.out.println(s);
}
System.out.println("-------------------");

System.out.println("公约数的长度有：");
for (Integer i : array) {
System.out.println(i);
}
System.out.println("-------------------");

System.out.println("最大公约数有：");
for (String s : ts) {
if (s.length() == array.get(array.size() - 1)) {
System.out.println(s);
} else if (s.length() < array.get(array.size() - 1)) {
break;
}
}
}
}

yqlbd · yqlbd

package test1203;
public class Test02 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1 ="abcdef";
String s2 ="abdcd";
String s3 =method(s1,s2);
System.out.println(s3);
}
public static String method(String s1, String s2) {
// TODO Auto-generated method stub
if(s1.length()<s2.length()){
String temp = s1;
s1 = s2;
s2 = temp;
}
for(int i = 0;i<s2.length();i++){
for(int a =0,b=s2.length()-i;b<=s2.length();a++,b++){
String s3 = s2.substring(a, b);
if(s1.contains(s3))
return s3;
}
}
return null;
}
}

复制代码

Rocky_zhang · Rocky_zhang

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

kunsongjack · kunsongjack

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

bug找到的不错,受教了

零尘 · 零尘

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

xiaolongwang · xiaolongwang

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

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;
}
}
}

}
}

hbcoding · hbcoding

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

//获取两个字符串的最大公约数，比如 ijsfajk 和 qhsfqal 两个字符串的最大公约数为sf
/*
思路：1.循环遍历两个字符串中的各个字符，判断相等的字符；
2.如果两个字符相等，则判断该字符在对应字符串中位置之后的字符是否相等，
如果是，将相等的部分连接在一起组成新的字符串存储起来；
3.再次回到循环，将新生成的子串同之前获取的子串的长度进行比较，选择较长的存储。
4.循环完毕，将最终的子串返回，即为最大公约数。
*/
import java.lang.*;
public class Demo{
public static void main(String[] args){
String arr1 = "abcdefg";
String arr2 = "yuabchdef";
String max = maxString(arr1,arr2);
System.out.println(max);
}
public static String maxString(String a,String b){
String temp = ""; //临时存储所获取的子串
String tem = ""; //存储当前最大长度的子串
//双重for循环遍历两个字符串中的各个字符
for(int i = 0;i<a.length();i++){
for(int j = 0;j<b.length();j++){
int m = i;
int n = j;
//判断第一个字符是否相等
if(a.charAt(m)==b.charAt(n)){
temp = a.charAt(m)+"";
//第一个字符相等时，判断之后的字符是否相等
while(++m<a.length() && ++n<b.length()){
if(a.charAt(m)==b.charAt(n)){
temp += a.charAt(m);
}
}
//和之前获取的子串长度相比较，获取长度大的子串
if(temp.length()>tem.length())
tem = temp;
}
}
}
return tem;
}
}

复制代码

米阳SOHO · 米阳SOHO

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

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

帐号		自动登录	找回密码
密码			加入黑马

[论坛提问] 面试题受阻

32 个回复