q******n
发帖数: 116 | 1 自己做一家公司的online test见过一次，也看同学遇到过几次，和leetcode上的edit
distance不太一样，望大牛给个code。
两个anagram string S 和 P，定义两个操作:
1)相邻的character swap算一次操作
2)第一个character 和最后一个character swap算一次操作
问从S变到P的最小操作数。 |
w********s
发帖数: 1570 | 2 把string b移动后变成string a
如果b[0] = a[0], 那么找出a[0]在b中的位置，不妨设b[k];
如果b[k]接近接近b的末尾，那么把b[k]往末尾交换移动，再和b[0]交换，否则，向前
移动b[k]至b[0]位置
现在a[0]和b[0]相同了
对去除a[0]和b[0]的字符串做相同的操作 |
j*********n
发帖数: 34 | 3 BFS，用hashmap记录已访问过的string
比如从 hello 到 llohe
hello可以变成 oellh, ehllo, hlelo, helol, 如此下去做 BFS |
n********e
发帖数: 24 | 4 这题我也碰到了，一直没想通。 二楼的贪心不对的，首先你如果是右移过去的前面的
顺序会受影响要调整，就算调整了也不是最优的，比如abcccd变成acccdb。 如果用
shortest path 算法，按case里要求最多2000length（我当时是这个限制，你这里没看
到）需要记录的node肯定爆了。我光用a-z26个字母排就有26！种可能 |
w********s
发帖数: 1570 | 5 对于你的例子
A=abcccd
B=acccdb
扫描到第一个不同的
A=bcccd
B=cccdb
B'=bccdc
A=cd
B=dc
B'=cd
结束，总共移动2次。哪里不对了？
【在 n********e 的大作中提到】
: 这题我也碰到了，一直没想通。 二楼的贪心不对的，首先你如果是右移过去的前面的
: 顺序会受影响要调整，就算调整了也不是最优的，比如abcccd变成acccdb。 如果用
: shortest path 算法，按case里要求最多2000length（我当时是这个限制，你这里没看
: 到）需要记录的node肯定爆了。我光用a-z26个字母排就有26！种可能
|
n********e
发帖数: 24 | 6 A = abcccd
B = acccdb
移动一次后是
A = abcccd
B = bcccda
你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
【在 w********s 的大作中提到】
: 对于你的例子
: A=abcccd
: B=acccdb
: 扫描到第一个不同的
: A=bcccd
: B=cccdb
: B'=bccdc
: A=cd
: B=dc
: B'=cd
|
w********s
发帖数: 1570 | 7 你没看懂我的意思
你第一位相同的，就扔掉，处理下面的
、
所以从
A=bcccd
B=cccdb
开始
【在 n********e 的大作中提到】
: A = abcccd
: B = acccdb
: 移动一次后是
: A = abcccd
: B = bcccda
: 你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
|
n********e
发帖数: 24 | 8 我的意思就是第一位不能扔掉，因为你b从后面交换到c的位置必然是要影响你扔掉的a的
【在 w********s 的大作中提到】
: 你没看懂我的意思
: 你第一位相同的，就扔掉，处理下面的
: 、
: 所以从
: A=bcccd
: B=cccdb
: 开始
|
g**i
发帖数: 20 | 9 我觉得可以做的，就是当前位之前的已经排好我们不再想，然后后续的移动只要查看当
前位前面有几位数字就好，如果有n位，次数就是2n+1。所以这个例子一共移动了4次而
不是2次。
不过这个算法应该不是最优的 - -。。
【在 n********e 的大作中提到】
: A = abcccd
: B = acccdb
: 移动一次后是
: A = abcccd
: B = bcccda
: 你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
|
n********e
发帖数: 24 | 10 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
A = acbcccd
B = accccdb
最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
算上调整的开销就已经是5了
【在 g**i 的大作中提到】
: 我觉得可以做的，就是当前位之前的已经排好我们不再想，然后后续的移动只要查看当
: 前位前面有几位数字就好，如果有n位，次数就是2n+1。所以这个例子一共移动了4次而
: 不是2次。
: 不过这个算法应该不是最优的 - -。。
|
|
|
w********s
发帖数: 1570 | 11 A=acbcccd
B=accccdb
先去掉相同的开头
A=bcccd
B=cccdb
然后B[0]!=A[0], 最后一个b交换到第一个
B=bccdc, 1次
A=bcccd
砍掉相同的
A=cd
B=dc
交换一次，完成
总共移动2次。
【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
|
w********s
发帖数: 1570 | 12 ok, 理解你说的了
【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
|
w********s
发帖数: 1570 | 13 右移b的时候，计算一下开头相同部分调整的开销，然后和做一比较。
【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
|
d****n
发帖数: 12461 | 14 例如len(P)=4
可以认为目标P就是1,2,3,4
原始S例如1,4,3,2
先考虑non-circular情形。计算所有的unordered pairs。例如上面(4,3),(4,2),(3,2)
就是。操作1只可以让unordered pairs增加或者减少1。所以最小操作就是unordered
pairs数目。
1432->1342->1324->1234
对于circular的情形，操作2可以让位置0的unordered pairs从k变成n-1-k。如果位置0
的数是i，那么就有i-1个unordered pairs，所以这个操作把i移到末尾以后关于i的
unordered pairs就变成了n-i。对于队尾的j，从n-j变成了j-1。i,j之间的交换只能算
一次，所以整体减少是2(i-j-1)+(i>j?)，在i=j+1时等于1。
4321->1324->1234
对于中间的数，往前还是往后移动，这个再仔细计算一下。
edit
【在 q******n 的大作中提到】
: 自己做一家公司的online test见过一次，也看同学遇到过几次，和leetcode上的edit
: distance不太一样，望大牛给个code。
: 两个anagram string S 和 P，定义两个操作:
: 1)相邻的character swap算一次操作
: 2)第一个character 和最后一个character swap算一次操作
: 问从S变到P的最小操作数。
|
I*********7
发帖数: 125 | 15 我晕，这题好难。。。
BFS应该是不行。状态太多了。 |
o*****n
发帖数: 189 | 16 BFS暴力了一下, 16 个char就要算半小时. 要2000个, 估计还的找出公式, 一层一层推
. |
g*******i
发帖数: 110 | |
l**********a
发帖数: 181 | |
w********s
发帖数: 1570 | 19 只要修改一下头尾两位呼唤的开销，就可以了。
【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
|
l******6
发帖数: 340 | 20
greedy is not right
same source
abccccb
to different destiny
baccccb
and
bbcccca
how you make your greedy choices ?
【在 w********s 的大作中提到】
: 只要修改一下头尾两位呼唤的开销，就可以了。
|
|
|
s******6
发帖数: 12 | 21
题目要求算出最小移动次数，你这方法明显不是最小，有何用？
【在 w********s 的大作中提到】
: 只要修改一下头尾两位呼唤的开销，就可以了。
|
w********s
发帖数: 1570 | 22 SRC=abccccb
DST1=baccccb
SRC第一位a在DST1中的位置2
把2移到1
DST1'=abccccb，并计算a(bccccb)和a(bccccb)的移动偏差，可以递归获得
DST2=bbcccca
SRC第一位a在DST2的第7位
2种选择, 左移a，或者和首位交换
左移的话
DST2'=bbcccac, bbccacc, .... a(bbcccc), 到了第一位满足后，计算bccccb和bbcccc
的偏差，可以递归获得
交换的话
DST2‘=abccccb, 首位相同后，计算剩余要移动的次数(bccccb)和(bccccb)
【在 l******6 的大作中提到】
:
: greedy is not right
: same source
: abccccb
: to different destiny
: baccccb
: and
: bbcccca
: how you make your greedy choices ?
|
M*******a
发帖数: 1633 | 23 anagram里面的字符有没有重复的，没有重复的话我貌似知道怎么做 |
l******6
发帖数: 340 | 24
bbcccc
You are changing dst to src so you didn't get what I say , that is fine look
at this
src = bcccccccab
dst = abcccccccb
how to change dst to src?
As your logic, src first bit is b, it is either in dst bit 2 or bit 10 ,
change to either one is 1 distance(1 swap) , and no greedy decision can be
made by just this bit.
Note this is the easy case, in normal case , if no greedy decision can be
made for each step, the recursive lead to experiential complexity
【在 w********s 的大作中提到】
: SRC=abccccb
: DST1=baccccb
: SRC第一位a在DST1中的位置2
: 把2移到1
: DST1'=abccccb，并计算a(bccccb)和a(bccccb)的移动偏差，可以递归获得
: DST2=bbcccca
: SRC第一位a在DST2的第7位
: 2种选择, 左移a，或者和首位交换
: 左移的话
: DST2'=bbcccac, bbccacc, .... a(bbcccc), 到了第一位满足后，计算bccccb和bbcccc
|
t*****a
发帖数: 106 | 25 我认为这个题是count inversion的变形。假设有两个string, S1,S2。我的思路是先选
取一个string,比如S1,对字符编号，S1="abcd"，则a=1,b=2,c=3,d=4.然后再对S2编号
，比如S2="acdb",则S2的编号是1342. 这样就相当于对S2排序，计算count inversion
。但是因为可以把第一个元素换到最后一个元素，所以在经典的merge count时，需要
多考虑一种情况，即向右swap，取最小的inversion值，而且是考虑全长度的向右swap
，不是sub array的向右swap。应该可以在n*(logn)的时间里解决。一个大概思路，回
头写个code试验一下。 |
f**********t
发帖数: 1001 | 26 // How do I convert two anagrams of a word, into a common anagram in minimum
number of moves with only two types of move allowed-1-You can swap 1st and
last character (of any given string) considered as one move. 2-You can swap
any two adjacent character (of any string) considered as one move?
// assume all characters appear only once
unsigned MinSwap(string a, string b) {
if (a.empty()) {
return 0;
}
unordered_map mp;
unsigned i = 0;
for (char c : a) {
mp[c] = i++;
}
vector vu(a.size());
for (size_t i = 0; i < b.size(); ++i) {
vu[i] = mp[b[i]];
}
unsigned count = 0;
while (1) {
size_t k = 0;
for (; k < vu.size(); ++k) {
if (vu[k] != k) {
break;
}
}
if (k == vu.size()) {
break;
}
unsigned forwardSteps;
if (k < vu[k]) {
forwardSteps = vu[k] - k;
} else {
forwardSteps = vu.size() - (k - vu[k]);
}
unsigned forwardStepsL;
unsigned kl = k == 0 ? vu.size() - 1 : k - 1;
if (kl < vu[kl]) {
forwardStepsL = vu[kl] - kl;
} else {
forwardStepsL = vu.size() - (kl - vu[kl]);
}
unsigned forwardStepsR;
unsigned kr = k == vu.size() - 1 ? 0 : k + 1;
if (kr < vu[kr]) {
forwardStepsR = vu[kr] - kr;
} else {
forwardStepsR = vu.size() - (kr - vu[kr]);
}
if (forwardSteps + (vu.size() - forwardStepsR)
< (vu.size() -forwardSteps) + forwardStepsL) {
swap(vu[k], vu[kr]);
} else {
swap(vu[k], vu[kl]);
}
++count;
}
return count;
}
void MinSwapTest() {
cout << MinSwap("acbd", "abcd") << ' ' << MinSwap("dbca", "abcd")
<< MinSwap("abcd", "dcba") << ' ' << MinSwap("abcd", "adbc")
<< endl;
} |
s***5
发帖数: 2136 | 27 把P中字符的序号引入S，然后S就成为一个数组，计算的结果就是求每个数字偏离其排
序（按P的字符）后位置的差值总和。
A = acbcccd
B = accccdb -> {1,2,3,4,5,6,7}
A -> {1,2,7,3,4,5,6}
就将A数组使用bubble sort排序需要swap的次数 -> 4 |
p****a
发帖数: 447 | 28 有点意思
这个能证明么？
【在 s***5 的大作中提到】
: 把P中字符的序号引入S，然后S就成为一个数组，计算的结果就是求每个数字偏离其排
: 序（按P的字符）后位置的差值总和。
: A = acbcccd
: B = accccdb -> {1,2,3,4,5,6,7}
: A -> {1,2,7,3,4,5,6}
: 就将A数组使用bubble sort排序需要swap的次数 -> 4
|
c****o
发帖数: 32446 | |
J******u
发帖数: 42 | 30 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
|
|
J******u
发帖数: 42 | 31 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
c*****m
发帖数: 271 | 32 要找最优解还是BFS比较合理吧，就是空间复杂度可能太高。
【在 j*********n 的大作中提到】
: BFS，用hashmap记录已访问过的string
:
: 比如从 hello 到 llohe
: hello可以变成 oellh, ehllo, hlelo, helol, 如此下去做 BFS
|
c*****m
发帖数: 271 | 33 要找最优解还是BFS比较合理吧，就是空间复杂度可能太高。 |
w****k
发帖数: 755 | 34 将P和Q相同index的字符绑定，然后任意调整次序，这样得到的P‘和Q’应该和原来的
PQ调整次数相同。
于是把其中之一调整为增序，则把另一个调整为增序做bubble sort所需要的步数就是
所求。
但这里没考虑首尾互换的问题，这个思路可以启发一下大家么？我在想LIS或者LCS是否
可以考虑。 |
q******n
发帖数: 116 | 35 自己做一家公司的online test见过一次，也看同学遇到过几次，和leetcode上的edit
distance不太一样，望大牛给个code。
两个anagram string S 和 P，定义两个操作:
1)相邻的character swap算一次操作
2)第一个character 和最后一个character swap算一次操作
问从S变到P的最小操作数。 |
w********s
发帖数: 1570 | 36 把string b移动后变成string a
如果b[0] = a[0], 那么找出a[0]在b中的位置，不妨设b[k];
如果b[k]接近接近b的末尾，那么把b[k]往末尾交换移动，再和b[0]交换，否则，向前
移动b[k]至b[0]位置
现在a[0]和b[0]相同了
对去除a[0]和b[0]的字符串做相同的操作 |
j*********n
发帖数: 34 | 37 BFS，用hashmap记录已访问过的string
比如从 hello 到 llohe
hello可以变成 oellh, ehllo, hlelo, helol, 如此下去做 BFS |
n********e
发帖数: 24 | 38 这题我也碰到了，一直没想通。 二楼的贪心不对的，首先你如果是右移过去的前面的
顺序会受影响要调整，就算调整了也不是最优的，比如abcccd变成acccdb。 如果用
shortest path 算法，按case里要求最多2000length（我当时是这个限制，你这里没看
到）需要记录的node肯定爆了。我光用a-z26个字母排就有26！种可能 |
w********s
发帖数: 1570 | 39 对于你的例子
A=abcccd
B=acccdb
扫描到第一个不同的
A=bcccd
B=cccdb
B'=bccdc
A=cd
B=dc
B'=cd
结束，总共移动2次。哪里不对了？
【在 n********e 的大作中提到】
: 这题我也碰到了，一直没想通。 二楼的贪心不对的，首先你如果是右移过去的前面的
: 顺序会受影响要调整，就算调整了也不是最优的，比如abcccd变成acccdb。 如果用
: shortest path 算法，按case里要求最多2000length（我当时是这个限制，你这里没看
: 到）需要记录的node肯定爆了。我光用a-z26个字母排就有26！种可能
|
n********e
发帖数: 24 | 40 A = abcccd
B = acccdb
移动一次后是
A = abcccd
B = bcccda
你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
【在 w********s 的大作中提到】
: 对于你的例子
: A=abcccd
: B=acccdb
: 扫描到第一个不同的
: A=bcccd
: B=cccdb
: B'=bccdc
: A=cd
: B=dc
: B'=cd
|
|
|
w********s
发帖数: 1570 | 41 你没看懂我的意思
你第一位相同的，就扔掉，处理下面的
、
所以从
A=bcccd
B=cccdb
开始
【在 n********e 的大作中提到】
: A = abcccd
: B = acccdb
: 移动一次后是
: A = abcccd
: B = bcccda
: 你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
|
n********e
发帖数: 24 | 42 我的意思就是第一位不能扔掉，因为你b从后面交换到c的位置必然是要影响你扔掉的a的
【在 w********s 的大作中提到】
: 你没看懂我的意思
: 你第一位相同的，就扔掉，处理下面的
: 、
: 所以从
: A=bcccd
: B=cccdb
: 开始
|
g**i
发帖数: 20 | 43 我觉得可以做的，就是当前位之前的已经排好我们不再想，然后后续的移动只要查看当
前位前面有几位数字就好，如果有n位，次数就是2n+1。所以这个例子一共移动了4次而
不是2次。
不过这个算法应该不是最优的 - -。。
【在 n********e 的大作中提到】
: A = abcccd
: B = acccdb
: 移动一次后是
: A = abcccd
: B = bcccda
: 你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
|
n********e
发帖数: 24 | 44 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
A = acbcccd
B = accccdb
最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
算上调整的开销就已经是5了
【在 g**i 的大作中提到】
: 我觉得可以做的，就是当前位之前的已经排好我们不再想，然后后续的移动只要查看当
: 前位前面有几位数字就好，如果有n位，次数就是2n+1。所以这个例子一共移动了4次而
: 不是2次。
: 不过这个算法应该不是最优的 - -。。
|
w********s
发帖数: 1570 | 45 A=acbcccd
B=accccdb
先去掉相同的开头
A=bcccd
B=cccdb
然后B[0]!=A[0], 最后一个b交换到第一个
B=bccdc, 1次
A=bcccd
砍掉相同的
A=cd
B=dc
交换一次，完成
总共移动2次。
【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
|
w********s
发帖数: 1570 | 46 ok, 理解你说的了
【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
|
w********s
发帖数: 1570 | 47 右移b的时候，计算一下开头相同部分调整的开销，然后和做一比较。
【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
|
d****n
发帖数: 12461 | 48 例如len(P)=4
可以认为目标P就是1,2,3,4
原始S例如1,4,3,2
先考虑non-circular情形。计算所有的unordered pairs。例如上面(4,3),(4,2),(3,2)
就是。操作1只可以让unordered pairs增加或者减少1。所以最小操作就是unordered
pairs数目。
1432->1342->1324->1234
对于circular的情形，操作2可以让位置0的unordered pairs从k变成n-1-k。如果位置0
的数是i，那么就有i-1个unordered pairs，所以这个操作把i移到末尾以后关于i的
unordered pairs就变成了n-i。对于队尾的j，从n-j变成了j-1。i,j之间的交换只能算
一次，所以整体减少是2(i-j-1)+(i>j?)，在i=j+1时等于1。
4321->1324->1234
对于中间的数，往前还是往后移动，这个再仔细计算一下。
edit
【在 q******n 的大作中提到】
: 自己做一家公司的online test见过一次，也看同学遇到过几次，和leetcode上的edit
: distance不太一样，望大牛给个code。
: 两个anagram string S 和 P，定义两个操作:
: 1)相邻的character swap算一次操作
: 2)第一个character 和最后一个character swap算一次操作
: 问从S变到P的最小操作数。
|
I*********7
发帖数: 125 | 49 我晕，这题好难。。。
BFS应该是不行。状态太多了。 |
o*****n
发帖数: 189 | 50 BFS暴力了一下, 16 个char就要算半小时. 要2000个, 估计还的找出公式, 一层一层推
. |
|
|
g*******i
发帖数: 110 | |
w********s
发帖数: 1570 | 52 只要修改一下头尾两位呼唤的开销，就可以了。
【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
|
l******6
发帖数: 340 | 53
greedy is not right
same source
abccccb
to different destiny
baccccb
and
bbcccca
how you make your greedy choices ?
【在 w********s 的大作中提到】
: 只要修改一下头尾两位呼唤的开销，就可以了。
|
s******6
发帖数: 12 | 54
题目要求算出最小移动次数，你这方法明显不是最小，有何用？
【在 w********s 的大作中提到】
: 只要修改一下头尾两位呼唤的开销，就可以了。
|
w********s
发帖数: 1570 | 55 SRC=abccccb
DST1=baccccb
SRC第一位a在DST1中的位置2
把2移到1
DST1'=abccccb，并计算a(bccccb)和a(bccccb)的移动偏差，可以递归获得
DST2=bbcccca
SRC第一位a在DST2的第7位
2种选择, 左移a，或者和首位交换
左移的话
DST2'=bbcccac, bbccacc, .... a(bbcccc), 到了第一位满足后，计算bccccb和bbcccc
的偏差，可以递归获得
交换的话
DST2‘=abccccb, 首位相同后，计算剩余要移动的次数(bccccb)和(bccccb)
【在 l******6 的大作中提到】
:
: greedy is not right
: same source
: abccccb
: to different destiny
: baccccb
: and
: bbcccca
: how you make your greedy choices ?
|
M*******a
发帖数: 1633 | 56 anagram里面的字符有没有重复的，没有重复的话我貌似知道怎么做 |
l******6
发帖数: 340 | 57
bbcccc
You are changing dst to src so you didn't get what I say , that is fine look
at this
src = bcccccccab
dst = abcccccccb
how to change dst to src?
As your logic, src first bit is b, it is either in dst bit 2 or bit 10 ,
change to either one is 1 distance(1 swap) , and no greedy decision can be
made by just this bit.
Note this is the easy case, in normal case , if no greedy decision can be
made for each step, the recursive lead to experiential complexity
【在 w********s 的大作中提到】
: SRC=abccccb
: DST1=baccccb
: SRC第一位a在DST1中的位置2
: 把2移到1
: DST1'=abccccb，并计算a(bccccb)和a(bccccb)的移动偏差，可以递归获得
: DST2=bbcccca
: SRC第一位a在DST2的第7位
: 2种选择, 左移a，或者和首位交换
: 左移的话
: DST2'=bbcccac, bbccacc, .... a(bbcccc), 到了第一位满足后，计算bccccb和bbcccc
|
t*****a
发帖数: 106 | 58 我认为这个题是count inversion的变形。假设有两个string, S1,S2。我的思路是先选
取一个string,比如S1,对字符编号，S1="abcd"，则a=1,b=2,c=3,d=4.然后再对S2编号
，比如S2="acdb",则S2的编号是1342. 这样就相当于对S2排序，计算count inversion
。但是因为可以把第一个元素换到最后一个元素，所以在经典的merge count时，需要
多考虑一种情况，即向右swap，取最小的inversion值，而且是考虑全长度的向右swap
，不是sub array的向右swap。应该可以在n*(logn)的时间里解决。一个大概思路，回
头写个code试验一下。 |
f**********t
发帖数: 1001 | 59 // How do I convert two anagrams of a word, into a common anagram in minimum
number of moves with only two types of move allowed-1-You can swap 1st and
last character (of any given string) considered as one move. 2-You can swap
any two adjacent character (of any string) considered as one move?
// assume all characters appear only once
unsigned MinSwap(string a, string b) {
if (a.empty()) {
return 0;
}
unordered_map mp;
unsigned i = 0;
for (char c : a) {
mp[c] = i++;
}
vector vu(a.size());
for (size_t i = 0; i < b.size(); ++i) {
vu[i] = mp[b[i]];
}
unsigned count = 0;
while (1) {
size_t k = 0;
for (; k < vu.size(); ++k) {
if (vu[k] != k) {
break;
}
}
if (k == vu.size()) {
break;
}
unsigned forwardSteps;
if (k < vu[k]) {
forwardSteps = vu[k] - k;
} else {
forwardSteps = vu.size() - (k - vu[k]);
}
unsigned forwardStepsL;
unsigned kl = k == 0 ? vu.size() - 1 : k - 1;
if (kl < vu[kl]) {
forwardStepsL = vu[kl] - kl;
} else {
forwardStepsL = vu.size() - (kl - vu[kl]);
}
unsigned forwardStepsR;
unsigned kr = k == vu.size() - 1 ? 0 : k + 1;
if (kr < vu[kr]) {
forwardStepsR = vu[kr] - kr;
} else {
forwardStepsR = vu.size() - (kr - vu[kr]);
}
if (forwardSteps + (vu.size() - forwardStepsR)
< (vu.size() -forwardSteps) + forwardStepsL) {
swap(vu[k], vu[kr]);
} else {
swap(vu[k], vu[kl]);
}
++count;
}
return count;
}
void MinSwapTest() {
cout << MinSwap("acbd", "abcd") << ' ' << MinSwap("dbca", "abcd")
<< MinSwap("abcd", "dcba") << ' ' << MinSwap("abcd", "adbc")
<< endl;
} |
s***5
发帖数: 2136 | 60 把P中字符的序号引入S，然后S就成为一个数组，计算的结果就是求每个数字偏离其排
序（按P的字符）后位置的差值总和。
A = acbcccd
B = accccdb -> {1,2,3,4,5,6,7}
A -> {1,2,7,3,4,5,6}
就将A数组使用bubble sort排序需要swap的次数 -> 4 |
|
|
p****a
发帖数: 447 | 61 有点意思
这个能证明么？
【在 s***5 的大作中提到】
: 把P中字符的序号引入S，然后S就成为一个数组，计算的结果就是求每个数字偏离其排
: 序（按P的字符）后位置的差值总和。
: A = acbcccd
: B = accccdb -> {1,2,3,4,5,6,7}
: A -> {1,2,7,3,4,5,6}
: 就将A数组使用bubble sort排序需要swap的次数 -> 4
|
c****o
发帖数: 32446 | |
J******u
发帖数: 42 | 63 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
J******u
发帖数: 42 | 64 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
c*****m
发帖数: 271 | 65 要找最优解还是BFS比较合理吧，就是空间复杂度可能太高。
【在 j*********n 的大作中提到】
: BFS，用hashmap记录已访问过的string
:
: 比如从 hello 到 llohe
: hello可以变成 oellh, ehllo, hlelo, helol, 如此下去做 BFS
|
c*****m
发帖数: 271 | 66 要找最优解还是BFS比较合理吧，就是空间复杂度可能太高。 |
w****k
发帖数: 755 | 67 将P和Q相同index的字符绑定，然后任意调整次序，这样得到的P‘和Q’应该和原来的
PQ调整次数相同。
于是把其中之一调整为增序，则把另一个调整为增序做bubble sort所需要的步数就是
所求。
但这里没考虑首尾互换的问题，这个思路可以启发一下大家么？我在想LIS或者LCS是否
可以考虑。 |
j********g
发帖数: 5 | 68
edit
http://faculty.cs.tamu.edu/ajiang/BRAMECC_journal.pdf
Theorem 1
【在 q******n 的大作中提到】
: 自己做一家公司的online test见过一次，也看同学遇到过几次，和leetcode上的edit
: distance不太一样，望大牛给个code。
: 两个anagram string S 和 P，定义两个操作:
: 1)相邻的character swap算一次操作
: 2)第一个character 和最后一个character swap算一次操作
: 问从S变到P的最小操作数。
|
j********g
发帖数: 5 | |
