黑马程序员技术交流社区

标题: 面试题受阻 [打印本页]

作者: 帮助信息 时间: 2015-11-30 00:51
标题: 面试题受阻
获取两个字符串的最大公约数，比如 ijsfajk 和 qhsfqal 两个字符串的最大公约数为sf。坐等大神支招

作者: wyasln 时间: 2015-11-30 08:25
感觉先拿第一个字符串的第一个字母去和第二个字符串匹配，在匹配下一个，这样持续下去，中间判断什么时候结束，什么时候跳

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

作者: 石三伢子1 时间: 2015-11-30 10:21
这个视频里有这道题的讲解，嵌套for循环解决；

作者: kunsongjack 时间: 2015-12-1 01:21

public class Demo6 {
public static void main(String[] args) {
String str1 = "sddjjfdssd";
String str2 = "askjjablafadabcdwerewrew";
searhMaxString(str1, str2);
}
public static void searhMaxString(String str1, String str2) {
String strMin ; //较长字符串
String strMax ; //较短字符串
if(str1.length() > str2.length()){
strMax = str1;
strMin = str2;
}else{
strMax = str2;
strMin = str1;
}
//每次截取的长度
out:
for(int i =strMin.length() ; i > 0 ;i--){ //从大到小取
for(int j =0; j < strMin.length() - i;j++){
String tmp = strMin.substring(j, j + i ); //依次截取不同长度不同位置的字符串
if(strMax.contains(tmp)){
System.out.println("最大的相同字符串是:" + tmp);
break out;
}
}
}
}
}

复制代码

作者: kunsongjack 时间: 2015-12-1 01:23
其实没什么难度啦,就是把最小的字符串挑出来,然后截取所有长度的字符串,长度从大到小排列,然后跟长字符串进行比较即可.

作者: 孙志明 时间: 2015-12-1 14:24
好厉害，牛人多

作者: 传奇查 时间: 2015-12-1 15:22
将两个字符串变成Char数组存入ArrayList中,
for循环嵌套,外层循环变量控制数组1的元素,
内层循环控制数组2的元素,
当两个元素相等时,存入数组3
把数组3遍历出来就~噢了~

作者: hbcoding 时间: 2015-12-1 15:54
这个是面试题？

作者: 帮助信息 时间: 2015-12-1 16:52

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

dui ,.,w 我遇到。。

作者: Little_jie 时间: 2015-12-1 17:19
学习了,得加油学习基础了

作者: hbcoding 时间: 2015-12-1 20:12

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

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

作者: hrfhwy 时间: 2015-12-1 20:43
毕老师视频教程中讲的就是这个题把

作者: 米阳SOHO 时间: 2015-12-1 21:37
这个字符串最大公约数怎么定义？是必须连续的吗！？

作者: 米阳SOHO 时间: 2015-12-1 21:49

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

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

作者: hbcoding 时间: 2015-12-2 10:11
这是我的代码，与楼上的解决思路略有不同：

//获取两个字符串的最大公约数，比如 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;
}
}

复制代码

作者: xiaolongwang 时间: 2015-12-2 11:14
受上边两位的启发做出来的，不同的地方是使用的数组和索引

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

}
}

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

作者: kunsongjack 时间: 2015-12-3 00:08

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

bug找到的不错,受教了

作者: Rocky_zhang 时间: 2015-12-3 14:51
要是在面试中，有时间限制，再加上气氛的不同，怕一下想不到。

作者: yqlbd 时间: 2015-12-3 15:13

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

复制代码

作者: xiaolongwang 时间: 2015-12-3 17:31
受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;
}
}
}
}

作者: lts0616 时间: 2015-12-3 20:19
好吧看来自己真的得在多努力了

作者: 牛德阳 时间: 2015-12-3 21:23
一道想不出来不影响很大吧

作者: StringBOX 时间: 2015-12-3 21:54
看着很难。。。。

作者: Camwly 时间: 2015-12-3 23:16
好多大神啊

作者: yubail 时间: 2015-12-3 23:20
来顶一下

作者: sun4w 时间: 2015-12-4 09:21
这个很厉害要学习一下哈哈

作者: 星晴。 时间: 2015-12-4 12:02
这个题目不错，记住了

作者: 许鹏飞 时间: 2015-12-4 12:24
找出字符串最小的那个定义成min最大的定义成max,然后对min进行截取,与max进行比较,直到相同就为最大公约数,

作者: 乌鲁特 时间: 2015-12-4 12:47
哎，看书去了，T^T

作者: jiangshicun007 时间: 2015-12-4 18:42
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)));

作者: jiangshicun007 时间: 2015-12-4 18:44

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

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

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

黑马程序员IT技术论坛 X3.2