您的位置：程序门 -> .net技术 -> c#

昨天微软的一个笔试题，大家讨论下

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

昨天微软的一个笔试题，大家讨论下[已结贴,结贴人:questionofms]

发表于：2007-03-23 10:19:50 楼主

有字符串如 "abcd,bdac,drf,frd,cadb,caadb,xb ",要将其中由相同字符组成的词归在一起，如果没有和其由相同字符组成的词则去掉，如上的结果为：
组1：abcd,bdac,cadb
组2: drf,frd
另外，caadb和xb去掉
请写出代码（c#)，思路和选择所使用的数据结构的原因

发表于：2007-03-23 10:22:301楼得分:2

等高人来解答

发表于：2007-03-23 10:22:562楼得分:2

等待..

发表于：2007-03-23 10:38:253楼得分:2

等待

发表于：2007-03-23 10:41:284楼得分:3

思路:
1.将字符串转换为asicc值.
2.比较asicc值，相通的则为解，反之则去除掉.

部分代码:

string str = "abcd,bdac,drf,frd,cadb,caadb,xb ";
arraylist arraylist=new arraylist（);
long lg;
string[] arry = str.split（ ', ');
foreach （string value in arry)
{
lg = 0;
foreach （char ch in value)
{
lg += （int)ch;
}
arraylist.add（lg);
}
下略.
..........................
..........................

发表于：2007-03-23 10:46:185楼得分:2

455454

发表于：2007-03-23 10:46:586楼得分:2

这样也可以。。。。。。

发表于：2007-03-23 10:48:577楼得分:2

运行完上面代码,你看看arraylist里的值就知道了，刚试了中文也没影响.

发表于：2007-03-23 10:49:148楼得分:5

不知道对不对,说说我的思路吧

分组replit
计算该组内单个字符的ascii码值,
参考http://www.kkun.com.cn/group/%e8%ae%a1%e7%ae%97%e6%9c%ba%e6%9f%a5%e8%af%a2/asciifull.gif
计算该组所有单个字符的ascii码值的和,
与其它组比较和是不是相等,再比较长度是否相等,两个条件满足刚归在一起

发表于：2007-03-23 10:50:269楼得分:2

回贴慢了一拍#75,
刚好正在看,c#生成汉字验证码这块呢

发表于：2007-03-23 10:51:3110楼得分:0

恩，关键思路其实都差不多
可以个人感觉要完整的写出来，所用的算法和数据结构还是有讲究
昨天我做的也很不好，修改完后我会发上我的代码，请大家指导下

发表于：2007-03-23 10:52:0111楼得分:2

厉害

发表于：2007-03-23 10:52:0512楼得分:2

按照楼上说法,ad 和 bc 他们的ascii值可是相等的,另外ac 和bb也是相等的,

发表于：2007-03-23 11:00:2013楼得分:2

我的思路是,分组排序,然后比较字符串是否相等.

发表于：2007-03-23 11:02:4214楼得分:2

ascii值不好，a-z按1-26取值
（1)按字符串长度,长度相同分一组
（2)字符串按a-z转换为1-26值,再相加

发表于：2007-03-23 11:04:1315楼得分:2

感觉两个字符的比较比较复杂,需要考虑几点
1) string长度,这个最简单,也效率最高
2) ascii值的和,ad 和 bc的asc值的和是一致的,ac和bb也是一样,但这不符合要求
3) 还要考虑aab 和abb的情况,他们都包含a和b, 但是却是不同的
综上,我的几个想法是
1) 把每个string都按照其字符的asc值排序,然后比较排序后的string是否完全一致
2) 逐个字符查看是否在另外一个string中,同时还要考虑存在的数目.

自我感觉方法比较苯,呵呵.学习中.....

发表于：2007-03-23 11:04:2016楼得分:0

ascii相加是不行的

skywind_jk（天风)：
按照楼上说法,ad 和 bc 他们的ascii值可是相等的,另外ac 和bb也是相等的,

