Оптимальный алгоритм для декомпрессии этой строки - PullRequest
Новая
       2

Оптимальный алгоритм для декомпрессии этой строки

0 голосов
/ 10 апреля 2020

Я работал над упражнением из технического руководства Google. Он называется Сжатие и декомпрессия. Вы можете проверить следующую ссылку, чтобы получить описание проблемы Описание задачи .

Вот мой код для решения: 

public static String decompressV2 (String string, int start, int times) {
    String result = "";
    for (int i = 0; i < times; i++) {
        inner:
        {
            for (int j = start; j < string.length(); j++) {
                if (isNumeric(string.substring(j, j + 1))) {
                    String num = string.substring(j, j + 1);
                    int times2 = Integer.parseInt(num);
                    String temp = decompressV2(string, j + 2, times2);
                    result = result + temp;
                    int next_j = find_next(string, j + 2);
                    j = next_j;
                    continue;
                }
                if (string.substring(j, j + 1).equals("]")) {  // Si es un bracket cerrado
                    break inner;
                }

                result = result + string.substring(j,j+1);
            }
        }
    }
    return result;
}

public static int find_next(String string, int start) {
    int count = 0;
    for (int i = start; i < string.length(); i++) {
        if (string.substring(i, i+1).equals("[")) {
            count= count + 1;
        }
        if (string.substring(i, i +1).equals("]") && count> 0) {
            count = count- 1;
            continue;
        }
        if (string.substring(i, i +1).equals("]") && count== 0) {
            return i;
        }
    }
    return -111111;
}

Я немного объясню внутреннюю работу моего подхода. Это базовое c решение включает использование простой рекурсии и циклов.

Итак, начнем с простой декомпрессии: 

DevTech.decompressV2("2[3[a]b]", 0, 1);

Как видите, 0 указывает на то, что необходимо выполнить итерацию по строке с индексом 0, а 1 означает, что строка должна быть оценена только один раз: 1 [ 2 [3 [a] b] ]

Суть в том, что каждый раз, когда вы сталкиваетесь с числом, вы вызываете алгоритм снова (рекурсивно) и продолжаете там, где заканчивается строка в скобках, это функция find_next для.

Когда он находит закрывающие скобки, внутренние l oop разрывы, именно так я хочу сделать знак остановки.

Я думаю, что это будет основной идеей алгоритма, если вы внимательно прочитаете код, вы получите полная картина.

Итак, вот некоторые из моих опасений по поводу того, как я написал решение:

  • Я не смог найти более чистого решения, чтобы сказать алгоритму go следующий, если найдет число. Так что я как бы жестко запрограммировал его с помощью функции find_next. Есть ли способ сделать это более понятным в процессе декомпрессии c?
  • Что касается производительности, тратя много времени на повторение того же самого действия, когда у вас в начале число больше 1 скобки.
  • Я отношусь к программированию, поэтому, возможно, этот код также нуждается в улучшении не в идее, а в том, как она написана. Поэтому был бы очень признателен за некоторые предложения.
  • Это подход, который я выясняю, но я уверен, что есть еще пара, я не могу думать ни о ком, но было бы здорово, если бы вы могли высказать свои идеи .
  • В описании рассказывается о некоторых вещах, которые вам следует учитывать при разработке решений. Это: обработка неповторяющихся строк, обработка повторений внутри, не выполнение одной и той же работы дважды, не слишком много копируя. Охвачены ли они моим подходом?
  • И последнее замечание. Дело в тестовых случаях. Я знаю, что доверие очень важно при разработке решений, и лучший способ придать алгоритму уверенность - это тестовые случаи. Я попробовал несколько, и все они работали, как ожидалось. Но какие методы вы рекомендуете для разработки тестовых случаев. Есть ли какие-нибудь программы?

Так что это все, ребята, я новичок в сообществе, поэтому я открыт для предложений о том, как улучшить качество вопроса. Ура!

Ответы [ 2 ]

3 голосов
/ 10 апреля 2020

Ваше решение включает в себя большое количество копий строк, которые действительно замедляют его. Вместо того, чтобы возвращать строки, которые вы объединяете, вы должны передавать StringBuilder в каждый вызов и append подстроки на него.

Это означает, что вы можете использовать возвращаемое значение, чтобы указать позицию для продолжения сканирования.

Вы также анализируете повторяющиеся части исходной строки более одного раза.

Мое решение выглядит так: 

public static String decompress(String src)
{
    StringBuilder dest = new StringBuilder();
    _decomp2(dest, src, 0);
    return dest.toString();
}

private static int _decomp2(StringBuilder dest, String src, int pos)
{
    int num=0;
    while(pos < src.length()) {
        char c = src.charAt(pos++);
        if (c == ']') {
            break;
        }
        if (c>='0' && c<='9') {
            num = num*10 + (c-'0');
        } else if (c=='[') {
            int startlen = dest.length();
            pos = _decomp2(dest, src, pos);
            if (num<1) {
                // 0 repetitions -- delete it
                dest.setLength(startlen);
            } else {
                // copy output num-1 times
                int copyEnd = startlen + (num-1) * (dest.length()-startlen);
                for (int i=startlen; i<copyEnd; ++i) {
                    dest.append(dest.charAt(i));
                }
            }
            num=0;
        } else {
            // regular char
            dest.append(c);
            num=0;
        }
    }
    return pos;
}
1 голос
/ 10 апреля 2020

Я бы попытался вернуть кортеж, который также содержит следующий индекс, откуда должна продолжаться декомпрессия. Тогда у нас может быть рекурсия, которая объединяет текущую часть с остальной частью блока в текущей глубине рекурсии.

Вот код JavaScript. Нужно подумать, чтобы инкапсулировать порядок операций, который отражает правила. 

function f(s, i=0){
  if (i == s.length)
    return ['', i];
    
  // We might start with a multiplier
  let m = '';
  while (!isNaN(s[i]))
    m = m + s[i++];

  // If we have a multiplier, we'll
  // also have a nested expression
  if (s[i] == '['){
    let result = '';
    const [word, nextIdx] = f(s, i + 1);
    for (let j=0; j<Number(m); j++)
      result = result + word;
    const [rest, end] = f(s, nextIdx);
    return [result + rest, end]
  }
  
  // Otherwise, we may have a word,
  let word = '';
  while (isNaN(s[i]) && s[i] != ']' && i < s.length)
    word = word + s[i++];

  // followed by either the end of an expression
  // or another multiplier
  const [rest, end] = s[i] == ']' ? ['', i + 1] : f(s, i);
  return [word + rest, end];
}

var strs = [
 '2[3[a]b]',
  '10[a]',
  '3[abc]4[ab]c',
  '2[2[a]g2[r]]'
];

for (const s of strs){
  console.log(s);
  console.log(JSON.stringify(f(s)));
  console.log('');
}
...