p*****2 发帖数: 21240 | 1 anagram大家都知道怎么回事吧
给两个string,S和T
现在需要把S变成T的anagram, 可以操作的是每次把S里的一个字符替换成另外一个字符
,问最小的操作次数可以完成这个转换
如果按照最小的次数可以有多种结果,那么输出按字典顺序最小的那个 |
j*****y 发帖数: 1071 | 2 不错。
S 和 T的长度要一样吧
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : anagram大家都知道怎么回事吧 : 给两个string,S和T : 现在需要把S变成T的anagram, 可以操作的是每次把S里的一个字符替换成另外一个字符 : ,问最小的操作次数可以完成这个转换 : 如果按照最小的次数可以有多种结果,那么输出按字典顺序最小的那个
|
p*****2 发帖数: 21240 | 3
一样的。
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不错。 : S 和 T的长度要一样吧
|
w****x 发帖数: 2483 | 4
需要转换多少次好求, 主要是最小的那个
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 一样的。
|
t*********n 发帖数: 89 | 5 有没有要求每一步中间过程必须是单词?不要求的话直接统计字母种类个数就可得到需
要转换的个数,然后从头到尾分配就好了。如果要求的话dfs搜索好说,但是如何求最
小的那个呢? |
P*******b 发帖数: 1001 | 6 这个就是bfs吧。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : anagram大家都知道怎么回事吧 : 给两个string,S和T : 现在需要把S变成T的anagram, 可以操作的是每次把S里的一个字符替换成另外一个字符 : ,问最小的操作次数可以完成这个转换 : 如果按照最小的次数可以有多种结果,那么输出按字典顺序最小的那个
|
p*****2 发帖数: 21240 | 7
不需要是单词。
【在 t*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有没有要求每一步中间过程必须是单词?不要求的话直接统计字母种类个数就可得到需 : 要转换的个数,然后从头到尾分配就好了。如果要求的话dfs搜索好说,但是如何求最 : 小的那个呢?
|
p*****2 发帖数: 21240 | 8
复杂度多少?
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个就是bfs吧。
|
p*****2 发帖数: 21240 | 9
是
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 需要转换多少次好求, 主要是最小的那个
|
l*****a 发帖数: 14598 | 10 没那么复杂吧
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个就是bfs吧。
|
|
|
w****x 发帖数: 2483 | 11
因该有某种规律,真伤脑经啊,不想了
【在 P*******b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个就是bfs吧。
|
l*****a 发帖数: 14598 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没那么复杂吧
|
b*****n 发帖数: 482 | 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;i
while(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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : anagram大家都知道怎么回事吧 : 给两个string,S和T : 现在需要把S变成T的anagram, 可以操作的是每次把S里的一个字符替换成另外一个字符 : ,问最小的操作次数可以完成这个转换 : 如果按照最小的次数可以有多种结果,那么输出按字典顺序最小的那个
|
p*****2 发帖数: 21240 | 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(i<-0 until n if s_counts(S(i)-'A')-t_counts(S(i)-'A')>0)
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 || next
S(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<-0 until 26)
{
if(t_counts(i)>s_counts(i)) return ('A'+i).toChar;
}
return None.get
} |
s*****n 发帖数: 5488 | 15 就是edit distance。DP
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : anagram大家都知道怎么回事吧 : 给两个string,S和T : 现在需要把S变成T的anagram, 可以操作的是每次把S里的一个字符替换成另外一个字符 : ,问最小的操作次数可以完成这个转换 : 如果按照最小的次数可以有多种结果,那么输出按字典顺序最小的那个
|
l*****a 发帖数: 14598 | 16 用得上那么高级的算法吗?
除非我的算法有什么问题?
【在 s*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是edit distance。DP
|
p*****2 发帖数: 21240 | 17
感觉你的算法是对的
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用得上那么高级的算法吗? : 除非我的算法有什么问题?
|
l*****a 发帖数: 14598 | 18 谢谢大牛点评
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 感觉你的算法是对的
|
e****e 发帖数: 418 | 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*****2 发帖数: 21240 | 20
你可以来这里测试你的程序
http://www.codeforces.com/problemset/problem/254/C
【在 e****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的代码, 大牛帮忙看看. : 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;
|