w********s
发帖数: 1570 | 1 a替换成b，或者b替换成a，算1次，
给出一个string，比如aaabababbba
问最少替换几次能变成左边都是a，右边都是b的那种？
举个例子，
aba，替换1次，变成aaa
bba，替换一次，变成bbb
aaba，替换1次，变成aabb
。。。。。。。。。。 |
l******6
发帖数: 340 | 2 int numOfConvert(const string &src)
{
int strSiz = src.size();
if(strSiz < 2)
return 0;
int ret = strSiz;
vector numOfPreB (strSiz , 0);
vector numOfPostA (strSiz , 0);
for( int i = 1; i < strSiz ; i++)
{
numOfPreB[i] = numOfPreB[i - 1];
if(src[i - 1] == 'b')
numOfPreB[i] += 1;
numOfPostA[strSiz - 1 - i] = numOfPostA[strSiz - i];
if(src[strSiz - i] == 'a')
numOfPostA[strSiz - 1 - i] += 1;
}
for( int i = 0 ; i < strSiz ; i++)
{
int num = numOfPreB[i] + numOfPostA[i];
ret = ret>num? num:ret;
}
return ret;
} |
D**********d
发帖数: 849 | 3 从前往后扫一遍，记录前面若全部变成 a 的替换数，与全部变成 b 的替换数。
从后往前扫一遍，记录后面若全部变成 a 的替换数，与全部变成 b 的替换数。
再扫一遍，对每个位置比较这四个数字，找最小的。
可以再优化:
1. 只记录全部变成 a 的替换数
2. 在扫第二遍时就找最小值。 |
r******j
发帖数: 92 | 4 可以看做选哪个位置开始由a->b。
从后到前扫一遍，对于每个b记录已经遇见了多少个a，也就是把当前b当做第一个b，需
要把多少个a变成b。
从前往后扫一遍，对于每个b记录已经遇见了多少个b，也就是把当前b当做第一个b，需
要把多少个b变成a。
把每个b的这个两个值相加，求最小。 |
r******j
发帖数: 92 | |
P*******r
发帖数: 210 | 6 好像不太对。
如果是aaaabaaaa呢？
答案应该是1，按你的做法是不是3？
【在 r******j 的大作中提到】
: 可以看做选哪个位置开始由a->b。
: 从后到前扫一遍，对于每个b记录已经遇见了多少个a，也就是把当前b当做第一个b，需
: 要把多少个a变成b。
: 从前往后扫一遍，对于每个b记录已经遇见了多少个b，也就是把当前b当做第一个b，需
: 要把多少个b变成a。
: 把每个b的这个两个值相加，求最小。
|
P*******r
发帖数: 210 | |
P*******r
发帖数: 210 | |
r******j
发帖数: 92 | 9
恩，你说的是对的。
是不是应该再考虑一种情况，就是全是a的，相当于把b的起始点选在最后。
【在 P*******r 的大作中提到】
: 好像不太对。
: 如果是aaaabaaaa呢？
: 答案应该是1，按你的做法是不是3？
|
l*n
发帖数: 529 | 10 有递推关系的不是直接的min值，而是i左右的b字符和a字符个数，所以好像没有办法针
对min值做dp。还是直接scan比较直观。
int minChange(String s) {
int[] countABackword = new int[s.length() + 1];
countABackword[s.length()] = 0;
for (int i = s.length() - 1; i >= 0; i--) {
char c = s.charAt(i);
countABackword[i] = c == 'a' ? countABackword[i + 1] + 1
: countABackword[i + 1];
}
int countBForward = 0;
int min = countABackword[0]; // case: all b
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == 'b') {
countBForward++;
}
int curr = countBForward + countABackword[i + 1];
if (curr < min)
min = curr;
}
return min;
}
【在 P*******r 的大作中提到】
: 展开说说？
|
|
|
l****h
发帖数: 1189 | 11 这个逻辑真么简单，居然是对的。
不过我还是没明白为什么是对的。
就是说，比较在所有b的位置：NUM=左边是b（包括该位置）的数目+右边是a的数目。最
小的NUM就是需要改字母的总数。
我就是想不明白这和原题为什么等价。
【在 l*n 的大作中提到】
: 有递推关系的不是直接的min值，而是i左右的b字符和a字符个数，所以好像没有办法针
: 对min值做dp。还是直接scan比较直观。
: int minChange(String s) {
: int[] countABackword = new int[s.length() + 1];
: countABackword[s.length()] = 0;
: for (int i = s.length() - 1; i >= 0; i--) {
: char c = s.charAt(i);
: countABackword[i] = c == 'a' ? countABackword[i + 1] + 1
: : countABackword[i + 1];
: }
|
P*******r
发帖数: 210 | 12 赞，简单明了。
【在 l*n 的大作中提到】
: 有递推关系的不是直接的min值，而是i左右的b字符和a字符个数，所以好像没有办法针
: 对min值做dp。还是直接scan比较直观。
: int minChange(String s) {
: int[] countABackword = new int[s.length() + 1];
: countABackword[s.length()] = 0;
: for (int i = s.length() - 1; i >= 0; i--) {
: char c = s.charAt(i);
: countABackword[i] = c == 'a' ? countABackword[i + 1] + 1
: : countABackword[i + 1];
: }
|
l*n
发帖数: 529 | 13 就是假设当前位置是最后一个a，剩下全是b，因为无论如何前段跟后段总是有个分界线
的。加上-1位为a(即0~n-1都改成b)和n位为b(0~n-1即都改成a),就是所有可能了。
【在 l****h 的大作中提到】
: 这个逻辑真么简单，居然是对的。
: 不过我还是没明白为什么是对的。
: 就是说，比较在所有b的位置：NUM=左边是b（包括该位置）的数目+右边是a的数目。最
: 小的NUM就是需要改字母的总数。
: 我就是想不明白这和原题为什么等价。
|
d**********x
发帖数: 4083 | 14 at each point, we have 3 choices:
change all a's to b
change all b's to a
change all b's on left to a's and change all a's on the right to b's
this implies if we know the number of a's b's on the left/right for each
point, we will know the best value for this point.
even better, we can actually do a dp. ( :D )
法针
【在 l****h 的大作中提到】
: 这个逻辑真么简单，居然是对的。
: 不过我还是没明白为什么是对的。
: 就是说，比较在所有b的位置：NUM=左边是b（包括该位置）的数目+右边是a的数目。最
: 小的NUM就是需要改字母的总数。
: 我就是想不明白这和原题为什么等价。
|
d**********x
发帖数: 4083 | 15 we can do a dp.
1. number of ops change all a's to b's >= number of ops change all a's to b'
s on the right hand of the first element.
2. number of ops change all b's to a's >= number of ops change all b's to a'
s on the left hand of the last element.
3. so we need only consider the min value of change all left hands to a and
change all right hands to b for each element.
4. starting with the first element, we count the number of a's on the right.
so it is opt[0]
5. consider opt[i] and opt[i+1]. if A[i] is a, A[i+1] is b, then opt[i+1]=
opt[i]; if A[i] is a and A[i+1] is a too, then opt[i+1]=opt[i]-1; bb, opt[i+
1]=opt[i]+1; ba, opt[i+1]=opt[i]
in summary opt[i+1]=opt[i] - (A[i+1]==a) + (A[i]==b)
so we can do a 1-dim dp, without any extra space.
【在 l*n 的大作中提到】
: 有递推关系的不是直接的min值，而是i左右的b字符和a字符个数，所以好像没有办法针
: 对min值做dp。还是直接scan比较直观。
: int minChange(String s) {
: int[] countABackword = new int[s.length() + 1];
: countABackword[s.length()] = 0;
: for (int i = s.length() - 1; i >= 0; i--) {
: char c = s.charAt(i);
: countABackword[i] = c == 'a' ? countABackword[i + 1] + 1
: : countABackword[i + 1];
: }
|
w*******e
发帖数: 395 | 16 你这个太晦涩难懂了
不就是，先从左到右，用opt[i]记录b的个数
然后从右到左，数a的个数的同时，记录下来“左边（包括i）的b的个数”和“右边（
包括i）a的个数”之和的最小值
最后的结果就是那个最小值减去1吗？
b'
a'
and
right.
【在 d**********x 的大作中提到】
: we can do a dp.
: 1. number of ops change all a's to b's >= number of ops change all a's to b'
: s on the right hand of the first element.
: 2. number of ops change all b's to a's >= number of ops change all b's to a'
: s on the left hand of the last element.
: 3. so we need only consider the min value of change all left hands to a and
: change all right hands to b for each element.
: 4. starting with the first element, we count the number of a's on the right.
: so it is opt[0]
: 5. consider opt[i] and opt[i+1]. if A[i] is a, A[i+1] is b, then opt[i+1]=
|
d**********x
发帖数: 4083 | 17 yes...
【在 w*******e 的大作中提到】
: 你这个太晦涩难懂了
: 不就是，先从左到右，用opt[i]记录b的个数
: 然后从右到左，数a的个数的同时，记录下来“左边（包括i）的b的个数”和“右边（
: 包括i）a的个数”之和的最小值
: 最后的结果就是那个最小值减去1吗？
:
: b'
: a'
: and
: right.
|
g*********e
发帖数: 14401 | 18
能说说题目啥意思吗？
aba -> aab?
bba -> abb?
aaabababbba -> aaaaaabbbbb ?
【在 w********s 的大作中提到】
: a替换成b，或者b替换成a，算1次，
: 给出一个string，比如aaabababbba
: 问最少替换几次能变成左边都是a，右边都是b的那种？
: 举个例子，
: aba，替换1次，变成aaa
: bba，替换一次，变成bbb
: aaba，替换1次，变成aabb
: 。。。。。。。。。。
|
z*****5
发帖数: 38 | 19 其实就是找到一个分界点，计算分界点左边的字母全变成a，右边的字母全变成b的花费
。该分界点可以从左到右一个一个试。一维DP问题。
比如aaabababbba，分界点从最左边开始，此时结果须为bbbbbbbbbbb.6个替换数。
然后分界点右移一位，此时结果为abbbbbbbbbb，5个替换数。
然后试aabbbbbbbbb,4个替换数。
然后试aaabbbbbbbb，3个替换数
然后试aaaabbbbbbb，4个替换数
然后试aaaaabbbbbb，3个替换数
。。。
替换数的变化是有规律的，每次分界点右移时，如果移进来的当前位是a，则替换数-1
，如果是b，则替换数+1.
所以不需要额外空间，只需一个变量存储当前最小替换数就行了。时间是O(n） |
z****s
发帖数: 409 | |
|
|
c********p
发帖数: 1969 | |
l****h
发帖数: 1189 | 22 真清楚，谢了。
1
【在 z*****5 的大作中提到】
: 其实就是找到一个分界点，计算分界点左边的字母全变成a，右边的字母全变成b的花费
: 。该分界点可以从左到右一个一个试。一维DP问题。
: 比如aaabababbba，分界点从最左边开始，此时结果须为bbbbbbbbbbb.6个替换数。
: 然后分界点右移一位，此时结果为abbbbbbbbbb，5个替换数。
: 然后试aabbbbbbbbb,4个替换数。
: 然后试aaabbbbbbbb，3个替换数
: 然后试aaaabbbbbbb，4个替换数
: 然后试aaaaabbbbbb，3个替换数
: 。。。
: 替换数的变化是有规律的，每次分界点右移时，如果移进来的当前位是a，则替换数-1
|
l*********u
发帖数: 19053 | 23 应该前后同时对扫。前面从第一个b开始，后面从第一个a开始。扫到碰上。
【在 D**********d 的大作中提到】
: 从前往后扫一遍，记录前面若全部变成 a 的替换数，与全部变成 b 的替换数。
: 从后往前扫一遍，记录后面若全部变成 a 的替换数，与全部变成 b 的替换数。
: 再扫一遍，对每个位置比较这四个数字，找最小的。
: 可以再优化:
: 1. 只记录全部变成 a 的替换数
: 2. 在扫第二遍时就找最小值。
|
