在比賽中有人問我這個(gè)問題。給定僅包含M和L的字符串，我們可以將任何“ M”更改為“ L”或?qū)⑷魏巍?L”更改為“ M”。該函數(shù)的目的是計(jì)算為了達(dá)到所需的最長M間隔長度K而必須進(jìn)行的最少更改。例如，給定S =“ MLMMLLM”并且K = 3，該函數(shù)應(yīng)返回1。我們可以更改位置4的字母（從0開始計(jì)數(shù)）以獲得“ MLMMMLM”，其中字母“ M”的最長間隔恰好是三個(gè)字符長。再舉一個(gè)例子，給定S =“ MLMMMLMMMM”和K = 2，該函數(shù)應(yīng)返回2。例如，我們可以修改位置2和7處的字母，以獲得滿足所需屬性的字符串“ MLLMMLMLMM”。這是我到目前為止嘗試過的方法，但是我沒有得到正確的輸出：我遍歷字符串，并且只要最長的字符數(shù)超過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貢獻(xiàn)1780條經(jīng)驗(yàn) 獲得超4個(gè)贊
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貢獻(xiàn)1828條經(jīng)驗(yàn) 獲得超3個(gè)贊
更正的代碼：
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 關(guān)注
- 195 瀏覽
添加回答
舉報(bào)
0/150
提交
取消