logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
请问我的1+1的铃声为何没有了？
avatar
请问我的1+1的铃声为何没有了？# PDA - 掌中宝
q*n
1 楼
自己做一家公司的online test见过一次，也看同学遇到过几次，和leetcode上的edit
distance不太一样，望大牛给个code。
两个anagram string S 和 P，定义两个操作:
1)相邻的character swap算一次操作
2)第一个character 和最后一个character swap算一次操作
问从S变到P的最小操作数。
avatar
b*g
2 楼
最近在准备交485的材料。
律师说出生公证要 City, Province if applicable, Country
但是我是在小县城出生的。办的出生公证只有县，省，国家，就是County, Province,
Country
这样可以么？
谢谢大家
avatar
l*o
4 楼
应该找那种remodel的company， 还是找handyman呢？
avatar
i*y
5 楼
突然发现来电铃声没有了
其他闹铃和短信的铃声还有，我下载了新的铃声设置进去还是没有
请问如何解决？现在只有震动了。。。。。
谢谢
avatar
w*s
6 楼
把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]的字符串做相同的操作
avatar
l*n
7 楼
可以。最好485 配套写。
avatar
l*h
8 楼
多找几个handyman问问价。

【在 l*****o 的大作中提到】
: 应该找那种remodel的company， 还是找handyman呢？
avatar
g*n
9 楼
Switched profile?

【在 i********y 的大作中提到】
: 突然发现来电铃声没有了
: 其他闹铃和短信的铃声还有，我下载了新的铃声设置进去还是没有
: 请问如何解决？现在只有震动了。。。。。
: 谢谢
avatar
j*n
10 楼
BFS，用hashmap记录已访问过的string

比如从 hello 到 llohe
hello可以变成 oellh, ehllo, hlelo, helol, 如此下去做 BFS
avatar
b*g
11 楼
谢谢。就是说485最好写县不要写县所属的城市么？

【在 l*******n 的大作中提到】
: 可以。最好485 配套写。
avatar
i*y
12 楼
我去
果然是我SB了，有一次开会设置了忘了改回去。。。。。
谢谢

【在 g*****n 的大作中提到】
: Switched profile?
avatar
n*e
13 楼
这题我也碰到了，一直没想通。 二楼的贪心不对的，首先你如果是右移过去的前面的
顺序会受影响要调整，就算调整了也不是最优的，比如abcccd变成acccdb。 如果用
shortest path 算法，按case里要求最多2000length（我当时是这个限制，你这里没看
到）需要记录的node肯定爆了。我光用a-z26个字母排就有26！种可能
avatar
a*r
14 楼
你护照上出生地怎么写的？ 485材料最好要保持一致，免得RFE。

【在 b*****g 的大作中提到】
: 谢谢。就是说485最好写县不要写县所属的城市么？
avatar
w*s
15 楼
对于你的例子
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！种可能
avatar
b*g
16 楼
护照上面出生地只有写省。没有写县/市的。省是一致的。

【在 a****r 的大作中提到】
: 你护照上出生地怎么写的？ 485材料最好要保持一致，免得RFE。
avatar
n*e
17 楼
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
avatar
a*r
18 楼
那填485及相关表格时，和公证书保持一致就行了。

【在 b*****g 的大作中提到】
: 护照上面出生地只有写省。没有写县/市的。省是一致的。
avatar
w*s
19 楼
你没看懂我的意思
你第一位相同的，就扔掉，处理下面的
、
所以从
A=bcccd
B=cccdb
开始

【在 n********e 的大作中提到】
: A = abcccd
: B = acccdb
: 移动一次后是
: A = abcccd
: B = bcccda
: 你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
avatar
x*3
20 楼
护照上的是：地级市
然而公证书上的是：县
这样的话，护照和公证书就不一致了，怎么弄？填表怎么填？可不可提交一个地级市与
县级市或者县的附属关系做个说明？
有类似情况的前辈来帮忙解答，谢谢。
avatar
n*e
21 楼
我的意思就是第一位不能扔掉，因为你b从后面交换到c的位置必然是要影响你扔掉的a的

【在 w********s 的大作中提到】
: 你没看懂我的意思
: 你第一位相同的，就扔掉，处理下面的
: 、
: 所以从
: A=bcccd
: B=cccdb
: 开始
avatar
l*n
22 楼
护照上只有省份。
avatar
g*i
23 楼
我觉得可以做的，就是当前位之前的已经排好我们不再想，然后后续的移动只要查看当
前位前面有几位数字就好，如果有n位，次数就是2n+1。所以这个例子一共移动了4次而
不是2次。
不过这个算法应该不是最优的 - -。。

【在 n********e 的大作中提到】
: A = abcccd
: B = acccdb
: 移动一次后是
: A = abcccd
: B = bcccda
: 你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
avatar
s*3
24 楼
之前没有注意过这个问题，刚才发现我的出生公证也写的是县，可是我的458是写的市
，两边没有统一起来，会有什么影响吗？