发表于：2007-03-23 11:05:0717楼得分:0

我想的是把每个词转化为char数组，然后做个sort，再比较

发表于：2007-03-23 11:05:1318楼得分:2

个人思路
1、用split分割 "abcd,bdac,drf,frd,cadb,caadb,xb " 得到数组arr1；
2、在循环把arr1中每个字符串进行排序；（排序算法是影响效率得关键）
3、定义一个sortedlist，循环把arr1中得字符串加进去（进去得时候判断是否已经存在）

发表于：2007-03-23 11:06:3019楼得分:0

zine_alone（*小飞*) （ ) 信誉：100 blog 2007-03-23 10:41:28 得分: 0

思路:
1.将字符串转换为asicc值.
2.比较asicc值，相通的则为解，反之则去除掉.

部分代码:

string str = "abcd,bdac,drf,frd,cadb,caadb,xb ";
arraylist arraylist=new arraylist（);
long lg;
string[] arry = str.split（ ', ');
foreach （string value in arry)
{
lg = 0;
foreach （char ch in value)
{
lg += （int)ch;
}
arraylist.add（lg);
}
下略.
..........................
..........................
------------------------------------------
不同意使用 arraylist 。应该用最基本的数组。

发表于：2007-03-23 11:07:0320楼得分:2

晕我理解错了

发表于：2007-03-23 11:12:4621楼得分:0

果然我昨天的代码有问题
我想把 "abcd,bdac,drf,frd,cadb,caadb,xb "转化为arraylist后做判断，并把判断完的删除
可是删除后报错“system.notsupportedexception ”
即：如果arraylist为只读，或者有固定大小将会引发此异常。

之前代码是：
string input = "abcd,bdac,drf,frd,cadb,caadb,xb ";
string[] s = input.split（ ', ');
arraylist al1 = arraylist.adapter（s);
al1.removeat（0);

要如何让al1可删除呢？

发表于：2007-03-23 11:13:0522楼得分:20

一段code,欢迎指正.
class program
{
static void main（string[] args)
{
list <string> list = start（ "abcd,bdac,drf,frd,cadb,caadb,xb,abb,baa "); // abb,baa是我测试加的

foreach （string str in list) // 输出结果
console.writeline（str);
}

static list <string> start（string oristring)
{
string[] orilist = oristring.split（ ', '); // 原始记录，分成 []
list <string> resultlist = new list <string> （); // 记录结果
bool[] flags = new bool[orilist.length]; // 用于记录比较状态
for （int i = 0; i < flags.length; i++)
flags[i] = false;

for （int i = 0; i < orilist.length; i++)
{
if（flags[i])
continue;

string result = " "; // 存放结果（单条）

// 比较后面的是否同当前（i) “相同”
for （int j = i + 1; j < orilist.length; j++)
{
if （flags[j])
continue;

if （rightop（orilist[i], orilist[j]))
{
result += ", " + orilist[j];
flags[j] = true;
}
}

if （result != " ")
{
flags[i] = true;
resultlist.add（orilist[i] + result);
}
}
return resultlist;
}
// 字符比较
static bool rightop（string str1, string str2)
{
// 字串长度判断
if （str1.length != str2.length)
return false;

foreach （char ch in str1.tochararray（))
{
// 是否包含字符的判断
if （str2.indexof（ch) < 0)
return false;

// 判断该字符个数是否一致。过滤如abb 和aab这种情况
if （str1.replace（ch.tostring（), " ").length != str2.replace（ch.tostring（), " ").length)
return false;
}

// compare one by one
return true;
}
}

发表于：2007-03-23 11:15:1623楼得分:18

static void main（string[] args)
{
string source = "abcd,bdac,drf,frd,cadb,caadb,xb ";
string[] arraysource = source.split（ ', ');
getmaxmin（arraysource);
console.read（);
}

