论坛首页 综合技术论坛

给大家出道题,算法的

浏览 32204 次
精华帖 (0) :: 良好帖 (1) :: 新手帖 (0) :: 隐藏帖 (17)
作者 正文
   发表时间:2012-02-15  
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.regex.Pattern;

public class test {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		System.out.print("Enter:");
		String str = sc.nextLine();
		
		Pattern p = Pattern.compile(",");
		String[] ss = p.split(str);
		
		boolean[] yes = new boolean[ss.length];
		for(int i = 0;i<yes.length;i++){
			yes[i] = true;
		}
		
		for(int i = 0;i<ss.length;i++){
			Set<String> set = new HashSet<String>();
			
			if(yes[i]==false){
				continue;
			}
			
			for(int j = 0;j<ss.length;j++){
				if(i!=j&&ss[i].length()==ss[j].length()&&!ss[i].equals(ss[j])&&yes[i]==true&&yes[j]==true){
					char[] ti = ss[i].toCharArray();
					char[] tj = ss[j].toCharArray();
					int acsiii = 0,acsiij = 0;
					
					for(int k = 0;k<ss[i].length();k++){
						acsiii+=ti[k];
						acsiij+=tj[k];
					}
					if(acsiii==acsiij){
						yes[j]=false;
						set.add(ss[j]);
					}
				}else{
					continue;
				}
			}
			yes[i] = false;
			System.out.println(ss[i]+"\t"+set.toString());
		}
	}
}


输出结果:
Enter:hor,jisk,kisj,ijsk,rot,roh
hor	[roh]
jisk	[ijsk, kisj]
rot	[]
0 请登录后投票
   发表时间:2012-02-15   最后修改:2012-02-15
要证明有点复杂. 当然我可以证明只有2个字母a,b的
str n = n1个a,n2个b
str m = m1个a,m2个b

n1+2 * n2= m1+2 * m2
n1+n2 = m1+m2

两式相减
=》
n2=m2.
=》n1=m1
0 请登录后投票
   发表时间:2012-02-15   最后修改:2012-02-15
求数学大神证明
0 请登录后投票
   发表时间:2012-02-15  
qseasideq 写道
求数学大神证明

证明这个没有什么太大的必要,你还是把key转为了string再去比较效率不高
key只有为数字的时候,比较的时候才有优势
0 请登录后投票
   发表时间:2012-02-15   最后修改:2012-02-15
kidding87 写道
qseasideq 写道
求数学大神证明

证明这个没有什么太大的必要,你还是把key转为了string再去比较效率不高
key只有为数字的时候,比较的时候才有优势



很明显的不严谨,sum(aab) =  sum(c)

然后呢?!   你还想怎么样?

请不要说长度

sum(aad) =  sum(bcc)

如果你想让2进制来实现,我建议用*法,   移位是最高速的,  但是26个字母,移位超过的可能性不小,

当然也不是没办法,建立新的结构,然后建立26划区域,然后移位!。。。。。。

比如说,

a,b,c,d 为一个区域,新的结构是这样的

struct letter{
    int precode;
    int code;
}   a对应的结构是a.precode = 1;  a.code = 1b.precode = 1; b.code = 2


然后建立一个算法,实现(    abcd)这样的letter[] = (bcad)的letter[](用新结构有2个好处
1.空间节省,不会实现别人的Z  2.N次方.
2.快速比,  算法快速而且算法应该是N,JAVA快速排序是nlogn);
结构建立起来了,实现应该是比较简单的,这样的轮子就造到了天上去了,    我想还是那什么,排序高速简单.
0 请登录后投票
   发表时间:2012-02-16  
这道题有那么难么?居然都想出了那么多不靠谱的解法。简单就是将单词内的字符排序之后形成新的字符串作为key,按照key分组就可以了。
简单写一下ruby代码:
%w{hat top potter pot pier ripe}.group_by {|w| w.chars.sort.join }.each{|_,group| puts group.join(" ") }  

0 请登录后投票
   发表时间:2012-02-16  
cucumber_pain 写道
kidding87 写道
qseasideq 写道
求数学大神证明

证明这个没有什么太大的必要,你还是把key转为了string再去比较效率不高
key只有为数字的时候,比较的时候才有优势



很明显的不严谨,sum(aab) =  sum(c)

然后呢?!   你还想怎么样?

请不要说长度

sum(aad) =  sum(bcc)

如果你想让2进制来实现,我建议用*法,   移位是最高速的,  但是26个字母,移位超过的可能性不小,

当然也不是没办法,建立新的结构,然后建立26划区域,然后移位!。。。。。。

比如说,

a,b,c,d 为一个区域,新的结构是这样的

struct letter{
    int precode;
    int code;
}   a对应的结构是a.precode = 1;  a.code = 1b.precode = 1; b.code = 2


然后建立一个算法,实现(    abcd)这样的letter[] = (bcad)的letter[](用新结构有2个好处
1.空间节省,不会实现别人的Z  2.N次方.
2.快速比,  算法快速而且算法应该是N,JAVA快速排序是nlogn);
结构建立起来了,实现应该是比较简单的,这样的轮子就造到了天上去了,    我想还是那什么,排序高速简单.

谢谢你指出我的错误和建议.
0 请登录后投票
   发表时间:2012-02-16  
neaudiy 写道
每个字母对应一个素数,
然后把所有单词响应的素数相乘,然后把结果做比较,结果相同的,说明这个单词和另一个单词又相同的字母


会出现两个问题:
1、先必须把相同长度的单词的归类
2、单词太长会溢出的~~~
0 请登录后投票
   发表时间:2012-02-16  
对neaudiy的想法,再加上根据字频统计进行素数分配会更好。
0 请登录后投票
   发表时间:2012-02-16  
function test(array $item)
{
	$_ret = array();
	$result = '';
	//分组
	foreach($item as $index => $split)
	{
		$splitToArray = str_split($split);		
		foreach($item as $key => $string)
		{
			if($index == $key)
			{
				$_ret[$index][] = $split;
				unset($item[$key]);
				continue;
			}
			if(array_diff($splitToArray,str_split($string))===array())
			{
				$_ret[$index][] = $string;
				unset($item[$key]);
			}
		}
	}
	//合并
	foreach($_ret as $rets)
	{
		$result .= implode(',', $rets);
		$result .= '<br>';
		$result .= "\n";
	}
	return $result;
}

0 请登录后投票
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics