在比赛中有人问我这个问题。给定仅包含M和L的字符串，我们可以将任何“ M”更改为“ L”或将任何“ L”更改为“ M”。该函数的目的是计算为了达到所需的最长M间隔长度K而必须进行的最少更改。例如，给定S =“ MLMMLLM”并且K = 3，该函数应返回1。我们可以更改位置4的字母（从0开始计数）以获得“ MLMMMLM”，其中字母“ M”的最长间隔恰好是三个字符长。再举一个例子，给定S =“ MLMMMLMMMM”和K = 2，该函数应返回2。例如，我们可以修改位置2和7处的字母，以获得满足所需属性的字符串“ MLLMMLMLMM”。这是我到目前为止尝试过的方法，但是我没有得到正确的输出：我遍历字符串，并且只要最长的字符数超过K，就用L代替M。public static int solution(String S, int K) { StringBuilder Str = new StringBuilder(S); int longest=0;int minCount=0; for(int i=0;i<Str.length();i++){ char curr=S.charAt(i); if(curr=='M'){ longest=longest+1; if(longest>K){ Str.setCharAt(i, 'L'); minCount=minCount+1; } } if(curr=='L') longest=0; } if(longest < K){ longest=0;int indexoflongest=0;minCount=0; for(int i=0;i<Str.length();i++){ char curr=S.charAt(i); if(curr=='M'){ longest=longest+1; indexoflongest=i; } if(curr=='L') longest=0; } Str.setCharAt(indexoflongest, 'M'); minCount=minCount+1; } return minCount;}
3 回答
Helenr
TA贡献1780条经验 获得超4个赞
int
process_data(const char *m, int k)
{
int m_cnt = 0, c_cnt = 0;
char ch;
const char *st = m;
int inc_cnt = -1;
int dec_cnt = -1;
while((ch = *m++) != 0) {
if (m_cnt++ < k) {
c_cnt += ch == 'M' ? 0 : 1;
if ((m_cnt == k) && (
(inc_cnt == -1) || (inc_cnt > c_cnt))) {
inc_cnt = c_cnt;
}
}
else if (ch == 'M') {
if (*st++ == 'M') {
/*
* losing & gaining M carries no change provided
* there is atleast one L in the chunk. (c_cnt != 0)
* Else it implies stretch of Ms
*/
if (c_cnt <= 0) {
int t;
c_cnt--;
/*
* compute min inserts needed to brak the
* stretch to meet max of k.
*/
t = (k - c_cnt) / (k+1);
dec_cnt += t;
}
}
else {
ASSERT(c_cnt > 0, "expect c_cnt(%d) > 0", c_cnt);
ASSERT(inc_cnt != -1, "expect inc_cnt(%d) != -1", inc_cnt);
/* Losing L and gaining M */
if (--c_cnt < inc_cnt) {
inc_cnt = c_cnt;
}
}
}
else {
if (c_cnt <= 0) {
/*
* take this as a first break and restart
* as any further addition of M should not
* happen. Ignore this L
*/
st = m;
c_cnt = 0;
m_cnt = 0;
}
else if (*st++ == 'M') {
/* losing m & gaining l */
c_cnt++;
}
else {
// losing & gaining L; no change
}
}
}
return dec_cnt != -1 ? dec_cnt : inc_cnt;
}
倚天杖
TA贡献1828条经验 获得超3个赞
更正的代码：
int
process_data(const char *m, int k)
{
int m_cnt = 0, c_cnt = 0;
char ch;
const char *st = m;
int inc_cnt = -1;
int dec_cnt = -1;
while((ch = *m++) != 0) {
if (m_cnt++ < k) {
c_cnt += ch == 'M' ? 0 : 1;
if ((m_cnt == k) && (
(inc_cnt == -1) || (inc_cnt > c_cnt))) {
inc_cnt = c_cnt;
}
}
else if (ch == 'M') {
if (*st++ == 'M') {
/*
* losing & gaining M carries no change provided
* there is atleast one L in the chunk. (c_cnt != 0)
* Else it implies stretch of Ms
*/
if (c_cnt <= 0) {
c_cnt--;
}
}
else {
ASSERT(c_cnt > 0, "expect c_cnt(%d) > 0", c_cnt);
ASSERT(inc_cnt != -1, "expect inc_cnt(%d) != -1", inc_cnt);
/* Losing L and gaining M */
if (--c_cnt < inc_cnt) {
inc_cnt = c_cnt;
}
}
}
else {
if (c_cnt <= 0) {
/*
* compute min inserts needed to brak the
* stretch to meet max of k.
*/
dec_cnt += (dec_cnt == -1 ? 1 : 0) + ((k - c_cnt) / (k+1));
/*
* take this as a first break and restart
* as any further addition of M should not
* happen. Ignore this L
*/
st = m;
c_cnt = 0;
m_cnt = 0;
}
else if (*st++ == 'M') {
/* losing m & gaining l */
c_cnt++;
}
else {
// losing & gaining L; no change
}
}
}
if (c_cnt <= 0) {
/*
* compute min inserts needed to brak the
* stretch to meet max of k.
*/
dec_cnt += (dec_cnt == -1 ? 1 : 0) + ((k - c_cnt) / (k+1));
}
return dec_cnt != -1 ? dec_cnt : inc_cnt;
}
- 3 回答
- 0 关注
- 177 浏览
添加回答
举报
0/150
提交
取消