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