//public static string[][] getfirttime（string[] source)
//{
// // string[][] temp = new string[source.length,3];
//}

/// <summary>
///
/// </summary>
/// <param name= "source "> </param>
public static void getmaxmin（string[] source)
{
//第一轮判断
//string[] needtemp = new string[source.length];
string _strtemp;
for （int i = 0; i < source.length; i++)
{
_strtemp = source[i];
if （source[i] == " ")
continue;
console.write（ "\n "+ _strtemp + "\t ");
for （int n = i+1; n < source.length; n++)
{
if （_strtemp.length == source[n].length)
{
if （orderword（_strtemp) == orderword（source[n]))
{
console.write（source[n] + "\t ");
source[n] = " ";
}
}
}
}

}

/// <summary>
/// order word
/// </summary>
/// <param name= "_source "> </param>
/// <returns> </returns>
public static string orderword（string _source)
{
char[] temp = _source.tochararray（);
array.sort（temp);
return temp.tostring（);
}

发表于：2007-03-23 11:16:5124楼得分:2

也 only顶一下

发表于：2007-03-23 11:17:4725楼得分:18

思路：
选择字符串和字符串列表
将单词排序作为关键字放在字符串的首部
判断一个单词是否列表中，就是将其排序后对列表的首部进行比较
中途结果如下
abcd=abcd,bdac,cadb
dfr=drf,frd
aabcd=caadb
bx=xb
其中没有出现“，”号说明没有重复
------------
string vtext = @ "abcd,bdac,drf,frd,cadb,caadb,xb ";
list <string> vresults = new list <string> （);
string[] vwords = vtext.split（ ", ".tochararray（),
stringsplitoptions.removeemptyentries);
foreach （string vword in vwords)
{
char[] vchars = vword.toupper（).tochararray（);
array.sort（vchars);
string t = new string（vchars);
bool vexists = false;
for （int i = 0; i < vresults.count; i++)
if （t + "= " == vresults[i].substring（0, t.length + 1))
{
vresults[i] += ", " + vword;
vexists = true;
break;
}
if （!vexists) vresults.add（t + "= " + vword);
}
int vgroup = 0;
foreach （string vresult in vresults)
{
if （vresult.indexof（ ', ') > 0)
{
vgroup++;
textbox1.appendtext（string.format（ "组{0}: {1}\r\n ",
vgroup, vresult.substring（vresult.indexof（ '= ') + 1)));
}
}
-----
组1: abcd,bdac,cadb
组2: drf,frd

发表于：2007-03-23 11:19:3826楼得分:0

大家好厉害，挨个学习先。。。。

发表于：2007-03-23 11:23:2027楼得分:2

呵呵
会写和写好的对比了

发表于：2007-03-23 11:24:1828楼得分:2

我的思路是,分组排序,然后比较字符串是否相等.
ty

发表于：2007-03-23 11:28:1629楼得分:0

哇，skywind_jk（天风)的这个算法不错
static bool rightop（string str1, string str2)
{
// 字串长度判断
if （str1.length != str2.length)
return false;

foreach （char ch in str1.tochararray（))
{
// 是否包含字符的判断
if （str2.indexof（ch) < 0)
return false;

// 判断该字符个数是否一致。过滤如abb 和aab这种情况
if （str1.replace（ch.tostring（), " ").length != str2.replace（ch.tostring（), " ").length)
return false;
}

// compare one by one
return true;
}

发表于：2007-03-23 11:33:1430楼得分:0

对，csshooter（sharp shooter) 的sort（）后再tostring（)再判断是方便多了
public static string orderword（string _source)
{
char[] temp = _source.tochararray（);
array.sort（temp);
return temp.tostring（);
}

发表于：2007-03-23 11:35:3131楼得分:0

不过csshooter（sharp shooter)没把孤儿词给去掉。。。。。。

发表于：2007-03-23 11:37:2432楼得分:2