【在 l*******n 的大作中提到】
: 可以。最好485 配套写。
avatar
n*e
25 楼
2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
A = acbcccd
B = accccdb
最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
算上调整的开销就已经是5了

【在 g**i 的大作中提到】
: 我觉得可以做的，就是当前位之前的已经排好我们不再想，然后后续的移动只要查看当
: 前位前面有几位数字就好，如果有n位，次数就是2n+1。所以这个例子一共移动了4次而
: 不是2次。
: 不过这个算法应该不是最优的 - -。。
avatar
X*J
26 楼
借楼问，同样的问题，我的G325A 上配偶的出生地律师填了 省， 配偶的G325A上，填
了 county,
出生证明上即有省也有 county.
律师说没有关系，这些都是minor问题。我还是想听听大牛们说说

【在 s*****3 的大作中提到】
: 之前没有注意过这个问题，刚才发现我的出生公证也写的是县，可是我的458是写的市
: ，两边没有统一起来，会有什么影响吗？
avatar
w*s
27 楼
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了
avatar
w*s
28 楼
ok, 理解你说的了

【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
avatar
w*s
29 楼
右移b的时候，计算一下开头相同部分调整的开销，然后和做一比较。

【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
avatar
d*n
30 楼
例如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的最小操作数。
avatar
I*7
31 楼
我晕，这题好难。。。
BFS应该是不行。状态太多了。
avatar
o*n
32 楼
BFS暴力了一下, 16 个char就要算半小时. 要2000个, 估计还的找出公式, 一层一层推
.
avatar
g*i
33 楼
顶一下。同求解法
avatar
l*a
34 楼
mark
avatar
w*s
35 楼
只要修改一下头尾两位呼唤的开销，就可以了。

【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
avatar
l*6
36 楼

greedy is not right
same source
abccccb
to different destiny
baccccb
and
bbcccca
how you make your greedy choices ?

【在 w********s 的大作中提到】
: 只要修改一下头尾两位呼唤的开销，就可以了。
avatar
s*6
37 楼

题目要求算出最小移动次数，你这方法明显不是最小，有何用？

【在 w********s 的大作中提到】
: 只要修改一下头尾两位呼唤的开销，就可以了。
avatar
w*s
38 楼
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 ?
avatar
M*a
39 楼
anagram里面的字符有没有重复的，没有重复的话我貌似知道怎么做
avatar
l*6
40 楼

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
avatar
t*a
41 楼
我认为这个题是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试验一下。
avatar
f*t
42 楼
// 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;
}
avatar
s*5
43 楼
把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
avatar
p*a
44 楼
有点意思
这个能证明么？

【在 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
avatar
c*o
45 楼
不用想，这种题肯定是用DP
avatar
J*u
46 楼
这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。
avatar
J*u
47 楼
这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。
avatar
c*m
48 楼
要找最优解还是BFS比较合理吧，就是空间复杂度可能太高。

【在 j*********n 的大作中提到】
: BFS，用hashmap记录已访问过的string
:
: 比如从 hello 到 llohe
: hello可以变成 oellh, ehllo, hlelo, helol, 如此下去做 BFS
avatar
c*m
49 楼
要找最优解还是BFS比较合理吧，就是空间复杂度可能太高。
avatar
w*k
50 楼
将P和Q相同index的字符绑定，然后任意调整次序，这样得到的P‘和Q’应该和原来的
PQ调整次数相同。
于是把其中之一调整为增序，则把另一个调整为增序做bubble sort所需要的步数就是
所求。
但这里没考虑首尾互换的问题，这个思路可以启发一下大家么？我在想LIS或者LCS是否
可以考虑。
avatar
q*n
51 楼
自己做一家公司的online test见过一次，也看同学遇到过几次，和leetcode上的edit
distance不太一样，望大牛给个code。
两个anagram string S 和 P，定义两个操作:
1)相邻的character swap算一次操作
2)第一个character 和最后一个character swap算一次操作
问从S变到P的最小操作数。
avatar
w*s
52 楼
把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]的字符串做相同的操作
avatar
j*n
53 楼
BFS，用hashmap记录已访问过的string

比如从 hello 到 llohe
hello可以变成 oellh, ehllo, hlelo, helol, 如此下去做 BFS
avatar
n*e
54 楼
这题我也碰到了，一直没想通。 二楼的贪心不对的，首先你如果是右移过去的前面的
顺序会受影响要调整，就算调整了也不是最优的，比如abcccd变成acccdb。 如果用
shortest path 算法，按case里要求最多2000length（我当时是这个限制，你这里没看
到）需要记录的node肯定爆了。我光用a-z26个字母排就有26！种可能
avatar
w*s
55 楼
对于你的例子
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！种可能
avatar
n*e
56 楼
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
avatar
w*s
57 楼
你没看懂我的意思
你第一位相同的，就扔掉，处理下面的
、
所以从
A=bcccd
B=cccdb
开始

【在 n********e 的大作中提到】
: A = abcccd
: B = acccdb
: 移动一次后是
: A = abcccd
: B = bcccda
: 你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
avatar
n*e
58 楼
我的意思就是第一位不能扔掉，因为你b从后面交换到c的位置必然是要影响你扔掉的a的

