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
相关阅读
求科普,高楼坠人能接住吗?这山。。。长成这样。。。中国版的honda CRV看着不错啊 (转载)萌图一:)口味重,慎入患上罕见睡眠性交症 英男子性侵少女获判无罪(图) (转载)今天车被撞了,心情低落,请教车祸理赔处理经验。 (转载)Johnny Depp?钻风V5should she date indians? (转载)原来修高铁是为了怕官老爷们坐飞机晚点 (转载)大家安慰我吧,7月5日晚被黑人袭击并性骚扰了 (转载)哥是党卫队的Re: 这样的文章也删,这里的版主板斧脑袋被夹了 (转载)Re: 她能产出有机的母乳吗 ?(转载)圣旨到!刚买的跑步机,试一试。。。我见过的最有特色和中国味十足的星巴克。。。京沪高铁贵宾候车室(图) (转载)老江上海时绝对人精 雄心勃勃一心想往上爬那种 (转载)