Redian新闻
>
鸭子不会就是秦火火吧 (转载)
avatar
w*s
2
a替换成b,或者b替换成a,算1次,
给出一个string,比如aaabababbba
问最少替换几次能变成左边都是a,右边都是b的那种?
举个例子,
aba,替换1次,变成aaa
bba,替换一次,变成bbb
aaba,替换1次,变成aabb
。。。。。。。。。。
avatar
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.
avatar
h*e
4
【 以下文字转载自 Military 讨论区 】
发信人: dongbeiren2 (Light be with you.), 信区: Military
标 题: 鸭子不会就是秦火火吧
发信站: BBS 未名空间站 (Sun Aug 25 22:41:08 2013, 美东)
自打秦进去以后, 就再没见鸭子来
或者是立二?
avatar
a*t
5
还不如去断背

【在 u*********k 的大作中提到】
: 就等好deal
avatar
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;
}
avatar
n*n
7
% matters. 3k is not so big.

【在 p******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.

avatar
H*g
8
赶紧在各版发贴澄清
avatar
u*k
9
被border 玩了一把的同时还错过了另一个窗口的$15
可恶的border
avatar
D*d
10
从前往后扫一遍,记录前面若全部变成 a 的替换数,与全部变成 b 的替换数。
从后往前扫一遍,记录后面若全部变成 a 的替换数,与全部变成 b 的替换数。
再扫一遍,对每个位置比较这四个数字,找最小的。
可以再优化:
1. 只记录全部变成 a 的替换数
2. 在扫第二遍时就找最小值。
avatar
p*3
11
I have 4000 shares of CBAK. Hope it will not break $2.
avatar
m*d
12
不可能
鸭子不用嫖妓

【在 h***e 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: dongbeiren2 (Light be with you.), 信区: Military
: 标 题: 鸭子不会就是秦火火吧
: 发信站: BBS 未名空间站 (Sun Aug 25 22:41:08 2013, 美东)
: 自打秦进去以后, 就再没见鸭子来
: 或者是立二?

avatar
a*t
13
what is $15?

【在 u*********k 的大作中提到】
: 被border 玩了一把的同时还错过了另一个窗口的$15
: 可恶的border

avatar
r*j
14
可以看做选哪个位置开始由a->b。
从后到前扫一遍,对于每个b记录已经遇见了多少个a,也就是把当前b当做第一个b,需
要把多少个a变成b。
从前往后扫一遍,对于每个b记录已经遇见了多少个b,也就是把当前b当做第一个b,需
要把多少个b变成a。
把每个b的这个两个值相加,求最小。
avatar
i*c
15
I haven't played low price stocks for more than a half year.
avatar
h*e
16
why? 你展开讲讲

【在 m**d 的大作中提到】
: 不可能
: 鸭子不用嫖妓

avatar
u*k
17
ebay上一个巨便宜的 flash drive BIN,慢了一步被人抢走了

【在 a**********t 的大作中提到】
: what is $15?
avatar
r*j
18

这个不行
baabbba
avatar
H*g
19
我觉得是说鸭子是公公

【在 h***e 的大作中提到】
: why? 你展开讲讲
avatar
y*g
20
BORDERS太...
avatar
P*r
21
好像不太对。
如果是aaaabaaaa呢?
答案应该是1,按你的做法是不是3?

【在 r******j 的大作中提到】
: 可以看做选哪个位置开始由a->b。
: 从后到前扫一遍,对于每个b记录已经遇见了多少个a,也就是把当前b当做第一个b,需
: 要把多少个a变成b。
: 从前往后扫一遍,对于每个b记录已经遇见了多少个b,也就是把当前b当做第一个b,需
: 要把多少个b变成a。
: 把每个b的这个两个值相加,求最小。

avatar
h*e
22
哦,还是曼德了解鸭子

【在 H********g 的大作中提到】
: 我觉得是说鸭子是公公
avatar
P*r
23
展开说说?
avatar
P*r
24
展开说说?
avatar
r*j
25

恩,你说的是对的。
是不是应该再考虑一种情况,就是全是a的,相当于把b的起始点选在最后。

【在 P*******r 的大作中提到】
: 好像不太对。
: 如果是aaaabaaaa呢?
: 答案应该是1,按你的做法是不是3?

avatar
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 的大作中提到】
: 展开说说?
avatar
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];
: }

avatar
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];
: }

avatar
l*n
29
就是假设当前位置是最后一个a,剩下全是b,因为无论如何前段跟后段总是有个分界线
的。加上-1位为a(即0~n-1都改成b)和n位为b(0~n-1即都改成a),就是所有可能了。

【在 l****h 的大作中提到】
: 这个逻辑真么简单,居然是对的。
: 不过我还是没明白为什么是对的。
: 就是说,比较在所有b的位置:NUM=左边是b(包括该位置)的数目+右边是a的数目。最
: 小的NUM就是需要改字母的总数。
: 我就是想不明白这和原题为什么等价。

avatar
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就是需要改字母的总数。
: 我就是想不明白这和原题为什么等价。

avatar
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];
: }

avatar
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]=

avatar
d*x
33
yes...

【在 w*******e 的大作中提到】
: 你这个太晦涩难懂了
: 不就是,先从左到右,用opt[i]记录b的个数
: 然后从右到左,数a的个数的同时,记录下来“左边(包括i)的b的个数”和“右边(
: 包括i)a的个数”之和的最小值
: 最后的结果就是那个最小值减去1吗?
:
: b'
: a'
: and
: right.

avatar
g*e
34

能说说题目啥意思吗?
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
: 。。。。。。。。。。

avatar
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)
avatar
z*s
36
O(n)的水题,至于讨论的热火朝天吗?
avatar
c*p
37
mark
avatar
l*h
38
真清楚,谢了。

1

【在 z*****5 的大作中提到】
: 其实就是找到一个分界点,计算分界点左边的字母全变成a,右边的字母全变成b的花费
: 。该分界点可以从左到右一个一个试。一维DP问题。
: 比如aaabababbba,分界点从最左边开始,此时结果须为bbbbbbbbbbb.6个替换数。
: 然后分界点右移一位,此时结果为abbbbbbbbbb,5个替换数。
: 然后试aabbbbbbbbb,4个替换数。
: 然后试aaabbbbbbbb,3个替换数
: 然后试aaaabbbbbbb,4个替换数
: 然后试aaaaabbbbbb,3个替换数
: 。。。
: 替换数的变化是有规律的,每次分界点右移时,如果移进来的当前位是a,则替换数-1

avatar
l*u
39
应该前后同时对扫。前面从第一个b开始,后面从第一个a开始。扫到碰上。

【在 D**********d 的大作中提到】
: 从前往后扫一遍,记录前面若全部变成 a 的替换数,与全部变成 b 的替换数。
: 从后往前扫一遍,记录后面若全部变成 a 的替换数,与全部变成 b 的替换数。
: 再扫一遍,对每个位置比较这四个数字,找最小的。
: 可以再优化:
: 1. 只记录全部变成 a 的替换数
: 2. 在扫第二遍时就找最小值。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。