минимальные операции, необходимые для того, чтобы сделать самый длинный символьный интервал равным K - PullRequest
0 голосов
/ 30 апреля 2018

Мне задали этот вопрос в конкурсе. Учитывая строку, содержащую только M и L, мы можем изменить любое «M» на «L» или любое «L» на «M». Цель этой функции - вычислить минимальное количество изменений, которые мы должны сделать, чтобы достичь желаемой максимальной длины М-интервала K.
Например, учитывая S = "MLMMLLM" и K = 3, функция должна вернуть 1. Мы можем изменить букву в позиции 4 (считая от 0), чтобы получить "MLMMMLM", в котором самый длинный интервал букв "M" равен ровно три символа в длину.

В другом примере, учитывая S = "MLMMMLMMMM" и K = 2, функция должна возвращать 2. Мы можем, например, изменить буквы в позициях 2 и 7, чтобы получить строку "MLLMMLMLMM", которая удовлетворяет желаемому свойство.

Вот что я пробовал до сих пор, но я не получаю правильный вывод: Я пересекаю строку и всякий раз, когда наибольшее число символов превышает K, я заменяю M на L в этой точке.

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 ]

0 голосов
/ 03 мая 2018
 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;
}
0 голосов
/ 04 мая 2018

Исправленный код:

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;
}
0 голосов
/ 30 апреля 2018

Этот алгоритм состоит из 2 частей, так как мы хотим получить самый длинный символьный интервал, равный K.

  1. У нас уже есть интервал> = K, поэтому теперь нам нужно соответствующим образом изменить некоторые символы, чтобы мы жадно меняли каждый (k + 1) -й символ и снова начинали считать с 0.

  2. Теперь, если интервал был меньше K, мне нужно будет запустить скользящее окно над массивом. Работая с этим окном, я в основном рассматриваю возможность преобразования всех L в M в этом окне длины K. Но это сопровождается побочным эффектом увеличения длины интервала, поскольку могут быть K вне, поэтому эта переменная (int nec) отслеживает тот. Так что теперь я должен также рассмотреть вопрос о преобразовании 2 возможных М вне окна (длина K) в L.

Вот полный исполняемый код на C ++. Хорошего дня.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <int> vi;
typedef pair<int, int> ii;



int change(string s, int k) {
    // handling interval >= k
    bool flag = false;
    int ans = 0;
    int cnt = 0;
    for(int i=0; i<s.size(); i++) {
        if(s[i] == 'M') cnt++;
        else cnt = 0;
        if(cnt == k) flag = true;
        if(cnt > k) s[i] = 'L', ans++, cnt = 0;
    }
    if(flag) return ans;

    // handling max interval < k
    // If the interval is too big.
    if(k > s.size()) {
        cerr << "Can't do it.\n"; exit(0);
    }

    // Sliding window
    cnt = 0;
    for(int i=0; i<k; i++) {
        if(s[i] == 'L') cnt++;
    }
    ans = cnt + (s[k] == 'M'); // new edit
    int nec = 0; // new edit
    for(int i=k; i<s.size(); i++) {
        if(s[i-k] == 'L') cnt--;
        if(s[i] == 'L') cnt++;
        nec = 0;
        if(i-k != 0 && s[i-k-1] == 'M')
            nec++;
        if(i < s.size()-1 && s[i+1] == 'M')
            nec++;
        ans = min(ans, cnt + nec);
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    string s;
    int k;

    cin >> s >> k;

    int ans = change(s, k);
    cout << ans << "\n";

    return 0;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...