sort 一下
就出来了

发表于：2007-03-23 11:45:2233楼得分:0

谢谢大家，结帖给分

发表于：2007-03-23 12:51:0534楼得分:0

学习....

发表于：2007-03-23 13:19:3935楼得分:0

/// <summary>
/// 比较两个字符串是否由相同字符组成
/// </summary>
/// <param name= "one "> </param>
/// <param name= "two "> </param>
/// <returns> </returns>
public static bool issamechars（string one, string two)
{
if （one == null ¦ ¦ two == null ¦ ¦ one.length != two.length)
{
return false;
}
char[] chartwo = two.tochararray（);
int len =one.length-1;
for （; len > = 0; len--)
{
int index = chartwo.length - 1;
for （; index > = 0; index--)
{
if （one[len] == chartwo[index])
{
chartwo[index] = '\u0000 ';
break;
}
if （index == 0)
{
return false;
}
}
}
if （len == -1)
{
return true;
}
return false;
}

发表于：2007-03-23 13:22:1336楼得分:0

学习

发表于：2007-03-23 13:22:4737楼得分:0

这个借鉴了楼上各位兄弟的做法，写了一个，写的很烂，结果好像可以的。
/////////////////////////////////////////
using system;
using system.collections.generic;
using system.text;

namespace consoleapplication2
{
class program
{
static void main（string[] args)
{
string strtest = "abcd,bdac,drf,frd,cadb,caadb,xb ";
string[][] strresult = null;
strresult = getresult（strtest);

for （int i=0;i <strresult.length;i++)
{
if （strresult[i].length > 1)
{
console.write（ "组 " + （i+1).tostring（) + ": ");

for （int j = 0; j < strresult[i].length; j++)
{
console.write（strresult[i][j]);
console.write（ " ");
}
console.write（ "\r\n ");
}
}
console.read（);
}

static string[][] getresult（string strvalue)
{
string[] strtmp = null;
groupitem[] gi = null;
list <string> [] strresult = null;
int i = 0,j = 0;
int icount = 0, jcount = 0;

strtmp = strvalue.split（new char[] { ', ' });
gi = new groupitem[strtmp.length];
strresult = new list <string> [strtmp.length];

for （i = 0; i < strtmp.length; i++)
{
gi[i].groupvalue = strtmp[i];
gi[i].hasfound = false;
}
for （i = 0; i < gi.length; i++)
{
jcount = 0;
if （!gi[i].hasfound)
{
gi[i].hasfound = true;
strresult[icount] = new list <string> （);
strresult[icount].add（gi[i].groupvalue);
for （j = 1; j < gi.length; j++)
{
if （!gi[j].hasfound)
{
if （stringequals（gi[i].groupvalue, gi[j].groupvalue))
{
strresult[icount].add（gi[j].groupvalue);
gi[j].hasfound = true;
}
}
}
icount++;
}
}

string[][] strret = new string[icount][];
for （i = 0; i < icount; i++)
{
strret[i] = new string[strresult[i].count];
for （j = 0; j < strresult[i].count; j++)
{
strret[i][j] = strresult[i][j];
}
}
return strret;
}

static bool stringequals（string str1, string str2)
{
if （str1.length != str2.length)
return false;
foreach （char ch in str1.tochararray（))
{
if （str2.indexof（ch) == -1)
return false;
if （（str1.replace（ch.tostring（), " ").length) != （str2.replace（ch.tostring（), " ").length))
return false;
}
return true;
}

}
struct groupitem
{
public string groupvalue;
public bool hasfound;
}
}

发表于：2007-03-23 13:25:1438楼得分:0

questionofms（) （一级（初级)) 信誉：100 2007-3-23 11:05:07 得分:0

我想的是把每个词转化为char数组，然后做个sort，再比较

感觉这个方法比较好，鼓掌

发表于：2007-03-23 13:28:3439楼得分:0

