Наивный сжатия строку


Описание:

Реализовать метод для выполнения основных сжатие с помощью графов повторяющихся символов. Если сжатая строка не меньше, затем вернитесь в исходную строку.

Код:

class Main {
  public static String compress(String in) {
    if (in == null) {
      throw new IllegalArgumentException("Input string cannot be null");
    }
    if (in.length() <= 1) {
      return in;
    }
    StringBuffer out = new StringBuffer();
    int count = 1;
    for (int i = 1; i < in.length(); i++) {
      char current  = in.charAt(i);
      char previous = in.charAt(i - 1);

      if (current == previous) {
        count++;
      }
      else {
        out.append(previous);
        out.append(count);
        count = 1;
      }
    }
    out.append(in.charAt(in.length() - 1));
    out.append(count);
    return out.toString().length() < in.length() ? out.toString() : in;
  }

  public static void main(String[] args) {
    try {
      System.out.println("Should not happen: " + compress(null));
    } catch (IllegalArgumentException e) {
      System.out.println("Got expected exception for null");
    }
    System.out.println(compress("").equals(""));
    System.out.println(compress("a").equals("a"));
    System.out.println(compress("ab").equals("ab"));
    System.out.println(compress("aa").equals("aa"));
    System.out.println(compress("aabcccccaaa").equals("a2b1c5a3"));
    System.out.println(compress("aabb").equals("aabb"));
  }
}

Вопрос:

Решение только основываясь на интуиции. Последнее добавление было сделано методом проб и ошибок, которая мне не нравится (может быть, я больше нервничать во время настоящего собеседования). Я хотел бы знать, если есть способ, чтобы избежать подобных ошибок, возможно, используя инварианты циклов?



Комментарии
2 ответа

Главная проблема ММО в том, что вы впихиваете все в один метод, который не полезно для упорядочивания мыслей.

Когда я попытался это для сравнения, я придумал следующую в псевдо код:

// outer logic
compress(s)
rle = doRunLengthEncoding(s)
if rle.length < s.length return rle
else return s

// base algorithm
doRunLengthEncoding(s)
res = empty String buffer
char[] characters = s.toCharArray
int startIndex = 0
while startIndex < characters.length
int endIndex = findEndOfCurrentSequence(startIndex, characters)
res.append(currentChar).append(endIndex - startIndex)
startIndex = endIndex
return res

// return the first index i, where c[i] != c[start], return
// c.length if there is no such index
findEndOfCurrentSequence(start, c)
... // simple enough

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

Кстати: с точки зрения интервьюера (по крайней мере, я вы хотите, чтобы в моей команде в моей стране ;-)) продуманный алгоритм псевдокод стоит больше, чем рабочий код. Если вы будете применять для программиста на работу, я только предполагаю, что у вас есть базовые навыки, чтобы использовать IDE, и пинать какого-то куска кода, пока он не компилируется и выдает правильный результат. То, что я ищу организована мысли и навыков решения проблем.

Одна последняя вещь: существует одно и только одно правильное исключение, чтобы бросить на нулевой параметр, который не должен быть нулем: исключение NullPointerException. В идеале просто с помощью объектов.requireNonNull.

1
ответ дан 28 марта 2018 в 06:03 Источник Поделиться


  • Если ваш цикл работает, сравнивая каждый символ на символ, который предшествует его, единственный способ, чтобы избежать дублирования последнее добавление было бы запустить цикл еще раз, т. е. сделать условие остановки i <= in.length() вместо i < in.length()и назначение current значение по умолчанию в случае i == in.length(). Проблема с этим подходом заключается в том, что он не будет работать, если последний символ строки совпадает с этим персонажем по умолчанию.

    Так что вы, вероятно, придется переделать цикл так, что она сравнивает каждый символ на символ, который следует за ним. Если следующий символ соответствует текущему символу, затем count увеличивается, а если нет, или если нет следующего характера, то текущий символ будет добавляться, затем его считать. Для этого, вам нужно будет инициализировать i для 0 вместо 1. Это также позаботиться о специальном случае, если входная строка имеет значение только одного символа.


  • Кроме того, вы используете StringBuffer даже если синхронизации не актуален в коде. Вы могли бы рассмотреть с помощью StringBuilder вместо этого, который имеет те же функциональные возможности, как StringBuffer но не синхронизированы и, следовательно, быстрее.

  • Наконец, в return заявление compress(String)можно сначала преобразовать out к String прежде чем определить его длину. Это не нужно, потому что StringBuffer/StringBuilder также имеет length() метод, который вы можете позвонить напрямую.

1
ответ дан 29 марта 2018 в 09:03 Источник Поделиться