w*s
2 楼
a替换成b,或者b替换成a,算1次,
给出一个string,比如aaabababbba
问最少替换几次能变成左边都是a,右边都是b的那种?
举个例子,
aba,替换1次,变成aaa
bba,替换一次,变成bbb
aaba,替换1次,变成aabb
。。。。。。。。。。
给出一个string,比如aaabababbba
问最少替换几次能变成左边都是a,右边都是b的那种?
举个例子,
aba,替换1次,变成aaa
bba,替换一次,变成bbb
aaba,替换1次,变成aabb
。。。。。。。。。。
p*3
3 楼
should cut CBAK when it broke $2.75. Now I have to join WU Bang. Anyone
still has CBAK? No idea how low it will go before it pops up.
still has CBAK? No idea how low it will go before it pops up.
h*e
4 楼
【 以下文字转载自 Military 讨论区 】
发信人: dongbeiren2 (Light be with you.), 信区: Military
标 题: 鸭子不会就是秦火火吧
发信站: BBS 未名空间站 (Sun Aug 25 22:41:08 2013, 美东)
自打秦进去以后, 就再没见鸭子来
或者是立二?
发信人: dongbeiren2 (Light be with you.), 信区: Military
标 题: 鸭子不会就是秦火火吧
发信站: BBS 未名空间站 (Sun Aug 25 22:41:08 2013, 美东)
自打秦进去以后, 就再没见鸭子来
或者是立二?
l*6
6 楼
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;
}
{
int strSiz = src.size();
if(strSiz < 2)
return 0;
int ret = strSiz;
vector
vector
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;
}
H*g
8 楼
赶紧在各版发贴澄清
u*k
9 楼
被border 玩了一把的同时还错过了另一个窗口的$15
可恶的border
可恶的border
D*d
10 楼
从前往后扫一遍,记录前面若全部变成 a 的替换数,与全部变成 b 的替换数。
从后往前扫一遍,记录后面若全部变成 a 的替换数,与全部变成 b 的替换数。
再扫一遍,对每个位置比较这四个数字,找最小的。
可以再优化:
1. 只记录全部变成 a 的替换数
2. 在扫第二遍时就找最小值。
从后往前扫一遍,记录后面若全部变成 a 的替换数,与全部变成 b 的替换数。
再扫一遍,对每个位置比较这四个数字,找最小的。
可以再优化:
1. 只记录全部变成 a 的替换数
2. 在扫第二遍时就找最小值。
p*3
11 楼
I have 4000 shares of CBAK. Hope it will not break $2.
r*j
14 楼
可以看做选哪个位置开始由a->b。
从后到前扫一遍,对于每个b记录已经遇见了多少个a,也就是把当前b当做第一个b,需
要把多少个a变成b。
从前往后扫一遍,对于每个b记录已经遇见了多少个b,也就是把当前b当做第一个b,需
要把多少个b变成a。
把每个b的这个两个值相加,求最小。
从后到前扫一遍,对于每个b记录已经遇见了多少个a,也就是把当前b当做第一个b,需
要把多少个a变成b。
从前往后扫一遍,对于每个b记录已经遇见了多少个b,也就是把当前b当做第一个b,需
要把多少个b变成a。
把每个b的这个两个值相加,求最小。
i*c
15 楼
I haven't played low price stocks for more than a half year.
r*j
18 楼
这个不行
baabbba
y*g
20 楼
BORDERS太...
P*r
23 楼
展开说说?
P*r
24 楼
展开说说?
l*n
26 楼
有递推关系的不是直接的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 的大作中提到】
: 展开说说?
对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
27 楼
这个逻辑真么简单,居然是对的。
不过我还是没明白为什么是对的。
就是说,比较在所有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];
: }
不过我还是没明白为什么是对的。
就是说,比较在所有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
28 楼
赞,简单明了。
【在 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 的大作中提到】
: 有递推关系的不是直接的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];
: }
d*x
30 楼
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就是需要改字母的总数。
: 我就是想不明白这和原题为什么等价。
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
31 楼
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];
: }
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
32 楼
你这个太晦涩难懂了
不就是,先从左到右,用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]=
不就是,先从左到右,用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]=
z*5
35 楼
其实就是找到一个分界点,计算分界点左边的字母全变成a,右边的字母全变成b的花费
。该分界点可以从左到右一个一个试。一维DP问题。
比如aaabababbba,分界点从最左边开始,此时结果须为bbbbbbbbbbb.6个替换数。
然后分界点右移一位,此时结果为abbbbbbbbbb,5个替换数。
然后试aabbbbbbbbb,4个替换数。
然后试aaabbbbbbbb,3个替换数
然后试aaaabbbbbbb,4个替换数
然后试aaaaabbbbbb,3个替换数
。。。
替换数的变化是有规律的,每次分界点右移时,如果移进来的当前位是a,则替换数-1
,如果是b,则替换数+1.
所以不需要额外空间,只需一个变量存储当前最小替换数就行了。时间是O(n)
。该分界点可以从左到右一个一个试。一维DP问题。
比如aaabababbba,分界点从最左边开始,此时结果须为bbbbbbbbbbb.6个替换数。
然后分界点右移一位,此时结果为abbbbbbbbbb,5个替换数。
然后试aabbbbbbbbb,4个替换数。
然后试aaabbbbbbbb,3个替换数
然后试aaaabbbbbbb,4个替换数
然后试aaaaabbbbbb,3个替换数
。。。
替换数的变化是有规律的,每次分界点右移时,如果移进来的当前位是a,则替换数-1
,如果是b,则替换数+1.
所以不需要额外空间,只需一个变量存储当前最小替换数就行了。时间是O(n)
z*s
36 楼
O(n)的水题,至于讨论的热火朝天吗?
c*p
37 楼
mark
l*h
38 楼
真清楚,谢了。
1
【在 z*****5 的大作中提到】
: 其实就是找到一个分界点,计算分界点左边的字母全变成a,右边的字母全变成b的花费
: 。该分界点可以从左到右一个一个试。一维DP问题。
: 比如aaabababbba,分界点从最左边开始,此时结果须为bbbbbbbbbbb.6个替换数。
: 然后分界点右移一位,此时结果为abbbbbbbbbb,5个替换数。
: 然后试aabbbbbbbbb,4个替换数。
: 然后试aaabbbbbbbb,3个替换数
: 然后试aaaabbbbbbb,4个替换数
: 然后试aaaaabbbbbb,3个替换数
: 。。。
: 替换数的变化是有规律的,每次分界点右移时,如果移进来的当前位是a,则替换数-1
1
【在 z*****5 的大作中提到】
: 其实就是找到一个分界点,计算分界点左边的字母全变成a,右边的字母全变成b的花费
: 。该分界点可以从左到右一个一个试。一维DP问题。
: 比如aaabababbba,分界点从最左边开始,此时结果须为bbbbbbbbbbb.6个替换数。
: 然后分界点右移一位,此时结果为abbbbbbbbbb,5个替换数。
: 然后试aabbbbbbbbb,4个替换数。
: 然后试aaabbbbbbbb,3个替换数
: 然后试aaaabbbbbbb,4个替换数
: 然后试aaaaabbbbbb,3个替换数
: 。。。
: 替换数的变化是有规律的,每次分界点右移时,如果移进来的当前位是a,则替换数-1
相关阅读
聘请司机兼伴游$200一天8.15~8.19(有修改) (转载)铁道部:恢复通车后上座率117% 乘客心态稳定 记者: 最后一节仅2人 (转载)银行抢劫国内人民真幽默这货是如何上去的?婷婷足协牛啊摄影师借口说姿势不对 18+i am falling in love (转载)女征男NY拆弹遇到过最牛的验证码了 能把人弄晕过去 你试试?此生纵有千年寿,尽献苍生作党臣 (转载)你信么?被删掉的微博真有意思 (转载)动车相撞的那一个瞬间从仿生学看,也可以考虑把火车都设计成人体的形状 (转载)果汁分你一半=。=也许是可乐吧。Re: 挪威的恐怖分子 (转载)一个牛人制作的关于中国动车事故的视频!关于中国动车事故的视频!