周末上道小题吧anagram的 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

周末上道小题吧anagram的

周末上道小题吧anagram的# JobHunting - 待字闺中

p*22013-01-28 08:01

1 楼

anagram大家都知道怎么回事吧
给两个string，S和T
现在需要把S变成T的anagram, 可以操作的是每次把S里的一个字符替换成另外一个字符
，问最小的操作次数可以完成这个转换
如果按照最小的次数可以有多种结果，那么输出按字典顺序最小的那个

j*y2013-01-28 08:01

2 楼

不错。
S 和 T的长度要一样吧

【在 p*****2 的大作中提到】

: anagram大家都知道怎么回事吧
: 给两个string，S和T
: 现在需要把S变成T的anagram, 可以操作的是每次把S里的一个字符替换成另外一个字符
: ，问最小的操作次数可以完成这个转换
: 如果按照最小的次数可以有多种结果，那么输出按字典顺序最小的那个

p*22013-01-28 08:01

3 楼

一样的。

【在 j*****y 的大作中提到】

: 不错。
: S 和 T的长度要一样吧

w*x2013-01-28 08:01

4 楼

需要转换多少次好求，主要是最小的那个

【在 p*****2 的大作中提到】

:
: 一样的。

t*n2013-01-28 08:01

5 楼

有没有要求每一步中间过程必须是单词？不要求的话直接统计字母种类个数就可得到需
要转换的个数，然后从头到尾分配就好了。如果要求的话dfs搜索好说，但是如何求最
小的那个呢？

P*b2013-01-28 08:01

6 楼

这个就是bfs吧。

【在 p*****2 的大作中提到】

p*22013-01-28 08:01

7 楼

不需要是单词。

【在 t*********n 的大作中提到】

: 有没有要求每一步中间过程必须是单词？不要求的话直接统计字母种类个数就可得到需
: 要转换的个数，然后从头到尾分配就好了。如果要求的话dfs搜索好说，但是如何求最
: 小的那个呢？

p*22013-01-28 08:01

8 楼

复杂度多少？

【在 P*******b 的大作中提到】

: 这个就是bfs吧。

p*22013-01-28 08:01

9 楼

是

【在 w****x 的大作中提到】

:
: 需要转换多少次好求，主要是最小的那个

l*a2013-01-28 08:01

10 楼

没那么复杂吧

【在 P*******b 的大作中提到】

: 这个就是bfs吧。

w*x2013-01-28 08:01

11 楼

因该有某种规律，真伤脑经啊，不想了

【在 P*******b 的大作中提到】

: 这个就是bfs吧。

l*a2013-01-28 08:01

12 楼

先找出 sorted需要替换的字符
start from beginning of S
如果当前字符不在T,use the smallest character
如果当前字符在T且需要被替换(S has more than T) {
if cur char> 需要被替换的,替换当前
else { if(already has the same cur char in S as T,must update this)
替换当前
}
}

【在 l*****a 的大作中提到】

: 没那么复杂吧

b*n2013-01-28 08:01

13 楼

写了一下，run了几个test cases，可能还有什么corner case没想到，就先抛个砖吧。
string getAna(string s, string t) {
assert(s.length() == t.length());
int len = t.length();
map ms;
map mt;
for(int i=0;i++mt[t[i]];
ms[t[i]] += 0;
++ms[s[i]];
}
map::iterator it=mt.begin();
for(int i=0;iwhile(it!=mt.end() &&
it->second <= ms[it->first]) ++it;
char c = s[i];
if(mt.count(c) && mt[c]>0 &&
(mt[c] >= ms[c] || cfirst))
mt[c]--;
else {
s[i] = it->first;
it->second--;
}
ms[c]--;
}
return s;
}
Test case (Hacker cup style)
$ cat w.txt
5
a b
cba bbc
abc bbc
abbcc cbbbd
abbeecc cbbbdek
$ ./go
Case #1: b
Case #2: cbb
Case #3: bbc
Case #4: bbbcd
Case #5: bbbdeck

【在 p*****2 的大作中提到】

p*22013-01-28 08:01

14 楼

我贴一下我的
val n=S.length
val s_counts=new Array[Int](26)
val t_counts=new Array[Int](26)

0 until n foreach{i=>
s_counts(S(i)-'A')+=1
t_counts(T(i)-'A')+=1
}
var count=0

for(i0)
process(i)
out.println(count)
out.println(S.mkString)
out.close

def process(i:Int){
val next=find
val c=S(i)

if(t_counts(c-'A')==0 || nextS(i)=next
count+=1
s_counts(c-'A')-=1
s_counts(next-'A')+=1
}
else{
s_counts(c-'A')-=1
t_counts(c-'A')-=1
}
}

def find():Char={
for(i{
if(t_counts(i)>s_counts(i)) return ('A'+i).toChar;
}

return None.get
}

s*n2013-01-28 08:01

15 楼

就是edit distance。DP

【在 p*****2 的大作中提到】

l*a2013-01-28 08:01

16 楼

用得上那么高级的算法吗？
除非我的算法有什么问题？

【在 s*****n 的大作中提到】

: 就是edit distance。DP

p*22013-01-28 08:01

17 楼

感觉你的算法是对的

【在 l*****a 的大作中提到】

: 用得上那么高级的算法吗？
: 除非我的算法有什么问题？

l*a2013-01-28 08:01

18 楼

谢谢大牛点评

【在 p*****2 的大作中提到】

:
: 感觉你的算法是对的

e*e2013-01-28 08:01

19 楼

我的代码, 大牛帮忙看看.
int solution(char[] s, String t) {
Map map = new LinkedHashMap();
for( char c : Arrays.sort( t ).toCharArray() ){
if( map.containsKey( c ) )
map.put( c, map.get( c ) + 1 );
else
map.put( c, 1 );
}
int count = 0;
for( int i = 0; i < s.length; i++ ) {
char c = s[i];
if( map.containsKey( c ) ) {
if ( map.get( c ) == 1 )
map.remove( c );
else
map.put( c, map.get( c ) - 1 );
}
else{
char first = map.keySet().iterator.next();
s[i] = first;
count++;
if ( map.get( first ) == 1 )
map.remove( first );
else
map.put( first, map.get( first ) - 1 );
}
}
return count;
}

p*22013-01-28 08:01

20 楼

你可以来这里测试你的程序
http://www.codeforces.com/problemset/problem/254/C

【在 e****e 的大作中提到】

: 我的代码, 大牛帮忙看看.
: int solution(char[] s, String t) {
: Map map = new LinkedHashMap();
: for( char c : Arrays.sort( t ).toCharArray() ){
: if( map.containsKey( c ) )
: map.put( c, map.get( c ) + 1 );
: else
: map.put( c, 1 );
: }
: int count = 0;