锁定老帖子 主题:给大家出道题,算法的
精华帖 (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 [] |
|
返回顶楼 | |
发表时间: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 |
|
返回顶楼 | |
发表时间:2012-02-15
最后修改:2012-02-15
求数学大神证明
|
|
返回顶楼 | |
发表时间:2012-02-15
qseasideq 写道 求数学大神证明
证明这个没有什么太大的必要,你还是把key转为了string再去比较效率不高 key只有为数字的时候,比较的时候才有优势 |
|
返回顶楼 | |
发表时间: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); 结构建立起来了,实现应该是比较简单的,这样的轮子就造到了天上去了, 我想还是那什么,排序高速简单. |
|
返回顶楼 | |
发表时间: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(" ") } |
|
返回顶楼 | |
发表时间: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); 结构建立起来了,实现应该是比较简单的,这样的轮子就造到了天上去了, 我想还是那什么,排序高速简单. 谢谢你指出我的错误和建议. |
|
返回顶楼 | |
发表时间:2012-02-16
neaudiy 写道 每个字母对应一个素数,
然后把所有单词响应的素数相乘,然后把结果做比较,结果相同的,说明这个单词和另一个单词又相同的字母 会出现两个问题: 1、先必须把相同长度的单词的归类 2、单词太长会溢出的~~~ |
|
返回顶楼 | |
发表时间:2012-02-16
对neaudiy的想法,再加上根据字频统计进行素数分配会更好。
|
|
返回顶楼 | |
发表时间: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; } |
|
返回顶楼 | |