【在 w********s 的大作中提到】
: 你没看懂我的意思
: 你第一位相同的，就扔掉，处理下面的
: 、
: 所以从
: A=bcccd
: B=cccdb
: 开始
avatar
g*i
59 楼
我觉得可以做的，就是当前位之前的已经排好我们不再想，然后后续的移动只要查看当
前位前面有几位数字就好，如果有n位，次数就是2n+1。所以这个例子一共移动了4次而
不是2次。
不过这个算法应该不是最优的 - -。。

【在 n********e 的大作中提到】
: A = abcccd
: B = acccdb
: 移动一次后是
: A = abcccd
: B = bcccda
: 你右移是会影响前面的，不能把前面匹配的去掉直接考虑后面的
avatar
n*e
60 楼
2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
A = acbcccd
B = accccdb
最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
算上调整的开销就已经是5了

【在 g**i 的大作中提到】
: 我觉得可以做的，就是当前位之前的已经排好我们不再想，然后后续的移动只要查看当
: 前位前面有几位数字就好，如果有n位，次数就是2n+1。所以这个例子一共移动了4次而
: 不是2次。
: 不过这个算法应该不是最优的 - -。。
avatar
w*s
61 楼
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了
avatar
w*s
62 楼
ok, 理解你说的了

【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
avatar
w*s
63 楼
右移b的时候，计算一下开头相同部分调整的开销，然后和做一比较。

【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
avatar
d*n
64 楼
例如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的最小操作数。
avatar
I*7
65 楼
我晕，这题好难。。。
BFS应该是不行。状态太多了。
avatar
o*n
66 楼
BFS暴力了一下, 16 个char就要算半小时. 要2000个, 估计还的找出公式, 一层一层推
.
avatar
g*i
67 楼
顶一下。同求解法
avatar
w*s
68 楼
只要修改一下头尾两位呼唤的开销，就可以了。

【在 n********e 的大作中提到】
: 2n+1确实是考虑了调整的开销，但这不是最优解了。我例子没给好，看这个
: A = acbcccd
: B = accccdb
: 最优解是B的最后一位b左移4位，而如果贪心解法应该是在第三位的时候要右移b，这里
: 算上调整的开销就已经是5了
avatar
l*6
69 楼

greedy is not right
same source
abccccb
to different destiny
baccccb
and
bbcccca
how you make your greedy choices ?

【在 w********s 的大作中提到】
: 只要修改一下头尾两位呼唤的开销，就可以了。
avatar
s*6
70 楼

题目要求算出最小移动次数，你这方法明显不是最小，有何用？

【在 w********s 的大作中提到】
: 只要修改一下头尾两位呼唤的开销，就可以了。
avatar
w*s
71 楼
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 ?
avatar
M*a
72 楼
anagram里面的字符有没有重复的，没有重复的话我貌似知道怎么做
avatar
l*6
73 楼

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
avatar
t*a
74 楼
我认为这个题是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试验一下。
avatar
f*t
75 楼
// 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;
}
avatar
s*5
76 楼
把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
avatar
p*a
77 楼
有点意思
这个能证明么？

【在 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
avatar
c*o
78 楼
不用想，这种题肯定是用DP
avatar
J*u
79 楼
这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。
avatar
J*u
80 楼
这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。
avatar
c*m
81 楼
要找最优解还是BFS比较合理吧，就是空间复杂度可能太高。

【在 j*********n 的大作中提到】
: BFS，用hashmap记录已访问过的string
:
: 比如从 hello 到 llohe
: hello可以变成 oellh, ehllo, hlelo, helol, 如此下去做 BFS
avatar
c*m
82 楼
要找最优解还是BFS比较合理吧，就是空间复杂度可能太高。
avatar
w*k
83 楼
将P和Q相同index的字符绑定，然后任意调整次序，这样得到的P‘和Q’应该和原来的
PQ调整次数相同。
于是把其中之一调整为增序，则把另一个调整为增序做bubble sort所需要的步数就是
所求。
但这里没考虑首尾互换的问题，这个思路可以启发一下大家么？我在想LIS或者LCS是否
可以考虑。
avatar
j*g
84 楼

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的最小操作数。
相关阅读
回国的话哪些手机或山寨版的东东值得带回来上国内网站特别慢skype 打个电话 c2d 就可以当炉子了问个视频网站速度问题今天才知道N4还要自己设APN急问，Nexus 4连不上wifi家里有小孩子的还有人要apple tv 2吗 200$ 出一个黑莓z10如何设置VPN？我用的是签约机，如果我买个unlocked的手机的话能把手机号换过来么？大家要理解软软淘宝上哪个手机能到美国入V网有3G？Re: 让我告诉你们一个真实的软工。。。 (转载)都是被逼的使用 WINDOWS的主要原因是officeablution 封 bullmaster 在 PDA 版急问，有微软的朋友在线吗？XBMC的射手(Shooter)字幕插件出错Error123 (转载)outlook.com 空间大小？与时俱进的国内小姐培训课程
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。