Подпоследовательность в последовательности чисел в scala

Question

Подпоследовательность в последовательности чисел в scala

Вы должны указать тип материала в ответе. Я использую аннотацию @GetMapping с результатами = MediaType.IMAGE_JPEG_VALUE. @RequestMapping будет работать одинаково.

@GetMapping(value="/current/chart",produces = MediaType.IMAGE_JPEG_VALUE)
@ResponseBody
public byte[] getChart() {
    return ...;
}

Без типа носителя трудно догадаться, что на самом деле возвращается (включая любого, кто читает код, браузер и, конечно же, сама Весна). Байт [] просто не определен. Единственный способ определить тип носителя из байта [] - это обнюхивание и угадывание вокруг.

Предоставление типа носителя - это наилучшая практика

0

scala

задан S.H 1 March 2019 в 01:35

3 ответа

Другие вопросы по тегам:

scala

Похожие вопросы:

score 0 · Answer 1

[Обновление в ответ на обновленный вопрос]

[Спасибо @jwvh за обнаружение ошибки в оригинальной версии]

Этот метод сгенерирует все возможные подпоследовательности a List:

def subsequences[T](list: List[T]): List[List[T]] =
  list match {
    case Nil =>
      List(List())
    case hd :: tl =>
      val subs = subsequences(tl)

      subs.map(hd +: _) ++ subs
  }

Обратите внимание, что это неэффективно по ряду причин, поэтому это не хороший способ решить «проблему наибольшей возрастающей подпоследовательности».

[Оригинальный ответ]

Эта функция будет генерировать все непустые непрерывные подпоследовательности любой последовательности:

 def subsequences[T](seq: Seq[T]) =
   seq.tails.flatMap(_.inits).filter(_.nonEmpty)

Возвращает [114 ] поэтому он создает каждую подпоследовательность по очереди, что уменьшает использование памяти.

Обратите внимание, что это сгенерирует все подпоследовательности и сохранит порядок значений, в отличие от решений, использующих combinations или Set.

Вы можете использовать это в своей «самой длинной возрастающей проблеме подпоследовательности», например:

def isAscending(seq: Seq[Int]): Boolean =
  seq.length <= 1 || seq.sliding(2).forall(x => x(0) < x(1))

subsequences(a).filter(isAscending).maxBy(_.length)

Результатом будет самая длинная последовательность возрастающих значений на входе a.

score 0 · Answer 2

Если они не упорядочены (например, Array(3, 1) совпадает с Array(1, 3)) и если в числах нет повторений, вы можете использовать subsets.

val a = Array(4, 3, 1)
val s = a.toSet.subsets.filter(_.nonEmpty).toList

println(s) // List(Set(4), Set(3), Set(1), Set(4, 3), Set(4, 1), Set(3, 1), Set(4, 3, 1))

Но это довольно сильные предположения, поэтому дайте мне знать, если одно из них не выполняется.

score 0 · Answer 3

Вы хотите, чтобы все combinations() от 1 до длины массива.

val arr = Array(4, 3, 1)

arr.indices.flatMap(x => arr.combinations(x + 1))
//res0: Seq[Array[Int]] = Vector(Array(4), Array(3), Array(1), Array(4, 3), Array(4, 1), Array(3, 1), Array(4, 3, 1))

update

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

def subseqs[A](seq :Seq[A]) :List[Seq[A]] = seq match {
  case hd +: tl =>
    val res = subseqs(tl)
    Seq(hd) :: res ++ res.map(hd +: _)
  case Seq() => Nil
}

Результатом является List из n ^ 2 - 1 возможных подпоследовательностей. Таким образом, для набора из 8 элементов вы получите 255 подпоследовательностей.

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

Гораздо лучше генерировать только увеличивающиеся подпоследовательности и находить самые длинные из этого набора (9 строк кода).