提一个算法：
给每个字母，分配一个质数，如给a分配2，b分配3，...
然后对每个字符串计算乘积，如ab为6。如果两个字符串的乘积相等
则表示他们是由相同的字母组成的。因为一个数的质因数分解是唯
一的。
这个算法的缺点是，乘积容易溢出。

发表于：2007-03-23 14:47:4040楼得分:0

shzues（) （ ) 信誉：100 blog 2007-03-23 13:28:34 得分: 0

提一个算法：
给每个字母，分配一个质数，如给a分配2，b分配3，...
然后对每个字符串计算乘积，如ab为6。如果两个字符串的乘积相等
则表示他们是由相同的字母组成的。因为一个数的质因数分解是唯
一的。
这个算法的缺点是，乘积容易溢出。

有道理!!! 我想这是微软想要的答案.
关于溢出,1-100之间有25个素数: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
另外,101是第26个.如果字符串较短就没有问题.

发表于：2007-03-23 15:01:2741楼得分:0

回楼上
对于可能溢出的算法
很容易被ms fail掉的
个人感觉csshooter（sharp shooter) 的sort（）后再tostring（)再判断比较好
另外循环时skywind_jk（天风)的增加bool[]标志数组和csshooter（sharp shooter)的将判断过的词置为空字符串都比较好

发表于：2007-03-23 15:19:5942楼得分:0

可以用2的n次幂来实现啊，从a到z分别是2的0次到2的25次
即使全部相加也就2的26次-1 这个值int型都可以表示
而且分解也唯一

发表于：2007-03-23 15:24:4743楼得分:0

不过这种算法对于有重复字符来说就没有用了
所以个人感觉还是先比较长短，再对相同长短的sort后直接用字符串的比较的好

发表于：2007-03-23 15:29:1544楼得分:0

回楼上：
用幂来表示的话就不能表示多个了，比如说有两个a,2个2的0次等于一个2的一次。你怎么判断是一个b还是两个a?

发表于：2007-03-23 16:08:0245楼得分:0

整理了一下，发现受了csshooter（sharp shooter)很大影响，呵呵
-----------
static void main（string[] args)
{
string input = "abcd,bdac,drf,frd,cadb,caadb,xb ";
string[] s = input.split（ ', ');
list <string> result = new list <string> （);

for （int i = 0; i < s.length; i++)
{
string tmp = getstr（s[i]);
//如果当前词已经和之前的匹配成功（或本身为空），则跳过
if （tmp == null ¦ ¦ tmp.length == 0)
continue;
//对即将进行的寻找兄弟之旅准备行装
int len = tmp.length;
list <string> tt = new list <string> （);
tt.add（s[i]);
//循环判断在后面的词中有没有当前词的兄弟
for （int j = i + 1; j < s.length; j++)
{
if （s[j].length != len)
continue;
if （tmp != getstr（s[j]))
continue;
tt.add（s[j]);
s[j] = " ";
}
//循环完毕，如果不是孤儿词就打印出来
if （tt.count > 1)
{
foreach （string zzz in tt)
{
console.write（zzz + " ");
}
console.write（ "\r\n ");
}
}
console.readline（);
}

//将一个词做排序，如输入 "acdb "，将返回 "abcd "
static string getstr（string input)
{
char[] c = input.tochararray（);
array.sort（c);
string s = new string（c);
return s;
}

发表于：2007-03-23 17:37:1346楼得分:0

学习

发表于：2007-03-25 19:07:3947楼得分:0

有个比较简单的方法就是将
abcd,bdac,drf,frd,cadb,caadb,xb里的每个单次进行排序结果为
abcd,abcd,dfr,dfr,abcd,aabcd,bx,然后做字符串比较
不知道大家有没更简单的方法

下一篇：c# 文件下载的问题
上一篇：如何得到程序集中的类的名称,以及类的相应属性（如实现了那些接口)?

其他资讯